Phát triển một dạng lược đồ chữ ký số mới dựa trên bài toán RSA

 thích: Chứng minh: 
 - p, q: là các số nguyên tố. Thật vậy, ta có: 
 - Việc tính: theo (3a) hay: a b c a a.b a.c
 S modn = (k x modn) modn = k x modn 
 −t b c
 y = x modn theo (3b) là tùy thuộc vào từng = (k a modn) (xa modn) modn = Rb yc modn
 lược đồ cụ thể. Trường hợp nếu y tính theo (3b) Mệnh đề đã được chứng minh. 
 thì x cần phải thỏa mãn điều kiện: gcd(x,n) =1 Tính đúng đắn của phương pháp hình thành và kiểm tra 
2) Phương pháp hình thành chữ ký chữ ký theo (4), (6), (8) và (9) có thể chứng minh như sau: 
 input: n, t, x, M – thông điệp dữ liệu cần ký. 
 Đặt: t = a, f2 (M, R) = b , f3(M,R) = c ta có: 
 output: (R,S)/(E,S) – chữ ký của U lên M. 
 u = S t modn = S a modn , với: 
 Các bước thực hiện: 
 Và: 
 1. Chọn ngẫu nhiên giá trị k trong khoảng (1,n), tính 
 f2 (M,R) f3(M,R) b c
 thành phần thứ nhất của chữ ký theo: v = R y modn = R y modn, với: 
 R = k t modn (4) và: 
 hoặc: Theo Mệnh đề 1 suy ra điều cần chứng minh: u = v. 
 f2 (M,R)
 E = f1(M, R modn) (5) Mệnh đề 2: 
 2. Tính thành phần thứ 2 của chữ ký theo: Cho p, q là 2 số nguyên tố, , 
 f (M ,R) f (M ,R)
 S = k 2 x 3 modn (6) , , , 
 hoặc: . Nếu: −a , , 
 f (M ,R) f (M ,E) gcd(x,n) =1 y = x modn
 S = k 2 x 3 modn (7) 
 b a c
 Chú thích: thì: R  S y modn . 
 Chứng minh: 
 - f1 (.) : hàm của M và R có giá trị trong khoảng 
 (1,n). Thật vậy, ta có: 
 a c
 S a y c modn = k b x c modn x −a modn modn
 - f2 (.),f3 (.): các hàm của M và R hoặc E có giá trị ( ) ( )
 trong khoảng (1, ). = k a.b x a.c x −a.c modn 
 b
 - (R,S): chữ ký được tạo theo (4) và (6). = k a.b modn = (k a modn) modn = R b modn
 - (E,S): chữ ký được tạo theo (5) và (7). 
 Mệnh đề đã được chứng minh. 
