Luận án Nghiên cứu phát triển một số lược đồ chữ ký số mù, chữ ký số tập thể mù dựa trên các chuẩn chữ ký số

ỢC ĐỒ EC-SCHNORR 
 Ưu điểm của hệ mật ECC so với các hệ mật khóa công khai khác là ECC cung 
cấp các thuộc tính an toàn có thể so sánh với các hệ mật khóa công khai truyền 
thống mặc dù độ dài khóa nhỏ hơn gấp nhiều lần. Do đó, việc cài đặt ECC tiêu tốn 
ít tài nguyên hệ thống và năng lượng hơn. Do lợi thế về độ dài khóa nhỏ, ECC đã 
được áp dụng rộng rãi trong nhiều lĩnh vực. 
 Trong phần này đề xuất 2 lược đồ chữ ký số tập thể mù dựa trên chuẩn GOST 
R34.10-2012 và lược đồ EC-Schnorr. Sau đó so sánh với một số lược đồ đã công 
bố, qua đó đề xuất hướng ứng dụng cho các lược đồ đề xuất. 
 Chuẩn chữ ký số GOST R34.10-2012 và lược đồ EC-Schnorr mô tả các lược 
đồ chữ ký số đơn. Cải tiến ở đây là dựa trên chuẩn và lược đồ phổ biến này, đề xuất 
phương pháp để xây dựng các lược đồ chữ ký số tập thể mù hiệu quả từ chữ ký số 
đơn. Qua đó có thể sử dụng được trong các ứng dụng yêu cầu nhiều người ký (dạng 
chữ ký tập thể) và cần tính ẩn danh (tính mù). Lược đồ đề xuất được mô tả như sau: 
2.2.1. Lược đồ chữ ký số tập thể mù dựa trên chuẩn GOST R34.10-2012 
2.2.1.1. Xây dựng lược đồ 
 Phần này đề xuất lược đồ chữ ký số tập thể mù dựa trên chuẩn GOST R34.10-
2012, được ký hiệu là LĐ 2.03. Lược đồ được trình bày như sau: 
 63 
 1) Cài đặt: Mỗi người ký trong tập thể B tính khóa công khai của mình và gửi 
đến TTP để tính khóa công khai tập thể P như sau: 
 n
 Pii d G ; P P12 P ... Pni  d G với i=1,2,,n 
 i 1
 Mỗi người ký trong B chọn ngẫu nhiên giá trị ki với kZiq và tính Ci sau đó 
 nn
gửi đến TTP để tính C như sau: Cii k G với i=1,2n và C  Cii k G , 
 ii 11
và gửi C đến người yêu cầu A. 
 2) Làm mù: A chọn ngẫu nhiên 2 giá trị , {1,2,...,q 1} và tính: 
 h H M ; e h mod q ; e e mod q
 CCG  
 r x mod q ; r ( r -1 )mod q
 C
 A gửi (,)re tới B. 
 3) Tạo chữ ký: Mỗi người ký trong B tính s và gửi TTP để tính s và gửi tới 
 (,)rs i
 n
A như: si k i e d i rmod q ; s r si mod q . 
 i 1
rr 
 4) Giải mù: Người yêu cầu A tính s: s ( 1 s e )mod q 
 Cặp là chữ ký số tập thể mù của tập thể B trên thông điệp M. 
 5) Kiểm tra chữ ký: Tính C , và so sánh, nếu thì chữ ký được chấp 
nhận, ngược lại thì chữ ký không được chấp nhận, với: 
 -1 -1
 C ( se mod q ) G - ( re mod q ) P và r xC ' mod q 
 Thật vậy, có thể chứng minh như sau: 
 Với si G (( k i e d i r )mod q ) G , tính CCi , như sau: 
 64 
 -1 -1
 CkGsei i ( i mod qGdre ) - ( i mod qG ) ;
 m m m
 -1 -1
 C  Cei ( s i mod qGre ) -  ( d i mod qG ) ;
 i 1 i 1 i 1
 (se-1 mod q ) G - ( re -1 mod q ) P
 Từ: r ( r-1 )mod q r r  -1 mod q , thay vào biểu thức tính C : 
 C ( se-1 mod q ) G - ( re -1 mod q ) P ;
 (( e  s -1 ) e -1 mod q ) G - (( r  -1 e -1 )mod q ) P ;
  ((se-1 mod q ) G - ( re -1 mod q ) P ) ( mod q ) G ;
  CGC 
 Hay rʹ = r, vậy rʹ = r đã được chứng minh hay chữ ký đã được xác thực. 
 Hình 2.3. Tóm tắt thuật toán ký số của LĐ 2.03 
