Chương4: Modes of Operation

Ch

ng4:

ươ Modes of Operation

N i dung

ộ

 Các ki u thao tác (Modes of Operation)  Các ki u chèn b sung thông tin (Padding Scheme)

ể ể

ổ

ể ể

Các ki u thao tác (Modes of Các ki u thao tác (Modes of Operation) Operation)

c chia thành t ng đo n (block) có ườ ượ ừ ạ

 Trong mã hóa, th ướ

ố ị

ng d li u đ ữ ệ c c đ nh (ví d nh 64 hay 128 bit). ụ ư ệ ể ề

 Đ mã hóa các thông đi p dài (có th chia thành nhi u block), có th ể modes of operation) khác

ể

kích th ể s d ng các ki u thao tác khác nhau ( ử ụ nhau

ể ể

Các ki u thao tác (Modes of Các ki u thao tác (Modes of Operation) Operation)

 Các ki u thao tác đ u tiên đ

ượ ề

c đ ngh (ECB, CBC, OFB, CFB) ị ậ confidentiality), không giúp đ m b o tính toàn ả ả

ả ẹ

 Các ki u thao tác đ ậ

ượ

 M t s ki u thao tác đ

t k cho phép ( ế ế ả ị CCM, EAX và OCB) v a ừ ẹ

c xây d ng đ mã hóa sector trên đĩa: ể ầ đ m b o tính bí m t ( ả v n thông tin ( ể ả ả ộ ố ể đ m b o tính bí m t, v a đ m b o xác đ nh tính toàn v n thông tin. ả ự ể

message integrity). c thi ừ ượ  Tweakable narrow-block encryption –LRW  Wide-block encryption -CMC và EME

Electronic codebook (ECB) Electronic codebook (ECB)

electronic codebook (ECB) ơ ả ể

 Ki u mã hóa đ n gi n nh t là ấ  Thông đi p c n mã hóa đ ượ ầ ệ mã hóa đ c l p nhau. ộ ậ  H n ch : các kh i có

c chia thành t ng đo n, m i đo n đ c ừ ạ ạ ỗ ượ

ế ạ cùng n i dung ộ

, sau khi mã hoá xong cũng t o ạ  Không che gi u đ c ố ế ượ ấ ả ố ệ

thành các kh i ố k t qu gi ng h t nhau các “m u” d li u (data pattern). ẫ

ECB trong các giao th c mã hóa ữ ệ  Không khuy n khích s d ng ế ử ụ ứ

Electronic codebook (ECB) Electronic codebook (ECB)

nh g c Ả ố Mã hóa theo các ki u khác Mã hóa theo ki u ể ECB ể

ứ ứ ể ể ẹ ẹ

ECBECB có th làm cho giao th c kém an toàn đ b o v tính toàn v n có th làm cho giao th c kém an toàn đ b o v tính toàn v n thông tin (ví d nh đ i v i ki u t n công thông tin (ví d nh đ i v i ki u t n công ệ ể ả ệ ể ả replay attacks)) replay attacks ư ố ớ ể ấ ư ố ớ ể ấ ụ ụ

Cipher-block chaining (CBC) Cipher-block chaining (CBC)

 Trong ki u mã hóa ể

cipher-block chaining (CBC):

 Nh v y, m i kh i ciphertext ph thu c vào t

 M i kh i plaintext đ ố mã hóa. ư ậ

c c khi đ c ượ XOR v i kh i ciphertext tr ớ ố ướ ượ ỗ

ỗ ụ ấ t c các kh i ố ả

ộ đ u đ n th i đi m đó ố plaintext xu t hi n t ệ ừ ầ ể ờ

c mã hóa, ta ấ ả ệ ỗ ượ

 Đ đ m b o tính duy nh t c a m i thông đi p đ ở ạ initialization vector)

