Ch ng 8ươ
M T MÃ ẬKHÓA CÔNG KHAI
8.1 T ng quan v m t mã công khaiổ ề ậ
Trong ch ng tr c chúng ta đã tìm hi u v m t mã đ i x ng. Chúng ta rõ r ng cácươ ướ ể ề ậ ố ứ ằ
bên tham gia c n có m t khóa m t đ mã hóa và gi i mã. Đi u này đ ng nghĩa v i vi cầ ộ ậ ể ả ề ồ ớ ệ
trao đ i khóa m t qua kênh. Vi c gi bí m t khóa m t đ ng nghĩa v i vi c gi m tổ ậ ệ ữ ậ ậ ồ ớ ệ ữ ậ
thông tin. Nên vi c trao đ i khóa ch di n ra trên kênh m t thì m i đ m b o đ c, thệ ổ ỉ ễ ậ ớ ả ả ượ ế
nh ng vi c trao đ i này cung không ph i d đ đ m b o đ an toàn cao. T đây hìnhư ệ ổ ả ễ ể ả ả ộ ừ
thành nên ý t ng c a m t mã công khai. T c là không c n ph i trao đ i khóa m t quaưở ủ ậ ứ ầ ả ổ ậ
kênh n a.ữ
Ý t ng c a h m t công khai đ c Diffie và Hellman đ a ra năm 1976. Còn vi cưở ủ ệ ậ ượ ư ệ
th c hi n h m t công khai thì do Rivest, Shamir và Adleman đ a ra đ u tiên năm 1977,ự ệ ệ ậ ư ầ
h đ xu t m t h m t RSA n i ti ng. Và k t đó có m t s h m t khác đ c côngọ ề ấ ộ ệ ậ ổ ế ể ừ ộ ố ệ ậ ượ
b , đ m t c a chúng d a trên bài tính toán khác nhau, nh d a trên đ khó c a bài toánố ộ ậ ủ ự ư ự ộ ủ
phân tích thành nhân t nh h m t RSA, d a vào đ khó logarithm r i r c nh h m tử ư ệ ậ ự ộ ờ ạ ư ệ ậ
ElGamal, hay d a trên đ ng cong Elliptíc. Chúng ta đi tìm hi u c th các h m t nàyự ườ ể ụ ể ệ ậ
trong các ph n sau. Nh ng tr c tiên chúng ta đi tìm hi u s đ và nguyên t c mã vàầ ư ướ ể ơ ồ ắ
gi i mã c a h m t công khai. ả ủ ệ ậ
S đ c a h mã công khai đ c cho hình 8.1.ơ ồ ủ ệ ượ ở
Hình 8.1. S đ mã hóa công khaiơ ồ
H mã công khai s d ng hai khóa có quan h toán h c v i nhau, t c là m t khóaệ ử ụ ệ ọ ớ ứ ộ
này đ c hình thành t khóa kia: Ng i mu n nh n b n mã (Alice) t o ra m t khóaượ ừ ườ ố ậ ả ạ ộ
m t (private key) và t khóa m t tính ra khóa công khai (public key) v i m t th t cậ ừ ậ ớ ộ ủ ụ
không ph c t p, còn vi c tìm khóa m t khi bi t khóa công khai là bài toán khó gi iứ ạ ệ ậ ế ả
đ c. Khóa công khai s đ a đ n cho ng i g i b n tin (Bob) qua kênh công c ng. Vàượ ẽ ư ế ườ ở ả ộ
b n tin đ c Bob mã hóa b ng khóa công c ng. B n mã truy n đ n Alice, và nó đ cả ượ ằ ộ ả ề ế ượ
gi i mã b ng khóa m t.ả ằ ậ
8.2 H m t RSAệ ậ
L ch s hình thànhị ử
Thu t toán đ c ậ ượ Ron Rivest, Adi Shamir và Len Adleman mô t l n đ u tiên vàoả ầ ầ
năm 1977 t i ạH c vi n Công ngh Massachusettsọ ệ ệ (MIT). Tên c a thu t toán l y t 3ủ ậ ấ ừ
ch cái đ u c a tên 3 tác gi . Đây là thu t toán đ u tiên phù h p v i vi c t o ra ữ ầ ủ ả ậ ầ ợ ớ ệ ạ ch kýữ
đi n tệ ử đ ng th i v i vi c ồ ờ ớ ệ mã hóa. Nó đánh d u m t s ti n b v t b c c a lĩnh v cấ ộ ự ế ộ ượ ậ ủ ự
m t mã h cậ ọ trong vi c s d ng khóa công c ng. RSA đang đ c s d ng ph bi nệ ử ụ ộ ượ ử ụ ổ ế
trong th ng m i đi n tươ ạ ệ ử và đ c cho là đ m b o an toàn v i đi u ki n đ dài ượ ả ả ớ ề ệ ộ khóa đủ
l n.ớ
Thu t toán RSA đ c MIT đăng ký b ng sáng ch t i Hoa Kỳ vào năm ậ ượ ằ ế ạ 1983 (Số
đăng ký 4,405,829). B ng sáng ch này h t h n vào ngày ằ ế ế ạ 21 tháng 9 năm 2000. Tuy
nhiên, do thu t toán đã đ c công b tr c khi có đăng ký b o h nên s b o h h uậ ượ ố ướ ả ộ ự ả ộ ầ
nh không có giá tr bên ngoài Hoa Kỳ. Ngoài ra, n u nh công trình c a Clifford Cocksư ị ế ư ủ
đã đ c công b tr c đó thì b ng sáng ch RSA đã không th đ c đăng ký.ượ ố ướ ằ ế ể ượ
Thu t toán d a trên đ khó c a bài toán phân tích m t s thành nhân t .ậ ự ộ ủ ộ ố ử
Quá trình t o khóa cho h m t RSA.ạ ệ ậ
Gi s Alice và Bob c n trao đ i thông tin bí m t thông qua m t kênh không an toànả ử ầ ổ ậ ộ
(ví d nh ụ ư Internet). V i thu t toán RSA, Alice đ u tiên c n t o ra cho mình c p khóaớ ậ ầ ầ ạ ặ
g m khóa công khai và khóa bí m t theo 6 b c sau:ồ ậ ướ
1. Ch n 2 s nguyên t l n khác nhau p, q th a mãn đi u ki n ọ ố ố ớ ỏ ề ệ
qp ≈
2. Tính tích c a nó ủ
qpn ⋅=
.
3. Tính giá tr hàm Phi Euler c a n: ị ủ
( ) ( )( )
1q1pn −−=ϕ
.
4. Ch n s nguyên d, sao choọ ố
( )
nd ϕ<
và gcd(d,
)(n
ϕ
)=1.
5. Tính giá tr e th a mãn đi u ki n:ị ỏ ề ệ
( )( )
nmod1de ϕ=⋅
.
6. Khóa công khai bao g m: n và e.ồ Khóa m tậ:d còn p,q và
)(n
ϕ
th ng là xóa sauườ
khi tính toán khóa.
Quá trình mã hóa:
Gi s Bob mu n g i đo n thông tin ả ử ố ử ạ m<n cho Alice, thì Bob tính b n mã nh sau. ả ư
)(modnmc e
=
Cu i cùng Bob g i ố ử c cho Alice.
Quá trình gi i mãả:
Alice nh n ậc t Bob và khóa bí m t ừ ậ d. Alice có th tìm đ c ể ượ m t ừc theo công th cứ
sau:
)(modncm d
=
Quá trình gi i mã ho t đ ng vì ta cóả ạ ộ
Do ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), theo Đ nh lý Fermat nhị ỏ nên:
)(mod pmmed ≡
)(modqmm
ed
≡
Do p và q là hai s nguyên t cùng nhau, áp d ng đ nh lý ph n d trung hoa, chúng taố ố ụ ị ầ ư
có:
)(mod pqmmed ≡
Hay
)(modnmcd≡
Ví dụ:
=p
70793
=q
707933
=⋅= qpn
50116700869
( ) ( )( )
=−−=ϕ 1q1pn
50115922144
=
d
30483041
=e
5851898625
m
)(modnmc e
=
)(mod
'ncm d
=
30483041 7523619714 30483041
7523619714 38101458113 7523619714
3487987 4469234330 3487987
754553 45262687896 754553
884545 48968540294 884545
46665533 10037623855 46665533
15657 29531681112 15657
95432 4648093185 95432
4545786 38326603863 4545786
777543 38921288996 777543
45673222 21930948547 45673222
M t s chú ý quan tr ng v RSAộ ố ọ ề
An ninh: Đ an toàn c a h th ng RSA d a trên 2 v n đ c a toán h c: bài toánộ ủ ệ ố ự ấ ề ủ ọ
phân tích ra th a s nguyên t các s nguyên l nừ ố ố ố ớ và bài toán RSA. N u 2 bài toán trên làế
khó (không tìm đ c thu t toán hi u qu đ gi i chúng) thì không th th c hi n đ cượ ậ ệ ả ể ả ể ự ệ ượ
vi c phá mã toàn b đ i v i RSA. Phá mã m t ph n ph i đ c ngăn ch n b ng cácệ ộ ố ớ ộ ầ ả ượ ặ ằ
ph ng pháp chuy n đ i b n rõ an toàn. ươ ể ổ ả Bài toán RSA là bài toán tính căn b c ậe môđun
n (v i ớn là h p s ): tìm s ợ ố ố m sao cho me=c mod n, trong đó (e, n) chính là khóa công khai
và c là b n mã. Hi n nay ph ng pháp tri n v ng nh t gi i bài toán này là phân tích ả ệ ươ ể ọ ấ ả n ra
th a s nguyên t . Khi th c hi n đ c đi u này, k t n công s tìm ra s mũ bí m t ừ ố ố ự ệ ượ ề ẻ ấ ẽ ố ậ d
t khóa công khai và có th gi i mã theo đúng quy trình c a thu t toán. N u k t n côngừ ể ả ủ ậ ế ẻ ấ
tìm đ c 2 s nguyên t ượ ố ố p và q sao cho: n = pq thì có th d dàng tìm đ c giá tr (ể ễ ượ ị p-1)
(q-1) và qua đó xác đ nh ịd t ừe. Trong ch ng s h c chúng ta đã bi t ch a có m tươ ố ọ ế ư ộ
ph ng pháp nào đ c tìm ra trên máy tính đ gi i bài toán này trong th i gian đa th cươ ượ ể ả ờ ứ
(polynomial-time). Tuy nhiên ng i ta cũng ch a ch ng minh đ c đi u ng c l i (sườ ư ứ ượ ề ượ ạ ự
không t n t i c a thu t toán). ồ ạ ủ ậ
T c đố ộ: RSA có t c đ th c hi n ch m h n đáng k so v i các ố ộ ự ệ ậ ơ ể ớ thu t toán mã hóaậ
đ i x ngố ứ . Trên th c t , Bob s d ng m t thu t toán mã hóa đ i x ng nào đó đ mã hóaự ế ử ụ ộ ậ ố ứ ể
văn b n c n g i và ch s d ng RSA đ mã hóa khóa đ gi i mã (thông th ng khóaả ầ ử ỉ ử ụ ể ể ả ườ
ng n h n nhi u so v i văn b n). Ph ng th c này cũng t o ra nh ng v n đ an ninhắ ơ ề ớ ả ươ ứ ạ ữ ấ ề
m i. M t ví d là c n ph i t o ra khóa đ i x ng th t s ng u nhiên. N u không, k t nớ ộ ụ ầ ả ạ ố ứ ậ ự ẫ ế ẻ ấ
công (th ng ký hi u là Eve) s b qua RSA và t p trung vào vi c đoán khóa đ i x ng.ườ ệ ẽ ỏ ậ ệ ố ứ
Chi u dàềi khóa: S n c n ph i có kích th c không nh h n 512 bít. Năm 2006 hố ầ ả ướ ỏ ơ ệ
m t RSA đ c cho là hi u qu v i kích th c n ph i t 1024. Và h khuy n cáo làậ ượ ệ ả ớ ướ ả ừ ọ ế
t ng lai thì chi u dài n ph i t 2024 bít. ươ ề ả ừ
Ch n tham s công khai:ọ ố
Đ nâng cao t c đ mã hóa, thì chúng ta nên ch n e v i giá tr không l n, th ng làể ố ộ ọ ớ ị ớ ườ
3, 7 hay 65537. Các s này khi bi u di n d ng nh phân ch có 2 ch s 1, nên khi th cố ể ễ ở ạ ị ỉ ữ ố ự
hi n l nh lũy th a s gi m đi l nh nhân.ệ ệ ừ ẽ ả ệ
Ch n tham s m tọ ố ậ .
•p và q còn c n đ c ch n không quá g n nhau đ phòng tr ng h p phân tíchầ ượ ọ ầ ể ườ ợ
n b ng ph ng pháp ằ ươ phân tích Fermat. Ngoài ra, n u ếp-1 ho c ặq-1 có th a sừ ố
nguyên t nh thì ố ỏ n cũng có th d dàng b phân tích theo ph ng pháp p-1ể ễ ị ươ
Pollaid và vì th ếp và q cũng c n đ c th đ tránh kh năng này. Chúng ta cóầ ượ ử ể ả
th ch n nh sau. Tr c tiên tìm s nguyên t pể ọ ư ướ ố ố 1 sao cho p=2p1+1 cũng là số
nguyên t , t ng t ch n s nguyên t l n qố ươ ự ọ ố ố ớ 1 sao cho q=2q1+1 cũng là số
nguyên t .ố
•Giá tr d c n ph i đ l n. Năm 1990 ị ầ ả ủ ớ Michael J. Wiener đã ch ng minh r ngứ ằ
n u nh ế ư
qpq 2<<
và
3/
4/1
nd <
, thì có ph ng pháp hi u qu đ tính d theoươ ệ ả ể
n và e.
8.3 H m t Elgamaệ ậ
H m t Elgama hình thành trên c s bài toán logarith r i r c. Đ c đ xu t nămệ ậ ơ ở ờ ạ ượ ề ấ
1984. Sau đó chu n ch ký đi n t c a M và Nga hình thành trên c s h m t này.ẩ ữ ệ ử ủ ỹ ơ ở ệ ậ
Hình thành khóa:
Giả s Alice và Bob mu n trao đ i thông tin m t v i nhau b ng h m t Elgamma.ử ố ổ ậ ớ ằ ệ ậ
Thì tr c tiên Alice th c hi n qúa trình hình thành khóa nh sau:ướ ự ệ ư
1. Ch nọ s nguyên t đ l n p có chi u dài là k sao cho bài toán logarithm trong ố ố ủ ớ ề
p
Z
là khó gi iả
2. Ch nọ
*
p
Z∈
α
là ph n t nguyên th y. Ch n x là s ng u nhiên sao cho 1<x<p.ầ ử ủ ọ ố ẫ
3. Tính giá tr y th a mãn công th c: ị ỏ ứ
( )
pmody x
α=
Khóa m t là x, còn khóa m là 3 s (ậ ở ố
α
,p,y).
Quá trình mã hóa b n tin Tả:
1. Ch n s ng u nhiênọ ố ẫ
R
. (ch n k)ọ
2. Tính:
( )
pmodC R
α=
′
. (
( )
pr kmod
α
=
)
3. Sử d ngụ khóa mở tính:
( )
pmodTyC R
=
′′
, (
( )
pTyC kmod=
)
4. Bob g i b n mã g m ở ả ồ
( )
C,C ′′′
đ n Alice (C,r)ế
Quá trình gi i mãả:
1. Tính giá trị:
( )
( )
Rx
x
R
x
CZ α=α=
′
=
. (
( )
( )
kx
x
k
x
rZ
αα
===
)
2. Tính gía trị ngh chị đ oả c aủ Z:
( )
( )
pmodZ
1
Rx1 −
−
α=
. (
( )
( )
pZ kx mod
1
1−
−=
α
)
3. Gi iả mã theo b nả mã
C′′
: