Xem mẫu
- 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
Phát triển một dạng lược đồ chữ ký số mới
Developing a new type of digital signature scheme
Lƣu Hồng Dũng1, Nguyễn Tiền Giang2, Hồ Ngọc Duy3, Nguyễn Thị Thu Thủy4
luuhongdung@gmail.com, ntgiang77@gmail.com, aimezthngocduy207@yahoo.com, thuthuynt@gmail.com
1
Khoa Công nghệ Thông tin – Học viện Kỹ thuật Quân sự
2
Cục Công nghệ Thông tin – Bộ Quốc phòng
3
Cục Công nghệ Thông tin – Bộ Quốc phòng
4
Trƣờng Cao đẳng Kinh tế – Kỹ thuật Quảng Nam
Tóm tắt—Bài báo đề xuất một dạng lược đồ chữ ký số mới được
Trong một hệ thống giao dịch điện tử với dịch vụ chứng
xây dựng trên cơ sở các bài toán phân tích một số nguyên lớn ra
các thừa số nguyên tố, bài toán khai căn trong modulo hợp số.
thực số dùng chung bộ tham số {n,t}, bài toán RSA(n,t) là
Từ dạng lược đồ mới đề xuất có thể phát triển thành một số lược khó theo nghĩa không thể thực hiện đƣợc trong thời gian
đồ chữ ký số có khả năng ứng dụng được trong thực tế. thực. Ở đó, mỗi thành viên U của hệ thống tự chọn cho
mình khóa bí mật x thỏa mãn: 1 < x < n, tính và công khai
Từ khoá: Digital Signature, Digital Signature Schema, tham số:
Hash Function.
y x t mod n (1.2)
I. ĐẶT VẤN ĐỀ Chú ý:
Chữ ký số hiện nay đã đƣợc ứng dụng rộng rãi trong (i) Mặc dù bài toán RSA(n,t) là khó, tuy nhiên không
các lĩnh vực nhƣ Chính phủ điện tử, Thƣơng mại điện tử,… phải với mọi yℤn* thì việc tính RSA(n,t)(y) đều khó, chẳng
hay trong các hệ thống viễn thông và mạng máy tính. Tuy t
hạn những y = x mod n với x không đủ lớn thì bằng cách
nhiên, việc nghiên cứu, phát triển các lƣợc đồ chữ ký số mới duyệt dần x = 1, 2, ... cho đến khi tìm đƣợc nghiệm của (1.2)
cho mục đích thiết kế - chế tạo các sản phẩm, thiết bị an ta sẽ tìm đƣợc khóa bí mật x, do đó các tham số mật x phải
toàn và bảo mật thông tin trong nƣớc vẫn luôn là vấn đề cần đƣợc lựa chọn sao cho việc tính RSA(n,t)(y) đều khó.
thiết đƣợc đặt ra.
Bài báo này đề xuất phát triển một dạng lƣợc đồ chữ 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 < (p1).(q1). 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(n,t): Với mỗi số nguyên dương y ℤ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
x t mod n 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ó:
s e1 mod n (r e2 y e3 mod n) e1 mod n k e1.e2 x e1.e3 mod n
A. Lược đồ dạng tổng quát (k e1 mod n) e2 ( x e1 mod n) e3 mod n r e2 y e3 mod n
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: e1 t , e2 f1 (M , r ) , e3 f 2 (M , r ) ta có:
1) Phương pháp hình thành tham số và khóa
Dữ liệu vào: p, q, t, x. u s t mod n s e1 mod n
Kết quả: n, y. và:
Các bƣớc thực hiện: v r f1 M ,r y f2 M ,r mod n r e2 y e3 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: uv
y x t mod n 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 , m n ;
1. Hình thành phần thứ nhất của chữ ký:
r k t mod n ; [3]. t n 1
2
2. Hình thành phần thứ 2 của chữ ký:
s k f1 M ,r x f 2 ( M ,r ) mod n [4]. y x t mod n (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:
(ii) f1 (.), f 2 (.) : các hàm của M và r. Input: n, t, x, k, M.
3) Phương pháp kiểm tra chữ ký Output: (r,s).
Dữ liệu vào: n, t, y, (r,s), M. [1]. r k t mod n (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 x r mod n (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 s t mod n 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).
v r f1 M ,r y f 2 M ,r mod n 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 s t mod n
4) Tính đúng đắn của phương pháp hình thành và kiểm [3]. v r e y r mod n
tra chữ ký [4]. if ( u v ) then {return true ;}
Mệnh đề 1:
else {return false ;}
Cho p, q là 2 số nguyên tố phân biệt, n pq ,
, 1 x, k n . Nếu: y x e mod n , 4) Tính đúng đắn của lược đồ LD-01
1 e1 , e2 , e3 ( p 1) (q 1)
1
Tính đúng đắn của lƣợc đồ LD 1.01 đƣợc chứng minh
r k e1 mod n , s k e2 x e3 mod n thì: s e1 r e2 y e3 mod n . 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
Đặt: t e1 , e e2 , r e3 . Từ (1.3), (1.4), (1.6) ta có: v H r || M (1.16)
Từ (1.16) và (1.9) suy ra:
u st mod n s e1 mod n ve
và: Đây là điều cần chứng minh.
v r e y r mod n r e2 y e3 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 Z m , m n ; Thuật toán 1.7:
Input: n, t, y.
[3]. t m 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 mod n ;
[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 mod n (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 x e mod n (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 mod n ;
[1]. u s t y e mod n (1.11) [2]. Euclid (e,t; a,b): a.e b.(t ) 1
[2]. v H u || M (1.12) [3]. z wa y b 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: a.e b.(t ) 1 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: t e1 , 1 e2 , e e3 . Từ (1.7), (1.8), (1.9), (1.10)
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 đó:
s t mod n r y e mod n (1.13)
w s k 1 mod n k x e k 1 mod n
Từ (1.13) suy ra:
r s t y e mod n (1.14) x e mod n
Giải: a.e b.(t ) 1 bằng thuật toán Euclid mở rộng
Từ (1.11) và (1.14) ta có:
ur (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
z w a y b mod n x a.e x b.( t ) mod n (e*,s*) bằng Thuật toán 1.9 là hoàn toàn có thể thực hiện
a .e b.( t ) đƣợc. Thật vậy:
x 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
ra: gcd(k , n) 1 và gcd(e,t ) 1 đƣợc thỏa mãn thì việc
u s y
t e
y
mod n k t t
y e mod n
tính khóa mật (x) là hoàn toàn có thể thực hiện đƣợc. r y e y e 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 (e*, s*) 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: (e1,s1), (e2,s2), k1 k2 , gcd((e1 e2 ),t ) 1 , của đối tƣợng U (chủ thể của khóa công khai y).
gcd(s2 , n) 1
Output: x – khóa bí mật của ngƣời ký. Điều kiện 1.4: Cần chọn t m 1
2
[1]. w s1 s2 1 mod n ;
[2]. Euclid (e1,e2,t; a,b): a.e1 e2 b.(t ) 1 ; 5) Tấn công giả mạo chữ ký nếu biết {p, q}.
[3]. z wa y b 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: (e*, s*) – 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]. r* k *t mod n ;
hiện đƣợc. Thật vậy, giả sử: r1 k1 t mod n , e1 H r1 || M1 , [2]. e* H r* || M mod n ;
[3]. s* k * y e*.t mod( p1).(q1) mod n
1
s1 k1 x e1 mod n là chữ ký tƣơng ứng với thông điệp M 1 (1.18)
và r2 k 2 t mod n , e2 H r2 || M 2 , s2 k 2 x e mod n là
2
[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*
k1 k 2 k , gcd((e1 e2 ),t ) 1 và gcd(s2 , n) 1 , khi đó: theo (1.18) và do đó việc tạo cặp chữ ký giả mạo (e*,s*)
bằng Thuật toán 1.10 là có thể thực hiện. Trong trƣờng hợp
w s1 s21 mod n 1
này, kẻ giả mạo (U*) có thể tính: e .t mod( p 1).(q 1) thay
x 1 k x
e2
k 1 mod n cho việc tính e * và kết quả (e*, s*) vẫn đƣợc công nhận là
e
t
x e1e2 mod n
Giải: a.(e1 e2 ) b.(t ) 1 đƣợc a và b, ta có: chữ ký hợp lệ của đối tƣợng U.
Đ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
a b
một số nguyên lớn ra các thừa số nguyên tố là khó giải.
x a.e1 e2 b.( t ) 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).
2 2
không hợp lý. 511+128s 511+128s
- ≤ 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).
Output: (e*, s*) – chữ ký của U do đối tƣợng giả - Các ƣớc nguyên tố của p±1 và q±1 (các số nguyên
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
[1]. r* k *t mod n ; dƣới đây:
[2]. e* H r* || M mod n ; Bảng 2.1: Tiêu chuẩn an toàn đối với các số nguyên tố
e bổ trợ.
[3]. s* k * y t mod n ; (1.17) nlen Độ dài tối thiểu Độ dài tối
của p1, p2 và q1, đa của p1, p2
[4]. return (e*, s*) ;
q2 và q1, q2
Nhận xét: Nếu e * 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:
IV. KẾT LUẬN
2 2
511+128s 511+128s
- ≤ 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ƣ
của thiểu của len(p1) + len(p2) và khía cạnh hiệu quả thực hiện.
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 Zn=p.q, ở [5] D.R Stinson, Cryptography: Theory and Practice, CRC Press
1995.
đây p và q là các số nguyên tố phân biệt. Lƣợc đồ sẽ an toàn
25
nguon tai.lieu . vn