2.2.1.2. Đánh giá tính an toàn của các lược đồ đề xuất 
 1) Tính mù: Các lược đồ chữ ký số tập thể mù đề xuất đảm bảo tính mù. 
 Chứng minh: Sử dụng các điều kiện trong định nghĩa 1.1 của chương 1 để 
chứng minh. 
 65 
 Lấy bộ chữ ký là một trong hai bộ chữ ký 
số được gửi đ(,,)ếMn ngư r sời ký B. Gọi (,,)e r s là dữ liệu được lưu trong các lược đồ chữ 
ký số được phát hành từ B. Sẽ tồn tại hai giá trị ngẫu nhiên α, β liên kết tới 
 . Từ mô tả trong các lược đồ, có các liên kết sau: 
 e emod q , r ( r -1 )mod q và s ( -1 s e )mod q 
 Theo các liên kết trên tính được: ee-1 và  ()s e ee-1 s -1 
 , r
 Thay vừa tính ở trên vào phương trình tính , thu được r như sau: 
 r ( r -1 )mod q r r ( s e ) s -1 mod q (2.7) 
 Từ (2.7) cho thấy là r luôn có mối quan hệ xác định là hằng số và không phụ 
thuộc vào hai hệ số , nên khi chọn với dữ 
liệu lưu trữ trong lược đồ phát hành của B là (,,)ei r i s i (với i=0,1) thì luôn tồn tại 
cặp thỏa mãn điều kiện. 
 Với xác suất lớn nhất lựa chọn đúng đ1ể bʹ = b trong tập ch1ữ ký phát hành lựa 
 Pr[bb ] 
 2 2
chọn là , hay , tức là biểu thức 
 11
Pr[bb ] | 
 2 pc
 là đúng, thỏa mãn điều kiện trong định nghĩa 1.1. Do đó, các 
lược đồ đề xuất là mù vô điều kiện. 
 Hay có thể nói rằng, đối với các lược đồ chữ ký số tập thể mù dựa trên chuẩn 
GOST R34.10-2012, người ký không thể biết nội dung thông điệp vì thông điệp 
được băm ra và kết hợp với các giá trị (,)  được lựa chọn ngẫu nhiên bởi người 
yêu cầu như là h H() M , e hmod q , . Do vậy mà bên ký không thể 
biết nội dung thông đi(ệMp mà ,,) r smình {( Mđã0 ký. ,, r 0 s 0 ),( M 1 ,,)} r 1 s 1
 66 
 2) Tính ch(,,)ốqngh qgi eả q smạo: Lược đồ chữ ký số tập thể mù đề xuất có bộ tham 
số(,,,,) t qh q e q s được gọi là an toàn trong ROM nếu tồn tại -ECDL trong 
trường GF(p), với: 
 Trong đó, lần lượt là số truy vấn của hàm băm, trích xuất xZvà tạoq 
chữ ký mù; E là thời gian thực hiện các phép tính luỹ thừa modulo trong GF(p). 
 Chứng minh: Sử dụng các kết quả trình bày trong định nghĩa 1.2 của chương 
1 để chứng minh. 
 Giả sử là tồn tại một kẻ giả mạo A, xây dựng thuật toán B để giúp A giải bài 
toán logarit rời rạc. B được cho là một nhóm nhân G trong GF(p) với thành phần G, 
số nguyên tố q và điểm Q trên đường cong elliptic. B được yêu cầu tìm giá trị 
 sao cho Q x G . 
 *
 B tiến hành như sau: chọn hàm băm thông điệp eH 0,1 q , gửi các 
tham số công khai (,,,)p G Q e tới A. B chọn hai số ngẫu nhiên (kʹ,dʹ) và tính C*: 
 C* k Q d G (2.8) 
 (,,)M r s
 dʹ được xem như là khoá riêng của người ký, kʹ là giá trị được chọn ngẫu nhiên 
