Một phương pháp xây dựng hệ mật pohlig - Hellman trên vành đa thức

Ngô Đức Thiện 
MỘT PHƯƠNG PHÁP XÂY DỰNG 
HỆ MẬT POHLIG-HELLMAN 
TRÊN VÀNH ĐA THỨC 
Ngô Đức Thiện 
Học viện Công nghệ Bưu chính Viễn thông 
Tóm tắt: Cho đến nay, cách thức mã hóa và giải mã của 
hệ mật khóa bí mật chủ yếu sử dụng các phép hoán vị, phép 
thay thế, lai ghép hai phép này, hoặc phép xử lý bit. Bài 
báo này đề xuất một phương pháp thực hiện hệ mật khóa 
bí mật nhưng dựa trên bài toán logarit rời rạc, trong đó 
phép mã hóa và giải mã được thực hiện bằng hàm lũy thừa 
các đa thức theo modulo, theo cách tương tự như hệ mật 
Pohlig-Hellman. Cùng với đó, bài báo cũng đề xuất thuật 
toán thực hiện hàm lũy thừa này. 
Từ khóa: Hệ mật khóa bí mật, bài toán logarit rời rạc, 
hệ mật Pohlig-Hellman, vành đa thức, trường số. * 
I. GIỚI THIỆU 
Hệ mật khóa bí mật [1], [3], [4]) (hay còn được biết 
đến là hệ mật khóa đối xứng) có lịch sử phát triển rất lâu 
đời. Phương pháp xây dựng hệ mật khóa bí mật cũng khá 
đơn giản, không có phép toán học nào đặc biệt mà chủ yếu 
dựa vào các phép thay thế, phép hoán vị, hoặc sử dụng cả 
hai phép này như các hệ mật DES hay AES; hoặc phương 
pháp xử lý bít như trong các hệ mật mã dòng (Stream 
cipher). Khi sử dụng lai ghép phép thay thế với phép hoán 
vị, thông thường các hệ mật đều hay sử dụng phép thay thế 
phi tuyến nhằm tăng độ an toàn. Sơ đồ chức năng của hệ 
mật khóa bí mật như hình 1. 
Hình 1. Sơ đồ chức năng của hệ mật khóa bí mật 
Hệ mật này có các ưu điểm nổi bật là tốc độ mã hóa và 
giải mã nhanh, hệ số mở rộng bản tin thấp. Chính vì thế 
các hệ mật khóa bí mật hay được dùng để mã hóa bảo mật 
dữ liệu hoặc trong các ứng dụng bảo mật thời gian thực. 
Tuy nhiên, các nhược điểm lớn nhất của hệ mật này là 
việc sinh khóa, lưu trữ khóa và bảo vệ khóa khá phức tạp, 
nhất là khi số lượng người dùng trên mạng tăng cao. Ngoài 
ra, các hệ mật này còn phải sử dụng kênh an toàn để phân 
Tác giả liên hệ: Ngô Đức Thiện, 
Email: thiennd@ptit.edu.vn 
Đến tòa soạn: 5/2020, chỉnh sửa: 6 /2020, chấp nhận đăng: 7/2020. 
phối khóa dẫn đến chi phí tăng; hoặc phải sử dụng một 
giao thức thỏa thuận khóa an toàn. Các hệ mật này cũng 
khó thực hiện được các dịch vụ như xác thực, chữ ký số, 
thương mại điện tử 
Các hệ mật khóa công khai (hay hệ mật khóa bất đối 
xứng) thường được xây dựng trên các bài toán một chiều. 
Một trong các hàm một chiều sử dụng nhiều đó là bài toán 
logarit rời rạc, với các hệ mật như: trao đổi và thỏa thuận 
khóa Diffie-Hellman, hệ mật Omura-Massey, Pohlig-
Hellman, hệ mật và chữ ký số ElGamal, hệ mật trên đường 
cong elliptic... 
 Bài toán logarit rời rạc thường được thực hiện trên 
