Phát triển lược đồ chữ ký số elgamal trên vành zn ngăn ngừa tấn công dựa vào tình huống lộ khóa phiên hoặc trùng khóa phiên

Journal of Science and Technique - Le Quy Don Technical University - No. 199 (6-2019)
PHÁT TRIỂN LƯỢC ĐỒ CHỮ KÝ SỐ
ELGAMAL TRÊN VÀNH Zn NGĂN NGỪA
TẤN CÔNG DỰA VÀO TÌNH HUỐNG
LỘ KHÓA PHIÊN HOẶC TRÙNG KHÓA PHIÊN
Lê Văn Tuấn1, Tạ Minh Thanh1, Bùi Thế Truyền1
Tóm tắt
Lược đồ ElGamal và các biến thể của nó dựa trên tính khó giải của bài toán logarit rời
rạc trên trường hữu hạn Zp là không an toàn khi xảy ra các tình huống lộ khóa phiên hoặc
trùng khóa phiên. Dựa trên lược đồ ElGamal, chúng tôi xây dựng lược đồ chữ ký cơ sở để
phát triển lược đồ chữ ký số mới có độ an toàn dựa trên tính khó giải của bài toán logarit
rời rạc trên vành hữu hạn Zn. Chúng tôi chứng minh rằng lược đồ đề xuất là an toàn trong
những tình huống trùng kháo phiên hoặc bị lộ khóa phiên, đồng thời đảm bảo tính đúng đắn,
an toàn và hiệu quả. Với những đặc tính này, lược đồ đề xuất có thể ứng dụng vào thực tế.
Từ khóa
Lược đồ chữ ký số, bài toán logarit rời rạc, hàm băm.
1. Giới thiệu
Lược đồ chữ ký số ElGamal được đề xuất vào năm 1985 [8],[9] bởi chính ElGmal.
Dựa trên lược đồ ElGaml, đã có nhiều lược đồ chữ ký số là biến thể của ElGaml được
đề xuất bởi các nhà khoa học trên thế giới, chẳng hạn như lược đồ chữ ký số Schnorr
năm 1990 [10], lược đồ chữ ký số DSA năm 1994 [11] và các lược đồ này đều phụ
thuộc vào độ khó giải của bài toán logarit rời rạc trên trường hữu hạn Zp không an
toàn trong những tình huống lộ khóa phiên hoặc trùng khóa phiên, nguyên nhân là các
lược đồ chữ ký số này đã công khai bậc của phần tử sinh, điều này được chỉ ra trong
các kết quả nghiên cứu liên quan [12], [13], [14], [15],[16]. Để khắc phục những điểm
tồn tại đã chỉ ra trong lược đồ chữ ký số Elgamal và biến thể của nó, trong thời gian
qua, nhiều lược đồ chữ ký số trên vành được nghiên cứu phát triển bởi các nhà khoa
học trong nước và trên thế giới[1],[2],[3], [17],[18],[19],[20], bởi một số lí do sau:
Thứ nhất, cấu trúc vành Zn cho phép che giấu được bậc của phẩn tử sinh[3].Chúng
ta biết rằng tập Zn cùng với phép cộng và phép nhân theo modul n tạo nên một vành
hữu hạn Zn, trong đó n được cấu tạo từ hai đến 3 số nguyên tố (thông thường n = p.q,
1Học viện Kỹ thuật quân sự
91
Section on Information and Communication Technology (ICT) - No. 13 (6-2019)
trong đó p, q là các số nguyên tố phân biệt). Trường hợp n = p.q thì nhóm nhân Z∗n là
nhóm có bậc lớn nhất là (p − 1).(q − 1) và việc tìm giá trị này được cho là khó khi
không biết phân tích của n, tức là bậc của các nhóm con của nhóm nhân Z∗n có thể giữ
được bí mật khi không biết phân tích của n.
Thứ hai, bài toán logarít rời rạc trên vành Zn(n = p.q, trong đó p, q là các số nguyên
tố phân biệt) được cho là khó hơn bài toàn logarít rời rạc trên trường Zp[3], bởi vì để
giải nó thì phải giải đồng thời ba bài toán, đó là: bài toán phân tích số n = p.q, bài
toán DLPp và DLPq.
Thứ ba, cho đến nay, ngoài thuật toán Baby step-giant step của Danied Shank có thể
ứng dụng để giải bài toán logarit rời rạc trên vành Zn[6] thì các thuật toán khác chẳng
hạn như: thuật toán Rho của Pollard, thuật toán Pohlig-Hellman, không áp dụng để giải
bài toán logarit rời rạc trên trường hữu hạn Zp.
Các lược đồ tiêu biểu trên vành của các nhà khoa học trong nước như: Pham Van
Hiep và cộng sự [1] vào năm 2018; Vũ Long Vân và cộng sự [3] vào năm 2017. Bên
cạnh đó là các lược đồ chữ ký số được phát triển bởi các nhà khoa học trên thế giới,
đó là: lược đồ Tripathi và Gupta[19] vào năm 2017; Tan[20] vào năm 2003. Tuy nhiên,
kết quả khảo sát cho thấy các lược đồ chữ ký trên vành này vẫn còn một số điểm tồn
tại, chẳng hạn như: bậc của phân tử sinh chưa tường minh, miền giá trị lớn hơn mức
cần thiết vừa chi phí tính toán lớn, vừa tốn bộ nhớ mà chưa chắc đã an toàn[19],[20];
Một số lược đồ có bậc của phần tử sinh đuợc cấu tạo bởi các số nguyên tố siêu mạnh
mà việc sinh các số nguyên tố này rất khó khăn [18]. Việc khắc phục những điểm còn
tồn tại trên các lược đồ chữ ký số trên vành Zn này như là nhiệm vụ nghiên cứu của
bài báo này, cụ thể là dựa trên lược đồ Elgamal, nhóm tác giả đã đề xuất một lược đồ
chữ ký số mới trên vành Zn với một số đóng góp quan trọng trong bài báo này, đó là:
Thứ nhất, xây dựng lược đồ chữ ký số cơ sở trên vành Zn, từ đó đề xuất lược đồ
chữ ký số mới dựa trên lược đồ cơ sở an toàn khi tình huống trùng khóa phiên hoặc lộ
khóa phiên xảy ra.
Thứ hai, xây dựng cơ sở toán học để xác định phần tử sinh và đã sinh thành công
bộ tham số của lược đồ đề xuất có cỡ khóa sát với cỡ khóa trên thực tế (vài ngàn bit)
phục vụ cho thử nghiệm.
Thứ ba, đã thử nghiệm thành công lược đồ đề xuất với các bộ tham số sinh ra. Tiến
trình thử nghiệm thực hiện trên hai khâu: khâu sinh chữ ký và xác nhận chữ ký. Kết
quả thử nghiệm cho thấy giữa phân tích lí thuyết và kết quả thử nghiệm là khá tương
đồng.
Bài báo được tổ chức như sau: Ngoài phần giới thiệu, trong phần II, chúng tôi đưa ra
một số công việc liên quan. Phần III, chúng tôi trình bày lược đồ đề xuất. Cuối cùng,
chúng tôi trình bày một số kết quả thử nghiệm, kết luận. Phần phụ lục trình bày công
cụ để thử nghiệm và một số kết quả thử nghiệm.
92
Journal of Science and Technique - Le Quy Don Technical University - No. 199 (6-2019)
2. Một số kiến thức liên quan
2.1. Một số hàm và định lý bổ trợ
Định nghĩa 2.1. Hàm H: {0, 1}∞ −→ {0, 1}512 chuyển một xâu có độ dài hữu hạn
bất kỳ thành xâu có 512 bit.
Định nghĩa 2.2. Hàm Num: {0, 1}∞ −→ Z, đổi một xâu nhị phân có độ dài hữu
hạn bất kỳ thành một số số nguyên. Num(bkbk−1...b0) trong đó a được tính theo công
thức: a = b0 + 21b1 + ...+ 2kbk
Định nghĩa 2.3. Hàm str(a): Z≥0 −→ {0, 1}∞ trả về một số nhị phân tương ứng
với số nguyên không âm a.
Định nghĩa 2.4. Hàm Random(X): Hàm trả về một phần tử ngẫu nhiên thuộc tập
X, giả sử phần tử k ∈ X , ta ký hiệu k ∈R X .
Định nghĩa 2.5. Cho phần tử g thuộc vành Zn, bậc của phần tử g là số nguyên dương
t nhỏ nhất sao cho gt = 1modn, ký hiệu t = ordn(g).
Định nghĩa 2.6. Cho n là số nguyên dương, hàm Len(n) trả về số  ... 12 được sử dụng trong thuật toán ký và xác nhận chữ ký của các
lược đồ.
- Công cụ thử nghiệm là chương trình thử nghiệm viết bằng ngôn ngữ lập trình C++,
được biên dịch bởi trình QT Creater và chạy trên hệ điều hành Windows 7. Bộ vi xử
lý Core2 Duo 2.2 GHz bộ nhớ 2GB.
- Tham số thử nghiệm của các lược đồ chữ ký số có kích thước và tiêu chuẩn gần
với tham số trên thực tế.
Kết quả thử nghiệm được chỉ ra trong hình 2. Kết quả sinh chữ ký được minh họa
bởi hình 2, chỉ ra mối quan hệ giữa thời gian ký và cỡ của khóa:
Kết quả xác nhận chữ ký, được minh họa trong hình dưới đây chỉ ra mối quan hệ giữa
thời gian xác nhận chữ ký và cỡ của khóa (hình 3).
108
Journal of Science and Technique - Le Quy Don Technical University - No. 199 (6-2019)
Hình 3. Đồ thị thời gian sinh chữ ký
Hình 4. Đồ thị thời gian xác nhận chữ ký
3.4.2. Đánh giá kết quả:
Việc đánh giá kết quả thử nghiệm được dựa trên các tiêu chí sau: Tính đúng đắn,
tính đầy đủ, tính hiệu quả.
- Tính đúng đắn: Kết quả thử nghiệm đã đảm bảo tính chính xác, bởi các tham số
cơ bản được sinh bằng các thuật toán tất định, đã được chứng minh tính đúng đắn.
- Kết quả thử nghiệm bảo đảm tính đầy đủ trên khâu sinh chữ ký và xác nhận chữ
ký được thực hiện ký với các loại file đầu vào (văn bản, audio, video...)
- Đảm bảo tính hiệu quả, cụ thể là: sinh tham số khá nhanh với tỷ lệ thành công
tuyệt đối.
Qua các công đoạn thử nghiệm sinh tham số và sử dụng tham số để thử nghiệm việc
ký và xác nhận chữ ký cho thấy: kết quả thử nghiệm đã sinh ra được bộ tham số cho
lược đồ theo đúng tiêu chuẩn đã xây dựng đảm bảo chính xác tuyệt đối. Mỗi bộ tham
số được sinh ra đều áp dụng vào để thử nghiệm cho quy trình ký và xác nhận chữ ký,
109
Section on Information and Communication Technology (ICT) - No. 13 (6-2019)
kết quả ký và xác nhận chữ ký đảm bảo nhanh và chính xác tuyệt đối.
4. Kết luận
Bài báo đã đề xuất hai lược đồ chữ ký số cơ sở CS01 và CS02 trên vành Zn. Điểm
khác biệt giữa hai lược đồ là lược đồ CS01 để phát triển các lược đồ chữ ký số cho
các ứng dụng mà độ phức tạp tính toán phân đều cho bên ký và bên xác nhận chữ ký.
Lược đồ CS02 để phát triển các lược đồ chữ ký số mà yêu cầu bên xác nhận chữ ký có
độ phức tạp tính toán lớn hơn bên ký (giá trị nghịch đảo của thành phần bí mật được
tính trước). Dựa trên lược đồ CS01, nhóm tác giả trong [17] đã phát triển một lược đồ
chữ ký số trên vành Zn. Trong bài bào này nhóm nghiên cứu đã phát triển một lược
đồ chữ ký số mới dựa trên lược đồ CS02, khắc phục được sự mất an toàn trong tình
huống lộ khóa phiên hoặc trùng khóa phiên. Một đóng góp quan trọng là nhóm nghiên
cứu đã đưa ra cơ sở toán học tồn tại phân tử sinh và đã xây dựng thuật toán để sinh và
sinh thành công phần tử sinh trong vành Zn. Nhóm tác giả đã chứng minh tính đúng
đắn, tính hiệu quả và an toàn của lược đồ đề xuất. Do tính độc lập của mỗi chữ ký dựa
vào thành phần ngẫu nhiên k và hàm băm SHA-512, cùng với bậc của phần tử sinh g
được giữ bí mật nên lược đồ đề xuất là an toàn với các mô hình tấn công cơ bản như
mô hình "Existential forgery", mô hình "Selective forgery". Hơn nữa, dựa theo chứng
minh trong [20] lược đồ đề xuất an toàn cả trong mô hình tấn công Random Oracle
Model. Phần tử nghiệm, nhóm tác giả đã viết chương trình thử nghiệm trên ngôn ngữ
C++. Kết quả thử nghiệm cho thấy giữa phân tích toán học về chi phí tính toán với kết
quả thử nghiệm là tương đồng. Tuy nhiên, để sử dụng trong thực tế, cần phải xác định
ngưỡng an toàn và hệ tiêu chuẩn tham số an toàn cho lược đồ chữ ký số này, đây là
vấn đề nghiên cứu mà nhóm tác giả sẽ giới thiệu trong bài báo tiếp theo.
Phụ lục A
Phầm mềm, công cụ thử nghiệm
Nhóm nghiên cứu đã viết chương trình sinh tham số, sinh chữ ký và xác nhận chữ
ký trên nền ngôn ngữ lập trình C++, được biên dịch bởi trình QT Creater và chạy trên
hệ điều hành Windows 7. Hình 5 là giao diện chính của chương trình.
Phụ lục B
Kết quả thử nghiệm
1. Sinh tham số
+ Đối tượng áp dụng: Kinh tế xã hội
+ Năm áp dụng: 2018
+ Độ dài số modul n, Nlen = 1792
+ Security_strength = 110
2.1. Sinh số nguyên tố:
110
Journal of Science and Technique - Le Quy Don Technical University - No. 199 (6-2019)
Hình 5. Giao diện của chương trình
p=5282945311356652463523397849165166065188473260361215221279607090266739
025567248594744836366500735269193878013655941812914496511318451374801508
460873861267681581952573332496660273965089772299521526413049796842047595
29953895665938963777587220555249311678856789340100756067 (897 bit)
q=5282945311356652463523397849173501083306400613792325182555901913881312
469788917147138302804293250146636155790298444481666155936947129272244886
904121923197170448836229758676945426021504796388303187828440145890005848
38607538326427409531894088353785727288347357889043869941 (897 bit)
p1=351135998686172145514800629219732389697237945919543610443067426510057
9719359093 (261 bit)
q1=239767701468901318717606028225365849694628979078731871393565209023030
8068120360840743559388426743 (321 bit)
n=p.q=279095111627852376407822673918505407354749705961588183386608979984
540925670091938384305766898611192576196487981187875342654271276455362578
441059659025112242589918768187462087436905433968688025045665606722493281
521161141737880734118201237469386163120818542305125859521374856983765793
510989417532589326792439128846817391492826615177106876643927259054603258
885399464024778550158780494646111202730280602862474875455792444910199699
684204689391545124447662262343901998741135472389812058690476179475514568
085713166979184410616266536711665714682047 (1793 bit)
t=p1.q1=8419107130797064865349090513227773703070006264494997465727900966
301411351030560683988845274427694659374506815090402679368847119214309412
872847601069944737601795634493541424099
2.2. Phần tử sinh g:
g=1407166053903100832888279187262758404918908741267136140296782039167623
111
Section on Information and Communication Technology (ICT) - No. 13 (6-2019)
712782160726503327343663996298299197281754517115315421875577266560675644
171643476323490152879308509416896514362246473923507912474282520495591593
698289135467272143181948842984084713986580688656193424172666483415788387
998503380984356119929288893109310657108836305548986000647616454579775420
319669475792311350419117305138328311145774137758847288327075620732571072
145129369829981634950867001563849028045482461369867179369611587701845984
95315513995870006888678139445175823538 (1792 bit)
2.3. Khóa bí mật x:
x=1278702594052290932204553770336181149779446303726
x−1=1=78949929196941749388200754408635888805981854924987701699945754248
98008752890152240189023211958895627489159720085461205000357350851961513
269331905176578746275099761068427242332 (581 bit)
2.4. Khóa công khai y:
y=256226867856780258434349260283936493614630430236186611647577296293269
24219491794951748166497406001862189961055240322038548672546636549535279
00807116558889712398458908232198127807304712967709146928999732877178222
15451706190930402348810137463793444332826817964954602173526289980601241
45492592289422824219945376550035302224187385480882236651006327768565141
45848503651213258463896224896807182125721179306797307912549034468797266
69656106762084606448485486629860796179617591882798037425395139988764081
986465595175730847406663057609428526603484514 (1792 bit)
2. Sinh chữ ký
2.1. Giá trị băm của tập tin:
M=3688A43481D893A943055F2F43D51BE2E17376433C6B9535F1D7F6FCC9FE332
AE7 94F3FDECC610A43FB2765470E37240372B6AC74AF3148490998B77B9F88598
2.2. Giá trị khóa phiên K:
K=45894939739183446465600355321120718409875671873669959165512997999193
87669598575769495202140003526086655401
2.3. Chữ ký được sinh:
R=266152254149393604237151675338372158144898001142355929180119661795423
002913676043105790731009828464401438623769512167077097534821009846077652
941884804065675625914436078896337553679502183813916848582378133026561228
379798265299476983823776628492432194583517613502755857797214286665530032
140344330433140076257230163963981138065850141904092078908319909473256688
351602099543780373277380915677367864428214051435476662136796697123946952
825623868683095521082433647486853763833239625269740686743474138953706931
774465488038146410329418688585656948363( 1792 bit)
S=169602705998183160037246459982528618296576667480398510986243038528629
58012940288565222833886113762436531275280960611164126766912319328188608
72038616318186133847044435894320192( 579 bit)
2.4. Thời gian sinh chữ ký: 1.673(s)
3. Xác nhận chữ ký
3.1. Kết quả: Xác nhận chữ ký thành công!
112
Journal of Science and Technique - Le Quy Don Technical University - No. 199 (6-2019)
3.2. Thời gian xác nhận chữ ký: 4.843(s)
Tài liệu tham khảo
[1] Phạm Văn Hiệp, Nguyễn Hữu Mộng, Lưu Hồng Dũng, "Một thuật toán chữ ký xây dựng trên tính khó của việc
giải đồng thời hai bài toán phân tích số và logarit rời rạc", Tạp chí khoa học và công nghệ, Đại học Đà nẵng,
2018.
[2] Lê Văn Tuấn, Bùi Thế Truyền, Lều Đức Tân, "Phát triển lược đồ chữ kí số mới có độ an toàn dựa trên bài toán
logarit rời rạc trên vành Zn", Tạp chí Khoa học công nghệ Thông tin và Truyền thông, Học viện Công nghệ
Bưu chính viễn thông, số. 10, 2018.
[3] Vũ Long Vân, Hồ Ngọc Duy, Nguyễn Kim Tuấn, Nguyễn Thị Thu Thủy, "Giải pháp nâng cao độ an toàn cho
lược đồ chữ ký số", Hội thảo SOIS, Dec. 2017.
[4] Hoàng Văn Thức, "Hệ tiêu chuẩn an toàn cho hệ mã RSA và ứng dụng", Luận án tiến sỹ, Hà Nội, 2011.
[5] Chu Minh Yên, "Nghiên cứu xây dựng hạ tầng cơ sở khóa công khai trong lĩnh vực An inh - Quốc phòng",
Luận án tiến sĩ, 2012.
[6] Lê Văn Tuấn, Bùi Thế Truyền, "Phát triển thuật toán của SHANK giải bài toán logarit rời rạc trên vành Zn",
Tạp chí Nghiên cứu Khoa học công nghệ quân sự, số 48, Apr. 2017.
[7] Lê Văn Tuấn, Lều Đức Tân, "Phát triển thuật toán Rho porllard tính cấp của phần tử trên vành Zn", Tạp chí
Nghiên cứu khoa học công nghệ quân sự, số 49, 6-2017.
[8] T. ElGamal, "A public key cryptosystem and signature scheme based on discrete logarithms", IEEE Transaction
on Information Theory, vol. IT-31, no. 4, pp. 469 - 472, 1985.
[9] W. C. Kuo, "On ElGamal Signature Scheme", Future Generation Communication and Networking (FGCN 2007),
pp. 151-153, 2007.
[10] C. P. Schnorr, "Efficient signaturegeneration for smartcards", Journal of Cryptology, vol. 4, pp. 161-174, 1991.
[11] B. Yang, "A DSA-Based and Efficient Scheme for Preventing IP Prefix Hijacking", International Conference
on Management of e-Commerce and e-Government, pp. 87-92, 2014.
[12] J. Liu, X. Cheng, and X. Wang, "Methods to forge elgamal signatures and determine secret key", Advanced
Information Networking and Applications, AINA, pp. 859–862, 2006.
[13] L. Xiao-fei, S. Xuan-jing and C. Hai-peng, "An improved ElGamal digital signature algorithm based on adding
a random number", 2nd International Conference on Networks Security, Wireless Communications and Trusted
Computing, pp. 236-240, 2010.
[14] C. Y. Lu, W. C. Yang and C. S. Laih, "Efficient Modular Exponentiation Resistant to Simple Power Analysis
in DSA-Like Systems", International Conference on Broadband, Wireless Computing, communication and
Applications, pp. 401-406, 2010.
[15] H. Zhang, R. Li, L. Li and Y. Dong, "Improved speed Digital Signature Algorithm based on modular inverse",
Proceedings of 2013 2nd International Conference on Measurement, Information and Control, pp. 706-710,
2013.
[16] Z. Ping, W. Tao and C. Hao, "Research on L3 Cache Timing Attack against DSA Adopting Square-and-Multiply
Algorithm", Fifth International Conference on Instrumentation and Measurement, Computer, Communication and
Control (IMCCC), pp. 1390-1393, 2015.
[17] Le Van Tuan, Bui The Truyen, Leu Duc Tan, "Contructing the digital signature besed on the discrete logarithmic
problem", The research journal of military science and technology, No 51a, ISSN 1859 – 1043, pp 44-56, 2017.
[18] Le Van Tuan, Ta Minh Thanh, Leu Duc Tan "A solution to improve the digital signature schemes DSA in field
Zp be secure from the situations of coinciding or revealing of session key", Journal of science and technology,
technical universities, 2018.
[19] S. K. Tripathi and B. Gupta, "An efficient digital signature scheme by using integer factorization and discrete
logaríthm problem", International Conference on Advances in Computing, Communications and Informatics
(ICACCI), pp. 1261-1266, 2017.
[20] C.H. Tan, X. Yi and C. K. Siew, "Signature scheme based on composite discrete logarithm", Fourth International
Conference on Information, Communications and Signal Processing, pp. 1702-1706, 2003.
[21] D.R Stinson, Cryptography Theory and Practice, CRC Press, 2003.
Ngày nhận bài 14-05-2018; Ngày chấp nhận đăng 14-05-2019.

