Xem mẫu
- Hội+ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJYj&{QJ1JKӋ7K{QJ7LQ (&,7
-
Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
PHÁT TRIӆN THUҰT TOÁN XÁC LҰP KHÓA
CHO CÁC Hӊ MҰT MÃ KHÓA ĈӔI XӬNG
Hoàng Văn ViӋt1, NguyӉn Ĉӭc Thөy2, Bùi ThӃ TruyӅn3, Lѭu Hӗng DNJng3.
1
Bӝ tѭ lӋnh Thông tin liên lҥc, 2Trѭӡng Cao ÿҷng Kinh tӃ - Kӻ thuұt TP. Hӗ Chí Minh, 3Hӑc viӋn Kӻ thuұt Quân sӵ
Email: viethv76@gmail.com, thuyphulam2013@gmail.com, buithetruyen@gmail.com, luuhongdung@gmail.com
Abstract — Bài báo ÿӅ xuҩt xây dӵng 2 dҥng thuұt toán xác lұp trình thiӃt lұp khóa chung bҵng các thuұt toán này chӍ cҫn thӵc
khóa mӟi cho các hӋ mұt mã khóa ÿӕi xӭng. Các thuұt toán mӟi hiӋn 1 lҫn truyӅn dӳ liӋu nên có thӇ sӁ phù hӧp vӟi các ӭng
ÿӅ xuҩt có ѭu ÿiӇm là viӋc thiӃt lұp khóa ÿѭӧc thӵc hiӋn chӍ sau dөng ÿòi hӓi tӕc ÿӝ thӵc hiӋn cao.
mӝt lҫn truyӅn thông tin thiӃt lұp khóa. Hѫn nӳa, khóa bí mұt
còn ÿѭӧc xác thӵc vӅ nguӗn gӕc nên các thuұt toán ÿѭӧc ÿӅ xuҩt
ӣ ÿây có thӇ chӕng lҥi các kiӇu tҩn công giҧ mҥo rҩt hiӋu quҧ. II. PHÁT TRIӆN THUҰT TOÁN XÁC LҰP KHÓA MӞI
Bài báo cNJng trình bày các phân tích, ÿánh giá vӅ mӭc ÿӝ an toàn CHO CÁC Hӊ MҰT KHÓA ĈӔI XӬNG
cӫa thuұt toán mӟi ÿӅ xuҩt, cho thҩy khҧ năng ӭng dөng cӫa nó 2.1 Thuұt toán xác lұp khóa dҥng 1
trong thӵc tӃ. 2.1.1 Thӫ tөc hình thành các tham sӕ hӋ thӕng và khóa công
khai
Keywords- Symmetrical Key Cryptography System, Key
Establishment, Key Agreement Protocols, Key Exchange Protocol,
Thӫ tөc bao gӗm các bѭӟc nhѭ sau:
Key Transport Protocols. 1 - Chӑn mӝt nhóm Zp vӟi p là mӝt sӕ nguyên tӕ lӟn sao
cho bài toán logarit trong Z ∗p là khó giҧi và g là phҫn tӱ
I. ĈҺT VҨN Ĉӄ
sinh cӫa Z ∗p .
Trong lƭnh vӵc bҧo mұt thông tin, các hӋ mұt mã khóa ÿӕi
xӭng (Symmetrical Key Cryptography System) có ѭu thӃ lӟn 2 - Khóa riêng x cӫa các ÿӕi tѭӧng tham gia trao ÿәi khóa
vӅ tӕc ÿӝ thӵc hiӋn so vӟi các hӋ mұt mã khóa công khai ÿѭӧc FKӑn là mӝt sӕnguyên thӓa mãn: 1 < x < ( p − 1) .
(Public Key Cryptography System), vì vұy chúng thѭӡng ÿѭӧc 3 - Khóa công khai tѭѫng ӭng y cӫa các ÿӕi tѭӧng tham
sӱ dөng ÿӇ mã hóa các khӕi dӳ liӋu có kích thѭӟc lӟn, ÿһc biӋt gia trao ÿәi khóa ÿѭӧc tính theo công thӭc:
là trong các giao dӏch trӵc tuyӃn. y = g x mod p (1.1)
Trong các hӋ mұt mã khóa ÿӕi xӭng, viӋc thiӃt lұp mӝt 4- Công khai các giá trӏ: p, g, y. Giӳ bí mұt: x.
khóa chung (Key Establishment) cho cҧ bên gӱi/mã hóa và bên 2.1.2 Thӫ tөc xác lұp khóa
nhұn/giҧi mã là mӝt vҩn ÿӅ rҩt quan trӑng, phӭc tҥp và thѭӡng Giҧ sӱ các ÿӕi tѭӧng tham gia trao ÿәi khóa ӣ ÿây là A và
ÿѭӧc hiӋn bҵng: a) các giao thӭc thӓa thuұn khóa (Key B. Giҧ thiӃt các ÿӕi tѭӧng A và B cNJng ÿã thӕng nhҩt sӱ dөng
Agreement Protocols), ӣ ÿó mӛi bên tham gia sӁ tҥo ra thông mӝt thuұt toán mұt mã khóa ÿӕi xӭng (ví dө: DES, AES,...) ÿӇ
tin ÿӇ thӓa thuұn cho viӋc thiӃt lұp 1 khóa bí mұt dùng chung mã hóa thông tin (văn bҧn, tài liӋu,...) cҫn trao ÿәi vӟi nhau.
rӗi trao ÿәi cho nhau, vì thӃ các giao thӭc thӓa thuұn khóa còn Ĉӕi tѭӧng A có khóa riêng là xA, khóa công khai tѭѫng ӭng là
ÿѭӧc gӑi là giao thӭc trao ÿәi khóa (Key Exchange Protocol) yA; ÿӕi tѭӧng B có khóa riêng là xB và khóa công khai cӫa B
mà giao thӭc ÿҫu tiên thuӝc loҥi này ÿѭӧc ÿӅ xuҩt bӣi W. là yB. Khóa công khai cӫa A và B ÿѭӧc hình thành theo Thͯ
Diffie và M. Hellman vào năm 1976 và ÿѭӧc gӑi là giao thӭc tͭc hình thành các tham s͙ h͏ th͙ng và khóa công khai ӣ Mͭc
trao ÿәi khóa Diffie-Hellman (Diffie-Hellman Key Exchange 2.1.1. Ӣ ÿây yA và yB cҫn phҧi ÿѭӧc chӭng thӵc bӣi mӝt CA
Protocol) [1]; b) các giao thӭc chuyӇn khóa (Key Transport
(Certificate Authority) ÿáng tin cұy. Thuұt toán cho phép các
Protocols), trong ÿó khóa bí mұt ÿѭӧc sinh bӣi mӝt trong hai
ÿӕi tѭӧng A và B thiӃt lұp mӝt khóa bí mұt chung K, bao gӗm
ÿӕi tѭӧng gӱi hoһc nhұn, rӗi ÿѭӧc mã hóa và truyӅn ÿӃn ÿӕi
tѭӧng kia bҵng mӝt thuұt toán mұt mã khóa công khai nhѭ các bѭӟc nhѭ sau:
RSA [2] hay ElGamal [3]. Tuy nhiên, thӓa thuұn khóa bҵng B˱ͣc 1: chӍ thӵc hiӋn bӣi A.
giao thӭc Diffie-Hellman hay viӋc sӱ dөng các thuұt toán mұt 1 - Chӑn mӝt giá trӏ ngүu nhiên k thӓa mãn:
mã khóa công khai nhѭ RSA hay ElGamal trong các giao thӭc 1 < k < ( p − 1) . Tính giá trӏ R theo công thӭc:
chuyӇn khóa ÿӅu có chung mӝt nhѭӧc ÿiӇm căn bҧn là không k
R = ( y A ) mod p (1.2)
có khҧ năng chӕng lҥi mӝt sӕ dҥng tҩn công giҧ mҥo nhѭ tҩn 2 - Gӱi R cho B.
công “kҿ ÿӭng giӳa” (Man-In-the-Middle Attack) [4-6], do
B˱ͣc 2: ÿѭӧc thӵc hiӋn bӣi cҧ A và B.
chúng không có cѫ chӃ xác thӵc bҧn tin khi nhұn ÿѭӧc. Bài báo
ÿӅ xuҩt xây dӵng mӝt dҥng thuұt toán xác lұp khóa mӟi, ѭu 1 - A hình thành khóa bí mұt chung KAB theo công thӭc:
ÿiӇm cӫa các thuұt toán mӟi ÿӅ xuҩt là có khҧ năng xác thӵc vӅ K AB = ( y B )
(k +1). x
A
mod p (1.3)
nguӗn gӕc cӫa khóa bí mұt ÿѭӧc tҥo ra, nên có thӇ chӕng ÿѭӧc 2 - B hình thành khóa bí mұt chung KBA theo công thӭc:
các kiӇu tҩn công giҧ mҥo ÿã biӃt trong thӵc tӃ. Mһt khác, quá x
K BA = (R × y A ) mod p
B (1.4)
ISBN: 978-604-67-0635-9 232
- Hội+ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJYj&{QJ1JKӋ7K{QJ7LQ (&,7
-
Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Khóa bí mұt chung K cӫa A và B ӣ ÿây là: K BA = (R × y A ) B mod p
x
K = K AB = K BA xB (1.6)
= g k . x A mod p × g x A mod p
( ) mod p
Chú ý: = (g ( k +1). x A xB
mod p mod p = g (k +1). x A . x B mod p
)
Có thӇ gia tăng tính ngүu nhiên cho khóa bí mұt chung Tӯ (1.5) và (1.6) suy ra ÿiӅu cҫn chӭng minh là:
cӫa A và B bҵng cách sӱ dөng hàm băm (Hash function) H(.) K AB = K BA .
nhѭ sau:
2.1.4 Mӭc ÿӝ an toàn cӫa thuұt toán mӟi ÿӅ xuҩt
K A = H ( K AB )
và: Mӭc ÿӝ an toàn cӫa thuұt toán mӟi ÿӅ xuҩt có thӇ ÿѭӧc
ÿánh giá qua các khҧ năng nhѭ sau:
K B = H ( K BA )
Khi ÿó khóa bí mұt chung cӫa A và B sӁ là: a). Kh̫ năng ch͙ng ṱn công làm l͡ khóa bí m̵t
K = KA = KB
Tӯ (1.3) và (1.4) cho thҩy, mӝt ÿӕi tѭӧng thӭ 3 (kҿ tҩn công)
Ӣ ÿây: KA là khóa bí mұt chung do bên A tҥo ra, còn KB là muӕn tính ÿѭӧc khóa bí mұt chung (K) thì cҫn phҧi biӃt ÿѭӧc k
khóa bí mұt chung ÿѭӧc tҥo ra phía bên B. và xA hoһc xB nhӡ giҧi (1.1) và (1.2). ViӋc giҧi (1.1) và (1.2)
Ví dө: Giҧ sӱ A và B thӕng nhҩt sӱ dөng hӋ mã AES vӟi thӵc chҩt là giҧi bài toán logarit rӡi rҥc - DLP (Discrete
khóa 128 bit hoһc 256 bit ÿӇ trao ÿәi thông tin mұt. Khi ÿó, A Logarithm Problem) [4-6]. Nhѭ vұy, khҧ năng chӕng tҩn công
và B có thӇ sӱ dөng hàm băm MD 5 hoһc SHA-256 ÿӇ gia làm lӝ khóa bí mұt chung cӫa thuұt toán mӟi ÿӅ xuҩt phө thuӝc
tăng tính ngүu nhiên cho khóa mұt nhѭ sau: vào mӭc ÿӝ khó cӫa bài toán logarit rӡi rҥc. HiӋn tҥi, bài toán
K A = MD5( K AB ) hoһc: K A = SHA − 256( K AB ) logarit rӡi rҥc vүn ÿѭӧc coi là bài toán khó nӃu tham sӕ p và
và: các giá trӏ k , xA , xB ÿѭӧc chӑn ÿӫ lӟn ÿӇ tҩn công theo kiӇu
“vét cҥn” là không khҧ thi trong các ӭng dөng thӵc tӃ.
K B = MD5( K BA ) hoһc: K B = SHA − 256( K BA )
Nh̵n xét: b). Kh̫ năng ch͙ng ṱn công gi̫ m̩o
Ӣ thuұt toán mӟi ÿӅ xuҩt, khóa bí mұt chung cӫa 2 ÿӕi
tѭӧng A và B là: K = K AB = K BA = g ( k +1). x . x mod p , còn thông
A B Giҧ sӱ C là kҿ tҩn công giҧ mҥo, vҩn ÿӅ ÿһt ra là C có thӇ
mҥo danh A ÿӇ thiӃt lұp ÿѭӧc khóa bí mұt chung vӟi B hoһc
tin A gӱi cho B là: R = g k mod p . Nhѭ vұy, thông tin mà A C mҥo danh B ÿӇ thiӃt lұp khóa bí mұt chung vӟi A bҵng
chuyӇn cho B không phҧi là khóa bí mұt nhѭ trong các giao thuұt toán mӟi ÿӅ xuҩt hay không?
thӭc chuyӇn khóa (sӱ dөng mұt mã khóa công khai nhѭ RSA, Tr˱ͥng hͫp thͱ nh̭t, C mҥo danh A ÿӇ thiӃt lұp khóa bí
El Gamal,...) mà chӍ là thông tin ÿӇ thiӃt lұp khóa, tӯ ÿó B sӁ mұt chung vӟi B. Ĉҫu tiên C chӑn ngүu nhiên mӝt giá trӏ k
tҥo nên khóa bí mұt chung cho mình. Vì vұy, thuұt toán mӟi thӓa mãn: 1 < k < p − 1 và tính: R = g k mod p , rӗi gӱi R cho B.
ÿӅ xuҩt không phҧi là mӝt giao thӭc chuyӇn khóa ÿã ÿѭӧc biӃt Khi nhұn ÿѭӧc R, B sӁ tính khóa bí mұt chung vӟi A theo
ÿӃn trong thӵc tӃ. Mһt khác, thông tin dùng ÿӇ thiӃt lұp khóa
(1.4) và ÿѭӧc: K BA = g (k +1). xA . xB mod p . Trong khi ÿó, C cNJng
bí mұt chung ӣ ÿây chӍ ÿѭӧc tҥo ra bӣi 1 trong 2 bên và gӱi
cho bên kia mà không phҧi do cҧ 2 cùng tҥo ra rӗi trao ÿәi cho tính khóa bí mұt chung vӟi B theo (1.3), nhѭng do không biӃt
nhau nhѭ ӣ các giao thӭc thӓa thuұn khóa kiӇu Diffie- xA, nên C phҧi chӑn ngүu nhiên 1 giá trӏ ngүu nhiên x∗A ÿӇ
Hellman. Tӯ ÿó cho thҩy thuұt toán ÿѭӧc ÿӅ xuҩt ӣ ÿây là mӝt tính KAB, nên sӁ nhұn ÿѭӧc: K AB = g (k +1). x . x mod p . Do:
∗
A B
dҥng giao thӭc xác lұp khóa mӟi cho các hӋ mұt khóa ÿӕi
xӭng. x∗A ≠ x A , nên: K AB ≠ K BA , nghƭa là C ÿã thҩt bҥi trong viӋc
2.1.3. Tính ÿúng ÿҳn cӫa thuұt toán mӟi ÿӅ xuҩt mҥo danh A ÿӇ thiӃt lұp khóa bí mұt chung vӟi B. CNJng cҫn
ĈiӅu cҫn chӭng minh ӣ ÿây là: cho p là sӕ nguyên tӕ và g phҧi nhҩn mҥnh rҵng, viӋc lӵa chӑn x A ÿӇ x A = x A ӣ ÿây
∗ ∗
là phҫn tӱ sinh cӫa nhóm Z *p , 1 < x A , xB < ( p − 1) , ÿѭӧc loҥi trӯ, vì ÿiӅu ÿó xҧy ra cNJng ÿӗng nghƭa vӟi viӋc giҧi
y A = g x A mod p , yB = g x mod p ,
ÿѭӧc bài toán logarit rӡi rҥc.
B
1 < k < ( p − 1) . NӃu:
(k +1). x A Tr˱ͥng hͫp thͱ hai, C mҥo danh B ÿӇ thiӃt lұp khóa
R = ( y A ) mod p , K AB = ( y B ) mod p , K BA = (R × y A )x mod p
k
chung vӟi A. Khi ÿó, A sӁ chӑn k thӓa mãn: 1 < k < p − 1 ÿӇ
B
thì: K AB = K BA . tính R theo (1.2) rӗi gӱi cho B, mà thӵc chҩt ngѭӡi nhұn ӣ
ÿây là C. Sau ÿó A sӁ tính khóa bí mұt chung KAB theo (1.3).
Chͱng minh: Do C mҥo danh B, nên A sӁ sӱ dөng khóa công khai cӫa B ÿӇ
Thұt vұy, tӯ (1.1) và (1.3) ta có: tính khóa bí mұt chung và nhұn ÿѭӧc:
K AB = ( y B )
(k +1). x A
mod p K AB = g ( k +1). x A . xB
mod p . Khi nhұn ÿѭӧc R, C tính khóa bí
(1.5)
(k +1). x A (k +1). x A . x B mұt chung vӟi A theo (1.4), ÿiӅu cҫn chú ý ӣ ÿây là do C
= (g mod p )
xB
mod p = g mod p
không biӃt ÿѭӧc khóa bí mұt xB cӫa B nên C phҧi chӑn ngүu
Mһt khác, tӯ (1.1), (1.2) và (1.4) ta lҥi có:
*
nhiên mӝt giá trӏ x B vӟi xác suҩt ÿӇ xB∗ = xB là rҩt nhӓ. Do
ÿó giá trӏ KBA mà C nhұn ÿѭӧc ӣ ÿây sӁ là:
K BA = g ( k +1). x A . xB mod p . DӉ dàng thҩy rҵng: K AB ≠ K BA do
∗
233
- Hội+ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJYj&{QJ1JKӋ7K{QJ7LQ (&,7
-
Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
xB∗ ≠ xB . Nói cách khác, C ÿã không thiӃt lұp ÿѭӧc khóa K BA = ( R × y A ) xB mod p (2.8)
chung vӟi A. Khóa bí mұt chung K cӫa A và B ӣ ÿây là:
Nhѭ vұy là trong cҧ 2 trѭӡng hӧp C ÿӅu không ÿҥt ÿѭӧc K = K AB = K BA
mөc ÿích giҧ mҥo cӫa mình. Nh̵n xét:
2.2 Thuұt toán xác lұp khóa dҥng 2 - Tѭѫng tӵ thuұt toán ÿӅ xuҩt trong Mͭc 2.1, thuұt toán ÿӅ
2.2.1 Thӫ tөc hình thành tham sӕ hӋ thӕng và khóa xuҩt ӣ ÿây cNJng là mӝt dҥng giao thӭc xác lұp khóa mӟi mà
không phҧi là các dҥng giao thӭc chuyӇn khóa hay thӓa thuұn
Thӫ tөc bao gӗm các bѭӟc nhѭ sau: khóa ÿã biӃt trong thӵc tӃ.
1 - Sinh 2 sӕ nguyên tӕ lӟn và mҥnh: p và q, sao cho: - Thay vì gӱi cho B giá trӏ R nhѭ ӣ thuұt toán dҥng 1, ӣ
q | ( p − 1) hay: p = N × q + 1 , vӟi N là sӕ nguyên. thuұt toán dҥng này A gӱi cho B cһp (E,S) ÿѭӧc tҥo ra tӯ R và
2 - Chӑn g = α ( p −1) / q mod p , là phҫn tӱ sinh có bұc q cӫa khóa bí mұt xA cӫa mình theo (2.3) và (2.4). Nhӡ ÿó B có thӇ
*
nhóm Zp , nghƭa là: 1 < g < p và: g q ≡ 1 mod p , ӣ khôi phөc lҥi giá trӏ R tӯ cһp (E,S) nhұn ÿѭӧc và khóa công
khai yA cӫa A theo (2.6). Tӯ giá trӏ R này (trong B˱ͣc 2 ÿѭӧc
*
ÿây: α∈Zp . ký hiӋu là R ), B sӁ tҥo ÿѭӧc khóa bí mұt dùng chung vӟi A.
Vҩn ÿӅ quan trӑng là ӣ chӛ, R ÿѭӧc khôi phөc tӯ (E,S) nhӡ
3 - Khóa riêng x ÿѭӧc Kunh WKjnh bҵng Fich FKӑn sӕ
khóa công khai cӫa A theo (2.6) chӭng tӓ rҵng (E,S) phҧi ÿѭӧc
nguyên thӓa mãn: 1 < x < q .
A tҥo ra tӯ khóa bí mұt cӫa mình theo (2.3) và (2.4). ĈiӅu ÿó
4 - Khóa công khai ÿѭӧc tính theo công thӭc: có nghƭa là (E,S) và do ÿó khóa bí mұt mà B tҥo ÿѭӧc (KBA)
y = g x mod p (2.1) phҧi có nguӗn gӕc tӯ A. Ĉây chính là cѫ chӃ xác thӵc nguӗn
5 - Công khai các giá trӏ: p, g, y. Giӳ bí mұt: x. gӕc khóa bí mұt cӫa thuұt toán mӟi ÿӅ xuҩt, nhӡ ÿó có thӇ
2.2.2 Thӫ tөc xác lұp khóa chӕng ÿѭӧc các kiӇu tҩn công giҧ mҥo khóa bí mұt.
- Trong B˱ͣc 2 cӫa thuұt toán mӟi ÿӅ xuҩt, B chӍ tҥo khóa
Các ÿӕi tѭӧng cҫn trao ÿәi thông tin mұt cùng thӕng nhҩt bí mұt chung vӟi A khi kiӇm tra thҩy thӓa mãn ÿiӅu kiӋn:
chӑn các tham sӕ p , q và g rӗi chӑn khóa riêng và tính khóa E = E . Tӯ (2.3), (2.4), (2.6) và (2.7) cho thҩy ÿiӅu kiӋn này
công khai cӫa mình theo Thͯ tͭc hình thành khóa công khai ӣ chӍ ÿѭӧc thӓa mãn nӃu (E,S) ÿѭӧc truyӅn tӯ A sang B nguyên
Mͭc 2.2.1. Giҧ sӱ ÿӕi tѭӧng gӱi/mã hóa thông tin ký hiӋu là A vҽn mà không có bҩt kǤ sӵ thay ÿәi nào cҧ. Mӝt sӵ thay ÿәi
có khóa bí mұt là xA, khóa công khai tѭѫng ӭng cӫa A là yA; giá trӏ cӫa E hoһc S hay ÿӗng thӡi cҧ hai ÿӅu dүn ÿӃn kӃt quҧ
Ĉӕi tѭӧng nhұn/giҧi mã thông tin ký hiӋu là B có khóa bí mұt là ÿiӅu kiӋn: E = E sӁ không ÿѭӧc thӓa mãn. ĈiӅu ÿó có nghƭa
là xB và khóa công khai cӫa B là yB. Ӣ ÿây yA và yB cNJng cҫn rҵng, nӃu ÿiӅu kiӋn ÿã chӍ ra ÿѭӧc thӓa mãn thì giá trӏ R ÿѭӧc
phҧi ÿѭӧc chӭng thӵc bӣi mӝt CA (Certificate Authority) tҥo ra ӣ phía bên A sӁ ÿѭӧc khôi phөc chính xác ӣ phía bên B
ÿáng tin cұy. Các ÿӕi tѭӧng A và B thӕng nhҩt sӱ dөng mӝt ( R = R ) và do ÿó khóa bí mұt chung KBA ÿѭӧc tҥo ra phía bên
thuұt toán mұt mã khóa ÿӕi xӭng (ví dө: DES, AES,...) ÿӇ mã B sӁ bҵng chính khóa bí mұt ÿѭӧc tҥo ra ӣ phía bên A. Nói
hóa thông tin (văn bҧn, tài liӋu,...) cҫn trao ÿәi vӟi nhau, khi khác ÿi, khóa bí mұt ÿã ÿѭӧc truyӅn toàn vҽn tӯ phía A sang
ÿó thuұt toán ÿӇ thiӃt lұp mӝt khóa bí mұt chung cho phép A cho phía B. Ĉây chính là cѫ chӃ xác thӵc tính toàn vҽn cӫa
mã hóa thông tin, B giҧi mã thông tin hoһc ngѭӧc lҥi, bao gӗm khóa bí mұt ӣ thuұt toán mӟi ÿӅ xuҩt dҥng 2.
các bѭӟc nhѭ sau: 2.2.3 Tính ÿúng ÿҳn cӫa thuұt toán ÿӅ xuҩt
B˱ͣc 1: ChӍ thӵc hiӋn bӣi A. ĈiӅu cҫn chӭng minh ӣ ÿây là: cho p, q là 2 sӕ nguyên tӕ
1 - Chӑn ngүu nhiên mӝt giá trӏ k thӓa mãn: 1 < k < q . ÿӝc lұp thӓa mãn: q | ( p − 1) , g = α ( p −1) / q mod p , α ∈ Z *p ,
2 - Tính giá trӏ R theo công thӭc:
1 < x A , xB < q , y A = g x mod p , y B = g xB mod p ,
A
1< k < q ,
k
R = ( y A ) mod p (2.2)
3 - Tính thành phҫn E theo công thӭc:
k
,
R = ( y A ) mod p E = R mod q , S = x A × (k − E ) mod q . NӃu:
mod p , R = g × ( y A ) mod p ,
x . (k +1 ) S E
E = R mod q (2.3) K AB = ( y B )
A
4 - Tính thành phҫn S theo công thӭc: , thì: và
x
K BA = (R × y A ) B mod p E = R mod q E =E
S = x A × (k − E ) mod q (2.4) K AB = K BA .
5 - Gӱi (E,S) cho ÿӕi tѭӧng B. Chӭng minh:
B˱ͣc 2: Ĉѭӧc thӵc hiӋn bӣi cҧ A và B. Thұt vұy, tӯ (2.1) và (2.4) ta có:
1 - A hình thành khóa bí mұt KAB theo công thӭc: E
x . ( k +1)
R = g S × ( y A ) mod p
K AB = ( y B ) A mod p (2.5) E
2 - B hình thành khóa bí mұt KBA theo các bѭӟc: = g x A .(k − E ) × g x A mod p
( ) mod p (2.9)
2.1 - Tính giá trӏ R theo công thӭc: = g ( k. xA
×g − xA . E
×g xA . E
)mod p
E
R = g S × ( y A ) mod p (2.6) k .xA
= g mod p
2.2 - Tính giá trӏ E theo công thӭc:
Tӯ (2.2) và (2.9) suy ra: R = R (2.10)
E = R mod q (2.7)
Tӯ (2.3), (2.7) và (2.10) suy ra ÿiӅu cҫn chӭng minh thӭ
2.3 - KiӇm tra nӃu E = E thì hình thành khóa bí mұt nhҩt:
KBA theo công thӭc: E = R mod q = R mod q = E
234
- Hội+ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJYj&{QJ1JKӋ7K{QJ7LQ (&,7
-
Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Tӯ (2.1), (2.2) và (2.5) ta có: III. KӂT LUҰN
x A . (k + )1
K AB = ( y B ) mod p Bài báo ÿӅ xuҩt 2 dҥng thuұt toán xác lұp khóa mӟi cho
x A . ( k +1) (2.11) các hӋ mұt khóa ÿӕi xӭng, các thuұt toán mӟi ÿӅ xuҩt có các
= (g xB
mod p ) mod p
ÿһc ÿiӇm cѫ bҧn nhѭ sau:
= g (k +1). x A . x B mod p
- ThiӃt lұp khóa bí mұt chung giӳa các ÿӕi tѭӧng tham
Mһt khác, tӯ (2.1), (2.8) và (2.10) ta lҥi có: gia giao dӏch chӍ phҧi thӵc hiӋn mӝt 1 lҫn truyӅn dӳ liӋu duy
xB
K BA = (R × y A ) mod p nhҩt tѭѫng tӵ nhѭ các giao thӭc chuyӇn khóa sӱ dөng mұt mã
= (R × y A ) B mod p
x (2.12) khóa công khai.
xB - Thông tin ÿѭӧc chuyӇn tӯ ÿӕi tѭӧng gӱi/mã hóa sang
= g k . x A mod p × g x A mod p
( ) mod p ÿӕi tѭӧng nhұn/giҧi mã hoһc ngѭӧc lҥi, không phҧi là khóa bí
=g ( k +1). x A . xB
mod p mұt mà chӍ là thông tin dùng ÿӇ thiӃt lұp khóa chung giӳa 2
Tӯ (2.11) và (2.12) ta có ÿiӅu cҫn chӭng minh thӭ hai: ÿӕi tѭӧng, tѭѫng tӵ nhѭ thông tin dùng ÿӇ thӓa thuұn khóa
K AB = K BA = K trong các giao thӭc trao ÿәi khóa. Tuy nhiên, thông tin này chӍ
Nhѭ vұy tính ÿúng ÿҳn cӫa thuұt toán mӟi ÿӅ xuҩt ÿã cҫn truyӅn ÿi theo 1 chiӅu, do ÿó ӣ các thuұt toán mӟi ÿӅ xuҩt
ÿѭӧc chӭng minh. viӋc truyӅn dӳ liӋu chӍ cҫn thӵc hiӋn 1 lҫn duy nhҩt.
2.2.4 Tính an toàn cӫa thuұt toán mӟi ÿӅ xuҩt - Khóa bí mұt chung ÿѭӧc xác thӵc vӅ nguӗn gӕc và tính
toàn vҽn (chӍ có ӣ dҥng thuұt toán thӭ 2), vì thӃ các thuұt toán
Mӭc ÿӝ an toàn cӫa thuұt toán mӟi ÿӅ xuҩt ӣ dҥng 2 cNJng này có khҧ năng chӕng ÿѭӧc các dҥng tҩn công giҧ mҥo ÿã
ÿѭӧc ÿánh giá qua các khҧ năng nhѭ sau: biӃt trong thӵc tӃ.
a) Kh̫ năng ch͙ng ṱn công làm l͡ khóa bí m̵t Tính hiӋu quҧ và mӭc ÿӝ an toàn cӫa các thuұt toán mӟi
ÿӅ xuҩt cho thҩy khҧ năng ӭng dөng cӫa chúng trong thӵc tӃ là
Phân tích tѭѫng tӵ nhѭ ӣ Mөc 2.1.4 a) có thӇ thҩy rҵng rҩt khҧ quan.
khҧ năng chӕng tҩn công làm lӝ khóa bí mұt cӫa 2 thuұt toán
này là nhѭ nhau và ÿӅu phө thuӝc vào tính khó giҧi cӫa bài TÀI LIӊU THAM KHҦO
toán logarit rӡi rҥc. [1] W. Diffie & M. Hellman, “New Directions in Cryptography”, IEEE
b) Kh̫ năng ch͙ng ṱn công gi̫ m̩o Trans. On Info. Theory, IT-22(6):644-654, 1976.
Nhѭ ÿã chӍ ra trong phҫn Nh̵n xét cӫa Mͭc 2.2.2, nӃu [2] R. L. Rivest, A. Shamir, and L. M. Adleman, “A Method for Obtaining
Digital Signatures and Public Key Cryptosystems”, Commun. of the
ÿiӅu kiӋn kiӇm tra: E = E không ÿѭӧc thӓa mãn thì B có thӇ ACM, Vol. 21, No. 2, pp. 120-126, 1978.
khҷng ÿӏnh cһp (E,S) nhұn ÿѭӧc hoһc không phҧi do A gӱi ÿӃn [3] T. ElGamal, “A public key cryptosystem and a signature scheme based
hoһc ÿã bӏ thay ÿәi trong quá trình truyӅn ÿi tӯ A, vì thӃ khóa on discrete logarithms”, IEEE Transactions on Information Theory. Vol.
mұt chung vӟi A sӁ không ÿѭӧc tҥo ra. Phân tích tѭѫng tӵ nhѭ IT-31, No. 4. pp.469–472, 1985.
ӣ mөc 2.1.4 b) cho thҩy ngay cҧ trѭӡng hӧp kҿ tҩn công mҥo [4] A. Menezes, P. van Oorschot and S. Vanstone, “Handbook of Applied
danh A tҥo ÿѭӧc cһp (E,S) thӓa mãn ÿiӅu kiӋn kiӇm tra nhѭ ÿã Cryptography”, Boca Raton, Florida: CRC Press, 1997.
chӍ ra thì cNJng không thӇ thiӃt lұp ÿѭӧc khóa bí mұt chung vӟi [5] D.R Stinson, “Cryptography: Theory and Practice”, CRC Press 1995.
B. [6] Wenbo Mao, “Modern Cryptography: Theory and Practice”, Prentice
Hall PTR, 2003.
235
nguon tai.lieu . vn
