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

Ta xét hai trường hợp: Trường hợp 1: k=l Như trong định lý 7.3 hoặc ta tìm thấy một va chạm đỗi với h hoặc ta nhận được y = y’ song đIều này lạI bao hàm x = x’, dẫn đến mâu thuẫn.
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 8Vietebooks Nguyễn Hoàng Cương§Þnh lý 7.4 Gi¶ sö h: (Z2)n→(Z2) lµ hµm hash kh«ng va ch¹m m¹nh. Khi ®ã hµm ∞h*: Ui =m (Z2)t→(Z2)t ®−îc x©y dùng nh− trªn h×nh 7.5 lµ hµm hash kh«ng vach¹m m¹nh.Chøng minh: Gi¶ sö r»ng ta cã thÓ t×m ®−îc x ≠x’ sao cho h*(x)=h*(x’). KÝ hiÖu: y(x) = y1y2....ykvµ y(x’) = y’1y’2....y’lTa xÐt hai tr−êng hîp:Tr−êng hîp 1: k=l Nh− trong ®Þnh lý 7.3 hoÆc ta t×m thÊy mét va ch¹m ®çi víi h hoÆc tanhËn ®−îc y = y’ song ®IÒu nµy l¹I bao hµm x = x’, dÉn ®Õn m©u thuÉn.Tr−êng hîp2: k≠ l Kh«ng mÊt tÝnh tæng qu¸t ,gi¶ sö l>k . tr−êng hîp nµy xö lý theo kiÓut−¬ng tù. NÕu gi¶ thiÕt ta kh«ng t×m thÊy va ch¹m nµo ®èi víi h ,ta cã d·y c¸cph−¬ng tr×nh sau: y k = y’ l yk-1 = y’l-1 ............... y1 = y’l-k+1Song ®IÒu nµy m©u thuÉn víi tÝnh chÊt “kh«ng posfixx” nªu ë trªn. Tõ ®©y takÕt luËn r»ng h* lµ h¹m kh«ng va ch¹m.Ta sÏ tæng kÕt ho¸ hai x©y dùng trong phÇn nµy vµ sè c¸c øng dông cña h cÇnthiÕt ®Ó tÝnh h* theo ®Þnh lý sau:§Þnh lý 7.5 Gi¶ sö h: (Z2)n→(Z2) lµ hµm hash kh«ng va ch¹m m¹nh,ë ®©y m>=t+1.Khi ®ã tån t¹I hµm kh«ng va ch¹m m¹nh Trang 43Vietebooks Nguyễn Hoàng Cương h*: U∞ m (Z2)t→(Z2)t i=Sè lÇn h ®−îc tÝnh trong −íc l−îng h* nhiÒu nhÊt b»ng : l +⎡ n⎤ nÕu m>=t+2 ⎢ m − t − 1⎥ ⎣ ⎦ 2n +2 nÕu m= t+2trong ®ã |x|=n.7.6 c¸c hµm hash dùa trªn c¸c hÖ mËt Cho ®Õn nay, c¸c ph−¬ng ph¸p ®· m« t¶ ®Ó ®−a ®Õn nhøng hµm hashhÇu nh− ®Òu rÊt chËm ®èi víi c¸c øng dông thùc tiÔn. Mét biÖn ph¸p kh¸c lµdïng c¸c hÖ thèng m· ho¸ bÝ mËt hiÖn cã ®Ó x©y dõng c¸c hµm hash. Gi¶ sör»ng (P,C,K,E,D) lµ mét hÖ thèng mËt m· an toµn vÒ mÆt tÝnh to¸n. §Ó thuËntiÖn ta còng gi¶ thiÕt r»ng P = C = K = (Z2)n.ë ®©ychän n>=128 ®Ó x©y ng¨nchÆn kiÓu tÊn c«ng ngµy sinh nhËt. §IÒu nµy lo¹I trõ viÖc dïng DES (v× ®é dµikho¸ cña DES kh¸c víi ®é dµi b¶n râ). Gi¶ sö cho tr−íc mét x©u bit: x= x1||x2||....||xktrong ®ã xi ∈ (Z2)n, 1≤ i ≤ (nÕu sè bit trong x kh«ng ph¶i lµ béi cña n th× cÇnchÌn thªm vµo x theo c¸ch nµo ®ã. Ch¼ng h¹n nh− c¸ch lµm trong nôc 7.5. §Ó®¬n gi¶n ta sÏ bá qua ®IÓm nµy). ý t−ëng c¬ b¶n lµ b¾t ®Çu b»ng mét “gi¸ trÞ ban ®Çu” cè ®Þnh g0 =IV vµsau ®ã ta x©y dùng g1,...,gk theo quy t¾c thiÕt lËp : gi = f(xi,gi-1).ë ®©y f lµ hµm kÕt hîp toµn bé c¸c phÐp m· ho¸ cña hÖ mËt ®−îc dïng. Cuèicïng ta ®Þnh nghÜa b¶n tãm l−îc cña th«ng b¸o h(x) =gk. Vµi hµm hash kiÓu nµy ®· ®−îc ®Ò xuÊt vµ nhiÒu lo¹i trong chóng tá rakh«ng an toµn (kh«ng phô thuéc vµo viÖc liÖu hÖ mËt c¬ b¶n cã an toµn haykh«ng ). Tuy nhiªn , cã 4 ph−¬ng ¸n kh¸c nhau cã vÎ an toµn cña s¬ ®å nµy : gi = e gi-1 (xi) ⊕ xi Trang 44Vietebooks Nguyễn Hoàng Cương gi = e gi-1 (xi) ⊕ xI ⊕ gi-1 gi = e gi-1 (xi ⊕ gi-1) ⊕ xI gi = e gi-1 (xi ⊕ gi-1) ⊕ xI ⊕ gi-1.7.7 Hµm hash MD4. Hµm hash MD4 ®−îc Riverst ®Ò xuÊt n¨m 1990 vµ mét hiªn b¶n m¹nhlµ MD5 còng ®−îc ®−a ra n¨m 1991. ChuÈn hµm hash an toµn (hay SHS) phøct¹p h¬n song còng d−a tªn c¸c ph−¬ng ph¸p t−¬ng tù. Nã ®−îc c«ng bè tronghå s¬ liªn bang n¨m 1992 vµ ®−îc chÊp nhËn lµm tiªu chuÈn vµo ngµy11/5/1993. TÊt c¶ c¸c hµm hash trªn ®Òu rÊt nhanh nªn trªn thùc tÕ chóngdïng ®Ó kÝ c¸c bøc ®iÖn dµi. Trong phÇn nµy sÏ m« t¶ chi tiÕt MD4 vµ th¶o luËn mét sè c¶I tiÕn dïngtrong MD5 vµ SHS. Cho tr−íc mét x©u bit tr−íc hÕt ta t¹o mét m¹ng: M = M[0] M[1]... M[N-1] . trong ®ã M[i] lµ x©u bit cã ®é dµI 32 vµ N ≡ 0 mod 16. Ta sÏ gäi M[i] lµtõ. M ®−îc x©y dùng tõ x b»ng thuËt to¸n trong h×nh 7.6. H×nh 7.6 X©y dùng M trong MD4 1. d = 447-(|x| mod 512) 2. gi¶ sö l lµ kÝ hiÖu biÓu diÔn nhÞ ph©n cña |x| mod 264.|l| = 64 3. M = x||1||0d||l Trong viÖc x©y dùng M, ta g¾n sè 1 ss¬n lÎ vµo x, sau ®ã sÏ gµi thªmc¸c sè 0 ®ñ ®Ó ®é dµi trë nªn ®ång d− víi 448 modulo 512.,cuèi cïng nèithªm 64 bit ch−a biÓu diÔn nhÞ ph©n vÒ ®é dµI (ban ®Çu) cña x(®−îc rót gäntheo mãulo 264 nÕu cÇn). X©u kÕt qu¶ M cã ®é dµI chia hÕt cho 512. V× thÕ khichÆt M thµnh c¸c tõ 32 bit , sè tõ nhËn ®−îc lµ N-sÏ chia hÕt cho 16. B©y giê, tiÕp tôc x©y dùng b¶n tãm l−îc th«ng b¸o 128 bit. H×nh 7.7®−a ra m« t¶ thuËt to¸n ë møc cao. B¶n tãm l−îc th«ng b¸o ®−îc x©y dùngnh− sù kÕt nèi 4 tõ A,B,C vµ D mµ ta sÏ gäi lµ c¸c thanh ghi. Bèn thanh ghi®−îc khëi ®éng nh− ...