113
Section on Information and Communication Technology (ICT) - No. 13 (6-2019)
Lê Văn Tuấn tốt nghiệp Đại học tại Đại học Thái Nguyên năm 1992, Thạc sĩ năm 2007.
Tuấn hiện đang là nghiên cứu sinh tại Khoa Công nghệ thông tin, Học viện Kỹ thuật quân sự.
Bùi Thế Truyền nhận bằng Kỹ sư tại Học viện Kỹ thuật quân sự năm 2000, bằng tiến sĩ năm
2008. Hiện Truyền đang công tác tại Viện Công nghệ mô phỏng, Học viện Kỹ thuật quân sự.
Tạ Minh Thanh hiện là giảng viên Khoa Công nghệ thông tin, Học viện Kỹ thuật quân sự.
DEVELOPING THE ELGAMAL DIGITAL SIGNATURE
SCHEME ON RING ZN PREVENT THE ATTACKS
FROM REVEALING OR COINCIDING OF SESSION KEY
Abstract
The Elgamal digital signature scheme and its variants are based on the discrete logarithm
problem on finite field Zp that are not secure when a session key is revealed or coincided.
Basing on the Elgamal digital signature scheme, we proposed two basic signature schemes.
Basing on these basic signature schemes we proposed a new signature scheme in which its
security is based on the discrete logarithm problem on finite ring Zn. We demonstrate that
the proposed scheme is secure when a session key is revealed or coincided. In addition, our
scheme is correct, secure, and effective and it can be applied into practice.
114