trường số, các dữ liệu bản rõ và bản mã được biểu diễn bằng 
các con số nguyên dương trong trường số GF p( ) với p là 
số nguyên tố. Từ các nghiên cứu trong [6] cho thấy sự đẳng 
cấu giữa vành đa thức có 2 lớp kề cyclic với trường số, và 
do đó ta có thể thực hiện bài toán logarit rời rạc trên các đa 
thức, khi đó dữ liệu sẽ được mô tả bằng các đa thức. 
Bài báo này đề xuất một phương pháp thực hiện một hệ 
mật mã khóa bí mật với phép mã hóa và giải mã là hãm lũy 
thừa các đa thức trên vành đa thức có hai lớp kề cyclic. 
Cùng với đó, bài báo cũng đề xuất thuật toán tính hàm lũy 
thừa của đa thức theo modulo. Cấu trúc bài báo chia thành 
5 phần, sau phần giới thiệu là các phần: phần 2 hệ mật 
Pohlig-Hellman; phần 3 cấu trúc tựa đẳng cấu giữa vành đa 
thức có hai lớp kề cyclic và trường số; phần 4 đề xuất hệ 
mật Pohlig-Hellman trên vành đa thức có 2 lớp kề cyclic và 
cuối cùng là phần kết luận. 
II. HỆ MẬT POHLIG-HELLMAN 
A. Bài toán logarit rời rạc 
Cho đến này chưa có thuật toán hiệu quả nào để giải bài 
toán logarit rời rạc tổng quát. Có nhiều thuật toán phức tạp, 
thường sinh ra từ những thuật toán tương tự như bài toán 
phân tích thừa số, chúng chạy nhanh hơn các thuật toán thô 
sơ, nhưng vẫn còn chậm hơn so với thời gian đa thức. Có 
thể kể đến một số thuật toán như: baby-step giant-step, 
Pollard, Pohlig-Hellman, COS, index calculus... 
Tóm tắt bài toán logarit rời rạc như sau [1], [2]: 
(Oscar) 
(Alice) 
Nguồn tin 
Bộ mã 
hóa 
Thám mã 
Kênh mở 
(không an toàn) 
Bộ giải 
mã 
Nhận tin 
Nguồn khóa 
Kênh an toàn 
Bản rõ Bản mã Bản rõ Bản mã 
(Bob) K K 
M C C M 
MỘT PHƯƠNG PHÁP XÂY DỰNG HỆ MẬT POHLIG-HELLMAN TRÊN VÀNH ĐA THỨC 
Xét một vành số ℤ𝑝, nếu 𝑝 là nguyên tố thì ℤ𝑝 là một 
trường (ℤ𝑝 = 𝐺𝐹(𝑝)). Tập tất cả các phần tử khác 0 của 
trường sẽ tạo nên một nhóm nhân cyclic ℤ𝑝
∗ . 
 ℤ𝑝
