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
, , ,
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
xây dựng trên cơ sở các bài tốn phân tích một số ngun lớn ra
các thừa số nguyên tố, bài toán khai căn trong modulo hợp số.
Từ dạng lược đồ mới đề xuất có thể phát triển thành một số lược
đồ chữ k‎ý số có khả năng ứng dụng được trong thực tế.
Từ khoá: Digital Signature,
Hash Function.

I.

Trong một hệ thống giao dịch điện tử với dịch vụ chứng
thực số dùng chung bộ tham số {n,t}, bài toán RSA(n,t) là
khó theo nghĩa khơng thể thực hiện đƣợc trong thời gian
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
tham số:

Digital Signature Schema,

y  x t mod n

ĐẶT VẤN ĐỀ

Chú ý:

Chữ k‎‎ý số hiện nay đã đƣợc ứng dụng rộng rãi trong
các lĩnh vực nhƣ Chính phủ điện tử, Thƣơng mại điện tử,…
hay trong các hệ thống viễn thông và mạng máy tính. Tuy
nhiên, việc nghiên cứu, phát triển các lƣợc đồ chữ k‎ý số mới
cho mục đích thiết kế - chế tạo các sản phẩm, thiết bị an
toàn và bảo mật thông tin trong nƣớc vẫn luôn là vấn đề cần
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‎ý
số mới dựa trên các bài tốn khó đã đƣợc biết đến nhƣ là cơ
sở để xây dựng nên hệ mật RSA danh tiếng [1]. Tuy nhiên,
việc sử dụng các bài toán này trong các thủ tục hình thành
tham số và khóa, hình thành chữ k‎ý ở lƣợc đồ chữ ký RSA
và các lƣợc đồ chữ k‎ý mới đề xuất là hoàn toàn khác nhau.
II.

(i) Mặc dù bài tốn RSA(n,t) là khó, tuy nhiên khơng
phải với mọi yℤn* thì việc tính RSA(n,t)(y) đều khó, chẳng
t
hạn những y = x mod n với x không đủ lớn thì bằng cách
duyệt dần x = 1, 2, ... cho đến khi tìm đƣợc nghiệm của (1.2)
ta sẽ tìm đƣợc khóa bí mật x, do đó các tham số mật x phải
đƣợc lựa chọn sao cho việc tính RSA(n,t)(y) đều khó.

(ii) Với lựa chọn x nêu trên thì rõ ràng khơng có ai
ngồi U biết đƣợc giá trị x, vì vậy việc biết đƣợc x đủ để
xác thực đó là U.
B. Bài tốn phân tích một số ngun lớn ra các thừa số
ngun tố
Bài tố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 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;
- Từ p và q dễ dàng tính đƣợc: n  p  q ;
- Từ n rất khó tìm đƣợc p và q.
Trong hệ mật RSA, bài tốn phân tích số đƣợc sử dụng
làm cơ sở để hình thành cặp khóa cơng khai/bí mật. Với
việc giữ bí mật các tham số p, q và  n  , có thể tính đƣợc
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.
Hiện tại, các bài tốn trên vẫn đƣợc coi là các bài tốn
khó [4,5] do chƣa có giải thuật thời gian đa thức cho các bài
tố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
giải các bài toán này khi các tham số của nó đƣợc chọn hợp
lý‎.

CÁC BÀI TỐN CƠ SỞ

A. Bài tốn khai căn trên vành số Zn
Cho cặp các số nguyên dƣơng {n,t} với n là tích của hai
số ngun tố p và q, cịn t đƣợc chọn trong khoảng:
1 < t < (p1).(q1). Khi này bài toán khai căn trên vành số
nguyên Zn hay cịn gọi là bài tốn RSA(n,t) đƣợc phát biểu
nhƣ sau:

Bài tốn RSA(n,t): Với mỗi số ngun dương y ℤn*,
hãy tìm x thỏa mãn phương trình sau:

x t mod n  y

(1.2)

(1.1)

Thuật tốn để giải bài tốn RSA(n,t) có thể đƣợc viết
nhƣ một thuật tốn tính hàm RSA(n,t)(.) với biến đầu vào là y
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
HAI BÀI TỐN KHAI CĂN VÀ PHÂN TÍCH SỐ

