Phát triển một dạng lược đồ chữ ký số mới

hữ k‎ý (ii) Với lựa chọn x nêu trên thì rõ ràng không có ai 
số mới dựa trên các bài toán khó đã đƣợc biết đến nhƣ là cơ ngoài U biết đƣợc giá trị x, vì vậy việc biết đƣợc x đủ để 
sở để xây dựng nên hệ mật RSA danh tiếng [1]. Tuy nhiên, xác thực đó là U. 
việc sử dụng các bài toán này trong các thủ tục hình thành 
 B. Bài toán phân tích một số nguyên lớn ra các thừa số 
tham số và khóa, hình thành chữ k‎ý ở lƣợc đồ chữ ký RSA 
 nguyên tố 
và các lƣợc đồ chữ k‎ý mới đề xuất là hoàn toàn khác nhau. 
 Bài toán phân tích một số nguyên lớn ra các thừa số 
 II. CÁC BÀI TOÁN CƠ SỞ nguyên tố (Bài toán phân tích số) đƣợc phát biểu nhƣ sau: 
 - Cho p, q là 2 số nguyên tố lớn và mạnh; 
A. Bài toán khai căn trên vành số Zn - Từ p và q dễ dàng tính đƣợc: n p q ; 
 Cho cặp các số nguyên dƣơng {n,t} với n là tích của hai - Từ n rất khó tìm đƣợc p và q. 
số nguyên tố p và q, còn t đƣợc chọn trong khoảng: Trong hệ mật RSA, bài toán phân tích số đƣợc sử dụng 
1 < t < (p 1).(q 1). Khi này bài toán khai căn trên vành số làm cơ sở để hình thành cặp khóa công khai/bí mật. Với 
nguyên Zn hay còn gọi là bài toán RSA(n,t) đƣợc phát biểu việc giữ bí mật các tham số p, q và  n , có thể tính đƣợc 
nhƣ sau: khóa mật (d) từ khóa công khai (e) nếu tìm đƣợc p, q từ việc 
 phân tích modulo n. 
 Bài toán RSA : Với mỗi số nguyên dương y ℤ *, 
 (n,t) n Hiện tại, các bài toán trên vẫn đƣợc coi là các bài toán 
hãy tìm x thỏa mãn phương trình sau: 
 khó [4,5] do chƣa có giải thuật thời gian đa thức cho các bài 
 xt modn y (1.1) toán này và cũng nhƣ chƣa có một công bố nào cho thấy hệ 
 mật RSA bị phá vỡ trong các ứng dụng thực tế bằng việc 
 Thuật toán để giải bài toán RSA(n,t) có thể đƣợc viết giải các bài toán này khi các tham số của nó đƣợc chọn hợp 
nhƣ một thuật toán tính hàm RSA(n,t)(.) với biến đầu vào là y lý‎. 
còn giá trị hàm là nghiệm x của phƣơng trình (1.1): 
 x RSA(n,t) (y) 
 21 
 Hội thảo quốc gia lần thứ XVI: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông- Đà Nẵng, 13-14/11/2013 
 III. XÂY DỰNG LƢỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN Chứng minh 
 HAI BÀI TOÁN KHAI CĂN VÀ PHÂN TÍCH SỐ Thật vậy, ta có: 
 e e e e e .e e .e
 s 1 modn (r 2 y 3 modn) 1 modn k 1 2 x 1 3 modn 
A. Lược đồ dạng tổng quát e e e e e e
 (k 1 modn) 2 (x 1 modn) 3 modn r 2 y 3 modn
 Lƣợc đồ dạng tổng quát bao gồm các phƣơng pháp hình 
thành các tham số hệ thống và khóa, phƣơng pháp hình Mệnh đề đã đƣợc chứng minh. 
thành chữ k‎ý và phƣơng pháp kiểm tra tính hợp lệ của chữ Tính đúng đắn của phƣơng pháp hình thành và kiểm tra 
ký. Từ dạng tổng quát này, bằng cách lựa chọn các tham số chữ k‎ý có thể chứng minh nhƣ sau: 
cụ thể sẽ cho phép tạo ra các lƣợc đồ chữ k‎ý số khác nhau. 
 Đặt: e t , e f (M,r), e f (M,r) ta có: 
 1 2 1 3 2
 1) Phương pháp hình thành tham số và khóa t e
 Dữ liệu vào: p, q, t, x. u s modn s 1 modn 
 Kết quả: n, y. và: 
 f M ,r f M ,r e e
 Các bƣớc thực hiện: v r 1 y 2 mod n r 2 y 3 mod n 
 1. Tính modulo n: n p q Theo Mệnh đề 1 suy ra: 
 2. Hình thành khóa công khai: u v 
 t
 y x modn B. Lược đồ chữ k‎ý LD-01 
 Chú thích: Lƣợc đồ thứ nhất - k‎ý hiệu LD 1.01, đƣợc hình thành từ 
 (i) p, q: các số nguyên tố phân biệt. lƣợc đồ dạng tổng quát với lựa chọn: f1(M,r) = H(M), 
 (ii) x: khóa bí mật có giá trị trong khoảng: 1 x n . f2(M,r) = r. 
 (iii) t: số mũ có giá trị trong khoảng: 1) Hình thành tham số và khóa 
 1 t (p 1) (q 1) Thuật toán 1.1: 
 2) Phương pháp hình thành chữ ký Input: p, q, x. 
 Dữ liệu vào: n, t, x, k, M – thông điệp dữ liệu cần k‎ý. Output: n, t, y, H(.). 
 Kết quả: (r,s) – chữ k‎ý của U lên M. [1]. n  p q 
 Các bƣớc thực hiện: 
 [2]. select H : 0,1 Z , m n ; 
 1. Hình thành phần thứ nhất của chữ k‎‎ý: m
 r k t modn ; [3]. n 
 t  1
 2. Hình thành phần thứ 2 của chữ k‎‎ý: 2 
 f M ,r f (M ,r) t
 s k 1 x 2 modn [4]. y  x modn (1.3) 
 Chú thích: [5]. return {n,t,y,H(.)}; 
 (i) k: khóa bí mật ngắn hạn có giá trị trong khoảng: 2) Hình thành chữ k‎ý 
 1 k n Thuật toán 1.2: 
 Input: n, t, x, k, M. 
 (ii) f1(.), f2 (.): các hàm của M và r. 
 3) Phương pháp kiểm tra chữ ký Output: (r,s). 
 t
 Dữ liệu vào: n, t, y, (r,s), M. [1]. r  k modn (1.4) 
 Kết quả: Khẳng định (r,s) là chữ k‎ý hợp lệ ((r,s) = true) [2]. e  H M (1.5) 
hay (r,s) là giả mạo và/hoặc M không còn toàn vẹn [3]. s  k e xr modn (1.6) 
((r,s) = false). [4]. return (r,s); 
 Các bƣớc thực hiện: 3) Kiểm tra chữ k‎ý 
 1. Tính vế thứ nhất của phƣơng trình kiểm tra: 
 u st modn ‎‎ Thuật toán 1.3: 
 2. Tính vế thứ hai của phƣơng trình kiểm tra: Input: n, t, y, M, (r,s). 
 f M ,r f M ,r 
 v r 1 y 2 modn Output: (r,s) = true / false . 
 3. Nếu (u = v) thì (r,s) = true , ngƣợc lại thì: [1]. e  H M 
 (r,s) = false. [2]. u  st modn 
 4) Tính đúng đắn của phương pháp hình thành và kiểm [3]. v  r e yr mod n 
tra chữ k‎ý [4]. if ( u v ) then {return true ;} 
 Mệnh đề 1: 
 else {return ;} 
 Cho p, q là 2 số nguyên tố phân biệt, n p q , 
 e 4) Tính đúng đắn của lược đồ LD-01 
1 e ,e ,e ( p 1) (q 1) , 1 x,k n . Nếu: y x 1 mod n , 
 1 2 3 Tính đúng đắn của lƣợc đồ LD 1.01 đƣợc chứng minh 
 e e e e e e
r k 1 modn , s k 2 x 3 modn thì: s 1 r 2 y 3 modn . nhƣ sau: 
 22 
 Hội thảo quốc gia lần thứ XVI: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông- Đà Nẵng, 13-14/11/2013 
 (1.16) 
 Đặt: t e1 , e e2 , r e3 . Từ (1.3), (1.4), (1.6) ta có: v H r || M 
 Từ (1.16) và (1.9) suy ra: 
 u st modn se1 modn v e 
 và: Đây là điều cần chứng minh. 
 e r e e3 
 v r y mod n r 2 y mod n D. Mức độ an toàn của các lược đồ mới đề xuất 
 Mức độ an toàn của một lƣợc đồ chữ k‎ý số đƣợc đánh 
 Theo Mệnh đề 1, suy ra: u v . giá qua các khả năng sau: 
 Đây là điều cần chứng minh. - Chống tấn công làm lộ khóa mật. 
 - Chống tấn công giả mạo chữ ký. 
C. Lược đồ chữ ký LD–02 Ở các lƣợc đồ mới đề xuất, có thể thực hiện một số 
 Lƣợc đồ thứ hai - k‎ý hiệu LD-02, đƣợc hình thành từ dạng tấn công làm lộ khóa mật (x) và giả mạo chữ k‎ý, từ 
lƣợc đồ dạng tổng quát với lựa chọn: f1(M,r) = 1, khả năng thành công của các dạng tấn công này có thể đánh 
f2(M,r) = H(r||M)). giá về mức độ an toàn và thiết lập một số điều kiện an toàn 
 1) Hình thành tham số và khóa cho các lƣợc đồ mới đề xuất. Phân tích, đánh giá mức độ an 
 Thuật toán 1.4: toàn sau đây đƣợc thực hiện cho lƣợc đồ chữ k‎ý LD-02, 
 Input: p, q, x. việc đánh giá cho lƣợc đồ LD-01 cũng có thể thực hiện theo 
 Output: n, t, y, H(.). cách tƣơng tự. 
 [1]. n  p q 1) Tấn công khóa mật bằng phương pháp “vét cạn”. 
 [2]. select H : 0,1 Zm , m n ; Thuật toán 1.7: 
 m Input: n, t, y. 
 [3]. t  1 Output: x – khóa bí mật của đối tƣợng k‎ý. 
 2 
 [1]. for i = 1 to n do 
 [4]. y  x t mod n (1.7) 
 [1.1]. z  i t modn ; 
 [5]. return {n,t,y,H(.)}; 
 [1.2]. if ( z y ) then { x  i ; break;} 
 2) Hình thành chữ k‎ý 
 Thuật toán 1.5: [2]. return (x); 
 Input: n, t, x, k, M. Nhận xét: Nếu giá trị của x không đủ lớn thì việc tấn 
 Output: (e,s). công làm lộ khóa mật bằng Thuật toán 1.7 là hoàn toàn có 
 [1]. r  k t modn (1.8) th ể th ự c hi ệ n đƣ ợ c. 
 [2]. e  H r || M (1.9) Điều kiện 1.1: Khóa bí mật x phải được chọn để việc 
 [3]. s  k xe modn (1.10) tính: x = RSA (n,t) ( y ) là khó. 
 [4]. return (e,s); 2) Tấn công khóa mật khi giá trị của k bị lộ. 
 3) Kiểm tra chữ k‎ý Thuật toán 1.8: 
 ‎‎ Thuật toán 1.6: Input: n, t, (e,s), k, gcd(k,n) 1, gcd(e, t) 1. 
 Input: n, t, y, M, (e,s). Output: x – khóa bí mật của đối tƣợng k‎ý. 
 Output: (e,s) = true / false. [1]. w  s k 1 modn; 
 [1]. u  st y e modn (1.11) [2]. Euclid (e,t ; a,b): a.e b.( t) 1 
 a b
 [2]. v  H u || M (1.12) [3]. z  w y mod n ; 
 [3]. if ( v e ) then {return true ;} [4]. return (z); 
 else {return false;} Chú thích: Euclid (e,t; a,b) là giải thuật Euclid mở rộng 
 để giải phƣơng trình: với e, t cho trƣớc và 
 4) Tính đúng đắn của lược đồ LD-02 
 Tính đúng đắn của lƣợc đồ LD 1.01 đƣợc chứng minh a, b là nghiệm. 
nhƣ sau: Nhận xét: Khi giá trị của k bị lộ hoặc do lựa chọn giá 
 trị không hợp l‎ý dẫn đến bị lộ, thì việc tấn công khóa mật 
 Đặt: , , e e . Từ (1.7), (1.8), (1.9), (1.10) 
 t e1 1 e2 3 bằng Thuật toán 1.8 là có thể thực hiện đƣợc. Thật vậy, với 
và Mệnh đề 1.1 ta có: 
 giả thiết: gcd(ki ,n) 1 và gcd(e, t) 1, khi đó: 
 st mod n r y e mod n (1.13) 
 w s k 1 mod n k xe k 1 mod n
 Từ (1.13) suy ra: 
 e
 r st y e modn (1.14) x mod n
 Giải: bằng thuật toán Euclid mở rộng 
 Từ (1.11) và (1.14) ta có: 
 u r (1.15) đƣợc a và b, ta có: 
 Thay (1.15) vào (1.12), ta đƣợc: 
 23 
 Hội thảo quốc gia lần thứ XVI: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông- Đà Nẵng, 13-14/11/2013 
 a b a.e b.( t) (e*,s*) bằng Thuật toán 1.9 là hoàn toàn có thể thực hiện 
 z w y mod n x x mod n 
 đƣợc. Thật vậy: 
 xa.e b.( t) mod n x
 e 
 .t
 Nhƣ vậy, nếu giá trị của khóa k bị lộ và các giả thiết đặt t t 
 u s y e mod n k y t ye mod n 
ra: gcd(k,n) 1 và gcd(e, t) 1 đƣợc thỏa mãn thì việc 
tính khóa mật (x) là hoàn toàn có thể thực hiện đƣợc. r y e ye mod n r 
 Điều kiện 1.2: Giá trị của k cần được chọn để việc Do đó: 
tính: k = RSA(n,t)(r) là khó. v H(u || M ) H(r || M ) e 
 3) Tấn công khóa mật khi giá trị của k bị sử dụng lặp Nhƣ vậy, chữ k‎ý giả mạo do U* tạo ra nhƣng 
lại. 
 hoàn toàn thỏa mãn điều kiện của thuật toán kiểm tra chữ k‎ý 
 Thuật toán 1.8: 
 (Thuật toán 1.16) do đó sẽ đƣợc công nhận là chữ k‎ý hợp lệ 
 Input: (e ,s ), (e ,s ), , , 
 1 1 2 2 k1 k2 gcd((e1 e2 ), t) 1 của đối tƣợng U (chủ thể của khóa công khai y). 
 gcd(s ,n) 1 
 2 m 
 Output: x – khóa bí mật của ngƣời k‎ý. Điều kiện 1.4: Cần chọn t 1 
 1 2 
 [1]. w  s1 s2 mod n; 
 5) Tấn công giả mạo chữ k‎ý nếu biết {p, q}. 
 [2]. Euclid (e1,e2,t; a,b): a. e1 e2 b.( t) 1; 
 [3]. z  wa yb mod n ; Thuật toán 1.10: 
 Input: n, p, q, t, M, k*, y – khóa công khai của U. 
 [4]. return (z); 
 Output: – chữ k‎ý của U do U* tạo ra. 
 Nhận xét: Khi giá trị của k bị sử dụng lại thì việc tấn 