3) Phương pháp kiểm tra chữ ký 
 Tính đúng đắn của phương pháp hình thành và kiểm tra 
 a. Trường hợp chữ ký là (R,S) 
 chữ ký theo (5), (7), (10) và (11) cũng được chứng minh 
 input: n, t, y, (R,S), M. 
 tương tự như sau: 
 output: (R,S) = true hoặc (R,S) = false. 
 Đặt: , , ta có: 
 Các bước thực hiện: f3(M,E) = c
 t f (M,E) a c
 1. Tính giá trị u theo: u = S y 3 modn = S y modn, với: 
 t
 u = S modn (8) và: . 
 2. Tính giá trị v theo: 
 Theo Mệnh đề 2 suy ra: 
 f (M,R) f (M,R)
 v = R 2 y 3 modn (9) 
 u = Rb modn , với: . 
 3. Nếu (u = v) thì (R,S) = true, ngược lại thì: Nên: 
 (R,S) = false. b f (M,R)
 v = f (M,u) = f (M, R modn)= f (M, R 2 modn) (12) 
 b. Trường hợp chữ ký là (E,S) 1 1 1
 Từ (5) và (12) ta có điều cần chứng minh: v = E. 
 1. Tính giá trị u theo: 
 t f (M,E) B. Lược đồ chữ ký LDH.01 
 u = S y 3 modn (10) 
 Lược đồ thứ nhất - ký hiệu LDH.01, được hình thành từ 
 2. Tính giá trị v theo: 
 lược đồ dạng tổng quát với lựa chọn: f2(M,R) = H(M), 
 v = f (M ,u) (11) 
 1 f3(M,R) = R. Ở đây H(.) là hàm băm và H(M) là giá trị đại 
 3. Nếu (v = E) thì (E,S) = true, ngược lại thì: diện (giá trị băm) của bản tin cần ký (M). 
 (E,S) = false. 
 Chú thích: 
 - (R,S)/(E,S) = true: chữ ký hợp lệ, bản tin M được 
 công nhận về nguồn gốc và tính toàn vẹn. 
 Pham Van Hiep, Luu Hong Dung 
 1. Thuật toán sinh tham số và khóa 1. Thuật toán sinh tham số và khóa 
 Thuật toán 1.1: Thuật toán 1.4: 
 Input: lp, lq. Input: lp, lq. 
 Output: n, t, x, y, H(.). Output: n, t, x, y, H(.). 
 [1]. generate p, q: len(p) = lp, len(q) = lq [1]. generate p, q: len(p) = lp, len(q) = lq 
 [2]. n  p q [2]. 
 [3]. select H : 0,1 Z , ; 
  m m n [3]. select , ; 
 [4]. select t: n 
 t (n) [4]. select t: m 
 2 t (n)
 2 
 [5]. select x: 1 x n
 [5]. select x: , gcd(x, n) = 1; 
 y xt modn (13) 
 [6]. [6]. y x−t modn (18) 
 [7]. return {n,t,x,y,H(.)}; [7]. return {n,t,x,y,H(.)}; 
 Chú thích: 
 2. Thuật toán ký 
 - len(.): hàm tính độ dài (theo bit) của một số 
 Thuật toán 1.5: 
 nguyên. 
 - p,q: là các số nguyên tố. Input: n, t, x, M. 
 2. Thuật toán ký Output: (E,S). 
 Thuật toán 1.2: [1]. select k: 
 Input: n, t, x, M. [2]. (19) 
 Output: (R,S). [3]. E  H(M || R) (20) 
 [1]. select k: [4]. S  k xE modn (21) 
 1 k n 
 [2]. R  k t modn (14) [5]. return (E,S) 
 [3]. E  H (M ) 
 3. Thuật toán kiểm tra chữ ký 
 E R
 [4]. S  k x modn (15) Thuật toán 1. 6 : 
 [5]. return (R,S) 
 Input: n, t, y, M, (E,S). 
 3. Thuật toán kiểm tra chữ ký Output: (E,S) = true / . 
 Thuật toán 1.3: 
 [1]. u St yE modn (22) 
 Input: n, t, y, M, (R,S). 
 Output: (R,S) = true/ false. [2]. v  H(M || u) (23) 
 [3]. if ( v = E ) then {return ;} 
 [1]. E  H (M ) else {return ;} 
 [2]. u  S t modn (16) 
 4. Tính đúng đắn của lược đồ LDH.02 
 [3]. E R (17) 
 v R y modn Tính đúng đắn của lược đồ LDH.02 được chứng minh 
 [4]. if ( u =v ) then {return ;} như sau: 
 else {return ;} Đặt: , b =1, E = c . Từ (18), (19), (21), (22) và 
 Mệnh đề 2 ta có: 
 4. Tính đúng đắn của lược đồ LDH.01 u = St yE modn = Sa yc modn = Rb modn = R (24) 
 Tính đúng đắn của lược đồ LDH.01 được chứng minh 
 Từ (23) và (24) suy ra: 
như sau: 
 v = H(M || u) = H(M || R) (25) 
 Đặt: t = a , E = b , R = c . Từ (13), (14), (15), (16) và 
(17) ta có: Từ (20) và (25) ta có điều cần chứng minh: v = E. 
 u = S t modn = S a modn D. Mức độ an toàn của các lược đồ mới đề xuất 
 Và: Mức độ an toàn của một lược đồ chữ ký số được đánh 
 E R b c
 v = R y modn = R y modn giá qua các khả năng sau: 
 Theo Mệnh đề 1, suy ra: . - Chống tấn công làm lộ khóa mật. 
 Đây là điều cần chứng minh. - Chống tấn công giả mạo chữ ký. 
 Ở các lược đồ mới đề xuất, có thể thực hiện một số dạng 
C. Lược đồ chữ ký LDH.02 tấn công làm lộ khóa mật (x) và giả mạo chữ ký, từ khả 
 Lược đồ thứ hai - ký hiệu LDH.02, được hình thành từ năng thành công của các dạng tấn công này có thể đánh giá 
