Hệ mật khóa công khai dựa trên tính khó của việc giải đồng thời 2 bài toán phân tích số và logarit rời rạc/khai căn

 tr ị RA theo công 
 y
 x1B (4.12) kA B
 −x1B . k k th ức: (5.2) 
 = M × g × ()g mod p mod p RA = (g mod p) mod nB
 = M × g −x1B . k × g x1B . k mod p = M 2 – G ửi RA cho B. 
 + B th ực hi ện: 
 Từ (4.3), (4.4), (4.9), (4.11) và (4.12) suy ra 
 1 – Ch ọn ng ẫu nhiên m ột giá tr ị k th ỏa 
điều c ần ch ứng minh: B
 mãn: 1< k < q , tính giá tr ị RB theo công 
 E = H (M ||R )mod q = H (M ||R )mod q = E B
 y
 kB A
 th ức: RB = (g mod p) mod nA (5.3) 
 c) M ức độ an toàn c ủa thu ật toán 2 – G ửi RB cho A. 
 Thu ật toán mã hóa – xác th ực được đề xu ất ở Bước 2 : 
đây th ực ch ất là s ự k ết h ợp gi ữa thu ật toán m ật mã ở + A th ực hi ện: 
mục 2 v ới thu ật toán ch ữ ký ở m ục 3, nh ằm cung 1 – Tính thành ph ần SA theo công th ức: 
 x1A
cấp tính n ăng b ảo m ật n ội dung c ủa b ản tin và xác S A = (yB ) mod p (5.4) 
th ực ngu ồn g ốc cùng v ới tính toàn v ẹn c ủa b ản tin 2 – Tính khóa bí m ật chia s ẻ v ới B theo: 
 k A
được th ực hi ện m ột cách đồng th ời. Có m ột điểm x2 A (5.5) 
 K AB = (()RB mod nA ) mod p
cần l ưu ý là d ạng t ấn công gi ả m ạo ở đây cần được 3 – Tính thành ph ần E theo công th ức: 
hi ểu theo ngh ĩa m ột k ẻ th ứ 3 (C) mu ốn m ạo danh A A
 E = H (K || S ) (5.6) 
để g ửi cho B b ản tin M. Tuy nhiên, phân tích t ừng A AB A
dạng t ấn công c ụ th ể t ươ ng t ự nh ư v ới các thu ật 4 – G ửi EA cho B. 
toán ở m ục 2 và 3 trên đây, đều cho th ấy độ an toàn + B th ực hi ện: 
của thu ật toán được đảm b ảo bởi độ khó c ủa vi ệc 1 – Tính thành ph ần SB theo công th ức: 
 S y x1B p (5.7) 
gi ải đồng th ời 2 bài toán IFP (n) và DLP (p,g) ho ặc B = ( A ) mod
IFP (n) và RSAP(n,e). 2 – Tính khóa bí m ật chia s ẻ v ới A theo: 
 kB
 K = R x2B mod n mod p (5.8) 
 5) Giao th ức trao đổi khóa BA (()A B )
 3 – Tính thành ph ần E theo công th ức: 
 Gi ả thi ết r ằng 2 đối t ượng tham gia truy ền B
 E = H (K || S ) (5.9) 
thông ở đây là A và B s ử d ụng m ột thu ật toán m ật B BA B
mã khóa đối x ứng (DES, AES,...) để mã hóa d ữ li ệu 4 – G ửi EB cho A. 
cần trao đổi v ới nhau, khi đó giao th ức trao đổi khóa Bước 3 : 
đề xu ất ở đây (Thu ật toán 5.1 ) được s ử d ụng để + A th ực hi ện: 
thi ết l ập m ột khóa bí m ật chung/chia s ẻ gi ữa A và Ki ểm tra n ếu: EA = EB thì kh ẳng định đối 
B. Các tham s ố h ệ th ống cũng được hình thành theo tượng tham gia trao đổi khóa là B và B đã thi ết l ập 
Thu ật toán 1.1 và khóa hình thành theo Thu ật được khóa bí m ật chia s ẻ v ới A, sau đó A có th ể 
toán 1.2 . Gi ả thi ết A và B có các cặp khóa bí dùng khóa này để trao đổi thông tin m ật v ới B b ằng 
mật/công khai t ươ ng ứng là và 1 thu ật toán m ật mã khóa đối x ứng. Ng ược l ại, tra 
 (,x1A x2 AA,)y
 , trong đó: được ch ọn ng ẫu nếu: EA ≠ EB thì kh ẳng định đối t ượng tham gia 
