![3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (5)
- M達 ho叩:
+ Nh畉n kho叩 c担ng khai c畛a A: n.
+ Bi畛u th畛 b畉n tin d動畛i d畉ng m畛t s畛 nguy棚n m
[ 0 , n 1]
n畉m trong d畉i
c = m 2 mod n
+ T鱈nh
+ G畛i b畉n m達 c cho A](https://image.slidesharecdn.com/chuong3matmakhoacongkhai-131012164708-phpapp01/85/MATMA-Chuong3matmakhoacongkhai-25-320.jpg)
![[123doc.vn] xay dung he thong mang cho doanh nhiep nho](https://cdn.slidesharecdn.com/ss_thumbnails/123doc-141031060437-conversion-gate02-thumbnail.jpg?width=560&fit=bounds)
More Related Content
What's hot (20)
Viewers also liked (8)
Similar to MATMA - Chuong3matmakhoacongkhai (20)
More from Sai Lemovom (9)
Recently uploaded (20)
MATMA - Chuong3matmakhoacongkhai
- 1. Ch動董ng 3. M畉t m達 kho叩 c担ng khai
- 2. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai 3.1 H畛 m畉t RSA 3.2 H畛 m畉t Merkle Hellman 3.3 H畛 m畉t McEliece 3.4 H畛 m畉t ElGamal 3.5 H畛 m畉t Chor- Rivest 3.6 H畛 m畉t tr棚n 動畛ng cong Elliptic
- 3. 3.1 H畛 m畉t RSA RSA l m達 c担ng khai 動畛c s叩ng t畉o b畛i Rivest, Shamir & Adleman 畛 MIT (Tr動畛ng 畉i h畛c C担ng ngh畛 Massachusetts) vo nm 1977. RSA l m達 c担ng khai 動畛c bi畉t 畉n nhi畛u nh畉t v s畛 d畛ng r畛ng r達i nh畉t hi畛n nay. RSA d畛a tr棚n c叩c ph辿p to叩n l滴y th畛a trong tr動畛ng h畛u h畉n c叩c s畛 nguy棚n theo modulo nguy棚n t畛. C畛 th畛, m達 ho叩 hay gi畉i m達 l c叩c ph辿p to叩n lu畛 th畛a theo modulo s畛 r畉t l畛n. Vi畛c th叩m m達, t畛c l t狸m kho叩 ri棚ng khi bi畉t kho叩 c担ng khai, d畛a tr棚n bi to叩n kh坦 l ph但n t鱈ch m畛t s畛 r畉t l畛n 坦 ra th畛a s畛 nguy棚n t畛. N畉u kh担ng c坦 th担ng tin g狸, th狸 ta ph畉i l畉n l動畛t ki畛m tra t鱈nh chia h畉t c畛a s畛 坦 cho t畉t c畉 c叩c s畛 nguy棚n t畛 nh畛 h董n cn c畛a n坦. 但y l vi畛c lm kh担ng kh畉 thi!
- 4. 3.1 H畛 m畉t RSA Ng動畛i ta ch畛ng minh 動畛c r畉ng, ph辿p l滴y th畛a c畉n O((log n)3) ph辿p to叩n, n棚n c坦 th畛 coi l滴y th畛a l bi to叩n d畛. C畉n ch炭 箪 r畉ng 畛 但y ta s畛 d畛ng c叩c s畛 r畉t l畛n kho畉ng 1024 bit, t畛c l c畛 10350. T鱈nh an ton d畛a vo 畛 kh坦 c畛a bi to叩n ph但n t鱈ch ra th畛a s畛 c叩c s畛 l畛n. Bi to叩n ph但n t鱈ch ra th畛a s畛 y棚u c畉u O(elogn log logn) ph辿p to叩n, 但y l bi to叩n kh坦.
- 5. 3.1 H畛 m畉t RSA Kh畛i t畉o kho叩 RSA M畛i ng動畛i s畛 d畛ng t畉o m畛t c畉p kho叩 c担ng khai ri棚ng nh動 sau: Ch畛n ng畉u nhi棚n 2 s畛 nguy棚n t畛 l畛n p v q T鱈nh s畛 lm modulo c畛a h畛 th畛ng: N = p.q Ta 達 bi畉t 个(N)=(p-1)(q-1) V c坦 th畛 d湛ng 畛nh l箪 Trung Hoa 畛 gi畉m b畛t t鱈nh to叩n Ch畛n ng畉u nhi棚n kho叩 m達 e Trong 坦 1<e< 个(N), gcd(e,个(N))=1 Gi畉i ph動董ng tr狸nh sau 畛 t狸m kho叩 gi畉i m達 d sao cho e.d=1 mod 个(N) v畛i 0d 个(N) In kho叩 m達 c担ng khai KU={e,N} Gi畛 kho叩 ri棚ng b鱈 m畉t KR={d,p,q}
- 6. 3.1 H畛 m畉t RSA S畛 d畛ng RSA 畛 m達 ho叩 m畉u tin, ng動畛i g畛i: L畉y kho叩 c担ng khai c畛a ng動畛i nh畉n KU={e,N} T鱈nh C=Me mod N, trong 坦 0M<N 畛 gi畉i m達 ho叩 b畉n m達, ng動畛i s畛 h畛u nh畉n: S畛 d畛ng kh坦a ri棚ng KR={d,p,q} T鱈nh M=Cd mod N L動u 箪 r畉ng b畉n tin M < N, do 坦 khi c畉n chia kh畛i b畉n r探.
- 7. 3.1 H畛 m畉t RSA C董 s畛 c畛a RSA Theo 畛nh l箪 Ole a陸(n) mod N = 1 trong 坦 gcd(a,N)=1 Ta c坦 N=p.q 个(N)=(p-1)(q-1) e.d=1 mod 个(N) e.d=1+k.个(N) 畛i v畛i m畛t gi叩 tr畛 k no 坦. Suy ra Cd = (Me)d = M1+k.陸(N) = M1.(M陸(n))k suy ra Cd modN = M1.(1)k modN = M1 modN = M modN
- 8. 3.1 H畛 m畉t RSA V鱈 d畛 Ch畛n c叩c s畛 nguy棚n t畛: p=17 & q=11. T鱈nh n = pq, n = 1711=187 T鱈nh 个(n)=(p1)(q-1)=1610=160 Ch畛n e : gcd(e,160)=1; L畉y e=7 X叩c 畛nh d: de=1 mod 160 v d < 160 Gi叩 tr畛 c畉n t狸m l d=23, v狸 237=161= 10160+1 In kho叩 c担ng khai KU={7,187} Gi畛 kho叩 ri棚ng b鱈 m畉t KR={23,17,11}
- 9. 3.1 H畛 m畉t RSA V鱈 d畛 叩p d畛ng m達 RSA tr棚n nh動 sau: Cho m畉u tin M = 88 (v畉y 88<187) M達 C = 887 mod 187 = 11 Gi畉i m達 M = 1123 mod 187 = 88 C坦 th畛 d湛ng 畛nh l箪 ph畉n d動 Trung Hoa 畛 gi畉i m達 cho nhanh nh動 sau: T鱈nh 1123 mod 11 = 0 T鱈nh 1123mod 17 = (-6)23 mod 17 = (-6)16(-6)4 (-6)2 (-6) mod 17 = c1= 3 V狸 (-6)2 mod 17 = 2, n棚n (-6)4 mod 17 = 4, (-6)8 mod 17 = -1, (-6)16 mod 17 = 1 11-1 mod 17 = (-6)-1 mod 17 = 14 n棚n 11(11-1 mod 17) = 11(14 mod 17) = c2 = 154 V畉y M = (3.154) mod 187 = 462 mod 187 = 88
- 10. 3.1 H畛 m畉t RSA M達 hi畛u qu畉: M達 s畛 d畛ng l滴y th畛a c畛a kho叩 c担ng khai e, n畉u gi叩 tr畛 c畛a e nh畛 th狸 t鱈nh to叩n s畉 nhanh, nh動ng d畛 b畛 t畉n c担ng. Th動畛ng ch畛n e nh畛 h董n ho畉c b畉ng 65537 (216-1), t畛c l 畛 di kho叩 c担ng khai l 16 bit. Ch畉ng h畉n trong v鱈 d畛 tr棚n ta c坦 th畛 l畛a ch畛n e = 23 ho畉c e = 7. Ta c坦 th畛 t鱈nh m達 ho叩 nhanh, n畉u bi畉t n=pq v s畛 d畛ng 畛nh l箪 ph畉n d動 Trung Hoa v畛i m畉u tin M theo c叩c Modulo p v q kh叩c nhau. N畉u kho叩 c担ng khai e c畛 畛nh th狸 c畉n tin t動畛ng r畉ng khi ch畛n n ta lu担n c坦 gcd(e,个(n)) = 1. Lo畉i b畛 m畛i p, q m lm cho 个(n) kh担ng nguy棚n t畛 c湛ng nhau v畛i e.
- 11. 3.1 H畛 m畉t RSA Gi畉i m達 hi畛u qu畉: C坦 th畛 s畛 d畛ng 畛nh l箪 ph畉n d動 Trung Hoa 畛 t鱈nh theo mod p v q, sau 坦 k畉t h畛p l畉i 畛 t狸m ra b畉n r探. V狸 畛 但y ng動畛i s畛 d畛ng kho叩 ri棚ng bi畉t 動畛c p v q, do 坦 c坦 th畛 s畛 d畛ng k畛 thu畉t ny. N畉u s畛 d畛ng 畛nh l箪 ph畉n d動 Trung Hoa 畛 gi畉i m達 th狸 hi畛u qu畉 l nhanh g畉p 4 l畉n so v畛i gi畉i m達 t鱈nh tr畛c ti畉p.
- 12. 3.1 H畛 m畉t RSA Sinh kho叩 RSA Ng動畛i s畛 d畛ng RSA c畉n ph畉i x叩c 畛nh ng畉u nhi棚n 2 s畛 nguy棚n t畛 r畉t l畛n p, q th担ng th動畛ng kho畉ng 512 bit. Sau khi ch畛n 動畛c m畛t kho叩 e ho畉c d nguy棚n t畛 c湛ng nhau v畛i 个(n), d畛 dng t鱈nh 動畛c kho叩 kia ch鱈nh l s畛 ngh畛ch 畉o c畛a n坦 qua thu畉t to叩n Euclide m畛 r畛ng.
- 13. 3.1 H畛 m畉t RSA An ton c畛a RSA Tr棚n th畛c t辿 c坦 nhi畛u c叩ch t畉n c担ng kh叩c nhau 畛i v畛i m達 c担ng khai RSA nh動 sau: T狸m ki畉m kho叩 b畉ng ph動董ng ph叩p v辿t c畉n, ph動董ng ph叩p ny kh担ng kh畉 thi v畛i k鱈ch th動畛c 畛 l畛n c畛a c叩c s畛 T畉n c担ng b畉ng to叩n h畛c d畛a vo 畛 kh坦 vi畛c t鱈nh 个(n) b畉ng c叩ch ph但n t鱈ch n thnh hai s畛 nguy棚n t畛 p v q ho畉c t狸m c叩ch t鱈nh tr畛c ti畉p 个(n). Trong qu叩 tr狸nh nghi棚n c畛u vi畛c th叩m m達 ng動畛i ta 畛 xu畉t ki畛u t畉n c担ng th畛i gian trong khi gi畉i m達, t畛c l cn c畛 vo t畛c 畛 m達 ho叩 v gi畉i m達 c叩c m畉u tin cho tr動畛c m ph叩n o叩n c叩c th担ng tin v畛 kho叩.
- 14. 3.1 H畛 m畉t RSA i畛m b畉t 畛ng 畛nh l鱈: N畉u c叩c th担ng b叩o 動畛c m達 b畉ng h畛 m畉t RSA v畛i c畉p kh坦a c担ng khai (e,n) v畛i n = p.q th狸 s畛 c叩c th担ng b叩o kh担ng th畛 che d畉u 動畛c l N = (1 + UCLN( e 1, p 1) ) (1 + UCLN( d 1, q 1) )
- 15. 3.2 H畛 m畉t Merkle Hellman H畛 m畉t Merkle Hellman - D達y si棚u1 tng: D達y s畛 ngd動董ng ( a1 , a 2 , , a n ) tm達n i a i > a j v畛i i , 2 i n j =1 - Bi to叩n x畉p ba l担:Cho t畉p c叩c gi叩 tr畛 v m畛t t畛ng S. H達y t鱈nh c叩c gi叩 tr畛 bi 畛: M1 , M 2 , , M n S = b1M1 + b 2 M 2 + + b n M n v畛i b i {0 ,1}
- 16. 3.2 H畛 m畉t Merkle Hellman TT gi畉i bto叩n x畉p ba l担 trong tr動畛ng h畛p d達y si棚u tng:
- 17. 3.2 H畛 m畉t Merkle Hellman - T畉o kho叩:
- 18. 3.2 H畛 m畉t Merkle Hellman M達 ho叩
- 19. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (15) Gi畉i m達
- 20. 3.2 H畛 m畉t Merkle Hellman Ch畛ng minh
- 21. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (1) 3.1 H畛 m畉t RSA (Ron Rivest, Adi Shamir v Len Adleman) - T畉o kho叩:
- 22. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (2) - M達 ho叩: B棚n m達 l B, b棚n nh畉n l A
- 23. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (3) Ch炭 箪: 了 = BCNN( p 1, q 1) 1. S畛 m滴 v畉n nng thay cho 陸 = ( p 1)( q 1) 2. i畛m b畉t 畛ng 畛nh l鱈: N畉u c叩c th担ng b叩o 動畛c m達 b畉ng h畛 m畉t RSA v畛i c畉p kh坦a c担ng khai ( e, n ) v畛i n = p.q th狸 s畛 c叩c th担ng b叩o kh担ng th畛 che d畉u 動畛c l N = (1 + UCLN( e 1, p 1) ) (1 + UCLN( d 1, q 1) )
- 24. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (4) 3.2 H畛 m畉t Rabin - T畉o kho叩 + T畉o 2 s畛 nguy棚n t畛 l畛n, ng畉u nhi棚n v ph但n bi畛t p v q c坦 k鱈ch th動畛c x畉p x畛 nhau. + T鱈nh n = p . q + Kho叩 c担ng khai l n, kho叩 b鱈 m畉t l c叩c c畉p s畛 (p, q).
- 25. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (5) - M達 ho叩: + Nh畉n kho叩 c担ng khai c畛a A: n. + Bi畛u th畛 b畉n tin d動畛i d畉ng m畛t s畛 nguy棚n m [ 0 , n 1] n畉m trong d畉i c = m 2 mod n + T鱈nh + G畛i b畉n m達 c cho A
- 26. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (6) - Gi畉i m達: + A ph畉i th畛c hi畛n c叩c b動畛c sau:T狸m 4 cn b畉c hai c畛a c mod n l m1, m2, m3 ho畉c m4 + Th担ng b叩o cho ng動畛i g畛i l m畛t trong 4 gi叩 tr畛 m1, m2, m3 ho畉c m4. B畉ng m畛t c叩ch no 坦 A s畉 quy畉t 畛nh m l gi叩 tr畛 no.
- 27. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (7) Ch炭 箪: Khi p, q l c叩c s畛 nguy棚n Blum th狸 ta c坦 th畛 t鱈nh 4 cn b畉c 2 c畛a c mod n nh動 sau: + T狸m a,b nguy棚n tho畉 m達n: ap + bq = 1 +T鱈nh c叩c gi叩 tr畛 sau: r = c ( p +1) / 4 mod p y = ( aps bqr ) mod n s = c ( q +1) / 4 mod q x = ( aps + bqr ) mod n 4 gi叩 tr畛 cn b畉c 2 c畛a c mod n l x mod n x, y mody v , n
- 28. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (8) 3.3 H畛 m畉t Elgamal - T畉o kho叩: 留 + T畉o 1 s畛 nguy棚n t畛 p l畛n v m畛t ph畉n t畛 sinh c畛a nh坦m nh但n Z* c畛a c叩c s畛 nguy棚n mod p. p + Ch畛n m畛t s畛 nguy棚n ng畉u nhi棚n a, 1 a p 2 v t鱈nh 留a mod p Kho叩 c担ng khai l b畛 3 s畛 p , 留 , 留 a , kho叩 b鱈 m畉t l a. ( )
- 29. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (9) - M達 ho叩: a + Nh畉n kho叩 c担ng khai p , 留 , 留 c畛a A + Bi畛u th畛 b畉n tin d動畛i d畉ng m畛t s畛 nguy棚n m trong d畉i { 0 ,1 , , p 1} + Ch畛n s畛 nguy棚n ng畉u nhi棚n k, 1 k p 2 k a k + T鱈nh 粒 = 留 mod p v 隆 = m 留 mod p + G畛i b畉n m達 c = ( 留 , 隆 ) cho A ( ) ( )
- 30. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (10) - Gi畉i m達: 粒 p 1 a mod p + S畛 d畛ng kho叩 ri棚ng a 畛 t鱈nh + Kh担i ph畛c b畉n r探 b畉ng c叩ch t鱈nh 粒 a 隆 mod p - Ch畛ng minh: ( ) 粒 a 隆 留 a k .m 留 a k m mod p
- 31. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (17) 3.5 H畛 m畉t tr棚n 動畛ng cong Elipptic
- 32. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (18)
- 33. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (19)
- 34. 3. M畛t s畛 h畛 m畉t kho叩 c担ng khai (20)