∗ = ℤ𝑝 /{0} = {1,2,  , 𝑝 − 1} () 
- Cho 𝑔 ∈ ℤ𝑝
∗ là một phần tử sinh (nguyên thủy) của 
nhóm nhân. 
- Cho 𝑦 ∈ ℤ𝑝
∗ , yêu cầu hãy tìm 𝑥 (nếu tồn tại) sao cho: 
𝑔𝑥 = 𝑦, tức là: 𝑥 = log𝑔 𝑦. 
Nhận xét: ∀𝑦 ∈ ℤ𝑝
∗ thì: 
- Bài toán có nghiệm khi 𝑔 là phần tử nguyên thủy. 
- Bài toán có thể không có nghiệm khi 𝑔 bất kỳ. 
Ví dụ 1: Xét 𝑝 = 17 và 𝑔 = 3 là phần tử nguyên thủy 
của nhóm nhân ℤ17
∗ , ta có các giá trị 3𝑡 và log3 𝑡 như trong 
bảng 1 (Chú ý, các phép tính đều lấy theo modulo của 17). 
BẢNG 1. GIÁ TRỊ HÀM MŨ VÀ LOGARIT RỜI RẠC CƠ SỐ 3 CỦA CÁC PHẦN 
TỬ TRONG NHÓM NHÂN ℤ17
∗ . 
𝑡 1 2 3 4 5 6 7 8 
3𝑡 3 9 10 13 5 15 11 16 
log3 𝑡 16 14 1 12 5 15 11 10 
𝑡 9 10 11 12 13 14 15 16 
3𝑡 14 8 7 4 12 2 6 1 
𝑙𝑜𝑔3 𝑡 2 3 7 13 4 9 6 8 
Từ bảng 1 ta nhận thấy cả hàm mũ và hàm logarit rời 
rạc đều không phải hàm đồng biến và nó phân bố ngẫu 
nhiên. Với trường hợp 𝑝 nhỏ thì việc tính 
g
x ylog= dễ 
dàng có được từ việc tính toàn bộ các số 
xy g= như trong 
bảng 1. Nhưng khi 𝑝 lớn (từ vài trăm bit trở lên) thì số lượng 
phép tính sẽ lớn hơn rất nhiều và khó có thể giải được. 
Bài toán logarit rời rạc không phải lúc nào cũng khó, độ 
khó của nó phụ thuộc vào các nhóm nhân được lựa chọn. 
Ví dụ, các hệ mật dựa trên phép logarit rời rạc thường chọn 
các nhóm nhân ℤ𝑝
∗ trong đó 𝑝 là số nguyên tố lớn. Tuy 
nhiên, nếu 𝑝 − 1 có thừa số là các số nguyên tố nhỏ, thì có 
thể sử dụng thuật toán Pohlig-Hellman để giải bài toán 
loga ... 
i I
a x f x x x
a f
Î
Î
= Î +
= Î
å
åa
Z
Z
và coi lũy đẳng 
1
0 0
( ) 0
n i
i
e x x
-
=
= =å . 
Khi đó ta có thể coi đây là một ánh xạ 1-1 giữa các phần 
tử của 
2
[ ]/ ( 1)nx x +Z với các phần tử của ( )GF p . Như 
vậy, vành đa thức có hai lớp kề cyclic và trường ( )GF p 
với 2 1np = - (𝑝 – nguyên tố) được gọi là tựa đẳng cấu 
(quasi-isomorphism). Ta có thể so sánh việc thực hiện các 
phép toán cộng và nhân trên hai cấu trúc này như bảng 2. 
BẢNG 2: PHÉP CỘNG VÀ NHÂN TRÊN CẤU TRÚC VÀNH ĐA THỨC VÀ 
TRƯỜNG SỐ. 
Phép 
tính 
Vành đa thức 
2
[ ]/ ( 1)nx x +Z 
Trường số 
( )GF p 
Phép 
cộng 
( )
n
i
i
i I
a x a x
Î Ì
= å
Z
; 
( )
Zn
j
j
j J
b x b x
Î Ì
= å 
( ) ( ) ( )
n
k
k
k K
c x a x b x
c x
Î Ì
= +
= å
Z
( ) ( )K I J I J= È - Ç 
, ( )
( ) mod
a b GF p
c a b
a b p
Î
= +
º +
Phép 
nhân 
n
c x a x b x
a x b x x
( ) ( ) ( )
( ( ) ( )mod( 1))
=
º +
c a b
a b p
.
( . mod )
=
º
Quan hệ tựa đồng cấu chỉ xảy ra đối với một số vành đa 
thức có hai lớp kề cyclic đặc biệt, các vành đa thức này 
được liệt kê dưới đây [7]. 
Số nguyên tố Mersenne: 2 1
np = - 
n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 52, 607, 
1279, 2203, 3217, 4253, 9689, 9941, 19937, , 74207281. 
Vành đa thức có hai lớp kề cyclic [5], [6]: 
n = 5, 11, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 
131, , 523, 613, 1277, 2213, 3203, 3253, 4253, , 
9941, 
IV. HỆ MẬT POHLIG-HELLMAN TRÊN VÀNH ĐA 
THỨC CÓ HAI LỚP KỀ CYCLIC 
A. Mô tả hệ mật 
Trong phần này tác giả đề xuất một phương pháp xây 
dựng hệ mật khóa bí mật theo cách của Pohlig-Hellman. 
Tuy nhiên, hàm mã hóa và giải mã đều là hàm lũy thừa các 
đa thức theo modulo, bản rõ 𝑚(𝑥) và bản mã 𝑐(𝑥) đều biểu 
diễn bằng các đa thức. Mô hình truyền tin của hệ mật như 
mô tả trong hình 2. 
Hình 2. Mô hình truyền tin của hệ mật Pohlig-Hellman 
xây dựng trên vành đa thức 
Mô tả hệ mật như sau: 
+ Tạo khóa: 
Bên Alice tạo khóa bí mật: , ,e d n theo các bước sau: 
Bước 1: chọn số 𝑛 thỏa mãn: 
• 
2
[ ]/ ( 1)nx x +Z là vành đa thức có 2 lớp kề 
cyclic. 
• = −np 2 1 là một số nguyên tố. 
Bước 2: Tính −= −nk 12 1 và chọn số mũ mã hóa e thỏa 
mãn điều kiện: 
gcd( , ) =e k 1 
Chú ý: gcd( , )e k là ước chung lớn nhất của ,e k . 
Sở dĩ ta lấy ước chung lớn nhất của e với k là do k 
chính là cấp cực đại của một phần tử trong vành đa thức 
2
[ ]/ ( 1)nx x +Z như trong biểu thức (8). 
Bước 3: tìm số mũ giải mã d thỏa mãn: 
 . modde k1 () 