(,x1B x2BB,)y (x1A , x1B )
 trao đổi khóa là gi ả m ạo và h ủy khóa đã được t ạo ra. 
nhiên trong kho ảng ( ,1 q) , còn (x ,)y và (x ,)y 
 2 AA 2BB + B th ực hi ện: 
được tính theo (1.1) và (1.2) nh ư sau: 
 Ki ểm tra n ếu: EA = EB thì B kh ẳng định đối 
 y = (g)−x1 A mod p, x = (y )−1 mod ϕ()n
 A 2 A A A (5.1) t ượ ng tham gia trao đổi khóa là A và A đã thi ết l ập 
 −x1B −1
 yB = ()()g mod p, x2B = yB mod ϕ()nB được khóa bí m ật chia s ẻ v ới B. Ng ược l ại, nếu: 
 E E thì kh ẳng định đối t ượng tham gia trao đổi 
a) Thu ật toán trao đổi khóa A ≠ B
 khóa là gi ả m ạo. 
 Vi ệc thi ết l ập khóa chung gi ữa A và B được th ực 
hi ện theo các b ước c ủa Thuật toán 5.1 nh ư sau: 
 6 
 Hội th ảo l ần th ứ III: M ột s ố v ấn đề ch ọn l ọc v ề an toàn an ninh thông tin – Đà N ẵng, 07/12/2018 
 b) Tính đúng đắn c ủa giao th ức - Tính an toàn khóa đã bi ết ( known – key 
 security ): vi ệc bi ết m ột ho ặc m ột s ố khóa chia s ẻ 
 Điều c ần ch ứng minh ở đây là: Cho p, q, p , q 
 1 1 gi ữa A và B c ũng không cho phép m ột đối t ượng 
là các s ố nguyên t ố th ỏa mãn: q (| p − )1 , n = p1 × q1 , th ứ 3 nào đó có th ể tính được các khóa khác c ũng 
 (p− 1) / q * ∗ a được thi ết l ập b ởi A và B. 
n > p, g = α mod p , α ∈ Z , H :{} 0,1 Z h với: 
 p - Tính bí m ật v ề phía tr ước (forward secrecy ): 
|q |≤ |h |< |p | x1A
 , 1< x1A , x1B < q , y A = g mod p , vi ệc tính các khóa bí m ật chia s ẻ đã được thi ết l ập 
 x1B −1
yB = g mod p , x2 A = (yA ) mod ϕ()nA , tr ước đó b ởi A và B là không th ể th ực hi ện được, dù 
 −1 , , các khóa bí m ật c ủa A và B ( ) b ị 
x2B = (yB ) mod ϕ()nB 1 < kA ,kB < q x1A, x2 A, x1B , x2B
 y
 k B yA
 A , kB . lộ. 
RA = (g mod p) mod nB RB = (g mod p) mod nA
 x Các tính ch ất an toàn nói trên th ực ch ất được 
Nếu: S = (y ) A mod p , S = (y )xB mod p , 
 A B B A đảm b ảo b ởi m ức độ an toàn của thu ật toán tr ước 
 k
 x2 A A , , 
K AB = (()RB mod nA ) mod p EA = H(K AB || S A ) các d ạng t ấn công: 
 k
 x2B B , thì: + T ấn công khóa bí m ật chia s ẻ: 
K BA = (()RA mod nB ) mod p EB = H (KBA || SB )
K AB = K BA và EA = EB . Để tính được khóa K AB , t ừ (5.5) cho th ấy k ẻ t ấn 
 Ch ứng minh : 
 công c ần ph ải tính được x2 A và kA . Để tính x2 A 
 Th ật v ậy, t ừ (5.3) và (5.3) ta có: 
 k cần ph ải gi ải được IFP , còn để tính k từ (5.2) 
 x2 A A (n) A
 K AB = (()RB mod nA ) mod p
 tr ước tiên c ần ph ải gi ải được bài toán phân tich s ố 
 y. x k A (5.10) 
 kB BB2 x
 = ()()g mod p mod nA mod p 2 A
 IFP (n) rồi tính: X = (RB ) mod nA ho ặc ph ải gi ải 
 k
 kB A kAB. k
 = ()g mod p mod p = g mod p được bài toán khai c ăn RSAP (n,e) để tìm: 
 Mặt khác, t ừ (5.2) và (5.8) ta l ại có: X = RSAP (R ). Sau đó ph ải gi ải ti ếp bài toán 
 (,)nAA y B
 k
 K = R x2 B mod n B mod p
 BA (()A B ) logarit r ời r ạc DLP để tìm k : . 
 (p,g) A k A = DLP ()p, g (RA )
 y. x kB (5.11) 
 kA BA2
 = ()()g mod p mod nB mod p Vi ệc tính KBA c ũng ph ải được th ực hi ện các b ước 
 k
 = ()g k A mod p B mod p = g kAB. k mod p tươ ng t ự nh ư v ậy. Nh ư v ậy, độ an toàn c ủa thu ật 
 Từ (5.10) và (5.11) suy ra điều c ần ch ứng minh toán tr ước d ạng t ấn công khóa bí m ật chia s ẻ được 
 đảm b ảo b ằng tính khó c ủa vi ệc gi ải đồng th ời 2 bài 
th ứ nh ất: K AB = K BA 
 toán: IFP (n) và DLP (p,g) . 
 Từ (5.1) và (5.4) ta có: + T ấn công gi ả m ạo: 
 S = (y )x A mod p
 A B (5.12) M ộ t k ẻ gi ả m ạ o C mu ố n m ạ o danh A để t ạo 
 x xA x. x
 = ()g B mod p mod p = g AB mod p khóa bí m ật chia s ẻ v ới B ho ặc m ạo danh B để chia 
 Từ (5.1) và (5.7) ta l ại có: sẻ khóa bí m ật v ới A thì c ần ph ải tính được E A ho ặc 
 xB E . Tuy nhiên, t ừ (5.6) và (5.9) cho th ấy th ực hi ện 
 SB = (y A ) mod p (5.13) B 
 x được vi ệc đó thì k ẻ t ấn công t ối thi ểu ph ải tính được 
 = ()g xA mod p B mod p = g xAB. x mod p
 KAB ho ặc KBA . Do đó, độ an toàn c ủa thu ật toán 
 Từ (5.12) và (5.13) suy ra: S A = SB (5.14) tr ướ c d ạ ng t ấ n công gi ả m ạ o c ũ ng s ẽ đượ c đả m b ả o 
 Từ (5.6), (5.9) và (5.14) suy ra điều c ần ch ứng bằng tính khó c ủa vi ệc gi ải đồng th ời 2 bài toán: 
minh th ứ hai: EA = HK( AB || SA ) = HK( BA || SB ) = EB IFP (n) và DLP (p,g) . 
 c) Độ an toàn c ủa giao th ức 
 III. KẾT LU ẬN 
 Giao th ức được đề xu ất b ảo đảm các tính ch ất 
của m ột giao th ức trao đổi khóa an toàn: Bài báo đề xu ất xây d ựng một hệ m ật khóa công 
 - Xác th ực th ực th ể ( entity authentication ): ở khai bao g ồm các thu ật toán mã hóa, ch ữ ký s ố và 
