ươ

ng 4

Ch Mã hóa công khai RSA

ộ

N i dung

 Mô hình mã hóa công khai  Mã hóa công khai RSA  B o m t, ch ng th c, không th  t

ứ ự ậ ể ừ ố ch i trong

 Ph

ả RSA ươ ổ ng pháp trao đ i khóa

ề

ặ ấ Đ t v n đ

ế ố ứ ể ừ ổ ể c  đi n đ n

ệ ể i 2 đi m y u sau:

ườ

ậ i nh n:  ậ

ể

 Mã hóa đ i x ng dù phát tri n t ế ẫ ồ ạ hi n đ i, v n t n t ườ ở ổ ◦  V n đ  trao đ i khóa gi a ng i g i và ng ổ ơ ở ể

ộ ậ ủ

ị ế ộ

ệ

ế

nhi m n u khóa b  ti

t l

ữ ấ ầ c n có m t kênh an toàn đ  trao đ i khóa bí m t. ◦  Tính bí m t c a khóa: không có c  s  đ  quy trách  .  Năm 1976 Whitfield Diffie và Martin Hellman đ a ư ế ấ

ạ ề

ề ả ả i quy t v n đ  trên: i pháp gi mã hóa công

ra gi khai

Ý t

ngưở

 Khóa mỗi người dùng được chia ra làm hai phần:

◦ Khoa chung: để mã hóa công khai với mọi người

◦ Khóa bí mật: để giải mã thì được giữ bí mật chỉ được

biết bởi chủ nhân của nó.

 Nếu khóa bí mật ở người nhận thì bộ sinh khóa

nằm ở người nhận.

 Các giai đo n mã hóa công khai

ạ

ị

ệ Đ nh nghĩa h  mã công khai

PP mã hóa RSA

 Là PP mã hóa công khai đ

ượ

ở ự c xây d ng b i Ron  ạ ệ i vi n MIT  Rivest, Adi Shamir và Len Adleman t năm 1977.

 Là PP mã hóa theo kh i, b n rõ M và b n mã C là

ả ả ố

ủ ố ớ ố ế 0 đ n 2i v i I là s  bit c a kh i

các s  nguyên t (i th

ừ ng là 1024). ộ ố ườ ử ụ ộ ố  S  d ng hàm m t chi u: phân tích m t s

ố ề ừ ố thành th a s  nguyên t

ự

ệ

ắ

Nguyên t c th c hi n RSA

ụ Ví d  RSA

ụ

Ví d  mã RSA (tt)

ứ ạ

ừ ả

ộ Đ  ph c t p tính toán trong  RSA  Phép mã hóa/gi

i mã: dùng phép lũy th a

ọ ể modular. Đ  an toàn, ch n N, e, M l n.

 Dùng phép “bình ph ừ ớ

ươ ế ệ

ộ

lũy th a l n, nâng cao t c đ  tính toán. ủ ớ ể ệ ớ ng liên ti p” tránh vi c tính  ố ọ  Phép tính sinh khóa: ch n p và q đ  l n đ  vi c

ử ả th  là không kh  thi

ụ Ví d  sinh khóa trong RSA

ủ

ộ

Đ  an toàn c a RSA

1. Vét c n khóa: th  t

ử ấ ả ể ể t c  các khóa d có th  đ

ạ ả ấ ớ b t kh  thi.

ừ tìm b n rõ có nghĩa, N l n ố

ộ

ấ ắ ủ ề

ả ố p.q : vi c ệ 2. Phân tích N thành th a s  nguyên t ả phân tích này là b t kh  thi vì đây là hàm m t  ạ ộ chi u, là nguyên t c ho t đ ng c a RSA. ự

ờ ọ ệ ứ ự ề ở

3. Đo th i gian: đây là PP phá mã không d a vào  toán h c mà d a vào “hi u  ng l ” sinh ra b i  quá trình gi

ả i mã RSA

ự

ể ở d  li u cho nhau, khóa (KRA , KUA), (KRB, KUB)

ứ ậ ả Tính b o m t, ch ng th c,  ố ừ  ch i trong mã hóa  không t công khai ả ử  Gi  s  Alice và Bob dùng mã hóa công khai đ  g i  ữ ệ ở ữ ệ

 G i d  li u cho Bob: C=E(M, KUB) i mã: M= D(C, KRB)

ả Bob gi

ả ể ả ự ừ

