Các hệ thống khóa công khai thác phần 1

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ã.
Nội dung trích xuất từ tài liệu:
Các hệ thống khóa công khai thác phần 1 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 r¹c cã thÓ ®−îc ph¸t biÓu d−íi d¹ng sau: t×m mét sè mò a duy nhÊ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Ðp t×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¸c thõ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Õp c¸c cÆp cã thø tù (a, αa mod p) cã l−u ý ®Õn c¸c t¹o ®é thø hai cña chóng, ta cã 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−íc vµ O(p) bé nhí ( vÉn bá qua c¸c thõa sè logarithm). ThuËt to¸n kh«ng tÇm th−ê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 Shanks Trang 3 Vietebooks Nguyễn Hoàng Cương H×nh 5.3. ThuËt to¸n Shanks cho bµi to¸n DL. 1. TÝnh αmj mod p, 0 ≤ j ≤ m-1 2. S¾p xÕp m cÆp thø tù ( j,αmj mod p) cã l−u ý tíi c¸c t¹o ®é thø hai cñ ...