Chứng minh
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
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
thành chữ k‎ý và phƣơng pháp kiểm tra tính hợp lệ của chữ
ký. Từ dạng tổng quát này, bằng cách lựa chọn các tham số
cụ thể sẽ cho phép tạo ra các lƣợc đồ chữ k‎ý số khác nhau.
1) Phương pháp hình thành tham số và khóa
Dữ liệu vào: p, q, t, x.
Kết quả: n, y.
Các bƣớc thực hiện:
1. Tính modulo n: n  p  q
2. Hình thành khóa công khai:
y  x t mod n

 (k e1 mod n) e2  ( x e1 mod n) e3 mod n  r e2  y e3 mod n

Mệnh đề đã đƣợc chứng minh.
Tính đúng đắn của phƣơng pháp hình thành và kiểm tra
chữ k‎ý có thể chứng minh nhƣ sau:
Đặt: e1  t , e2  f1 (M , r ) , e3  f 2 (M , r ) ta có:

u  s t mod n  s e1 mod n
và:

v  r f1 M ,r   y f2 M ,r  mod n  r e2  y e3 mod n
Theo Mệnh đề 1 suy ra:
uv
B. Lược đồ chữ k‎ý LD-01
Lƣợc đồ thứ nhất - k‎ý hiệu LD 1.01, đƣợc hình thành từ
lƣợc đồ dạng tổng quát với lựa chọn: f1(M,r) = H(M),
f2(M,r) = r.
1) Hình thành tham số và khóa

Thuật tốn 1.1:
Input: p, q, x.
Output: n, t, y, H(.).
[1]. n  p  q

Chú thích:
(i) p, q: các số nguyên tố phân biệt.
(ii) x: khóa bí mật có giá trị trong khoảng: 1  x  n .
(iii) t: số mũ có giá trị trong khoảng:
1  t  ( p  1)  (q  1)

2) Phương pháp hình thành chữ ký
Dữ liệu vào: n, t, x, k, M – thông điệp dữ liệu cần k‎ý.
Kết quả: (r,s) – chữ k‎ý của U lên M.
Các bƣớc thực hiện:
1. Hình thành phần thứ nhất của chữ k‎‎ý:
r  k t mod n ;
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

[2]. select H : 0,1  Z m , m  n ;
[3]. t   n   1
 2 
[4]. y  x t mod n
[5]. return {n,t,y,H(.)};
2) Hình thành chữ k‎ý
Thuật tốn 1.2:
Input: n, t, x, k, M.
Output: (r,s).
[1]. r  k t mod n

[2]. e  H M 
[3]. s  k e  x r mod n
[4]. return (r,s);
3) Kiểm tra chữ k‎ý

Chú thích:
(i) k: khóa bí mật ngắn hạn có giá trị trong khoảng:
1 k  n
(ii) f1 (.), f 2 (.) : các hàm của M và r.
3) Phương pháp kiểm tra chữ ký
Dữ liệu vào: n, t, y, (r,s), M.
Kết quả: Khẳng định (r,s) là chữ k‎ý hợp lệ ((r,s) = true)
hay (r,s) là giả mạo và/hoặc M khơng cịn tồn vẹn
((r,s) = false).
Các bƣớc thực hiện:
1. Tính vế thứ nhất của phƣơng trình kiểm tra:
2. Tính vế thứ hai của phƣơng trình kiểm tra:
v  r f1 M ,r   y f 2 M ,r  mod n
3. Nếu (u = v) thì (r,s) = true , ngƣợc lại thì:
(r,s) = false.
4) Tính đúng đắn của phương pháp hình thành và kiểm
tra chữ k‎ý
Mệnh đề 1:

1  e1 , e2 , e3  ( p  1)  (q  1)

(1.4)
(1.5)
(1.6)


‎Thuật toán 1.3:
Input: n, t, y, M, (r,s).
Output: (r,s) = true / false .
[1]. e  H M 
[2]. u  s t mod n
[3]. v  r e  y r mod n
[4]. if ( u  v ) then {return true ;}
else {return false ;}

