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 tố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 Tồn2
Trường Đại học Tài nguyên và Môi trường Hà Nội
Email:

1

2

Học viện Phụ nữ Việt Nam
Email:

Abstract:
Trong bài báo này chúng tơi đề xuất kết hợp phương pháp
mã hóa Hill và 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. Thuật tốn mã hóa Hill là
thuật tốn dễ dàng, tuy nhiên cái khó khăn là chọn khóa làm
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
đề xuất dùng mã OTP làm khóa cho thuật tốn mã hóa Hill.
Trong phần thực nghiệm chúng tơi chọn khóa có kích thước
2x2 và 3x3. Do đó khóa nhận được là có tính ngẫu nhiên.
Keywords- Python, Hill, OTP, mã hóa, giải mã.

I.

điều kiện sau [1]:

GIỚI THIỆU

Với sự phát triển nhanh chóng của công nghệ
thông tin, bảo mật thông tin ngày càng trở nên quan
trọng. Trước đây, người ta thường dùng phương pháp
mật mã (cryptography) để bảo mật thông tin. Tuy nhiên,
khi sử dụng phương pháp này, đối tượng cần
bảo mật được chuyển thành dạng mật mã khó hiểu nên
gây sự chú ý nhiều hơn. Điều này làm cho những kẻ
xấu ln tìm cách giải mã để hiểu được nội dung của
đối tượng được bảo vệ đó. Nhằm tránh gây sự chú ý,
một phương pháp bảo mật khác được đề xuất và sử
dụng rộng rãi là giấu tin mật. Thông tin cần bảo vệ
được ẩn giấu trong một đối tượng mang tin, thường là
ảnh, video, âm thanh, văn bản,… Kỹ thuật này có ưu
điểm là thông tin không chỉ được bảo vệ mà cịn che
giấu được sự tồn tại của nó.
Mật mã đối xứng sử dụng cùng một khóa cho việc mã
hóa và giải mã. Có thể nói mã đối xứng là mã một khố
hay mã khóa riêng hay mã khố thỏa thuận. Ở đây
người gửi và người nhận chia sẻ khoá chung K, mà họ
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à
hàm biến đổi bản mã trở về bản rõ. Giả sử X là văn bản
cần mã hóa và Y là dạng văn bản đã được thay đổi qua
việc mã hóa. Khi đó ta ký hiệu:
Y = EK (X)
X = DK (Y)

ISBN 978-604-80-5958-3


Mọi thuật toán mã cổ điển đều là mã khoá đối xứng, vì
ở đó thơng tin về khóa được chia sẻ giữa người gửi và
người nhận. Mã đối xứng là kiểu duy nhất trước khi phát
minh ra khố mã cơng khai (cịn được gọi là mã không
đối xứng) vào những năm 1970. Hiện nay các mã đối
xứng và công khai tiếp tục phát triển và hồn thiện. Mã
cơng khai ra đời hỗ trợ mã đối xứng, khơng thay thế nó,
do đó mã đối xứng đến nay vẫn được sử dụng rộng rãi.
Định nghĩa một số khái niệm cơ bản về mã hóa.
Một hệ mật mã là một bộ 5 (P,C,K,E,D) thoả mãn các

221

P (Plaintext) là một tập hợp hữu hạn các bản rõ và được
gọi là không gian bản rõ.
C (Ciphertext) là tập các hữu hạn các bản mã và được
gọi là không gian các bản mã.
K (Key) là tập hữu hạn các khố hay cịn gọi là khơng
gian khố. Đối với mỗi phần tử k của K được gọi là
một khoá (Key). Số lượng của khơng gian khố phải
đủ lớn để khơng có đủ thời gian thử mọi khố;
E (Encrytion) là tập hợp các qui tắc mã hóa có thể.
D (Decrytion) là tập hợp các qui tắc giải mã có thể.
Đối với mỗi 𝑘 ∈ 𝐾 có một quy tắc mã 𝑒𝑘: 𝑃 → C và
một quy tắc giải mã tương ứng dk ∈ D.
Mỗi ek: P → C và dk: C → P là những hàm mà:
𝑑𝑘(𝑒𝑘(𝑥)) = 𝑥 với mỗi x ∈ P.
Chúng ta đã biết một thông tin thường được tổ chức
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
được gửi đi trên một đường truyền tới người nhận, sau
khi nhận được bản mã người nhận giải mã nó để tìm
hiểu nội dung.
Thuật toán dùng khi sử dụng định nghĩa hệ mật mã:
𝑒𝑘(𝐶) = 𝑃, 𝑑𝑘(𝑃) = 𝐶
Một mã đối xứng có các đặc trưng là cách xử lý thơng
tin của thuật tốn mã, giải mã, tác động của khóa vào
bản mã, độ dài của khóa. Mối liên hệ giữa bản rõ, khóa
và bản mã càng phức tạp càng tốt, nếu tốc độ tính tốn
là chấp nhận được [3]. Cụ thể hai u cầu để sử dụng an
tồn mã khố đối xứng là:
+) Thuật tốn mã hố mạnh. Có cơ sở tốn học vững
chắc đảm bảo rằng mặc dù cơng khai thuật tốn, mọi


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à
phức tạp nếu khơng biết khóa.
+) Khố mật chỉ có người gửi và người nhận biết. Có
kênh an tồn để phân phối khố 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
nhận biết được.
Phần còn lại của bài báo được tổ chức như sau: trong
phần II, chúng tơi miêu tả thuật tốn. Trong phần III,
chúng tôi xây dựng demo IV cung cấp các kết quả mơ
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
phần IV.