và (kʹ,dʹ,C*) là kết quả đầu ra. A truy vấn tập Oracle của chữ ký số với thông điệp 
M và khoá riêng dʹ. Đầu tiên, B kiểm tra xem d' đã được sử dụng cho truy vấn trong 
các phần cài đặt trước chưa. Nếu dʹ đã được sử dụng rồi thì B lấy bộ (C*,,, k d e) 
(C*,kʹ,dʹ,e) từ bảng được lưu để ký thông điệp M theo pha tạo chữ ký được mô tả 
trong lược đồ. Đầu ra của thuật toán ký là . Nếu dʹ chưa được sử dụng 
trong các phần cài đặt trước thì B thực hiện lại các mô phỏng và chọn lại khoá bí 
mật dʹ cho đến khi thỏa (,)mãn. t 
 qh() q e q s 11 
  (1 )(1 ) ; t t O() qes q E
 q q qh
 67 
 *
 Cuối cùng, A tạo ra chữ ký số giả mạo là s11 (,,) e r s trên M bởi khoá bí mật 
dʹ. B lại thực hiện lần nữa bằng cách giữ nguyên (,)er và lại yêu cầu A ký tiếp và 
 *
thu được s22 ( e , r , s ). 
 Với C* ( se-1 mod q ) G - ( re -1 mod q ) P ; P d G 
 Thay vào (2.8), tính được: 
 * -1 -1
 k Q d G ( sj e mod q ) G - ( re mod q ) P
 * -1 -1 
 k x G d G ( sj e mod q ) G - ( re mod q ) d G 
 * *
 sj e() k x hH d rd 0,1 q
 ()qqes 
 với j=1,2. 
 Thuật toán B chưa biết (,)xr nên để thu được x thì B phải giải phương trình 
tuyến tính có hai ẩn số hoặc phải giải bài toán ECDLP. 1
 .
 q
 Phân tích xác suất: Xác suất thực hiện thành công việch lựa chọn đúng giá trị 
 q
hàm băm là 1 h và được mô phỏng thực hiện trong 
 q
 q q() q q
lần. Ta có (1 h )qqes 1 h e s nên B có thể xác định chính xác điểm 
 qq
nghiêm ngặt để chọn lại giá trị hàm băm là Do tính ngẫu nhiên lý tưởng trong 
 1
ROM nên xác suất tồn tại chữ ký s là . Như vậy, xác suất thành công là 
 q
t t O(). q q E
 q()es q q 11
 (1 h e s )(1 ) , và độ phức tạp về thời gian của thuật toán B dựa 
 q q qh
trên hàm mũ được thực hiện trong pha hình thành khoá và ký, và là 
2.2.2. Lược đồ chữ ký số tập thể mù dựa trên lược đồ EC-Schnorr 
 68 
2.2.2.1. Xây dựng lược đồ chữ ký số 
 Phần này đề xuất lược đồ chữ ký số tập thể mù dựa trên lược đồ EC-Schnorr, 
ký hiệu là LĐ 2.04. Lược đồ được trình bày như sau:n 
 Pii d G P P12 P ... Pni  d G
 i 1
 1) Thiết lập: Mỗi người ký trong tập thể B tính giá trị khóa công khai Pi của 
mình và gửi đến TTP để tính giá trị khóa công khai tkậip thể PkZiq như sau. Ci
 nn
 C ; Cii k G vớCi i=1,2n  Cii k G
 ii 11 
 C
 Mỗi người ký chọn ngẫu nhiên giá trị với và tính sau đó gửi đến 
TTP để tính như: với i=1,2,,n và và gửi 
đến người yêu cầu A. 
 2) Làm mù: A chọn ngẫu nhiên 2 giá trị , {1,2,...,q -1} và tính: 
 CCGP  
 r H( M , x )mod q 
 C s s
 r ( r )mod q i
 n
 Người yêu cầu gửi r tớsi mỗi ngư si modời ký q trong B. 
 i 1
 3) Tạo chữ ký: Mỗi người ký tính và gửi đến TTP để tính và gửi tới A, 
với: si k i d i rmod q ; . 
 4) Giải mù: Người yêu cầu tính s: s ( s )mod q , cặp (r,s) là chữ ký số tập 
thể mù của tập thể người ký lên thông điệp M . 
 5) Kiểm tra chữ ký: Tính các giá trị: C s G r P và r H(,) M xC ' . 
 So sánh: nếu rr thì chữ ký được chấp nhận, ngược lại không chấp nhận. 
 Thật vậy, có thể chứng minh như sau: 
 Với C s G r P 
 69 
 Thay công thức tính s và r ở trên vào, tính được: 
 C ()() s(,,)M  r s G r P
 nn
 ((-))  G P  ki rd i G r d i G
 ii 11
 CGP  
 C
 r H(,) M xC 
 H(,) M xC r
 Vậy rʹ = r đã được chứng minh hay chữ ký đã được xác thực. 
 Hình 2.4. Tóm tắt thuật toán ký số của LĐ 2.04 
