Phát triển thuật toán của danied shank để giải bài toán logarit rời rạc trên vành Zn - Lê Văn Tuấn

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 48, 04 - 2017 129 PHÁT TRIỂN THUẬT TOÁN CỦA DANIED SHANK ĐỂ GIẢI BÀI TOÁN LOGARIT RỜI RẠC TRÊN VÀNH Zn Lê Văn Tuấn1*, Bùi Thế Truyền2 Tóm tắt: Bài viết này giới thiệu phương pháp tính logarit rời rạc trên trường hữu hạn Zp của Danied Shanks và của Polig-Hellman. Dựa trên phương pháp của Danied Shanks, chúng tôi phát triển nó để giải bài toán logarit rời rạc trên vành Zn. Kết quả nghiên cứu được ứng dụng vào phân tích độ an toàn của lược đồ chữ ký số trên bài toán logarit rời rạc trong vành Zn Từ khoá: Vành hữu hạn, Trường hữu hạn, Bài toán logarit rời rạc. 1. MỞ ĐẦU Tương tự bài toán phân tích số nguyên lớn ra thừa số, bài toán logarit rời rạc thuộc lớp bài toán khó giải. Hiện nay, một lớp hệ mật khóa công khai và biến thể của nó được xây dựng dựa trên độ khó của bài toán này. Tuy nhiên, bài toán logarit rời rạc không phải khó giải trong mọi trường hợp. Chính vì thế, các nhà khoa học đã lợi dụng những trường hợp không khó của bài toán để xây dựng các thuật toán giải bài toán logarit rời rạc. Một thực tế cho thấy, đa số các thuật toán giải bài toán logarit rời rạc hiện nay, chỉ áp dụng được trên trường hữu hạn Zp. Trong khi đó, một số hệ mã khóa công khai và các biến thể của nó được xây dựng trên cấu trúc vành Zn. Với mục tiêu nhằm loại bỏ những mầm mống không an toàn cho các hệ mật khoá công khai và các hệ chữ ký số dựa trên độ khó của bài toán logarit rời rạc trên vành Zn, trên cơ sở tìm hiểu những thuật toán giải bài toán logarit rời rạc đã được công bố trên thế giới[2][3][5] và một số công trình liên quan đến bài toán logarit rời rạc trên vành Zn,[1][4][8], chúng tôi phát triển thuật toán Baby step Giant Step của Danied Shanks để giải được bài toán logarit rời rạc trên vành Zn. Giả sử nhóm cyclic G= là nhóm con của nhóm nhân và cỡ bậc của g là m bit. Khi đó bậc của g thuộc đoạn [2m-1,2 m-1] và khoảng tìm giá trị logarit rời rạc thuộc đoạn [0,2m-1]. Trong bài viết này, chúng tôi phát triển thuật toán Baby-step Giant-step của Danied Shanks để tìm logarit rời rạc trong nửa đoạn [0,2m-1) trên vành Zn. Việc tìm logarit rời rạc thuộc đoạn [2 m-1,2m-1] nằm ngoài phạm vi nghiên cứu trong bài báo này. Kết quả nghiên cứu là cơ sở để xây dựng tiêu chuẩn tham số an toàn [9] cho hệ chữ ký số, hoặc các biến thể của nó dựa vào độ khó của bài toán logarit rời rạc trên vành Zn. 2. CƠ SỞ TOÁN HỌC 2.1. Một số ký hiệu, định nghĩa và tính chất Bitlength(M): Hàm trả về số bít của số nhị phân biểu diễn M. #G: Chỉ bậc của nhóm G. OrdG(g): Chỉ bậc của phần tử g thuộc tập G. Định nghĩa 2.1: Cho G là một nhóm nhân với phần tử đơn vị là 1 và g ∈ G. Nếu tồn tại số tự nhiên d sao cho = 1 (2.1) thì g được gọi là “có cấp hữu hạn” và giá trị d nhỏ nhất thỏa mãn đẳng thức (2.1) được gọi là “cấp của g trong G” và ký hiệu là ord(g) mod G hay .■ Công nghệ thông tin & Cơ sở toán học cho tin học L.V. Tuấn, B.T. Truyền, “Phát triển thuật toán của Danied Shank rời rạc trên vành Zn.” 130 Lưu ý. Nếu G là nhóm hữu hạn thì mọi phần tử trong G đều có cấp hữu hạn và luôn là ước bậc của nhóm G, ký hiệu |#G, ngoài ra, nếu số tự nhiên d thỏa mãn (2.1) thì cũng là ước của d. Định lí 2.1: Cho G= Zn *(n= pxq), [2m-1,2m-1], 1k1,k2 2 m-1, thoả mãn: gk1=b mod n (2.2) và gk2=b mod n (2.3) thì k1=k2. Chứng minh: Giả sử k1 k2 không giảm tổng quát, giả sử k1>k2, từ (2.2) và (2.3) ta có = 1 mod n, khi đó (k1-k2), nghĩa là k1-k2 2 m-1, điều này mẫu thuẫn với giả thiết 1k1,k2 2 m-1■ Định lý 2.2 [11]: Giả sử Γ...m1m là các số nguyên dương nguyên tố cùng nhau từng đôi một và cho Γ...a1a là các số nguyên. Khi đó, hệ r đồng dư thức )i(modmiax  (1<=i<=r) sẽ có một nghiệm duy nhất theo modulo M= Γ1 m...m  được cho theo công thức: x= iii Γ 1i yMa  mod M, trong đó và yi= M -1 mod mi với 1<=i<=r. Bổ đề 2.1. Cho nhóm cyclic G= có bậc M, M= RS và k=loggx mod M ta có: k= S g xlog S mod R (2.4) k= R g xlog R mod S (2.5) Bổ đề 2.2. Cho G= có bậc M=Rc, i=loggx=i0+i1R+...+ic-1R c-1 ta có: i0= 1 c-1R log ( ) cR g x  . (2.6) it= ))xg((log 1tc1t 1t0 RRi...i g   1-cR (t=1,...,c-1). (2.7) 2.2. Logarit rời rạc và ứng dụng Định nghĩa 2.2: Cho G= bậc M, khi đó G,  duy nhất ZM sao cho =g. Giá trị  được gọi là logarit rời rạc [10]cơ số g của  và ký hiệu logg. Cho trước phần tử g G, khi đó, với mọi G= việc tìm logg được gọi là bài toán logarit rời rạc trên G. Định nghĩa 2.3: Cho p là số nguyên tố lẻ, G==Z*p , g là phần tử nguyên thuỷ của Z * p và  Z*p. tồn tại duy nhất ,0 p-1 sao cho g   mod p. Giá trị  được gọi là logarit rời rạc [10] cơ số g của , ký hiệu là logg. Cho trước phần tử g  Z * p, khi đó, với mọi  Z*p, tìm logg gọi là bài toán logarit rời rạc[10] trên trường Zp. Tính chất 2.1: log(1.2. . . .k )log1+log 2+ . . + log k(mod p-1). (2.8) Tính chất 2.2: log .log(mod p-1) (2.9) Ứng dụng bài toán logarit rời rạc: Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 48, 04 - 2017 131 Một lớp các hệ mã khoá công khai và biến thể quan trọng mà độ an toàn của nó dựa trên tính khó giải của bài toán logarit rời rạc, chẳng hạn như hệ mã khóa công khai của Elgamal, giao thức trao đổi khóa Diffie-Hellman v.v... Trong phần này, bài báo sẽ trình bày ứng dụng bài toán logarit rời rạc trong xây dựng hệ mật khóa công khai Elgamal và hệ chữ ký số Elgamal. Giả sử một hệ thống truyền tin sử dụng hệ mã khóa công khai Elgamal trên trường Zp để bảo mật thông tin. Khóa của hệ mã xây dựng theo các bước như sau: Thuật toán 2.1: + Bước 1: Chọn số nguyên tố p đủ lớn sao cho bài toán logarith trong pZ là khó giải. + Bước 2: Chọn *pZα  là phần tử nguyên thủy. + Bước 3: Chọn x là số ngẫu nhiên sao cho 1<x<p. + Bước 4: Tính giá trị y thỏa mãn công thức:  modxy p Khóa bí mật là x, còn khóa công khai là bộ gồm 3 số (y, p, ). Để mã hóa bản rõ R bên gửi sử dụng khóa công khai của bên nhận là bộ ba số (y,p, ). Tiếp theo chọn số ngẫu nhiên k và tính  pmodkαC'  ( 2.10)  pRmodkyC"  ( 2.11) Sau đó gửi bản mã gồm  CC , đến bên nhận. Một ứng dụng khác của bài toán logarit rời rạc là xây dựng lược đồ chữ ký số Elgamal. Quá trình tạo khóa giống như qúa trình tạo khóa của hệ mật Elgamal, tức là chọn số nguyên tố p đủ lớn để bài toán logarith rời rạc trên Zp là khó giải, và chọn * pZα  là phần tử nguyên thủy, chọn 1px A  là số nguyên làm khóa bí mật và tính khóa công khai yA= (modp)α A x . Để ký lên bức điện m * pZ bên ký tạo ra số ngẫu nhiên k thỏa mãn 1pk  và UCLN(k, p-1)=1 và hình thành nên chữ ký là cặp (r,s), ở đây r và s tính như sau: Thuật toán 2.2: .1)r)(modpx(mks (modp),αr A 1 k    ( 2.12) (2.13) Xác nhận chữ ký (r,s) trên bức điện m, bên nhận thực hiện như sau: Thuật toán 2.3: Verify( ,yA,p)(m,(r,s))=TRUE, nếu như r < p và p) (modαry msr A  ( 2.14) Verify( ,yA,p)(m,(r,s))=FALSE, nếu r>p hoặc p) (modαry msr A  ( 2.15) 3. GIẢI BÀI TOÁN LOGARIT RỜI RẠC Việc tấn công các hệ mã khóa công khai hoặc biến thể của nó dựa trên độ khó của bài toán logarit rời rạc đều phải giải bài toán này. Chẳng hạn kẻ tấn công muốn khám phá bản mã (C”,C’) được tạo ra trong thuật toán 2.1, để tìm ra bản rõ R, đầu tiên cần phải xác định khóa bí mật x từ phương trình . Từ giá trị x tìm được, với biểu hình mã (C”,C’) ta dễ dàng khôi phục bản rõ R theo công thức sau đây: Công nghệ thông tin & Cơ sở toán học cho tin học L.V. Tuấn, B.T. Truyền, “Phát triển thuật toán của Danied Shank rời rạc trên vành Zn.” 132 Tính giá trị:    ' x xk kxZ C     (2.16) Tính gía trị nghịch đảo của Z:    1 modkxZ p  (2.17) Tính R = C”. Z-1 (modul p) (2.18) Một trong các kiểu tấn công hệ chữ ký số là giả mạo chữ ký được tạo ra trong thuật toán 2.2, muốn vậy kẻ tấn công phải có khóa bí mật xA, tức là phải giải phương trình yA= (modp)α A x , đây là bài toán khó giải nếu tham số của hệ chữ ký được xây dựng an toàn[9]. Trên thực tế, bài toán tìm logarit rời rạc không phải khó giải trong mọi trường hợp, chẳng hạn như bậc của trường hữu hạn Zp không đủ lớn, hoặc p-1 có các ước số nguyên tố nhỏ thì bài toán logarit rời rạc trên đó sẽ không khó. Dựa vào những trường hợp không khó của bài toán mà các nhà khoa học đã phát minh ra một số thuật toán để giải nó. Trong phần này, bài báo sẽ trình bày một số thuật toán giải bài toán logarit rời rạc trên trường Zp. 3.1. Thuật toán Baby-step Giant-step của Danied Shanks [2][3][6] Nếu số nguyên tố p không đủ lớn, một thuật toán có độ phức tạp về thời gian và không gian tính toán là O( ) có thể tính khóa bí mật x. Dưới đây giới thiệu một thuật toán Baby-step Giant-step của Danied Shanks. Giả sử cho G= = Zp * là một nhóm cyclic bậc p-1 sinh bởi g và b G. Bài toán đặt ra là tìm k sao cho gk = b. Thuật toán Baby-step Giant-step của Danied Shanks được miêu tả như sau: Thuật toán 3.1: Input: Nhóm cyclic G= = Zp * có bậc p-1, b G. Output: k= loggb. Bước 1: q ← // q nhận giá trị là cận trên của 1p  Bước 2: Với mỗi i, 0 ≤ i < q tính (i,b.gi), lưu trữ trong danh sách S và sắp xếp (Baby step) Bước 3: Với mỗi j,0 ≤ j < q tính (q.j,gq.j), lưu trữ trong danh sách T và sắp xếp (Giant step) Bước 4: Tìm trong danh sách S giá trị b.gi bằng với giá trị gq.j trong T, khi đó k= qj-i. Độ phức tạp về thời gian và không gian nhớ là O( 1p  ), so với phương pháp vét cạn có độ phức tạp về thời gian và không gian của bộ nhớ là O( ). Để minh hoạ cho thuật toán Baby-step Giant-step của Danied Shanks giải bài toán logarit rời rạc trên trường Zp, xét một ví dụ sau: Giả sử G= Z19 *=. Giả sử cần giải bài toán logarit rời rạc k= log26. Theo thuật toán 3.1, việc tìm k được thực hiện như sau: Bước 1: q= = 5. Bước 2: Với mỗi i, 0 ≤ i < 5 tính (i,6.2i mod 19 ), ta có S={(0, 6), (1, 12) (2, 5), (3, 10), (4,1)}, sau khi sắp xếp cho dãy S ={(4,1), (5,2), (2, 5), (0, 6), (3,10), (1, 12)}. Bước 3: Với mỗi j, 0 ≤ j 5 tính (5.j,25j mod 19 ), ta có T= {(0,1), (5,13), (10,17), (15,12), (20,4)}, sau khi sắp xếp cho dãy T ={(0,1), (20,4), (15,12), (5,13), (10,17)} Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 48, 04 - 2017 133 Bước 4: So sánh giữa S và T cho thấy giá trị 12 là giá trị chung cho hai dãy S và T, khi đó k= q.j-i=15-1=14. 3.2. Thuật toán Polig-Hellman[5][6] Trong trường hợp chỉ có các thừa số nguyên tố bé, bài toán logarit rời rạc sẽ giải được bởi thuật toán của Polig-Hellman. Thuật toán mô tả như sau: Thuật toán 3.2: Input: Nhóm cyclic G= = Zp * có bậc p-1, b G. Output: k= mod p-1 Bước 1. Phân tích ra thừa số nguyên tố của p-1 (Ri là các số nguyên tố khác nhau). Bước 2. Đặt gi= và bi= ni= và tính ki là logarit rời rạc cơ số i = của bi Bước 3. Áp dụng công thức 2.4 và công thức 2.5, tính k từ các phương trình sau: k= mod R1 c1 k= mod R2 c2 .... k= mod Rh ch Áp dụng định lý 2.2 xác định được k= mod p-1. Bước 4. Đưa ra giá trị của x; Để minh hoạ thuật toán Pohlig-Hellman, xét ví dụ sau: Giả sử p=31. Ta có 31- 1=30= 5.3.2. Giả sử cần tìm x, x=y mod 31, với =3, y=26, ta có phương trình ẩn x, 3x=26 mod 31. Áp dụng thuật toán 3.2 ta có: n1 = = 6; 1= = mod 31=16; y1= =26 6 mod 31= 1 n2 = = 10; 2= = mod 31= 25; y2= =26 10 mod 31= 5 n3 = = 15; 3= = mod 31=30; y3= =26 15 mod 31= 30 Tính x là logarit rời rạc của y, ký hiệu là x= ta tính logarit rời rạc x từ hệ phương trình sau: x= = mod 5 (*) x= = mod 3(**) x= = mod 2(***) Từ (*)(**)(***) ta có hệ phương trình: Do các số 5, 3, 2 là nguyên tố cùng nhau, áp dụng định lý Trung quốc về đồng dư, tìm ra x = 5 mod 5.3.2. Tương đương với phương trình x = 5 mod 30 là giá trị cần tìm. Kiểm tra lại dễ thấy 35 = 26 mod 31. 4. PHÁT TRIỂN THUẬT TOÁN DANIED SHANKS GIẢI BÀI TOÁN LOGARIT RỜI RẠC TRÊN VÀNH Zn[7] Thuật toán 3.1 và thuật toán 3.2 áp dụng giải bài toán logarit rời rạc trên trường Zp, trong đó, thuật toán 3.2 phụ thuộc hoàn toàn vào bậc của nhóm cyclic G= Zp * (p nguyên tố), chính vì thế, không thể áp dụng để giải bài toán logarit rời rạc trên vành Zn. Thuật toán 3.1 có thể phát triển để giải bài toán logarit rời rạc trong một đoạn nào đó trên vành Zn, mà không cần dựa trực tiếp vào bậc của nhóm nhân cyclic G= Zn *. Giả sử nhóm cyclic G= là nhóm con của nhóm nhân Công nghệ thông tin & Cơ sở toán học cho tin học L.V. Tuấn, B.T. Truyền, “Phát triển thuật toán của Danied Shank rời rạc trên vành Zn.” 134 và cỡ bậc của G là m bit, khi đó thuộc đoạn [2m-1,2 m-1] và giá trị logarit rời rạc loggb sẽ thuộc đoạn [0,2 m-1]. Trong phần này, chúng tôi phát triển thuật toán Baby-step Giant-step của Danied Shanks để tìm logarit rời rạc trong nửa đoạn [0,2m-1) trên vành Zn. 4.1. Thuật toán Input: Vành Zn và nhóm cyclic G= Zn *, bậc của g, ký hiệu là là một số m bit (m=bitlength( )), b G Output: k= loggb. Bước 1: q ← // q nhận giá trị là cận trên của Bước 2: Với mỗi i, 0 ≤ i < q tính (i,b.gi mod n ), lưu trữ trong danh sách S và sắp xếp (Baby step) Bước 3: Với mỗi j,0 ≤ j < q tính (q.j, gq.j mod n ), lưu trữ trong danh sách T và sắp xếp (Giant step) Bước 4: Duyệt danh sách S và danh sách T, và kiểm tra hai điều kiện: - Giá trị b.gi trong S bằng với giá trị gq.j trong T và qj-i<2m-1, thì giá trị logarit rời rạc cần tìm, k= qj-i. - Nếu không thoả mãn một trong hai điều kiện trên thì giá trị logarit rời rạc không nằm trong khoảng tìm kiếm của thuật toán. 4.2. Tính đúng đắn của thuật toán Do cấp của nhóm G= là m bít, nên logarit rời rạc cơ số g của b là nghiệm k từ phương trình gk = b mod n sẽ thuộc khoảng [0,2m-1]. Danh sách tạo ra trong bước nhỏ (Baby step) chứa đựng các cặp (i,bgi), 0 ≤ i < q), danh sách tạo ra trong bước lớn chứa đựng các cặp (jq, gqj), 1≤ j ≤ q). Quá trình tạo ra danh sách bước lớn mà phát hiện giá trị gqj bằng gi trong danh sách được tạo ra ở bước nhỏ, tức là ta có phương trình bgi= gqj mod n. Do g Zn *, nên (g, n)=1, khi đó, tồn tại g-1 và từ kết quả gqj= bgi mod n ta có g-igjq=b mod n hay có g-i+jq=b mod n. Nếu giá trị jq- i< 2m-1, theo định lý 2.1 thì k là giá trị duy nhất thuộc khoảng [0, 2m-1) thoả mãn g-i+jq=b mod n nên giá trị logarit rời rạc cần tìm là k= jq- i. Để minh họa cho thuật toán tìm logarit rời rạc trên vành Zn, xét vành Z77 và nhóm G= Z77 * và Z77 * có bậc cỡ 5 bít. Giả sử cần giải bài toán logarit rời rạc k= log39. Việc tìm k được thực hiện như sau: Bước 1: q= = 6. Bước 2: Với mỗi i, 0 ≤ i <6 tính (i,9.3i mod 77 ), ta có S={(0, 9), (1, 27) (2, 4) (3, 12), (4, 36), (5, 31)}, sau khi sắp xếp cho dãy S ={(2, 4), (0, 9), (3, 12) (1, 27), (5, 31), (4, 36)}. Bước 3: Với mỗi j, 0≤ j 6 tính (6.j, 36j mod 77 ), ta có T={(0,1), (6,36), (12,64), (18,71), (24,15), (30,1)}, sau khi sắp xếp cho sãy T ={(0,1), (30,1), (24, 15), (6,36), (12,64), (18,71), }. Bước 4: So sánh giữa S và T cho thấy giá trị 36 thuộc cả hai dãy S và T, khi đó, k= q.j-i=5-3=2 .[0,24). 4.3. Độ phức tạp của thuật toán Nếu không tính đến thừa số của logarit thì thuật toán 4.1 có độ phức tạp tính toán về thời gian là O( ) phép tính số học và yêu cầu về không gian của bộ nhớ là O( ), so với phương pháp vét cạn có độ phức tạp về thời gian và không gian của Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 48, 04 - 2017 135 bộ nhớ đã giảm đi một nửa. Chính vì thế, thuật toán này chỉ áp dụng được với bài toán tìm logarit rời rạc trên nhóm G có bậc đủ nhỏ. Dựa trên thuật toán, 4.1, chúng tôi đã viết chương trình chạy thủ nghiệm trên ngôn ngữ lập trình Visual studio 2008, chạy trên máy tính sony vio core i3. Màn hình giao diện chương trình trong hình 4.1. Hình 4.1. Giao diện chương trình chạy thử nghiệm. Bảng 4.1 đã thống kê kết quả chạy thử nghiệm tìm logarit rời rạc trên một số vành Zn. Kết quả chạy thử nghiệm luôn cho kết quả và có độ chính xác tuyệt đối. Bảng 4.1. Kết quả thử nghiệm tìm logarit rời rạc trên vành Zn. STT Vành Zn Cơ số(g) Giá trị tìm logarit rời rạc (b) Kết quả k 1 Z1739 2 427 25 2 Z2173 5 829 185 3 Z2479 2 2048 11 4 Z3713 3 3354 10 5 Z7387 3 6118 13 6 Z8989 3 6510 23 7 Z8453 5 3797 4096 8 Z10807 8 719 57 9 Z10807 10 4252 97 10 Z13081 97 8344 2091 11 Z24047 139 14776 6095 5. KẾT LUẬN Trên cơ sở nghiên cứu hai thuật toán của Poling Hellman và thuật toán của Danied Shanks để giải bài toán logarit rời rạc trên trường Zp, tác giả đã phát triển thuật toán Baby-step Giant-step của Danied Shanks để tìm logarit trên vành Zn, trong điều kiện biết cỡ bậc của nhóm nhân cyclic là m bít. Thuật toán luôn cho kết quả chính xác nếu giá trị logarit cần tìm thuộc nửa đoạn [0,2m-1). Để tìm các giá trị logarit rời rạc thuộc đoạn [2m-1,2m-1], cần xây dựng một thuật toán riêng. Thuật toán được viết trên ngôn ngữ lập trình visual studio 2008 và được áp dụng để tính toán logarit rời rạc trên một số vành Zn trong bảng 4.1. Kết quả thử nghiệm cho thấy chương trình chạy cho kết quả chính xác, điều đó chứng tỏ thuật toán đảm bảo Công nghệ thông tin & Cơ sở toán học cho tin học L.V. Tuấn, B.T. Truyền, “Phát triển thuật toán của Danied Shank rời rạc trên vành Zn.” 136 tính đúng đắn, tính dừng. Kết quả nghiên cứu làm cơ sở để xây dựng hệ tiêu chuẩn về tham số cho hệ chữ ký số mới trên vành Zn. TÀI LIỆU THAM KHẢO [1]. Nguyễn xuân Quỳnh, Nguyễn Hồng Quang, “Báo cáo khoa học về độ mật chống lại đối phương tích cực của giao thức thiết lập khóa dựa theo ID”, Hội nghị toàn quốc lần thứ V về tự động hóa 24-26/10/2002, Hà nội. [2] Daniel Shank, “Class number, a theory of factorization, and genera”, Symposium Pure Mathematics, 1972. [3] Douglas R. Stinson, “Cyptography theory and practice”, 2003 [4] OKAMOTO E, (1987), “Key distribution systems based on identification information”. Proc. Of Crypto. [5].[Pohlig&Hellman] Stephen C. Pohlig and Martin E. Hellman, “An improved algoritm for computing logarithms over GF(p) and its cryptographic significance”, IEEE Transaction Theory IT-24 (1979), no. 1, 106-110. [6] Song Y. Yan, “Number Theory for Computing”, page 244-267, spring - 2001 [7] Steven D Galbraith, John M, Pollard, and Ramindern S. Ruprai. “Computing discrete logarithms in an interval” [8] C Meshram. “Discrete Logarithm and Integer Factorization using IBE”. ISSN: 2089-3191, Bulletin of Electrical Engineering and Informatics Vol. 4, No. 2, June 2015, pp. 160~168 [9]. FIPS PUB 186-3,“Digital Sinature Standrd (DSS)”, 2009. [10]. https://vi.wikipedia.org/wiki/Logarit rời rạc [11]. https://vi.wikipedia.org/wiki/đinh lý Trung quốc về đồng dư. ABSTRACT DEVELOPING SHANK’S ALGORITHM FOR SOLVING THE DISCRETE LOGARITHM PROBLEM IN RING Zn In this submission, some computing methods for discrete logarithm problem of Danied Shanks and Polig-Hellman in finite field Zp have been introduced. Based on Danied Shanks's algorithm, we developed it to solve the discrete logarithm problem on the Zn ring. The results are able to apply on problem for analysing security of digital signature schemes, which are on basis of discrete logarithm problem in ring Zn. Keywords: Finite ring, Finite field, Discrete Logarithm Problem. Nhận bài ngày 27 tháng 02 năm 2017 Hoàn thiện ngày 27 tháng 03 năm 2017 Chấp nhận đăng ngày 05 tháng 4 năm 2017 Địa chỉ: 1 Học viện Khoa học quân sự; 2 Học viện Kỹ thuật quân sự. * Email: levantuan71@yahoo.com