ế ấ ủ ể ả s d ng thêm vector kh i t o ( ử ụ

Cipher-block chaining (CBC) Cipher-block chaining (CBC)

CC00 = IV = IV CCii = = EEKK ( (PPii ¯

CCii – 1 – 1))

Cipher-block chaining (CBC) Cipher-block chaining (CBC)

CC00 = IV = IV PPii = = DDKK ( (CCii ) ) ¯

CCii – 1 – 1

Cipher-block chaining (CBC) Cipher-block chaining (CBC)

ng đ ượ ử ụ

ườ , không th song song hóa ạ c s d ng nh t ấ ể

 CBC là ki u mã hóa th ể  H n ch : x lý tu n t ầ ự ế ử  có th ch n gi ả ể

i pháp counter mode đ x lý song song ọ ể ử

Cipher feedback (CFB) Cipher feedback (CFB)

 B n ch t:

ấ ả

ượ ậ

 Plaintext KHÔNG đ  Plaintext đ ậ

ằ c mã hóa b ng cách XOR v i m t chu i đ c t o ra c mã hóa b ng chính thu t toán đang xét ỗ ượ ạ ớ ằ ộ

ượ b ng thu t toán mã hóa.  Bi n Block Cipher thành stream cipher ằ ế

Cipher feedback (CFB) Cipher feedback (CFB)

CC00 = IV = IV CCii = = PPii ¯

EEKK ( (CCii – 1 – 1) )

Cipher feedback (CFB) Cipher feedback (CFB)

Output feedback (OFB) Output feedback (OFB)

 B n ch t:

ấ ả

ượ ậ

 Plaintext KHÔNG đ  Plaintext đ ậ

ằ c mã hóa b ng cách XOR v i m t chu i đ c t o ra c mã hóa b ng chính thu t toán đang xét ỗ ượ ạ ớ ằ ộ

ượ b ng thu t toán mã hóa.  Bi n Block Cipher thành stream cipher ằ ế

Output feedback (OFB) Output feedback (OFB)

OO00 = IV = IV OOii = CCii =

= EEKK ( (OOii – 1 – 1) ) = PPii ¯

OOii

Output feedback (OFB) Output feedback (OFB)

OO00 = IV = IV OOii = PPii =

= EEKK ( (OOii – 1 – 1) ) = CCii ¯

OOii

Counter (CTR)

 Ki u CTR còn g i là Segmented Integer Counter (SIC) OFB, ki u Counter cũng bi n  T

ọ

ế block cipher thành stream ự ể

ể ng t ươ cipher.  T o ra block keystream ti p theo b ng cách mã hóa giá tr k ti p ị ế ế ế ằ

 Counter có th là b t kỳ hàm nào sinh ra dãy s không có giá tr l p

ạ c a "counter". ủ

ị ặ ể ấ ố

i sau m t kho ng th i gian đ lâu l ạ ủ ả ờ ộ

Counter (CTR)

ố

 CTR có tính ch t gi ng OFC, ấ  CTR cho phép gi  L u ý: vai trò c a đo n d li u ủ

i mã “ng u nhiên” b t kỳ kh i cipherytext nào ả ố

ạ ấ ẫ ữ ệ nonce gi ng nh ố ư initialization vector

 IV/nonce và giá tr counter có th đ

ư (IV)

ố ớ ộ ị

ấ ứ ư ặ ớ ị

c n i v i nhau, c ng hay XOR ể ượ đ t o thành 1 dãy bit đ c tr ng duy nh t ng v i m i giá tr counter ỗ ể ạ c thụ ể

Counter (CTR)

Initialization vector (IV)

 T t c các ki u mã hóa (ngo i tr ECB) đ u s d ng vector kh i t o

ạ ừ ử ụ ở ạ ề ấ ả

 Tác d ng c a IV: ụ

 Dummy block đ vi c x lý kh i đ u tiên không khác bi

ể (initialization vector - IV). ủ

ố ầ ử ệ t so v i ớ

 Tăng tính ng u nhiên c a quy trình mã hóa.

ệ ử ể ệ ố ế

 IV:

vi c x lý các kh i ti p thao ẫ ủ

ữ ầ ậ

bí m t  Không c n gi  C n đ m b o là h n ch vi c s d ng l ạ ả ế ệ ử ụ ầ ạ i cùng giá tr IV v i cùng ị ớ

ả 1 khóa.

Counter (CTR)

 V i CBC và CFB, s d ng l i giá tr IV làm rò r thông tin. ạ i IV làm phá v hoàn toàn tính an toàn  V i OFB và CTR, s d ng l ạ

ị ỉ

ử ụ ử ụ ỡ

ớ ớ c a h th ng ủ

bí m t cho đ n c phát sinh ng u nhiên và gi ẫ ữ ế ậ

c s n sàng đ mã hóa ệ ố  IV trong CFB ph i đ ả ượ khi n i dung c a kh i plaintext đ u tiên đ ố ủ ầ ộ ượ ể ẵ

Ch

ươ

ệ

ng 5: H mã công khai và RSA

Ly thuyêt toán hoc

 Sô nguyên tô

́ ́ ̣

ư ơ ́ ́ ́ ̀ ̣ ̉

́ ̀ ́ ̀ ̀ ́ ̀ ̉ ́

 Hai sô a va n đ

́ : Sô nguyên tô la môt sô l n h n 1, nh ng chi chia ́ ớ hêt cho 1 va chinh nó, ngoai ra không con sô nao nó có thê chia hêt n a ữ

ượ ́ ̀ ̣ ̀ ́ ́ ́

ừ ́ ̀ ́ ́ ̣ ́ ́ ́

ớ ́ ́ ̉ ̀ ̀ ̀ ̉ ́

c goi la hai sô nguyên tô cùng nhau nêu chúng không có th a sô chung nao khac 1, hay noi môt cach khac, nêu c sô chung l n nhât cua a va n la băng 1. Chúng ta có thê viêt ướ nh sau : ư

GCD(a,n)=1, (GCD-Greatest Common Divisor)

Ly thuyêt toán hoc

ọ

́ ́ ̣

̀ ̣

ớ

ọ

Hàm f: X ﬁ Y đ ư

c g i là hàm ựơ X là d nh ng vi c tìm x khi ệ

ễ

t y l

 Ham môt chi u (one-way functions): m t chi u n u tính y=f(x) v i m i x bi ề

ề i là v n đ khó. ạ

ề ế ấ

ộ ế

̣ ợ

ề ư

́ ớ

̣ ́ ́ ̀ ̣ ́ ̣ ̀ ̀ ̣

ượ

ừ

ớ

́ ́ ̉ ̣ ̀ ́ ̀ ̃

 Viêc nhân hai sô nguyên tô la môt vi du vê ham môt chi u , nhân cac sô nguyên tô l n đê tao thanh môt h p sô la dê , nh ng công c lai phân tich môt sô nguyên l n thanh dang th a sô viêc ng nguyên tô lai la môt bai toan kho (ch a co môt thuât toan tôt)

̣ ̣ ́ ̣ ́ ̀ ̣ ́

́ ̣ ̀ ̣ ̀ ́ ́ ́ ̣ ̣ ́ ́

Hàm Phi

le (Euler)

Ơ

: Hàm Phi ị ng n là s các s ố ố

ố le c a s nguyên d ố ủ cùng nhau v i n nh h n n. Kí hi u ỏ ơ ươ ệ Ф(n). ơ ớ

{0,1,2,3,4,5,6,7,8,9} ầ ủ

ư ư ầ ầ ọ

 Đ nh nghĩa nguyên t  Ví d : n=10 ụ ậ ậ ố

v i 10 là {1,3,7,9} ố ớ c a t p rút g n trên là giá tr c a hàm le ị ủ ọ Ơ Ф(n).

• T p đ y đ các ph n d là • T p rút g n các ph n d nguyên t • S các ph n t ầ ử ủ ậ ư ậ

Nh v y, Ф(10) = 4.

Hàm Phi

le (Euler)

Ơ



ấ ủ

• •

Tính ch t c a hàm Phi le: ơ thì Ф (n) = n-1. Ví d : ụ Ф (7)=6 N u n là s nguyên t ố ố cùng nhau thì: N u p, q là 2 s nguyên t ố ế ế ố

Ф (p*q)=Ф (p-1)*Ф (q-1) ví d ụ Ф(26)= Ф(2*13)= Ф(2)* Ф(13)=1*12=12

•

thi: Ф(pn) = pn-pn-1 N u p là s nguyên t ố ế ố

Hàm Phi

le (Euler)

Ơ

le : N u a, m là nguyên t

cùng nhau thì

 Đ nh lý ị ế

ố

Ví d :ụ

Thuât toan clit

́ Ơ

c chung l n nh t GCD(a, b)

Ơ ơ

ướ

ớ

ấ

 Thu t toán c lit tìm ậ A=a, B=b

while B>0

R = A mod B A = B, B = R

return A

Thuât toan clit

́ Ơ

 Ví d : GCD(1970,1066)



ụ 



gcd(1066, 904) gcd(904, 162) gcd(162, 94) gcd(94, 68) gcd(68, 26) gcd(26, 16) gcd(16, 10) gcd(10, 6) gcd(6, 4) gcd(4, 2)

1970 = 1 x 1066 + 904 1066 = 1 x 904 + 162 904 = 5 x 162 + 94 162 = 1 x 94 + 68 94 = 1 x 68 + 26 68 = 2 x 26 + 16 26 = 1 x 16 + 10 16 = 1 x 10 + 6 10 = 1 x 6 + 4 6 = 1 x 4 + 2 4 = 2 x 2 + 0 gcd(1970, 1066) = 2

02/04/13

An toàn và bảo mật thông tin

Thuât toan clit

́ Ơ

Thu t toán:

ướ

c chung l n nh t) ớ

ấ

ậ  Cho: r1 , r0

Tìm GCD(

R0 = q1.r1 + r2 R1 = q2.r2 + r3 … Rm-2 = qm-1.rm-1 + rm Rm-1 = qm.rm + 0

gcd(r0, r1) = gcd(r1,r2) gcd(r1, r2) = gcd(r2,r3) …. gcd(rm-2, rm-1) = gcd(rm-1,rm) gcd(r0, r1) = gcd(rm-1,rm)=rm

ả

i thu t k t thúc ậ ế

02/04/13

An toàn và bảo mật thông tin

Thuât toan clit

́ Ơ

Ví d : ụ Tính

ướ

c s chung l n nh t c a ớ

ấ ủ 973 và 301.

ố

r0 = 973; r1 = 301.

gcd(973; 301)

973 = 3 * 301 + 70. gcd(301; 70)

301 = 4 * 70 + 21.

gcd(70; 21)

70 = 3 * 21 + 7.

gcd(21; 7)

21 = 3 * 7 + 0

 7

Ư c s chung l n nh t là : 7

ấ

ớ

ố

ớ

Rm1 = qm.rm + 0 gcd(r0, r1) = gcd(rm1,rm)=rm

Thuât toan clit m r ng

ở ộ

́ Ơ

B đổ ề:

ồ ạ

ố

0 , r1, t n t

Cho 2 s nguyên: r ố sao cho : s.r0 + t.r1 =gcd(r0,r1)=1 Khi đó t=r1

i 2 s nguyên khác s và t -1 Theo mod r0

02/04/13

An toàn và bảo mật thông tin

Thuât toan clit m r ng

ở ộ

́ Ơ

Thu t toán :

ậ

Cho 2 s nguyên r ố

0 , r1 tìm r1

-1 theo mod r0

s.r0 + t.r1 =gcd(r0,r1)=1

 Theo b đ trên ta tìm s và t sao cho công th c trên

ứ

c s, t ta dùng công th c nh sau:

ổ ề c th a mãn ỏ ượ  Đ tìm đ ượ ể

ứ

02/04/13

An toàn và bảo mật thông tin

Thuât toan clit m r ng

ở ộ

́ Ơ

S0 =1 S1 = 0 Si = s(i-2) – q(i-1) * s(i-1)

T0 = 0 T1 = 1 ti = t(i-2) – q(i-1) * t(i-1)

…

ớ

Trong đó ta có: V i i=0,1,2,3 ri =qi+1*ri+1+ri+2

02/04/13

An toàn và bảo mật thông tin

Thuât toan clit m r ng

ở ộ

́ Ơ

S0 =1

T0 = 0

s.r0 + t.r1 =gcd(r0,r1)

S1 = 0

T1 = 1

Si = s(i-2) – q(i-1) * s(i-1)

ti = t(i-2) – q(i-1) * t(i-1) ; i=2,3,4…

Ví dụ : Cho r0=29, r1=8 tìm 8-1 theo mod 29

B cướ

qi+1

ri+1

ri+2

ri

si

ti

29

0

3

8

5

1

0

8

1

5

3

0

1

5

2

1

3

2

1 -3

3

1

2

1 -1

4

2

4

2

1

0

2 -7

5

3

11

Rõ ràng : 29*(-3) + 8*11 = 1 s=3, t=11

Gi

i thi u H mã công khai và

ớ

ệ

ệ RSA

 V n đ phát sinh trong các h th ng mã hóa c đi n là vi c th ng ệ ố

ề ệ ố

i g i A và ng ổ ể ườ ườ ử

 Đ b o m t khóa

ấ ấ  Trên th c t t, do nh t chung khóa m t ự ế i nh n B. ậ K là c n thi ầ ủ ế

ậ K gi a ng ữ ầ K gi a A và B. đó, c n có s trao đ i thông tin v khóa ữ ổ K, A và B ph i trao đ i v i nhau trên m t kênh ổ ớ ộ

ầ ể ả ạ ậ

ậ ậ ự ấ ể ả

, nhu c u thay đ i n i dung c a khóa ổ ộ ề ự ả liên l c th t s an toàn và bí m t.  Tuy nhiên, r t khó có th b o đ m đ ả K v n có th b phát hi n b i ng c s an toàn c a kênh liên ủ ượ i C! ệ l c nên mã khóa ạ ự ở ể ị ườ ẫ

Gi

i thi u H mã công khai và

ớ

ệ

ệ RSA

 Ý t

ng v h mã công khai đ

c Martin Hellman, Ralph Merkle

ưở

ề ệ

ượ

và Whitfield Diffie t

i Đ i h c Stanford gi

ạ ạ ọ

ệ

 Sau đó, ph

ớ ng pháp Diffie-Hellman c a Martin Hellman và

ươ

i thi u vào năm 1976. ủ

c công b .

Whitfield Diffie đã đ

ượ

ố  Năm 1977, trên báo "The Scientific American", nhóm tác gi

ng pháp RSA, ph

ươ ấ

ử ụ

ộ ụ

ứ

ệ

ề

ả Ronald Rivest, Adi Shamir và Leonard Adleman đã công b ố ng pháp mã hóa khóa công c ng n i ph ổ ươ c s d ng r t nhi u hi n nay trong các ng d ng mã ti ng và đ ượ ế hóa và b o v thông tin ệ ả

Gi

i thi u H mã công khai và

ớ

ệ

ệ RSA

 M t h mã công khai s d ng hai lo i khóa:

ộ ệ

ử ụ

ạ ượ

c công b r ng rãi và đ ố ộ

ượ

i n m gi

 khóa công khai (public key) đ s d ng trong vi c mã hóa, ử ụ ỉ

ượ

ộ i mã thông tin đã đ

ệ  khóa riêng (private key) ch do m t ng ượ

ể ả

c và đ ữ ườ ắ c mã hóa b ng khóa ằ

ữ

s d ng đ gi ử ụ công khai.  Các ph ươ ệ ự

ng pháp mã hóa này khai thác nh ng ánh x ệ

ớ

ệ K thì m i có th th c hi n đ

c ấ c khóa riêng

ạ f mà vi c ệ ượ f –1 r t khó so v i vi c th c hi n ánh x ạ c ượ

ự ể ự

ệ

ớ

th c hi n ánh x ng f. Ch khi bi ỉ ánh x ng ạ

ạ t đ ế ượ ượ f –1 . c

Ph

ng pháp RSA

ươ

 Năm 1978, R.L.Rivest, A.Shamir và L.Adleman đã đ xu t h mã

ấ ệ

ề

công khai RSA.

 Trong ph

c th c hi n

ươ

ề

ượ

ự

ệ

t c các phép tính đ u đ ấ ả ố

ủ

ố ẻ p và q khác nhau.

ng pháp này, t trên Zn v i ớ n là tích c a hai s nguyên t

 Khi đó, ta có f (n) = (p–1) (q–1)

Ph

ng pháp RSA

ươ

Phát sinh khóa

l n ọ ẫ ố ố ớ p và q

n = p.q Ch n ng u nhiên 2 s nguyên t Tính s làm modulo c a h th ng: ệ ố ủ ố

t ế Ф(n)=(p-1)(q-1)

 Ta đã bi ẫ ọ

Ch n ng u nhiên khoá mã hóa b

 Trong đó 1

Gi i ph i mã ươ ng trình sau đ tìm khoá gi ể

•  b.a=1 mod Ф(n) v i 0≤a≤

a sao cho ả a = b–1 mod Ф(n) (b ng thu t toán Euclide m r ng) ở ộ ằ

ậ Ф(n) ớ

Khoá mã công khai Kpub={b,n} Gi khoá riêng bí m t ữ ậ Kpr={a,p,q}

Ph

ng pháp RSA

ươ

 Hàm mã hóa: S d ng khóa riêng

ử ụ

KKpubpub

Hàm g i mã  Hàm g i mã

ả ả

ử ụ ử ụ

:s d ng khóa K :s d ng khóa K prpr

Ph

ng pháp RSA

ươ

i Bob sau khi

 Ví d :ụ Alice s g i m t b n rõ (x=4) t

ẽ ử

ả

ộ

ớ

Bob g i cho cô khóa công khai

ử

M t s ph ộ ố

ươ

ng pháp t n công ấ

RSA

 Tính ch t an toàn c a ph

ng pháp RSA d a trên c s chi phí cho ươ ự ủ

c ấ i mã s quá l n nên xem nh không th th c hi n đ ả ơ ở ệ vi c gi ệ ư ẽ ớ

ể ự  Vì khóa là công khai nên vi c t n công b khóa ph ệ ấ ươ

c khóa riêng t ẻ ị ự

ượ ng pháp RSA ng ươ đó tính ượ p, q c a ủ n, t ừ ng d a vào khóa công khai đ xác đ nh đ n đ tính ể ự ề

th ứ đ c a. ể ườ ng. Đi u quan tr ng là d a vào ọ ượ

Ph

ng pháp s d ng

f (n)

ươ

ử ụ

 Gi

c giá tr ả ử ệ ị

ị f (n). Khi đó vi c xác đ nh ng trình sau i hai ph s ng giá tr ị p, q đ ươ ả

 Thay q = n/p, ta đ

)