II.

THUẬT TOÁN HILL VÀ MÃ OTP

2.1 Thuật toán Hill
Mã hoá Hill phát minh bởi Lester S. Hill năm 1929, là
mật mã cổ điển cho phép mã hoá hai, hoặc ba, hoặc
nhiều hơn các ký tự (theo lý thuyết) tại cùng thời điểm.
Mã hoá Hill sử dụng hai lý thuyết tốn học cực kì quan
trọng trong ngành mật mã là Đại số tuyến tính và Số học
mơ-đun [8].
Để thuật tiện cho q trình mã hố, quy ước mỗi chữ cái
trong bảng chữ cái tương ứng với một giá trị theo thứ tự
tăng dần. Vì thuật tốn Hill thực hiện việc mã hoá theo
khối block gồm m ký tự tại cùng một thời điểm.
Bước 1: Mã hóa
Cho biết khố K và thơng điệp P, mã hố Hill thực hiện
phép nhân ma trận giữa K và P để mã hoá thông điệp tạo
bản mã C.
𝐾 ⋅ 𝑃 ≡ 𝐶(𝑚𝑜𝑑26)
Để mã hố một thơng điệp, chúng ta cần tạo một
khố K. Khố này là bí mật và chỉ giữa những người
trao đổi thơng tin với nhau biết được. Khố phải đảm
bảo 2 tính chất:
 K có độ dài là m x m (bình phương độ dài khối
block m)
 K là ma trận khả nghịch theo modulo 26
𝐾 ⋅ 𝐾 −1 ≡ 1 (𝑚𝑜𝑑26)
𝐾 −1 là ma trận nghịch đảo của K trên vành Z26
Trong thuật toán này mã khoá hợp lệ là khố có độ dài

2x2 hoặc 3x3 và khả nghịch theo modulo 26.
Thỏa mãn: Khóa phải có độ dài là số chính phương. [7]
Bước 2: Giải mã
Cho biết khố 𝐾 và bản mã 𝐶, mã hoá Hill thực hiện
phép nhân ma trận nghịch đảo 𝐾 −1 và bản mã 𝐶 để tạo
thông điệp gốc 𝑃.
𝐾 −1 ⋅ 𝐶 ≡ 𝑃(𝑚𝑜𝑑26)
Trước hết, để tìm ma trận nghịch đảo 𝐾 −1 , chúng ta đã
biết theo lý thuyết đại số tuyến tính:
𝐾 −1 = 1𝑑𝑒𝑡(𝐾). 𝐾 ∗
Trong đó 𝑑𝑒𝑡(𝐾) là định thức ma trận K, và 𝐾 ∗ là ma
trận liên hợp của 𝐾. Tuy nhiên đối với mã hoá Hill,
chúng ta đang cần tìm ma trận nghịch đảo 𝐾 −1 theo
modulo 26, công thức trở thành:
𝐾 −1 = det(𝐾)−1 . 𝐾 ∗ (𝑚𝑜𝑑26)

ISBN 978-604-80-5958-3

222