giao th ức này vi ệc ki ểm tra điều ki ện EA = EB cho giao th ức trao đổi khóa an toàn cho các h ệ m ật khóa 
phép các đối t ượng tham gia trao đổi khóa hoàn toàn đối x ứng. Qua phân tích đánh giá cho th ấy các thu ật 
có th ể xác th ực được danh tính c ủa nhau. toán c ủa h ệ m ật m ới đề xu ất có độ an toàn được đảm 
 - Xác th ực khóa hi ện ( explicit key bảo b ằng m ức độ khó c ủa vi ệc gi ải đồng th ời 2 bài 
authentication ): C ũng ch ỉ bằng vi ệc ki ểm tra điều toán: bài toán phân tích m ột s ố nguyên l ớn ra các 
ki ện EA = EB , A hoàn toàn có th ể kh ẳng định B đã th ừa s ố nguyên t ố và bài toán logarit r ời r ạc trên Z p, 
tạo được khóa bí m ật chia s ẻ v ới mình và B c ũng có ho ặc: bài toán phân tích m ột s ố nguyên l ớn ra các 
th ể kh ẳng định được điều t ươ ng t ự nh ư th ế v ới A. th ừa s ố nguyên t ố và bài toán khai c ăn trên vành Z n. 
 7 
 Hội th ảo l ần th ứ III: M ột s ố v ấn đề ch ọn l ọc v ề an toàn an ninh thông tin – Đà N ẵng, 07/12/2018 
Hoàn toàn có th ể kh ẳng định r ằng không có b ất k ỳ [13] Lưu H ồng D ũng, Hoàng Th ị Mai, Nguy ễn H ữu M ộng, 
ki ểu t ấn công nào vào h ệ m ật thành công được mà ” M ột d ạng l ược đồ ch ữ ký xây d ựng trên bài toán phân tích 
 số”, K ỷ y ếu H ội ngh ị Qu ốc gia l ần th ứ VIII v ề Nghiên c ứu 
không ph ải gi ải được đồng th ời 2 bài toán khó nêu cơ b ản và ứng d ụng Công Ngh ệ thông tin (FAIR 2015); Hà 
trên, do đó hệ m ật m ới đề xu ất có th ể phù h ợp v ới Nội 09-10/07/2015. ISBN: 978-604-913-397-8. 
các ứng d ụng yêu c ầu cao về độ an toàn trong th ực [14] Luu Hong Dung, Le Dinh Son, Ho Nhat Quang and 
tế. Nguyen Duc Thuy,” DEVELOPING DIGITAL 
 SIGNATURE SCHEMES BASED ON DISCRETE 
 LOGARITHM PROBLEM”, The 8th National Conference 
 TÀI LI ỆU THAM KH ẢO 
 on Fundamental and Applied IT Research (FAIR 2015). Ha 
[1] Q. X. WU, Y. X. Yang and Z. M. HU, "New signature Noi 09-10/07/2015 ISBN: 978-604-913-397-8. 
 schemes based on discrete logarithms and factoring", [15] Lưu H ồng D ũng, Nguy ễn Đức Th ụy, Nguy ễn L ươ ng Bình 
 Journal of Beijing University of Posts and và T ống Minh Đức, “Phát tri ển thu ật toán m ật mã khóa 
 Telecommunications, vol. 24, pp. 61-65, January 2001. công khai d ựa trên bài toán logarit rời r ạc”, H ội ngh ị khoa 
[2] Z. Y. Shen and X. Y. Yu, "Digital signature scheme based học Qu ốc gia l ần th ứ IX v ề Nghiên c ứu c ơ b ản và ứng d ụng 
 on discrete logarithms and factoring", Information Công ngh ệ thông tin (FAIR 2016). ISBN: 978-604-913-
 Technology, vol. 28,pp. 21-22, June 2004. 397-8. 2016. 