t đ i t n công bi ế ượ ườ ấ c đ a v vi c gi ư ệ ề ượ n = p (cid:215) c ph ượ

)1 =++ np

 p, q chính là hai nghi m c a ph

- - q ng trình b c hai ậ ươ )( ( ( -= nf p 1 ) ( ) ( 1

ươ

ng trình b c hai này. Tuy nhiên ị f (n) còn khó h n vi c xác đ nh hai ệ ậ ơ ị

v n đ phát hi n đ ệ th a s nguyên t ấ ừ ề ố ệ ủ c giá tr ượ ố ủ n. c a

ậ

ừ

Thu t toán phân tích ra th a s p-1ố

Nh p ậNh p ậ nn và

và BB 1.1. a a = 2= 2 2.2. forfor j j = 2 = 2 toto B B dodo

a a = = aajj mod mod nn

3.3. d d = gcd( 4.4. ifif 1 < = gcd(a a -- 1, 1, nn)) 1 < d d < < nn thenthen

c a c a ừ ừ (thành công) ố ủ n n (thành công) ố ủ

dd là th a s nguyên t là th a s nguyên t ố ố elseelse không xác đ nh đ không xác đ nh đ c a c a nn ượ ượ ị ị c th a s nguyên t ố c th a s nguyên t ố ừ ừ ố ủ ố ủ

(th t b i) ấ ạ (th t b i) ấ ạ

ậ

ừ ố

Thu t toán phân tích ra th a s p- 1

ậ ậ ơ ộ

 Thu t toán Pollard ệ

ả ữ ố ừ ả ố

p-1 (1974) là m t trong nh ng thu t toán đ n các s ố ẻ n ố

gi n hi u qu dùng đ phân tích ra th a s nguyên t nguyên l n. Tham s đ u vào c a thu t toán là s nguyên (l ) ủ c n đ ầ ể ố ầ ớ c phân tích ra th a s nguyên t ừ ậ và giá tr gi ố ị ớ ạ B. i h n ượ ố

t) và ế B là m t s nguyên đ l n, v i ớ ộ ố ủ ớ

ả ử n = p.q (p, q ch a bi  Gi ỗ m i th a s nguyên t ố ư ố k, s ừ

(

pkBk

- (cid:222) - (cid:217) £

) 1

) B !1

ậ

Thu t toán phân tích ra th a s ừ ố p-1



cu i vòng l p (b c 2), ta có Ở ố ặ ướ

a ” 2B! (mod n)

 Suy ra: a ”  Do p|n nên theo đ nh lý Fermat, ta có : ị

 Do (p-1)|B!, nên

2B! (mod p)

b ở ướ 2p-1 ” ủ

a ”

 Vì th , n u ế d = gcd(a - 1,n) thì d = p

1 (mod p) c 3 c a thu t toán, ta có: ậ 1 (mod p) p|(a - 1) và p|n nên c 4: b ế ở ướ

ậ

Thu t toán phân tích ra th a s ừ ố p-1

ả ử n = 15770708441.

s ụ ậ

 Ví d :ụ  Gi  Áp d ng thu t toán b = 11620221425 ở ướ d = 135979.

 Trong tr

p – 1 v i ớ B = 180, chúng ta xác đ nh đ ị c 3 c a thu t toán và xác đ nh đ ượ ủ ậ ượ a c c giá tr ị ị

thành ợ ườ ừ ố ố

ng h p này, vi c phân tích ra th a s nguyên t nh khi ỏ ừ ố ố

ệ công do giá tr 135978 ch có các th a s nguyên t ỉ ị phân tích ra th a s nguyên t ừ ố

135978 = 2 ·

 Do đó, khi ch n ọ B ‡

173 s đ m b o đi u ki n 135978 ‰ B! : ố 3 · ẽ ả 131 · ả 173 ề ệ

ậ

Thu t toán phân tích ra th a s ừ ố p-1

ỗ

 Trong thu t toán ậ i đa 2log ỏ ố ng và nhân

 Vi c tính USCLN s d ng thu t toán Euclide có đ ph c t p

ừ ử ụ ậ p - 1 có B - 1 phép tính lũy th a modulo, m i phép 2B phép nhân modulo s d ng thu t toán bình

ứ ạ O((log ử ụ ậ ộ

 Nh v y, đ ph c t p c a thu t toán là: ứ ạ

đòi h i t ph ươ ệ n)3).

ư ậ ủ ậ ộ

O(B log B(log n)2 + (log n)3)

ậ

 Xác su t ch n giá tr

Thu t toán phân tích ra th a s ừ ố p-1 ị B t ươ

ề ệ ấ ố ọ ng đ i nh và th a đi u ki n là r t ỏ ấ ỏ

th p. ấ

 Khi tăng giá tr ị B (ch ng h n nh ) thì gi ơ

ư ả ẳ

B »

ư ẽ ậ i thu t s thành ậ ẽ i thu t chia ậ ả

ạ công, nh ng thu t toán này s không nhanh h n gi d n nh trình bày trên. ư ầ

ậ

Thu t toán phân tích ra th a s ừ ố p-1

ả ươ

ng pháp RSA trong c ấ ố p mà (p - 1) ch có các ướ ỉ

ố ấ

i thu t này ch hi u qu khi t n công ph  Gi ậ ỉ ệ ả ợ n có th a s nguyên t ng h p tr ố ừ ườ r t nh s nguyên t ỏ ố ể ễ

ố ớ ả ơ

 Chúng ta có th d dàng xây d ng m t h th ng mã hóa khóa công ự ộ ệ ố p - 1. Cách đ n gi n i thu t t n công c ng RSA an toàn đ i v i gi ậ ấ ả ộ p = 2p1 + 1 cũng là s ố ố p1 l n, mà nh t là tìm m t s nguyên t ớ ấ q = 2q1 + 1 nguyên t l n và nguyên t ố ớ

q1 nguyên t tìm ộ ố ng t ự , t ố ươ .ố

B khóa d a trên các t n

ẻ

ấ

ự công l p l

i

ặ ạ

ể ị ổ ươ

 Simons và Norris: h th ng RSA có th b t n th ệ ố ế

ng khi s d ng ử ụ n, b} và ặ ộ

e (mod n)

t c p khóa công c ng { khóa sau: khóa t n công l p liên ti p. N u đ i th bi ủ ế ặ ế ấ C thì có th tính chu i các t t ừ ể ừ ố ỗ

ế ầ ử Cj trong chu i ỗ C1, C2, C3,…., Ci sao cho Cj = C

e (mod n)

C1=Ce (mod n) C2=C1 e (mod n) … Ci=Ci-1  N u có m t ph n t ộ thì khi đó s tìm đ c ẽ ượ M = Cj-1 vì

Cj = Cj-1 C = Me (mod n)

ẻ

ự

ấ

i

B khóa d a trên các t n công l p l ặ ạ

 Ví d : Gi

t { s anh ta bi ế n, b, C}={35, 17, 3},anh ta s tính: ẽ ả ử

 Vì C2 = C nên M = C1 = 33

ụ C1 = Ce (mod n) = 317 (mod 35) = 33 e (mod n) = 3317 (mod 35) = 3 C2 = C1

ự

S che d u thông tin trong h ệ ấ th ng RSA

ố

 H th ng RSA có đ c đi m là thông tin không ph i luôn đ

c che ệ ố ể ả ặ ượ

d u. ấ

 Gi li u nào thu c t p sau ệ

s ng ả ử e = 17, n = 35. N u anh ta mu n g i b t c d ở ấ ứ ữ ế ố

i g i có ườ ở ộ ậ

{1, 6, 7, 8, 13, 14, 15, 20, 21, 22, 27, 28, 29, 34} ả ủ i chính là d li u ban đ u. ữ ệ ạ ầ Nghĩa là, ế ệ

 Còn khi p = 109, q = 97, e = 865 thì h th ng hoàn toàn không có

thì k t qu c a vi c mã hóa l M = Me mod n.

ệ ố

s che d u thông tin, b i vì: ự ấ ở

" M, M = M865 mod (109*97)

ự

S che d u thông tin trong h ệ ấ th ng RSA

ố

 V i m i giá tr

ỗ ườ ng h p k t qu mã hóa chính là d ữ ế ả ợ

ị n, có ít nh t 9 tr ớ li u ngu n ban đ u. Th t v y, ệ ầ ồ

ấ ậ ậ M = Me mod n

hay:

M = Me mod p và M = Me mod q (*)

 V i m i ớ

i pháp thu c t p ỗ e, m i đ ng th c trong (*) có ít nh t ba gi ỗ ẳ ứ ấ ả ộ ậ

 S thông đi p không đ

{0, 1, -1}.

ệ ượ c che d u (không b thay đ i sau khi mã ị ấ ổ

ố hóa):

m = [1+gcd(e-1, p-1)][1+gcd(e-1), q-1]

Nh n xét ậ

 M u ch t đ có th gi ố ể

i mã đ c thông tin là có đ c giá tr ể ả ấ ượ ượ ị p và q

ị n.

t o nên giá tr ạ  Khi có đ c hai giá tr này, ta có th d dàng tính ra đ c ượ ể ễ ị ượ f (n) =

ậ

 N u s nguyên ố

(p – 1)(q – 1) và giá tr ị a = b–1 mod f (n) theo thu t toán Euclide m ở r ng. ộ ế ể ượ ố

, t c là c phân tích ra th a s nguyên t ố ứ c xác đ nh thì xem nh tính an toàn c a ủ n có th đ ể ượ ừ ư

giá tr ị p và q có th đ ph ị ng pháp RSA không còn đ ượ ươ c b o đ m n a. ả ữ ả

Nh n xét ậ

ạ ng pháp RSA d a trên c s các ơ ở ự i quy t vi c ế ư ệ ả ả

 Năm 1994, Peter Shor, m t nhà khoa h c t

 Nh v y, tính an toàn c a ph ủ ư ậ ươ máy tính t i th i đi m hi n t i ch a đ kh năng gi ạ ệ ể . phân tích các s nguyên r t l n ra th a s nguyên t ấ ớ ộ

ủ ố ờ ố ừ ố

ệ ạ ọ

ư ệ ậ ộ

ng t . i phòng thí nghi m AT&T, đã đ a ra m t thu t toán có th phân tích m t cách hi u qu ộ ả các s nguyên r t l n trên máy tính l ấ ớ ể ượ ử ố

V n đ s nguyên t

ề ố

ấ

ố

ệ ố ố

 Đ b o đ m an toàn cho h th ng mã hóa RSA, s nguyên ể ễ

n = pq n ra ể ế ệ

 Hi n t

ph i đ l n đ không th d dàng ti n hành vi c phân tích th a s nguyên t .

i, các thu t toán phân tích th a s nguyên t đã có th gi ừ ố i ể ả

 Đ an toàn, s nguyên t

ể ả ả ả ủ ớ ừ ố ệ ạ quy t đ ế ượ ậ ố ậ ố

c các s nguyên có trên 130 ch s (th p phân). ư ầ ố p và q c n ph i đ l n, ví d nh trên 100 ụ ố ố ữ ố ả ủ ớ

đây là gi ề ặ ở ả ế ế

ể ể ng ể ch s . ữ ố  V n đ đ t ra ấ ộ i quy t bài toán: làm th nào đ ki m tra n là s ố ộ ố ươ

m t cách nhanh chóng và chính xác m t s nguyên d nguyên t hay h p s ? ợ ố ố

V n đ s nguyên t

ề ố

ấ

ố

ị ộ ố ươ ố ố khi và ch ỉ

 Theo đ nh nghĩa, m t s nguyên d ế

 T đó suy ra,

khi n ch chia h t cho 1 và ỉ n là s nguyên t ố

ng ỉ khi và ch khi n ( đây ch xét các s nguyên d ướ ỉ ng). ươ c s ố

2,...,

Ø ø Ø ø d ừ ươ n không có n º ß º ß

ở n là s nguyên t ố ố ng nào thu c đo n ạ ộ  . Nh v y, ta có: ư ậ n là s nguyên t ố ố

)

(

)

2,...,

( 0 mod

Ø ø Ø ø (cid:219) " ˛ (cid:216) ” º ß º ß

V n đ s nguyên t

ề ố

ấ

ố

ng n là s nguyên t theo ph ng ệ ể ộ ố ươ ố ố ươ

 Vi c ki m tra m t s nguyên d ẽ ư ờ

pháp trên s đ a ra k t qu hoàn toàn chính xác. ế ả

ấ ớ

 Tuy nhiên, th i gian x lý c a thu t toán rõ ràng là r t l n, ho c ặ ng đ i ố

ậ c, trong tr ng h p ử ể ự ợ n t ủ ệ ườ ượ ươ

th m chí không th th c hi n đ ậ l n. ớ

Thu t toán Miller-Rabin

ậ

n là s nguyên t ự ế ộ ố ươ ệ ể ố

 Trên th c t th ườ Carlo,  ví d : ụ

ng ố ng pháp thu c nhóm thu t toán Monte , vi c ki m tra m t s nguyên d ng áp d ng các ph ụ ươ ậ ộ

ậ

 thu t toán Solovay-Strassen hay thu t toán Miller-Robin;  thu t toán Miller-Robin th ơ ườ

c s d ng ph bi n h n. ng đ ổ ế ử ụ ậ ậ ượ

ậ

Thu t toán thu c nhóm Monte ộ Carlo

 Thu t toán thu c nhóm Monte Carlo đ

ậ ượ ẳ

ử ụ ậ ộ ủ ị ệ ư

ộ ấ i thu đ i và câu tr l ượ ặ ả

c s d ng trong vi c kh ng đ nh hay ph đ nh m t v n đ nào đó. Thu t toán luôn đ a ra câu ị ề c ch có kh năng ho c là “Có” (yes) tr l ỉ ả ờ ả ờ ho c là “Không” (no) ặ

ậ ậ

 Thu t toán “yes-biased Monte Carlo” là thu t toán Monte Carlo, i ả ờ

i “Có” (Yes) luôn chính xác nh ng câu tr l ư

trong đó, câu tr l ả ờ “Không” (No) có th không chính xác ể

Thu t toán Miller-Rabin

ậ



n có th đ ể : X lý nhanh (s nguyên d ử ươ ể ượ ể

ố v i log c ki m tra ng các bit trong bi u ỉ ệ ớ ứ ể ng 2n, t c là s l ố ượ

u đi m Ư trong th i gian t l ờ di n nh phân c a ị ễ

ả

i đ ạ ượ ế ậ ố ủ n) ậ ế ả

ủ ộ ợ ế

 Có kh năng k t lu n c a thu t toán không hoàn toàn chính xác, ậ nghĩa là có kh năng m t h p s c k t lu n là s nguyên ố n l , m c dù xác su t x y ra k t lu n không chính xác là không cao. t ậ ố  Có th kh c ph c b ng cách th c hi n thu t toán nhi u l n đ ể ự ng cho phép

ề ầ ặ ể ắ

i ng ậ ướ ụ ả ệ ố ưỡ ế ậ ả

ấ ả ằ gi m kh năng x y ra k t lu n sai xu ng d  k t lu n có đ tin c y cao ậ ả ậ ế ộ

Thu t toán Miller-Rabin

ậ

ng ớ ươ

n = 2km + 1 v i m l a ˛ ẻ {1, 2, ..., n – 1} ng ươ ọ ố

Phân tích s nguyên d ố Ch n ng u nhiên s nguyên d ẫ Tính b = am mod p if b ”

K t lu n “ ậ p là s nguyên t ” và d ng thu t toán ố ừ ậ 1 (mod p) then ố ế

end if for i = 0 to k - 1

p - 1 (mod p) then

ậ p là s nguyên t ” và d ng thu t toán ố ừ ậ ố

if b ” K t lu n “ ế else b = b2 mod p end if

end for K t lu n “ ế ậ p là h p s ” ố ợ

Thu t toán Miller-Rabin

ậ

 Thu t toán Miller-Rabin là thu t toán “yes-biased Monte Carlo” đ i ố ậ ng  Xác su t x y ra k t lu n sai, nghĩa là thu t toán đ a ra k t lu n “

v i phát bi u “s nguyên d n là h p s ”. ợ ươ ố ố ớ

ậ n ư ế ậ ậ

ế i đa là 25%. ố ố ố

ế ấ ả là s nguyên t ” khi  N u áp d ng thu t toán ụ ậ

c k t lu n “ ỉ ố ị a khác nhau mà ta v n ẫ n là s nguyên t ” thì xác su t chính xác c a ế ậ n th t s là h p s , ch t ợ ậ ự k l n v i các giá tr ớ ầ ố ủ ấ

ế thu đ k t lu n này là 1-4 ế ượ ậ ố -k  1, v i ớ k đ l n. ủ ớ

X lý sử

ố h cọ

 Tính giá tr c a bi u th c ể ị ủ  Thu t toán “bình ph

ứ z = xb mod n ng và nhân”

˛ {0, 1}, ễ b d ng nh phân ạ ươ ị ể bl-1bl-2...b1b0, bi

ậ Bi u di n 0£ i

end for

Mã hóa đ i x ng VS mã hóa ố ứ b t đ i x ng ấ ố ứ

ướ c có u đi m x lý r t nhanh so ử ư ể ấ

 Các ph ớ

ươ v i các ph ng pháp mã hóa khóa công c ng. ng pháp mã hóa quy ươ ộ

ượ ầ

 Do khóa dùng đ mã hóa cũng đ ể ậ ộ

c dùng đ gi bí m t n i dung c a khóa và mã khóa đ ữ

ợ

ể ả ượ ng h p khóa đ ị ủ ả ẫ ườ ả ự ế

ươ

i mã nên c n c g i là khóa ph i gi ọ ả c trao đ i bí m t (secret key). Ngay c trong tr ượ ổ ậ tr c ti p thì mã khóa này v n có kh năng b phát hi n. V n đ ề ấ ệ khó khăn đ t ra đ i v i các ph ng pháp mã hóa này chính là bài ặ ố ớ toán trao đ i mã khóa. ổ

Mã hóa đ i x ng VS mã hóa ố ứ b t đ i x ng ấ ố ứ

Ñ o äd a øi m a õk h o ùa ( b i t s )

ồ ị ậ

Đ th so sánh chi phí công phá khóa bí m t và khóa công c ngộ

Mã hóa đ i x ng VS mã hóa ố ứ b t đ i x ng ấ ố ứ

ễ ị ấ ậ

ể ộ ượ ơ i gi ườ ầ ả ả ậ

 Khóa công c ng d b t n công h n khóa bí m t. c khóa bí m t, ng  Đ tìm ra đ thông tin liên quan đ n các đ c tính c a văn b n ngu n tr ặ ế mã hóa đ tìm ra manh m i gi ể pháp vét c n mã khóa. ạ ệ

 Ngoài ra, vi c xác đ nh xem thông đi p sau khi gi ệ c khi mã hóa hay không l ướ

ướ i mã thay vì ph i s d ng ph i mã c n ph i có thêm m t s ộ ố c khi ủ ng ươ ồ ả ả ử ụ ả ố

 Đ i v i các khóa công c ng, vi c công phá hoàn toàn có th th c ệ

i mã có đúng là i là m t v n đ ề ộ ấ ả ạ ầ

ể ự ộ

c v i đi u ki n có đ tài nguyên và th i gian x lý. ủ ử ờ ị thông đi p ban đ u tr ệ khó khăn. ố ớ hi n đ ệ ượ ề ớ ệ

ng 6:

ươ

H m t mã ElGamal

Ch ệ ậ

Bài toán logarithm r i r c

ờ ạ

 Elgamal đã phát tri n m t h m t khoá công khai d a trên bài toán ậ

ể ệ ộ

ờ ạ ượ

logarithm r i r c. Bài toán logarithm r i r c đ ờ ạ I = (p,a ,b ) trong đó p là s nguyên t ư nguyên ố ự c phát bi u nh sau: ể ầ ử ố a ˛ Zp là ph n t ,

thu , ỷ b ˛ Zp* ụ ấ a, 0 £ a £ p-2 sao cho:

M c tiêu:Hãy tìm m t s nguyên duy nh t ộ ố a a ” b (mod p) Ta s xác đ nh s nguyên ị a b ng ằ ẽ ố loga b

ệ ậ

H m t mã khoá công khai Elgamal trong Zp

 T o khóa:

 Cho p là s nguyên t

ạ

sao cho bài toán logarithm r i r c trong ố ờ ạ

nguyên thu

ỷ a ˛ Zp* . {2,3,..,p-2} là khoá bí m t th nh t (khoá c a ng ậ ứ ủ ấ i ườ

ố i. ả Zp là khó gi  Ch n ọ ph n t ầ ử ˛  Ch n a ọ nh n)ậ

 Ta tính b ” a a (mod p)}  Khi đó Kpub=( p, a ,b ) đ ượ Kpr=(a) là khóa bí m tậ

c g i là khóacông khai ọ

ệ ậ

H m t mã khoá công khai Elgamal trong Zp

 Ch n m t s ng u nhiên bí m t

 Hàm mã hóa: ọ

ộ ố ẫ ậ k ˛ Zp-1, ta xác đ nh: ị

ek (x,k) = (y1 ,y2 )

trong đó

y1 = a k mod p y2 = xb k mod p

ệ ậ

H m t mã khoá công khai Elgamal trong Zp

 Hàm gi

i mã: ả

a )-1 mod p

