Giáo trình tin học tìm hiểu một sơ đồ chữ kí số phần
- 6 trang
- file .pdf
Vietebooks Nguyễn Hoàng Cương
Ch−¬ng 6
Giáo trình tin học : Tìm hiểu một sơ đồ chữ kí số
C¸c s¬ ®å ch÷ kÝ sè
6.1 giíi thiÖu.
Trong ch−¬ng nµy, chóng ta xem xÐt c¸c s¬ ®å ch÷ kÝ sè (cßn ®−îc gäi
lµ ch÷ kÝ sè ). Ch÷ kÝ viÕt tay th«ng th−êng trªn tµI liÖu th−êng ®−îc dïng ®Ó
x¸c ng−êi kÝ nã. Ch÷ kÝ ®−îc dïng hµng ngµy ch¼ng h¹n nh− trªn mét bøc th−
nhËn tiÒn tõ nhµ b¨ng, kÝ hîp ®ång...
S¬ ®å ch÷ kÝ lµ ph−¬ng ph¸p kÝ mét bøc ®iÖn l−u d−íi dang ®iÖn tõ.
Ch¼ng h¹n mét bøc ®iÖn cã ký hiÖu ®−îc truyÒn trªn m¹ng m¸y tinh. Ch−¬ng
tr×nh nµy nghiªn cøu vµi s¬ ®å ch÷ kÝ. Ta sÏ th¶o luËn trªn mét vµI kh¸c biÖt
c¬ b¶n giöa c¸c ch÷ kÝ th«ng th−êng vµ ch÷ kÝ sè.
§Çu tiªn lµ mét vÊn ®Ò kÝ mét tµi liÖu. Víi ch÷ kÝ th«ng th−êng, nã lµ
mét phÇn vËt lý cña tµi liÖu. Tuy nhiªn, mét ch÷ kÝ sè kh«ng g¾n theo kiÓu
vËt lý vµo bøc ®iÖn nªn thuËt to¸n ®−îc dïng ph¶i ”kh«ng nh×n thÊy” theo
c¸ch nµo ®ã trªn bøc ®iÖn.
Thø hai lµ vÊn ®Ò vÒ kiÓm tra. Ch÷ kÝ th«ng th−êng ®−îc kiÓm tra b»ng
c¸ch so s¸nh nã víi c¸c ch÷ kÝ x¸c thùc kh¸c. vÝ dô, ai ®ã kÝ mét tÊm sÐc ®Ó
mua hµng, ng−êi b¸n ph¶i so s¸nh ch÷ kÝ trªn m¶nh giÊy víi ch÷ kÝ n»m ë mÆt
sau cña thÎ tÝn dông ®Ó kiÓm tra. DÜ nhiªn, ®©y kh«ng ph¶i lµ ph−¬g ph¸p an
toµn v× nã dÓ dµng gi¶ m¹o. M¾t kh¸c, c¸c ch÷ kÝ sè cã thÓ ®−îc kiÓm tra nhê
dïng mét thuËt to¸n kiÓm tra c«ng khai. Nh− vËy, bÊt kú ai còng cã thÓ kiÓm
tra d−îc ch÷ kÝ sè. ViÖc dïng mét s¬ ®å ch÷ kÝ an toµn cã thÓ sÏ ng¨n chÆn
d−îc kh¶ n¨ng gi¶ m¹o.
Sù kh¸c biÖt c¬ b¶n kh¸c gi÷a ch÷ kÝ sè vµ ch÷ kÝ th«ng th−êng b¶n
copy tµi liÖu ®−îc kÝ b¨ng ch÷ kÝ sè ®ång nhÊt víi b¶n gèc, cßn copy tµi liÖu
cã ch÷ kÝ trªn giÊy th−êng cã thÓ kh¸c víi b¶n gèc. §iÒu nµy cã nghÜa lµ ph¶i
cÈn thËn ng¨n ch¨n mét bøc kÝ sè khái bÞ dung l¹I. VÝ dô, Bob kÝ mét bøc ®iÖn
x¸c nhËn Alice cã kh¶ n¨ng lµm ®iÒu ®ã mét lÇn. V× thÕ, b¶n th©n bøc ®iÖn
cÇn chøa th«ng tin (ch¼ng h¹n nh− ngµy th¸ng) ®Ó ng¨n nã khái bÞ dung l¹i.
Mét s¬ ®å ch÷ kÝ sè th−êng chøa hai thµnh phÇn: thuËt to¸n kÝ vµ thuËt
to¸n x¸c minh. Bob cã thÓ kÝ ®iÖn x dïng thuËt to¸n kÝ an toµn. Ch÷ kÝ sig(x)
nhËn ®−îc cã thÓ kiÓm tra b»ng thuËt to¸n x¸c minh c«ng khai ver. Khi cho
tr−íc cÆp (x,y), thuËt to¸n x¸c minh cã gi¸ trÞ TRUE hay FALSE tuú thuéc
vµo ch÷ kÝ ®−îc thùc nh− thÕ nµo. D−íi ®©y lµ ®Þnh nghÜa h×nh thøc cña ch÷
kÝ:
§Þnh nghÜa 6.1
Trang 1
Vietebooks Nguyễn Hoàng Cương
Mét s¬ ®å ch÷ kÝ sè lµ bé 5( P,A, K,S,V) tho¶ m·n c¸c ®iÒu kiÖn d−íi
®©y:
1. P lµ tËp h÷u h¹n c¸c bøc ®iÖn cã thÓ.
2. A lµ tËp h÷u h¹n c¸c ch÷ kÝ cã thÓ.
3. K kh«ng gian kho¸ lµ tËp h÷u h¹n c¸c kho¸ cã thÓ.
4. Víi mçi K thuéc K tån t¹I mét thuËt to¸n kÝ sigk ∈ S vµ lµ mét thuËt
to¸n x¸c minh verk∈ V. Mçi sigk : P → A vµ verk: P×a →{true,false} lµ
nh÷ng hµm sao cho mçi bøc ®iÖn x∈ P vµ mèi ch÷ kÝ y∈ a tho¶ m·n ph−¬ng
tr×nh d−íi ®©y.
True nÕu y=sig(x)
verk
False nÕu y# sig(x)
Víi mçi k thuéc K hµm sigk vµ verk lµ c¸c hµm th¬× than ®a thøc.
Verk sÏ lµ hµm c«ng khai sigk lµ mËt. Kh«ng thÓ dÓ dµng tÝnh to¸n ®Ó gi¶ m¹o
ch÷ kÝ cña Bob trªn bøc ®iÖn x. NghÜa lµ x cho tr−íc, chØ cã Bob míi cã thÓ
tÝnh ®−îc y ®Ó verk = True. Mét s¬ ®å ch÷ kÝ kh«ng thÓ an toµn v« ®iÒu kiÖn v×
Oscar cã thÓ kiÓm tra tÊt c¶ c¸c ch÷ sè y cã thÓ cã trªn bøc ®iÖn x nhê dïng
thu©t to¸n ver c«ng khai cho ®Õn khi anh ta t×m thÊy mét ch÷ kÝ ®óng. Vi thÕ,
nÕu cã ®ñ thêi gian. Oscar lu«n lu«n cã thÓ gi¶ m¹o ch÷ kÝ cña Bob. Nh− vËy,
gièng nh− tr−êng hîp hÖ thèng m· kho¸ c«ng khai, môc ®Ých cña chóng ta lµ
t×m c¸c s¬ ®å ch÷ kÝ sè an toan vÒ mÆt tÝnh to¸n.
Xem thÊy r»ng, hÖ thèng m· kho¸ c«ng khai RSA cã thÓ dïng lµm s¬
®å ch÷ kÝ sè, Xem h×nh 6.1.
Nh− vËy, Bob kÝ bøc ®iÖn x dïng qui t¾c gi¶i m· RSA lµ dk,. Bob lµ
ng−êi t¹o ra ch÷ kÝ v× dk = sigk lµ mËt. ThuËt to¸n x¸c minh dïng qui t¾c m·
RSA ek. BÊt k× ai cñng cã x¸c minh ch÷ kÝ vi ek ®−îc c«ng khai.
Chó ý r»ng, ai ®ã cã thÓ gi¶ m¹o ch÷ kÝ cña Bob trªn mét bøc ®iÖn “
ngÈu nhiªn” x b»ng c¸ch t×m x=ek(y) víi y nµo ®ã; khi ®ã y= sigk(x). Mét
ph¸p xung quanh vÊn ®Ò khã kh¨n nµy lµ yªu cÇu bøc ®iÖn ch−a ®ñ phÇn d− ®Ó
ch÷ kÝ gi¶ m¹o kiÓu nµy kh«ng t−¬ng øng víi bøc ®iÖn ®©y nghÜa lµ x trõ mét
x¸c suÊt rÊt bÐ. Cã thÓ dïng c¸c hµm hash trong viÖc kÕt nèi víi c¸c s¬ ®å ch÷
kÝ sè sÏ lo¹i trõ ®−îc ph−¬ng ph¸p gi¶ m¹o nµy (c¸c hµm hash ®−îc xÐt trong
ch−¬ng 7).
H×nh 6.1 s¬ ®å ch÷ kÝ RSA
Trang 2
Vietebooks Nguyễn Hoàng Cương
Cho n= pq, p vµ q lµ c¸c sè nguyªn tè. Cho p =a= Zn vµ ®Þnh
nghÜa p= {(n,p,q,a,b):=n=pq,p vµ q lµ nguyªn tè, ab ≡ 1(mod( φ (n))) }.
C¸c gi¸ trÞ n vµ b lµ c«ng khai, ta ®Þng nghÜa :
sigk(x)= xa mod n
vµ verk (x,y)= true ⇔ x ≡ yb (mod n)
(x,y ∈ Zn)
Cuèi cïng, ta xÐt tãm t¾t c¸c kÕt hîp ch÷ kÝ vµ m· kho¸ c«ng khai. Gi¶
sö r»ng, Alice tÝnh to¸n ch− kÝ cña ta y= sigAlice(x) vµ sau ®ã m· c¶ x vµ y b»ng
hµm m· kho¸ c«ng khai eBob cña Bob, khi ®ã c« ta nhËn ®−îc z = eBob(x,y).
B¶n m· z sÏ ®−îc truyÒn tíi Bob. Khi Bob nhËn ®−îc z, anh ta sÏ tr−íc hÕt sÏ
gi¶i m· hµm dBob ®Ó nhËn ®−îc (x,y). Sau ®ã anh ta dung hµm x¸c minh c«ng
khai cña Alice ®Ó kiÓm tra xem verAlice(x,y) cã b»ng True hay kh«ng.
Song nÕu ®Çu tiªn Alice m· x råi sau ®ã míi kÝ tªn b¶n m· nhËn ®−îc
th× sao?. Khi ®ã c« tÝnh :
y= sigAlice(eBob(x)).
Alice sÏ truyÒn cÆp (z,y) tíi Bob. Bob sÏ gi¶i m· z, nhËn x vµ sau ®ã x¸c minh
ch÷ kÝ y trªn x nhê dïng verAlice. Mét vÊn ®Ò tiÓm Èn trong biÖn ph¸p nµy lµ
nÕu Oscar nhËn ®−îc cÆp (x,y) kiÓu nµy, ®−îc ta cã thay ch÷ kÝ y cña Alice
b»ng ch÷ kÝ cña m×nh.
y, = sigOscar(eBob(x)).
(chó ý r»ng,Oscar cã thÓ kÝ b¶n m· eBob(x) ngay c¶ khi anh ta kh«ng biÕt b¶n
’
râ x). Khi ®ã nÕu Oscar truyÒn(x, y ) ®Õn Bob th× ch÷ kÝ Oscar ®−îc Bob x¸c
minh b»ng verOscar vµ Bob cã thÓ suy ra r»ng, b¶n râ x xuÊt ph¸t tõ Oscar. Do
khã kh¨n nµy, hÇu hÕt ng−êi sö dông ®−îc khuyÕn nghÞ nÕu kÝ tr−íc khi m·.
6.2 s¬ ®å ch÷ kÝ ELGAMAL
Sau ®©y ta sÏ m« t¶ s¬ ®å ch÷ kÝ Elgamal ®· tõng d−íi thiÖu trong bµi
b¸o n¨m 1985. B¶n c¶ tiÕn cña s¬ ®å nµy ®· ®−îc ViÖn Tiªu chuÈn vµ C«ng
NghÖ Quèc Gia Mü (NIST) chÊp nhËn lµm ch÷ kÝ sè. S¬ ®å Elgamal (E.) ®−îc
Trang 3
Vietebooks Nguyễn Hoàng Cương
thiÕt kÕ víi môc ®Ých dµnh riªng cho ch÷ kÝ sè, kh¸c s¬ ®å RSA dïng cho c¶
hÖ thèng m· kho¸ c«ng khai lÉn ch÷ kÝ sè.
S¬ ®å E, lµ kh«ng tÊt ®Þnh gièng nh− hÖ thèng m· kho¸ c«ng khai
Elgamal. §iÒu nµy cã nghÜa lµ cã nhiÒu ch÷ kÝ hîp lÖ trªn bøc ®iÖn cho tr−¬c
bÊt kú. ThuËt to¸n x¸c minh ph¶i cè kh¶i n¨ng chÊp nhËn bÊt k× ch÷ kÝ hîp lÖ
khi x¸c thùc. S¬ ®å E. ®−îc m«t t¶ trªn h×nh 6.2
NÕu ch÷ kÝ ®−îc thiÕt lËp ®óng khi x¸c minh sÏ thµnh c«ng v× :
βγ γδ ≡ αa γ αkγ(mod p)
≡ αx(mod p)
lµ ë ®©y ta dïng hÖ thøc :
a γ+ k δ ≡ x (mod p-1)
H×nh 6.2 s¬ ®å ch÷ kÝ sè Elgamal.
Cho p lµ sè nguyªn tè sao cho bµi to¸n log rêi r¹c trªn Zp lµ khã vµ gi¶
sö α ∈ Zn lµ phÇn tö nguyªn thuû p = Zp* , a = Zp* × Zp-1 vµ ®Þnh nghÜa :
K ={(p,α ,a,β ):β ≡ α (mod p)}.
a
Gi¸ trÞ p,α ,β lµ c«ng khai, cßn a lµ mËt.
Víi K = (p,α ,a,β ) vµ mét sè ngÉu nhiªn (mËt) k∈ Zp-1. ®Þnh nghÜa :
Sigk(x,y) =(γ ,δ),
γ = α mod p
k
trong ®ã
-1
vµ δ =(x-a) k mod (p-1).
Víi x,γ ∈ Zp vµ δ ∈ Zp-1 , ta ®Þnh nghÜa :
γ δ
Ver(x,γ ,δ ) = true ⇔ β γ ≡ α (mod p).
x
Bob tÝnh ch÷ kÝ b»ng c¸ch dïng c¶ gÝa trÞ mËt a (lµ mét phÇn cña kho¸)
lÉn sè ngÉu nhiªn mËt k (dïng ®Ó kÝ lªn bøc ®iÖn x ). ViÖc x¸c minh cã thùc
hiÖn duy nhÊt b»ng th«ng b¸o tin c«ng khai.
Chóng ta h·y xÐt mét vÝ dô nhá minh ho¹.
VÝ dô 6.1
Trang 4
Ch−¬ng 6
Giáo trình tin học : Tìm hiểu một sơ đồ chữ kí số
C¸c s¬ ®å ch÷ kÝ sè
6.1 giíi thiÖu.
Trong ch−¬ng nµy, chóng ta xem xÐt c¸c s¬ ®å ch÷ kÝ sè (cßn ®−îc gäi
lµ ch÷ kÝ sè ). Ch÷ kÝ viÕt tay th«ng th−êng trªn tµI liÖu th−êng ®−îc dïng ®Ó
x¸c ng−êi kÝ nã. Ch÷ kÝ ®−îc dïng hµng ngµy ch¼ng h¹n nh− trªn mét bøc th−
nhËn tiÒn tõ nhµ b¨ng, kÝ hîp ®ång...
S¬ ®å ch÷ kÝ lµ ph−¬ng ph¸p kÝ mét bøc ®iÖn l−u d−íi dang ®iÖn tõ.
Ch¼ng h¹n mét bøc ®iÖn cã ký hiÖu ®−îc truyÒn trªn m¹ng m¸y tinh. Ch−¬ng
tr×nh nµy nghiªn cøu vµi s¬ ®å ch÷ kÝ. Ta sÏ th¶o luËn trªn mét vµI kh¸c biÖt
c¬ b¶n giöa c¸c ch÷ kÝ th«ng th−êng vµ ch÷ kÝ sè.
§Çu tiªn lµ mét vÊn ®Ò kÝ mét tµi liÖu. Víi ch÷ kÝ th«ng th−êng, nã lµ
mét phÇn vËt lý cña tµi liÖu. Tuy nhiªn, mét ch÷ kÝ sè kh«ng g¾n theo kiÓu
vËt lý vµo bøc ®iÖn nªn thuËt to¸n ®−îc dïng ph¶i ”kh«ng nh×n thÊy” theo
c¸ch nµo ®ã trªn bøc ®iÖn.
Thø hai lµ vÊn ®Ò vÒ kiÓm tra. Ch÷ kÝ th«ng th−êng ®−îc kiÓm tra b»ng
c¸ch so s¸nh nã víi c¸c ch÷ kÝ x¸c thùc kh¸c. vÝ dô, ai ®ã kÝ mét tÊm sÐc ®Ó
mua hµng, ng−êi b¸n ph¶i so s¸nh ch÷ kÝ trªn m¶nh giÊy víi ch÷ kÝ n»m ë mÆt
sau cña thÎ tÝn dông ®Ó kiÓm tra. DÜ nhiªn, ®©y kh«ng ph¶i lµ ph−¬g ph¸p an
toµn v× nã dÓ dµng gi¶ m¹o. M¾t kh¸c, c¸c ch÷ kÝ sè cã thÓ ®−îc kiÓm tra nhê
dïng mét thuËt to¸n kiÓm tra c«ng khai. Nh− vËy, bÊt kú ai còng cã thÓ kiÓm
tra d−îc ch÷ kÝ sè. ViÖc dïng mét s¬ ®å ch÷ kÝ an toµn cã thÓ sÏ ng¨n chÆn
d−îc kh¶ n¨ng gi¶ m¹o.
Sù kh¸c biÖt c¬ b¶n kh¸c gi÷a ch÷ kÝ sè vµ ch÷ kÝ th«ng th−êng b¶n
copy tµi liÖu ®−îc kÝ b¨ng ch÷ kÝ sè ®ång nhÊt víi b¶n gèc, cßn copy tµi liÖu
cã ch÷ kÝ trªn giÊy th−êng cã thÓ kh¸c víi b¶n gèc. §iÒu nµy cã nghÜa lµ ph¶i
cÈn thËn ng¨n ch¨n mét bøc kÝ sè khái bÞ dung l¹I. VÝ dô, Bob kÝ mét bøc ®iÖn
x¸c nhËn Alice cã kh¶ n¨ng lµm ®iÒu ®ã mét lÇn. V× thÕ, b¶n th©n bøc ®iÖn
cÇn chøa th«ng tin (ch¼ng h¹n nh− ngµy th¸ng) ®Ó ng¨n nã khái bÞ dung l¹i.
Mét s¬ ®å ch÷ kÝ sè th−êng chøa hai thµnh phÇn: thuËt to¸n kÝ vµ thuËt
to¸n x¸c minh. Bob cã thÓ kÝ ®iÖn x dïng thuËt to¸n kÝ an toµn. Ch÷ kÝ sig(x)
nhËn ®−îc cã thÓ kiÓm tra b»ng thuËt to¸n x¸c minh c«ng khai ver. Khi cho
tr−íc cÆp (x,y), thuËt to¸n x¸c minh cã gi¸ trÞ TRUE hay FALSE tuú thuéc
vµo ch÷ kÝ ®−îc thùc nh− thÕ nµo. D−íi ®©y lµ ®Þnh nghÜa h×nh thøc cña ch÷
kÝ:
§Þnh nghÜa 6.1
Trang 1
Vietebooks Nguyễn Hoàng Cương
Mét s¬ ®å ch÷ kÝ sè lµ bé 5( P,A, K,S,V) tho¶ m·n c¸c ®iÒu kiÖn d−íi
®©y:
1. P lµ tËp h÷u h¹n c¸c bøc ®iÖn cã thÓ.
2. A lµ tËp h÷u h¹n c¸c ch÷ kÝ cã thÓ.
3. K kh«ng gian kho¸ lµ tËp h÷u h¹n c¸c kho¸ cã thÓ.
4. Víi mçi K thuéc K tån t¹I mét thuËt to¸n kÝ sigk ∈ S vµ lµ mét thuËt
to¸n x¸c minh verk∈ V. Mçi sigk : P → A vµ verk: P×a →{true,false} lµ
nh÷ng hµm sao cho mçi bøc ®iÖn x∈ P vµ mèi ch÷ kÝ y∈ a tho¶ m·n ph−¬ng
tr×nh d−íi ®©y.
True nÕu y=sig(x)
verk
False nÕu y# sig(x)
Víi mçi k thuéc K hµm sigk vµ verk lµ c¸c hµm th¬× than ®a thøc.
Verk sÏ lµ hµm c«ng khai sigk lµ mËt. Kh«ng thÓ dÓ dµng tÝnh to¸n ®Ó gi¶ m¹o
ch÷ kÝ cña Bob trªn bøc ®iÖn x. NghÜa lµ x cho tr−íc, chØ cã Bob míi cã thÓ
tÝnh ®−îc y ®Ó verk = True. Mét s¬ ®å ch÷ kÝ kh«ng thÓ an toµn v« ®iÒu kiÖn v×
Oscar cã thÓ kiÓm tra tÊt c¶ c¸c ch÷ sè y cã thÓ cã trªn bøc ®iÖn x nhê dïng
thu©t to¸n ver c«ng khai cho ®Õn khi anh ta t×m thÊy mét ch÷ kÝ ®óng. Vi thÕ,
nÕu cã ®ñ thêi gian. Oscar lu«n lu«n cã thÓ gi¶ m¹o ch÷ kÝ cña Bob. Nh− vËy,
gièng nh− tr−êng hîp hÖ thèng m· kho¸ c«ng khai, môc ®Ých cña chóng ta lµ
t×m c¸c s¬ ®å ch÷ kÝ sè an toan vÒ mÆt tÝnh to¸n.
Xem thÊy r»ng, hÖ thèng m· kho¸ c«ng khai RSA cã thÓ dïng lµm s¬
®å ch÷ kÝ sè, Xem h×nh 6.1.
Nh− vËy, Bob kÝ bøc ®iÖn x dïng qui t¾c gi¶i m· RSA lµ dk,. Bob lµ
ng−êi t¹o ra ch÷ kÝ v× dk = sigk lµ mËt. ThuËt to¸n x¸c minh dïng qui t¾c m·
RSA ek. BÊt k× ai cñng cã x¸c minh ch÷ kÝ vi ek ®−îc c«ng khai.
Chó ý r»ng, ai ®ã cã thÓ gi¶ m¹o ch÷ kÝ cña Bob trªn mét bøc ®iÖn “
ngÈu nhiªn” x b»ng c¸ch t×m x=ek(y) víi y nµo ®ã; khi ®ã y= sigk(x). Mét
ph¸p xung quanh vÊn ®Ò khã kh¨n nµy lµ yªu cÇu bøc ®iÖn ch−a ®ñ phÇn d− ®Ó
ch÷ kÝ gi¶ m¹o kiÓu nµy kh«ng t−¬ng øng víi bøc ®iÖn ®©y nghÜa lµ x trõ mét
x¸c suÊt rÊt bÐ. Cã thÓ dïng c¸c hµm hash trong viÖc kÕt nèi víi c¸c s¬ ®å ch÷
kÝ sè sÏ lo¹i trõ ®−îc ph−¬ng ph¸p gi¶ m¹o nµy (c¸c hµm hash ®−îc xÐt trong
ch−¬ng 7).
H×nh 6.1 s¬ ®å ch÷ kÝ RSA
Trang 2
Vietebooks Nguyễn Hoàng Cương
Cho n= pq, p vµ q lµ c¸c sè nguyªn tè. Cho p =a= Zn vµ ®Þnh
nghÜa p= {(n,p,q,a,b):=n=pq,p vµ q lµ nguyªn tè, ab ≡ 1(mod( φ (n))) }.
C¸c gi¸ trÞ n vµ b lµ c«ng khai, ta ®Þng nghÜa :
sigk(x)= xa mod n
vµ verk (x,y)= true ⇔ x ≡ yb (mod n)
(x,y ∈ Zn)
Cuèi cïng, ta xÐt tãm t¾t c¸c kÕt hîp ch÷ kÝ vµ m· kho¸ c«ng khai. Gi¶
sö r»ng, Alice tÝnh to¸n ch− kÝ cña ta y= sigAlice(x) vµ sau ®ã m· c¶ x vµ y b»ng
hµm m· kho¸ c«ng khai eBob cña Bob, khi ®ã c« ta nhËn ®−îc z = eBob(x,y).
B¶n m· z sÏ ®−îc truyÒn tíi Bob. Khi Bob nhËn ®−îc z, anh ta sÏ tr−íc hÕt sÏ
gi¶i m· hµm dBob ®Ó nhËn ®−îc (x,y). Sau ®ã anh ta dung hµm x¸c minh c«ng
khai cña Alice ®Ó kiÓm tra xem verAlice(x,y) cã b»ng True hay kh«ng.
Song nÕu ®Çu tiªn Alice m· x råi sau ®ã míi kÝ tªn b¶n m· nhËn ®−îc
th× sao?. Khi ®ã c« tÝnh :
y= sigAlice(eBob(x)).
Alice sÏ truyÒn cÆp (z,y) tíi Bob. Bob sÏ gi¶i m· z, nhËn x vµ sau ®ã x¸c minh
ch÷ kÝ y trªn x nhê dïng verAlice. Mét vÊn ®Ò tiÓm Èn trong biÖn ph¸p nµy lµ
nÕu Oscar nhËn ®−îc cÆp (x,y) kiÓu nµy, ®−îc ta cã thay ch÷ kÝ y cña Alice
b»ng ch÷ kÝ cña m×nh.
y, = sigOscar(eBob(x)).
(chó ý r»ng,Oscar cã thÓ kÝ b¶n m· eBob(x) ngay c¶ khi anh ta kh«ng biÕt b¶n
’
râ x). Khi ®ã nÕu Oscar truyÒn(x, y ) ®Õn Bob th× ch÷ kÝ Oscar ®−îc Bob x¸c
minh b»ng verOscar vµ Bob cã thÓ suy ra r»ng, b¶n râ x xuÊt ph¸t tõ Oscar. Do
khã kh¨n nµy, hÇu hÕt ng−êi sö dông ®−îc khuyÕn nghÞ nÕu kÝ tr−íc khi m·.
6.2 s¬ ®å ch÷ kÝ ELGAMAL
Sau ®©y ta sÏ m« t¶ s¬ ®å ch÷ kÝ Elgamal ®· tõng d−íi thiÖu trong bµi
b¸o n¨m 1985. B¶n c¶ tiÕn cña s¬ ®å nµy ®· ®−îc ViÖn Tiªu chuÈn vµ C«ng
NghÖ Quèc Gia Mü (NIST) chÊp nhËn lµm ch÷ kÝ sè. S¬ ®å Elgamal (E.) ®−îc
Trang 3
Vietebooks Nguyễn Hoàng Cương
thiÕt kÕ víi môc ®Ých dµnh riªng cho ch÷ kÝ sè, kh¸c s¬ ®å RSA dïng cho c¶
hÖ thèng m· kho¸ c«ng khai lÉn ch÷ kÝ sè.
S¬ ®å E, lµ kh«ng tÊt ®Þnh gièng nh− hÖ thèng m· kho¸ c«ng khai
Elgamal. §iÒu nµy cã nghÜa lµ cã nhiÒu ch÷ kÝ hîp lÖ trªn bøc ®iÖn cho tr−¬c
bÊt kú. ThuËt to¸n x¸c minh ph¶i cè kh¶i n¨ng chÊp nhËn bÊt k× ch÷ kÝ hîp lÖ
khi x¸c thùc. S¬ ®å E. ®−îc m«t t¶ trªn h×nh 6.2
NÕu ch÷ kÝ ®−îc thiÕt lËp ®óng khi x¸c minh sÏ thµnh c«ng v× :
βγ γδ ≡ αa γ αkγ(mod p)
≡ αx(mod p)
lµ ë ®©y ta dïng hÖ thøc :
a γ+ k δ ≡ x (mod p-1)
H×nh 6.2 s¬ ®å ch÷ kÝ sè Elgamal.
Cho p lµ sè nguyªn tè sao cho bµi to¸n log rêi r¹c trªn Zp lµ khã vµ gi¶
sö α ∈ Zn lµ phÇn tö nguyªn thuû p = Zp* , a = Zp* × Zp-1 vµ ®Þnh nghÜa :
K ={(p,α ,a,β ):β ≡ α (mod p)}.
a
Gi¸ trÞ p,α ,β lµ c«ng khai, cßn a lµ mËt.
Víi K = (p,α ,a,β ) vµ mét sè ngÉu nhiªn (mËt) k∈ Zp-1. ®Þnh nghÜa :
Sigk(x,y) =(γ ,δ),
γ = α mod p
k
trong ®ã
-1
vµ δ =(x-a) k mod (p-1).
Víi x,γ ∈ Zp vµ δ ∈ Zp-1 , ta ®Þnh nghÜa :
γ δ
Ver(x,γ ,δ ) = true ⇔ β γ ≡ α (mod p).
x
Bob tÝnh ch÷ kÝ b»ng c¸ch dïng c¶ gÝa trÞ mËt a (lµ mét phÇn cña kho¸)
lÉn sè ngÉu nhiªn mËt k (dïng ®Ó kÝ lªn bøc ®iÖn x ). ViÖc x¸c minh cã thùc
hiÖn duy nhÊt b»ng th«ng b¸o tin c«ng khai.
Chóng ta h·y xÐt mét vÝ dô nhá minh ho¹.
VÝ dô 6.1
Trang 4