công làm lộ khóa mật bằng Thuật toán 1.8 là có thể thực [1]. ; 
hiện đƣợc. Thật vậy, giả sử: t , , [2]. ; 
 r1 k1 modn e1 H r1 || M1 
 1 
 e1 e*.t mod(p 1).(q 1) 
s1 k1 x mod n là chữ k‎‎ý tƣơng ứng với thông điệp M1 [3]. s*  k * y modn (1.18) 
 t e2
và r2 k2 mod n , e2 H r2 || M 2 , s2 k2 x modn là [4]. return (e*, s*) ; 
chữ k‎‎ý tƣơng ứng với thông điệp M 2 . Với giả thiết: Nhận xét: Nếu từ n có thể biết {p,q} thì việc tính s* 
 theo (1.18) và do đó việc tạo cặp chữ k‎ý giả mạo (e*,s*) 
k1 k2 k , gcd((e1 e2 ), t) 1 và gcd(s2 ,n) 1, khi đó: 
 1 bằng Thuật toán 1.10 là có thể thực hiện. Trong trƣờng hợp 
 w s s mod n 1 
 1 2 này, kẻ giả mạo (U*) có thể tính: e .t mod( p 1).(q 1) thay 
 e1 e2 1 e * 
 x k x k mod n cho việc tính và kết quả vẫn đƣợc công nhận là 
 t
 e e 
 x 1 2 mod n
 chữ k‎‎ý hợp lệ của đối tƣợng U. 
 Giải: a.(e1 e2 ) b.( t) 1 đƣợc a và b, ta có: 
 a b Điều kiện 1.5: Cần chọn {p,q} để bài toán phân tích 
 z w y mod n một số nguyên lớn ra các thừa số nguyên tố là khó giải. 
 a. e e b.( t)
 x 1 2 mod n x Trong ứng dụng thực tế, các tham số {p,q} có thể chọn 
 Nhƣ vậy, việc tấn công khóa mật (x) có thể thành công theo Chuẩn X9.31 hay FIPS 186-3 của Hoa Kỳ cho hệ mật 
nếu khóa k bị sử dụng lặp lại và các giả thiết đặt ra đƣợc RSA nhƣ sau: 
thỏa mãn. Chuẩn X9.31. 
 Điều kiện 1.3: Giá trị của k không được phép lặp lại ở Theo X9.31, tiêu chuẩn đối với các tham số {p,q} của 
các lần k‎ý khác nhau. hệ mật RSA bao gồm: 
 4) Tấn công giả mạo chữ k‎ý khi lựa chọn tham số t - Độ dài modulo n (nlen) là: 1024+256s (s ≥ 0). 
không hợp l‎ý. 511+128s 511+128s
 - 2 2 ≤ p, q ≤ 2 (s ≥ 0). 
 Thuật toán 1.9: 412+128s 
 Input: n, t, M, k*, y – khóa công khai của U. - |p – q| > 2 (s ≥ 0). 
 - Các ƣớc nguyên tố của p±1 và q±1 (các số nguyên 
 Output: (e*, s*) – chữ k‎ý của U do đối tƣợng giả 
 * tố bổ trợ), k‎ý hiệu là: p1, p2 và: q1, q2 phải thỏa mãn 
 mạo U tạo ra. các thông số kỹ thuật đƣợc cho trong Bảng 2.1 
 t
 [1]. r*  k * modn ; dƣới đây: 
 [2]. e*  H r*|| M modn ; Bảng 2.1: Tiêu chuẩn an toàn đối với các số nguyên tố 
 bổ trợ. 
 e 
 [3]. s*  k * y t mod n ; (1.17) nlen Độ dài tối thiểu Độ dài tối 
 của p , p và q , đa của p , p 
 [4]. return ; 1 2 1 1 2
 q và q , q 
 e * 2 1 2
 Nhận xét: Nếu cho kết quả là một giá trị nguyên 1024 + 256.s > 100 bit ≤ 120 bit 
 t 
