Lý thuyết mật mã - 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ùng nhiều trong nhiều thủ tục mật mã. Bởi vậy ta sẽ dμnh nhiều thời gian để thảo luậ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 Elgamal dự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...
Nội dung trích xuất từ tài liệu:
Lý thuyết mật mã - Chương 5 Vietebooks Nguyễn Hoàng Cương 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ïng nhiÒu trong nhiÒu thñ tôc mËt m·. Bëi vËy ta sÏ dµnh nhiÒu thêi gian ®Ó th¶o luË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 Elgamal dù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 log¶ithm rêi r¹c . Chóng ta 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¹n Zp, p lµ sè nguyªn tè ( h×nh 5.1) ( Nhí l¹i r»ng nhãm nh©n Zp* lµ nhãm cyclic vµ 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×nh nghiª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 150 ch÷ 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µi to¸n logarithm rêi r¹c trong x©y d−îng hÖ mËt lµ khã t×m ®−îc c¸c logarithm rê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¶ theo thuËt to¸n b×nh ph−¬ng vµ nh©n. Nãi c¸ch kh¸c , luü thõa theo modulo p lµ hµ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¸n logarithm 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¶n râ 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· ®−îc m· tõ cïng b¶n râ. Trang 1 Vietebooks Nguyễn Hoàng Cương 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: a K = {(p, α,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 k y2 = xβ mod p * víi y1 ,y2 ∈ Zp ta x¸c ®Þnh: a -1 dk(y1 ,y2 ) = y2 (y1 ) mod p Sau ®©y sÏ nm« t¶ s¬ l−îc c¸ch lµm viÖc cña hÖ mËt Elgamal .B¶n râ x k k ®−îc che dÊu b»ng c¸ch nh©n nã víi β ®Ó t¹o y2 . Gi¸ trÞ α 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 k k β tõ α . Sau ®ã anh ta sÏ th¸o mÆt n¹ b»ng c¸ch chia y2 cho β ®Ó thu ®−îc x. VÝ dô 5.1 Trang 2 Vietebooks Nguyễn Hoàng Cương Cho p = 2579, α = 2, a = 765. Khi ®ã β = 2765 mod 2579 = 949 B©y giê ta gi¶ sö Alice muèn göi th«ng b¸o x = 1299 tíi Bob. Gi¶ sö sè ngÉu nhiªn k mµ c« chän lµ k = 853. Sau ®ã c« ta tÝnh y1 = 2853 mod 2579 = 435 y2 = 1299 × 949853 mod 2579 = 2396 Khi ®ã 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ªn thuû theo modulo p. Ta thÊy r»ng p vµ α lµ c¸c sè cè ®Þnh. Khi ®ã bµi to¸n logarithm rêi ...