ứ  Đ  đ m b o tính ch ng th c, Alice không t ở ữ ệ ệ

ố  ch i  ể tránh nhi m g i d  li u, Alice dùng khóa riêng đ   mã hóa

C=E(M, KRA) M=D(C, KUA)

 N u b n gi

ả

ả ế ứ ỉ ử ườ ở ữ i mã có nghĩa, t c Alice là ng i g i d   ả ả i mã

ế

ể ộ ế ệ ệ li u. N u Trudy can thi p ch nh s a thì b n gi không có nghĩa, n u Trudy có khóa KRA thì Alice  ệ không th  thoái tránh nhi m làm l

ể ả khóa. ậ i

ườ ư ả  Tuy nhiên mô hình CT không b o m t. Đ  gi i ta đ a ra mô hình: ế quy t, ng

ổ

Trao đ i khóa công khai

 Khi hai ng

ườ ố i dùng mu n truy n d  li u cho nhau

ữ ệ ọ ả ướ ề c tiên h  ph i trao

ằ ổ

ớ ể ườ ề b ng mã hóa công khai, tr đ i khóa v i nhau. ề  Khóa có th  truy n công khai trên đ ng truy n

th ấ ự ủ ứ mô

ỉ

ườ ng. ề tính ch ng th c c a khóa KU  V n đ :  ứ hình ch ng ch  khóa công khai –CA (certificate  Authority )

ổ

Trao đ i khóa công khai dùng  CA

ể ọ

Dùng khóa công khai trao đ i ổ khóa bí m tậ ặ  Do đ c đi m toán h c c a mã hóa công khai

ớ

ậ

ố ứ ườ ượ ế ậ

ậ ỗ ủ ậ ự ơ ch m h n so v i mã hóa đ i x ng nên trong th c  ố ả ế ể ả , đ  đ m b o bí m t, ng i ta dùng mã hóa đ i  t ể ứ c dùng đ  thi x ng, mã hóa công khai đ t l p  ổ ữ ệ khóa bí m t cho m i phiên trao đ i d  li u.

ậ

Dùng khóa công khai trao đ i ổ khóa bí m t (tt)

 A trao đ i khóa phiên Ks mã hóa b ng khóa riêng,

ằ ổ

ằ

 K t th c phiên trao đ i DL, Ks đ

sau đó mã hóa b ng khóa công khai c a B ỗ ượ ủ ủ ứ ể ả c h y đ  đ m

ế ả ậ b o tính bí m t.

ổ

ươ

ng pháp trao đ i khóa

ế ậ ể

Ph Diffie – Hellman  Dùng đ  thi ườ

ậ ế ậ

ữ ả i nh n mà không c n đ n gi ể ườ ở i g i và  i pháp mã hóa  ề

t l p khóa bí m t gi a ng ầ ng công khai hay chuy n chìa trên kênh truy n an  toàn.

ả

ủ

Gi

i pháp c a Diffie­Hellman

Alice

Bob

ố

ọ

ố

1. Ch n s  ngto p và s  g nh  h n p và là primitive root

ố

ữ

ậ

ỏ ơ ầ

ủ c a p. hai s  p và g không c n gi ọ

ậ ố

ữ

bí m t. ữ

ậ ố

bí m t s  a

ọ 2. Ch n và gi

Ch n và gi

bí m t s  b

3. Tính A= ga mod p

Tính B = gb mod p

ổ

ớ

4. Alice và Bob trao đ i A và B v i nhau

5.  Tính (gb)a mod p = gab

Tính (ga)b mod p = gab mod

p

ượ

ố ứ

mod p ị Giá tr  này đ

c dùng làm khóa cho mã hóa đ i x ng

ậ

Nh n xét

 thu t toán Diffie­Hellman l

ậ ạ ấ ạ ố ớ i th t b i đ i v i cách

ữ ẻ ứ ấ t n công k ­đ ng­gi a.

 Đ  an toàn, quá trình thi

ể ế ậ t l p khóa Diffie­Hellman

ả ượ ằ ẫ v n ph i đ ộ c mã hóa b ng m t khóa công khai.

 N u đã đ

ế ượ ệ ằ ả c b o v  b ng khóa công khai, thì

ấ ỳ ầ ố ứ ọ ọ ch n khóa đ i x ng b t k , c n gì ch n khóa

Diffie­Hellman???

ệ

ả ằ

B o v  khóa Diffie­Hellman  b ng khóa công khai