lược đồ dạng tổng quát với lựa chọn: f1(M,R) = f3(M,E) = về mức độ an toàn và thiết lập một số điều kiện an toàn cho 
H(M||R), f2(M,R) = 1. Toán tử “||” được sử dụng ở đây là các lược đồ mới đề xuất. Phân tích, đánh giá mức độ an 
phép nối 2 xâu bit. toàn sau đây được thực hiện cho lược đồ chữ ký LDH.02, 
 việc đánh giá cho lược đồ LDH.01 cũng có thể thực hiện 
 theo cách tương tự. 
PHÁT TRIỂN MỘT DẠNG LƯỢC ĐỒ CHỮ KÝ SỐ MỚI DỰA TRÊN BÀI TOÁN RSA 
 1. Tấn công khóa mật bằng phương pháp “vét cạn”. Nhận xét: Khi giá trị của k bị sử dụng lại thì việc tấn 
 Thuật toán 1.7: công làm lộ khóa mật bằng Thuật toán 1.8 là có thể thực 
 Input: n, t, y. hiện được. 
 Thật vậy, giả sử: t , , 
 Output: x - khóa bí mật của đối tượng ký. R1 = (k1) modn E1 = H(M1 || R1 )
 S = k xE1 modn là chữ ký tương ứng với thông điệp M 
 [1]. for i = 1 to n do 1 1 1
 t E
 −t và R = k modn , E = H(M || R ), S = k x 2 modn 
 [1.1]. z (i) modn ; 2 ( 2 ) 2 2 2 2 2 ( )
 là chữ ký tương ứng với thông điệp M . Với giả thiết: 
 [1.2]. if ( z = y ) then { x i ; break;} 2
 , và , khi 
 [2]. return (x) k1 = k2 = k gcd(S2 , n) = 1
 đó: 
 Nhận xét: Nếu giá trị của x không đủ lớn thì việc tấn −1
 w = S1 S2 modn
công làm lộ khóa mật bằng Thuật toán 1.7 là hoàn toàn có 
 E1 −E2 −1 
thể thực hiện được. = (x) k (x) k modn
 (E −E )
 Điều kiện 1.1: Khóa bí mật x phải được chọn để việc = x 1 2 modn
tính: x = RSA(n,t)(y) là khó. Giải: a (E1 − E2 ) + b (−t) = 1 được a và b, ta có: 
 2. Tấn công khóa mật khi giá trị của k bị lộ. a b
 z = w (y) modn 
 Thuật toán 1.8: a.(E −E )+b.(−t)
 = x 1 2 modn = x
 Input: n, t, (E,S), k, gcd(k, n) =1, gcd(E,−t) =1 Như vậy, việc tấn công khóa mật (x) có thể thành công 
 Output: x – khóa bí mật của đối tượng ký nếu khóa k bị sử dụng lặp lại và các giả thiết đặt ra được 
 thỏa mãn. 
 −1
 [1]. w  S k modn ; Điều kiện 1.3: Giá trị của k không được phép lặp lại ở 
 [2]. Euclid (E,t; a,b): a E + b (−t) =1 các lần ký khác nhau. 
 [3]. z wa yb modn ; 4. Tấn công giả mạo chữ ký khi lựa chọn tham số t không 
 [4]. return (z) hợp lý. 
 Thuật toán 1.10: 
 Chú thích: là giải thuật Euclid mở rộng để giải phương Input: n, t, M, y – khóa công khai của U. 
trình: a E + b (−t) =1 với E, t cho trước và a, b là Output: (E*,S*) – chữ ký của U do đối tượng giả 
nghiệm. mạo U* tạo ra. 
 Nhận xét: Khi giá trị của k bị lộ hoặc do lựa chọn giá trị [1]. select k*: 1 k* n 
không hợp lý dẫn đến bị lộ, thì việc tấn công khóa mật bằng [2]. R*  (k *)t modn; 
Thuật toán 1.8 là có thể thực hiện được. Thật vậy, với giả 
 [3]. E*  H(M || R*); 
thiết: gcd(ki ,n) =1 và , khi đó: 
 E 
 −1 E −1 − 
 w = S k modn = k x k modn [4]. S*  k * y t modn ; (26) 
 = xE modn [5]. return ; 
 Giải: bằng thuật toán Euclid mở rộng E * 
 Nhận xét: Nếu cho kết quả là một giá trị nguyên 
được a và b, ta có: t 
 a b a.E b.(−t)
 z = w y modn = x x modn thì việc tính S* theo (26) và do đó việc tạo chữ ký giả mạo 
 = xa.E+b.(−t) modn = x (E*,S*) bằng Thuật toán 1.9 là hoàn toàn có thể thực hiện 
 Như vậy, nếu giá trị của khóa k bị lộ và các giả thiết đặt được. Thật vậy: 
 E 
 − .t