2.2.2.2. Đánh giá tính an toàn của các lược đồ đề xuất 
 1) Tính mù: Các lược đồ chữ ký số tập thể mù đề xuất đảm bảo tính mù. 
 Chứng minh: Sử dụng các điều kiện trong định nghĩa 1.1 của chương 1 để 
chứng minh. 
 Lấy bộ chữ ký là một trong hai bộ chữ ký 
số được gửi đến ngườ(iM ký ,,) r B. s Gọ {(i M(,)rs0 ,, r 0 slà 0 ),( d Mữ 1li ,,)}ệ r 1u sđư 1 ợc lưu trong các lược đồ chữ 
ký số được phát hành từ B. Sẽ tồn tại hai giá trị ngẫu nhiên α, β liên kết (,)rs tới 
 . Từ mô tả trong các lược đồ, có các liên kết sau: 
 70 
 r ( r - )mod(,,)qh q q e, qs s ( s )mod q 
 (,,,,) t q q q
 Theoh các e sliên kết trên tính được: ss và  ()rr 
 Thay vừa tính ở trên vào phương trình tính C, tính được: 
 CC  G PCssGrrP()() (2.9) 
 Từ (2.9) có thể nhận thấy là r luôn có mối quan hệ xác định là hằng số với M 
và và không phụ thuộc vào hai hệ số . Do đó mà khi chọn 
 (,,)s r s ,
(M , r , s ) {( M0 , r 0 , s 0 ),( M 1 , r 1 , s 1 )} với dữ liệu lưu trữ trong lược đồ phát hành của B 
là (,)rs thì luôn tồn tại cặp thỏa mãn. 
 Với xác suất lớn nhất lựa chọn đúng để bʹ = b trong tập chữ ký phát hành lựa 
chọn là , hay , tức là biểu thức 
 là đúng, thỏa mãn điều kiện trong định nghĩa 1.1. Do đó, các 
lược đồ đề xuất là mù vô điều kiện. 
 1 1
 Pr[bb ] 
 Do người ký không thể biết nội dung 2thông điệp vì thông2 điệp được băm và 
kết hợp với 11 hoành độ điểm C với r H( M , x )mod q và CCGP  . 
Pr[bb ] | C
 2 pc
Do vậy mà bên ký không thể biết được nội dung thông điệp mà mình đã ký. 
 2) Tính chống giả mạo: Lược đồ chữ ký số tập thể mù đề xuất có bộ tham 
số được gọi là an toàn trong ROM nếu tồn tại -ECDL trong 
trường GF(p), với: 
 Trong đó, (M ,,) r l sần lư {(ợ Mt 0là ,, r 0số s 0truy ),( M 1v ,,)}ấ r 1n sc 1ủa hàm băm, trích xuất và tạo 
 (,) t
chữ ký mù; E là thời gian thực hiện các phép tính luỹ thừa modulo trong GF(p). 
 qh() q e q s 11 
  (1 )(1 ) ; t t O() qes q E
 q q qh
 71 
 Chứng minh: Sử dụng các kết quả trình bày trong định nghĩa 1.2 của chương 
1 để chứng minh. 
 Giả sử tồn tại một kẻ giả mạo A, xây dựng thuật toán B để giúp A giải bài toán 
logarit rời rạc. B được cho là một nhóm nhân G trong GF(p) với thành phần G, số 
nguyên tố q và điểm Q trên đường cong elliptic. B được yêu cầu tìm giá trị 
sao cho . 
 xZ q
 *
 B tiến hành như sau: chọn hàm băm thông điệp rH 0,1 q , gửi 
tham số công khai (,,,)p G Q r tới A. B chọn hai giá trị ngẫu nhiên (kʹ,dʹ) và tính 
C*: 
 C* Q d G k P (2.10) 
 dʹ được xem như là khoá riêng của người ký, kʹ là giá trị được chọn ngẫu 
nhiên và (kʹ,dʹ,C*) là kết quả đầu ra. A truy vấn tập Oracle của chữ ký số với thông 
 Q x G