Có nhiều cách để giải phương trình (10) tuy nhiên cách 
hiệu quả nhất là sử dụng thuật toán Euclid [2], [3]. 
Khóa mã hóa của Alice là ,e n còn khóa giải mã của 
Bob là bộ số ,d n (hoặc ngược lại). Alice gửi khóa giải mã 
cho Bob qua kênh an toàn, hoặc sử dụng một thủ tục trao 
đổi khóa an toàn nào đó. 
+ Mã hóa: 
Bên Alice cần mã hóa một bản tin rõ là đa thức 
( ) [ ] / +Z nm x x x2 1 , Alice tính: 
 ( ) ( )=
ec x m x () 
Sau đó Alice sẽ gửi ( )c x đến Bob qua kênh mở. 
+ Giải mã: 
Bob nhận bản mã ( )c x , khóa giải mã ,d n và tiến hành 
giải mã theo phương trình sau: 
Nguồn tin 
Bộ mã 
hóa 
Thám mã 
Kênh mở 
(không an toàn) 
Bộ giải 
mã 
Nhận tin 
Nguồn khóa 
Kênh an toàn 
Bản rõ Bản mã Bản rõ Bản mã 
(Alice) 𝒆, 𝒏
 𝒅, 𝒏 
𝒎(𝒙) 𝒄(𝒙) 𝒄(𝒙) 𝒎(𝒙) 
(Oscar) 
(Bob) 
MỘT PHƯƠNG PHÁP XÂY DỰNG HỆ MẬT POHLIG-HELLMAN TRÊN VÀNH ĐA THỨC 
( ) ( ) [ ( )]
( ) ( )
d e d
ed
m x c x m x
m x m x
= =
= =
 () 