ị  v i ớ y1 ,y2 ˛ Zp* ta xác đ nh:

dk(y1 ,y2 ) = y2 (y1

ệ ậ

H m t mã khoá công khai Elgamal trong Zp

 Ví d :ụ

ệ ậ

H m t mã khoá công khai Elgamal trong Zp

 Ví d :ụ

x = 1299 t i Bob. s Alice mu n g i thông báo ớ = 2, a = 765. Khi đó = 2765 mod 2579 = 949 ố

s s ng u nhiên k mà cô ch n là k = 853. Sau đó cô ta tính ử ọ

949^853 mod 2579 = 2396

- Cho p = 2579, a b - Bây gi ta gi ờ ả ử Gi ẫ ả ử ố y1 = 2853 mod 2579= 435 y2 = 1299 · - Khi đó Bob thu đ y = (435,2396), anh ta tính ượ ả

x = 2396 ·

c b n mã (435765)-1 mod 2579= 1299 - Đó chính là b n rõ mà Alice đã mã hoá. ả

H m t mã d a trên đ

ng

ệ ậ

ườ

ự cong Elliptic

V nhà đ c thêm

ọ

ề

Ch

ữ

ố

ng 7: Ch ký s ươ (Digital signature)

N i dung

ộ

ệ ử ữ

ệ

 M c tiêu c a ch ký đi n t ủ  M t s khái ni m c b n ơ ả  S đ ch ký RSA ữ  S đ ch ký ELGAMAL ữ ụ ộ ố ơ ồ ơ ồ

ụ

ữ

M c tiêu c a ch ký s ố ủ (Digital Signature)

ậ ườ

ch i trách nhi m (Non-Repudiation) i dùng (Authentication)  Xác nh n ng  Tính toàn v n thông tin (Data Integrity) ẹ  Không th t ố ể ừ ệ

M t s khái ni m c b n

ộ ố

ơ ả

ệ

 Ch ký đi n t

ỗ ữ ệ ấ ồ ố ị

ệ ử: chu i d li u cho phép xác đ nh ngu n g c/xu t ể ệ

x /th c th đã t o ra 1 thông đi p. ạ  Thu t toán phát sinh ch ký đi n t ng pháp t o ra ch ký ữ ệ ử: ph ươ ữ ạ ữ ứ ự ậ

đi n tệ ử

ệ ử: Bao g m ồ

 Giao th c ký đi n t ứ ậ ậ

ươ -thu t toán phát sinh ch ký đi n t ệ ử ng ng đ ki m ch ng ch ký đi n t -thu t toán t ứ ữ ể ể ữ ứ . ệ ử

Mã hóa khóa công khai



Public key: M i ng i đ u có th s d ng đ c ọ ườ ề ể ử ụ ượ

i ch s h u c p khóa ỉ ườ ặ

Private key: Ch ng m i có đ s d ng ớ ủ ở ữ ậ ể ử ụ  B o m t thông tin ả

Ý t

ng: ch ký đi n t

ưở

ệ ử

ữ

Private key: Ch ng i ch s h u c p khóa m i có đ ký ỉ ườ ủ ở ữ ớ ể ặ

 





Public key: M i ng ọ ườ ề i đ u có th ki m tra ch ký ể ể ữ

ị

ố

Đ nh nghĩa ch ký s (Digital ữ Signature)

 M t s đ ch kí s là b 5( P, A, K, S, V) tho mãn các đi u ki n

ữ ề ệ ả ộ ố

ệ ể

ộ ơ ồ i đây: ướ ậ ậ ạ ạ ữ ữ

ạ

ớ ỗ ộ S và là m t ộ

˛ ữ i m t thu t toán kí ậ ộ V. d  P là t p h u h n các b c đi n có th . ứ  A là t p h u h n các ch kí có th . ể ữ  K không gian khoá là t p h u h n các khoá có th . ậ ể sigk ˛  V i m i k thu c K t n t ạ ồ verk thu t toán xác minh

˛ ˛ ữ A tho mãn ph A và verk: P· A ﬁ{ true,false} là nh ng hàm sao ng ệ P và m i ch kí y ỗ ươ ữ ả

i đây. ậ  M i ỗ sigk : P ﬁ cho m i b c đi n x ỗ ứ trình d ướ

S đ ch ký RSA

ơ ồ ữ

S đ ch ký RSA

ơ ồ ữ

Phát sinh khóa

l n ọ ẫ ố ố ớ p và q

Tính s làm modulo c a h th ng: n = p.q 1) Ch n ng u nhiên 2 s nguyên t 2) ệ ố ủ ố