điệp M và khoá riêng dʹ. Đầu tiên, B kiểm tra xem d' đã được sử dụng cho truy vấn 
trong các phần cài đặt trước chưa. Nếu dʹ đã được sử dụng rồi thì B lấy bộ 
(C*,, k d ) từ bảng được lưu để ký thông điệp M theo pha tạo chữ ký được mô tả 
trong lược đồ. Đầu ra của thuật toán ký là (,,)M r s . Nếu dʹ chưa được sử dụng 
trong các phần cài đặt trước thì B thực hiện lại các mô phỏng và chọn lại khoá bí 
 *
mật dʹ cho đến khi thỏa mãn. Cuối cùng, A tạo ra chữ ký số giả mạo là s11 (,) r s 
trên M bởi khoá bí mật dʹ. B lại thực hiện lần nữa bằng cách giữ nguyên ()r và lại 
 *
yêu cầu A ký tiếp và thu được s22 (,) r s . 
 Từ C* s G r P 
 Thay vào (2.10), tính được: 
 *
 Q k d G d G sj G r P
 *
 x G k d G d G sj G rd G 
 *
 sj x d k - rd d 
 72 
 với j=1,2. 
 Thuật toán B chưa biết nên để thu được x thì B phải giải phương trình 
tuyến tính có hai ẩn số hoặc phải giải bài toán ECDLP. 
 Phân tích xác suất: Xác suất thực hiện thành công việc lựa chọn đúng giá trị 
hàm băm là và được mô phỏng thực hiện trong 
lần. Ta có nên B có thể xác định chính xác điểm 
nghiêm ngặt để chọn lại giá trị hàm* băm là 1/q . 
 hH 0,1 q h
 ()qq 
 Do tính ngẫu nhiên lý tưởng trong ROMes nên xác suất tồn tại chữ ký s là 1/q . 
 q() q q 11
Như vậy, xác suất thành công(,)xr là  (1 h e s )(1 ) . Độ phức tạp về 
 q q qh
thời gian của thuật toán B dựa trên hàm mũ được thực hiện trong pha hình thành 
khoá và ký số, và là 
 q
 1 h
2.2.3. Đánh giá độ phức tạp thời gianq của các lược đồ đề xuất 
 q q() q q
 Theo [2(16 ], cóh ) qq ưes ớc lư 1ợ ng: h TTTTTT e s ; 240 ; 29 , trên cơ sở các 
 qqh m inv m s m
phép tính trong các phương trình của lược đồ đề xuất và lược đồ được trình bày 
trong [79], quy đổi về độ phức tạp thời gian của phép tính nhân Tm , các kết quả so 
sánh như trình bày bên dưới. 
 Z
 Phần này so sánh độ phức tạpp thời gian của các lược đồ LĐ 2.03 với lược đồ 
t t O(). q q E
được mô tảes trong [73] với giả định là các lược đồ đó phải được tính toán với cùng 
tham số an toàn trong và số thành viên của tập thể người ký là n. 
 73 
 Bảng 2.8. Độ phức tạp thời gian của lược đồ LĐ 2.03 
 Lược đồ dựa trên chuẩn GOST R34.10-2012 (LĐ 2.03) 
 Loại phép tính 
 T
 Làm mù Tạo chm ữ ký Giải mù Kiểm tra 
Phép tính luỹ thừa 
Phép tính nghịch đảo 1 1 2 
Phép tính hàm băm 1 
Phép tính nhân vô hướng 2 
Phép tính nhân modulo 3 2n 3 2 
 Quy đổi ra Tm 302Tm 2nTm 243Tm 482Tm 
 Tổng chi phí thời gian (1027+2n) Tm 
 Bảng 2.9. So sánh độ phức tạp thời gian của lược đồ LĐ 2.03 và lược đồ [73] 
 Lược đồ LĐ 2.03 [73] 
 Làm mù 302 310 
 Tạo chữ ký 2n 2n 
 Giải mù 243 243 
 Kiểm tra chữ ký 540 482 
 Tổng cộng (1027+2n) (1057+2n) 
 Bảng 2.9 cho thấy độ phức tạp thời gian của lược đồ chữ ký số tập thể mù dựa 
trên chuẩn GOST R34.10-2012 làZ pgần như tương đương với lược đồ trong [73], tuy 
nhiên do lược đồ LĐ 2.03 dựa trên bài toán ECDLP, trong khi [73] dựa trên bài toán 
DLP nên độ dài khóa của LĐ 2.03 nhỏ hơn nhiều so với độ dài khóa trong [73] khi 
có cùng mức độ an toàn. 
 Phần tiếp theo so sánh độ phức tạp thời gian của các lược đồ LĐ 2.04 với hai 
lược đồ được mô tả trong [73] và [79] với giả định là các lược đồ đó phải được tính 
toán với cùng tham số an toàn trong và số thành viên của tập thể người ký là n. 
 74 
 Bảng 2.10. Độ phức tạp thời gian của lược đồ LĐ 2.04 
 Lược đồ dựa trên EC-Schnorr (LĐ 2.04) 
 Loại phép tính 
 Làm mù Tạo Tchm ữ ký Giải mù Kiểm tra 
Phép tính luỹ thừa 
Phép tính nghịch đảo 
Phép tính hàm băm 1 
Phép tính nhân vô hướng 2 2 
Phép tính nhân modulo n 
Quy đổi ra Tm 59Tm nTm Không đáng kể 58Tm 
Tổng chi phí thời gian (117+n) 
 Bảng 2.11. Độ phức tạp thời gian của lược đTồm [79] 
 Lược đồ [79] 
 Loại phép tính 
 Làm mù Tạo chữ ký Giải mù Kiểm tra 
Phép tính luỹ thừa 
Phép tính nghịch đảo 1 
Phép tính hàm băm 1 
Phép tính nhân vô hướng 
Phép tính nhân modulo 3 n 1 1 
 Quy đổi ra Tm 245Tm nTm Tm Tm 
Tổng chi phí thời gian (247+n) 
 Bảng 2.12. So sánh chi phí thời gian của LĐ 2.04 và lược đồ [73] và [79] 
 (LĐ 2.04) [73] [79] 
Làm mù 59 310 245 
Tạo chữ ký mù n 2n n 
Giải mù Không đáng kể 243 
Kiểm tra chữ ký 58 482 
 Tổng cộng (117+n) (1057+2n) (247+n) 
 75 
 Bảng 2.12 cho thấy độ phức tạp thời gian của lược đồ chữ ký số tập thể mù 
dựa trên lược đồ EC-Schnorr là thấp hơn [73] và [79], Tuy nhiên do LĐ 2.04 dựa 
trên bài toán ECDLP, trong khi [73] dựa trên bài toán DLP nên độ dài khóa của LĐ 
 T
2.04 nhỏ hơn nhiều so với độ dài khóa trongm [73] khi có cùng mức độ an toàn. Đối 
với lược đồ [79] thì lược đồ LĐ 2.04 và lược đồ [79] cùng dựa trên bài toán ECDLP 
nên với cùng độ dài khóa thì độ phức tạp về thời gian của LĐ 2.04 thấp hơn khoảng 
hai lần so với [79] nên có thể nghiên cứu tính toán ứng dụng được trong thực tế. 
 Tiếp theo là phần so sánh độ phức tạp thời gian của các lược đồ LĐ 2.03 và 
LĐ 2.04 là hai lược đồ đề xuất dựa trên bài toán khó ECDLP. 
 Bảng 2.13. So sánh chi phí thời gian của LĐ 2.03 và lược đồ LĐ 2.04 
 LĐ 2.03 LĐ 2.04 
 Làm mù 302 59 
 Tạo chữ ký mù 2n n 
 Giải mù 243 Không đáng kể 
 Kiểm tra chữ ký 540 58 
 Tổng cộng (1027+2n) (117+n) 
 Bảng 2.13 cho thấy, độ phức tạp thời gian của lược đồ chữ ký số tập thể mù 
dựa trên chuẩn GOST R34.10-2012 là cao hơn lược đồ chữ ký số dựa trên EC-
Schnorr. Phát hiện này phù hợp với các đánh giá so sánh giữa chuẩn GOST R34.10-
2012 và lược đồ chữ ký số EC-Schnorr. 
2.3. ĐỘ PHỨC TẠP VỀ THỜI GIAN CỦA CÁC LƯỢC ĐỒ ĐỀ XUẤT 
2.3.1. Thực nghiệm 
 Phần này chạy thực nghiệm tính thời gian của các pha trong các lược đồ đề 