ra: gcd(k, n) =1 và được thỏa mãn thì việc t t 
 u = S (y)E modn = k y t y E modn 
tính khóa mật (x) là hoàn toàn có thể thực hiện được. ( ) ( )
 Điều kiện 1.2: Giá trị của k cần được chọn để việc tính: = R y −E y E modn = R 
k = RSA(n,t)(R) là khó. Do đó: 
 3. Tấn công khóa mật khi giá trị của k bị sử dụng lặp lại v = H(M || u*) = H(M || R*) = E 
 Thuật toán 1.9: 
 Như vậy, chữ ký giả mạo do U* tạo ra nhưng 
 Input: (E ,S ), (E ,S ), , 
 1 1 2 2 k1 = k2 gcd(S2 , n) = 1 hoàn toàn thỏa mãn điều kiện của thuật toán kiểm tra chữ 
 gcd((E1 − E2 ),−t) =1 ký (Thuật toán 1.6) do đó sẽ được công nhận là chữ ký hợp 
 Output: x – khóa bí mật của người ký. lệ của đối tượng U (chủ thể của khóa công khai y). 
 m 
 [1]. w  S S −1 modn; Điều kiện 1.4: Cần chọn t = +1 
 1 ( 2 ) 2 
 [2].Euclid (E1,E2,t; a,b): a (E − E )+ b (−t) = 1; 
 1 2 5. Tấn công giả mạo chữ ký nếu biết {p, q}. 
 a b
 [3]. z w y modn ; Thuật toán 1.11: 
 [4]. return (z) Input: n, p, q, t, M, y – khóa công khai của U. 
 Output: – chữ ký của U do U* tạo ra. 
 Pham Van Hiep, Luu Hong Dung 
 [1]. select k*: 1 k* n Những phân tích trên đây cho thấy, mức độ an toàn của 
 [2]. R*(k *)t modn; lược đồ mới đề xuất phụ thuộc vào mức độ khó của hai bài 
 toán: Bài toán phân tích số nguyên lớn ra các thừa số 
 [3]. E*  H(M || R *); 
 nguyên tố và Bài toán khai căn trên vành số nguyên Zn=p.q, 
 −1
 [4]. S* k * y−(E*.t mod(n)) modn (27) ở đây p và q là các số nguyên tố phân biệt. Lược đồ sẽ an 
 [5]. return (E*,S*); toàn trước các dạng tấn công làm lộ khóa mật và tấn công 
 giả mạo chữ ký nếu tuân thủ các điều kiện an toàn đã được 
 Nhận xét: Nếu từ n có thể biết {p,q} thì việc tính S* chỉ ra. 
theo (27) và do đó việc tạo cặp chữ ký giả mạo 
bằng Thuật toán 1.10 là có thể thực hiện. Trong trường hợp IV. KẾT LUẬN 
này, kẻ giả mạo (U*) có thể tính: E .t −1 mod(n) thay cho Bài báo đề xuất một dạng lược đồ chữ ký số mới xây 
 E * 
việc tính và kết quả vẫn được công nhận là dựng dựa trên bài toán khai căn trên vành Zn. Từ dạng lược 
 t đồ đã đề xuất có thể xây dựng được một họ lược đồ chữ ký 
chữ ký hợp lệ của đối tượng U. số mới, trong đó các lược đồ LDH.01 và LDH.02 chỉ là hai 
 Điều kiện 1.5: Cần chọn {p,q} để bài toán phân tích trong số các lược đồ được xây dựng theo phương pháp 
một số nguyên lớn ra các thừa số nguyên tố là khó giải. được đề xuất ở đây. Việc đánh giá mức độ an toàn của lược 
 Trong ứng dụng thực tế, các tham số {p,q} có thể chọn đồ LDH.02 trước một số dạng tấn công cho thấy khả năng 
theo Chuẩn X9.31 [2] hay FIPS 186-3 [3] của Hoa Kỳ cho ứng dụng của các lược đồ dạng này là hoàn toàn thực tế 
hệ mật RSA như sau: nếu bảo đảm các điều kiện an toàn đã được phân tích, đánh 
 Chuẩn X9.31. giá đưa ra trong bài báo. 
 Theo X9.31, tiêu chuẩn đối với các tham số {p,q} của 