t ế Ф(n)=(p-1)(q-1)

 Ta đã bi ẫ ọ

3) Ch n ng u nhiên khoá mã hóa b

 Trong đó 1

i ph i mã ng trình sau đ tìm khoá gi ể ươ

a sao cho ả a = b–1 mod Ф(n) (b ng thu t toán Euclide m r ng) ở ộ ằ

4) Gi •  b.a=1 mod Ф(n) v i 0≤a≤ ậ Ф(n) ớ

5) Khoá mã công khai Kpub={b,n}

6) Gi khoá riêng bí m t ữ ậ Kpr={a,p,q}

S đ ch ký RSA

ơ ồ ữ

Hàm ký

sigk(x) xa mod n v i x Zn

˛ ớ

Hàm ki m tra ể

ớ

˛ Verk(x,y) = true → yb mod n = x v i x,y Zn

S đ ch ký RSA

ơ ồ ữ

S đ ch ký ElGamal

ơ ồ ữ

S đ ch ký ElGamal

ơ ồ ữ

 T o khóa:

ạ

 Cho p là s nguyên t sao cho bài toán logarithm r i r c trong ố ờ ạ

nguyên thu i. ả ầ ử ỷ a ˛ Zp* . ọ

ố Zp là khó gi  Ch n ph n t  Ch n ọ a ˛ {2,3,..,p-2} là khoá bí m t th nh t (khoá c a ng i ườ ứ ủ ấ ậ

nh n)ậ

 Ta tính b ” a a (mod p)  Khi đó Kpub=( p, a ,b ) đ Kpr=(a) là khóa bí m tậ

c g i là khóacông khai ượ ọ

S đ ch ký ElGamal

ơ ồ ữ

Hàm ký

k˛ {1,2..,p-2} sao cho gcd(k,p-1)=1. ọ ộ ố ẫ

• Ch n m t s ng u nhiên • Ta đ nh nghĩa hàm ký s : ị

ố SigKpr(x,k) =(g ,d )

trong đó

g = a k mod p d =(x-a*g ) k-1 mod (p-1).

S đ ch ký ElGamal

ơ ồ ữ

Hàm ki m tra ể

V i ớ x,g ˛ Zp và d ˛ Zp-1 , ta đ nh nghĩa :

ị

g .g

Ver(x, g ,d ) = true (cid:219)

x (mod p).

” a