xuất. Thời gian tính toán cho các pha làm mù, ký số, giải mù và kiểm tra là các trình 
quản lý độc lập, tức là không dựa trên ứng dụng nào được phát triển trong môi 
trường thực tế. Do đó tất cả thời gian tính toán không bao gồm thời gian giao tiếp. 
 76 
Ngoài ra, phần này được giả định rằng các yếu tố gây mù, số nguyên bí mật, số 
nguyên tố, của các thực thể liên quan được chuẩn bị trước. Đồng thời, các hoạt 
động không liên quan đến mật mã không được xem xét. 
 Tm
 Phần thực nghiệm sử dụng máy tính ảo hóa trên nền VMWare đặt tại trung 
tâm dữ liệu tỉnh Tây Ninh, với cấu hình máy chủ là: Processor Intel Xeon Silver 
4216 2.1G, 16C/32T, 9.6GT/s, 22M Cache, Turbo, HT (100W) DDR4-2400; 
Memory 16GB; Microsoft Windows 10 (10.0) Professional 64-bit; java version 
"1.8.0_201" (JAVA 8); NetBeans 8.2. Các tham số đầu vào sử dụng khóa 1024 bit 
cho các lược đồ dựa trên bài toán DLP và 192 bit cho các lược đồ dựa trên bài toán 
ECDLP, sử dụng hàm băm là SHA-256, số thành viên ký trong lược đồ ký tập thể là 
n=3. Kết quả được tính trung bình 1000 lần chạy và được chỉ ra như bên dưới. 
 Bảng 2.14 cho thấy, nếu sử dụng độ dài khóa cho các lược đồ dựa trên bài toán 
DLP là 1024 bit và sử dụng độ dài khóa cho các lược đồ dựa trên bài toán ECDLP 
là 192 bit (khi đó độ dài khóa của DLP gấp khoảng 5.3 lần ECDLP) thì thời gian 
tính toán của các lược đồ chữ ký số tập thể mù dựa trên chuẩn GOST R34.10-94 
(bài toán DLP) là 29.1965 mili giây và lược đồ chữ ký số tập thể mù dựa trên chuẩn 
GOST R34.10-2012 (bài toán ECDLP) là 43.9465 mili giây, tức là thời gian tính 
toán của LĐ 2.03 khoảng 1.5 lần thời gian của LĐ 2.01. 
 Bảng 2.14. Chi phí thời gian của lược đồ đề xuất theo chuẩn GOST (mili giây) 
 (LĐ 2.01) (LĐ 2.03) 
 Thực 
 Lý thuyết Lý thuyết Thực nghiệm 
 nghiệm 
Làm mù 287 11.2791 302 13.7003 
Tạo chữ ký 2n 0.2463 2n 0.2509 
Giải mù 243 8.1671 243 8.7312 
Kiểm tra chữ ký 264 9.5040 540 21.2641 
Tổng thời gian (794+2n) 29.1965 (1027+2n) 43.9465 
 77 
 Bảng 2.15. Chi phí thời gian của lược đồ đề xuất theo Schnorr (mili giây) 
 (LĐ 2.02) (LĐ 2.04) 
 ThTực Thực nghiệm 
 Lý thuyết m Lý thuyết 
 nghiệm 
Làm mù 45 1.8551 59 2.9692 
Tạo chữ ký n 0.1232 n 0.1932 
Giải mù Không đáng kể 0.0004 Không đáng kể 0.0005 
Kiểm tra chữ ký 44 1.6584 58 2.3191 
Tổng thời gian (89+n) 3.6371 (117+n) 5.4920 
 Bảng 2.15 cho thấy, thời gian tính toán của các lược đồ chữ ký số tập thể mù 
dựa trên lược đồ Schnorr (LĐ 2.02) là 3.6371 mili giây và lược đồ chữ ký số tập thể 
mù dựa trên lược đồ EC-Schnorr (LĐ 2.04) là 5.4920 mili giây, tức là thời gian tính 
toán của lược đồ LĐ 2.04 khoảng 1.5 lần thời gian của LĐ 2.02. 
 Như vậy, kết quả thực nghiệm cho thấy thời gian tính toán của các lược đồ 
chữ ký số tập thể mù dựa trên bài toán DLP là thấp hơn các lược đồ dựa trên bài 
toán ECDLP (khoảng 1.5 lần), trong khi độ dài khóa của các lược đồ dựa trên bài 
toán ECDLP là thấp hơn các lược đồ