Chương 5 : Các hệ mật khóa công khai ppt

Vietebooks Nguyễn Hoàng Cương

Trang 1

Ch−¬ng 5

C¸c hÖ mËt kho¸ c«ng khai kh¸c

Trong ch−¬ng nµy ta sÏ xem xÐt mét sè hÖ mËt kho¸ c«ng khai kh¸c.

HÖ mËt Elgamal dùa trªn bµi to¸n logarithm rêi r¹c lµ bµi to¸n ®−îc dïng

nhiÒu trong nhiÒu thñ tôc mËt m·. Bëi vËy ta sÏ dµnh nhiÒu thêi gian ®Ó th¶o

luËn vÒ bµi to¸n quan träng nµy. ë c¸c phÇn sau sÏ xem xÐt s¬ l−îc mét sè hÖ

mËt kho¸ c«ng khai quan träng kh¸c bao gåm c¸c hÖ thoãng lo¹i Elgamal

dùa trªn c¸c tr−êng h÷u h¹n vµ c¸c ®−êng cong elliptic, hÖ mËt xÕp ba l«

Merkle-Helman vµ hÖ mËt McElice.

5.1. HÖ mËt Elgamal vµ c¸c logarithm rêi r¹c.

HÖ mËt Elgamal ®−îc x©y dùng trªn bµi to¸n log¶ithm rêi r¹c . Chóng

ta sÏ b¾t ®Çu b¨ng viÖc m« t¶ bµi to¸n bµi khi thiÕt lËp m«i tr−êng h÷u h¹n

Zp, p lµ sè nguyªn tè ( h×nh 5.1) ( Nhí l¹i r»ng nhãm nh©n Zp

*

lµ nhãm cyclic

vµ phÇn tö sinh cña Zp

*

®−îc gäi lµ phÇn tö nguyªn thuû).

Bµi to¸n logarithm rêi r¹c trong Zp lµ ®èi t−îng trong nhiÒu c«ng tr×nh

nghiªn cøu vµ ®−îc xem lµ bµi to¸n khã nÕu p ®−îc chän cÈn thËn. Cô thÓ

kh«ng cã mét thuËt to¸n thêi gian ®a thøc nµo cho bµi to¸n logarithm rêi r¹c.

§Ó g©y khã kh¨n cho c¸c ph−¬ng ph¸p tÊn c«ng ®· biÕt p ph¶i cã Ýt nhÊt 150

ch÷ sè vµ (p-1) ph¶i cã Ýt nhÊt mét thõa sè nguyªn tè lín. Lîi thÕ cña bµi

to¸n logarithm rêi r¹c trong x©y d−îng hÖ mËt lµ khã t×m ®−îc c¸c logarithm

rêi r¹c ,song bµi to¸n ng−îc lÊy luü thõa l¹i cã thÓ tÝnh to¸n hiÖu qu¶ theo

thuËt to¸n "b×nh ph−¬ng vµ nh©n". Nãi c¸ch kh¸c , luü thõa theo modulo p lµ

hµm mét chiÒu víi c¸c sè nguyªn tè p thÝch hîp.

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. HÖ thèng nµy ®−îc tr×nh bµy trªn h×nh 5.2.

HÖ mËt nµy lµ mét hÖ kh«ng tÊt ®Þnh v× b¶n m· phô thuéc vµo c¶ b¶n

râ x lÉn gi¸ trÞ ngÉu nhiªn k do Alice chän. Bëi vËy, sÏ cã nhiÒu b¶n m· ®−îc

m· tõ cïng b¶n râ.

Vietebooks Nguyễn Hoàng Cương

Trang 2

H×nh 2.6 Bµi to¸n logarithm rêi r¹c trong Zp

H×nh 2.7 HÖ mËt kho¸ c«ng khai Elgamal trong Zp*

Sau ®©y sÏ nm« t¶ s¬ l−îc c¸ch lµm viÖc cña hÖ mËt Elgamal .B¶n râ x

®−îc "che dÊu" b»ng c¸ch nh©n nã víi βk ®Ó t¹o y2 . Gi¸ trÞ α

k

còng ®−îc göi

®i nh− mét phÇn cña b¶n m·. Bob -ng−êi biÕt sè mò bÝ mËt a cã thÓ tÝnh ®−îc