Trong đó, 𝑑𝑒𝑡𝐾 −1 là nghịch đảo của 𝑑𝑒𝑡(𝐾) theo
modulo 26:
𝑑𝑒𝑡𝐾 ∗ det(𝐾)−1 ≡ 1(𝑚𝑜𝑑26)
Chúng ta tìm được nghịch đảo của 𝑑𝑒𝑡(𝐾) bằng cách
lặp các giá trị từ 0 tới 25, nhân với 𝑑𝑒𝑡(𝐾) và lấy dư
phép chia 26, giá trị thoả mãn chia 26 dư 1 chính là
det(𝐾)−1
2.2 Mã OTP
Hệ mật mã với khóa sử dụng một lần OTP (One Time
Pad) là một hệ mật mã dòng, đã được chứng minh có độ

an tồn hồn hảo. Đặc điểm nổi bật của hệ mật này là
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
này là độ dài của khóa phải bằng đúng độ dài của bản rõ
và một yêu cầu rất khắt khe nữa là các khóa phải được
sinh thực sự ngẫu nhiên. Đây là một điều kiện rất khó
thực hiện ngay cả các chuỗi ngẫu nhiên được sinh tự
động bằng máy tính cũng mới chỉ là giả ngẫu nhiên vì
chúng phụ thuộc vào một cái nhân (seed) cho trước[4].
Lược đồ này gồm ba qui trình sau:
Bước 1 Mã hóa:
Chia bản rõ thành các khối có kích thước bằng 256 bit.
Nếu khơng chẵn thì phải chèn thêm cho đủ một khối.
Băm bản rõ bằng một hàm băm với giá trị băm có kích
thước bằng 256 bit. Giá trị băm này được chọn làm khóa
OTP khởi đầu, gọi là K1 . Sau đó, K1 sẽ được XOR với
khối bản rõ thứ nhất để tạo ra khối bản mã thứ nhất. Các
khóa OTP tiếp theo, K i (i >= 2) sẽ được sinh ra bằng
cách mã hóa khối bản rõ thứ i − 1 bằng hệ mật AES256
với khóa K i−1 . Các khóa mới được sinh ra lại được
XOR với khối bản rõ tương ứng để tạo ra các khối bản
mã tiếp theo. Ghép tất cả các khối bản mã để thu được
bản mã.
Bước 2 Ký bản rõ và gửi bản mã:
Khóa K1 được mã hóa bằng khóa bí mật của người gửi.
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
mã.
Bước 3 Xác thực và giải mã: Người nhận sử dụng khóa
bí mật của mình và khóa cơng khai của người gửi để

giải mã ra khóa K1 . Chia bản mã thành các khối có kích
thước 256 bit sau đó làm tương tự như q trình mã hóa
để thu được bản rõ.
Lược đồ trên, đã lấy giá trị băm của bản rõ làm khóa
OTP. Vì các bản rõ là những văn bản bất kỳ nên giá trị
băm của chúng là các chuỗi bit ngẫu nhiên và gần như là
duy nhất đối với mỗi bản rõ. Việc chọn giá trị băm làm
khóa OTP đã làm giảm đáng kể độ dài của khóa đối với
những bản rõ có dung lượng lớn. Các khóa tiếp theo
được sinh ra bằng thuật toán AES trên khối bản rõ tương
ứng với khóa được sinh ra trước đó vẫn đảm bảo được
tính OTP.
Trong hệ mã với khóa sử dụng một lần OTP (One _Time Pad) mỗi byte của bản rõ được mã hóa bằng một
byte của luồng khóa và mỗi byte khóa chỉ được sử dụng
đúng một lần và không bao giờ được sử dụng lại. Trong
hệ mật mã này độ dài của khóa phải bằng đúng độ dài


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ự
ngẫu nhiên, tức là mọi byte của khóa có thể nhận bất kỳ
giá trị nào trong khoảng từ 0 đến 255 với xác suất như
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
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õ.
Việc mã hóa bằng OTP thường được ký hiệu là:
Ci = Pi  K i , (i = 1, 2, 3, . . . )
Trong đó Pi là ký tự thứ i của bản rõ, K i là byte thứ

i của khóa được sử dụng để mã hóa bản rõ này và Ci là
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ã
hóa OTP nhưng vẫn có thể được thay bằng phép tốn
khác.
Q trình giải mã được làm tương tự như mã hóa :
Pi = Ci  K i
Tuy nhiên, phương pháp One_Time_ Pad khơng có ý
nghĩa sử dụng thực tế vì chiều dài khóa bằng chiều dài
bản tin, mỗi khóa chỉ sử dụng một lần, nên thay vì
truyền khóa trên kênh an tồn thì có thể truyền trực tiếp
bản rõ mà không cần quan tâm đến vấn đề mã hóa nữa.
2.3 Kết hợp thuật tốn Hill và mã OTP