[3] Shimin Wei, “Digital Signature Scheme Based on Two [16] Lưu H ồng D ũng, Nguy ễn Đức Th ụy, Lê Đình S ơn và 
 Hard Problems”, IJCSNS International Journal of Computer Nguy ễn Th ị Thanh Th ủy, “ Một ph ươ ng pháp xây d ựng 
 Science and Network Security, VOL.7 No.12, December lược đồ ch ữ ký s ố d ựa trên bài toán logarit r ời r ạc”, H ội 
 2007. ngh ị khoa h ọc Qu ốc gia l ần th ứ IX v ề Nghiên c ứu c ơ b ản 
[4] Eddie Shahrie Ismail, Tahat N.M.F., Rokiah. R. Ahmad, “A và ứng d ụng Công ngh ệ thông tin (FAIR 2016). ISBN: 978-
 New Digital Signature Scheme Based on Factoring and 604-913-397-8. 2016. 
 Discrete Logarithms”, Journal of Mathematics and [17] Lưu H ồng D ũng, Nguy ễn Đức Th ụy, Nguy ễn V ăn Phúc và 
 Statistics, 04/2008; 12(3). DOI: Đỗ Anh Tu ấn, “M ột ph ươ ng pháp xây d ựng thu ật toán ch ữ 
 10.3844/jmssp.2008.222.225 Source:DOAJ. ký s ố”, H ội th ảo l ần th ứ I: M ột s ố v ấn đề ch ọn l ọc v ề an 
[5] Qin Yanlin , Wu Xiaoping,“ New Digital Signature Scheme toàn, an ninh thông tin (SoIS 2016), 11/2016. 
 Based on both ECDLP and IFP”, Computer Science and [18] Nguyen Duc Thuy and Luu Hong Dung, “A New 
 Information Technology, 2009. ICCSIT 2009. 2nd IEEE Construction Method of Digital Signature Algorithms”, 
 International Conference on, 8-11 Aug. 2009, E-ISBN : IJCSNS International Journal of Computer Science and 
 978-1-4244-4520-2, pp 348 - 351. Network Security. Vol. 16 No. 12 pp. 53-57, December 
[6] Swati Verma1, Birendra Kumar Sharma, “A New Digital 2016. ISSN: 1738 - 7906. 
 Signature Scheme Based on Two Hard Problems”, [19] Nguyen Duc Thuy, Nguyen Tien Giang, Le Dinh Son and 
 International Journal of Pure and Applied Sciences and Luu Hong Dung, “ A Design Method of Digital Signature 
 Technology, ISSN 2229 – 6107, Int. J. Pure Appl. Sci. Scheme Based on Discrete Logarithm Problem”, IJCSNS 
 Technol., 5(2) (2011), pp. 55-59. International Journal of Computer Science and Network 
[7] Sushila Vishnoi , Vishal Shrivastava, ”A new Digital Security. Vol. 17 No. 2 pp. 214-218, February 2017. ISSN: 
 Signature Algorithm based on Factorization and Discrete 1738 - 7906. 
 Logarithm problem”, International Journal of Computer [20] Lưu H ồng D ũng, Nguy ễn V ĩnh Thái và Nguy ễn Đức Th ụy, 
 Trends and Technology, volume 3, Issue 4, 2012. “ Phát tri ển h ệ m ật khóa công khai t ừ h ệ mã Pohlig - 
[8] A.N. Berezin, N.A. Moldovyan, V.A. Shcherbacov, Hellman “, H ội th ảo l ần th ứ II: M ột s ố v ấn đề ch ọn l ọc v ề 
 "Cryptoschemes Based on Difficulty of Simultaneous an toàn, an ninh thông tin (SoIS 2017), Tp. HCM 
 Solving Two Different Difficult Problems", Computer 03/12/2017. 
 Science Journal of Moldova, vol.21, no.2(62), 2013. [21] Ph ạm V ăn Hi ệp, Nguy ễn H ữu M ộng và L ưu H ồng 
