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

cộng các đa thức đều 
 ∗ n n
các nhóm nhân ℤ trong đó là số nguyên tố lớn. Tuy được tính theo modulo của x +1 . Tức là coi x +=10 
nhiên, nếu − 1 có thừa số là các số nguyên tố nhỏ, thì có hay xxn ==1 0 (phép cộng là phép cộng mod 2). Và để 
thể sử dụng thuật toán Pohlig-Hellman để giải bài toán thuận tiện, trong bài báo này tác giả sẽ không ghi 
logarit rời rạc rất hiệu quả. Vì thế người ta thường lựa chọn mod(x n +1 ) đối với các phép cộng, nhân và lũy thừa các 
 ∗
 là số nguyến tố lớn an toàn, để thành lập nhóm nhân ℤ đa thức. 
cho các hệ mật. 
 Trong các vành đa thức này tồn tại nhóm nhân cyclic 
 Một số nguyên tố an toàn là một số nguyên tố có dạng có cấp cực đại [5], [6]: 
 = 2푞 + 1, với 푞 là số nguyên tố lớn. Điều này đảm bảo 
 − 1 = 2푞 có thừa số nguyên tố lớn và không dễ dàng có G=={[ a ( x )],i i 1,2,3,..., k } () 
thể giải được bài toán logarit rời rạc bằng thuật toán Pohlig-
Hellman. 
B. Hệ mật Pohlig – Hellman Với: 
 Bài toán logarit rời rạc là bài toán khó, trong khi bài k=max ord a ( x ) = 2n- 1 - 1 () 
toán lũy thừa rời rạc lại không khó (có thể tính bằng thuật 
toán nhân và bình phương). Trường hợp này, cũng giống * Mối quan hệ giữa và GF() p 
như bài toán phân tích thừa số hay phép nhân các số 
nguyên, chúng đều có thể dùng để xây dựng cấu trúc cho n
một hệ mật mã. Xét một số nguyên tố p với p =-21. Khi đó vành 
 số modulo Z sẽ trở thành trường hữu hạn và trên 
 Hệ mật Pohlig-Hellman là một hệ mật sử dụng bài toán p
logarit rời rạc, có thể tóm tắt hệ mật này như sau [1]: trường này tồn tại một nhóm nhân cyclic [6]: 
 Ngô Đức Thiện 
 ZZ* = / {0} có cấp |¢ * |=p - 1 = 2n - 2 Trong phần này tác giả đề xuất một phương pháp xây 
 pp p dựng hệ mật khóa bí mật theo cách của Pohlig-Hellman. 
 và "a ÎZZ* ® $ a-- 1 Î *: aa 1 º 1mod p . Tuy nhiên, hàm mã hóa và giải mã đều là hàm lũy thừa các 
 pp đa thức theo modulo, bản rõ ( ) và bản mã ( ) đều biểu 
 n diễn bằng các đa thức. Mô hình truyền tin của hệ mật như 
 Xét a( x )Î+Z2 [ x ]/ ( x 1) với ax() có trọng số lẻ. mô tả trong hình 2. 
Khi đó $ax- 1() với W( a- 1 ( x )) lẻ thỏa mãn: 
 Thám mã (Oscar) 
 a() x a- 1 () xº+ 1mod( x n 1) () Bản rõ Bản mã Bản mã Bản rõ 
 (풙) (풙) (풙) (풙) 
 Bộ mã Kênh mở Bộ giải 
 Nguồn tin Nhận tin 
 Do vậy, có thể xây dựng phép tương ứng sau [6]: hóa (không an toàn) mã 
 (Alice) 풆, 풏 풅, 풏 (Bob) 
 in
 a( x )=å fi x ÎZ2 [ x ]/ ( x + 1) Kênh an toàn 
 iIÎ 
 i * Nguồn khóa 
 a af=Îå ip2 Z 
 iIÎ
 Hình 2. Mô hình truyền tin của hệ mật Pohlig-Hellman 
 n- 1
 và coi lũy đẳng e( x )== x i 0. xây dựng trên vành đa thức 
 0 å i= 0
 Khi đó ta có thể coi đây là một ánh xạ 1-1 giữa các phần Mô tả hệ mật như sau: 
 n + Tạo khóa: 
