Giáo trình Mật mã và ứng dụng: Chương 7

Giáo trình Mật mã và ứng dụng - Chương 7: Các hàm Hash, trình bày các nội dung cơ bản: các chữ kí và hàm Hash, hàm Hash không va chạm, hàm hash logarithm rời rạc, các hàm hash mở rộng, 8 nhãn thời gian. Đây là tài liệu tham khảo dành cho sinh viên Công nghệ thông tin.
Nội dung trích xuất từ tài liệu:
Giáo trình Mật mã và ứng dụng: Chương 7Vietebooks Nguyễn Hoàng Cương 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ò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. Trang 1Vietebooks Nguyễn Hoàng CươngH×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 bit7.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è tinhs 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’). Trang 2Vietebooks Nguyễn Hoàng CươngNhË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. 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 gi¶ thiÕt yÕu vÒ kÝch th−íc t−¬ng®èi cña vïng vµ miÒn (domain and range) ...