Đồ án Lược đồ chữ ký chống chối bỏ có người xác nhận

B, C) = (AÙB)Ú(AC) g(A, B, C) = (AÙB)Ú(AÙC)Ú(BÙC) h(A, B, C) = A Å B Å C Ta ký hiÖu c¸c h»ng sè: K1 = 0x5a827999 K2 = 0x6ed9eba1 C¸c biÕn Xi, i = B¶ng ch©n lý cña 3 hµm: A B C f(A, B, C) g(A, B, C) h(A, B, C) 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 3 vßng Round1, Round2, Round3 ®­îc m« t¶ theo b¶ng sau: Round1: 1 A = (A + f(B, C, D) + Xo)<<3 2 D = (D + f(A, B, C) + X1)<<7 3 C = (C + f(D, A, B) + X2)<<11 4 B = (B + f(C, D, A) + X3)<<19 5 A = (A + f(B, C, D) + X4)<<3 6 D = (D + f(A, B, C) + X5)<<7 7 C = (C + f(D, A, B) + X6)<<11 8 B = (B + f(C, D, A) + X7)<<19 9 A = (A + f(B, C, D) + X8)<<3 10 D = (D + f(A, B, C) + X9)<<7 11 C = (C + f(D, A, B) + X10)<<11 12 B = (B + f(C, D, A) + X11)<<19 13 A = (A + f(B, C, D) + X12)<<3 14 D = (D + f(A, B, C) + X13)<<7 15 C = (C + f(D, A, B) + X14)<<11 16 B = (B + f(C, D, A) + X15)<<19 Round2: 1 A = (A + g(B, C, D) + Xo + K1)<<3 2 D = (D + g(A, B, C) + X4 + K1)<<5 3 C = (C + g(D, A, B) + X8 +K1)<<9 4 B = (B + g(C, D, A) + X12 + K1)<<13 5 A = (A + g(B, C, D) + X1 + K1)<<3 6 D = (D + g(A, B, C) + X5 + K1)<<5 7 C = (C + g(D, A, B) + X8 +K1)<<9 8 B = (B + g(C, D, A) + X13 + K1)<<13 9 A = (A + g(B, C, D) + X2 + K1)<<3 10 D = (D + g(A, B, C) + X6 + K1)<<5 11 C = (C + g(D, A, B) + X10 +K1)<<9 12 B = (B + g(C, D, A) + X14 + K1)<<13 13 A = (A + g(B, C, D) + X3 + K1)<<3 14 D = (D + g(A, B, C) + X7 + K1)<<5 15 C = (C + g(D, A, B) + X11 +K1)<<9 16 B = (B + g(C, D, A) + X15 + K1)<<13 Round3: 1 A = (A + h(B, C, D) +X0 + K2)<<3 2 D = (D + h(A, B, C) + X8 + K2)<<9 3 C = (C + h(D, A, B) + X4 + K2)<<11 4 B = (B + h(C, D, A) + X12 + K2)<<15 5 A = (A + h(B, C, D) +X2 + K2)<<3 6 D = (D + h(A, B, C) + X10 + K2)<<9 7 C = (C + h(D, A, B) + X6 + K2)<<11 8 B = (B + h(C, D, A) + X14 + K2)<<15 9 A = (A + h(B, C, D) +X1 + K2)<<3 10 D = (D + h(A, B, C) + X9 + K2)<<9 11 C = (C + h(D, A, B) + X5 + K2)<<11 12 B = (B + h(C, D, A) + X13 + K2)<<15 13 A = (A + h(B, C, D) +X3 + K2)<<3 14 D = (D + h(A, B, C) + X11 + K2)<<9 15 C = (C + h(D, A, B) + X7 + K2)<<11 16 B = (B + h(C, D, A) + X15 + K2)<<15 Ch­¬ng IV Ch÷ Ký Chèng Chèi Bá IV.1. Giíi thiÖu Ch÷ ký chèng chèi bá ®­îc c«ng bè bëi Chaum vµ van Antwerpen vµo n¨m 1989. Nã cã mét sè nÐt riªng míi l¹ rÊt thó vÞ. Quan träng nhÊt trong sè ®ã lµ ch÷ ký kh«ng thÓ kiÓm tra khi kh«ng cã sù céng t¸c cña ng­êi ký, Bob. Sù b¶o vÖ nµy cña Bob ®Ò phßng kh¶ n¨ng ch÷ ký trong tµi liÖu cña anh ta bÞ sao chÐp vµ ph©n bè bëi thiÕt bÞ ®iÖn tö mµ kh«ng cã sù ®ång ý cña anh ta. VÝ dô, Bob cã mét phÇn mÒm vµ ch÷ ký kÌm theo ®­îc t¹o ra nhê thuËt to¸n cña ch÷ ký sè th«ng th­êng. Nh­ vËy, sÏ kh«ng tr¸nh khái tr­êng hîp phÇn mÒm ®ã bÞ sao chÐp mµ Bob kh«ng biÕt. Ng­êi mua sÏ kiÓm tra ch÷ ký kÌm theo phÇn mÒm nhê thuËt to¸n kiÓm tra c«ng khai Ver vµ c«ng nhËn ®ã lµ ch÷ ký ®óng. V× nh­ chóng ta ®· biÕt b¶n sao cña ch÷ ký sè lµ ®ång nhÊt víi b¶n gèc. §­¬ng nhiªn nh­ vËy Bob ®· bÞ mÊt b¶n quyÒn. §Ó tr¸nh ®iÒu bÊt lîi ®ã Bob ®· dïng ch÷ ký sè chèng chèi bá. Sù kiÓm tra sÏ thµnh c«ng khi thùc hiÖn giao thøc hái - ®¸p. L­îc ®å ch÷ ký chèng chèi bá gåm 3 phÇn: thuËt to¸n ký, giao thøc kiÓm tra, giao thøc chèi bá. IV.2. L­îc ®å ch÷ ký chèng chèi bá IV.2.1. ThuËt to¸n ký * T¹o kho¸: Cho p, q lµ c¸c sè nguyªn tè lÎ sao cho p = 2q + 1 vµ bµi to¸n rêi r¹c trªn Zp lµ khã. LÊy a Î Zp* lµ mét phÇn tö cña bËc q (NÕu a0 lµ phÇn tö nguyªn thuû cña Zp th× a = a0(p -1)/q modp). LÊy 1 £ a £ q-1 vµ x¸c ®Þnh: b = aa modp. LÊy G lµ ph©n nhãm nh©n cña Zp* bËc q (G bao gåm c¸c thÆng d­ bËc 2 theo modun p). LÊy P = A = G, x¸c ®Þnh: K = { (p, a, a, b): b = aa modp} C¸c gi¸ trÞ p, a, b lµ c«ng khai, a lµ bÝ mËt. * T¹o ch÷ ký: Víi K = (p, a, a, b) vµ x Î G, x¸c ®Þnh ch÷ ký y trªn th«ng b¸o x: y = sigk(x) = xa modp IV.2.2. Giao thøc kiÓm tra Víi x, y Î G, sù kiÓm tra ®­îc tiÕn hµnh theo giao thøc sau: 1. Alice chän e1, e2 ngÉu nhiªn, e1, e2 Î Zp*. 2. Alice tÝnh c = y b modp vµ göi nã cho Bob. 3. Bob tÝnh d = c modp vµ göi nã cho Alice. 4. Alice chÊp nhËn y lµ ch÷ ký ®óng khi vµ chØ khi: d º xamodp. * Vai trß cña p, q trong l­îc ®å: L­îc ®å n»m trong Zp; tuy nhiªn chóng ta cÇn tÝnh to¸n trong ph©n nhãm nh©n G cña Zp* cña bËc nguyªn tè lÎ. §Æc biÖt, chóng ta cÇn tÝnh phÇn tö nghÞch ®¶o theo modun ½G½, ®iÒu nµy lý gi¶i t¹i sao ½G½nªn lµ nguyªn tè lÎ. Nã thuËn tiÖn nÕu lÊy p =2q+1 víi q lµ nguyªn tè lÎ. Trong tr­êng hîp nµy, ph©n nhãm G lµ tån t¹i. *Chøng minh b­íc 4 cña giao thøc kiÓm tra: ë ®©y, chóng ta chøng minh r»ng Alice sÏ chÊp nhËn ch÷ ký ®óng. Trong c¸c phÐp to¸n d­íi ®©y, tÊt c¶ sè mò lµ biÕn ®æi theo modun q. Ta cã: d º c modp Mµ c = y b modp Þ d º ybmodp (1) Ta l¹i cã: b º aamodp Þ b º a modp (2) T­¬ng tù ta còng cã: y = xa modp Þ y = x modp (3) Thay (2), (3) vµo (1) ®­îc: d º xamodp. _ §ã lµ ®iÒu ph¶i chøng minh. VÝ dô: Gi¶ sö chóng ta lÊy p = 467. Tõ 2 lµ c¨n nguyªn thuû => 22 = 4 lµ thÆng d­ bËc 2 theo modun 467 vµ 4 lµ phÇn tö sinh cña G. LÊy a = 4. Gi¶ sö a = 101, ta cã: b = aamodp = 4101 mod467 = 449 Bob sÏ ký th«ng b¸o x = 119 víi ch÷ ký: y = xa modp = 119101 mod467 = 129 Gi¶ sö Alice muèn kiÓm tra ch÷ ký y. Alice chän ngÉu nhiªn e1 = 38, e2 = 397. Ta cã: c = y b modp = 12938 449397 mod467 = 13 Alice göi c =13 cho Bob vµ Bob sÏ tÝnh d theo: d = c modp Þ d = 13101 mod233 mod467 (q = (p - 1)/2 = (467 –1 )/2 = 233) Þ d = 9 Alice kiÓm tra ch÷ ký y theo b­íc 4. Cã: xamodp = 11938 4397 mod467 = 9 Þ d º xamodp . Do ®ã, Alice chÊp nhËn ch÷ ký lµ ®óng. IV.2.3. Giao thøc chèi bá Mét vÊn ®Ò ®Æt ra, nÕu sù céng t¸c cña Bob lµ cÇn thiÕt trong viÖc kiÓm tra ch÷ ký th× ®iÒu g× ®· ng¨n c¶n Bob tõ chèi ch÷ ký do chÝnh anh ta t¹o ra trong thêi gian gÇn ®©y? TÊt nhiªn, Bob cã thÓ cho r»ng ch÷ ký ®óng ®ã lµ gi¶ m¹o vµ tõ chèi kiÓm tra nã hoÆc Bob thùc hiÖn mét giao thøc mµ theo ®ã ch÷ ký sÏ kh«ng ®­îc kiÓm tra. V× vËy, mét l­îc ®å ch÷ ký chèng chèi bá ®­îc kÕt hîp chÆt chÏ víi mét giao thøc chèi bá vµ nhê ®iÒu ®ã Bob cã thÓ chøng minh ®­îc r»ng ch÷ ký ®ã lµ gi¶ m¹o. (NÕu anh ta tõ chèi thùc hiÖn mét phÇn trong giao thøc chèi bá, ®iÒu ®ã ®ång nghÜa víi dÊu hiÖu chøng minh ch÷ ký ®ã lµ x¸c thùc trªn thùc tÕ vµ anh ta ®ang cè g¾ng tõ chèi ch÷ ký cña m×nh). Giao thøc chèi bá gåm 2 tiÕn tr×nh cña giao thøc kiÓm tra vµ cã c¸c b­íc sau: Alice chän e1, e2 ngÉu nhiªn, e1, e2 Î Zq*. 2. Alice tÝnh c = y b modp vµ göi nã cho Bob. 3. Bob tÝnh d = c modp vµ göi nã cho Alice. 4. Alice kiÓm tra d ¹ xamodp. 5.Alice chän f1, f2 ngÉu nhiªn, f1, f2 Î Zq*. 6. Alice tÝnh C = yb modp vµ göi nã cho Bob. 7. Bob tÝnh D = c modp vµ göi nã cho Alice. 8. Alice kiÓm tra D ¹ xamodp 9. Alice kÕt luËn r»ng y lµ ch÷ ký gi¶ m¹o khi vµ chØ khi (da) º (Da) modp C¸c b­íc 1 – 4 vµ 5 – 8 lµ 2 tiÕn tr×nh kh«ng thµnh c«ng cña giao thøc kiÓm tra. B­íc 9 lµ b­íc “kiÓm tra tÝnh chÝnh x¸c” cho phÐp Alice x¸c ®Þnh râ ch÷ ký ®ã cã x¸c thùc hay kh«ng nÕu sù tr¶ lêi cña Bob ®­îc t¹o ra nh­ giao thøc theo lý thuyÕt. VÝ dô: Ta lÊy t­¬ng tù nh­ vÝ dô tr­íc. LÊy p =467, a = 4, a = 101, b = 449. Ký th«ng b¸o x =286 víi ch÷ ký y = 83 (lµ gi¶ m¹o). Bob muèn thuyÕt phôc Alice r»ng ch÷ ký ®ã lµ kh«ng ®óng. VËy ph¶i thùc hiÖn nh­ sau: Alice chän ngÉu nhiªn e1 = 45, e2 = 237. Alice tÝnh c = 305 vµ Bob tr¶ lêi víi d = 109. Alice tÝnh: 28645. 4237mod467 = 149. V× 149 ¹ 109 nªn Alice thùc hiÖn tiÕp giao thøc chèi bá. Alice chän tiÕp f1 = 125, f2 = 9, ngÉu nhiªn, Alice tÝnh C = 270 vµ Bob tr¶ lêi víi D = 68. Alice tÝnh: 286125.49mod467 = 25. V× 25 ¹ 68 nªn Alice thùc hiÖn b­íc cuèi cïng cña giao thøc tøc lµ thùc hiÖn kiÓm tra tÝnh chÝnh x¸c. Ta cã: (109.4-237)125 º 188 mod467 vµ (68.4-9)45 º 188 mod467 Þ(da) º (Da) modp VËy Alice tin ch¾c r»ng ch÷ ký ®ã lµ kh«ng ®óng. Š B©y giê, chóng ta cÇn ph¶i chøng minh 2 ®iÒu lµ: Bob cã thÓ thuyÕt phôc Alice r»ng ch÷ ký kh«ng ®óng ®ã lµ gi¶ m¹o. b. Bob kh«ng thÓ lµm cho Alice bÞ thuyÕt phôc r»ng ch÷ ký ®óng ®ã lµ gi¶ m¹o ngo¹i trõ x¸c suÊt rÊt nhá. IV. 3. C¸c ®Þnh lý IV.3.1 §Þnh lý 1: NÕu y ¹ xa modp, Alice sÏ chÊp nhËn y nh­ lµ mét ch÷ ký ®óng cña x víi x¸c suÊt . Chøng minh: Tr­íc tiªn, ta nhËn xÐt r»ng mçi yªu cÇu c cã thÓ x¶y ra sÏ t­¬ng øng chÝnh x¸c víi mét cÆp (e1, e2) bËc q. (Bëi v× y vµ b ®Òu lµ phÇn tö cña nhãm nh©n G cã bËc nguyªn tè lÎ q). Khi Bob nhËn yªu cÇu c anh ta kh«ng biÕt Alice ®· dïng cÆp (e1, e2) nµo ®Ó x©y dùng c. Chóng ta cÇn ph¶i chøng minh r»ng, nÕu y ¹ xamodp th× c¸c c©u tr¶ lêi cña Bob d Î G cã thÓ ®óng víi duy nhÊt mét cÆp (e1, e2) trong c¸c cÆp (e1, e2) bËc q. Tõ phÇn tö sinh a cña nhãm G, chóng ta cã thÓ viÕt ®­îc mét sè phÇn tö cña G nh­ lµ mét kh¶ n¨ng cña a víi sè mò x¸c ®Þnh duy nhÊt theo modun q. Nh­ vËy, ta cã thÓ viÕt: c = ai, d = aj, x = ak, y = al víi i, j, k, l Î Zp vµ tÊt c¶ tÝnh theo modun p. Ta xÐt 2 ®ång d­ sau: c º yebe modp (1) d º xeaemodp (2) Û ai º al .e.bemodp víi b = aamodp Þ ai º al .e. aa.emodp Û ai º al .e + a .emodp Þ i º l.e1 + a.e2 modq (3) (2) Þ aj º ak .e. aemodp Û aj º ak .e + emodp Þ j º k.e1 + e2 modq (4) Tõ (3) vµ (4) ta cã hÖ: i º l.e1 + a.e2 modq j º k.e1 + e2 modq XÐt D = ½lk a1½ = l – a.k (5) MÆt kh¸c: y ¹ xa modp (gt) Û al ¹ ak .amodp Þ l ¹ a.k modq (6) Tõ (5) vµ (6) Þ D ¹ 0 V× hÖ sè ma trËn cña hÖ ®ång d­ theo modun q ¹ 0 nªn hÖ cã mét nghiÖm duy nhÊt nghÜa lµ ta t×m ®­îc duy nhÊt mét cÆp (e1, e2) " i, j, k, l Î Zp. Do ®ã, " d Î G lµ c©u tr¶ lêi th× tÊt c¶ c¸c c©u tr¶ lêi ®ã chØ ®óng víi mét cÆp (e1, e2) trong c¸c cÆp (e1, e2) bËc q. VËy, x¸c suÊt r»ng Bob ®­a cho Alice c©u tr¶ lêi d mµ sÏ ®­îc kiÓm tra lµ vµ ®ång nghÜa víi viÖc Alice chÊp nhËn y lµ ch÷ ký ®óng cña x víi x¸c suÊt IV.3.2. §Þnh lý 2. Khi Alice vµ Bob cïng thùc hiÖn giao thøc chèi bá. NÕu y ¹ xamodp th× (da-e)f º (Da-f)e modp. Chøng minh: Ta cã: d º camodp Mµ c º yebe modp Þ d º ye.a.be.amodp MÆt kh¸c: b º aa modp Þ d º ye.a. ae.a.a modp Do vËy: (d.a-e)f º (ye.a.ae.a.a.a-e)f modp º ye.a.f.ae.f – e.f modp º ye.a.f modp (1) T­¬ng tù nh­ trªn ta còng tÝnh ®­îc: (D.a-f)e º ye.a.f modp (2) víi D º Camodp C º yfbf modp b º aa modp Tõ (1) vµ (2) Þ(da-e)f º (Da-f)e modp. ‹ V× vËy, nÕu y lµ ch÷ ký gi¶ m¹o th× Bob cã thÓ thuyÕt phôc Alice tin ch÷ ký ®ã lµ gi¶ m¹o. IV.3.3. §Þnh lý 3. Gi¶ sö y º xamodp, Alice thùc hiÖn giao thøc chèi bá. NÕu d ¹ xeaemodp, D ¹ xfafmodp th× kh¶ n¨ng (da-e)f ¹ (Da-f)e modp cã x¸c suÊt lµ 1 – . Chøng minh: ë ®©y, ta xÐt tr­êng hîp r»ng Bob cã thÓ thö tõ chèi ch÷ ký ®óng cña anh ta. Trong tr­êng hîp nµy, chóng ta kh«ng thÓ gi¶ ®Þnh Bob lµm theo giao thøc nghÜa lµ Bob cã thÓ kh«ng x©y dùng d vµ D nh­ lý thuyÕt bëi giao thøc, chóng ta chØ gi¶ ®Þnh Bob t¹o ra 2 gi¸ trÞ d vµ D tho¶ m·n ®iÒu kiÖn trong b­íc 4, b­íc 8 vµ b­íc 9 cña giao thøc chèi bá. Gi¶ thiÕt chóng ta cã: y º xamodp d ¹ xeaemodp D ¹ xfafmodp (da-e)f º (Da-f)e modp Tõ (da-e)f º (Da-f)e modp cã: (da-e)f.e º D.a-f modp (da-e)f.e .af º D modp Û D º (dea-e.e)f. af modp §Æt d0 = dea-e.emodp _ d0 chØ phô thuéc vµo b­íc 1 – 4 cña giao thøc. Þ D º d0f.af modp Tõ d0 = dea-e.emodp Þ d0e = da-e.modp Þ d = d0e.aemodp ¸p dông ®Þnh lý 1, chóng ta kÕt luËn y lµ ch÷ ký ®óng cña d0 víi x¸c suÊt 1 –. Nh­ng chóng ta ®ang gi¶ ®Þnh y lµ ch÷ ký ®óng cña x. Do ®ã, víi x¸c suÊt cao chóng ta cã: xa º d0a modp Þ x = d0 (1) MÆt kh¸c: d ¹ xeaemodp (gt) d.a-e ¹ xemodp (d.a-e)e ¹ xmodp x ¹ d e .a-e. e modp mµ d0 = d e a-e. e modp (theo trªn) Þ x ¹ d0 (2) Ta thÊy (1) vµ (2) m©u thuÉn . V× vËy, ®Ó (da-e)f ¹ (Da-f)e modp víi d ¹ xeaemodp vµ D ¹ xfafmodp th× x¸c suÊt x¶y ra lµ rÊt cao 1 – . NghÜa lµ, Bob chØ cã thÓ lõa Alice trong tr­êng hîp nµy víi x¸c suÊt rÊt nhá lµ. IV.4. VÊn ®Ò cÇn gi¶i quyÕt Ba ®Þnh lý trong phÇn nµy ®Òu míi chØ ®Ò cËp tíi mét khÝa c¹nh lµ Bob chÊp nhËn hay chèi bá ch÷ ký cña m×nh mµ ch­a nãi tíi mét khÝa c¹nh kh¸c lµ Alice cã thÓ chèi bá viÖc m×nh ®· ®äc th«ng b¸o do Bob göi. Ta gi¶ ®Þnh r»ng, nÕu Bob göi cho Alice mét th«ng b¸o ®ßi nî nh­ng Alice ch­a muèn tr¶ hoÆc kh«ng muèn tr¶ th× c« ta sÏ lê ®i vµ coi nh­ ch­a nhËn hay ch­a ®äc th«ng b¸o ®ã. VËy Bob cã thÓ lµm c¸ch nµo ®Ó chøng minh Alice ®· më th«ng b¸o? §Ó gi¶i quyÕt vÊn ®Ò trªn Bob vµ Alice thùc hiÖn theo giao thøc sau: Tr­íc tiªn, Bob vµ Alice cïng x©y dùng kho¸ K theo l­îc ®å trao ®æi kho¸ Diffie – Hellman. Giao thøc nh­ sau: Gi¶ sö p lµ sè nguyªn tè, a lµ c¨n nguyªn thuû cña Zp*; a, p lµ c«ng khai. Cuéc trao ®æi kho¸ gi÷a Bob vµ Alice theo c¸c b­íc sau: Bob chän ngÉu nhiªn aB: 0 £ aB £ p – 2 Bob tÝnh aamodp vµ göi nã cho Alice Bob chän ngÉu nhiªn aA: 0 £ aA £ p – 2 Bob tÝnh aamodp vµ göi nã cho Bob Bob tÝnh K = (aa )a modp Alice tÝnh K = (aa )a modp Sau ®ã, Bob tiÕp tôc x©y dùng mét kho¸ K1, K1 bÝ mËt. Bob cã thÓ x©y dùng K1 theo hÖ mËt ®èi xøng(DES , AES - ®ã lµ hÖ mét kho¸. C¸c kho¸ lËp vµ gi¶i m· lµ nh­ nhau hay dÔ dµng x¸c ®Þnh lÉn nhau. C¸c hÖ mét kho¸ cung cÊp mét c¸ch tuyÖt vêi cho viÖc m· ho¸ c¸c tÖp riªng cña ng­êi dïng). Bob vµ Alice tiÕn hµnh tiÕp theo c¸c b­íc d­íi ®©y: Bob dïng K1 ®Ó m· ho¸ th«ng b¸o x vµ ch÷ ký kÌm theo: y = sigB(x) i = eK(x, y) Bob göi i cho Alice Alice göi l¹i th«ng b¸o x1 kÌm ch÷ ký y1 = sigA(x1) vµ m· y1 b»ng K: j = eK(y1) råi göi cho Bob. Trong ®ã x1 chøa ngµy, giê, lêi yªu cÇu vµ chøa c¶ i. Bob tÝnh i1 = eK(K1) vµ göi nã cho Alice. Khi Bob vµ Alice tiÕn hµnh theo giao thøc trªn, muèn ®äc ®­îc th«ng b¸o th× Alice ph¶i göi l¹i mét th«ng b¸o (®· ®­îc m· ho¸ b»ng kho¸ K) tíi Bob, yªu cÇu Bob göi kho¸ K1 cho m×nh bëi v× K1 chØ m×nh Bob biÕt. Bob kiÓm tra th«ng b¸o cña Alice theo thuËt to¸n kiÓm tra c«ng khai Ver ®Ó x¸c ®Þnh th«ng b¸o cã ®óng cña Alice göi hay kh«ng? NÕu ®óng, anh ta göi kho¸ K1 cho Alice mµ K1 ®· ®­îc m· ho¸ theo K. Bob thùc hiÖn theo c¸ch trªn sÏ cã ®ñ chøng cø ®Ó chøng minh tr­íc toµ r»ng Alice cã më vµ ®äc th«ng b¸o anh ta göi tíi b»ng c¸ch ®­a th«ng b¸o cã kÌm theo ch÷ ký cña Alice vµ c¶ ngµy giê Bob nhËn ®­îc th«ng b¸o ®ã. Ch­¬ng V Ch÷ ký ng­êi x¸c nhËn ®­îc chØ ®Þnh V.1. Giíi thiÖu PhÐp chøng minh tri thøc kh«ng lµ phÐp chøng minh dïng ®Ó thuyÕt phôc bªn nhËn tin nh÷ng ®iÒu ng­êi chøng minh ®­a ra lµ ®óng ®¾n nh­ng kh«ng cho phÐp bªn nhËn thuyÕt phôc ng­êi kh¸c. §©y lµ phÐp chøng minh rÊt thó vÞ trong c¸c hÖ thèng chøng minh t­¬ng t¸c. HÖ thèng chøng minh nµy chØ cã 2 ng­êi tham gia, gi¶ sö lµ Peggy vµ Vic. Peggy lµ ng­êi chøng minh vµ Vic lµ ng­êi kiÓm tra. Peggy biÕt mét vµi ®iÒu trong thùc tÕ vµ c« Êy muèn chøng minh víi Vic r»ng c« Êy ®óng. Ban ®Çu c¶ Peggy vµ Vic ®Òu cã ®Çu vµo x. Peggy thuyÕt phôc Vic r»ng x cã mét vµi ®Æc tÝnh ®Þnh râ nh­ng cuèi giao thøc Vic vÉn kh«ng biÕt c¸ch chøng minh x cã ®Æc tÝnh nµy nh­ thÕ nµo. Ng­îc l¹i, ch÷ ký sè tù x¸c thùc (vÝ dô ch÷ ký RSA, Elgamal…) lµ cùc ®èi lËp víi phÐp chøng minh tri thøc kh«ng. Ch÷ ký sè thùc x¸c thùc kh«ng chØ cho phÐp bªn nhËn thuyÕt phôc ng­êi kh¸c mét c¸ch ®¬n gi¶n b»ng c¸ch cung cÊp mét b¶n copy cña ch÷ ký mµ cßn cho phÐp ng­êi bÊt kú ®· bÞ thuyÕt phôc ®i thuyÕt phôc ng­êi kh¸c. §iÒu nµy cã nghÜa lµ bÊt kú ng­êi nµo còng cã kh¶ n¨ng kiÓm tra ch÷ ký. Ch÷ ký chèng chèi bá cã mét vÞ trÝ ®Æc biÖt, nã ë mét n¬i gi÷a c¸c cùc nµy, b¶o vÖ c¶ nh÷ng lîi Ých riªng cña ng­êi ký trong viÖc b¶o ®¶m r»ng c¸c ch÷ ký kh«ng bÞ bªn nhËn dïng sai môc ®Ých còng nh­ c¸c viÖc lµm cña bªn nhËn ®Ó thuyÕt phôc ng­êi kh¸c sau nµy. Bªn nhËn ch÷ ký chèng chèi bá bÞ thuyÕt phôc r»ng tÊt c¶ nh­ng ng­ßi nµo gi÷ nã ®Òu cã thÓ th¸ch thøc ng­êi ký nã vµ r»ng ng­ßi ký kh«ng thÓ tr¶ lêi sai. Bëi v× ng­êi ký lu«n lu«n cã thÓ thuyÕt phôc mét ng­êi bÊt kú nµo ®ã r»ng mét ch÷ ký tin cËy lµ tin cËy vµ ch÷ ký kh«ng tin cËy lµ kh«ng tin cËy. Nh­ vËy ng­êi nhËn Ýt nhÊt yªn t©m r»ng ng­êi ký kh«ng thÓ tõ chèi mét ch÷ ký tin cËy. C¸c ch÷ ký chèng chèi bá cã nhiÒu øng dông nh­ trong cuéc b¸n ®Êu gi¸ mµ sù tr¶ gi¸ ®­îc gi÷ bÝ mËt, b¶o vÖ sù sao chÐp phÇn mÒm… §èi víi bªn nhËn, c¸c ch÷ ký chèng chèi bá cã ­u thÕ h¬n so v¬i tri thøc kh«ng ë chç bªn nhËn n¾m gi÷ ®iÒu g× ®ã mµ sau nµy, trong nh÷ng hoµn c¶nh nhÊt ®Þnh, cã thÓ ®­îc sö dông ®Ó thuyÕt phôc ng­êi kh¸c. VÝ dô, Bob ký mét th«ng b¸o cho phÐp Alice rót $1000 tõ tµi kho¶n cña Bob b»ng ch÷ ký chèng chèi bá. Alice muèn rót ®­îc tiÒn th× ph¶i chøng minh ch÷ ký trªn th«ng b¸o ®óng lµ cña Bob. Nh­ng trong nhiÒu øng dông thùc tÕ sù b¶o vÖ nµy lµ qu¸ yÕu. Nã dùa trªn ng­êi ký céng t¸c trong viÖc tiÕp tôc x¸c nhËn ch÷ ký. NÕu ng­êi ký kh«ng thÓ ®¸p øng ®Çy ®ñ c¸c ®iÒu kiÖn trong giao thøc hái ®¸p hoÆc ng­êi ký tõ chèi hîp t¸c th× bªn nhËn kh«ng thÓ sö dông ch÷ ký. VÝ dô, nÕu Bob x©y dung c©u tr¶ lêi d kh«ng ®óng theo giao thøc hoÆc Bob tõ chèi tham gia kiÓm tra ch÷ ký th× Alice kh«ng thÓ sö dông ch÷ ký ®ã ®Ó rót tiÒn. VÝ dô 1: ¤ng Gi¸m ®èc mét c«ng ty nµo ®ã göi mét th«ng b¸o, cã kÌm ch÷ ký cña «ng ta, tíi nh©n viªn trong c«ng ty trªn m¹ng m¸y tÝnh. Néi dung th«ng b¸o muèn c«ng ty thanh to¸n mét ho¸ ®¬n mua hµng, mµ thùc ra lµ ho¸ ®¬n khèng. Anh nh©n viªn ®ã thùc hiÖn theo ®óng ho¸ ®¬n. Nh­ng khi Thanh tra kiÓm tra vµ ph¸t hiÖn ho¸ ®¬n ®ã lµ gi¶, «ng Gi¸m ®èc muèn tr¾ng téi nªn «ng ta phñ nhËn ch÷ ký ®iÖn tö trªn th«ng b¸o göi cho anh nh©n viªn VÝ dô 2: ¤ng Gi¸m ®èc c«ng ty PhÇn mÒm b¸n phÇn mÒm, cã kÌm ch÷ ký ®iÖn tö cña «ng ta ®­îc t¹o theo thuËt to¸n ký cña l­îc ®å ch÷ ký chèng chèi bá, trªn m¹ng m¸y tÝnh. Kh¸ch hµng muèn kiÓm tra ®é tin cËy cña ch÷ ký trªn phÇn mÒm th× cÇn ph¶i cã sù céng t¸c cña ng­êi ký. §iÒu nµy kh«ng thÓ thùc hiÖn th­êng xuyªn ®èi víi mét «ng Gi¸m ®èc. VËy ph¶i gi¶i quyÕt vÊn ®Ò nµy nh­ thÕ nµo? C¬ së giao thøc ng­êi x¸c nhËn ®­îc chØ ®Þnh gi¶i quyÕt ®iÓm yÕu nµy cña ch÷ ký chèng chèi bá. Nã l«i cuèn 3 phÝa cïng tham gia: ®ã lµ bªn nhËn ch÷ ký, ng­êi ký vµ ng­êi x¸c nhËn. Bªn nhËn ch÷ ký ®Æt tªn lµ Rita, lµ phÝa kh«ng cÇn khãa c«ng khai. Ng­êi ký ®Æt tªn lµ Simon, vµ ng­êi x¸c nhËn, ®Æt tªn lµ Colin, mçi ng­êi cã khãa c«ng khai ®­îc phÐp chÊp nhËn bëi Rita. Giao thøc ký chØ gåmt­¬ng t¸c gi÷a Simon vµ Rita. Nã lµm cho Rita bÞ thuyÕt phôc r»ng Simon ®· ®­a cho c« Êy mét ch÷ ký ng­êi x¸c nhËn ®­îc chØ ®Þnh, ®èi víi th«ng b¸o ®­îc tháa thuËn, sö dông khãa riªng cña Simon vµ khãa c«ng khai cña colin. Do ®ã Rita bÞ thuyÕt phôc r»ng ch÷ ký cña Simon trªn th«ng b¸o nµy cã thÓ ®­îc x¸c nhËn bëi Colin. Giao thøc x¸c nhËn bÊt kú sau ®ã bëi Colin, phô thuéc vµo viÖc anh ta tiÕt lé nhiÒu nh­ thÕ nµo cã thÓ lµ tri thøc kh«ng, ng­êi x¸c nhËn ®­îc chØ ®Þnh hoÆc tù x¸c thùc. V.2. HÖ thèng c¬ së Ta x©y dùng mét vÞ trÝ ®¬n gi¶n cho giao thøc ng­êi x¸c nhËn ®­îc chØ ®Þnh c¬ së nh­ sau: Simon ®­a cho Rita ch÷ ký sè tù x¸c thùc trªn th«ng b¸o tháa thuËn ®­îc ký bëi khãa riªng cña anh ta – trõ viÖc ch÷ ký lµ kh«ng ®Çy ®ñ theo nghÜa nã tïy thuéc vµo sù tin cËy cña ch÷ ký chèng chèi bá bÊt kú. Ch÷ ký chèng chèi bá nµy ®­îc t¹o bëi Simon nh­ thÓ nã ®­îc ký bëi Colin vµ nã t­¬ng øng mét c¸ch tin cËy víi khãa c«ng khai cña Colin. ( Simon cã kh¶ n¨ng t¹o ch÷ ký nh­ thÕ cña Colin nh­ng chØ trªn c¸c th«ng b¸o ngÉu nhiªn bëi v× sau khi anh ta chän ch÷ ký, anh ta ®­îc tù do ®Ó chän gi¸ trÞ bÊt kú cho th«ng b¸o ®· ®­îc ký). Simon sau ®ã chøng minh víi Rita r»ng ch÷ ký chèng chèi bá ®ã lµ tin cËy. Rita kh«ng thÓ chøng minh ®iÒu g× vÒ b¶n sao sù hîp t¸c cña c« Êy víi Simon, trõ khi c« Êy nhËn ®­îc sù gióp ®ì. Nh­ng Colin víi khãa riªng cña m×nh lu«n lu«n cã thÓ gióp Rita b»ng c¸ch chøng minh víi ng­êi bÊt kú r»ng ch÷ ký chèng chèi bá mµ Simon lµ tin cËy, do ®ã thuyÕt phôc hä vÒ sù tin cËy cña ch÷ ký gèc kh«ng ®Çy ®ñ cña Simon. V× vËy, Colin cã thÓ chøng minh ®iÒu ®ã b»ng nhiÒu c¸ch kh¸c nhau. Sù khÐo lÐo cña tiÕp cËn cÊu tróc ë trªn lµ c¸ch ®Ó t¹o ch÷ ký tù x¸c thùc tïy thuéc vµo ch÷ ký chèng chèi bá. §iÒu nµy cã hai khÝa c¹nh. Mét mÆt, nÕu ch÷ ký chèng chèi bá lµ kh«ng tin cËy vµ cã thÓ ®­îc chän tù do th× ch÷ ký tù x¸c thùc sÏ kh«ng cã gi¸ trÞ theo nghÜa lµ bÊt kú ng­êi nµo còng cã thÓ dÔ dµng t¹o ra nã. MÆt kh¸c, nÕu ch÷ chèng chèi bá lµ tin cËy vµ ai ®ã bÞ thuyÕt phôc vÒ sù tin cËy cña nã th× hä sÏ bÞ thuyÕt phôc vÒ sù tin cËy cña ch÷ ký tù x¸c thùc. C¸c tÝnh chÊt nµy cã thÓ ®­îc hoµn thµnh víi c¸c l­îc ®å ch÷ ký x¸c thùc dùa trªn hµm mét chiÒu. Mét d¹ng ®iÓn h×nh cña ch÷ ký lµ n¬i ®Çu ra cña hµm mét chiÒu ®­îc dïng ®Ó x¸c ®Þnh c¸i sÏ lµ th¸ch thøc cña chøng minh tri thøc kh«ng. L­îc ®å ch÷ ký nh­ thÕ ®­îc söa ®æi sao cho viÖc x¸c ®Þnh hµm mét chiÒu bao gåm ch÷ ký chèng chèi bá theo c¸ch thÝch hîp. Ch¼ng h¹n, ®Çu ra cña hµm mét chiÒu míi cã thÓ ®­îc x¸c ®Þnh nh­ ®Çu ra cña hµm gèc ®­îc XOR víi ch÷ ký chèng chèi bá. Nh­ vËy sù tù do hoµn toµn trong lùa chän c¸i g× lµ ch÷ ký chèng chèi bá cho phÐp sù tù do hoµn toµn trong viÖc chän ®Çu ra cña hµm mét chiÒu míi, nh­ng sù lùa chän cã giíi h¹n cña ch÷ ký chèng chèi bá cã nghÜa lµ nh÷ng rµng buéc trªn ®Çu ra cña hµm mét chiÒu míi. V.3. Giao thøc ký Giao thøc nµy nh»m ®Ó cho Simon ký th«ng b¸o vµ thuyÕt phôc Rita r»ng ch÷ ký lµ tin cËy. §Ó ®¬n gi¶n, Simon sÏ sö dôngl­îc ®å ch÷ ký RSA víi m«dun kho¸ c«ng khai n vµ sè mò 3. Kho¸ c«ng khai cña Colin sÏ lµ h = gz, trong ®ã z lµ kho¸ riªng cña Colin, g lµ c¨n nguyªn thuû (cã bËc cao nhÊt) cña n. Kho¸ c«ng khai nµy vµ tÊt c¶ nh÷ng tÝnh to¸n trong giao thøc lµ trong nhãm bËc nguyªn tè mµ ë ®ã bµi to¸n logarit rêi r¹c ®­îc gi¶ thiÕt lµ khã. V.3.1. T¹o kho¸ Simon chän n = p.q víi p, q lµ c¸c sè nguyªn tè lín kh¸c nhau, f(n) = (p - 1)(q - 1). Cho P = A = Zn vµ x¸c ®Þnh: K = {(n, p, q, 3-1, 3): n = p.q; p, q nguyªn tè: 3-1.3 º 1 mod f(n)} C¸c gi¸ trÞ n, 3 c«ng khai; c¸c gi¸ trÞ p, q, 3-1 bÝ mËt. V.3.2. T¹o ch÷ ký Simon tiÕn hµnh ký th«ng b¸o m nh­ sau: Simon chän x ngÉu nhiªn vµ tÝnh: a = gx b = hx Víi K = (n, p, q, 3-1, 3) Simon tÝnh ch÷ ký RSA trªn H(a, b) Å F(m) a = (H(a, b) Å F(m)) modn Trong ®ã H(a, b) lµ hµm tæ hîp ®Ó khö cÊu tróc nh©n nh­ng l¹i dÔ dµng tÝnh ng­îc; F lµ hµm Hash thÝch hîp. Sau ®ã Simon göi a, b , a cho Rita. ë giao thøc nµy, Simon ®· t¹o ra ®­îc mét ch÷ ký chèng chèi bá nh­ thÓ nã ®­îc ký bëi Colin. Ta dÔ dµng chøng minh ®­îc ®iÒu nµy. Ta cã: a = gx b = hx mµ h = gz Þ b = (gz)x = (gx)z = az MÆt kh¸c: z lµ kho¸ riªng cña Colin Do ®ã: b = (gx)z lµ ch÷ ký chèng chèi bá cña Colin, víi g lµ c¨n nguyªn thuû cã bËc cao nhÊt cña n vµ z lµ kho¸ bÝ mËt. V.3.3. Giao thøc kiÓm tra ë ®©y ta gi¶ thiÕt ng­êi ký tham gia vµo giao thøc kiÓm tra, ch­a cÇn sù cã mÆt cña ng­êi x¸c nhËn. Giao thøc kiÓm tra diÔn ra víi sù céng t¸c cña Simon (ng­êi ký) vµ Rita (ng­êi nhËn). Giao thøc tiÕn hµnh nh­ sau: Rita chän s, t ngÉu nhiªn vµ tÝnh c = gsht , råi göi c cho Simon. Simon chän ngÉu nhiªn vµ tÝnh: d = g; e = (c.d)x Simon göi d, e cho Rita. Rita göi s, t cho Simon Simon kiÓm tra nÕu gsht = c th× simon göi cho Rita Rita kiÓm tra nÕu d = g, e.a = asbt, H(a, b) Å F(m) = a3 modn th× ch÷ ký lµ tin cËy. Ng­îc l¹i, ch÷ ký lµ kh«ng tin cËy. Trong b­íc 5, Rita kiÓm tra ®¼ng thøc e.a = asbt tøc lµ kiÓm tra b = az. ThËt vËy: Tõ asbt = e.a Þ bt = e.a.a-s (1) mµ e = (c.d)x c = gsht d = g Þ e = (gs.ht.g )x = gs.x.ht.x.g.x = (gx)s.ht.x.(gx) = as.htx.a (2) Tõ (1) vµ (2) Þ bt = as.htx.a . a.a-s = ht.x Þ b = hx = (gz)x = (gx)z = az.  §iÒu nµy thuyÕt phôc Rita r»ng ch÷ ký nµy do Simon t¹o ra vµ cã thÓ ®­îc kiÓm tra bëi Colin. Nh­ng Rita kh«ng thÓ dïng kÕt qu¶ nµy ®Ó chøng minh nã víi nh÷ng ng­êi kh¸c. V.4. Giao thøc x¸c nhËn Giao thøc nµy ®Ó cho ng­êi kiÓm tra bÞ thuyÕt phôc r»ng ch÷ ký lµ phï hîp nh­ng còng kh«ng cho phÐp ng­êi kiÓm tra ®i thuyÕt phôc ng­êi kh¸c. Giao thøc nh­ sau: Ng­êi kiÓm tra Veronica chän u, v ngÉu nhiªn vµ tÝnh: k = gu.av. Råi göi k cho Colin. Colin chän ngÉu nhiªn vµ tÝnh: l = g, n = (k.l)z Sau ®ã göi l, n cho ng­êi kiÓm tra Veronica. Ng­êi kiÓm tra göi u, v cho Colin Colin kiÓm tra nÕu gu.av = k th× Colin göi cho ng­êi kiÓm tra Veronica. Ng­êi kiÓm tra Veronica sÏ kiÓm tra nÕu g = l vµ n.h = hu.bv th× ch÷ ký lµ tin cËy. Ng­îc l¹i, ch÷ ký lµ kh«ng tin cËy. ë b­íc 5, ng­êi kiÓm tra Veronica kiÓm tra ®¼ng thøc n.h = hu.bv còng chÝnh lµ kiÓm tra b = az. Ta cã: n.h = hu.bv Þ bv = n. h. h-u (1) MÆt kh¸c: n = (k.l)z k = gu.av l = g Þ n = (gu.av.g)z (2) Tõ (1) vµ (2) Þ bv = (gu.av.g)z. h. h-u = guz.avz.g.g-uz.g Þ bv = av.z Þ b = az.  V.5. Giao thøc chuyÓn ®æi. §©y lµ mét giao thøc x¸c nhËn kh¸c cña Colin, giao thøc nµy lµ c¸ch ®Ó Colin chuyÓn ch÷ ký ng­êi x¸c nhËn ®­îc chØ ®Þnh thµnh ch÷ ký sè tù x¸c thùc. Ë ®©y Colin lËp nªn mét chøng minh kh«ng t­¬ng t¸c r»ng mét ng­êi nµo ®ã biÕt c¸ch biÓu diÔn b nh­ luü thõa cña a. ý t­ëng c¬ b¶n cña sù chuyÓn ®æi nµy lµ ph¶i biÕt c¸ch biÓu diÔn b nh­ luü thõa cña a ®Ó thµnh lËp cÆp (r, y) sao cho ay = r.bF(a, r), trong ®ã F lµ hµm mét chiÒu thÝch hîp. Ta thÊy r»ng kho¸ c«ng khai h cña Colin kh«ng xuÊt hiÖn ë ®©y, h chØ xuÊt hiÖn trong giao thøc ký. Do vËy, sau khi Colin thùc hiÖn giao thøc chuyÓn ®æi th× bÊt kú ng­êi nµo còng cã thÓ kiÓm tra ch÷ ký mµ kh«ng cÇn sù cã mÆt cña ng­êi ký hay ng­êi x¸c nhËn. Giao thøc tiÕn hµnh nh­ sau: Colin chän w ngÉu nhiªn vµ tÝnh: r = aw y = w + z.F(a, r) Sau ®ã göi r, y cho ng­êi kiÓm tra Veronica. Ng­êi kiÓm tra Veronica kiÓm tra nÕu ay = r. bF(a, r) th× ch÷ ký lµ tin cËy. Ng­îc l¹i, ch÷ ký lµ kh«ng tin cËy. Chøng minh: ay = r. bF(a, r) th× ch÷ ký lµ tin cËy. Ta cã: ay = r. bF(a, r) Û aw + z.F(a, r) = aw.bF(a, r) Û aw.az.F(a, r) = aw.bF(a, r) Þ az.F(a, r) = bF(a, r) Þ az = b hay b = az Þ ch÷ ký lµ tin cËy. V.6. Tæng qu¸t L­îc ®å ch÷ ký c¬ së cã thÓ ®­îc tæng qu¸t ho¸ b»ng c¸ch bao gåm nhiÒu ng­êi x¸c nhËn. H¬n mét kho¸ c«ng khai cña ng­êi x¸c nhËn cã thÓ ®­îc tæ hîp trong ch÷ ký chèng chèi bá ( nh­ lÊy tÝch cña c¸c kho¸ c«ng khai), sao cho sù céng t¸c cña tÊt c¶ nh÷ng ng­êi x¸c nhËn sÏ lµ cÇn thiÕt cho sù x¸c nhËn bÊt kú. Cµng yªu cÇu nhiÒu ng­êi x¸c thùc th× cµng khã kh¨n ®Ó nhËn sù x¸c thùc, vµ theo mét nghÜa trùc quan th× l­îc ®å ch÷ ký cµng tiÕp cËn gÇn h¬n víi giao thøc tri thøc kh«ng. Vµ nÕu kho¸ cña Simon ®­îc kÕt hîp vµo th× kÕt qu¶ lµ sù tiÕt lé tèi thiÓu. Ch­¬ng VI Ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá VI.1. Giíi thiÖu ë c¸c ch­¬ng tr­íc chóng ta ®· lµm quen víi kh¸i niÖm vÒ ch÷ ký chèng chèi bá vµ ch÷ ký ng­êi x¸c nhËn. L­îc ®å ch÷ ký ng­êi x¸c nhËn ®· gi¶i quyÕt ®­îc mét sè yÕu ®iÓm cña l­îc ®å ch÷ ký chèng chèi bá. Trong l­îc ®å ch÷ ký chèng chèi bá chØ gåm 2 thµnh phÇn tham gia lµ ng­êi ký vµ ng­êi x¸c nhËn (hoÆc ng­êi kiÓm tra). Do vËy, nÕu ng­êi ký tõ chèi céng t¸c ®ång nghÜa víi viÖc ch÷ ký kh«ng ®­îc kiÓm tra. Trong l­îc ®å ch÷ ký ng­êi x¸c nhËn, kh¶ n¨ng kiÓm tra c¸c ch÷ ký lµ ng­êi ®¹i diÖn ®­îc thªm vµo thùc thÓ gäi lµ ng­êi x¸c nhËn. Sù kiÓm tra cña ng­êi x¸c nhËn chÝnh x¸c h¬n ng­êi ký, c« ta ( anh ta) cã kh¶ n¨ng x¸c nhËn hoÆc tõ chèi ®é tin cËy cña ch÷ ký nh­ng c« ta (anh ta) kh«ng cã kh¶ n¨ng gi¶ m¹o mäi ch÷ ký. Trong nhiÒu l­îc ®å ch÷ ký ng­êi x¸c nhËn, ng­êi ký kh«ng thÓ x¸c nhËn ch÷ ký cña m×nh lµ tin cËy. NÕu ng­êi x¸c nhËn tõ chèi céng t¸c dÉn ®Õn ch÷ ký kh«ng thÓ kiÓm tra. Trong thùc tÕ, sù tin cËy cña ng­êi tham gia gi÷ vai trß rÊt quan träng, v× vËy gi¶m t×nh tr¹ng r¾c rèi cña bÊt kú ng­êi tham gia nµo lµ mong muèn cao dùa vµo c¶ c¸c lý do kü thuËt vµ c¸c lý do tiÕt kiÖm. §iÒu nµy ®­îc thùc hiÖn nÕu ch÷ ký cã thÓ kiÓm tra víi sù céng t¸c cña ng­êi ký hoÆc céng t¸c cña ng­êi x¸c nhËn. Sau ®ã ng­êi sö dông cã thÓ tr¶ lêi ng­êi ký sù kiÓm tra ch÷ ký. Nh­ mét sù b¶o vÖ an toµn, ng­êi x¸c nhËn cßn cã thÓ kiÓm tra ch÷ ký nÕu ng­êi ký tõ chèi céng t¸c. Ch­¬ng nµy giíi thiÖu l­îc ®å ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá, ®­a ra chøc n¨ng kiÓm tra ch÷ ký cña c¶ ng­êi ký vµ ng­êi x¸c nhËn. L­îc ®å nµy lµ sù biÕn ®æi cña ch÷ ký ng­êi x¸c nhËn. L­îc ®å cung cÊp mét c¸ch linh ho¹t ®èi víi ng­êi ký vµ ng­êi sö dông còng nh­ bao hµm c¸c biÕn ®æi cña ng­êi x¸c nhËn ®­îc chØ ®Þnh – ng­êi th­êng ®­îc tin t­ëng trong thùc tÕ. Sù bæ sung vµo l­îc ®å nh»m môc ®Ých ®¸nh l¹c h­íng nghÜa lµ c¸c ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá cã thÓ sinh ra víi môc ®Ých ®¸nh lõa. C¸c ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá mï qu¸ng cã lîi Ých trong nhiÒu øng dông nh­ c¸c hÖ thèng tr¶ tiÒn tr­íc víi m¹ng lín cña c¸c dÞch vô n¬i mµ quyÒn riªng t­ cña ng­êi sö dông m¹ng nªn ®­îc b¶o vÖ trong khi kiÓm duyÖt sù mua b¸n cña c¸c dÊu hiÖu mua b¸n dµi h¹n cÇn ph¶i ®­îc ng¨n chÆn. VI. 2. M« h×nh cña ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá PhÇn nµy cung cÊp mét kiÓu ®Æc tr­ng cña c¸c ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá. Nã cung cÊp sù ®Þnh nghÜa kh«ng ®æi cho c¸c giao thøc gi¶i m· sö dông c¸c kh¸i niÖm chuÈn cña m¸y Turing t­¬ng t¸c, hÖ thèng chøng minh t­¬ng t¸c vµ tri thøc kh«ng. §Ó ®¬n gi¶n, chóng ta dïng S chØ ng­êi ký, C chØ ng­êi x¸c nhËn vµ V lµ ng­êi kiÓm tra. L­îc ®å ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá bao gåm c¸c thuËt to¸n vµ c¸c giao thøc sau: - ThuËt to¸n t¹o kho¸: t¹o 2 kho¸ GENS vµ GENC nhËn 1l lµ ®Çu vµo (1l nghÜa lµ mét d·y cã l sè 1), trong ®ã l lµ tham sè an toµn vµ lÇn l­ît lµ 2 cÆp ®Çu ra (SS, PS) vµ (SC, PC). ThuËt to¸n GENS ®­îc thùc hiÖn bëi S, GENC ®­îc thùc hiÖn bëi C. (SS, PS), (SC, PC) lÇn l­ît lµ c¸c cÆp kho¸ bÝ mËt vµ c«ng khai cña S vµ C. Kho¸ bÝ mËt S ®­îc sö dông ®Ó t¹o ra c¸c ch÷ ký. Ngoµi ra SS, SC ®­îc lÇn l­ît sö dông bëi ng­êi ng­êi ký vµ ng­êi x¸c nhËn trong c¸c giao thøc x¸c nhËn vµ giao thøc chèi bá. - ThuËt to¸n ký ®a thøc theo x¸c suÊt SIGN nhËn kho¸ bÝ mËt SS, th«ng b¸o m vµ c¸c ®Çu ra cña ch÷ ký s. - Giao thøc kiÓm tra ch÷ ký t­¬ng t¸c (CVer , VVer ). §©y lµ cÆp ®Çu vµo cña m¸y Turing thêi gian ®a thøc t­¬ng t¸c gi÷a ng­êi x¸c nhËn vµ ng­êi kiÓm tra: ( CVer (SC), VVer ())(m, s, PS, PC) ® v §Çu vµo chung gåm th«ng b¸o m, ch÷ ký s, 2 kho¸ c«ng khai PS, PC. Ng­êi x¸c nhËn cã SC lµ ®Çu vµo riªng. Sù tr¶ vÒ cña giao thøc lµ gi¸ trÞ logic v. NÕu ®Çu ra lµ 1 nghÜa lµ ch÷ ký s tin cËy trªn th«ng b¸o m, ®Çu ra lµ 0 th× ng­îc l¹i. - Giao thøc kiÓm tra ch÷ ký t­¬ng t¸c (SVer, VVer). §©y lµ cÆp ®Çu vµo cña m¸y Turing thêi gian ®a thøc t­¬ng t¸c gi÷a ng­êi ký vµ ng­êi kiÓm tra: (SVer(SS), VVer())(m, s, PS, PC) ® v §Çu vµo chung gåm th«ng b¸o m, ch÷ ký s vµ 2 kho¸ c«ng khai PS, PC. Ng­êi ký cã SS lµ ®Çu vµo riªng. Sù tr¶ vÒ cña giao thøc lµ gi¸ trÞ logic v. NÕu ®Çu ra lµ 1 nghÜa lµ ch÷ ký s tin cËy trªn th«ng b¸o m, ®Çu ra lµ 0 th× ng­îc l¹i. * C¸c yªu cÇu an toµn cña c¸c thµnh phÇn trong giao thøc: - TÝnh kh«ng thÓ ph©n biÖt ®­îc cña ch÷ ký: Ch÷ ký m« pháng SIGNsim ®­îc t¹o b»ng thuËt to¸n thêi gian ®a thøc theo x¸c suÊt, nã nhËn th«ng b¸o m, 2 kho¸ c«ng khai PS, PC lµ ®Çu vµo vµ cho ra mét phÇn tö ®­îc gäi lµ ch÷ ký m« pháng trong kh«ng gian ký. Ch÷ ký m« pháng nµy kh«ng thÓ ph©n biÖt so víi ch÷ ký thùc ®èi víi bÊt kú ng­êi nµo mµ chØ hiÓu c¸c th«ng tin c«ng khai. Dùa vµo mét th«ng b¸o vµ mét ch÷ ký cã nghÜa, mét ng­êi nµo ®ã kh«ng thÓ tù m×nh x¸c ®Þnh ®­îc ch÷ ký lµ tin cËy. - TÝnh kh«ng thÓ gi¶ m¹o cña ch÷ ký: Kh«ng tån t¹i thuËt to¸n thêi gian ®a thøc nhËn kho¸ c«ng khai PS cña ng­êi ký; kho¸ bÝ mËt SC, kho¸ c«ng khai PC cña ng­êi x¸c nhËn vµ truy cËp ®Õn ch÷ ký ng­êi tin cËy SIGN, cho ra mét cÆp th«ng b¸o- ch÷ ký (m’, s’) kh«ng ®­îc t¹o bëi SIGN víi x¸c suÊt ®¸ng kÓ. - TÝnh chÝnh x¸c cña sù kiÓm tra: Kh«ng l­u ý tíi sù dÝnh lÝu cña mét trong hai ng­êi lµ ng­êi ký hoÆc ng­êi x¸c nhËn, c¸c giao thøc kiÓm tra lµ nhÊt qu¸n. Ngo¹i trõ x¸c suÊt kh«ng ®¸ng kÓ, giao thøc kiÓm tra tr¶ vÒ 1 nh­ lµ ®Çu ra cña ng­êi kiÓm tra nÕu cÆp th«ng b¸o – ch÷ ký (m, s) tin cËy, hoÆc lµ 0 nÕu (m, s) lµ kh«ng tin cËy. VI.3. C¸c l­îc ®å ch÷ ký vµ phÐp chøng minh t­¬ng t¸c VI.3.1. Ký hiÖu + Ký hiÖu çç biÓu thÞ sù ghÐp nèi cña 2 d·y nhÞ ph©n. + LÊy p, q lµ c¸c sè nguyªn tè lín vµ xem r»ng p - 1 chia hÕt cho q + Cho g lµ phÇn tö sinh cña ph©n nhãm nh©n G cña Z bËc q. + Hµm Hash chÞu ®ùng sù va ch¹m H: {0, 1} ® Z (k =½q½, k > 160). VI.3.2. L­îc ®å ch÷ ký Schnorr §Þnh nghÜa : Cho y = gx modp, ch÷ ký Schnorr trªn th«ng b¸o m kiÓm tra sö dông kho¸ c«ng khai (g, y) lµ cÆp (u, v) Î Z ´ Z tho¶ m·n u = H(mççyççgççgvyu). Ch÷ ký nh­ vËy cã thÓ ®­îc tÝnh nÕu biÕt kho¸ bÝ mËt x b»ng c¸ch chän r Î Z (chän r ngÉu nhiªn thuéc Z ) vµ tÝnh: u = H(mççyççgççgr) vµ v = r – ux mod q. §Ó ®¬n gi¶n, ta dïng S(x, y)(m) biÓu thÞ ch÷ ký Schnorr trªn th«ng b¸o m ®· ®­îc t¹o víi kho¸ bÝ mËt x vµ cã thÓ kiÓm tra víi kho¸ c«ng khai y. VI.3.3. Ch÷ ký Chaum-Petersen dùa vµo ®¼ng thøc cña thuËt to¸n rêi r¹c §Þnh nghÜa 2: Cho y1 = g vµ y2 = g, ch÷ ký Chaum-Petersen dùa vµo ®¼ng thøc cña thuËt to¸n rêi r¹c y1 vµ y2 víi c¬ sè lµ g1, g2 trªn th«ng b¸o m lµ cÆp (u, v) Î Z ´ Z tho¶ m·n: u = H(mççy1ççy2ççg1ççg2ççgyççgy) D­íi m« h×nh Oracle ngÉu nhiªn, ch÷ ký nh­ thÕ cã thÓ ®­îc thµnh lËp nÕu biÕt kho¸ bÝ mËt x tho¶ m·n y1 = g vµ y2 = g. Ch÷ ký sau ®ã ®­îc tÝnh b»ng c¸ch chän r Î Z, tÝnh: u = H(mççy1ççy2ççg1ççg2ççgyççgy) vµ v = r – ux mod q. Ta cã thÓ viÕt l¹i u nh­ sau: Tõ v = r – ux modq Þ r = v + ux modq Theo gi¶ thiÕt: y1 = g Þ gy= g(g)u = g = g T­¬ng tù: y2 = g Þ gy= g(g)u = g = g VËy: u = H(mççy1ççy2ççg1ççg2ççgççg) §Ó ®¬n gi¶n, ta dïng CP(x, y1, y2, g1, g2)(m) biÓu thÞ ch÷ ký Chaum-Petersen trªn th«ng b¸o m ®· ®­îc t¹o ra víi kho¸ bÝ mËt x tho¶ m·n ®¼ng thøc cña thuËt to¸n rêi r¹c y1, y2 víi c¬ sè lÇn l­ît lµ g1, g2. VI.3.4. PhÐp chøng minh ký t­¬ng t¸c Fujioka-Okamoto-Ohta cña ®¼ng thøc PhÐp chøng minh ký ®¼ng thøc log(y1) º log(y2) lµ giao thøc hoÆc chøng minh log(y1) º log(y2) hoÆc chøng minh log(y1) ¹ log(y2). Giao thøc cña Fujioka-Okamoto-Ohta chøng minh ®¼ng thøc (hoÆc kh«ng lµ ®¼ng thøc) cña thuËt to¸n rêi r¹c y1, y2 víi c¬ sè lÇn l­ît lµ g1, g2. Giao thøc nh­ sau: V (ng­êi kiÓm tra) C (ng­êi x¸c nhËn) u, v Î Z a = gymodp k, k’, w Î Z r1 = g; r2 = g r = g; r= g a = gy? z = k – (v + w) c z’ = k’ – (v + w) k gy = r1 gr = r gr = r = ( g2z y º r2) Ta cã thÓ diÔn gi¶i giao thøc trªn thµnh c¸c b­íc sau: Ng­êi kiÓm tra V chän u, v ngÉu nhiªn Î Z vµ tÝnh a = gymodp, råi göi a cho ng­êi x¸c nhËn C Ng­êi x¸c nhËn C chän k, k’, w ngÉu nhiªn Î Zvµ tÝnh r1 = g; r2 = g; r = g; r= g Sau ®ã göi r1, r2, r1’, r2’ cho V Khi nhËn ®­îc r1, r2, r1’, r2’ do C göi, V göi l¹i C hai gi¸ trÞ u, v Ng­êi x¸c nhËn nhËn ®­îc u, v th× kiÓm tra ®¼ng thøc a = gymodp. NÕu ®óng, C göi cho V hai gi¸ trÞ z, z’ ®­îc tÝnh nh­ sau: z = k – (v + w) c z’ = k’ – (v + w) k Ng­êi kiÓm tra V sÏ kiÓm tra xem c¸c ®¼ng thøc sau cã x¶y ra hay kh«ng? gy = r1 gr = r gr = r = ( g2z y º r2) KÕt thóc giao thøc ®Çu ra cña ng­êi kiÓm tra lµ . PhÐp chøng minh tr¶ vÒ 1 nÕu log(y1) º log(y2), tr¶ vÒ 0 nÕu log(y1) ¹ log(y2). Giao thøc ®­îc ký hiÖu nh­ sau: Bi – Proof[log(y1) º log(y2)] Chó ý: ë ®©y y1, y2 ®­îc tÝnh nh­ sau: y1 = g1c mod p, y2 = g2c mod p VI.4. CÊu tróc l­îc ®å ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá VI.4.1. T¹o kho¸ + Ng­êi ký chän s Î Z, thiÕt lËp cÆp kho¸ bÝ mËt vµ c«ng khai (S S, PS) víi SS = s, PS = gs modp. + Ng­êi x¸c nhËn chän c Î Z, thiÕt lËp cÆp kho¸ bÝ mËt vµ c«ng khai (SC, PC ) víi SC = c, PC = gc modp. VI.4.2. T¹o ch÷ ký §Ó t¹o ch÷ ký s trªn th«ng b¸o m, ng­êi ký S chän r Î Z, t¹o: a : = gr, as : = P, as+c : = (PSPC), gs : = PS, gs+c : =PSPC Sau ®ã S tÝnh s1 = CP(r, a, as+c, g, gs+c)(m) vµ s2 = S(sr, g, as)(s1). Þ Ch÷ ký s cña ng­êi ký trªn th«ng b¸o m lµ: s = (s1, s2). VI.4.3. KiÓm tra ch÷ ký §Çu tiªn ng­êi kiÓm tra sÏ kiÓm tra ®é tin cËy cña (s1, s2) víi s1 lµ ch÷ ký Chaum-Petersen ®¼ng thøc cña thuËt to¸n rêi r¹c tin cËy trªn th«ng b¸o m vµ s2 lµ ch÷ ký Schnorr tin cËy trªn s1. Ng­êi kiÓm tra dõng nÕu mäi sù kiÓm tra ®Òu dÉn ®Õn kÕt qu¶ kh«ng tin cËy. Ng­îc l¹i, ng­êi kiÓm tra tiÕp tôc kiÓm tra ch÷ ký nh­ sau: - §èi víi ng­êi ký: §Çu ra v cña ng­êi kiÓm tra cña (SVer(SS), VVer())(m, s, PS, PC) ®­îc tÝnh: v = Bi-Proof [log(as) º logg(gs)] Trong giao thøc nµy ng­êi ký ®ãng vai trß ng­êi chøng minh. - §èi víi ng­êi x¸c nhËn: §Çu ra v cña ng­êi kiÓm tra cña (CVer(SC), VVer())(m, s, PS, PC) ®­îc tÝnh: v = Bi-Proof [logg (gc ) º log(ac)] Trong giao thøc phÐp chøng minh ký nµy, ng­êi x¸c nhËn gi÷ nhiÖm vô nh­ ng­êi chøng minh vµ ac = as+c /as. Trong c¶ 2 sù kiÓm tra cña ng­êi ký vµ ng­êi x¸c nhËn, ng­êi kiÓm tra chÊp nhËn ch÷ ký khi vµ chØ khi v =1. VI.4.4. Gi¶i thÝch cÊu tróc b»ng trùc gi¸c Ta thÊy r»ng trong cÊu tróc nµy, ng­êi ký cã kho¸ bÝ mËt s, kho¸ c«ng khai gs, ng­êi x¸c nhËn cã kho¸ bÝ mËt c, kho¸ c«ng khai gc. Gi¸ trÞ gs+c ®­îc tÝnh: gs+c =PS.PC = gsgc (v× gs = PS, gc = PC ) Ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá s gåm 2 ch÷ ký lµ s1, s2. Trong ®ã s1 lµ ch÷ ký Chaum-Petersen ®­îc t¹o ra víi kho¸ bÝ mËt r1 = r, kiÓm tra víi kho¸ c«ng khai a = gr vµ as+c = g; s2 lµ ch÷ ký Schnorr ®­îc t¹o víi kho¸ bÝ mËt r2 = rs, kiÓm tra víi kho¸ c«ng khai as = g. B»ng trùc gi¸c thÊy r»ng, ch÷ ký lµ luËn chøng cña tri thøc kho¸ bÝ mËt. Nh­ vËy nÕu mét ng­êi nµo ®ã cã thÓ t¹o ra s1, s2 th× ng­êi ®ã ph¶i cã tri thøc cña r1, r2. NÕu ng­êi ®ã cã thÓ chøng minh r»ng r2 = r1s nghÜa lµ ch÷ ký ®ã lµ tin cËy. Cã 2 c¸ch ®Ó chøng minh r2 = r1s nh­ sau: * C¸ch 1: Chøng minh r»ng: logg(gs) º log(as). C¸ch nµy yªu cÇu tri thøc cña logg (gs ), v× vËy chØ cã thÓ thùc hiÖn bëi ng­êi ký. * C¸ch 2: Chøng minh r»ng: logg(gc ) = log(as+c /as). C¸ch nµy yªu cÇu tri thøc cña logg(gc), v× vËy chØ cã thÓ ®­îc thùc hiÖn bëi ng­êi x¸c nhËn. VI.5. PhÐp ph©n tÝch an toµn §Ó chØ ra r»ng cÊu tróc lµ an toµn, chóng ta gi¶ sö r»ng l­îc ®å ch÷ ký Schnorr vµ ch÷ ký Chaum-Petersen dùa vµo ®¼ng thøc cña thuËt to¸n rêi r¹c lµ an toµn. PhÐp chøng minh ký t­¬ng t¸c Fujioka-Okamoto-Ohta cña ®¼ng thøc lµ an toµn, ®óng ®¾n vµ chøng cí kh«ng thÓ ph©n biÖt ®­îc. PhÐp chøng minh an toµn nµy cã thÓ ®­îc chøng minh trong m« h×nh Oracle ngÉu nhiªn. D­íi ®©y lµ c¸c chøng minh chØ ra r»ng cÊu tróc cña ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá lµ kh«ng thÓ gi¶ m¹o, kh«ng thÓ ph©n biÖt ®­îc vµ sù kiÓm tra ch÷ ký lµ nhÊt qu¸n. VI.5.1.Ch÷ ký kh«ng thÓ gi¶ m¹o §Þnh nghÜa. §Æc tÝnh kh«ng thÓ gi¶ m¹o ch÷ ký v÷ng ch¾c. Ngo¹i trõ víi x¸c suÊt kh«ng ®¸ng kÓ, kh«ng tån t¹i thuËt to¸n thêi gian ®a thøc theo x¸c suÊt A mµ cã thÓ sinh ra ch÷ ký s trªn th«ng b¸o ®Æc biÖt m, kiÓm tra víi kho¸ c«ng khai y khi truy cËp ®Õn ch÷ ký Oracle cña tÊt c¶ kho¸ c«ng khai y* cho tÊt c¶ c¸c th«ng b¸o cÇn truy cËp ®Õn y ®Ó ®­îc th«ng b¸o m. ë ®©y khi mäi th«ng b¸o m*, ch÷ ký Oracle cña kho¸ c«ng khai y* sinh ra ch÷ ký s* cña m* kiÓm tra víi y*. B»ng trùc gi¸c, ®Æc tÝnh kh«ng thÓ gi¶ m¹o ch÷ ký v÷ng ch¾c cã nghÜa r»ng khi truy cËp ®Õn ch÷ ký Oracle cña tÊt c¶ c¸c ch÷ ký c«ng khai tin cËy cho tÊt c¶ c¸c th«ng b¸o cÇn ch÷ ký mong muèn, nã lµ kh«ng thÓ sinh ra ch÷ ký s d­íi kho¸ c«ng khai mong muèn, trªn th«ng b¸o mong muèn m. §Þnh nghÜa nµy thuyÕt phôc h¬n kh¸i niÖm ch÷ ký an toµn chuÈn. Nã lµ b¶n sao t­¬ng ®­¬ng cña an toµn ®èi lËp víi c¸c lùa chän thÝch hîp ®Æc tÝnh tÊn c«ng v¨n b¶n mËt m· cña l­îc ®å gi¶i m·. Do ®ã l­îc ®å ch÷ ký lµ kh«ng thÓ gi¶ m¹o v÷ng ch¾c nÕu nã tho¶ m·n ®Æc tÝnh kh«ng thÓ gi¶ m¹o ch÷ ký v÷ng ch¾c. Bæ ®Ò: Ch÷ ký s = (s1, s2) lµ ch÷ ký qua ®­îc sù kiÓm tra chØ nÕu s1 = CP(r, a, as+c, g, gs+c)(m), s2 = S(sr, g, as)(s1) vµ r1 = r2. Chøng minh: NÕu s lµ tin cËy, s1 vµ s2 ®­îc thµnh lËp lµ s1 = CP(r, a, as+c, g, gs+c)(m), s2 = S(sr, g, as)(s1). Cßn l¹i chøng tá r1 = r2. Chóng ta gi¶ sö r»ng s kh¸c 0. Ch÷ ký s ®­îc coi lµ tin cËy nÕu nã tr¶i qua mét trong hai b­íc thö kiÓm tra, ®ã lµ kiÓm tra ®èi víi ng­êi x¸c thùc vµ kiÓm tra ®èi víi ng­êi ký. KiÓm tra ®èi víi ng­êi x¸c nhËn ph¶i thùc hiÖn phÐp chøng minh ký Bi – Proof [logg(gc) º log(ac)]. Do ®ã nã chØ ra r»ng ac = ac hoÆc ac = as+c/ as. H¬n n÷a s1, s2 lµ ®óng Þ tån t¹i r1 vµ sr2, xem r»ng: as+c =g = g(s+c)r , as = gsr Þ ac = g= g/ g Þ g =g V× s ¹ 0 Þ r1 = r2. Víi tr­êng hîp kiÓm tra ®èi víi ng­êi ký t­¬ng tù nh­ trªn. §Þnh lý: Trong m« h×nh Oracle ngÉu nhiªn, ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá lµ kh«ng thÓ gi¶ m¹o. Chøng minh: Theo bæ ®Ò trªn, ch÷ ký s+ lµ tin cËy nÕu s+1 = CP(r1, a, as+c, g, gs+c)(m), s+2 = S(sr2, g, as)(s+1) vµ r1 = r2. §iÒu nµy cã nghÜa r»ng nÕu tån t¹i thêi gian ®a thøc ®èi thñ A thµnh c«ng t¹o ra c¶ s vµ s, sau ®ã A ph¶i biÕt r1, r2s vµ kho¸ bÝ mËt s. V× vËy chØ cã mét viÔn c¶nh r»ng A cã thÓ gi¶ m¹o s+ mµ kh«ng cÇn truy cËp ®Õn kho¸ bÝ mËt s ®Ó ®¹t ®­îc hoÆc s hoÆc s. Gi¶ sö A ®¹t ®­îc s, s h×nh thµnh tõ ch÷ ký s* = (s,s). Theo bæ ®Ò trªn, ®iÒu nµy cã nghÜa lµ s, s ®· ®ùoc t¹o ra cïng mét kho¸ bÝ mËt r2s Þ A biÕt bÝ mËt ®Ó t¹o s. §iÒu nµy m©u thuÉn víi ®Æc tÝnh kh«ng thÓ gi¶ m¹o v÷ng ch¾c cña s2.  VI.5.2. Ch÷ ký kh«ng thÓ ph©n biÖt §Þnh nghÜa 4: (ch÷ ký bÞ gi¶ m¹o) Cho x, gy = gy vµ gz = gz, ch÷ ký gi¶ m¹o s* = (s, s) trªn th«ng b¸o m ®­îc tÝnh: s= CP(x, X, Xy+c, g, gy+c) vµ s= S(z, g, yz)( s) Trong ®ã c, gc lµ kho¸ bÝ mËt vµ c«ng khai cña ng­êi x¸c nhËn, X = gx, Xy+c = g vµ gy+c = gygc. Ch÷ ký nh­ trªn ®­îc ®Æt d­íi m« h×nh Oracle ngÉu nhiªn. PhÇn ®Çu cña ch÷ ký lµ s cã thÓ lu«n lu«n ®­îc thµnh lËp khi biÕt x. PhÇn tiÕp theo cña ch÷ ký lµ s, ch÷ ký Schnorr kiÓm tra dïng kho¸ c«ng khai gz = gz. Ch÷ ký Schnorr (u,v) ®­îc gi¶ m¹o trong m« h×nh Oracle ngÉu nhiªn. §iÒu nµy ®­îc thùc hiÖn b»ng c¸ch chän u,v ngÉu nhiªn vµ Oracle ngÉu nhiªn gi¶ m¹o trong c¸ch mµ nã cã c¸c ®Çu ra u víi ®Çu vµo (mççyççgççgvyu). §Þnh lý: Trong m« h×nh Oracle ngÉu nhiªn, nÕu tån t¹i ng­êi gi¶ m¹o A mµ cã thÓ ph©n biÖt ch÷ ký tin cËy tõ ch÷ ký gi¶ m¹o ®· ®­îc t¹o ra dïng ®Þnh nghÜa ë trªn trong thêi gian ®a thøc theo x¸c suÊt th× cã mét thuËt to¸n gi¶i quyÕt vÊn ®Ò Diffie – Hellman trong thêi gian ®a thøc theo x¸c suÊt. Chøng minh: Gi¶ sö cã mét ®èi thñ A mµ cã thÓ ph©n biÖt ch÷ ký tin cËy s tõ ch÷ ký gi¶ m¹o s* dïng th«ng tin c«ng khai. Ký hiÖu tËp hîp cña tÊt c¶ (a, gb, gc½ab = c) lµ D vµ ( a, gb, gc ½aÎR Z ) lµ X. LÊy t* = (x1, gy, gz ) Î D, t+ = (x2, gy, gz )Î X. Theo ®Þnh nghÜa cña ch÷ ký gi¶ m¹o, A cã thÓ t¹o ra 2 ch÷ ký gi¶ m¹o s*, s+ lÇn l­ît tõ t*, t+. ë ®ay kho¸ c«ng khai cña ng­êi ký lµ gy. Theo bæ ®Ò trong phÇn [VI. 5. 1], s* lµ ch÷ ký tin cËy, s+ lµ ch÷ ký kh«ng tin cËy. Ngoµi ra sù thuËn lîi cña A trong ph©n biÖt s* tõ s+ lµ kh«ng ®¸ng kÓ h¬n ph©n biÖt gi÷a t* vµ t+ . V× vËy nÕu A cã kh¶ n¨ng nhËn biÕt ch÷ ký chÝnh x¸c tõ s* vµ s+, chóng ta nãi r»ng t* hoÆc t+ h×nh thµnh tõ D. A ®· gi¶i quyÕt ®­îc vÊn ®Ò cña Diffie – Hellman.   VI.5.3. TÝnh nhÊt qu¸n cña kiÓm tra ch÷ ký Theo bæ ®Ò phÇn [VI. 5. 1], ch÷ ký lµ tin cËy chØ khi hoÆc as+c /as = ac hoÆc as = as. Nã kh«ng phøc t¹p ®Ó chØ ra sù t­¬ng quan ®èi lËp, nãi c¸ch kh¸c nÕu ®¹t ®­îc hoÆc as+c /as = ac hoÆc as = as th× s1 lµ phÐp chøng minh hîp lý cña tri thøc vµ ®¼ng thøc, s2 lµ ch÷ ký tin cËy, s lµ ch÷ ký ®óng. V× vËy tÝnh nhÊt qu¸n cña sù kiÓm tra ch÷ ký tu©n theo tÝnh ®óng ®¾n vµ hîp lý cña phÐp chøng minh ký cña tri thøc. VI. 6. Ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá mï qu¸ng vµ c¸c øng dông VI. 6. 1. CÊu tróc Giao thøc ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá mï qu¸ng gåm ®Æc thï cña ch÷ ký Schnorr mï qu¸ng vµ ®Æc thï cña ch÷ ký Chaum – Petersen cña ®¼ng thøc mï qu¸ng thùc hiÖn song song víi nhau. CÊu tróc nh­ sau: Ng­êi nhËn Ng­êi ký p, r1, r2 ÎZ r, r1, r2 Î Z a = gr as = gsr as+c = g w2 = g w1 = g W1 = g = = = w2 = w2p. g w1 = w1p. g = W1p. g v = H(m ½½½½½½½½w2½½w1½½) u = v/p v1 = r1 – u(r) v2 = r2 – u(rs) = v1p + r1 = v2p + r2 s+1 = (v, , , , w1, 1) s+2 = (v, , , w2) Trong cÊu tróc nµy, ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá mï qu¸ng lµ s = (s+1, s+2), chóng ta ®¸nh l¹c h­íng mét ®Æc thï t­¬ng t¸c cña giao thøc t¹o ch÷ ký tõ t¹o s1 = CP(r, a, as+c, g, gs+c)(m), s2 = S(sr, g, as)(s1) ®Ó t¹o s+1 = CP(rp, b, bs+c, g, gs+c)(m), s+2 = S(srp, g, bs)(s+1) trong ®ã b = ap , bs = a vµ bs+c = a. Ng­êi trung gian tøc ng­êi nhËn ch÷ ký trong giao thøc biÕt gi¸ trÞ p. §iÒu nµy kh«ng phøc t¹p ®Ó kiÓm tra s+1 lµ ch÷ ký Chaum – Petersen tin cËy trªn th«ng b¸o m vµ s+2 lµ ch÷ ký Schnorr tin cËy trªn th«ng b¸o (mïïs+1). Do ®ã s+ = (s+1, s+2) lµ ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá tin cËy. VI. 6. 2. L­îc ®å tr¶ tr­íc cã thÓ leo thang Chóng ta còng ®· kh¸ quen víi c¸c hÖ thèng tr¶ tiÒn tr­íc ®Ó mua mét s¶n phÈm nµo ®ã nh­ ®Æt mua t¹p chÝ, truyÒn h×nh c¸p… HiÖn nay, cïng víi sù ph¸t triÓn m¹nh mÏ cña c«ng nghÖ th«ng tin vµ sù giao l­u th«ng tin ngµy cµng trë nªn phæ biÕn trªn c¸c m¹ng truyÒn th«ng th× ng­êi ta còng nghÜ tíi c¸c ho¹t ®éng kinh doanh trªn m¹ng Internet. C¸c ho¹t ®éng th­¬ng m¹i cña c¸c dÞch vô trùc tuyÕn trªn Internet ®ßi hái ph¶i nhanh vµ cã c¸c ph­¬ng thøc tr¶ tiÒn ®¹t hiÖu qu¶ cao. Gi¶i ph¸p phæ biÕn lµ micropayment nghÜa lµ ng­êi sö dông tr¶ mét sè tiÒn nhá cho tong s¶n phÈm mua trùc tuyÕn. Gi¶i ph¸p lùa chän lµ tr¶ tr­íc, ng­êi sö dông tr¶ tr­íc víi dÞch vô mét sè tiÒn cè ®Þnh gäi lµ lÖ phÝ hµng n¨m. Ng­êi sö dông sau ®ã ®­îc cÊp mét giÊy chøng nhËn tr¶ tr­íc mµ cho phÐp truy cËp ®Õn mäi s¶n phÈm cña dÞch vô. Sù thuËn lîi cña dÞch vô tr¶ tr­íc trªn micropayment lµ nã gi¶m mét l­îng lín qu¸ tr×nh tiÕn hµnh c«ng viÖc mua b¸n cña sù giao dÞch khi mua mét s¶n phÈm ®Þnh gi¸ nhá. Trong thùc tÕ, kh«ng x¶y ra viÖc ng­êi cung cÊp dÞch vô cã thÓ cung cÊp t¸t c¶ c¸c dÞch vô mong muèn tíi ng­êi sö dông. Ngoµi ra nã bÊt tiÖn víi ng­êi sö dông khi ph¶i gi÷ m· sè cña giÊy chøng nhËn tr¶ tr­íc, nÕu mçi s¶n phÈm ng­êi sö dông ph¶i gi÷ mét giÊy chøng nhËn tr¶ tr­íc th× ®iÒu nµy sÏ g©y phiÒn to¸i cho ng­êi sö dông. Gi¶i ph¸p mong muèn lµ sÏ liªn hiÖp c¸c c«ng ty lín cña nh÷ng ng­êi cung cÊp dÞch vô ®Ó cung cÊp nhiÒu lo¹i kh¸c nhau cña c¸c dÞch vô trùc tuyÕn. Trong thø tù truy cËp ®Õn c¸c dÞch vô nµy, mçi ng­êi sö dông chØ cÇn mét giÊy chøng nhËn ®Æt tr­íc víi c¸i mµ anh ta ®· tr¶ tiÒn lÖ phÝ cè ®Þnh hµng n¨m. Khi ®ã ng­êi sö dông cã thÓ truy cËp ®Õn tÊt c¶ c¸c dÞch vô cung cÊp bëi bÊt kú thµnh phÇn nµo trong liªn hiÖp c¸c c«ng ty. Ch÷ ký mï qu¸ng cã thÓ dïng ®Ó thiÕt kÕ mét hÖ thèng tr¶ tr­íc víi quyÒn riªng t­ cña ng­êi sö dông. Trong m« h×nh nµy, giÊy chøng nhËn tr¶ tr­íc lµ ®­a ra ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá mï qu¸ng bëi ng­êi qu¶n lý cña liªn hiÖp c¸c c«ng ty. §Ó truy cËp tíi c¸c dÞch vô trùc tuyÕn, ng­êi sö dông chøng tá giÊy chøng nhËn tr¶ tr­íc tin cËy víi ng­êi cung cÊp dÞch vô, ng­êi cã vai trß ng­êi x¸c nhËn trong l­îc ®å ch÷ ký. ThuËn lîi chÝnh cña c¸ch nµy lµ gi¶m tr¸ch nhiÖm mét l­îng lín qu¸ tr×nh tiÕn hµnh c«ng viÖc mua b¸n cña viÖc tr¶ mét l­îng nhá trong khi, thËm chÝ cung cÊp c¶ quyÒn riªng t­ cho ng­êi sö dông. KÕt luËn Ngµy nay, cïng víi sù ph¸t triÓn cña khoa häc c«ng nghÖ hiÖn ®¹i vµ C«ng nghÖ th«ng tin, ngµnh mËt m· ®· cã nh÷ng b­íc ph¸t triÓn m¹nh mÏ, ®¹t ®­îc nhiÒu kÕt qu¶ lý thuyÕt s©u s¾c vµ t¹o c¬ së cho viÖc ph¸t triÓn c¸c gi¶i ph¸p b¶o mËt, an toµn th«ng tin trong mäi lÜnh vùc ho¹t ®éng cña con ng­êi. §Æc biÖt lµ nh÷ng ­u ®iÓm cña ch÷ ký sè. Ch÷ ký sè ®­îc biÕt ®Õn khi sù trao ®æi th«ng tin ngµy cµng phæ biÕn trªn c¸c m¹ng truyÒn th«ng ë n¬i mµ ch÷ ký tay kh«ng thÓ ph¸t huy t¸c dông. Trong ®å ¸n nµy, t«i ®· t×m hiÓu vÒ l­îc ®å ch÷ ký sè ng­êi x¸c nhËn kh«ng thÓ chèi bá. Tuy cßn nhiÒu ®iÓm cÇn ph¶i nghiªn cøu vµ hoµn thiÖn nh­ng do thêi gian vµ tr×nh ®é hiÓu biÕt cßn h¹n chÕ nªn kh«ng tr¸nh khái nh÷ng nh­îc ®iÓm, rÊt mong sù gãp ý cña c¸c ThÇy, C« vµ c¸c b¹n. Cuèi cïng, em xin ch©n thµnh c¶m ¬n thÇy gi¸o TS. NguyÔn Ngäc C­¬ng ®· tËn t×nh chØ b¶o, h­íng dÉn gióp em hoµn thµnh ®å ¸n nµy. Tµi liÖu tham kh¶o TS. NguyÔn Ngäc C­¬ng – “Bµi gi¶ng An toµn th«ng tin” – 1999 NguyÔn ThÞ M­êi Ph­¬ng – “LuËn v¨n th¹c sÜ “- 2003 3. D.R Stinson – “Cryptography Theory and Practice”, CRC press – 1995 4. Moti Yung – “Weaknesses of undeniable Signature Schemes” 5. David Chaum – “Designated Confirmer Signatures” 4. Khanh Nguyen, Yi Mu, Vijay Varadharajan – “Undeniable Confirmer Signature” Môc lôc Lêi nhËn xÐt Môc lôc §Æt vÊn ®Ò 1 Ch­¬ng I: Tæng quan vÒ ng«n ng÷ C 4 I.1. LÞch sö h×nh thµnh vµ ph¸t triÓn 4 I.2. C¸c tÝnh chÊt ®Æc tr­ng cña ng«n ng÷ 5 Ch­¬ng II: Ch÷ ký sè 7 II. 1. Giíi thiÖu chung vÒ ch÷ ký sè 7 II.2. §Þnh nghÜa l­îc ®å ch÷ ký sè 8 II.3. Mét sè l­îc ®å ch÷ ký sè 9 II.3.1. L­îc ®å ch÷ ký RSA 9 II.3.2.L­îc ®å ch÷ ký ElGamal 11 Ch­¬ng III: Hµm Hash 15 III.1. Giíi thiÖu 15 III.2. §Þnh nghÜa 16 III.3. Mét sè hµm Hash sö dông trong l­îc ®å ch÷ ký sè 16 III.3.1.C¸c hµm Hash ®¬n gi¶n 16 III.3.2. Kü thuËt khèi xÝch 18 III.3.3. C¸c hµm Hash më réng 18 III.3.4. Hµm Hash MD4 19 Ch­¬ng IV: Ch÷ ký chèng chèi bá 25 IV.1. Giíi thiÖu 25 IV.2. L­îc ®å ch÷ ký sè chèng chèi bá 25 IV.2.1. ThuËt to¸n ký 25 IV.2.2. Giao thøc kiÓm tra 26 IV.2.3. Giao thøc chèi bá 27 IV.3. C¸c ®Þnh lý 29 IV.3.1. §Þnh lý 1 29 IV.3.2. §Þnh lý 2 30 IV.3.3. §Þnh lý 3 31 IV.4. VÊn ®Ò cÇn gi¶i quyÕt 33 Ch­¬ng V: Ch÷ ký ng­êi x¸c nhËn ®­îc chØ ®Þnh 35 V.1. Giíi thiÖu 35 V.2. HÖ thèng c¬ së 37 V.3. Giao thøc ký 38 V.3.1. T¹o kho¸ 38 V.3.2. T¹o ch÷ ký 38 V.3.3. Giao thøc kiÓm tra 39 V.4. Giao thøc x¸c nhËn 40 V.5. Giao thøc chuyÓn ®æi 41 V.6. Tæng qu¸t 42 Ch­¬ng VI: Ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá 43 VI.1. Giíi thiÖu 43 VI.2. M« h×nh cña ch÷ ký ng­êi x¸c nhËn chèng chèi bá 44 VI.3. C¸c l­îc ®å ch÷ ký vµ phÐp chøng minh ký t­¬ng t¸c 46 VI.3.1. Ký hiÖu 46 VI.3.2. L­îc ®å ch÷ ký Schnorr 46 VI.3.3. Ch÷ ký Chaum – Petersen dùa vµo ®¼ng thøc cña thuËt to¸n rêi r¹c 46 VI.3.4. PhÐp chøng minh ký t­¬ng t¸c Fujioka – Okamoto – Ohto cña ®¼ng thøc 47 VI.4. CÊu tróc 49 VI.4.1. T¹o kho¸ 49 VI.4.2. T¹o ch÷ ký 49 VI.4.3. KiÓm tra ch÷ ký 49 VI.4.4. Gi¶i thÝch cÊu tróc cña l­îc ®å ch÷ ký b»ng trùc gi¸c 50 VI.5. PhÐp ph©n tÝch an toµn 50 VI.5.1. Ch÷ kýkh«ng thÓ gi¶ m¹o 51 VI.5.2. Ch÷ ký kh«ng thÓ ph©n biÖt ®­îc 52 VI.5.3. TÝnh nhÊt qu¸n cña kiÓm tra ch÷ ký 53 VI.6. Ch÷ ký ng­êi x¸c nhËn kh«ng thÓ chèi bá mï qu¸ng vµ c¸c øng dông 54 VI.6.1. CÊu tróc 54 VI.6.2L­îc ®å tr¶ tr­íc cã thÓ leo thang 55 KÕt luËn 57 Tµi liÖu tham kh¶o 58