Xem mẫu
- Hội nghị Quốc gia lần thứ 24 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2021)
Kết hợp thuật toán mật mã Hill và mã OTP
trong mã hóa và giải mã thông điệp
Vũ Ngọc Phan1 và Nguyễn Đức Toàn2
1
Trường Đại học Tài nguyên và Môi trường Hà Nội
Email: vnphan@hunre.edu.vn
2
Học viện Phụ nữ Việt Nam
Email: ductoanndt9@gmail.com
Abstract: Mọi thuật toán mã cổ điển đều là mã khoá đối xứng, vì
Trong bài báo này chúng tôi đề xuất kết hợp phương pháp ở đó thông tin về khóa được chia sẻ giữa người gửi và
mã hóa Hill và mã OTP để mã hóa và giải mã thông điệp dựa người nhận. Mã đối xứng là kiểu duy nhất trước khi phát
trên ngôn ngữ lập trình Python. Thuật toán mã hóa Hill là minh ra khoá mã công khai (còn được gọi là mã không
thuật toán dễ dàng, tuy nhiên cái khó khăn là chọn khóa làm đối xứng) vào những năm 1970. Hiện nay các mã đối
sao cho thỏa mãn khóa có tính khả nghịch. Mã OTP là mã
khóa chỉ dùng 1 lần, chính vì thế trong bài báo này chúng tôi
xứng và công khai tiếp tục phát triển và hoàn thiện. Mã
đề xuất dùng mã OTP làm khóa cho thuật toán mã hóa Hill. công khai ra đời hỗ trợ mã đối xứng, không thay thế nó,
Trong phần thực nghiệm chúng tôi chọn khóa có kích thước do đó mã đối xứng đến nay vẫn được sử dụng rộng rãi.
2x2 và 3x3. Do đó khóa nhận được là có tính ngẫu nhiên. Định nghĩa một số khái niệm cơ bản về mã hóa.
Keywords- Python, Hill, OTP, mã hóa, giải mã. Một hệ mật mã là một bộ 5 (P,C,K,E,D) thoả mãn các
I. GIỚI THIỆU điều kiện sau [1]:
P (Plaintext) là một tập hợp hữu hạn các bản rõ và được
Với sự phát triển nhanh chóng của công nghệ gọi là không gian bản rõ.
thông tin, bảo mật thông tin ngày càng trở nên quan C (Ciphertext) là tập các hữu hạn các bản mã và được
trọng. Trước đây, người ta thường dùng phương pháp gọi là không gian các bản mã.
mật mã (cryptography) để bảo mật thông tin. Tuy nhiên, K (Key) là tập hữu hạn các khoá hay còn gọi là không
khi sử dụng phương pháp này, đối tượng cần gian khoá. Đối với mỗi phần tử k của K được gọi là
bảo mật được chuyển thành dạng mật mã khó hiểu nên một khoá (Key). Số lượng của không gian khoá phải
gây sự chú ý nhiều hơn. Điều này làm cho những kẻ đủ lớn để không có đủ thời gian thử mọi khoá;
xấu luôn tìm cách giải mã để hiểu được nội dung của E (Encrytion) là tập hợp các qui tắc mã hóa có thể.
đối tượng được bảo vệ đó. Nhằm tránh gây sự chú ý, D (Decrytion) là tập hợp các qui tắc giải mã có thể.
một phương pháp bảo mật khác được đề xuất và sử Đối với mỗi 𝑘 ∈ 𝐾 có một quy tắc mã 𝑒𝑘: 𝑃 → C và
dụng rộng rãi là giấu tin mật. Thông tin cần bảo vệ một quy tắc giải mã tương ứng dk ∈ D.
được ẩn giấu trong một đối tượng mang tin, thường là Mỗi ek: P → C và dk: C → P là những hàm mà:
ảnh, video, âm thanh, văn bản,… Kỹ thuật này có ưu 𝑑𝑘(𝑒𝑘(𝑥)) = 𝑥 với mỗi x ∈ P.
điểm là thông tin không chỉ được bảo vệ mà còn che Chúng ta đã biết một thông tin thường được tổ chức
giấu được sự tồn tại của nó. dưới dạng bản rõ. Người gửi sẽ làm nhiệm vụ mã hoá
bản rõ, kết quả thu được gọi là bản mã. Bản mã này
Mật mã đối xứng sử dụng cùng một khóa cho việc mã được gửi đi trên một đường truyền tới người nhận, sau
hóa và giải mã. Có thể nói mã đối xứng là mã một khoá khi nhận được bản mã người nhận giải mã nó để tìm
hay mã khóa riêng hay mã khoá thỏa thuận. Ở đây hiểu nội dung.
người gửi và người nhận chia sẻ khoá chung K, mà họ Thuật toán dùng khi sử dụng định nghĩa hệ mật mã:
có thể trao đổi bí mật với nhau. Ta xét hai hàm ngược 𝑒𝑘(𝐶) = 𝑃, 𝑑𝑘(𝑃) = 𝐶
nhau: E là hàm biến đổi bản rõ thành bản mã và D là Một mã đối xứng có các đặc trưng là cách xử lý thông
hàm biến đổi bản mã trở về bản rõ. Giả sử X là văn bản tin của thuật toán mã, giải mã, tác động của khóa vào
cần mã hóa và Y là dạng văn bản đã được thay đổi qua bản mã, độ dài của khóa. Mối liên hệ giữa bản rõ, khóa
việc mã hóa. Khi đó ta ký hiệu: và bản mã càng phức tạp càng tốt, nếu tốc độ tính toán
Y = EK (X) là chấp nhận được [3]. Cụ thể hai yêu cầu để sử dụng an
toàn mã khoá đối xứng là:
X = DK (Y) +) Thuật toán mã hoá mạnh. Có cơ sở toán học vững
chắc đảm bảo rằng mặc dù công khai thuật toán, mọi
ISBN 978-604-80-5958-3 221
- Hội nghị Quốc gia lần thứ 24 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2021)
người đều biết, nhưng việc thám mã là rất khó khăn và Trong đó, 𝑑𝑒𝑡𝐾 −1 là nghịch đảo của 𝑑𝑒𝑡(𝐾) theo
phức tạp nếu không biết khóa. modulo 26:
+) Khoá mật chỉ có người gửi và người nhận biết. Có 𝑑𝑒𝑡𝐾 ∗ det(𝐾)−1 ≡ 1(𝑚𝑜𝑑26)
kênh an toàn để phân phối khoá giữa các người sử dụng
chia sẻ khóa. Mối liên hệ giữa khóa và bản mã là không Chúng ta tìm được nghịch đảo của 𝑑𝑒𝑡(𝐾) bằng cách
nhận biết được. lặp các giá trị từ 0 tới 25, nhân với 𝑑𝑒𝑡(𝐾) và lấy dư
Phần còn lại của bài báo được tổ chức như sau: trong phép chia 26, giá trị thoả mãn chia 26 dư 1 chính là
phần II, chúng tôi miêu tả thuật toán. Trong phần III, det(𝐾)−1
chúng tôi xây dựng demo IV cung cấp các kết quả mô 2.2 Mã OTP
phỏng và phân tích lý thuyết và đánh giá hiệu năng của
hệ thống. Cuối cùng, chúng tôi kết luận bài báo trong Hệ mật mã với khóa sử dụng một lần OTP (One Time
phần IV. Pad) là một hệ mật mã dòng, đã được chứng minh có độ
an toàn hoàn hảo. Đặc điểm nổi bật của hệ mật này là
II. THUẬT TOÁN HILL VÀ MÃ OTP mỗi khóa chỉ sử dụng đúng một lần và không bao giờ
được dùng lại. Nhưng nhược điểm cơ bản của hệ mật
2.1 Thuật toán Hill này là độ dài của khóa phải bằng đúng độ dài của bản rõ
Mã hoá Hill phát minh bởi Lester S. Hill năm 1929, là và một yêu cầu rất khắt khe nữa là các khóa phải được
mật mã cổ điển cho phép mã hoá hai, hoặc ba, hoặc sinh thực sự ngẫu nhiên. Đây là một điều kiện rất khó
nhiều hơn các ký tự (theo lý thuyết) tại cùng thời điểm. thực hiện ngay cả các chuỗi ngẫu nhiên được sinh tự
Mã hoá Hill sử dụng hai lý thuyết toán học cực kì quan động bằng máy tính cũng mới chỉ là giả ngẫu nhiên vì
trọng trong ngành mật mã là Đại số tuyến tính và Số học chúng phụ thuộc vào một cái nhân (seed) cho trước[4].
mô-đun [8]. Lược đồ này gồm ba qui trình sau:
Để thuật tiện cho quá trình mã hoá, quy ước mỗi chữ cái Bước 1 Mã hóa:
trong bảng chữ cái tương ứng với một giá trị theo thứ tự Chia bản rõ thành các khối có kích thước bằng 256 bit.
tăng dần. Vì thuật toán Hill thực hiện việc mã hoá theo Nếu không chẵn thì phải chèn thêm cho đủ một khối.
khối block gồm m ký tự tại cùng một thời điểm. Băm bản rõ bằng một hàm băm với giá trị băm có kích
Bước 1: Mã hóa thước bằng 256 bit. Giá trị băm này được chọn làm khóa
Cho biết khoá K và thông điệp P, mã hoá Hill thực hiện OTP khởi đầu, gọi là K1 . Sau đó, K1 sẽ được XOR với
phép nhân ma trận giữa K và P để mã hoá thông điệp tạo khối bản rõ thứ nhất để tạo ra khối bản mã thứ nhất. Các
bản mã C. khóa OTP tiếp theo, K i (i >= 2) sẽ được sinh ra bằng
𝐾 ⋅ 𝑃 ≡ 𝐶(𝑚𝑜𝑑26) cách mã hóa khối bản rõ thứ i − 1 bằng hệ mật AES256
Để mã hoá một thông điệp, chúng ta cần tạo một với khóa K i−1 . Các khóa mới được sinh ra lại được
khoá K. Khoá này là bí mật và chỉ giữa những người XOR với khối bản rõ tương ứng để tạo ra các khối bản
trao đổi thông tin với nhau biết được. Khoá phải đảm mã tiếp theo. Ghép tất cả các khối bản mã để thu được
bảo 2 tính chất: bản mã.
K có độ dài là m x m (bình phương độ dài khối Bước 2 Ký bản rõ và gửi bản mã:
block m) Khóa K1 được mã hóa bằng khóa bí mật của người gửi.
K là ma trận khả nghịch theo modulo 26 Sau đó, lại được mã hóa bằng khóa công khai của người
nhận. Gửi cho bên nhận thông tin đã mã hóa này và bản
𝐾 ⋅ 𝐾 −1 ≡ 1 (𝑚𝑜𝑑26)
mã.
𝐾 −1 là ma trận nghịch đảo của K trên vành Z26
Bước 3 Xác thực và giải mã: Người nhận sử dụng khóa
Trong thuật toán này mã khoá hợp lệ là khoá có độ dài
bí mật của mình và khóa công khai của người gửi để
2x2 hoặc 3x3 và khả nghịch theo modulo 26.
giải mã ra khóa K1 . Chia bản mã thành các khối có kích
Thỏa mãn: Khóa phải có độ dài là số chính phương. [7]
thước 256 bit sau đó làm tương tự như quá trình mã hóa
để thu được bản rõ.
Bước 2: Giải mã
Lược đồ trên, đã lấy giá trị băm của bản rõ làm khóa
Cho biết khoá 𝐾 và bản mã 𝐶, mã hoá Hill thực hiện
OTP. Vì các bản rõ là những văn bản bất kỳ nên giá trị
phép nhân ma trận nghịch đảo 𝐾 −1 và bản mã 𝐶 để tạo
băm của chúng là các chuỗi bit ngẫu nhiên và gần như là
thông điệp gốc 𝑃.
duy nhất đối với mỗi bản rõ. Việc chọn giá trị băm làm
𝐾 −1 ⋅ 𝐶 ≡ 𝑃(𝑚𝑜𝑑26)
khóa OTP đã làm giảm đáng kể độ dài của khóa đối với
Trước hết, để tìm ma trận nghịch đảo 𝐾 −1 , chúng ta đã
những bản rõ có dung lượng lớn. Các khóa tiếp theo
biết theo lý thuyết đại số tuyến tính:
được sinh ra bằng thuật toán AES trên khối bản rõ tương
𝐾 −1 = 1𝑑𝑒𝑡(𝐾). 𝐾 ∗ ứng với khóa được sinh ra trước đó vẫn đảm bảo được
tính OTP.
Trong đó 𝑑𝑒𝑡(𝐾) là định thức ma trận K, và 𝐾 ∗ là ma Trong hệ mã với khóa sử dụng một lần OTP (One -
trận liên hợp của 𝐾. Tuy nhiên đối với mã hoá Hill, _Time Pad) mỗi byte của bản rõ được mã hóa bằng một
chúng ta đang cần tìm ma trận nghịch đảo 𝐾 −1 theo byte của luồng khóa và mỗi byte khóa chỉ được sử dụng
modulo 26, công thức trở thành: đúng một lần và không bao giờ được sử dụng lại. Trong
𝐾 −1 = det(𝐾)−1 . 𝐾 ∗ (𝑚𝑜𝑑26) hệ mật mã này độ dài của khóa phải bằng đúng độ dài
ISBN 978-604-80-5958-3 222
- Hội nghị Quốc gia lần thứ 24 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2021)
của bản rõ và phải là một luồng được sinh ra thực sự ra lại được XOR với khối bản rõ tương ứng để tạo ra
ngẫu nhiên, tức là mọi byte của khóa có thể nhận bất kỳ các khối bản mã tiếp theo.
giá trị nào trong khoảng từ 0 đến 255 với xác suất như return matrix
nhau và độc lập với giá trị của tất cả các byte khóa khác.
[2] Trong hệ mã OTP, bản rõ được biểu diễn dưới dạng Bước 4: Tính ma trận nghịch đảo
một chuỗi nhị phân, luồng khóa cũng là một chuỗi nhị
phân có độ độ dài bằng độ dài bản rõ. et = np.linalg.det(matrix)
Việc mã hóa bằng OTP thường được ký hiệu là: if math.gcd(int(round(det)), len(alphabet)) == 1:
Ci = Pi K i , (i = 1, 2, 3, . . . ) matrix = Matrix(matrix)
return np.array(matrix.inv_mod(len(alphabet)))
Trong đó Pi là ký tự thứ i của bản rõ, K i là byte thứ else:
i của khóa được sử dụng để mã hóa bản rõ này và Ci là return None
ký tự thứ i của bản mã kết quả, là ký hiệu của phép
cộng loại trừ (XOR), phép toán hay được dùng trong mã Bước 5: Giải mã
hóa OTP nhưng vẫn có thể được thay bằng phép toán plaintext = ""
khác. ciphervector = [0 for i in range (n)]
Quá trình giải mã được làm tương tự như mã hóa : messagevector = [0 for i in range (n)]
Pi = Ci K i
block = 0
Tuy nhiên, phương pháp One_Time_ Pad không có ý while block * n < len(_ciphertext):
nghĩa sử dụng thực tế vì chiều dài khóa bằng chiều dài for i in range (n):
bản tin, mỗi khóa chỉ sử dụng một lần, nên thay vì ciphervector[i] = char_to_int(_ciphertext[i +
truyền khóa trên kênh an toàn thì có thể truyền trực tiếp block * n], alphabet)
bản rõ mà không cần quan tâm đến vấn đề mã hóa nữa. print("Cipher vector: ")
print(ciphervector)
2.3 Kết hợp thuật toán Hill và mã OTP
for i in range (n):
messagevector[i] = 0
Bước 1: Mã hóa for j in range (n):
def int_matrix_to_str(matrix, alphabet): messagevector[i] += invkmatrix[i][j] *
word = "" ciphervector[j]
n = len(matrix) print(messagevector[i])
for i in range (n): plaintext += str(int_to_char(messagevector[i],
for j in range (n): alphabet))
word += int_to_char(matrix[i][j], alphabet) block += 1
return word return plaintext
Bước 2: Tạo ma trận có đảo ngược ngẫu nhiên
def gen_random_inv_matrix(n, alphabet): 2.4 Đánh giá độ an toàn
matrix = gen_random_matrix(n, alphabet) Khóa OTP đề xuất kết hợp với thuật toán Hill có khả
while not is_invertible_matrix(matrix, alphabet): năng xác thực nguồn gốc và tính toàn vẹn của bản tin
matrix = gen_random_matrix(n, alphabet) nhận được. Vì thế ngoài khả năng chống được các dạng
return matrix tấn công đối với các hệ mã khối thông thường khác,
Bước 3: Tạo khóa dùng mã OTP thuật toán còn có thể chống lại một số dạng tấn công giả
if len(word)
- Hội nghị Quốc gia lần thứ 24 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2021)
phần II. Việc sử dụng khóa OTP để mã hóa/giải mã bản
tin, trong đó khóa k OTP được sử dụng tương tự như hệ
mã OTP [6] cho phép loại trừ hầu hết các dạng tấn công
đã được biết đến trong thực tế: thám mã vi sai, thám mã
tuyến tính, tấn công bản mã có lựa chọn, tấn công bản rõ
đã biết...
Các phương pháp tấn công này hoàn toàn không có
tác dụng với khóa OTP do k OTP chỉ sử dụng 1 lần cùng
với bản tin được mã hóa, hơn nữa với kích thước 128 bit
thì phương pháp vét cạn là không khả thi để tấn công
các khóa con k i [2].
3.1 Thực nghiệm với bản rõ với các kí tự chữ a đến z với
các khóa ma trận 2x2 và 3x3
Hình 3 Chuyển đổi ma trận 2x2
Hình 1 Chuyển đổi ma trận 2x2
Hình 4 Chuyển đổi ma trận 3x3 với bản rõ z26
3.2 Thực nghiệm với bản rõ với các kí tự chữ và các số
với các khóa ma trận 2x2 và 3x3
Hình 2 Chuyển đổi ma trận 3x3
3.2 Thực nghiệm với bản rõ với các kí tự chữ a đến z và
các số từ 0 đến 9 với các khóa ma trận 2x2 và 3x3
ISBN 978-604-80-5958-3 224
- Hội nghị Quốc gia lần thứ 24 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2021)
hội phát triển không ngừng. Để đáp ứng được các nhu
cầu bảo mật và việc áp dụng các kỹ thuật mã hóa, các
nhà khoa học đã nỗ lực nghiên cứu, đề xuất, cải tiến các
thuật toán mã hóa để phù hợp với tình hình mới và giải
quyết được những bài toán mới phát sinh trong thực
tiễn. Trong bài báo này, chúng tôi đề xuất và tiến hành
thực nghiệm thuật toán Hill kết hợp với mã OTP để mã
hóa và giải mã thông điệp dựa trên ngôn ngữ lập trình
Python. Đề xuất của bài báo nhằm giải quyết khó khăn
trong việc chọn khóa có tính khả nghịch cho thuật toán
mã hóa Hill. Đây là thuật toán dựa trên sự kết hợp của
mã dòng và mã khối, sử dụng hàm băm SHA256 để sinh
khóa OTP ban đầu. Thuật toán AES để sinh khóa OTP
tiếp theo cho mỗi khối dữ liệu 256 bit. Thuật toán này sẽ
tăng tốc độ mã hóa và giải mã, tăng tính bảo mật, giảm
độ dài khóa bí mật, đồng thời thuật toán cònxác thực
được nội dung của thông điệp và bảo mật được khóa ban
đầu nhờ hệ mật khóa công khai RSA và thuật toán Hill.
TÀI LIỆU THAM KHẢO
Hình 5 Chuyển đổi ma trận 2x2 [1] Nguyễn Đức Toàn, Nguyễn Văn Tảo, (2016), “Thiết kế các bộ
tạo dãy giả ngẫu nhiên có chu kỳ cực đại”, Tạp chí Khoa học và
Công nghệ, Chuyên san Khoa học Tự nhiên Kỹ thuật – Đại học
Thái Nguyên, ISSN 1859-2171, Tập 159, Số 14, tr 115 – 118.
[2] Nguyễn Đức Toàn, Bùi Thế Hồng, Nguyễn Văn Tảo, Trần
Mạnh Hường, (2016), “Mã hóa và xác thực thông điệp bằng
thuật toán mật mã với khóa sử dụng một lần”, Kỷ yếu Hội nghị
Khoa học Công nghệ Quốc gia lần thứ IX (FAIR’9), Nhà xuất
bản Khoa học Tự nhiên và Công nghệ, ISBN 978-604-913-472-
2, tr 284 -289.
[3] Nguyễn Đức Toàn, Nguyễn Văn Tảo, (2016), “Kết hợp phương
thức xử lý mã OTP và mã khối để mã hóa và giải mã thông
điệp”, Hội thảo toàn quốc về Điện tử, Truyền thông và Công
nghệ thông tin REV/ECIT 2016, Nhà xuất bản Công thương,
Chủ đề: 4-1, tr 191 – 196.
[4] Ioannis Tsamardinos, Laura E. Brown,(2006), “The Max-Min
Hill-Climbing Bayesian Network Structure Learning
Algorithm”, Machine Learning volume 65, pages31–78.
[5] N.J.Croft and M.S.Olivier (2005). “Using an approximated
One-Time Pad to Secure ShortMessaging service(SMS)”.
SATNAC 2005 Proceedings.
[6]. Raman Kumar,Roma Jindal, Abhinav Gupta , SagarBhalla,
HarshitArora (2011). "A Secure Authentication System-Using
Enhanced One Time Pad Technique". IJCSNS International
Journal of Computer Science and Network Security,VOL.11
No.2,February 2011.
[7] SharadPatil , Ajay Kumar (2010). "Effective Secure Encryption
Scheme(One Time Pad) using Complement Approach".
International Journal of Computer Science & Communication,
Hình 6 Chuyển đổi ma trận 3x3 Vol.1,No.1,January-June 2010, pp.229-233.
[8]. SharadPatil ,ManojDevare , Ajay Kumar (2007). "Modified One
Time Pad Data Security Scheme: Random Key Generation
IV. KẾT LUẬN Approach". International Journal of Computer Science and
Sự phát triển vượt bậc của công nghệ thông tin và Security (IJCSS) ,Volume (3): Issue(2).
truyền thông đã đem lại rất nhiều ứng dụng trong thực tế
và thu được những kết quả hết sức to lớn thúc đẩy xã
ISBN 978-604-80-5958-3 225
nguon tai.lieu . vn