Ví dụ 2: 
+ Tạo khóa: 
Bước 1: Alice chọn =n 5 thỏa mãn +x 5 1 là vành đa 
thức có hai lớp kề cyclic và = − =p 52 1 31 là số nguyên 
tố. 
Bước 2: Alice tính −= − =k 5 12 1 15 và chọn =e 13 
thỏa mãn gcd( , ) ( , )= =gcdk13 13 15 1 
Bước 3: Tính =d 7 thỏa mãn . mod7 13 1 15 
+ Mã hóa: 
Giả sử Alice cần gửi bản tin rõ ( )m x cho Bob: 
( ) ( , , )= + + m x x x3 41 0 3 4 
Chú ý: ( , , )0 3 4 là biểu diễn dạng số mũ của đa thức 
x x x x x+ + = + +3 4 0 3 41 . 
Alice tính: 
( ) ( ) ( )
( , , )
ec x m x x x
x x x
= = + +
= + + 
3 4 13
2 3
1
1 2 3
Sau đó Alice gửi ( )c x qua kênh mở cho Bob. 
+ Giải mã: 
Bob nhận ,= =5 7n d và ( )c x và giải mã: 
( ) ( ) ( )
( ) ( , , )
dm x c x x x x
x x
= = + +
= + + 
2 3 7
3 41 0 3 4
B. Thuật toán tính lũy thừa của đa thức theo modulo 
+nx 1 
Thông thường các hệ mật sử dụng bài toán logarit rời 
rạc đều phải thực hiện lũy thừa các số theo modulo trên 
trường số và người ta thường sử dụng thuật toán nhân và 
bình phương [1], [3], [4]. 
Với hệ mật đề xuất như trong bài báo cũng phải thực 
hiện phép lũy thừa nhưng là lũy thừa đa thức theo modulo 
của +nx 1 . Dựa vào một tính chất đặc biệt của đa thức sau 
đây, bài báo đưa ra thuật toán tính lũy thừa cho đa thức. 
Xét đa thức ( ) [ ] / +Z
na x x x2 1 : 
( ) ... −−= + + + +
n
na x a x a x a x a x
0 1 2 1
0 1 2 1 
với [ , ] ia 0 1 . 
Biểu diễn dạng số mũ (chỉ cho các 
i
a 1= ): 
( )ˆ( ) , , ,..., ( )na x a a a a a n− = −0 1 2 10 1 2 1 
+ Nếu một số k có dạng uk = 2 khi đó: 
. mod[ ( )] ( )[ ]
u
n
k i k n
i
i
a x a x a x
−
=
= = 
1
2
0
 () 
Dạng mũ: 
ˆ( ) ( mod , mod ,
mod ,..., ( ) mod )
k
n
a a k n a k n
a k n a n k n−
=
−
0 1
2 1
0 1
2 1
 () 