[9] Lưu H ồng D ũng, Tr ần Trung D ũng, T ống Minh Dũng,” MỘT THU ẬT TOÁN CH Ữ KÝ XÂY D ỰNG 
 Đức, “Nghiên c ứu xây d ựng h ệ tích h ợp m ật mã khóa công DỰA TRÊN TÍNH KHÓ C ỦA VI ỆC GI ẢI ĐỒNG TH ỜI 
 khai - ch ữ ký s ố”, T ạp chí Khoa h ọc và K ỹ thu ật (H ọc vi ện HAI BÀI TOÁN PHÂN TÍCH S Ố VÀ LOGARIT R ỜI 
 KTQS), s ố 149 (08-2012). ISSN: 1859 - 0209., 01/08/2012. RẠC “, T ẠP CHÍ KHOA H ỌC VÀ CÔNG NGH Ệ ĐẠI 
[10] Lưu H ồng D ũng, “Phát tri ển thu ật toán m ật mã khóa công HỌC ĐÀ N ẴNG, S Ố 7(128).2018. ISSN 1859-1531. 
 khai d ựa trên h ệ m ật El Gamal”, Chuyên san Các công trình [22] Nguy ễn L ươ ng Bình, L ưu H ồng D ũng, T ống Minh 
 nghiên c ứu, phát tri ển và ứng d ụng CNTT và TT, B ộ TT và Đức, “M ột ph ươ ng pháp phát tri ển h ệ m ật khóa công khai”, 
 TT, t ập V-1, số 8(28) (12-2012). ISSN: 1859 - 3526., pp. 8, Hội ngh ị Qu ốc gia lần th ứ XI về Nghiên c ứu c ơ b ản và ứng 
 01/12/2012. dụng CNTT (FAIR 2018). ISBN: 978-604-913-397-8. Hà 
[11] Lưu H ồng D ũng, Ngô Đă ng Ti ến, Tr ần Trung D ũng, V ũ Nội 8/2018. 
 Tất Th ắng, “Phát tri ển m ột s ố thu ật toán m ật mã khóa công [23] R. L. Rivest, A. Shamir, and L. M. Adleman, “A Method 
 khai”, H ội th ảo qu ốc gia l ần th ứ XV: M ột s ố v ấn đề ch ọn for Obtaining Digital Signatures and Public Key 
 lọc c ủa Công ngh ệ Thông tin và Truy ền thông. Hà N ội 3- Cryptosystems”, Commun. of the ACM, Vol. 21, No. 2, 
 4/12/2012. ISBN: 978 - 604 - 67 - 0645 - 8., pp. 6, 1978, pp. 120-126. 
 04/12/2012. [24] National Institute of Standards and Technology, NIST FIPS 
 PUB 186-4. Digital Signature Standard, U.S. Department of 
[12] Lưu H ồng D ũng, H ồ Ng ọc Duy, Nguy ễn Ti ền Giang and 
 Commerce, 2013. 
 Nguy ễn Th ị Thu Th ủy, “ Phát tri ển m ột d ạng l ược đồ ch ữ 
 ký s ố m ới”, H ội th ảo qu ốc gia l ần th ứ XVI: M ột s ố v ấn đề [25] T. ElGamal, “A public key cryptosystem and a signature 
 ch ọn l ọc của Công ngh ệ Thông tin và Truy ền thông, Đà scheme based on discrete logarithms”, IEEE Transactions 
 Nẵng - 11/2013. ISBN: 978 - 604 - 67 - 0645 - 8. on Information Theory. 1985, Vol. IT-31, No. 4. pp.469–
 472. 
 8 
Hội th ảo l ần th ứ III: M ột s ố v ấn đề ch ọn l ọc v ề an toàn an ninh thông tin – Đà N ẵng, 07/12/2018 
 9 
Hội th ảo l ần th ứ III: M ột s ố v ấn đề ch ọn l ọc v ề an toàn an ninh thông tin – Đà N ẵng, 07/12/2018 
 10