Tìm hiểu hệ mật ELGAMAL và các LOGARITHM rời rạc phần 4

Tham khảo tài liệu tìm hiểu hệ mật elgamal và các logarithm rời rạc phần 4, công nghệ thông tin, an ninh - bảo mật phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Tìm hiểu hệ mật ELGAMAL và các LOGARITHM rời rạc phần 4Vietebooks Nguyễn Hoàng Cương®iÒu nµy kÐo theo xi+1 = L2(βi) , i≥0V× r»ng xi+1 = L2(β) nªn thuËt to¸n lµ ®óng. C¸c chi tiÕt dµnh cho ®éc gi¶xem xÐt.5.2. Tr−êng h÷u h¹n vµ c¸c hÖ thèng ®−¬ng cong elliptic. Chóng ta ®· dµnh thêi gian ®¸ng kÓ ®Ó xÐt bµi to¸n logarithm rêi r¹c(DL) vµo viÖc ph©n tÝch sè. Ta sÏ cßn trë l¹i hai bµi to¸n nµy trong c¸c lo¹ihÖ mËt vµ c¸c giao thøc m· kh¸c nhau. Bµi to¸n DL ®· ®−îc nghiªn cøutrong tr−¬ng h÷u h¹n Zp, tuy nhiªn viÖc xÐt bµi to¸n nµy theo c¸c thiÕt lËpkh¸c nhau còng rÊt cã Ých vµ lµ chñ ®Ò cña phÇn nµy. HÖ mËt Elgamal cã thÓ ®−îc ¸p dông trong mét nhãm bÊt k× mµ bµito¸n DL lµ khã gi¶i. Ta ®· dïng nhãm nh©n Zp* tuy nhiªn c¸c nhãm kh¸ccòng lµ nh÷ng øng cö viªn thÝch hîp. Tr−íc hÕt ta ph¸t biÓu bµi to¸n DLtrong mét nhãm h÷u h¹n nãi chung G (h÷u h¹n) vµ ë ®ã kÝ hiÖu phÐp lÊynhãm lµ dÊu ο. D¹ng bµi to¸n tæng qu¸t ho¸ nh− vËy tr×nh bµi trªn h×nh 5.8. DÔ dµng x¸c ®Þnh mét hÖ mËt Elgamal trong nhãm con H theo c¸cht−¬ng tù ®· m« t¶ trong Zp* vµ ®−îc tr×nh bµy trªn h×nh 5.9. Chó ý r»ng phÐpm· ho¸ yªu cÇu dïng sè nguyªn k ngÉu nhiªn sao cho 0 ≤ k ≤ | H | - 1. Tuynhiªn, nÕu Alice kh«ng biÕt cÊp cña nhãm con H th× c« ta cã thÓ t¹o mét sènguyªn k tho¶ m·n 0 ≤ k ≤ | G | -1, khi ®ã sÏ kh«ng cã bÊt k× sù thay ®æi nµotrong qu¸ tr×nh m· vµ gi¶i m·. Còng cÇn chó ý lµ nhãm G kh«ng ph¶i lµnhãm Aben (Tuy H vÉn lµ nhãm Aben v× nã lµ nhãm cyclic). Trang 16Vietebooks Nguyễn Hoàng CươngH×nh 5.8. Bµi to¸n logarithm rêi r¹c trong (G,0) §Æc tr−ng cña bµi to¸n: I = (G, α, β), trong ®ã G lµ mét nhãm h÷u h¹n víi phÐp lÊy nhãm o , α ∈ G vµ β ∈ H, trong ®ã H = { αi : i ≥ 0} lµ mét nhãm con sinh bëi α. Môc tiªu: T×m mét sè nguyªn duy nhÊt a sao cho 0 ≤ a ≤ | H | -1 vµ αa = β, víi kÝ hiÖu αa cã nghÜa lµ α o . . . o α (a lÇn) Ta sÏ kÝ hiÖu sè nguyªn a nµy b»ng logαβB©y giê ta sÏ trë l¹i bµi to¸n DL tæng qu¸t ho¸ . Nhãm con H ®−îc sinh bëiphÇn tö α tuú ý ∈ G dÜ nhiªn ph¶i lµ nhãm con cyclic cÊp | H |. Bëi vËy, d¹ngbÊt k× cña bµi to¸n theo mét nghÜa nµo ®ã ®Òu t−¬ng ®−¬ng víi bµi to¸n DLtrong mét nhãm cyclic. Tuy nhiªn, ®é khã cña bµi to¸n DL d−êng nh− phôthuéc vµo c¸ch biÓu diÔn nhãm ®−îc dïng. XÐt mét vÝ dô vÒ c¸ch biÓu diÔn mµ víi nã, bµi to¸n logarithm rêi r¹crÊt dÔ gi¶i. XÐt nhãm céng cyclic Zn vµ gi¶ sö UCLN(α,n) = 1, bëi vËy α lµphÇn tö sinh cña Zn. V× phÐp to¸n trong nhãm lµ céng theo modulo n nªnphÐp lÊy mò sÏ lµ nh©n víi a theo modulo n. V× thÕ trong c¸ch x©y dùng nµy,bµi to¸n logarithm rêi r¹c sÏ lµ t×m sè nguyªn a sao cho. αa ≡ β (mod n)V× UCLN(α,n) = 1 nªn α cã phÇn tö nghÞch ®¶o nh©n theo modulo n vµ ta cãthÓ dÔ dµng tÝnh α-1 mod n b»ng thuËt to¸n Euclide. Sau ®ã cã thÓ gi¶i ®Ó t×ma vµ nhËn ®−îc logαβ = β α-1 mod n Trang 17Vietebooks Nguyễn Hoàng CươngH×nh 5.9. HÖ mËt kho¸ c«ng khai Elgamal tæng qu¸t Gi¶ sö G lµ mét nhãm h÷u h¹n cã phÐp lÊy nhãm o. Gi¶ sö α ∈ G lµ mét phÇn tö sao cho bµi to¸n DL trong H lµ khã; ë ®©y H = {αi, i ≥ 0} lµ mét nhãm con sinh bëi α. §Æt P = G, C = G×G vµ ®Þnh nghÜa: K = {(G, α, a, β) : β = αa} C¸c gi¸ trÞ α, β c«ng khai, cßn a ®−îc gi÷ kÝn. Víi K = (G, α, a, β) vµ víi mét sè ngÉu nhiªn bÝ mËt k ∈ Z|H| ta x¸c ®Þnh: eK(x,k) = (y1,y2) y 1 = αk trong ®ã y2 = (x o βk) vµ Víi b¶n m· y = (y1,y2) ta x¸c ®Þnh: dK(y) = y2 o (y1a)-1 ë phÇn trªn ta ®· nghiªn cøu bµi to¸n DL trong nhãm nh©n Zp* v¬i p lµlµ sè nguyªn tè . Nhãm nµy lµ nhãm cyclic cÊp p-1 vµ bëi vËy nã ®¼ng cÊuvíi nhãm céng Zp-1. Theo th¶o luËn ë trªn, ta ®· biÕt c¸ch tinh c¸c logarithmrêi r¹c mét c¸ch hiÖu qu¶ trong nhãm céng nµy. §iÒu ®ã gîi ý kh¶ n¨ng gi¶ibµi to¸n DL trong Zp* b»ng c¸ch quy nã vÒ bµi to¸n gi¶i ®−îc dÔ dµng trongZp-1. Ta h·y xem xÐt ®iÒu nµy ®−îc thùc hiÖn nh− thÕ nµo?. Khi nãi r»ng,(Zp , ×) lµ ®¼ng cÊu víi (Zp-1, +) cã nghÜa lµ cã mét song ¸nh : * φ : Zp* Zp-1 φ(xy mod p) = (φ(x) + φ(y)) mod (p-1)sao cho§iÒu ®ã kÐo theo: φ(αa mod p) = a φ(α) mod (p-1)Bëi vËy β ≡ αa mod p ⇔ a φ(α) ≡ φ(β) (mod p-1)Do ®ã nÕu t×m a theo m« t¶ ë trªn, ta cã: logαβ = φ(β) (φ(α))-1 mod (p-1) B©y giê, nÕu cã mét ph−¬ng ph¸p h÷u hiÖu ®Ó tÝnh phÐp ®¼ng cÊu φ th×ta sÏ cã mét thuËt to¸n h÷u hiÖu ®Ó tÝnh c¸c logarithm rêi r¹c trong Zp*. Khãkh¨n ë ®©y lµ kh«ng cã mét ...