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

Giáo trình Mật mã và ứng dụng - Chương 5: Các hệ mã hóa công khai khác, trình bày các nội dung chính: hệ mật Elgamal và các logarithm rời rạc, trường hữu hạn và các hệ thống đường cong Elliptic, hệ mật xếp ba lô Merkle - Hell man,... Đâ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 5 Ch−¬ng 5 C¸c hÖ mËt kho¸ c«ng khai kh¸c Trong ch−¬ng n y ta sÏ xem xÐt mét sè hÖ mËt kho¸ c«ng khai kh¸c.HÖ mËt Elgamal dùa trªn b i to¸n logarithm rêi r¹c l b i to¸n ®−îc dïngnhiÒu trong nhiÒu thñ tôc mËt m . Bëi vËy ta sÏ d nh nhiÒu thêi gian ®Ó th¶oluËn vÒ b i to¸n quan träng n y. ë c¸c phÇn sau sÏ xem xÐt s¬ l−îc mét sè hÖmËt kho¸ c«ng khai quan träng kh¸c bao gåm c¸c hÖ thoãng lo¹i Elgamaldùa trªn c¸c tr−êng h÷u h¹n v c¸c ®−êng cong elliptic, hÖ mËt xÕp ba l«Merkle-Helman v hÖ mËt McElice.5.1. HÖ mËt Elgamal v c¸c logarithm rêi r¹c. HÖ mËt Elgamal ®−îc x©y dùng trªn b i to¸n logarithm rêi r¹c . Chóngta sÏ b¾t ®Çu b¨ng viÖc m« t¶ b i to¸n b i khi thiÕt lËp m«i tr−êng h÷u h¹nZp, p l sè nguyªn tè (h×nh 5.1) (Nhí l¹i r»ng nhãm nh©n Zp* l nhãm cyclicv phÇn tö sinh cña Zp* ®−îc gäi l phÇn tö nguyªn thuû). B i to¸n logarithm rêi r¹c trong Zp l ®èi t−îng trong nhiÒu c«ng tr×nhnghiªn cøu v ®−îc xem l b i to¸n khã nÕu p ®−îc chän cÈn thËn. Cô thÓkh«ng cã mét thuËt to¸n thêi gian ®a thøc n o cho b i to¸n logarithm rêi r¹c.§Ó g©y khã kh¨n cho c¸c ph−¬ng ph¸p tÊn c«ng ® biÕt p ph¶i cã Ýt nhÊt 150ch÷ sè v (p-1) ph¶i cã Ýt nhÊt mét thõa sè nguyªn tè lín. Lîi thÕ cña b ito¸n logarithm rêi r¹c trong x©y dùng hÖ mËt l khã t×m ®−îc c¸c logarithmrêi r¹c ,song b i to¸n ng−îc lÊy luü thõa l¹i cã thÓ tÝnh to¸n hiÖu qu¶ theothuËt to¸n b×nh ph−¬ng v nh©n. Nãi c¸ch kh¸c , luü thõa theo modulo p lh m mét chiÒu víi c¸c sè nguyªn tè p thÝch hîp. Elgamal ® ph¸t triÓn mét hÖ mËt kho¸ c«ng khai dùa trªn b i to¸nlogarithm rêi r¹c. HÖ thèng n y ®−îc tr×nh b y trªn h×nh 5.2. HÖ mËt n y l mét hÖ kh«ng tÊt ®Þnh v× b¶n m phô thuéc v o c¶ b¶nrâ x lÉn gi¸ trÞ ngÉu nhiªn k do Alice chän. Bëi vËy, sÏ cã nhiÒu b¶n m ®−îcm tõ cïng b¶n râ.H×nh 2.6 B i to¸n logarithm rêi r¹c trong Zp §Æc tr−ng cña b i to¸n: I = (p,α,β) trong ®ã p l sè nguyªn tè, α ∈ Zp l phÇn tö nguyªn thuû , β ∈ Zp* Môc tiªu: H y t×m mét sè nguyªn duy nhÊt a, 0 ≤ a ≤ p-2 sao cho: a α ≡ β (mod p) Ta sÏ x¸c ®Þnh sè nguyªn a b»ng logα β *H×nh 2.7 HÖ mËt kho¸ c«ng khai Elgamal trong Zp Cho p l sè nguyªn tè sao cho b i to¸n logarithm rêi r¹c trong Zp l * * khã gi¶i. Cho α ∈ Zp l phÇn tö nguyªn thuû.Gi¶ sö P = Zp , C = Zp* × Zp* . Ta ®Þnh nghÜa: K = {(p, α,a,β): β ≡ αa (mod p)} C¸c gi¸ trÞ p, α,β ®−îc c«ng khai, cßn a gi÷ kÝn Víi K = (p, α,a,β) v mét sè ngÉu nhiªn bÝ mËt k ∈ Zp-1, ta x¸c ®Þnh: ek (x,k) = (y1 ,y2 ) trong ®ã k y1 = α mod p y2 = xβk mod p * víi y1 ,y2 ∈ Zp ta x¸c ®Þnh: dk(y1 ,y2 ) = y2 (y1a )-1 mod p Sau ®©y sÏ m« t¶ s¬ l−îc c¸ch l m viÖc cña hÖ mËt Elgamal .B¶n râ x®−îc che dÊu b»ng c¸ch nh©n nã víi βk ®Ó t¹o y2 . Gi¸ trÞ αk còng ®−îc göi®i nh− mét phÇn cña b¶n m . Bob -ng−êi biÕt sè mò bÝ mËt a cã thÓ tÝnh ®−îcβk tõ αk . Sau ®ã anh ta sÏ th¸o mÆt n¹ b»ng c¸ch chia y2 cho βk ®Ó thu®−îc x.VÝ dô 5.1Cho p = 2579, α = 2, a = 765. Khi ®ã β = 2765 mod 2579 = 949B©y giê ta gi¶ sö Alice muèn göi th«ng b¸o x = 1299 tíi Bob. Gi¶ sö sè ngÉunhiªn k m c« chän l k = 853. Sau ®ã c« ta tÝnh y1 = 2853 mod 2579 = 435 y2 = 1299 × 949853 mod 2579 = 2396Khi ®ã Bob thu ®−îc b¶n m y = (435,2396), anh ta tÝnh x = 2396 × (435765)-1 mod 2579 = 1299§ã chÝnh l b¶n râ m Alice ® m ho¸.5.1.1. C¸c thuËt to¸n cho b i to¸n logarithm rêi r¹c. Trong phÇn n y ta xem r»ng p l sè nguyªn tè, α l phÇn tö nguyªnthuû theo modulo p. Ta thÊy r»ng p v α l c¸c sè cè ®Þnh. Khi ®ã b i to¸nlogarithm rêi r¹c cã thÓ ®−îc ph¸t biÓu d−íi d¹ng sau: t×m mét sè mò a duynhÊt, 0 ≤ a ≤ p-2 sao cho αa ≡β (mod p), víi β ∈ Zp* cho tr−íc. Râ r ng l b i to¸n logarithm rêi r¹c (DL) cã thÓ gi¶i b»ng mét phÐpt×m kiÕm vÐt c¹n víi thêi gian cì O(p) v kh«ng gian cì O(1) ( bá qua c¸cthõa sè logarithm). B»ng c¸ch tÝnh to¸n tÊt c¶ c¸c gi¸ trÞ αa cã thÓ v s¾p xÕpc¸c cÆp cã thø tù (a, αa mod p) cã l−u ý ®Õn c¸c t¹o ®é thø hai cña chóng, tacã thÓ gi¶i b i to¸n DL víi thêi gian cì O(1) b»ng O(p) phÐp tÝnh to¸n tr−ícv O(p) bé nhí ( vÉn bá qua c¸c thõa sè logarithm). ThuËt to¸n kh«ng tÇmth−êng ®Çu tiªn m chóng ta sÏ m« t¶ l thuËt to¸n tèi −u ho¸ thêi gian - bénhí cña Shanks.ThuËt to¸n ShanksH×nh 5.3. ThuËt to¸n Shanks cho b i ...