βk

tõ α

k

. Sau ®ã anh ta sÏ "th¸o mÆt n¹" b»ng c¸ch chia y2 cho βk ®Ó thu

®−îc x.

VÝ dô 5.1

§Æc tr−¬ng cña bµi to¸n: I = (p,α,β) trong ®ã p lµ sè nguyªn tè,

α ∈ Zp lµ phÇn tö nguyªn thuû , β ∈ Zp*

Môc tiªu:H·y t×m mét sè nguyªn duy nhÊt a, 0 ≤ a ≤ p-2 sao

cho:

α

a

≡ β (mod p)

Ta sÏ x¸c ®Þnh sè nguyªn a b»ng logα β

Cho p lµ sè nguyªn tè sao cho bµi to¸n logarithm rêi r¹c trong Zp lµ

khã gi¶i. Cho α ∈ Zp

*

lµ phÇn tö nguyªn thuû.Gi¶ sö P = Zp

*

,

C = Zp

*

× Zp

*

. Ta ®Þnh nghÜa:

K = {(p, α,a,β): β ≡ α

a

(mod p)}

C¸c gi¸ trÞ p, α,β ®−îc c«ng khai, cßn a gi÷ kÝn

Víi K = (p, α,a,β) vµ mét sè ngÉu nhiªn bÝ mËt k ∈ Zp-1, ta x¸c

®Þnh:

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

trong ®ã

y1 = α

k

mod p

y2 = xβk

mod p

víi y1 ,y2 ∈ Zp

*

ta x¸c ®Þnh:

dk(y1 ,y2 ) = y2 (y1

a

)-1 mod p

Vietebooks Nguyễn Hoàng Cương

Trang 3

Cho p = 2579, α = 2, a = 765. Khi ®ã

β = 2765 mod 2579 = 949

B©y giê ta gi¶ sö Alice muèn göi th«ng b¸o x = 1299 tíi Bob. Gi¶ sö sè ngÉu

nhiªn k mµ c« chän lµ k = 853. Sau ®ã c« ta tÝnh

y1 = 2853 mod 2579

= 435

y2 = 1299 × 949853 mod 2579

= 2396

Khi ®ã Bob thu ®−îc b¶n m· y = (435,2396), anh ta tÝnh

x = 2396 × (435765)

-1 mod 2579

= 1299

§ã chÝnh lµ b¶n râ mµ Alice ®· m· ho¸.

5.1.1. C¸c thuËt to¸n cho bµi to¸n logarithm rêi r¹c.

Trong phÇn nµy ta xem r»ng p lµ sè nguyªn tè, α lµ phÇn tö nguyªn

thuû theo modulo p. Ta thÊy r»ng p vµ α lµ c¸c sè cè ®Þnh. Khi ®ã bµi to¸n

logarithm rêi r¹c cã thÓ ®−îc ph¸t biÓu d−íi d¹ng sau: t×m mét sè mò a duy

nhÊt, 0 ≤ a ≤ p-2 sao cho αa ≡β (mod p), víi β ∈ Zp

*

cho tr−íc.

Râ rµng lµ bµi to¸n logarithm rêi r¹c (DL) cã thÓ gi¶i b»ng mét phÐp

t×m kiÕm vÐt c¹n víi thêi gian cì O(p) vµ kh«ng gian cì O(1) ( bá qua c¸c

thõa sè logarithm). B»ng c¸ch tÝnh to¸n tÊt c¶ c¸c gi¸ trÞ αa

cã thÓ vµ s¾p xÕp

c¸c cÆp cã thø tù (a, αa

mod p) cã l−u ý ®Õn c¸c t¹o ®é thø hai cña chóng, ta

cã thÓ gi¶i bµi to¸n DL víi thêi gian cì O(1) b»ng O(p) phÐp tÝnh to¸n tr−íc

vµ O(p) bé nhí ( vÉn bá qua c¸c thõa sè logarithm). ThuËt to¸n kh«ng tÇm

th−êng ®Çu tiªn mµ chóng ta sÏ m« t¶ lµ thuËt to¸n tèi −u ho¸ thêi gian - bé

nhí cña Shanks.

ThuËt to¸n Shanks