Báo cáo Một giải pháp xây dựng hệ mật khóa đối xứng
MỘT GIẢI PHÁP XÂY DỰNG
HỆ MẬT KHÓA ĐỐI XỨNG
@ Lưu Hồng Dũng1, Nguyễn Ánh Việt2
1 Học viện Kỹ Thuật Quân sự; 2 Bộ Tư Lệnh Tác chiến không gian mạng
Bài viết đề xuất giải pháp xây dựng thuật toán mật mã khóa đối xứng từ việc phát triển hệ
mã sử dụng khóa một lần OTP (One-Time Pad). Ưu điểm của thuật toán xây dựng theo giải
pháp mới đề xuất là tính an toàn và hiệu quả thực hiện được kế thừa mật mã OTP. Đồng thời
việc thiết lập, quản lý - phân phối và sử dụng khóa của thuật toán đề xuất dựa trên các hệ
mã khóa đối xứng đang được ứng dụng trong thực tế (DES, AES…).
GIỚI THIỆU
trực tiếp các bit của bản rõ với các bit tương ứng của
khóa mật.
Việc xây dựng các thuật toán mật mã hiệu năng
cao cho mục đích thiết kế, chế tạo các thiết bị bảo
mật thông tin phục vụ lĩnh vực an ninh - quốc phòng
và kinh tế - xã hội trong điều kiện hiện nay có ý
nghĩa thực tiễn hết sức to lớn. Với mục tiêu đặt ra,
thuật toán được xây dựng nhằm đáp ứng các yêu cầu:
Lý thuyết của Claude E. Shannon [6] đã chỉ ra
OTP là một loại mật mã có độ mật hoàn thiện (perfect
secrecy). Hiện tại, OTP vẫn được xem là loại mật mã
an toàn tuyệt đối, không thể phá vỡ. Điều đặc biệt là
ngay cả tấn công vét cạn (brute force) bằng máy tính
lượng tử đối với loại mã này cũng trở nên vô nghĩa, nếu
có thể đáp ứng được các điều kiện về khóa như sau:
- Loại trừ các dạng tấn công đã biết đối với các hệ
mật khóa đối xứng trong thực tế;
- Khóa có tính chất ngẫu nhiên;
- Tích hợp hiệu quả trên các thiết bị có kích thước
nhỏ, dung lượng nhớ và năng lực tính toán hạn chế.
- Mỗi khóa chỉ được dùng để mã hóa duy nhất
một bản tin;
Giải pháp để xây dựng thuật toán mật mã với các
yêu cầu đặt ra được đề xuất dựa trên việc phát triển
hệ mã sử dụng OTP có độ an toàn và hiệu quả thực
hiện cao [1-5]. OTP được Gilbert Vernam đề xuất
vào năm 1917 và được Joseph Mauborgne tiếp tục
hoàn thiện sau đó. Nguyên tắc căn bản của OTP là
sử dụng một khóa mật chia sẻ trước có độ dài bằng
với độ dài của bản tin cần mã hóa (bản rõ), các bit
của bản mã nhận được từ việc cộng loại trừ (XOR)
- Kích thước của khóa phải bằng hoặc lớn hơn
kích thước của bản rõ;
- Khóa phải được giữ bí mật hoàn toàn.
Tuy có độ an toàn và tốc độ mã hóa cao, cũng như
khả năng cài đặt dễ dàng trên các thiết bị có năng lực
tính toán và tài nguyên hạn chế, nhưng với các yêu
cầu về khóa đã chỉ ra, thì loại mã này khó triển khai
trong thực tế.
Số 5 (057) 2020 l Tạp chí AN TOÀN THÔNG TIN
21
Nguyên nhân đầu tiên là việc tạo khóa phải thực con Ki có kích thước tương ứng với kích thước của
sự ngẫu nhiên, nhằm loại trừ các nguy cơ mất an khối dữ liệu:
toàn bao gồm: a) từ một khóa đã biết, kẻ tấn công
KOT = {K1,K2,...,Ki,...,Kn}, |Ki| = m bit, i = 1...n
có thể tìm (suy ra) được các khóa đã được sử dụng
Thuật toán mã hóa là phép XOR các bit của khối
trước đó hay các khóa sẽ được sử dụng trong tương
bản rõ Pi với các bit tương ứng của khóa con Ki :
lai; b) chuỗi bit khóa tồn tại chu kỳ lặp lại, từ đó tạo
ra mối liên quan giữa bản rõ và bản mã, kẻ tấn công
có thể tận dụng mối liên quan này để phá mã, tương
tự như với mã hóa đa bảng Vigenère [7]. Tuy nhiên,
đây là một yêu cầu không dễ thực hiện về mặt kỹ
thuật trong các ứng dụng.
Ci = Pi ⊕ Ki, i = 1...n
Do đó, bản mã C cũng bao gồm n khối dữ liệu Ci
có kích thước m bit:
C = {C1,C2,…,Ci,…,Cn}, |Ci| = m bit, i = 1...n
Tương tự, thuật toán giải mã cũng là phép XOR
các bit của khối bản mã Ci với các bit tương ứng của
khóa con Ki:
Trong [8], trên cơ sở các nghiên cứu đã được
công bố trước đó, các tác giả đề xuất thuật toán mã
hóa phát triển dựa trên nguyên lý của mật mã OTP
trong đó sử dụng hàm băm (Hash Function) để sinh
dòng khóa, thuật toán có tính hiệu quả thực hiện cao,
dễ cài đặt trên cả phần cứng và phần mềm.
Pi = Ci ⊕ Ki, i = 1...n
Chú ý, trường hợp chia bản tin P thành n khối
không chẵn thì bù thêm 1 số bit để khối cuối cùng đủ
m bit, việc bù thêm này được thực hiện tương tự như
ở các hệ mã khối khác (DES, AES,…).
Trong bài báo này, nhóm tác giả đề xuất một giải
pháp nhằm cho phép tạo ra các biến thể của mật mã
OTP, thừa kế được một số ưu điểm của OTP, song
việc thiết lập, quản lý – phân phối và sử dụng khóa
là đồng nhất với các hệ mã khóa đối xứng đang sử
dụng trong thực tế. Ngoài ra, xác thực nguồn gốc và
tính toàn vẹn của bản tin được mã hóa cũng là một
tính năng bổ sung quan trọng cho các thuật toán xây
dựng theo giải pháp này. Điểm khác của giải pháp đề
xuất ở đây so với thuật toán trong [8] là chuỗi khóa
được tạo ra chủ yếu bằng các thuật toán sinh số ngẫu
nhiên có kết hợp với hàm băm mà không hoàn toàn
bởi hàm băm như trong [8], điều đó cho phép nâng
cao tốc độ thực hiện thuật toán mã hóa nhất là khi sử
dụng thuật toán sinh số ngẫu nhiên dạng thanh ghi
dịch hồi tiếp tuyến tính – LFSR (Linear Feedback
Shift Registers) [9] kiểu Shrinking Generator [10].
Sử dụng 2 khóa khác nhau để mã hóa/giải mã bản tin
Khóa bí mật K để mã hóa/giải mã cho một bản tin
P bao gồm khóa sử dụng một lần KOT và khóa bí mật
chia sẻ trước giữa 2 đối tượng gửi (mã hóa) và nhận
(giải mã) – KS. Trong đó, khóa sử dụng một lần KOT
được dùng để mã hóa các khối dữ liệu của bản rõ ở
bên gửi và giải mã các khối bản mã ở phía bên nhận.
Khóa bí mật chia sẻ KS được bên gửi sử dụng để
tạo ra “mầm khóa” C0 tương ứng với mỗi bản tin cần
mã hóa nhờ hàm băm F1: C0 = F1(P, KS). Thành phần
C0 này được gửi như một khối của bản mã sang cho
bên nhận. Dễ thấy rằng, giá trị C0 là khác nhau với
các bản tin cần mã hóa khác nhau và có tính chất
ngẫu nhiên vì được tạo ra từ hàm băm F1.
GIẢI PHÁP XÂY DỰNG THUẬT TOÁN MẬT
MÃ KHÓA ĐỐI XỨNG HIỆU NĂNG CAO
Tiếp đến, hai bên gửi và nhận đều tạo khóa con
đầu tiên K1 từ KS và C0 nhờ hàm F1 như sau:
Nguyên tắc xây dựng thuật toán mật mã theo giải
pháp đề xuất
K1 = F1(C0, KS)
Phía gửi tin, các khóa Ki được sinh bởi cùng một
thuật toán F2 từ khóa con đứng trước Ki-1 và khối dữ
liệu tương ứng Pi-1:
Mã hóa và giải mã theo khối với OTP
Bản rõ P được mã hóa dưới dạng n khối dữ liệu
Pi có kích thước m bit:
Ki = F2(Pi-1, Ki-1), i = 2...n
P = {P1,P2,…,Pi,…,Pn}, |Pi| = m bit, i = 1...n
Ở đây, F2 là hàm sinh số ngẫu nhiên – RNG
Khóa sử dụng một lần KOT cũng bao gồm n khóa
(Random Number Generator), như phân tích ở phần
Số 5 (057) 2020 l Tạp chí AN TOÀN THÔNG TIN
22
sau (mục Mức độ an toàn) cho thấy F2 hoàn toàn
Thuật toán sinh khóa, giải mã và xác thực bao
có thể là các hàm sinh số giả ngẫu nhiên – PRNG gồm các bước thực hiện như sau:
(PseudoRandom Number Generator) mà không nhất
Input: C = {C0,C1,C2,…,Ci,…,Cn}, KS
thiết phải thực sự là RNG.
Output: M = {M1,M2,…,Mi,…,Mn}, true/false.
Phía nhận tin, sau khi tạo: K1 = F1(C0,KS) sẽ giải
[1]. K1 = F1(C0,KS)
mã khối đầu tiên: P1 = C1 K1. Từ đây, các khóa con
[2]. M1 = C1 ⊕ K1
tiếp theo sẽ được tạo ra theo cùng một quy tắc với
[3]. M[1] = M1
phía bên gửi:
[4]. for i = 2 to n do:
Ki = F2(Pi-1, Ki-1), i = 2...n
begin
Với mỗi khóa con Ki được tạo ra thì việc giải mã
Ki = F2(Mi-1,Ki-1)
các khối mã tiếp theo sẽ được thực hiện:
Mi = Ci ⊕ Ki
Pi = Ci Ki, i = 2...n
M[i] = Mi
end
Như vậy ở giải pháp đề xuất, khóa bí mật K sẽ
bao gồm hai thành phần có chức năng phân biệt: K
= {KS, KOT}. Trong đó: KS là khóa bí mật chia sẻ giữa
các đối tượng tham gia trao đổi thông tin mật, khóa
này được sử dụng để tạo ra khóa KOT tương ứng với
mỗi bản tin. Còn KOT là khóa sử dụng một lần cho
việc mã hóa và giải mã bản tin.
[5]. M0 = F1(M,KS)
[6]. if (M0 = C0) then return {M,true}
else return {M,false}
Ghi chú:
- Nếu kết quả trả về là {M,true} thì bản tin được
xác thực về nguồn gốc và tính toàn vẹn. Ngược lại,
kết quả trả về là {M,false} thì M là bản tin giả mạo
hoặc C đã bị thay đổi trong quá trình truyền tin.
Thuật toán bên người gửi
Thuật toán sinh khóa và mã hóa bao gồm các
bước thực hiện được mô tả như sau:
- Nếu bản mã được truyền chính xác từ bên gửi
sang bên nhận thì khối dữ liệu C0 của bên nhận
cũng chính là C0 của bên gửi. Mặt khác, do bên
nhận và bên gửi có cùng thuật toán sinh khóa với
dữ liệu vào C0 và khóa bí mật chia sẻ KS như nhau,
nên khóa mã hóa và khóa giải mã sử dụng một lần
KOT sẽ hoàn toàn giống nhau. Vì thế bản tin sau giải
mã cũng chính là bản rõ trước khi mã hóa. Nên điều
kiện M0 = C0 được thỏa mãn hoàn toàn.
Input: P = {P1,P2,…,Pi,…,Pn}, KS
Output: C = {C0,C1,C2,…,Ci,…,Cn}
[1]. C0 = F1(P,KS)
[2]. K1 = F1(C0,KS)
[3]. C1 = P1 K1
[4]. C[0] = C0, C[1] = C1
[5]. for i = 2 to n do
begin
MỘT SỐ ĐÁNH GIÁ VỀ GIẢI PHÁPXÂYDỰNG
THUẬT TOÁN MẬT MÃ ĐƯỢC ĐỀ XUẤT
Ki = F2(Pi-1, Ki-1)
Ci = Pi Ki
Mức độ an toàn
C[i] = Ci
Mức độ an toàn của thuật toán mật mã khóa đối
xứng xây dựng theo giải pháp đề xuất có thể đánh giá
qua khả năng chống lại một số dạng tấn công như sau:
end
[6]. return C
Ghi chú:
- Tấn công khóa bí mật chia sẻ: Tấn công khóa bí
mật chia sẻ có thể thực hiện dựa vào cách tạo giá trị
C0: C0 = F1(P,KS) hoặc tính giá trị của khóa con K1:
K1 = F1(C0,KS).
- Phép toán ⊕ là phép cộng modulo 2 (XOR) hai
chuỗi bit.
Thuật toán bên người nhận
Số 5 (057) 2020 l Tạp chí AN TOÀN THÔNG TIN
23
Với việc tạo C0 và K1 như trên thì kích thước LK con (m bit đầu tiên) rồi ghép nối tiếp n chuỗi con
của khóa bí mật chia sẻ hoàn toàn có thể chọn tùy này với nhau.
biến trong khoảng: Lmin≤LK≤2L-LP. Trong đó, Lmin là
Nếu các chuỗi bit cơ sở được tạo ra bởi các hàm
kích thước tối thiểu đủ để bảo đảm ngưỡng an toàn
băm và hàm sinh số giả ngẫu nhiên có chu kỳ lặp lại
(≥ 80 bit); LP là kích thước bản rõ và L là kích thước
lớn và kích thước của các chuỗi con Ki được chọn
lớn nhất của dữ liệu đầu vào hàm băm F1. Khi đó, dữ
nhỏ hơn chu kỳ lặp lại của chuỗi bit cơ sở thì các
liệu đầu vào hàm F1 là sự ghép nối tiếp xâu bit của KS
chuỗi con này thực sự có tính ngẫu nhiên theo nghĩa:
với P trong trường hợp tạo giá trị C0, hoặc là sự ghép
a) không tồn tại chu kỳ lặp lại; b) từ một số bit cho
nối tiếp xâu bit của KS với C0 trong trường hợp tạo
trước không thể tính được bit tiếp theo, là điều hoàn
khóa con K1. Từ đây có thể thấy rằng, khóa bí mật
toàn có thể khẳng định. Mặt khác, do các chuỗi con
chia sẻ trước giữa bên gửi và nhận hoàn toàn có thể
Ki được tạo theo: Ki = F2(Pi-1, Ki-1), nên một trong
được giữ bí mật không chỉ về giá trị mà còn bí mật
các điều kiện để các Ki tạo thành chuỗi giá trị lặp lại
cả về kích thước khóa.
là các Pi cũng phải tạo thành chuỗi lặp lại, mà trên
Dễ thấy rằng, với đặc tính một chiều của hàm thực tế điều này lại khó xảy ra.
băm, hơn nữa với kích thước của KS cũng là một
Do đó, với giải pháp đề xuất KOT đã đáp ứng được
tham số bí mật, thì việc tìm được KS từ C0, P và K1 là
yêu cầu về tính ngẫu nhiên của khóa theo nghĩa: a)
hoàn toàn không khả thi.
từ một khóa đã biết, kẻ tấn công không thể tìm được
- Tấn công vét cạn khi chỉ có bản mã: Nếu KOT là các khóa đã được tạo ra trước hoặc sau đó; b) chuỗi
một chuỗi bit thực sự ngẫu nhiên thì giữa bản rõ và bit khóa không tồn tại chu kỳ lặp lại, nên sẽ không
bản mã được tạo ra sẽ không có bất kỳ mối quan hệ tạo ra mối liên quan giữa bản rõ và bản mã. Từ đó,
nào. Tấn công vét cạn có thể giải một bản mã thành thuật toán được xây dựng theo giải pháp đề xuất
bất kỳ bản tin nào có cùng độ dài (với bản mã) và đối hoàn toàn có thể kháng lại tấn công vét cạn.
với kẻ tấn công thì tất cả các bản tin có nghĩa sau giải
- Tấn công giả mạo: OTP không cung cấp tính
mã đều có khả năng là bản tin được mã hóa. Nghĩa
năng xác thực cho bản tin được mã hóa, vì vậy kẻ
là, sẽ không có bất kỳ thông tin nào trong bản mã cho
tấn công có thể chặn bản mã được gửi đi và gửi cho
phép kẻ tấn công lựa chọn đúng bản rõ trong số các
bên nhận một bản tin giả mạo có cùng kích thước với
bản tin có nghĩa sau giải mã bằng tấn công vét cạn.
bản tin thật. Trường hợp giải mã ra một bản rõ vô
Ngoài ra, nếu KOT thực sự ngẫu nhiên thì từ một khóa
nghĩa, người nhận có thể suy đoán về một sự giả mạo
đã biết, kẻ tấn công không thể tìm (suy) ra các khóa
đã được thực hiện hoặc do lỗi truyền tin gây ra. Tuy
khác đã được tạo ra trước hay sau đó.
nhiên, nếu giải mã ra một bản tin có nghĩa, thì chính
Theo giải pháp đề xuất, khóa sử dụng một người nhận cũng không có cách nào để khẳng định
lần KOT là một tập các khóa con Ki được tạo bởi được rằng đây là bản tin thật hay bản tin giả mạo.
hàm băm F1 và hàm sinh số ngẫu nhiên F2 theo 2
Với giải pháp đề xuất, bằng việc tạo “mầm khóa”
nguyên tắc: Thứ nhất, mỗi khóa con Ki được sinh
C0 từ khóa bí mật chia sẻ KS và bản rõ nhờ hàm băm
ra từ khóa con đứng trước nó là Ki-1 và khối dữ liệu
F1 ở phía bên gửi: C0 = F1(P,KS), bên nhận hoàn toàn
tương ứng Pi-1 bởi F2; Thứ hai, riêng khóa con đầu
có khả năng nhận thức chính xác nguồn gốc cũng
tiên K1 được tạo ra bởi “mầm khóa” C0 và khóa bí
như tính toàn vẹn của bản tin sau giải mã qua việc
mật chia sẻ KS bởi hàm băm F1. Như vậy, KOT thực
tính: M0 = F1(M,KS) và kiểm tra điều kiện: M0 = C0.
chất là một chuỗi bit được tạo ra bởi việc ghép nối
Hiệu quả thực hiện
tiếp n chuỗi (bit) con Ki, mà các chuỗi con Ki này
chính là đoạn m bit đầu tiên của n chuỗi bit cơ sở
được tạo bởi F1 hoặc F2 với các giá trị khởi tạo
hay các “mầm” khác nhau. Nói cách khác, chuỗi
bit KOT được tạo ra từ n chuỗi bit cơ sở khác nhau,
bằng cách lấy ra từ mỗi chuỗi bit cơ sở 1 chuỗi
Có thể nâng cao hiệu quả thuật toán xây dựng
theo giải pháp đề xuất nếu khóa KOT được tạo ra
trước các khi các thủ tục mã hóa và giải mã được
thực hiện. Khi đó, các thuật toán sinh khóa, mã hóa
và giải mã được mô tả như sau:
Số 5 (057) 2020 l Tạp chí AN TOÀN THÔNG TIN
24
+ Thuật toán sinh khóa:
dạng tấn công đối với các hệ mã khối, đây là một ưu
điểm rất quan trọng được kế thừa từ OTP. Ngoài ra,
do có cơ chế xác thực nguồn gốc và tính toàn vẹn
của bản tin được mã hóa, các thuật toán này còn có
khả năng chống lại các dạng tấn công giả mạo trong
thực tế. Những ưu điểm khác của các thuật toán này
là tốc độ và hiệu quả thực hiện có thể so sánh với hệ
mã OTP, song khóa mật chia sẻ có thể sử dụng nhiều
lần như các hệ mã khóa đối xứng khác. Đây là những
đặc tính rất quan trọng mang lại khả năng cho các
thuật toán mới có thể ứng dụng được trong việc thiết
kế, chế tạo các thiết bị bảo mật thông tin.
Input: P = {P1,P2,…,Pi,…,Pn}, KS
Output: KOT = {K1,K2,…,Ki,…,Kn}, C0
[1]. C0 = F1(P,KS)
[2]. KOT[1] = F1(C0,KS)
[3]. for i = 2 to n do
begin
KOT[i] = F2(KOT[i-1])
end
[4]. return {KOT,C0}
+ Thuật toán mã hóa:
Input: P = {P1,P2,…,Pi,…,Pn}, C0,
KOT = {K1,K2,…,Ki,…,Kn}
Output: C = {C0,C1,C2,…,Ci,…,Cn}
[1]. C[0] = C0
TÀI LIỆU THAM KHẢO
1. SharadPatil, Ajay Kumar (2010). Effective Secure
Encryption Scheme (One Time Pad) using Complement
Approach. International Journal of Computer Science &
Communication, Vol.1,No.1,January-June 2010, pp.229-233.
[2]. for i = 1 to n do
begin
C[i] = P[i] ⊕ KOT[i]
end
2. Raman Kumar, Roma Jindal, Abhinav Gupta,
SagarBhalla, HarshitArora (2011).
A
Secure
[3]. return C
Authentication System - Using Enhanced One Time Pad
Technique. IJCSNS International Journal of Computer
Science and Network Security, Vol.11 No.2.
+ Thuật toán giải mã và xác thực:
Input: C = {C0,C1,C2,…,Ci,…,Cn},
KOT = {K1,K2,…,Ki,…,Kn},KS
Output: M = {M1,M2,…,Mi,…,Mn}, true/false.
[1]. for i = 1 to n do:
3. SharadPatil, ManojDevare,Ajay Kumar (2007). Modified
One Time Pad Data Security Scheme: Random Key
Generation Approach. International Journal of Computer
Science and Security (IJCSS), Volume (3): Issue(2).
4. N.J.Croft and M.S.Olivier (2005). “Using an
approximated One-Time Pad to Secure ShortMessaging
service(SMS)”. SATNAC 2005 Proceedings.
begin
M[i] = C[i] ⊕ KOT[i]
end
5. Jeff Connelly (1978). A Practical Implementation of a
One-time Pad Cryptosystem. CPE 456.
[2]. M0 = F1(M,KS)
[3]. if (M0 = C0) then return {M,true}
else return {M,false}
6. Shannon C.E. (1949). Communication Theory of Secrecy
Systems. Bell System Technical Journal, Vol.28-4, pp.656-715.
7. William Stallings (2005). Cryptography and Network
Security Principles and Practices. Prentice Hall.
Có thể thấy rằng, hiệu quả thực hiện của thuật
toán được đề xuất khi đó đạt xấp xỉ hiệu quả thực
hiện của mật mã OTP. Tuy nhiên, do:
8. Marcio Ricardo Rosemberg, Daniel Schwabe, Marcus Poggi,
A Hybrid Block and Stream Cipher Encryption Scheme
Based on Collision Resistant Hash Functions. Monografias
em Ciência da Computação n° 13/17, ISSN: 0103-9741.
KOT[i] = F2(KOT[i-1])
Nên sẽ tiềm tàng khả năng tồn tại chu kỳ lặp lại
9. Menezes A., Van Oorschot P. and Vanstone S. (1996).
Handbook of Applied Cryptography. Boca Raton,
Florida: CRC Press.
trong chuỗi KOT.
KẾT LUẬN
10. D. Coppersmith, H. Krawczyk, and Y. Mansour
(1994), “The shrinking generator,” in CRYPTO ’93:
Proceedings of the 13th annual international cryptology
conference on Advances in cryptology, (New York, NY,
USA), pp. 22-39, Springer-Verlag New York, Inc.
Bài báo đề xuất giải pháp xây dựng thuật toán
mật mã khóa đối xứng từ việc phát triển mật mã sử
dụng khóa một lần OTP. Với giải pháp thiết kế khóa
mật từ 2 phân khóa tách biệt, các thuật toán xây dựng
theo giải pháp ở đây có khả năng loại trừ một số
Số 5 (057) 2020 l Tạp chí AN TOÀN THÔNG TIN
25
5 trang
10/05/2022
3180
Bạn đang xem tài liệu "Báo cáo Một giải pháp xây dựng hệ mật khóa đối xứng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bao_cao_mot_giai_phap_xay_dung_he_mat_khoa_doi_xung.pdf