thì việc tính s* theo (1.17) và do đó việc tạo chữ k‎ý giả mạo 
 24 
 Hội thảo quốc gia lần thứ XVI: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông- Đà Nẵng, 13-14/11/2013 
 trƣớc các dạng tấn công làm lộ khóa mật và tấn công giả 
 Chuẩn FIPS 186-3. mạo chữ k‎ý nếu tuân thủ các điều kiện an toàn đã đƣợc chỉ 
 Theo FIPS 186-3, tiêu chuẩn đối với các tham số {p,q} ra. 
 của hệ mật RSA bao gồm: 
 511+128s 511+128s IV. KẾT LUẬN 
 - 2 2 ≤ p, q ≤ 2 (s ≥ 0). 
 Bài báo đề xuất một dạng lƣợc đồ chữ k‎‎ý số mới xây 
 nlen 
 100 dựng dựa trên các bài toán phân tích số, khai căn trên vành 
 2 
 - |p – q| > 2 . Zn. Từ dạng lƣợc đồ mới đề xuất đã xây dựng đƣợc một số 
 - Các ƣớc nguyên tố của p±1 và q±1 (các số nguyên lƣợc đồ chữ k‎ý số cụ thể cho mục đích ứng dụng. Mức độ an 
 tố bổ trợ), k‎ý hiệu là: p1, p2 và: q1, q2 phải thỏa mãn toàn của các lƣợc đồ mới đề xuất đƣợc đánh giá qua một số 
 các thông số kỹ thuật đƣợc cho trong Bảng 2.2 dạng tấn công đã đƣợc biết đến trong thực tế, cho thấy các 
 dƣới đây: lƣợc đồ mới này có thể sử dụng cho các ứng dụng thực tế 
 Bảng 2.2: Tiêu chuẩn an toàn đối với các số nguyên tố nếu các tham số hệ thống đƣợc lựa chọn hợp l‎ý. Tuy nhiên, 
 bổ trợ. để sử dụng đƣợc trong thực tế, các lƣợc đồ này cần đƣợc cải 
 Độ dài Độ dài tối Độ dài tối đa của tiến và đánh giá kỹ càng hơn cả về mức độ an toàn cũng nhƣ 
 khía cạnh hiệu quả thực hiện. 
 của thiểu của len(p1) + len(p2) và 
 modulo p1, p2, q1, len(q1) + len(q2) 
 n q2 Các số Các số TÀI LIỆU THAM KHẢO 
 (nlen) nguyên tố nguyên tố 
 [1] R.L. Rivest, A. Shamir, and L. Adleman, “A method for 
 xác xuất chứng Obtaining digital signatures and public key cryptosystems”, 
 minh được Commun. of the ACM, 21:120-126,1978. 
 1024 bit > 100 bit < 496 bit < 239 bit [2] Burt Kaliski, “RSA Digital Signature Standards“, RSA 
 2048 bit > 140 bit < 1007 bit < 494 bit Laboratories 23rd National Information Systems Security 
 Conference, October 16-19,2000. 
 3072 bit > 170 bit < 1518 bit < 750 bit 
 [3] National Institute of Standards and Technology, NIST FIPS 
 PUB 186-3. Digital Signature Standard, U.S. Department of 
 Những phân tích trên đây cho thấy, mức độ an toàn của Commerce,1994. 
lƣợc đồ mới đề xuất phụ thuộc vào mức độ khó của 2 bài [4] A. Menezes, P. van Oorschot, and S. Vanstone, “Handbook of 
toán: Bài toán phân tích số nguyên lớn ra các thừa số Applied Cryptography”, CRC Press, 1996. 
nguyên tố và Bài toán khai căn trên vành số nguyên Z , ở [5] D.R Stinson, Cryptography: Theory and Practice, CRC Press 
 n=p.q 1995. 
đây p và q là các số nguyên tố phân biệt. Lƣợc đồ sẽ an toàn 
 25