hệ mật RSA bao gồm: REFERENCES 
 - Độ dài modulo n (nlen) là: 1024+256s (s ≥ 0). [1] R.L. Rivest, A. Shamir, and L. Adleman, “A method for Obtaining 
 511+128s 511+128s digital signatures and public key cryptosystems”, Commun. of the 
 - 2 2 ≤ p, q ≤ 2 (s ≥ 0). ACM, 21:120-126,1978. 
 412+128s 
 - |p – q| > 2 (s ≥ 0). [2] Burt Kaliski, “RSA Digital Signature Standards“, RSA 
 Laboratories 23rd National Information Systems Security 
 - Các ước nguyên tố của p±1 và q±1 (các số nguyên Conference, October 16-19,2000. 
 tố bổ trợ), ký hiệu là: p1, p2 và: q1, q2 phải thỏa [3] National Institute of Standards and Technology, NIST FIPS PUB 
 mãn các thông số kỹ thuật được cho trong Bảng 186-3. Digital Signature Standard, U.S. Department of 
 Commerce,1994. 
 1 dưới đây: [4] A. Menezes, P. van Oorschot, and S. Vanstone, “Handbook of 
 Bảng 1. Tiêu chuẩn an toàn đối với các số nguyên tố bổ Applied Cryptography”, CRC Press, 1996. 
 trợ [5] D.R Stinson, Cryptography: Theory and Practice, CRC Press 1995. 
 [6] Wenbo Mao, Modern Cryptography: Theory and Practice, Prentice 
 Độ dài của Độ dài tối thiểu Độ dài tối đa Hall PTR, 2003. 
 modulo n của p , p và q , của p , p và 
 1 2 1 1 2 DEVELOPING A NEW TYPE OF DIGITAL 
 (nlen) q2 q1, q2 
 1024 + 256.s > 100 bit ≤ 120 bit SIGNATURE SCHEME BASED ON RSA 
 PROBLEM 
 Chuẩn FIPS 186-3. 
 Theo FIPS 186-3, tiêu chuẩn đối với các tham số {p,q} Abstract: The paper proposes a new method for constructing 
 của hệ mật RSA bao gồm: a signature scheme based on the Zn ring-rooted problem, also 
 511+128s 511+128s
 - 2 ≤ p, q ≤ 2 (s ≥ 0). known as RSA problem. From the proposed method, it is possible 
 to create a new family of signature schemes similar to ElGamal's 
 nlen 
 −100 signature family based on discrete logarithmic problem. The 
 - |p – q| > 2 2 . paper also proposes two signature schemes and assessments of 
 - Các ước nguyên tố của p±1 và q±1 (các số their security for the purpose of illustrating the implementation of 
 the proposed method to create signature schemes and their 
 nguyên tố bổ trợ), ký hiệu là: p1, p2 và: q1, q2 phải 
 applicability in practical applications. The schemas will be safe 
 thỏa mãn các thông số kỹ thuật được cho trong 
 against attacks that expose secret keys and forged signature 
 Bảng 2 dưới đây: attacks if the specified security conditions are followed. 
 Bảng 2. Tiêu chuẩn an toàn đối với các số nguyên tố bổ 
 trợ (độ dài tối đa, tối thiểu của p1, p2, q1, q2) Keywords: Root problem, Digital Signature Schema, Hash 
 Độ dài Độ dài tối Độ dài tối đa của len(p1) Function, Schema, Digital Signature. 
 của thiểu của + len(p2) và len(q1) + 
 modulo p1, p2, q1, len(q2) Phạm Văn Hiệp Nhận học vị Thạc sỹ 
 n (nlen) q2 Các số Các số năm 2007. Hiện công tác tại khoa Công 
 nguyên tố nguyên tố nghệ thông tin, trường Đại học Công 
 xác suất chứng nghiệp Hà Nội. Lĩnh vực nghiên cứu: Mật 
 minh được mã và An toàn thông tin, Mạng và hệ 
 1024 bit > 100 bit < 496 bit < 239 bit thống thông tin. 
 2048 bit > 140 bit < 1007 bit < 494 bit 
 3072 bit > 170 bit < 1518 bit < 750 bit 
PHÁT TRIỂN MỘT DẠNG LƯỢC ĐỒ CHỮ KÝ SỐ MỚI DỰA TRÊN BÀI TOÁN RSA 
 Lưu Hồng Dũng Nhận học vị Tiến sỹ 
 năm 2013. Hiện công tác tại khoa Công 
 nghệ thông tin, Học viện Kỹ thuật Quân 
 sự. Lĩnh vực nghiên cứu: Mật mã và An 
 toàn thông tin.