u  s t mod n

Cho p, q là 2 số nguyên tố phân biệt,

(1.3)

n  pq ,

4) Tính đúng đắn của lược đồ LD-01
Tính đúng đắn của lƣợc đồ LD 1.01 đƣợc chứng minh

, 1  x, k  n . Nếu: y  x e mod n ,
1

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 
Từ (1.16) và (1.9) suy ra:

(1.16)

ve

u  st mod n  s e1 mod n

Đây là điều cần chứng minh.

và:

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
giá qua các khả năng sau:
- 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ác lƣợc đồ mới đề xuất, có thể thực hiện một số
dạng tấn cơng làm lộ khóa mật (x) và giả mạo chữ k‎ý, từ
khả năng thành công của các dạng tấn cơng này có thể đánh
giá về mức độ an toàn và thiết lập một số điều kiện an toàn
cho các lƣợc đồ mới đề xuất. Phân tích, đánh giá mức độ an
toàn sau đây đƣợc thực hiện cho lƣợc đồ chữ k‎ý LD-02,
việc đánh giá cho lƣợc đồ LD-01 cũng có thể thực hiện theo
cách tƣơng tự.
1) Tấn cơng khóa mật bằng phương pháp “vét cạn”.


v  r e  y r mod n  r e2  y e3 mod n

Theo Mệnh đề 1, suy ra: u  v .
Đây là điều cần chứng minh.
C. Lược đồ chữ ký LD–02
Lƣợc đồ thứ hai - k‎ý hiệu LD-02, đƣợc hình thành từ
lƣợc đồ dạng tổng quát với lựa chọn:
f1(M,r) = 1,
f2(M,r) = H(r||M)).
1) Hình thành tham số và khóa
Thuật toán 1.4:
Input: p, q, x.
Output: n, t, y, H(.).
[1]. n  p  q
[2]. select H : 0,1  Z m , m  n ;

Thuật toán 1.7:
Input: n, t, y.
Output: x – khóa bí mật của đối tƣợng k‎ý.
[1]. for i = 1 to n do
[1.1]. z  i t mod n ;
[1.2]. if ( z  y ) then { x  i ; break;}
[2]. return (x);

[3]. t   m   1
 
2

[4]. y  x t mod n

(1.7)
[5]. return {n,t,y,H(.)};
2) Hình thành chữ k‎ý
Thuật tốn 1.5:
Input: n, t, x, k, M.
Output: (e,s).
[1]. r  k t mod n
(1.8)
[2]. e  H r || M 
(1.9)
[3]. s  k  x e mod n
(1.10)
[4]. return (e,s);
3) Kiểm tra chữ k‎ý
‎Thuật toán 1.6:
Input: n, t, y, M, (e,s).
Output: (e,s) = true / false .
[1]. u  s t  y e mod n
(1.11)
[2]. v  H u || M 
(1.12)
[3]. if ( v  e ) then {return true ;}
else {return false ;}

Nhận xét: Nếu giá trị của x khơng đủ lớn thì việc tấn
cơng làm lộ khóa mật bằng Thuật tốn 1.7 là hồn tồn có
thể thực hiện đƣợc.
Điều kiện 1.1: Khóa bí mật x phải được chọn để việc
tính: x = RSA(n,t)(y) là khó.
2) Tấn cơng khóa mật khi giá trị của k bị lộ.

Thuật toán 1.8:
Input: n, t, (e,s), k, gcd(k , n)  1 , gcd(e,t )  1 .
Output: x – khóa bí mật của đối tƣợng k‎ý.
[1]. w  s  k 1 mod n ;
[2]. Euclid (e,t; a,b): a.e  b.(t )  1
[3]. z  wa  y b mod n ;
[4]. return (z);
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à
a, b là nghiệm.
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
bằng Thuật tốn 1.8 là có thể thực hiện đƣợc. Thật vậy, với
giả thiết: gcd(ki , n)  1 và gcd(e,t )  1 , khi đó:

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
nhƣ sau:
Đặt: t  e1 , 1  e2 , e  e3 . Từ (1.7), (1.8), (1.9), (1.10)
và Mệnh đề 1.1 ta có:
s t mod n  r  y  e mod n
Từ (1.13) suy ra:
r  s t  y e mod n
Từ (1.11) và (1.14) ta có:
ur
Thay (1.15) vào (1.12), ta đƣợc:

(1.13)

w  s  k 1 mod n  k  x e  k 1 mod n

 x e mod n

(1.14)

Giải: a.e  b.(t )  1 bằng thuật toán Euclid mở rộng
đƣợc a và b, ta có:

(1.15)

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 tốn 1.9 là hồn tồn có thể thực hiện
đƣợc. Thật vậy:

a .e b.(  t )

x
mod n  x
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
tính khóa mật (x) là hồn tồ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: k = RSA(n,t)(r) là khó.
3) Tấn cơng khóa mật khi giá trị của k bị sử dụng lặp
lại.

Thuật toán 1.8:
Input: (e1,s1), (e2,s2), k1  k2 , gcd((e1  e2 ),t )  1 ,
gcd(s2 , n)  1
Output: x – khóa bí mật của ngƣời k‎ý.
[1]. w  s1  s2 1 mod n ;
[2]. Euclid (e1,e2,t; a,b): a.e1  e2   b.(t )  1 ;
[3]. z  wa  y b mod n ;
[4]. return (z);
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 tốn 1.8 là có thể thực
hiện đƣợc. Thật vậy, giả sử: r1  k1 t mod n , e1  H r1 || M1  ,
s1  k1  x e1 mod n là chữ k‎‎ý tƣơng ứng với thông điệp M 1
và r2  k 2 t mod n , e2  H r2 || M 2  , s2  k 2  x e mod n là
chữ k‎‎ý tƣơng ứng với thông điệp M 2 . Với giả thiết:
k1  k 2  k , gcd((e1  e2 ),t )  1 và gcd(s2 , n)  1 , khi đó:





e2



 y e mod n



5) Tấn công giả mạo chữ k‎ý nếu biết {p, q}.
Thuật toán 1.10:

Input: n, p, q, t, M, k*, y – khóa cơng khai của U.
Output: (e*, s*) – chữ k‎ý của U do U* tạo ra.
[1]. r*  k *t mod n ;
[2]. e*  H r* || M mod n ;

[3]. s*  k *  y e*.t mod( p1).(q1)  mod n
(1.18)
[4]. return (e*, s*) ;
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*)
bằng Thuật tốn 1.10 là có thể thực hiện. Trong trƣờng hợp
 1
này, kẻ giả mạo (U*) có thể tính: e .t mod( p  1).(q  1) thay
cho việc tính  e *  và kết quả (e*, s*) vẫn đƣợc công nhận là
1

 k 1 mod n

 t 

 x e1e2  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 tốn phân tích
một số nguyên lớn ra các thừa số nguyên tố là khó giải.
Trong ứng dụng thực tế, các tham số {p,q} có thể chọn
theo Chuẩn X9.31 hay FIPS 186-3 của Hoa Kỳ cho hệ mật
RSA nhƣ sau:
Chuẩn X9.31.

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:
- Độ dài modulo n (nlen) là: 1024+256s (s ≥ 0).

z  w   y  mod n
a

 e 
 .t
 t 

Điều kiện 1.4: Cần chọn t   m   1
2

w  s1  s21 mod n
e

  y

mod n  k

 t

 r   y e  y e mod n  r 
Do đó:
v  H (u  || M )  H (r  || M )  e
Nhƣ vậy, chữ k‎ý giả mạo (e*, s*) do U* tạo ra nhƣng
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 tốn 1.16) do đó sẽ đƣợc cơng nhận là chữ k‎ý hợp lệ
của đối tƣợng U (chủ thể của khóa công khai y).


2

 x  1  k  x 

   y

u  s

e

 t

b

 x a.e1 e2 b.( t ) mod n  x
Nhƣ vậy, việc tấn cơng khóa mật (x) có thể thành cơng
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.
Điều kiện 1.3: Giá trị của k không được phép lặp lại ở
các lần k‎ý khác nhau.
4) Tấn công giả mạo chữ k‎ý khi lựa chọn tham số t
khơng hợp l‎ý.
Thuật tốn 1.9:
Input: n, t, M, k*, y – khóa cơng khai của U.
Output: (e*, s*) – chữ k‎ý của U do đối tƣợng giả
mạo U* tạo ra.
[1]. r*  k *t mod n ;
[2]. e*  H r* || M mod n ;


