Giáo trình tin học : Tìm hiểu một sơ đồ chữ kí số phần 5

Hệ phương trình này có ít nhâts một nghiệm nhận được bằng cách dùng khoá K.Vì hàng của ma trận hệ số bằng 3 nên suy ra rằng chiều của không gian nghiệm là 4-3=1 và có chính xác q nghiệm.
Nội dung trích xuất từ tài liệu:
Giáo trình tin học : Tìm hiểu một sơ đồ chữ kí số phần 5Vietebooks Nguyễn Hoàng Cươngcã thÓ thÊy ma trËn hÖ thèng sè cña ph−¬ng tr×nh cã h¹ng lµ 3( h¹ng cña métma trËn lµ sè cùc ®Ëi cña c¸c hµng ®éc lËp tuyÕn tÝnh mµ nã cã). Râ rµng,h¹ng Ýt nhÊt b»ng 3 v× c¸c hµng 1, 2 vµ 4 lµ ®éc lËp tuyÕn tÝnh trªn Zp. cßnh¹ng nhiÒu nhÊt còng b»ng 3 v×: r1 +x r2-r3-a0r4= (0,0,0,0).Víi r1 chØ hµng thø i cña ma trËn. HÖ ph−¬ng tr×nh nµy cã Ýt nh©ts mét nghiÖm nhËn ®−îc b»ng c¸chdïng kho¸ K.V× hµng cña ma trËn hÖ sè b»ng 3 nªn suy ra r»ng chiÒu cñakh«ng gian nghiÖm lµ 4-3=1 vµ cã chÝnh x¸c q nghiÖm. T−¬ng tù nh− vËy ta cã thÓ chøng minh ®−îc kÕt qña sau:Bæ ®Ò 6.6 Gi¶ sö K lµ kho¸ y=sigK(x) cßn verK (x’,y’)=true, trong ®ã x’ # x. Khi ®ãtån t¹i Ýt nhÊt mét kho¸ K’ t−¬ng ®−¬ng víi K sao cho y=sigK’(x) vµ y’=sigK’(x’) Ta h·y lµm s¸ng tá hai bæ ®Ò trªn vÒ ®é mËt cña s¬ ®å. Khi cho tr−íc y lµch÷ kÝ hîp lÖ cña x, sÏ tån t¹i q kho¸ cã thÓ ®Ó x sÏ ®−îc kÝ b»ng y. Song víibøc ®iÖn bÊt k× x’≠ x, q kho¸ nµy sÏ t¹o ra q kho¸ kh¸c nhau trªn x’. §iÒu ®ãdÉn ®Õn ®Þnh lÝ sau ®©y:§Þnh lÝ 6.7: NÕu cho tr−íc sigK(x)=y vµ x’≠ x. Oscar cã thÓ tÝnh sig K(x’) víi x¸c suÊtlµ 1/q. Chó ý r»ng, ®Þnh lÝ nµy kh«ng phô thuéc vµo kh¶ n¨ng tÝnh to¸n cña Oscar:Møc an toµn qui ®Þnh ®¹t ®−îc v× Oscar kh«ng thÓ nãi vÒ q kho¸ cã thÓ mµBob ®ang dïng. Nh− vËy ®é an toµn ë ®©y lµ v« ®iÒu kiÖn. TiÕp tôc xem xÐt vÒ kh¸i niÖm Fail- Stop. Khi cho tr−íc ch÷ ký y trªnbøc ®iÖn x. Oscar kh«ng thÓ tÝnh ra ®−îc ch÷ ký y’ cña Bob trªn bøc ®iÖn x’kh¸c. §iÒu nµy còng cã thÓ hiÓu r»ng, Oscar cã thÓ tÝnh ®−îc ch÷ ký gi¶ m¹o Trang 25Vietebooks Nguyễn Hoàng Cươngy’’ = sigK(x’)(sÏ ®−îc chøng minh ). Tuy nhiªn, nÕu ®−a cho Bob mét ch÷ kýgi¶ m¹o hîp lÖ, th× anh ta cã thÓ t¹o ra “mét b»ng chøng vÒ sù gi¶ m¹o ” víix¸c suÊt 1-1/q. B»ng chøng vÒ sù gi¶ m¹o lµ gi¸ trÞ a0=logα β (chØ ng−êi cãthÈm quyÒn trung t©m biÕt ). Gi¶ sö Bob së h÷u cÆp (x’,y’’) sao cho ver(x’,y’’)= true vµ y’’≠sigK(x’).NghÜa lµ: γ1γ2x’ ≡ αy”1βy”2(mod p)trong ®ã :y’’=(y’’1,y’’2). B©y giê Bob cã thÓ tÝnh ch÷ ký cña m×nh trªn x’ lµ y’ =(y’1,y2’). Khi ®ã : γ1γ2x’ ≡ αy’1βy’2(mod p) αy”1βy”2 ≡ αy’1βy’2(mod p)v× thÕNÕu viÕt β = α 0mod p, ta cã : a αy”1+ a0 y”2 ≡ αy’1+ a0 y’2(mod p)hay: y”+a0y”2 ≡ y’1+a0y’(mod q)hoÆc: y’’1- y1’ ≡ a0(y’2-y”2’)(mod q)XÐt thÊy y’1≡ y’’2(mod q) v× y’ lµ gi¶ m¹o. V× thÕ (y’2-y’’2)-1 mod q tån t¹i vµ a0 =logα β = (y’’1-y’1) (y’2-y’’2)-1 mod q DÜ nhiªn, b»ng viÖc chÊp nhËn b»ng chøng vÒ sù gi¶ m¹o nh− vËy,ta gi¶thiÕt Bob kh«ng thÓt ù tÝnh ®−îc logarithm rêi r¹c logα β. §©y lµ g¶i thiÕt vÒmÆt tÝnh to¸n. Cuèi cïng, chó ý r»ng,s¬ ®å ch÷ kÝ lµ mét lÇn v× khãa k cña Bob cã thÓtÝnh dÔ dµng nÕu hai bøc ®iÖn ®Òu dïng K ®Ó ký. D−íi ®©y lµ vÝ dô minh ho¹c¸ch Bob t¹o mét b»ng chøng vÒ sù gi¶ m¹o. Trang 26Vietebooks Nguyễn Hoàng CươngVi dô 6.7 Cho p=4367=2.1733+1. PhÇn tö α =4 cã bËc lµ 1733 trong Z3467*Gi¶ sö ao =1567, ta cã: β = 41567 mod 346=514(Bob biÕt α vµ β song kh«ng biÕt a0). Gi¶ sö Bob tËp kho¸ b»ng c¸ch dïng a1 =888, a2 = 1042, b1 = 786, b2 = 999. Khi ®ã γ 1=48885141024 mod 3476=3405 γ 2=4786 514999 mod 3476=2281vµ TiÕp theo, gi¶ sö Bob nhËn ®−îc ch÷ kÝ gi¶ m¹o (822,55) trªnª bøc ®iÖn3383. §©y lµ ch÷ ký h¬p lÖ v× tho¶ m·n ®iÒu kiÖn x¸c minh. 3405 × 22813384≡ 2282 (mod 3476) 482251455≡ 2282(mod 3476)vµMÆt kh¸c ®©y kh«ng ph¶i lµ ch÷ kÝ ®· ®−îc Bob x©y dùng. Bob cã thÓ tÝng ch÷kÝ cña m×nh nh− sau:(888+3383×786 mod 1733.1024+3383×999 mod 1733 )=(1504.1291)Sau ®ã anh ta tÝnh tiÕp log rêi r¹c bÝ mËt a0 =(822-1504)(1291-55)-1 mod 1733 =1567.§©y lµ b»ng chøng vÒ sù gi¶ m¹o.6.7 c¸c chó gi¶i vÒ tμi liÖu dÉn Mitchell, Piper vµ Wild [MPW 92] ®· ®−a ra mét tæng quan ®Çy ®ñ vÒ c¸cs¬ ®å ch÷ kÝ. Bµi nµy còng cã hai ph−¬ng ph¸p gi¶ m¹o ch÷ kÝ cña Elgamalmµ ta ®· ®−a ra trong 6.2. S¬ ®å ch÷ kÝ Elgamal ®· ®−îc nªu trong [EL 85], tiªu chuÈn ch÷ kÝ sè®−îc c«ng bè ®Çu tiªn vµo 8/1991 bëi NIST vµ ®−îc chÊp nhËn lµm tiªu chuÈnvµo 12/94 [NBS 94]. Mét cuéc tho¶ luËn dµi vÒ DSS vµ nh÷ng cuéc tranh c·ixung quanh nã vµo 7/1992 ®−îc ®¨ng trªn Communication of the ACM. S¬ ®å Lamport ®−îc m« t¶ trong bµi b¸o cña Diffie_Hellman [DH 76]n¨m 1976. B¶n c¶i tiÕn cñaBob vµ Chaum ®−îc nªu trong [BC 93]. S¬ ®å ch÷ Trang 27Vietebooks Nguyễn Hoàng CươngkÝ kh«ng chèi nªu trong môc 6.5 do Chaum vµ Van Antwerpen ®−a ra trong[CVA 90]. S¬ ®å ch÷ kÝ ...