Bước 4: Tính ma trận nghịch đảo
et = np.linalg.det(matrix)
if math.gcd(int(round(det)), len(alphabet)) == 1:
matrix = Matrix(matrix)
return np.array(matrix.inv_mod(len(alphabet)))
else:
return None
Bước 5: Giải mã
plaintext = ""
ciphervector = [0 for i in range (n)]
messagevector = [0 for i in range (n)]
block = 0
while block * n < len(_ciphertext):
for i in range (n):
ciphervector[i] = char_to_int(_ciphertext[i +
block * n], alphabet)

print("Cipher vector: ")
print(ciphervector)
for i in range (n):
messagevector[i] = 0
for j in range (n):
messagevector[i] += invkmatrix[i][j] *
ciphervector[j]
print(messagevector[i])
plaintext += str(int_to_char(messagevector[i],
alphabet))
block += 1
return plaintext

Bước 1: Mã hóa
def int_matrix_to_str(matrix, alphabet):
word = ""
n = len(matrix)
for i in range (n):
for j in range (n):
word += int_to_char(matrix[i][j], alphabet)
return word
Bước 2: Tạo ma trận có đảo ngược ngẫu nhiên
def gen_random_inv_matrix(n, alphabet):
matrix = gen_random_matrix(n, alphabet)
while not is_invertible_matrix(matrix, alphabet):
matrix = gen_random_matrix(n, alphabet)
return matrix
Bước 3: Tạo khóa dùng mã OTP
if len(word) <= 0:
return None

n = int(math.sqrt(len(word)))
if n * n != len(word):
return None
matrix = [[0 for i in range (n)] for j in range (n)]
k = 0 (Đây là khóa khởi đầu cho luồng OTP)
for i in range (n):
for j in range (n):
matrix[i][j] = char_to_int(word[k], alphabet)
k1 XOR Ci
Các khóa OTP tiếp theo, 𝐾𝑖 (𝑖 = 2, 3, . . . , 𝑛) sẽ
được sinh ra bằng cách mã hóa khối bản rõ 𝑃𝑖−1 bằng
hệ mật AES256 với khóa 𝑘𝑖−1 . Các khóa mới được sinh

ISBN 978-604-80-5958-3

ra lại được XOR với khối bản rõ tương ứng để tạo ra
các khối bản mã tiếp theo.
return matrix

223

2.4 Đánh giá độ an tồn
Khóa OTP đề xuất kết hợp với thuật tốn Hill có khả
năng xác thực nguồn gốc và tính tồn vẹn của bản tin
nhận được. Vì thế ngồi khả năng chống được các dạng
tấn công đối với các hệ mã khối thông thường khác,
thuật tốn cịn có thể chống lại một số dạng tấn công giả
mạo trong thực tế [5].
Ngoại trừ khối đầu tiên được mã hóa và giải mã theo
phương pháp của các hệ mã lũy thừa như: RSA,

Elgamal…thì các khối cịn lại của bản tin được mã
hóa/giải mã hồn tồn theo nguyên tắc của hệ mã OTP.
Vì thế, về căn bản hiệu quả thực hiện của thuật toán kết
hợp tương đương với hệ mã OTP.
Trong phần thực nghiệm chúng tôi đã để khóa dưới
dạng ma trận 2x2 và 3x3. Các khóa này được tạo ra
hoàn toàn ngẫu nhiên mà người dùng khơng cần phải
tính xem khóa có độ dài là số chính phương.
III. KẾT QUẢ
Trong phần này, chúng tơi thực hiện các mơ phỏng
thuật tốn Hill kết hợp với mã OTP để mã hóa và giải
mã thơng điệp bằng các cơng thức đã được trình bày ở


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 hồn tồ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 tố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 tố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 tốn
mã hóa Hill. Đây là thuật tố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 tố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 tố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 tốn Hill.
TÀI LIỆU THAM KHẢO
Hình 5 Chuyển đổi ma trận 2x2

Hình 6 Chuyển đổi ma trận 3x3
IV.

KẾT LUẬN
Sự phát triển vượt bậc của công nghệ thông tin và
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

[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 tố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-4722, 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 tồ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,
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
Approach". International Journal of Computer Science and
Security (IJCSS) ,Volume (3): Issue(2).