Chứng minh: 
lÇn
u
u
ka x a x a x2 2 2 2...2[ ( )] [ ( )] ((([ ( )] ) ) )= =
6447 448
Mà : 
n n
i n i j n
i i j
i i j
i j
a x a x a a x
1 1
2 2 2 mod ( ) mod
0 , 0;
[ ( )] 2
- -
+
= =
¹
= +å å Ta 
thấy với i j¹ : 
( ) mod ( ) mod ( ) mod2
0
i j n i j n i j n
i j i j i j
a a x a a x a a x+ + += +
=
do phép cộng đa thức là cộng modulo 2. 
Vì thế: 
n
i j n
i j
i j
i j
a a x
1
( ) mod
, 0;
2 0
-
+
=
¹
=å 
Vậy ta có: 
n
i n
i
i
a x a x
1
2 2 2 mod
0
[ ( )]
-
=
= å 
Tương tự như thế ta tính được: 
n
i n
i
i
n
i n
i
i
a x a x a x
a x
1
4 2 2 2 2 mod 2
0
1
4 4 mod
0
[ ( )] ([ ( )] ) ( )
-
=
-
=
= =
=
å
å
Tổng quát: 
u u u u
n n
i n i n
i i
i i
a x a x a x
1 1
2 2 2 mod 2 mod
0 0
[ ( )]
- -
= =
= =å å 
Chú ý: do 
i
a [0,1]Î nên 
u
i i
a a2 = 
Điều phải chứng minh 
Ví dụ 3: xét ˆ; ( ) ( , , )= = + +  =n a x x x a
3 45 1 0 3 4 
- Nếu k = 2 thì: 
. mod . mod[ ( )] = + + = + +a x x x x x2 3 2 5 4 2 5 31 1 
- Nếu k = =32 8 thì: 
ˆ( ) ( * mod , * mod , * mod )
( , , ) ( , , )
=
= =
8 0 8 5 3 8 5 4 8 5
0 4 2 0 2 4
a
Tức là để tính lũy thừa [ ( )]
ka x ta chỉ việc nhân các số 
mũ của từng đơn thức x trong ( )a x với k rồi lấy modulo 
theo n như biểu thức (13), (14). 
Dựa vào tính chất này của đa thức ta có thể tính lũy thừa 
bất kỳ cho đa thức ( )a x như sau: 
Cho k nguyên dương và có phân tích như sau: 
tu
t
t t
k k= = 2 
Ngô Đức Thiện 
Ví dụ: = = + + = + +k 0 1 419 2 2 2 1 2 16 
t
u k kˆ (0,1, 4); [ ] [1,2,16]= = = 
Khi đó phép lũy thừa [ ( )] mod( )+
k na x x 1 có thể tính 
như sau: 
 ( ) ( )] [ ( )][
ut
t
k k
t t
a x a x a x= =  2 
Thuật toán tính lũy thừa của đa thức theo modulo 
+nx 1 như sau: 
Thuật toán: Tính lũy thừa các đa thức theo modulo 
nx +1 
Vào: ˆ, ( , ,..., ) , , ,...,[ ]r r t tn a a a a k k k k = =1 2 1 1 2 1 
Ra: ˆ ˆ( ) mod( )= +k nb a x 1 
[1] ˆ ( )b 0 , if =k 0 then return bˆ 
[2] For i from 1 to t do: 
[2.1] for j from 1 to r do: 
. modj j iA a k n 
[2.2]: ˆˆ .ˆb b A 
[3] Return (bˆ ) 
Chú thích 
+ Số n đảm bảo [ ] /
nx x +2 1Z là vành đa thức có 2 
lớp kề cyclic và np = −2 1 là số nguyên tố. 
+ Đa thức ( ) [ ] /
na x x x +2 1Z ; dạng số mũ 
ˆ( ) ( , ,..., )r ra x a a a a  = 1 2 1 độ dài aˆ là r n . 
+ Số nguyên k , ( );
nk − −10 2 1 k được biểu diễn 
thành một vector bao gồm t số thập phân 
, ,...,[ ]t tk k k k = 1 2 1 ; trong đó 
tu
ik = 2 : 
[ ]t t t
t
k k k k =  = 1 
+ Mục [1] ˆ ( ) ( )=  = =b b x
00 1 2 ; 
+ Mục [2.1] tập các số jA là biểu diễn dạng mũ của 
đa thức ( )A x ; ˆ( ) ( , ,..., )rA x A A A A = 1 2 . Trong 
một số ngôn ngữ lập trình (như Matlab) có thể dễ 
dàng tính được ngay cho toàn bộ các phần tử trong 
Aˆ mà không cần phải dùng vòng lặp. Tức là ta có 
thể tính trực tiếp ( ) ( . mod ): , ,...,j j iA a k n j r = 1 2
. 
+ Mục [2.2] là phép nhân đa thức theo modulo, đây là 
phép nhân bình thường trên vành đa thức được lấy 
theo modulo của nx +1 . 
+ Kết quả dạng mũ: ˆ ˆ( ) mod( )
k nb a x= +1 
Ví dụ 4: 
xét ˆ; ( ) ( , , ) = = + +  =n a x x x a
2 4
1 35 1 0 2 4 và 
= = + + = + +k 0 2 313 1 4 8 2 2 2 , biểu diễn k như sau: 
[ , , ] =k 1 31 4 8 . Ta có: ;r t= =3 3 
Khi đó ˆ ˆ=b a13 được tính như sau: 
[1] ˆ ( )b  0 
[2] For i from 1 to 3 do: 
▪ :=i 1 (với =k1 1 ) 
 + ˆ ( , , )=A A A A1 2 3 
( * mod , * mod , * mod )
( , , )
=
=
0 1 5 2 1 5 4 1 5
0 2 4
 + ˆ ( )*( , , ) ( , , )b  =0 0 2 4 0 2 4 
▪ 2i = : (với 
2
4k = ) 
 + ˆ ( , , )=A A A A1 2 3 
( * mod , * mod , * mod )
( , , )
=
=
0 4 5 2 4 5 4 4 5
0 3 1
 + ˆ ( , , )*( , , ) ( , , )b  =0 2 4 0 3 1 0 1 4 
▪ :=i 3 (với =k3 8 ) 
 + ˆ ( , , )=A A A A1 2 3 
( * mod , * mod , * mod )
( , , )
=
=
0 8 5 2 8 5 4 8 5
0 1 2
 + ˆ ( , , )*( , , ) ( , , )b  =0 1 4 0 1 2 1 3 4 
[3] Return ˆ ( , , )b = 1 3 4 
Vậy kết quả có được là: 
( ) mod( )+ + + = + +x x x x x x2 4 13 5 3 41 1 
Tiến hành mô phỏng thuật toán nêu trên bằng phần 
mềm Matlab (phiên bản R2016a), cấu hình máy tính: chip 
Intel Core i5 (7th gen), RAM 8GB, hệ điều hành Windows 
64 bits. 
Với mỗi bộ tham số mô phỏng được thực hiện 5000 lần 
và sau đó lấy trung bình thời gian tính toán, một số kết quả 
có được như trong bảng 3. 
BẢNG 3: THỜI GIAN XỬ LÝ CỦA THUẬT TOÁN 
TT Tham số mô phỏng 
Thời gian 
xử lý (ms) 
1 ;n = 5 ;=k 13 ˆ ( , , )=a 0 3 4 ,0 050 
2 ;n =19 .=k 103 567
ˆ ( , , , , , , , , )=a 0 2 5 8 10 11 13 15 17 
,0 164 
MỘT PHƯƠNG PHÁP XÂY DỰNG HỆ MẬT POHLIG-HELLMAN TRÊN VÀNH ĐA THỨC 
3 ;n = 61 . .=k 1 239 878
ˆ ( , , , , , , ,
, , , , , )
=a 1 3 7 12 19 21 29
32 38 45 50 55 59
,0 236 
4 ;n = 107 . . .=k 2 341 235 671
ˆ ( , , , , , , ,
, , , , , )
=a 1 9 17 26 38 47 54
62 74 82 91 98 105
,0 436 
5 ;n = 4253 . . .=k 139 749 574 567
ˆ ( , , , , , , , ,
, , , , )
=
a 1 56 98 147 209 300 478 698
1002 1348 2034 3045 4002
,4 300 
6 ;n =9941
. . . . .k =13 974 957 456 787 957 
ˆ ( , , , , , ,
, , , , ,
, , , , , )
a = 0 100 456 989 1456 2002
2560 3001 3982 4679 5398
6003 7623 7982 8567 9234 9657
,19 300 
Nhận xét: Với các giá trị n nhỏ thì tốc độ tính toán là 
nhanh. Với trường hợp n =4253 tương đương với việc 
tính toán với các con số 4252 bit mà thời gian tính toán của 
một phép lũy thừa là 4,3ms có thể nói là hoàn toàn chấp 
nhận được. Cho đến hiện nay để đảm bảo tính an toàn, các 
hệ mật cũng chỉ dùng các con số từ 1000 đến 2000bit. Với 
trường hợp n =9941 thời gian tính toán với khả năng của 
máy tính laptop như cấu hình ở trên là , ms19 3 . Cho đến 
nay thì chưa cần thiết dùng đến giá trị n lớn như vậy, trong 
tương lai có thể sử dụng đến với các con số lớn hơn, khi 
đó tốc độ tính của máy tính cũng như các chip xử lý sẽ 
nhanh hơn thời điểm hiện tại và như thế sẽ rút ngắn được 
thời gian tính toán và hoàn toàn có thể áp dụng được hệ mật 
này. 
V. KẾT LUẬN 
Bài báo đề xuất phương pháp thực hiện một hệ mật khóa 
bí mật theo cách của hệ mật Pohlig-Hellman. Trong đó, bản 
rõ và bản mã được mô tả bằng các đa thức trên vành đa 
thức, thay vì được mô tả bằng các con số trên trường số. Sở 
dĩ có thể thực hiện được điều này là nhờ cấu trúc tựa đẳng 
cấu của vành đa thức có hai lớp kề cyclic với trường số. 
Độ an toàn của hệ mật này tương đương với độ an toàn 
của các hệ mật khác xây dựng trên bài toán logarit rời rạc, 
cho đến nay với giá trị số nguyên tố lớn thì bài toán logarit 
rời rạc vẫn là bài toán khó. 
Để hệ mật có tính khả thi, bài báo cũng đề xuất thuật 
toán thực hiện hàm lũy thừa cho các đa thức theo modulo. 
Các kết quả mô phỏng cho thấy tốc độ tính toán của thuật 
toán với tường hợp các số lớn là rất khả quan để áp dụng 
vào thực tế. 
TÀI LIỆU THAM KHẢO 
[1] Nguyễn Bình, Giáo trình Mật mã học, Học viện Công nghệ 
BCVT, 2013. 
[2] Frederik Vercauteren, Discrete Logarithms in Cryp-
tography, ESAT/COSIC - K.U. Leuven ECRYPT Summer 
School 2008. 
[3] Jean-Yves Chouinard, ELG 5373, “Secure commu-
nications and data encryption,” School of Information 
Technology and Engineering, University of Ottawa, April 
2002. 
[4] A. Menezes, P. van Oorschot, and S. Vanstone, "Handbook 
of Applied Cryptography", CRC Press, 1996. 
[5] Nguyen Trung Hieu, Ngo Duc Thien, Tran Duc Su, "On 
Constructing Cyclic Multiplicative Groups with Maximum 
Order over Polynomial Rings with Two Cyclotomic 
Cosets", Jounal of scientific research and military 
technology, Vol. 17, February - 2012, pp. 133-140, ISSN 
1859-1043. 
[6] Lê Danh Cường, Nguyễn Bình, “Cấu trúc tựa đẳng cấu 
giữa vành đa thức có 2 lớp kề cyclic và trường số”, Tạp 
chí Khoa học và Công nghệ các trường đại học kỹ thuật, 
ISSN 2354-1083, số 121, 2017, tr. 54-57. 
[7] Nguyễn Trung Hiếu, Ngô Đức Thiện, "Hệ mật Omura-
Massey xây dựng trên vành đa thức có hai lớp kề cyclic", 
Tạp chí khoa học và Công nghệ các trường đại học kỹ thuật, 
ISSN 2354-1083, số 125, 2018, tr. 29-34. 
ONE METHOD OF IMPLEMENTING 
POHLIG-HELLMAN CRYPTOSYSTEM OVER 
POLYNOMIAL RINGS 
Abstract: Until now, the methods of encryption and 
decryption of a symmetric cryptosystem mainly used some 
operations, such as permutation, substitution or combine 
these two operations, or bit processing (in stream ciphers). 
This paper proposes a new method for implementing a 
symmetric cryptosystem but is based on discrete logarithm 
problem, in which encryption and decryption are 
performed by polynomial exponential function with 
modulo, in a manner like the Pohlig-Hellman 
cryptosystem. Along with that, this article also proposed an 
algorithm to implement that exponential function. 
Ngô Đức Thiện, Nhận học vị 
Tiến sỹ năm 2010. Hiện công tác 
tại Học viện Công nghệ Bưu chính 
Viễn thông. 
Lĩnh vực nghiên cứu: Lý thuyết 
thông tin và mã hóa, mật mã.