tử của Z2[xx ]/ (+ 1) 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 Bên Alice tạo khóa bí mật: e,, d n theo các bước sau: 
 n
với p =-21 ( – nguyên tố) được gọi là tựa đẳng cấu Bước 1: chọn số 푛 thỏa mãn: 
(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. • là vành đa thức có 2 lớp kề 
 cyclic. 
 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Ố. • p =−21n là một số nguyên tố. 
 Phép Vành đa thức Trường số 
 n −1
 tính GF() p Bước 2: Tính k =−21 và chọn số mũ mã hóa e thỏa 
 mãn điều kiện: 
 i
 a() x= å ai x ; a,() bÎ GF p gcd(ek , ) = 1 
 Phép iIÎÌZn
 c=+ a b Chú ý: gcd(ek , ) là ước chung lớn nhất của ek, . 
 cộng j
 b() x= å bj x º+(a b ) mod p
 jJÎÌZn Sở dĩ ta lấy ước chung lớn nhất của với k là do 
 chính là cấp cực đại của một phần tử trong vành đa thức 
 c()()() x=+ a x b x
 k như trong biểu thức (8). 
 = å cxk
 kKÎÌZ
 n Bước 3: tìm số mũ giải mã d thỏa mãn: 
 KIJIJ=()() È - Ç de.1 mod k () 
 Phép c()()() x= a x b x c= ab. Có nhiều cách để giải phương trình (10) tuy nhiên cách 
 nhân hiệu quả nhất là sử dụng thuật toán Euclid [2], [3]. 
 (º+a ()()mod( x b x x n 1)) (º ab . mod p )
 Khóa mã hóa của Alice là en, còn khóa giải mã của 
 Quan hệ tựa đồng cấu chỉ xảy ra đối với một số vành đa Bob là bộ số dn, (hoặc ngược lại). Alice gửi khóa giải mã 
thức có hai lớp kề cyclic đặc biệt, các vành đa thức này cho Bob qua kênh an toàn, hoặc sử dụng một thủ tục trao 
được liệt kê dưới đây [7]. đổi khóa an toàn nào đó. 
 Số nguyên tố Mersenne: p =-21n 
 + Mã hóa: 
 n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 52, 607, 
1279, 2203, 3217, 4253, 9689, 9941, 19937, , 74207281. Bên Alice cần mã hóa một bản tin rõ là đa thức 
 n
 Vành đa thức có hai lớp kề cyclic [5], [6]: m()[]/ x +Z2 x x 1 , Alice tính: 
 5, 11, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, c()() x= me x () 
131, , 523, 613, 1277, 2213, 3203, 3253, 4253, , 
9941, Sau đó Alice sẽ gửi cx()đến Bob qua kênh mở. 
IV. HỆ MẬT POHLIG-HELLMAN TRÊN VÀNH ĐA + Giải mã: 
 THỨC CÓ HAI LỚP KỀ CYCLIC 
 Bob nhận bản mã , khóa giải mã và tiến hành 
A. Mô tả hệ mật giải mã theo phương trình sau: 
MỘT PHƯƠNG PHÁP XÂY DỰNG HỆ MẬT POHLIG-HELLMAN TRÊN VÀNH ĐA THỨC 
 m( x )== cd ( x ) [ m e ( x )] d (aˆ )k = ( a01 k mod n , a k mod n ,
 () 01 () 
 ed
 ==m()() x m x a2121 kmod n ,..., an − ( n− ) k mod n )
 Ví dụ 2: Chứng minh: 
 + Tạo khóa: 6447448u lÇn
 k 2u 2 2 2...2
 Bước 1: Alice chọn n = 5 thỏa mãn x 5 +1 là vành đa [()]a x== [()] a x ((([()])) a x ) 
 5
thức có hai lớp kề cyclic và p =2 − 1 = 31 là số nguyên Mà : 
tố. 
 nn--11
 51− 2 2 2i mod n ( i+ j ) mod n Ta 
 Bước 2: Alice tính k =2 − 1 = 15 và chọn e =13 [a ( x )]=+åå ai x 2 a i a j x
 i==0 i , j 0;
thỏa mãn gcd(13 ,k )==gcd ( 13 , 15 ) 1 ij¹
 Bước 3: Tính d = 7 thỏa mãn 7. 13 1 mod 15 thấy với ij¹ : 
 + Mã hóa: 2a a x(i+ j )mod n=+ a a x ( i + j )mod n a a x ( i + j )mod n
 i j i j i j 
 Giả sử Alice cần gửi bản tin rõ mx() cho Bob: = 0
 m()(,,) x=1 + x34 + x  0 3 4 do phép cộng đa thức là cộng modulo 2. 
 n- 1
 Chú ý: (,,)034 là biểu diễn dạng số mũ của đa thức Vì thế: (i+ j ) mod n 
 20å aij a x =
 3 4 0 3 4 ij,= 0;
1+x + x = x + x + x . ij¹
 Alice tính: n- 1
 Vậy ta có: [a ( x )]2= a 2 x 2in mod 
 c()()() x= me x =1 + x3 + x 4 13 å i
 i= 0
 23
 =x + x + x  (,,)1 2 3 Tương tự như thế ta tính được: 
 Sau đó Alice gửi cx() qua kênh mở cho Bob. n- 1
 [()]a x4== ([()]) a x 2 2 ( a 2 x 2in mod ) 2
 å i
 + Giải mã: i= 0
 n- 1 
 4 4in mod
 Bob nhận nd==57, và và giải mã: = å axi
 i= 0
 m()()() x= cd x = x + x2 + x 3 7
 Tổng quát: 
 34
 =()(,,)1 +xx +  0 3 4 nn--11
 u u u u
 [a ( x )]2== a 2 x 2i mod n a x 2 i mod n
 ååii 
B. Thuật toán tính lũy thừa của đa thức theo modulo ii==00
 n
 x +1 u
 Chú ý: do a Î [0,1] nên aa2 = 
 Thông thường các hệ mật sử dụng bài toán logarit rời i ii
rạc đều phải thực hiện lũy thừa các số theo modulo trên Điều phải chứng minh 
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í dụ 3: xét n=5;()(,,) a x = 1 + x34 + x  aˆ = 0 3 4 
 Với hệ mật đề xuất như trong bài báo cũng phải thực 
 - Nếu k = 2 thì: 
hiện phép lũy thừa nhưng là lũy thừa đa thức theo modulo 
của . Dựa vào một tính chất đặc biệt của đa thức sau [a ( x )]2=11 + x 3. 2 mod 5 + x 4 . 2 mod 5 = + x + x 3 
đây, bài báo đưa ra thuật toán tính lũy thừa cho đa thức. 
 3
 n - Nếu k ==28 thì: 
 Xét đa thức a()[]/ x +Z2 x x 1 : 
 (aˆ )8 = (0 * 8 mod 5 , 3 * 8 mod 5 , 4 * 8 mod 5 )
 a( x )= a x0 + a x 1 + a x 2 + ... + a x n − 1 
 0 1 2n − 1 ==(,,)(,,)0 4 2 0 2 4
 với a [,]01 . k
 i Tức là để tính lũy thừa [ax ( )] ta chỉ việc nhân các số 
 mũ của từng đơn thức x trong ax() với rồi lấy modulo 
 Biểu diễn dạng số mũ (chỉ cho các ai = 1 ): 
 theo n như biểu thức (13), (14). 
 a() x aˆ = a0 ,, a 1 a 2 ,..., a ( n − 1 )
 ( 0 1 2n − 1 ) 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 như sau: 
 + Nếu một số k có dạng k = 2u khi đó: 
 n −1 Cho nguyên dương và có phân tích như sau: 
 k2u i. k mod n
 [a ( x )]==[] a ( x )  ai x () 
 i=0 ut
 kk==2 t 
 Dạng mũ: tt
 Ngô Đức Thiện 
 0 1 4 24
 Ví dụ: k =19 = 2 + 2 + 2 = 1 + 2 + 16 xét n=5;()(,,) a x = 1 + x + x  aˆ = 0 2 4 13 và 
 0 2 3
 uˆ =(0,1,4); k = [ kt ] = [1,2,16] k =13 = 1 + 4 + 8 = 2 + 2 + 2 , biểu diễn như sau: 
 k = [,,]1 4 8 13 . Ta có: rt==33; 
 Khi đó phép lũy thừa [a ( x )]kn mod( x +1 ) có thể tính 
như sau: Khi đó baˆ = ˆ13 được tính như sau: 
 k k 2ut [1] bˆ  ()0 
 a( x ) ==[ a ( x )]t [ a ( x )] 
 tt [2] For from 1 to 3 do: 
 Thuật toán tính lũy thừa của đa thức theo modulo 
 ▪ i =1: (với k = 1 ) 
x n +1 như sau: 1
 ˆ
 Thuật toán: Tính lũy thừa các đa thức theo modulo + AAAA= (,,)1 2 3 
 x n +1 
 = (0 * 1 mod 5 , 2 * 1 mod 5 , 4 * 1 mod 5 )
 n, aˆ == ( a , a ,..., a ) , k[] k , k ,..., k 
 Vào: 1 2r 1 r 1 2 t 1 t = (,,)0 2 4
 ˆ kn
 Ra: b=+( aˆ ) mod( x 1 ) +bˆ =()*(,,)(,,)0 0 2 4 0 2 4 
 [1] bˆ  ()0 , if k = 0 then return bˆ 
 ▪ i = 2: (với k2 = 4 ) 
 [2] For i from 1 to t do: 
 + 
 [2.1] for j from 1 to r do: 
 = (0 * 4 mod 5 , 2 * 4 mod 5 , 4 * 4 mod 5 )
 A a. k mod n 
 j j i = (,,)0 3 1
 ˆˆˆ
 [2.2]: b b. A + bˆ =(,,)*(,,)(,,)0 2 4 0 3 1 0 1 4 
 [3] Return ( ) 
 ▪ i = 3: (với k3 = 8 ) 
 Chú thích + 
 n
 + Số n đảm bảo Z2[]/xx+1 là vành đa thức có 2 
 n = (0 * 8 mod 5 , 2 * 8 mod 5 , 4 * 8 mod 5 )
 lớp kề cyclic và p =−21 là số nguyên tố. 
 = (,,)0 1 2
 n
 + Đa thức a()[]/ x +Z2 x x 1 ; dạng số mũ 
 + bˆ =(,,)*(,,)(,,)0 1 4 0 1 2 1 3 4 
 a( x )= aˆ ( a1 , a 2 ,..., arr ) 1 độ dài aˆ là rn . 
 n −1 bˆ = (,,)1 3 4
 + Số nguyên k , (0 k 2 − 1 ); được biểu diễn [3] Return 
 thành một vector bao gồm số thập phân Vậy kết quả có được là: 
 k= [] k, k ,..., k ; trong đó k = 2ut : 
 1 2tt 1 i (11+x2 + x 4 ) 13 mod( x 5 + ) = x + x 3 + x 4 
 k= kt  k = [] k t1 t Tiến hành mô phỏng thuật toán nêu trên bằng phần 
 t mềm Matlab (phiên bản R2016a), cấu hình máy tính: chip 
 th
 0 Intel Core i5 (7 gen), RAM 8GB, hệ điều hành Windows 
 + Mục [1] bˆ =()()0  b x = 1 = 2 ; 
 64 bits. 
 + Mục [2.1] tập các số Aj là biểu diễn dạng mũ của 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ả 
 đa thức Ax(); A( x )= A ( A12 , A ,..., Ar ) . Trong có được như trong bảng 3. 
 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 BẢNG 3: THỜI GIAN XỬ LÝ CỦA THUẬT TOÁN 
 Aˆ mà không cần phải dùng vòng lặp. Tức là ta có 
 Thời gian 
 TT Tham số mô phỏng 
 thể tính trực tiếp (Aj )= ( a j . k i mod n ): j12 , ,..., r xử lý (ms) 
 . 
 1 n = 5; k =13; aˆ = (,,)034 0, 050 
 + 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 2 n =19; k =103. 567 0, 164 
 theo modulo của x n +1 . aˆ = (,,,,,,,,)0 2 5 8 10 11 13 15 17 
 + Kết quả dạng mũ: bˆ =+( aˆ )kn mod( x 1 ) 
 Ví dụ 4: 
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 0, 236 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ệ 
 aˆ = (,,,,,,,1 3 7 12 19 21 29
 BCVT, 2013. 
 32,,,,,) 38 45 50 55 59 [2] Frederik Vercauteren, Discrete Logarithms in Cryp-
 tography, ESAT/COSIC - K.U. Leuven ECRYPT Summer 
 4 n =107; k =2... 341 235 671 0, 436 School 2008. 
 aˆ = (,,,,,,,1 9 17 26 38 47 54 [3] Jean-Yves Chouinard, ELG 5373, “Secure commu-
 62,,,,,) 74 82 91 98 105 nications and data encryption,” School of Information 
 Technology and Engineering, University of Ottawa, April 
 5 n = 4253; k =139... 749 574 567 4, 300 2002. 
 [4] A. Menezes, P. van Oorschot, and S. Vanstone, "Handbook 
 aˆ = (,,,,,,,,1 56 98 147 209 300 478 698 of Applied Cryptography", CRC Press, 1996. 
 1002,,,,) 1348 2034 3045 4002 [5] Nguyen Trung Hieu, Ngo Duc Thien, Tran Duc Su, "On 
 Constructing Cyclic Multiplicative Groups with Maximum 
 6 n =9941; 19, 300 Order over Polynomial Rings with Two Cyclotomic 
 k =13..... 974 957 456 787 957 Cosets", Jounal of scientific research and military 
 technology, Vol. 17, February - 2012, pp. 133-140, ISSN 
 aˆ = (,,,,,,0 100 456 989 1456 2002
 1859-1043. 
 2560,,,,, 3001 3982 4679 5398 
 [6] Lê Danh Cường, Nguyễn Bình, “Cấu trúc tựa đẳng cấu 
 6003,,,,,) 7623 7982 8567 9234 9657 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, 
 Nhận xét: Với các giá trị n nhỏ thì tốc độ tính toán là ISSN 2354-1083, số 121, 2017, tr. 54-57. 
nhanh. Với trường hợp n =4253 tương đương với việc [7] Nguyễn Trung Hiếu, Ngô Đức Thiện, "Hệ mật Omura-
tính toán với các con số 4252 bit mà thời gian tính toán của Massey xây dựng trên vành đa thức có hai lớp kề cyclic", 
một phép lũy thừa là 4,3ms có thể nói là hoàn toàn chấp Tạp chí khoa học và Công nghệ các trường đại học kỹ thuật, 
nhận được. Cho đến hiện nay để đảm bảo tính an toàn, các ISSN 2354-1083, số 125, 2018, tr. 29-34. 
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 ONE METHOD OF IMPLEMENTING 
máy tính laptop như cấu hình ở trên là 19, 3ms . Cho đến 
 POHLIG-HELLMAN CRYPTOSYSTEM OVER 
nay thì chưa cần thiết dùng đến giá trị 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 POLYNOMIAL RINGS 
đó 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 Abstract: Until now, the methods of encryption and 
thời gian tính toán và hoàn toàn có thể áp dụng được hệ mật decryption of a symmetric cryptosystem mainly used some 
này. operations, such as permutation, substitution or combine 
 these two operations, or bit processing (in stream ciphers). 
 V. KẾT LUẬN This paper proposes a new method for implementing a 
 Bài báo đề xuất phương pháp thực hiện một hệ mật khóa symmetric cryptosystem but is based on discrete logarithm 
bí mật theo cách của hệ mật Pohlig-Hellman. Trong đó, bản problem, in which encryption and decryption are 
rõ và bản mã được mô tả bằng các đa thức trên vành đa performed by polynomial exponential function with 
thức, thay vì được mô tả bằng các con số trên trường số. Sở modulo, in a manner like the Pohlig-Hellman 
dĩ có thể thực hiện được điều này là nhờ cấu trúc tựa đẳng cryptosystem. Along with that, this article also proposed an 
cấu của vành đa thức có hai lớp kề cyclic với trường số. algorithm to implement that exponential function. 
 Độ 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, Ngô Đức Thiện, Nhận học vị 
cho đến nay với giá trị số nguyên tố lớn thì bài toán logarit Tiến sỹ năm 2010. Hiện công tác 
rời rạc vẫn là bài toán khó. tại Học viện Công nghệ Bưu chính 
 Viễn thông. 
 Để hệ mật có tính khả thi, bài báo cũng đề xuất thuật Lĩnh vực nghiên cứu: Lý thuyết 
toán thực hiện hàm lũy thừa cho các đa thức theo modulo. thông tin và mã hóa, mật mã. 
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ế.