Xem mẫu
- HộiHội
Thảo Quốc
Thảo Gia
Quốc Gia2015
2015về
vềĐiện
Điện Tử,
Tử,Truyền
Truyền Thông vàCông
Thông và CôngNghệ
Nghệ Thông
Thông TinTin (ECIT
(ECIT 2015)
2015)
Về Một Phương Pháp Xây Dựng
Hệ Mật Mã Lai Ghép
Nguyễn Toàn Thắng1, Ngô Đức Thiện2
1
Nghiên cứu sinh, Học Viện Công Nghệ Bưu Chính Viễn Thông
2
Khoa Kỹ thuật Điện tử 1, Học Viện Công Nghệ Bưu Chính Viễn Thông
Email: thangnt20@gmail.com, thiennd@ptit.edu.vn
Tóm tắt— Cho đến nay các hệ mật khóa công khai thường trao đổi và thỏa thuận khóa Diffie-Hellman, hệ mật Omura-
được xây dựng trên các bài toán một chiều, tức là việc tính xuôi Massey, hệ mật và chữ ký số ElGamal...
(hay mã hóa) khá đơn giản, còn tính ngược (hay thám mã) là rất
khó. Bài toán logarit rời rạc là một trong các bài toán một chiều Cho đến này chưa có thuật toán hiệu quả nào để giải bài toán
khó và cho đến nay vẫn chưa có thuật toán hiệu quả nào để giải logarit rời rạc tổng quát. Có nhiều thuật toán phức tạp, thường
bài toán logarit rời rạc tổng quát. Bài báo này đề xuất một phương sinh ra từ những thuật toán tương tự như bài toán phân tích thừa
pháp xây dựng một hệ mật mã khóa bí mật lai ghép sử dụng hệ số, chúng chạy nhanh hơn các thuật toán thô sơ nhưng vẫn còn
mật Pohlig-Hellman kết hợp với sơ đồ Feistel, cùng với đó là một chậm hơn so với thời gian đa thức. Có thể kể đến một số thuật
số đánh giá về tính khuếch tán của hệ mật đề xuất này. toán như: Baby-step giant-step, Pollard, Pohlig-Hellman, COS,
Từ khóa— Mật mã khối, bài toán logarit rời rạc, hệ mật Pohlig-
tính toán chỉ số (index calculus)...
Hellman, sơ đồ Feistel. Với mục đích kết hợp ưu điểm của các hệ mật và sơ đồ mã
I. MỞ ĐẦU hóa đã có, bài báo này đề xuất một phương pháp xây dựng hệ
mật mã lai ghép, trong đó hàm mã hóa sử dụng phép mã hóa của
Trong mô hình mật mã cổ điển, thì Alice (người gửi) và Bob hệ mật Pohlig-Hellman và sơ đồ mã hóa theo mạng Feistel cân
(người nhận) chọn một khoá 𝑘𝑘 bí mật nào đó; sau đó dùng 𝑘𝑘 để bằng. Hệ mật mã lai ghép này bao gồm hai phép hoán vị và phép
tạo luật mã hoá 𝑒𝑒𝑘𝑘 và luật giải mã 𝑑𝑑𝑘𝑘 , luật giải mã 𝑑𝑑𝑘𝑘 hoặc giống tính hàm mũ theo modulo.
𝑒𝑒𝑘𝑘 hoặc dễ dàng nhận được từ nó. Các hệ mật này được gọi là
mật mã khoá bí mật (hoặc mật mã khóa đối xứng), nếu để lộ 𝑘𝑘 II. BÀI TOÁN LOGARIT RỜI RẠC VÀ HỆ MẬT
thì hệ thống mất an toàn. POHLIG-HELLMAN
Ý tưởng xây dựng một hệ mật khoá công khai (hay dùng A. Bài toán logarit rời rạc
chung) là tìm một hệ mật không có khả năng tính toán để xác Các phép tính logarit rời rạc là các phép logarit được thực
định 𝑑𝑑𝑘𝑘 khi biết 𝑒𝑒𝑘𝑘 . Nếu thực hiện được như vậy thì quy tắc mã hiện trên các nhóm nhân cyclic. Nếu 𝐺𝐺 là một nhóm nhân cyclic
hóa 𝑒𝑒𝑘𝑘 có thể được công khai bằng cách công bố nó trong một và 𝑔𝑔 là một phần tử sinh của 𝐺𝐺𝐺 thì theo tính chất của nhóm nhân
danh bạ (bởi vậy nên có thuật ngữ hệ mật khoá công khai). Ưu cyclic, ta thấy rằng mỗi phần tử 𝑦𝑦 trong 𝐺𝐺 có thể được tính bằng
điểm của hệ mật khoá công khai là ở chỗ Alice (hoặc bất kỳ ai) 𝑔𝑔𝑥𝑥 với một giá trị 𝑥𝑥 nào đó. Phép tính logarit rời rạc của 𝑦𝑦𝑦với
có thể gửi một bản tin đã mã hóa cho Bob (mà không cần thông cơ số 𝑔𝑔 sẽ cho kết quả là 𝑥𝑥.
tin trước về khoá mật) bằng cách dùng luật mã hóa công khai 𝑒𝑒𝑘𝑘 .
Người nhận Bob sẽ là người duy nhất có thể giải được bản mã Có thể tóm tắt bài toán logarit rời rạc như sau [1], [4]:
này bằng cách sử dụng luật giải bí mật 𝑑𝑑𝑘𝑘 của mình. Cho một vành số ℤ𝑝𝑝 , theo [1] nếu 𝑝𝑝 là nguyên tố thì ℤ𝑝𝑝 là
Ý tưởng về một hệ mật khoá công khai được Diffie và một trường (ℤ𝑝𝑝 = 𝐺𝐺𝐺𝐺(𝑝𝑝)). Tập tất cả các phần tử khác không
Hellman đưa ra vào năm 1976. Còn việc hiện thực hoá nó thì do của trường sẽ tạo nên một nhóm nhân cyclic ℤ∗𝑝𝑝 .
Rivesrt, Shamir và Adleman đưa ra lần đầu tiên vào năm 1977,
họ đã tạo nên hệ mật nổi tiếng RSA [7]. ℤ∗𝑝𝑝 = ℤ𝑝𝑝 /{0} = {1,2, … , 𝑝𝑝 𝑝 𝑝𝑝
Hàm mã khoá công khai 𝑒𝑒𝑘𝑘 của Bob phải là một hàm dễ tính
toán, song việc tìm hàm ngược (hàm giải mã) rất khó khăn (đối Cho 𝑔𝑔 𝑔 𝑔∗𝑝𝑝 là một phần tử sinh của nhóm nhân.
với bất kỳ ai không phải là Bob). Đặc tính dễ tính toán này Cho 𝑦𝑦 𝑦𝑦𝑝𝑝∗ , yêu cầu hãy tìm 𝑥𝑥 (nếu tồn tại) sao cho:
thường được gọi là đặc tính một chiều, và điều kiện cần thiết là 𝑔𝑔 𝑥𝑥 = 𝑦𝑦, tức là: 𝑥𝑥 𝑥 𝑥𝑥𝑥 𝑔𝑔 𝑦𝑦.
𝑒𝑒𝑘𝑘 phải là hàm một chiều (tính thuận đơn giản, nhưng tính ngược
rất khó) [1], [7]. Nhận xét: ∀𝑦𝑦 𝑦𝑦∗𝑝𝑝 thì [1]:
Một trong các hàm một chiều được sử dụng nhiều trong các Bài toán có nghiệm khi 𝑔𝑔 là phần tử nguyên thủy.
hệ mật khóa công khai đó là bài toán logarit rời rạc [2], [7]. Có
thể kể đến các hệ mật khóa công khai sử dụng bài toán này như: Bài toán có thể không có nghiệm khi 𝑔𝑔 bất kỳ.
ISBN: 978-604-67-0635-9 227
227
- HộiHội
Thảo Quốc
Thảo Gia
Quốc 2015
Gia 2015về
vềĐiện
ĐiệnTử,
Tử,Truyền
TruyềnThông và Công
Thông và CôngNghệ
NghệThông
ThôngTinTin (ECIT
(ECIT 2015)
2015)
Ví dụ: Xét 𝑝𝑝 𝑝 19 và 𝑔𝑔 𝑔 𝑔 là phần tử nguyên thủy của 𝑚𝑚𝑚𝑚𝑚 𝑑𝑑 mod 𝑝𝑝
∗
nhóm nhân ℤ19 , ta có các giá trị 2𝑡𝑡 và log 2 𝑡𝑡 như trong bảng I
(Chú ý, các phép tính đều lấy theo modulo của 19). Trong đó: 𝑚𝑚 là bản rõ; 𝑐𝑐 là bản mã; 𝑒𝑒 là số mũ mã hóa và 𝑑𝑑
là số mũ giải mã.
BẢNG I. GIÁ TRỊ HÀM MŨ VÀ LOGARIT RỜI RẠC CƠ SỐ 2 CỦA CÁC PHẦN TỬ
TRONG NHÓM NHÂN ℤ19 ∗ Số mũ mã hóa 𝑒𝑒 (hay khóa) phải là số khả nghịch và do đó 𝑒𝑒
phải thỏa mãn điều kiện sau [6]:
𝑡𝑡 1 2 3 4 5 6 7 8 9
2 𝑡𝑡 2 4 8 16 13 7 14 9 18 gcd(𝑒𝑒𝑒 𝑒𝑒(𝑝𝑝)) = 1
log 2 𝑡𝑡 18 1 13 2 16 14 6 3 8
Với 𝜑𝜑𝜑𝜑𝜑𝜑 là hàm Phi-Euler, cách tính 𝜑𝜑𝜑𝜑𝜑𝜑 có trong [7]. Kết
𝑡𝑡 10 11 12 13 14 15 16 17 18 quả của hàm 𝜑𝜑(𝑝𝑝) cho ta biết số lượng các số nguyên tố cùng
2𝑡𝑡 17 15 11 3 6 12 5 10 1 nhau với 𝑝𝑝.
log 2 𝑡𝑡 17 12 15 5 7 11 4 10 9 Do 𝑝𝑝 là số nguyên tố nên 𝜑𝜑(𝑝𝑝) = 𝑝𝑝 𝑝𝑝, và như thế số mũ
giải mã tương ứng 𝑑𝑑 được tính từ phép nghịch đảo của
Từ bảng I ta nhận thấy cả hàm mũ và hàm logarit rời rạc đều 𝑒𝑒𝑒mod 𝜑𝜑𝜑𝜑𝜑𝜑 như sau [7]:
không phải hàm đồng biến, chúng đều là các hàm phi tuyến. Kết
quả của hai hàm này khi đối số tăng là các giá trị có phân bố 𝑑𝑑 𝑑𝑑𝑑 −1 mod 𝑝𝑝 𝑝𝑝 𝑝 𝑝𝑝 𝜑𝜑[𝜑𝜑(𝑝𝑝)]−1 mod 𝑝𝑝 𝑝𝑝
ngẫu nhiên.
= 𝑒𝑒 𝜑𝜑(𝑝𝑝𝑝𝑝)−1 mod 𝑝𝑝 𝑝𝑝
Một số tính chất của hàm logarit rời rạc [1].
+ 𝑥𝑥 𝑥 log 𝑔𝑔 𝑏𝑏𝑏𝑏 = (log 𝑔𝑔 𝑏𝑏 𝑏 log 𝑔𝑔 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑐 𝑐 Hệ mật Pohlig – Hellman có thể sử dụng làm hệ mật khóa bí
mật thông thường vì rất dễ xác định 𝑑𝑑 từ 𝑒𝑒 và 𝑝𝑝. Thậm chí nếu
𝑏𝑏
+ 𝑥𝑥 𝑥 log 𝑔𝑔 𝑐𝑐 = (log 𝑔𝑔 𝑏𝑏 𝑏 log 𝑔𝑔 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑐 𝑐 giữ bí mật 𝑝𝑝 thì nó có thể suy ra từ kích thước của khối bản mã.
+ log 𝑔𝑔−1 𝑦𝑦 𝑦𝑦 log 𝑔𝑔 𝑦𝑦 𝑦𝑦𝑦𝑦𝑦𝑦 log 𝑔𝑔 𝑦𝑦 III. ĐỀ XUẤT MỘT PHƯƠNG PHÁP XÂY DỰNG
HỆ MẬT MÃ LAI GHÉP
+ log 𝑔𝑔 1 = 0 = 𝑝𝑝 𝑝𝑝
Trong phần này, chúng tôi đề xuất một hệ mật mã lai ghép
Bài toán logarit rời rạc không phải lúc nào cũng khó, độ khó sử dụng hai phép mã hóa là hoán vị và lũy thừa. Sơ đồ khối và
của nó phụ thuộc vào các nhóm nhân được lựa chọn. sơ đồ mã hóa chi tiết như mô tả trong hình 1 và hình 2.
Ví dụ, các hệ mật dựa trên phép logarit rời rạc thường chọn Lược đồ mã hóa của hệ mật thực hiện theo sơ đồ Feistel cân
các nhóm nhân ℤ𝑝𝑝∗ trong đó 𝑝𝑝 là số nguyên tố lớn. Tuy nhiên, bằng [6]. Các khâu IP và IP-1 trong hình 2 là các bảng hoán vị
nếu 𝑝𝑝 𝑝𝑝 là tích của các số nguyên tố nhỏ, thì có thể sử dụng 64 bit và như thế sẽ có tổng cộng 64! cách lựa chọn khác nhau.
thuật toán Pohlig - Hellman để giải bài toán logarit rời rạc rất Trong bài báo này chúng tôi chọn các bảng hoán vị theo cách
hiệu quả. Vì thế người ta thường lựa chọn 𝑝𝑝 là số nguyên tố an của hệ mật DES, như trong bảng II và bảng III [6].
toàn, để thành lập nhóm nhân ℤ∗𝑝𝑝 cho các hệ mật. Một số nguyên
tố an toàn là một số nguyên tố có dạng 𝑝𝑝 = 2𝑞𝑞 + 1, với 𝑞𝑞 là số BẢNG II. HOÁN VỊ BAN ĐẦU (IP)
nguyên tố lớn. Điều này đảm bảo 𝑝𝑝 − 1 = 2𝑞𝑞 có phân tích thành 58 50 42 34 26 18 10 2
tích của các số nguyên tố lớn và không dễ dàng có thể giải được 60 52 44 36 28 20 12 4
bài toán logarit rời rạc bằng thuật toán Pohlig - Hellman [7]. 62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
B. Hệ mật Pohlig - Hellman 57 49 41 33 25 17 9 1
Bài toán logarit rời rạc là bài toán khó, trong khi bài toán lũy 59 51 43 35 27 19 11 3
thừa rời rạc lại không khó (có thể tính bằng thuật toán nhân và 61 53 45 37 29 21 13 5
bình phương). Bài toán này cũng giống như bài toán phân tích 63 55 47 39 31 23 15 7
thừa số và phép nhân các số nguyên, đều có thể dùng để xây
dựng cấu trúc cho một hệ mật mã. BẢNG III. HOÁN VỊ ĐẢO (IP-1)
Hệ mật Pohlig – Hellman cũng là một hệ mật sử dụng bài 40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
toán logarit rời rạc, có thể tóm tắt hệ mật này như sau [3], [7]:
38 6 46 14 54 22 62 30
- Chọn 𝑝𝑝 là một số nguyên tố lớn. 37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
- Phép mã hóa thực hiện theo phương trình đồng dư sau: 35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
𝑐𝑐 𝑐 𝑐𝑐𝑒𝑒 mod 𝑝𝑝 33 1 41 9 49 17 57 25
- Phép giải mã được thực hiện theo phương trình sau:
228
228
- HộiHội
Thảo Quốc
Thảo GiaGia
Quốc 2015
2015vềvềĐiện
ĐiệnTử,
Tử,Truyền
TruyềnThông và Công
Thông và CôngNghệ
NghệThông
ThôngTinTin (ECIT
(ECIT 2015)
2015)
Mã hóa Chú ý, riêng vòng cuối cùng thuật toán mã hóa sẽ là:
Bản rõ M Bản mã C
(64 bit) (64 bit) 𝑅𝑅 = 𝑅𝑅3 ⨁ 𝑒𝑒4
{ 4
𝐿𝐿4 = 𝐿𝐿3 ⨁ 𝑓𝑓𝑓𝑓𝑓3 ⨁𝑒𝑒4 , 𝑒𝑒4 )
Khóa bí mật K
(128 bit)
Hàm mã hóa 𝑓𝑓 sử dụng thuật toán mã hóa của hệ mật Pohlig
Hình 1. Sơ đồ khối của hệ mật – Hellman, thực hiện theo một trong hai cách sau:
Cách 1 sử dụng khóa làm số mũ mã hóa theo phương trình
Bản rõ M( 64 bits) đồng dư sau:
Hoán vị 𝑒𝑒
IP 𝑐𝑐𝑖𝑖 = 𝑓𝑓(𝑚𝑚𝑖𝑖 , 𝑒𝑒𝑖𝑖 ) ≡ 𝑚𝑚𝑖𝑖 𝑖𝑖 mod 𝑝𝑝
ban đầu
L0 ( 32 bits) R0 ( 32 bits) Cách 2 sử dụng dữ liệu làm số mũ mã hóa như sau:
𝑚𝑚𝑖𝑖
e1 𝑐𝑐𝑖𝑖 = 𝑓𝑓(𝑚𝑚𝑖𝑖 , 𝑒𝑒𝑖𝑖 ) ≡ 𝑒𝑒𝑖𝑖 mod 𝑝𝑝
m1
f Trong đó: 𝑚𝑚𝑖𝑖 = 𝑅𝑅𝑖𝑖𝑖𝑖 ⨁𝑒𝑒𝑖𝑖 và 𝑒𝑒𝑖𝑖 lần lượt là dữ liệu đầu vào
mã hóa và khóa mã hóa tại bước thứ 𝑖𝑖; còn 𝑝𝑝 là một số nguyên
tố. Tất cả 𝑝𝑝𝑝𝑝𝑝𝑖𝑖 và 𝑒𝑒𝑖𝑖 đều có kích thước là 32 bit.
L1 ( 32 bits) R1 ( 32 bits)
Trong sơ đồ hình 2 tại vòng mã hóa thứ 𝑖𝑖, khối 32 bit của
e2 nửa phải ở bước 𝑖𝑖 − 1 (𝑅𝑅𝑖𝑖−1 ) sẽ được cộng thêm với khóa 𝑒𝑒𝑖𝑖
m2 trước khi đưa vào hàm 𝑓𝑓. Điều này là để tránh trường hợp khi
f bản rõ đầu vào 𝑀𝑀 chứa toàn bit "0" thì bản mã đầu ra 𝐶𝐶 cũng sẽ
toàn là bit "0".
L2 ( 32 bits) R2 ( 32 bits) Các khóa con 𝑒𝑒𝑖𝑖 tại các vòng mã hóa được trích chọn từ khóa
ban đầu 𝐾𝐾 (128 bit). Cách đơn giản nhất là chia 128 bit khóa
e3 thành 4 khối 32 bit tương ứng với 4 khóa 𝑒𝑒1 , 𝑒𝑒2 , 𝑒𝑒3 và 𝑒𝑒4 , như
m3 mô tả trong hình 3.
f
e1 (32bit) e2 (32bit) e3 (32bit) e4 (32bit)
L3 ( 32 bits) R3 ( 32 bits) Khóa bí mật K (128 bits)
Hình 3. Tách các khóa con 𝑒𝑒𝑖𝑖 cho các vòng mã hóa
e4
m4 Do hệ mật sử dụng sơ đồ Feistel cân bằng nên sơ đồ giải mã
f
về cơ bản giống với sơ đồ mã hóa. Ta thực hiện sơ đồ từ dưới đi
lên, tức là thứ tự của các khóa sẽ đảo lại bắt đầu từ 𝑒𝑒4 và kết thúc
ở 𝑒𝑒1 . Thuật toán giải mã ở mỗi vòng được thực hiện như sau:
L4 ( 32 bits) R4 ( 32 bits)
𝐿𝐿 = 𝑅𝑅𝑖𝑖𝑖𝑖 ⨁ 𝑓𝑓𝑓𝑓𝑓𝑖𝑖𝑖𝑖 , 𝑒𝑒𝑖𝑖 )
-1 Hoán vị { 𝑖𝑖
IP 𝑅𝑅𝑖𝑖 = 𝐿𝐿𝑖𝑖𝑖𝑖 ⨁ 𝑒𝑒𝑖𝑖
đảo
Bản mã C( 64 bits) Vì lý do mạch giải mã vẫn dùng các khóa bí mật 𝑒𝑒𝑖𝑖 để giải
mã, nên ta không cần phải tính số mũ giải mã 𝑑𝑑𝑖𝑖 , và như vậy các
Hình 2. Sơ đồ mã hóa của hệ mật khóa 𝑒𝑒𝑖𝑖 cũng không cần phải thỏa mãn biểu thức (4). Tức là có
thể chọn 𝑒𝑒𝑖𝑖 > 0 tùy ý, và hàm mã hóa 𝑓𝑓 có thể thực hiện theo
Sơ đồ mã hóa trải qua bốn vòng mã hóa với bốn khóa riêng hai cách như mô tả trong các biểu thức (8) và (9).
biệt 𝑒𝑒1 , 𝑒𝑒2 , 𝑒𝑒3 và 𝑒𝑒4 . Việc lựa chọn số vòng mã hóa là do từng hệ
mật, ví dụ như DES là 16 vòng, thông thường số vòng mã hóa Tiến hành mô phỏng tính khuếch tán của hệ mật khi thay đổi
liên quan đến độ khuếch tán của hệ mật. Với hệ mật đề xuất này dữ liệu bản rõ 𝑀𝑀 và thay đổi khóa bí mật 𝐾𝐾, với các thông số mô
thì chỉ cần 4 vòng mã hóa đã đạt độ khuếch tán đầu ra tốt. phỏng được chọn như sau:
Mỗi vòng mã hóa thực hiện theo thuật toán sau: Bản rõ 𝑀𝑀 gồm 64 bit được chọn và biễu diễn dưới dạng hexa
như sau [5]:
𝐿𝐿 = 𝑅𝑅𝑖𝑖𝑖𝑖 ⨁ 𝑒𝑒𝑖𝑖
{ 𝑖𝑖 𝑀𝑀ℎ𝑒𝑒𝑒𝑒 = 0123456789ABCDEF
𝑅𝑅𝑖𝑖 = 𝐿𝐿𝑖𝑖𝑖𝑖 ⨁ 𝑓𝑓𝑓𝑓𝑓𝑖𝑖𝑖𝑖 ⨁𝑒𝑒𝑖𝑖 , 𝑒𝑒𝑖𝑖 )
229
229
- HộiHội
Thảo Quốc
Thảo QuốcGia
Gia2015
2015về
vềĐiện
Điện Tử,
Tử,Truyền
Truyền Thông vàCông
Thông và CôngNghệ
Nghệ Thông
Thông TinTin (ECIT
(ECIT 2015)
2015)
Khóa bí mật 𝐾𝐾 gồm 128 bit (32 số hexa) được chọn như sau: BẢNG IV. KHOẢNG CÁCH HAMMING CỦA MỘT VÀI CẶP BẢN MÃ KHI THAY
ĐỔI 1 BIT BẢN TIN RÕ 𝑀𝑀
𝐾𝐾ℎ𝑒𝑒𝑒𝑒 = 00112233445566778899AABBCCDDEEFF Vị trí
Trường hợp 1: Trường hợp 2:
Bản rõ 𝑀𝑀𝑗𝑗 Hàm mã hóa Hàm mã hóa
bit 𝑒𝑒 𝑚𝑚
Hàm mã hóa 𝑓𝑓 là hàm mũ và tính toán theo giá trị nhị phân. thay (16 số hexa 𝑓𝑓(𝑚𝑚𝑖𝑖 , 𝑒𝑒𝑖𝑖 ) = 𝑚𝑚𝑖𝑖 𝑖𝑖 mod 𝑝𝑝 𝑓𝑓(𝑚𝑚𝑖𝑖 , 𝑒𝑒𝑖𝑖 ) = 𝑒𝑒𝑖𝑖 𝑖𝑖 mod 𝑝𝑝
Sử dụng thuật toán nhân và bình phương có thể dễ dàng thực đổi 64 bit)
𝑗𝑗 Bản mã 𝐶𝐶𝑗𝑗 𝑑𝑑𝐻𝐻 (𝐶𝐶0 , 𝐶𝐶𝑗𝑗 ) Bản mã 𝐶𝐶𝑗𝑗 𝑑𝑑𝐻𝐻 (𝐶𝐶0 , 𝐶𝐶𝑗𝑗 )
hiện các phép tính mũ theo modulo này [1].
Do yêu cầu số 𝑝𝑝 phải là một số lớn, trong bài báo để đơn giản Chưa 01234567 875A60A6 01690489
0 0
đổi 89ABCDEF DD4861DC 53487B72
chúng tôi mới chỉ chọn số 𝑝𝑝 32 bit với bit MSB của 𝑝𝑝 có giá trị
1 11234567 77AC3950 38 715CCD70 33
là "1"; 𝑝𝑝 được chọn như sau: 89ABCDEF 516F1AF3 CB949AD8
2 21234567 682D9393 39 61B6C088 35
𝑝𝑝𝑑𝑑𝑑𝑑𝑑𝑑 = 3.541.619.869 89ABCDEF 6F019515 B42A86CC
... ... ... ... ... ...
↔ 𝑝𝑝𝑏𝑏𝑏𝑏𝑏𝑏 = 10111001001010110001100011001011
30 01234565 194487F4 30 A9E0D179 36
89ABCDEF ED02549A 09D4878F
Bảng IV là một vài kết quả tính toán khoảng cách Hamming
𝑑𝑑𝐻𝐻 (𝐶𝐶0 , 𝐶𝐶𝑖𝑖 ) của các cặp bản mã khi thay đổi lần lượt từng bit 31 01234563 AB780035 24 D287E92B 30
89ABCDEF 2340FB9C 13414BC4
trong 64 bit bản rõ ban đầu 𝑀𝑀. Khóa bí mật 𝐾𝐾 được giữ cố định
... ... ... ... ... ...
tại các bước mô phỏng [5]. Hàm mã hóa 𝑓𝑓 trong sơ đồ mã hóa
thực hiện theo hai trường hợp: trường hợp 1 mã hóa theo biểu 63 01234567 7EBC520B 40 88B33D4B 25
89ABCDEB 23F17E6E 0948EF31
thức (8) và trường hợp 2 mã hóa theo biểu thức (9).
64 01234567 C6FF5110 33 4E6BAC67 31
Khoảng cách Hamming trung bình (hay là độ khuếch tán) 89ABCDE7 BA721B39 A5FCFB9B
của 64 lần thay đổi bản rõ (lần lượt từ bit 1 đến 64) được tính
theo công thức sau: BẢNG V. KHOẢNG CÁCH HAMMING CỦA MỘT VÀI CẶP BẢN MÃ KHI THAY ĐỔI
1 BIT KHÓA BÍ MẬT 𝐾𝐾
1
𝑑𝑑𝐻𝐻(𝑡𝑡𝑡𝑡) = ∑64
𝑗𝑗𝑗𝑗 𝑑𝑑𝐻𝐻 (𝐶𝐶0 , 𝐶𝐶𝑗𝑗 ) Trường hợp 1: Trường hợp 2:
64 Khóa bí
Vị trí Hàm mã hóa Hàm mã hóa
bit thay mật 𝐾𝐾𝑗𝑗 𝑒𝑒
𝑓𝑓(𝑚𝑚𝑖𝑖 , 𝑒𝑒𝑖𝑖 ) = 𝑚𝑚𝑖𝑖 𝑖𝑖 mod 𝑝𝑝
𝑚𝑚
𝑓𝑓(𝑚𝑚𝑖𝑖 , 𝑒𝑒𝑖𝑖 ) = 𝑒𝑒𝑖𝑖 𝑖𝑖 mod 𝑝𝑝
Với trường hợp 1 tính được: đổi
(32 số hexa
𝑗𝑗 Bản mã 𝐶𝐶𝑗𝑗 𝑑𝑑𝐻𝐻 (𝐶𝐶0 , 𝐶𝐶𝑗𝑗 ) Bản mã 𝐶𝐶𝑗𝑗 𝑑𝑑𝐻𝐻 (𝐶𝐶0 , 𝐶𝐶𝑗𝑗 )
128 bit)
𝑑𝑑𝐻𝐻(𝑡𝑡𝑡𝑡) = 31,84 𝑏𝑏𝑏𝑏𝑏𝑏
00112233
Chưa 44556677 875A60A6 01690489
Và trường hợp 2 là: 0 0
đổi 8899AABB DD4861DC 53487B72
CCDDEEFF
𝑑𝑑𝐻𝐻(𝑡𝑡𝑡𝑡) = 31,98 𝑏𝑏𝑏𝑏𝑏𝑏 1 10112233
44556677 C5C2F1B5 7EBFDD39
26 34
8899AABB C80DB24F 5466507C
Bảng V là một vài kết quả tính toán khoảng cách Hamming CCDDEEFF
của các cặp bản mã khi thay đổi lần lượt từng bit khóa đầu vào 2 20112233
𝐾𝐾; Bản rõ 𝑀𝑀 được giữ cố định tại các bước mô phỏng [5], và 44556677 B40F8E3A
34
72405AD9
34
8899AABB 80BAE970 35379279
cũng xét hai trường hợp sử dụng hàm mã hóa 𝑓𝑓 như đề cập ở CCDDEEFF
trên.
... ... ... ... ... ...
Chú ý, trong các bảng IV và bảng V các giá trị 𝑀𝑀𝑗𝑗 , 𝐶𝐶𝑗𝑗 và 𝐾𝐾𝑗𝑗 64 00112233
được biểu diễn theo dạng hexa; các ký tự hexa in đậm chứa các 4455667F F651D78C 82732146
34 33
8899AABB 988A9F2E F87CD709
bit đã được thay đổi so với ban đầu. CCDDEEFF
Khoảng cách Hamming trung bình của các bản mã so với 65 00112233
44556677 FC8D4B5C 1CC8A983
bản mã ban đầu khi thay đổi lần lượt từng bit của khóa 𝐾𝐾 từ bit 9899AABB 2BF6F0B5
41
105E2A90
27
1 đến bit 128 được tính theo công thức sau: CCDDEEFF
... ... ... ... ... ...
1
𝑑𝑑𝐻𝐻(𝑡𝑡𝑡𝑡) = ∑128
𝑗𝑗𝑗𝑗 𝑑𝑑𝐻𝐻 (𝐶𝐶0 , 𝐶𝐶𝑗𝑗 ) 127 00112233
128
44556677 865234A6 503150C8
13 19
8899AABB DC18249D 121C2B32
Với hai trường trường hợp hàm mã hóa tính được như sau: CCDDEEFB
128 00112233
Với trường hợp 1: 𝑑𝑑𝐻𝐻(𝑡𝑡𝑡𝑡) = 28,25 𝑏𝑏𝑏𝑏𝑏𝑏 44556677 DA5F30A6
17
1D7C449D
16
8899AABB 8C0C64DD 174D7B67
CCDDEEF7
Và trường hợp 2: 𝑑𝑑𝐻𝐻(𝑡𝑡𝑡𝑡) = 28,23 𝑏𝑏𝑏𝑏𝑏𝑏
230
230
- Hội+ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJYj&{QJ1JKӋ7K{QJ7LQ (&,7
-
Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Nhận xét về kết quả mô phỏng: Để đơn giản, bài báo chỉ minh họa trường hợp số nguyên tố
gồm 32 bit. Ta hoàn toàn có thể tăng độ dài từ mã cũng như
Một trong các yêu cầu khi đánh giá một hệ mật đó là tính
độ dài khóa bằng cách tăng giá trị số lên để hệ mật an toàn
khuếch tán tại đầu ra. Theo các kết quả mô phỏng ở (15), (16) ta
hơn. Tuy nhiên, khi chọn phải chú ý đến điều kiện số nguyên
thấy độ khuếch tán đầu ra của hệ mật khi thay đổi một bit dữ liệu
tố an toàn như đã trình bày trong mục II.A ở trên.
của bản rõ đầu vào lần lượt là 31,84 bit và 31,98 bit (tương ứng
với hai kiểu mã hóa khác nhau), các giá trị này đạt xấp xỉ một Trong khuôn khổ bài báo chỉ đề cập đến tính khuếch tán của
nửa độ dài từ mã (32 bit). Tương tự trong (18) và (19) độ khuếch hệ mật, để đánh giá hoàn chỉnh hơn về hệ mật này cần có thêm
tán của hệ mật khi thay đổi một bit của khóa cũng đạt lần lượt là các mô phỏng tính toán các phép tấn công khác nữa lên hệ mật.
28,25 bit và 28,23 bit. Chỉ với 4 vòng mã hóa nhưng hệ mật đã
đạt độ khuếch tán rất tốt, đây chính là một ưu điểm đáng chú ý TÀI LIỆU THAM KHẢO
của hệ mật này. [1] Nguyễn Bình, “Giáo trình Mật mã học”, Học viện Công nghệ Bưu chính
Viễn thông, 2013.
IV. KẾT LUẬN [2] Nguyen Minh Trung, Nguyen Binh, “Some Hybrid Crypto Systems
Constructed on Discrete Logarithm Problem”, The International
Hệ mật mã lai ghép như đề xuất trong bài báo bao gồm hai Conference on Advanced Technologies for Communications (ATC)
phép mã hóa là phép hoán vị (các bảng IP và IP-1 trong sơ đồ Hanoi, Vietnam, October, 2014.
Feistel), và phép mũ rời rạc theo hệ mật Pohlig - Hellman. Hệ [3] Mollin, Richard A., "An Introduction to Cryptography (2nd ed.)".
mật này có một số ưu điểm sau: (a) Hàm mã hóa được thực hiện Chapman and Hall/CRC, 2006.
trên bài toán logarit rời rạc nên hệ mật có tính phi tuyến, cùng [4] Frederik Vercauteren, “Discrete Logarithms in Cryptography”,
ESAT/COSIC - K.U. Leuven ECRYPT Summer School 2008.
với độ dài khóa bí mật 128 bit nên hệ mật đạt được độ an toàn
[5] Jean-Yves Chouinard - ELG 5373, “Secure Communications and Data
nhất định; (b) Do sử dụng sơ đồ Feistel nên mạch mã hóa và giải Encryption, School of Information Technology and Engineering”,
mã tương tự nhau rất thuận lợi cho việc thiết kế mạch phần cứng; University of Ottawa, April 2002.
(c) Để hệ mật có độ khuếch tán đạt khoảng một nửa độ dài từ mã [6] Pascal JUNOD, "Statistical Cryptanalysis of Block Ciphers", Thèse N0
thì hệ mật chỉ cần bốn vòng mã hóa điều này sẽ làm tăng đáng 3179, Insitute de systèmes de communication, Ècole Polytechnique
kể tốc độ mã hóa. Fédérale de Lausanne, 2005.
[7] A. Menezes, P. van Oorschot, and S. Vanstone, "Handbook of Applied
Với các ưu điểm này của hệ mật, chúng tôi nhận thấy hệ mật Cryptography", CRC Press, 1996.
này rất phù hợp để ứng dụng vào các lưu đồ thực hiện hàm băm
không khóa (MDC).
231
nguon tai.lieu . vn
