Mật mã - Khoa học khám phá: Phần 2

Lịch sử của mật mã là câu chuyện về cuộc chiến kéo dài hàng thế kỷ giữa người lập mã và người giải mã, cuộc chạy đua vũ khí trí tuệ đã có tác động rất to lớn đến tiến trình của lịch sử. Tài liệu đã phác họa sự tiến hóa của mật mã và quá trình phá mã - tái lập mật mã mới. Mời các bạn cùng tham khảo phần 2 Tài liệu này.
Nội dung trích xuất từ tài liệu:
Mật mã - Khoa học khám phá: Phần 2Vietebooks Nguyễn Hoàng Cương6.11. Chøng minh r»ng, mçi líp t−¬ng ®−¬ng c¸c kho¸ trong s¬ ®å ch÷ kÝFail-Stop cña Pedersen-Van Hðyt chøa q2 kho¸.6.12. Gi¶ sö Bob ®ang dïng s¬ ®å ch÷ kÝ Fail-Stop cña Pedersen-Van Heystvíi p = 3467, α =4, a 0=1567 vµ β =514 (dÜ nhiªn Bob kh«ng biÕt gi¸ trÞ a0). a) Dïng yÕu tè a0 =1567, x¸c ®Þnh tÊt c¶ c¸c kho¸ cã thÓ : K = (γ1, γ2, a1, a2, b1, b2) sao cho sig K(42) =(1118,1449) b) G¸i sö sigK(42) =(1118,1449) vµ sigK(969) =(899,471). Kh«ng cÇndïng ®iÒu kÞªn a0 =1567. H·y x¸c ®Þnh K (®iÒu nµy sÏ chøng tá s¬ ®å lµ dïngmét lÇn).6.13. G¶i sö Bob dïng s¬ ®å Fail-Stop cña Pedersen-Van Heyst v¬i p =5087,α =25, β =1866. Gi¶ sö K =(5065, 5067,144,874,1873,2345) vµ Bob t×m ch÷kÝ (2219,458) ®−îc gi¶ m¹o trªn bøc ®iÖn 4785 a) Chøng minh r»ng, ch÷ kÝ gi¶ m¹o nµy tho¶ m·n ®iÒu kiÖn x¸c minh nªn nã lµ ch÷ kÝ hîp lÖ. b) ChØ ra c¸ch Bob tÝnh “ b»ng chøng gi¶ m¹o a0 khi cho tr−íc ch÷ kÝ gi¶ m¹o nµy. ” ch−¬ng 7 c¸c hμm hash7.1 c¸c chò kÝ vμ hμm hash. B¹n ®äc cã thÓ thÊy r»ng c¸c s¬ då ch÷ kÝ trong ch−¬ng 6 chØ cho phÐpkÝ c¸c bøc ®iÖn nhá.VÝ dô, khi dïng DSS, bøc ®iÖn 160 bit sÏ ®−îc kÝ b»ngch÷ kÝ dµi 320 bÝt. Trªn thùc tÕ ta cÇn c¸c bøc ®iÖn dµi h¬n nhiÒu. Ch¼ng h¹n,mét tµi liÖu vÒ ph¸p luËt cã thÓ dµi nhiÒu Megabyte. Mét c¸ch ®¬n gi¶n ®Ó g¶i bµi to¸n nµy lµ chÆt c¸c bøc ®iÖn dµi thµnhnhiÒu ®o¹n 160 bit, sau ®ã kÝ lªn c¸c ®o¹n ®ã ®éc lËp nhau. §iÒu nµy còng Trang 30Vietebooks Nguyễn Hoàng Cươngt−¬ng tù nh− m· mét chu«Ü dµi b¶n râ b»ng c¸ch m· cña mçi kÝ tù b¶n râ ®éclËp nhau b»ng cïng mét b¶n kho¸. (VÝ dô: chÕ ®é ECB trong DES). BiÖn ph¸p nµy cã mét sè vÊ ®Ò trong viÖc t¹o ra c¸c ch÷ kÝ sè. Tr−íchÕt, víi mét bøc ®iÖn dµi, ta kÕt thóc b»ng mét ch÷ kÝ rÊt lín ( dµi gÊp ®«i bøc®iÖn gèc trong tr−êng hîp DSS). Nh−îc ®iÓm kh¸c lµ c¸c s¬ ®å ch÷ kÝ “antoµn” l¹i chËm v× chóng dïng c¸c ph¸p sè häc phøc t¹p nh− sè mò modulo.Tuy nhiªn, vÊn ®Ò nghiªm träng h¬n víi phÐp to¸n nµy lµ bóc ®iÖn ®· kÝ cã thÓbÞ s¾p xÕp l¹i c¸c ®o¹n kh¸c nhau,hoÆc mét sè ®o¹n trong chóng cã thÓ bÞ lo¹ibá vµ bøc ®iÖn nhËn ®−îc vÉn ph¶i x¸c minh ®−îc. Ta cÇn b¶o vÖ sù nguyªnvÑn cña toµn bé bøc ®iÖn vµ ®iÒu nµy kh«ng thÓ thùc hiÖn ®−îc b»ng c¸ch kÝ®éc lËp tõng mÈu nhá cña chóng. Gi¶i ph¸p cho tÊt c¶ c¸c vÊn ®Ò nµy lµ dïng hµm Hash m· kho¸ c«ngkhai nhanh. Hµm nµy lÊy mét bøc ®iÖn cã ®é dµi tuú ý vµ t¹o ra mét b¶n tãml−îc th«ng b¸o cã kÝch th−íc qui ®Þnh (160 bit nÕu dïng DSS). Sau ®ã b¶n tãm l−îc th«ng b¸o sÏ ®−îc kÝ. V¬i DSS, viÖc dïng hµmHash ®−îc biÓu diÔn trª h×nh 7.1. Khi Bob muèn kÝ bøc ®iÖn x, tr−íc tiªn anh ta x©y dùng mét bnr tãml−îc th«ng b¸o z = h(x) vµ sau ®ã tÝnh y = sigK (z ). Bob truyÒn cÆp ( x, y)trªn kªnh. XÐt thÊy cã thÓ thùc hiÖn x¸c minh (bëi ai ®ã ) b»ng c¸ch tr−íc hÕtkh«i phôc b¶n tãm l−îc th«ng b¸o z =h (x) b»ng hµm h c«ng khai vµ sau ®ãkiÓm tra xem verk (x,y) cã = true, hay kh«ng.H×nh 7.1.KÝ mét b¶n tãm l−îc th«ng b¸o Bøc ®iÖn :x ®é dµi tuú ý ↓ b¶n tãm l−îc th«ng b¸o:z = h (x) 160 bit ↓ Ch÷ kÝ y = sig K(z) 320 bit Trang 31Vietebooks Nguyễn Hoàng Cương7.2. hμm hash kh«ng va ch¹m Chóng ta cÇn chó ý r»ng,viÖc dïng hµm hash h kh«ng lµm gi¶m sù an toµncña s¬ ®å ch÷ kÝ v× nã lµ b¶n tãm l−îc th«ng b¸o ®−îc ch÷ kÝ kh«ng ph¶i lµbøc ®iÖn. §iÒu cÇn thiÕt ®èi víi h lµ cÇn tho¶ m·n mét sè tÝnh chÊt nµo ®ã ®Ótranh sù gi¶ m¹o. KiÓu tÊn c«ng th«ng th−êng nhÊt lµ Oscar b¾t ®Çu b»ng mét bøc diÖn ®−îckÝ hîp lÖ (x, y), y =sigK(h (x)),(CÆp (x, y) lµ bøc ®iÖn bÊt k× ®−îc Bob kÝ tr−íc®ã). Sau ®ã anh ta tÝnh z = h(x) vµ thö t×m x ≠ x’ sao cho h(x’) = h(x). NÕuOscar lµm ®−îc nh− vËy, (x’, y) sÏ lµ bøc ®iÖn kÝ hîp lÖ, tøc mét bøc ®iÖn gi¶m¹o. §Ó tr¸nh kiÓu tÊn c«ng nµy, h cÇn tho¶ m·n tÝnh kh«ng va ch¹m nh− sau:§Þnh nghÜa 7.1 Hµm hash h lµ hµm kh«ng va ch¹m yÕu nÕu khi cho tr−íc mét bøc ®iÖnx, kh«ng thÓ tiÕn hµnh vÒ mÆt tÝnh to¸n ®Ó t×m mét bøc ®iÖn x ≠ x’ sao choh (x’) = h(x). Mét tÊn c«ng kiÓu kh¸c nh− sau: Tr−íc hÕt Oscar t×m hai bøc ®iÖn x ≠ x’sao cho h(x) =h(x’). Sau ®ã Oscar ®−a x cho Bob vµ thyÕt phôc Bob kÝ b¶n tãml−îc th«ng b¸o h(x) ®Ó nhËn ®−îc y. Khi ®è (x’,y) lµ th«ng b¸o (bøc ®iÖn ) gi¶m¹o hîp lÖ. §©y lµ lÝ do ®−a ra mét tÝnh chÊt kh«ng va ch¹m kh¸c.§Þnh nghÜa 7.2. Hµm Hash h lµ kh«ng va ch¹m m¹nh nÕu kh«ng cã kh¶ n¨ng tÝnh to¸n®Ó t×m ra bøc ®iªnk x vµ x’ sao cho x ≠ x’ vµ h(x) = h(x’).NhËn xÐt r»ng: kh«ng va ch¹m m¹nh bao hµm va ch¹m yÕu. Cßn ®©y lµ kiÓu tÊn c«ng thø 3: Nh− ®· nãi ë phÇn 6.2 viÖc gi¶ m¹o c¸cch÷ kÝ trªn b¶n tãm l−îc th«ng b¸o z ngÉu nhiªn th−êng x¶y ra víi s¬ ®å ch÷kÝ. Gi¶ sö Oscar tÝnh ch÷ kÝ trªn b¶n tãm l−îc th«ng b¸o z ngÉu nhiªn nh−vËy. Sau ®ã anh ta t×m x sao cho z= h(x). NÕu lµm ®−îc nh− vËy th× (x,y) lµbøc ®iÖn gi¶ m¹o hîp lÖ. §Ó tr¸nh ®−îc tÊn c«ng nµy, h cÇn tho¶ m·n tÝnhchÊt mét chiÒu (nh− trong hÖ m· kho¸ c«ng khai vµ s¬ ®å Lamport).§Þnh nghÜa 7.3. Hµm Hash h lµ mét chiÒu nÕu khi cho tr−íc mét b¶n tãm l−îc th«ng b¸o z,kh«ng thÓ thùc hiÖn vÒ mÆt tÝnh to¸n ®Ó t×m bøc ®iÖn x sao cho h(x) = z. Trang 32Vietebooks Nguyễn Hoàng Cương B©y giê ta sÏ chøng minh r»ng, tÝnh chÊt kh«ng va ch¹m m¹nh bao hµmtÝnh mét chiÒu b»ng ph¶n chøng. §Æc biÖt ta sÏ chøng minh r»ng, cã thÓ dïngthuËt to¸n ®¶o víi hµm Hash nh− mét ch−¬ng tr×nh con (gi¶ ®Þnh ) trong thuËtto¸n x¸c suÊt Las Vegas ®Ó t×m c¸c va ch¹m. Sù rót gän nµy cã thÓ thùc hiÖn víi mét g ...