-

2 2

511+128s

≤ p, q ≤ 2

412+128s

511+128s

(s ≥ 0).

|p – q| > 2
(s ≥ 0).
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
các thông số kỹ thuật đƣợc cho trong Bảng 2.1
dƣới đây:
Bảng 2.1: Tiêu chuẩn an toàn đối với các số nguyên tố
bổ trợ.
nlen
Độ dài tối thiểu Độ dài tối
của p1, p2 và q1, đa của p1, p2
q2
và q1, q2
1024 + 256.s > 100 bit
≤ 120 bit
-


 e 
 

[3]. s*  k *  y  t  mod n ;
(1.17)
[4]. return (e*, s*) ;
Nhận xét: Nếu  e *  cho kết quả là một giá trị nguyên
 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ả
mạo chữ k‎ý nếu tn thủ các điều kiện an toàn đã đƣợc chỉ
ra.

Chuẩn FIPS 186-3.
Theo FIPS 186-3, tiêu chuẩn đối với các tham số {p,q}
của hệ mật RSA bao gồm:
-

2 2

511+128s


≤ p, q ≤ 2

511+128s

IV.

(s ≥ 0).

Bài báo đề xuất một dạng lƣợc đồ chữ k‎‎ý số mới xây
dựng dựa trên các bài toán phân tích số, khai căn trên vành
Zn. Từ dạng lƣợc đồ mới đề xuất đã xây dựng đƣợc một số
lƣợc đồ chữ k‎ý số cụ thể cho mục đích ứng dụng. Mức độ an
toàn của các lƣợc đồ mới đề xuất đƣợc đánh giá qua một số
dạng tấn công đã đƣợc biết đến trong thực tế, cho thấy các
lƣợc đồ mới này có thể sử dụng cho các ứng dụng thực tế
nếu các tham số hệ thống đƣợc lựa chọn hợp l‎ý. Tuy nhiên,
để sử dụng đƣợc trong thực tế, các lƣợc đồ này cần đƣợc cải
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.

 nlen 

 100
 2 

|p – q| > 2
.
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
các thông số kỹ thuật đƣợc cho trong Bảng 2.2

dƣới đây:
Bảng 2.2: Tiêu chuẩn an toàn đối với các số nguyên tố
bổ trợ.
Độ dài Độ dài tối Độ dài tối đa của
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ố
(nlen)
nguyên tố nguyên tố
xác xuất
chứng
minh được
1024 bit > 100 bit
< 496 bit
< 239 bit
2048 bit > 140 bit
< 1007 bit < 494 bit
3072 bit > 170 bit
< 1518 bit < 750 bit
-

KẾT LUẬN

TÀI LIỆU THAM KHẢO

[1]

[2]

[3]

Những phân tích trên đây cho thấy, mức độ an toàn của
lƣợc đồ mới đề xuất phụ thuộc vào mức độ khó của 2 bài
tốn: Bài tốn phân tích số ngun lớn ra các thừa số
ngun tố và Bài toán khai căn trên vành số nguyên Zn=p.q, ở
đây p và q là các số nguyên tố phân biệt. Lƣợc đồ sẽ an toàn

[4]
[5]

25

R.L. Rivest, A. Shamir, and L. Adleman, “A method for
Obtaining digital signatures and public key cryptosystems”,
Commun. of the ACM, 21:120-126,1978.
Burt Kaliski, “RSA Digital Signature Standards“, RSA
Laboratories 23rd National Information Systems Security
Conference, October 16-19,2000.
National Institute of Standards and Technology, NIST FIPS
PUB 186-3. Digital Signature Standard, U.S. Department of
Commerce,1994.
A. Menezes, P. van Oorschot, and S. Vanstone, “Handbook of
Applied Cryptography”, CRC Press, 1996.
D.R Stinson, Cryptography: Theory and Practice, CRC Press
1995.