Thuật toán chữ ký số xây dựng trên bài toán logarit rời rạc kết hợp khai căn

Công nghthông tin & Cơ stoán hc cho tin hc  
THUT TOÁN CHKÝ SXÂY DNG TRÊN BÀI TOÁN  
LOGARIT RI RC KT HP KHAI CĂN  
Nguyn Đức Thy1, Lưu Hng Dũng2  
Tóm tt:  
Bài báo đề xut xây dng lược đồ chký sda trên tính khó ca bài toán logarit  
ri rc kết hp khai căn trên Zp . Bài toán logarit ri rc kết hp khai căn được đề xut ở  
đây là mt dng bài toán khó mi thuc lp các bài toán chưa có cách gii vmt toán  
hc. Phương pháp xây dng lược đồ chký sda trên tính khó ca bài toán logarit ri  
rc kết hp khai căn này cho phép nâng cao độ an toàn ca thut toán. Ngoài ra, phương  
pháp xây dng lược đồ chở đây có tháp dng để phát trin mt lp thut toán chữ  
ký smi phù hp vi các ng dng yêu cu cao về độ an toàn trong thc tế.  
Tkhóa: Chký s; Thut toán chký s; Lược đồ chký s; Bài toán Logarit ri rc; Bài toán khai căn.  
1. ĐẶT VN ĐỀ  
Chký shin nay đã được ng dng rng rãi trong các lĩnh vc như Chính  
phủ đin t, Thương mi đin t,… hay trong các hthng vin thông và mng  
máy tính. Tuy nhiên, vic nghiên cu, phát trin các lược đồ chký smi cho  
mc đích thiết kế - chế to các sn phm, thiết ban toàn và bo mt thông tin  
trong nước vn luôn là vn đề cn thiết được đặt ra. Trong [1] đã đề xut mt  
phương pháp xây dng thut toán chký sda trên tính khó ca vic gii bài  
toán logarit ri rc trên Zp [2]. Ưu đim ca phương pháp mi đề xut là từ đó có  
thtrin khai mt lp thut toán chký scho các ng dng khác nhau. Tuy  
nhiên, độ an toàn ca các thut toán chđược xây dng theo phương pháp này  
chỉ được đảm bo bi độ khó ca vic gii bài toán logarit ri rc – DLP (Discrete  
Logarithm Problem) trên Zp. Do đó, nếu có mt gii thut thi gian đa thc cho bài  
toán này (DLP) thì tính an toàn ca các thut toán sbphá vhoàn toàn. Nâng  
cao độ an toàn cho các thut toán chký sda trên tính khó ca vic gii đồng  
thi 2 bài toán khó là mt hướng tiếp cn đang nhn được nhiu squan tâm ca  
các nhà nghiên cu, trong [3 13] các tác giả đã đề xut mt sthut toán chký  
xây dng trên đồng thi hai bài toán phân tích svà logarit ri rc. Trong bài báo  
này, cũng vi mc đích nâng cao độ an toàn cho các thut toán chký s, nhóm  
tác gitiếp tc phát trin phương pháp đề xut trong [1] trên cơ stính khó gii  
ca mt bài toán mi, ở đây được gi là bài toán logarit ri rc kết hp khai căn  
trên Zp, ký hiu: DLRP (Discrete Logarithm combining Finding Root Problem).  
Đây là mt dng bài toán khó ln đầu được đề xut và ng dng cho vic xây dng  
thut toán chký svà có nhiu trin vng cho phép xây dng các thut toán phù  
hp vi các ng dng thc tế đòi hi độ an toàn cao.  
2. BÀI TOÁN KHÓ MI VÀ PHƯƠNG PHÁP XÂY DNG THUT TOÁN  
CHKÝ SỐ  
2.1. Bài toán logarit ri rc kết hp khai căn trên Zp  
Bài toán được đề xut ở đây là mt dng bài toán khó mi và được gi là Bài  
toán logarit ri rc kết hp khai căn trên trường Zp, dng thnht ca bài toán này  
có thphát biu như sau:  
192  
N.Đ. Thy, L.H. Dũng “Thut toán chký sxây dng trên … kết hp khai căn”  
Nghiên cu khoa hc công nghệ  
Cho 2 snguyên tp, q tha mãn điu kin: q|(p-1), vi mi snguyên dương  
* , hãy tìm các sx1 và x2 tha mãn phương trình sau:  
yZ p  
(
)
x1 )  
1 .x2  
(
x1  
mod q mod p = y  
Dng thhai ca bài toán logarit ri rc kết hp khai căn có thể được phát biu  
như sau:  
Cho snguyên tp, vi mi cp snguyên dương a,bZ*p , hãy tìm sx tha  
mãn phương trình sau:  
x
)
(
a
(
x
)
b mod p  
Trong toán hc, bài toán trên thuc lp các bài toán chưa có cách gii, các gii  
thut cho bài toán logarit ri rc – DLP (Discrete Logarithm Problem) hay bài toán  
khai căn – FRP (Finding Root Problem) trên Zp hin ti là không áp dng được vi  
DLRP.  
2.2. Xây dng lược đồ chký da trên tính khó ca bài toán mi đề xut  
2.2.1. Thut toán sinh khóa  
phương pháp xây dng thut toán chmi đề xut, bài toán DLRP được  
sdng để hình thành cp khóa bí mt và công khai ca các đối tượng ký. Trong  
đó, p là tham shthng (tham smin) do nhà cung cp dch vto ra, ở đây p là  
snguyên tcn phi được chn sao cho vic gii bài toán DLP là khó. Các tham  
s(x1, x2, q) là khóa bí mt và y là khóa công khai tương ng ca mi đối tượng ký  
trong hthng. Để to khóa x1 mi thc thký cn to trước snguyên tq tha  
mãn: q|(p – 1) và mt số  
p1  
* . Khóa x1 được to theo:  
Zp  
α
q
x1 =  
α
mod p  
Khóa x2 là mt giá trị được chn ngu nhiên trong khong (1, q). Sau đó, khóa  
công khai được to ra t(x1, x2, q) theo (1):  
(
x1 )  
1 ×x2  
modq mod p  
(1)  
y =  
Thut toán sinh khóa có thể được mô tli như trên Bng 1 sau đây:  
Bng 1. Thut toán sinh tham svà khóa  
input: lp, lq – độ dài (tính theo bit) ca các snguyên tp,q.  
(
x1  
)
output: p,q, x1, x2, y.  
[1]. generate p,q: len(p) = lp, len(q) = lq, q|(p-1)  
[2]. select α: 1 <  
α
< p  
x1 α ( / q mod p  
p1  
)
[3].  
[4]. if (x1 = 1) then goto [2]  
[5]. select x2: 1 < x2 < q  
1  
(x1 )  
2
[6].  
y x1  
( )  
.x modq mod p  
[7]. return {p,q, x1,x2,y}  
Chú thích:  
- len(.) : Hàm tính độ dài (theo bit) ca mt snguyên.  
- p: Tham shthng/tham smin.  
Tp chí Nghiên cu KH&CN quân s, S66, 04 – 2020  
193  
Công nghthông tin & Cơ stoán hc cho tin hc  
- q, x1, x2: Khóa bí mt.  
- y: Khóa công khai ca đối tượng ký.  
2.2.2. Thut toán ký  
Gis(R,S) là chký lên bn tin M, u là 1 giá trtrong khong (1,q) và R  
được tính tu theo công thc:  
R = (x1 )  
u mod p  
(2)  
Và S được tính tv theo công thc:  
S = x1  
( )  
v mod p  
(3)  
(4)  
Ở đây: v cũng là 1 giá trtrong khong (1,q).  
Cũng githiết rng phương trình kim tra ca lược đồ có dng:  
E
y
S R × y  
( ) ( ) ( )  
R×S mod p mod p  
Vi:  
R× S mod p = (x1 )  
k mod p  
và:  
E = H(M)  
*
k Zq  
Trong đó: H(.) là hàm băm và  
.
Đặt:  
k
(5)  
(6)  
x1 mod p = Z  
( )  
Khi đó có thể đưa phương trình kim tra vdng:  
E
y
(S) (R) ×(y)  
Z mod p  
T(1), (2), (3) và (6) ta có:  
v.E  
u.y  
)
(x1 )  
1.x2 .Z  
(7)  
(
x1  
T(7) suy ra:  
v × E u × y + x1 × x2 × Z  
Nên:  
v = E1 ×  
Mt khác, t(2), (3) và (4) ta có:  
)
(
x1  
×
(
x1  
)
mod p  
(
)
mod q  
1 × x2 × Z  
modq  
)
(8)  
(
u × y +  
(
x1  
)
(9)  
(v + u)mod q = k  
T(8) và (9) ta có:  
k = u + E1  
×
(
u × y +  
(
x1  
)
1 × x2 × Z  
)
mod q  
(10)  
T(10), suy ra:  
(11)  
u =  
(
k −  
(
x1  
)
1 × x2 × Z × E1  
)
×
(
E1 × y +1  
)
1 modq  
T(11) và (8), có thtính thành phn thnht ca chký theo (2):  
R = x1  
( )  
u mod p  
và thành phn th2 theo (3):  
S = x1  
v mod p  
(
)
Từ đây thut toán ký được mô ttrên Bng 2 như sau:  
Bng 2. Thut toán ký  
input: p, q, x1, x2, y, M.  
output: (R,S).  
[1].  
E H(M )  
[2]. select k: 1 < k < q  
194  
N.Đ. Thy, L.H. Dũng “Thut toán chký sxây dng trên … kết hp khai căn”  
Nghiên cu khoa hc công nghệ  
k
[3].  
Z ←  
u ←  
(
x1  
)
mod p  
x1  
1 × x2 × Z × E1  
u × y +  
u mod p  
v mod p  
(
k −  
(
)
)
×
(
)
E1 × y +1  
modq  
)
1 mod q  
[4].  
[5].  
[6].  
[7].  
)
v E×  
(
(
x1  
1 × x2 × Z  
1
R  
S  
(
x1  
)
(
x1  
)
[8]. return (R,S)  
Chú thích:  
M {0,1}∞  
- M: b  
- (R,S): ch  
2.2.3. Thu t toán ki  
Thu t toán ki m tra c  
n tin c  
ký c  
m tra ch  
a lượ  
n ký, v  
lên M.  
ký  
i:  
.
a U  
c
đồ được githiết là:  
S R × y  
( ) ( ) ( )  
R×S mod p mod p  
E
y
Ở đây, E là giá trị đại di  
ký (R,S) th a mãn đẳng th  
xác th c v ngu n g c và tính toàn v  
n tin b ph nh n v ngu n g c và tính toàn v  
m tra được tính theo:  
n c  
c trên thì ch  
n. Ngược l  
a b  
n tin c  
n th  
m tra: E = H(M ). N  
p l và b n tin sẽ đượ  
ký b coi là gi o và  
ó, n u v trái c  
ếu M và chữ  
được coi là h  
đ
c
i, thì ch  
mạ  
b
th  
n. Do  
ế
ế
a
đẳng  
c ki  
A = S  
( )  
E mod p  
(12)  
và v  
ế
phi được tính theo:  
y
Z
(13)  
(14)  
B =  
(
R
)
×
(
y
)
mod p  
ở đây:  
Thì  
Khi  
sau:  
Z = R × S mod p  
đ
i
u ki  
ó, thu  
n chữ  
t toán ki  
ký h  
p l  
m tra c  
là: A = B  
a lượ  
đ
c
đồ  
m
i
đề xu  
t  
được mô t  
trong B  
ng 3  
nh  
ư
Bng 3. Thu  
t toán ki  
m tra  
input: p, y, M, (R,S).  
output: TRUE / FALSE.  
[1].  
[2].  
[3].  
[4].  
E H(M)  
A  
E mod p  
(S)  
Z R × S mod p  
y
B ←  
(
R
)
×
(
y
)
Z modp  
[5]. if (A = B) then  
else return FALSE}  
Chú thích:  
{return TRUE}  
{
- M, (R,S): b  
- N u k t qu  
kh ng định. Ngược l  
và tính toàn v n.  
n tin, ch  
ký c  
là TRUE thì tính toàn v  
i, n u k t qu là FALSE thì M b  
n thm tra.  
ế
ế
tr  
v
n và ngu  
n g  
nh  
c c  
a M đượ  
c
c
ế
ế
ph  
n v  
ngun g  
Tp chí Nghiên cu KH&CN quân s, S66, 04 – 2020  
195  
Công nghthông tin & Cơ stoán hc cho tin hc  
đề xu  
ng minh ở đây là: Cho p, q là 2 s  
2.2.4. Tính  
u c  
đ
úng đắn c  
a lượ  
c
đồ  
m
i  
t  
Đi  
n ch  
nguyên t  
v
i q|(p-1),  
1< x2 < q  
0,1 ∗  
}
a Zn  
1  
x1 = α (  
q mod p  
p
1 /  
)
H :  
{
,
| q || n |<| p |  
,
1 <  
α
< p ,  
,
,
(
x1  
)
.
x2 mod  
k
,
,
1 < k < p ,  
,
,
,
(
)
y =  
u =  
R =  
B =  
(
x1  
k −  
x1  
u mod p  
)
q mod p  
E = H  
M
Z = x1 mod p  
( )  
1 ×x2 ×Z  
)
1
,
(
(
(
x1  
)
1 × x2 × Z × E1  
)
(
×
(
E1 × y +1 1  
)
modq  
v = E×  
(
u× y +  
(
x
)
modq  
mod p  
1
E
)
v
)
,
.
N
ếu:  
,
Z = R× S mod p  
A =  
(
S
)
S =  
x1  
mod p  
y
Z
thì: A = B.  
(
Tính  
R
)
×
(
y
)
mod p  
đ
úng đắn c  
a thu  
t toán m  
i
đề xu  
t được chng minh như sau:  
T
(3), (8) và (12) ta có:  
E mod p =  
1  
)
1.x2.Z  
A =  
(
S
)
(
x1  
)
v.E mod p =  
(
x1  
.E mod p  
)
(
)
E
.
(
u.y+  
(
x1  
)
(15)  
(
u.y+(x1 )  
1.x2.Z  
= x1  
( )  
) mod p  
Vi:  
1
k mod p  
và :  
Z = (x1 )  
)
1
1
1
u =  
(
k −  
(
x1  
× x2 × Z × E−  
)
×
(
E× y +1  
)
modq  
T(2), (3), (5), (8), (11) và (14) ta li có:  
Z = R× S mod p = x1 × x1 x1  
v mod p = u+v mod p  
( ) ( ) ( )  
u
1  
)
1  
u+u.  
)
(
E
)
1.y+  
(
E
.(  
x1  
)
1.x2.Z  
u.  
)
(
E
1.y+1 1.x2.Z  
)
+(E) .(x1 )  
(16)  
(17)  
=
=
(
x1  
mod p =  
1  
(
x1  
mod p  
mod p = (x1 )  
k mod p = Z  
1  
(k−  
(
x1  
)
1.x2.  
(
E
)
1.Z  
).  
((  
E
)
1.y+1  
)
.
((  
E
)
1.y+1 1.x2.Z  
+(E) .(x1 )  
)
(
x1  
)
Thay (1), (2), (5) và (16) vào (13) ta được:  
1  
(x1 )  
y
Z
u.y  
B =  
(
R
)
×
(
y
)
mod p =  
) mod p  
(
x1  
)
×
(
x1  
)
.x .Z mod p  
2
(
u.y+(x1 )  
1.x2.Z  
= x1  
( )  
T
(15) và (17) suy ra  
2.2.5. M độ an toàn c a thu  
độ an toàn c a lượ  
ng t n công nh  
n công khóa bí m  
ượ đồ đề xu  
để hình thành ch ký. Vì th  
, nói cách khác là k n công ph  
t h p khai c n và bài toán tìm b  
a lượ đồ đề xu t xét theo kh  
ánh giá b ng m độ khó c a vi c gi  
ng bài toán khó m i, mà ngay c  
ng không có ngh  
n công gi o ch ký  
thu t toán ki m tra (B ng 3) c  
(R,S) gi o sẽ được công nh  
u ki  
đ
i
u c  
n ch  
ng minh: A = B.  
đề xu  
đề xu t có thể đánh giá qua kh  
c
t toán đượ  
c
t  
M
t s  
c
c
đồ  
m
i
n
ă
ng ch  
ng  
l
i m  
d
ư:  
- T  
t  
l
c
m
i
t, các tham s  
(x1,x2,q) cùng được s  
đồ ch phá v u c  
i gi đượ đồng th i bài toán logarit r  
a ph n t trên Zp. Do ó, m độ an toàn  
ng ch ng t n công làm l khóa bí m đượ  
được các bài toán. C n chú ý, DLRP là  
khi có các gi i thu t th i gian a th c cho  
gi được bài toán này.  
d
ng làm khóa bí  
3 tham s này cùng  
i r  
m
b
k
c
đ
l
t
ế
, lượ  
c
b
n
ế
ế
t
i  
c
ờ ạc  
ă
c c  
đ
c  
c
m
i
n
ă
t  
c
c
i  
m
t d  
đ
FRP và DLP c  
ũ
ĩ
a là s  
i  
- T  
m
T
m
a thu  
ký h  
t toán m  
p l i m  
i
đề xu  
t cho th  
t b n tin M n  
y, m  
t cp  
n:  
n là ch  
v
ếu th  
a mãn  
đ
i
S R × y  
( ) ( ) ( )  
R.S modp modp  
E
y
(18)  
196  
N.Đ. Thy, L.H. Dũng “Thut toán chký sxây dng trên … kết hp khai căn  
Nghiên cu khoa hc công nghệ  
(18), n u ch n trước R r  
T
ế
i tính S thì khi  
đ
ó
đ
i
u ki  
n (18) s  
tr  
ng th  
có d  
thành:  
hai c  
ng:  
E
S a  
( ) ( )  
S mod p  
(19)  
(20)  
Còn n  
ế
u ch  
n trước S r  
i tính R thì khi  
đ
ó
đ
i
u ki n (18) s  
y
R
R b mod p  
( ) ( )  
V
i a và b là h  
ng s  
toán logarit r i r c k  
, d y r  
th  
ng (19) và (20) chính là d  
a bài  
ế
t h  
p khai căn trên Zp.  
4. KT LUN  
Bài báo đề xut xây dng lược đồ chký stheo mt phương pháp mi da  
trên tính khó gii ca bài toán logarit ri rc kết hp khai căn trên Zp. Mc độ an  
toàn ca thut toán xây dng theo phương pháp này được đảm bo bng mc độ  
khó ca vic gii bài toán trên. Ở đây, bài toán logarit ri rc kết hp khai căn trên  
Zp là mt dng bài toán khó mi, ln đầu được đề xut và ng dng trong vic xây  
dng thut toán chký s. Tphương pháp mi đề xut có thxây dng mt lp  
thut toán chký sđộ an toàn cao cho các ng dng trong thc tế.  
.
TÀI LIU THAM KHO  
[1] Nguyen Duc Thuy and Luu Hong Dung, December 2016, “A New Construction Method of  
Digital Signature Algorithms”, IJCSNS International Journal of Computer Science and Network  
Security. Vol. 16 No. 12 pp. 53-57, ISSN: 1738 - 7906.  
[2] T. ElGamal (1985). “A public key cryptosystem and a signature scheme based on discrete  
logarithms”. IEEE Transactions on Information Theory. Vol. IT-31, No. 4. pp.469–472.  
[3] Q. X. WU, Y. X. Yang and Z. M. HU, January 2001, "New signature schemes based on  
discrete logarithms and factoring", Journal of Beijing University of Posts and  
Telecommunications, vol. 24, pp. 61-65.  
[4] Z. Y. Shen and X. Y. Yu, June 2004, "Digital signature scheme based on discrete logarithms  
and factoring", Information Technology, vol. 28,pp. 21-22.  
[5] Shimin Wei, December 2007, “Digital Signature Scheme Based on Two Hard Problems”,  
IJCSNS International Journal of Computer Science and Network Security, VOL.7 No.12, ISSN:  
1738 - 7906.  
[6] Eddie Shahrie Ismail, Tahat N.M.F., Rokiah. R. Ahmad, 04/2008, “A New Digital Signature  
Scheme Based on Factoring and Discrete Logarithms”, Journal of Mathematics and Statistics;  
12(3). DOI: 10.3844/jmssp.2008.222.225 Source:DOAJ.  
[7] Qin Yanlin , Wu Xiaoping, 8-11 Aug. 2009, “ New Digital Signature Scheme Based on both  
ECDLP and IFP”, Computer Science and Information Technology, 2009. ICCSIT 2009. 2nd  
IEEE International Conference on, pp 348 – 351, E-ISBN : 978-1-4244-4520-2.  
[8] Swati Verma1, Birendra Kumar Sharma, 2011, “A New Digital Signature Scheme Based on  
Two Hard Problems”, International Journal of Pure and Applied Sciences and Technology, Int.  
J. Pure Appl. Sci. Technol, no.5(2), pp. 55-59, ISSN 2229 – 6107.  
[9] Sushila Vishnoi , Vishal Shrivastava, 2012, ”A new Digital Signature Algorithm based on  
Factorization and Discrete Logarithm problem”, International Journal of Computer Trends and  
Technology, volume 3, Issue 4.  
[10] A.N. Berezin, N.A. Moldovyan, V.A. Shcherbacov, 2013, "Cryptoschemes Based on  
Difficulty of Simultaneous Solving Two Different Difficult Problems", Computer Science Journal  
of Moldova, vol.21, no.2(62).  
[11] Phm Văn Hip, Nguyn Hu Mng, Lưu Hng Dũng, “Mt thut toán chký xây dng da  
trên tính khó ca vic gii đồng thi hai bài toán phân tích svà logarit ri rc“, Tp chí Khoa  
Tp chí Nghiên cu KH&CN quân s, S66, 04 – 2020  
197  
Công nghthông tin & Cơ stoán hc cho tin hc  
hc và Công nghệ Đi hc Đà Nng, s7(128). 2018, ISSN: 1859 – 1531.  
[12] Phm văn Hip, Lưu Hng Dũng, “Chký stp thvà mô hình ng dng“, Tp chí Nghiên  
cu KH và CN Quân s, số Đặc san CNTT, 11 – 2018, ISSN: 1859 – 1043.  
[13] Nguyn Vĩnh Thái, Lưu Hng Dũng, “Mt lược đồ chký xây dng trên tính khó ca vic  
gii đồng thi 2 bài toán phân tích svà logarit ri rc trên Zp“, Tp chí Nghiên cu KH và  
CN Quân s, số Đc san CNTT, 04 – 2019, ISSN: 1859 – 1043.  
ABSTRACT  
A NEW DIGITAL SIGNATURE ALGORITHM BASED ON DISCRETE  
LOGARIT COMBINING FINDING ROOT PROBLEM  
The paper proposes to build a digital signature schema based on the difficulty  
of the discrete logarithm combining finding root problem on Zp. This problem is a  
new difficult problem type of the problems class without mathematical solution.  
Building a digital signature scheme based on the difficulty of the discrete  
logarithm combining finding root problem allows to improve the security of the  
algorithm. In addition, the signature schema construction method here can be  
applied to develop a new digital signature algorithm layer that is suitable for  
applications that require high levels of security in practice.  
Keywords: Digital Signature; Digital Signature Algorithm; Digital Signature Schema; Discrete Logarithm  
problem; Finding Root Problem.  
Nhn bài ngày 07 tháng 11 năm 2019  
Hoàn thin ngày 08 tháng 12 năm 2019  
Chp nhn đăng ngày 10 tháng 04 năm 2020  
Địa ch: 1 Khoa CNTT, Cao đẳng Kinh tế - Kthut TP. HChí Minh.  
2 Khoa CNTT, Hc vin KTQS.  
*
Email: luuhongdung@gmail.com.  
198  
N.Đ. Thy, L.H. Dũng “Thut toán chký sxây dng trên … kết hp khai căn”  
pdf 7 trang baolam 10/05/2022 3340
Bạn đang xem tài liệu "Thuật toán chữ ký số xây dựng trên bài toán logarit rời rạc kết hợp khai căn", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfthuat_toan_chu_ky_so_xay_dung_tren_bai_toan_logarit_roi_rac.pdf