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

Tiếp tục theo cách tương tự, có thể tính được các bội còn lại như sau: α = (2,7) 2α = (5,2) 3α = (8,3) 4α = (10,2) 5α = (3,6) 6α = (7,9) 7α = (7,2) 8α = (3,5) 9α = (10,9) 10α = (8,8) 11α = (5,9) 12α = (2,4) Do đó α = (2,7) thực sự là phần tử nguyên thuỷ.
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 6Vietebooks Nguyễn Hoàng Cương TiÕp tôc theo c¸ch t−¬ng tù, cã thÓ tÝnh ®−îc c¸c béi cßn l¹i nh− sau: α = (2,7) 2α = (5,2) 3α = (8,3) 4α = (10,2) 5α = (3,6) 6α = (7,9) 7α = (7,2) 8α = (3,5) 9α = (10,9) 10α = (8,8) 11α = (5,9) 12α = (2,4)Do ®ã α = (2,7) thùc sù lµ phÇn tö nguyªn thuû. Mét ®−êng cong elliptic x¸c ®Þnh trªn Zp (p lµ sè nguyªn tè >3) sÏ cãkho¶ng p ®iÓm. ChÝnh x¸c h¬n, theo mét ®Þnh lý næi tiÕng cña Hasse, sè c¸c®iÓm trªn E ( kÝ hiÖu lµ #E) th¶o m·n bÊt ®¼ng thøc sau: p + 1 − 2 p ≤# E ≤ p + 1 + 2 p ViÖc tÝnh to¸n chÝnh x¸c gi¸ trÞ cña #E cã khã h¬n nh−ng ®· cã métthuËt to¸n h÷u hiÖu do Schoof ®−a ra gióp tÝnh to¸n dÔ dµn h¬n.( NghÜa h÷uhiÖu ë ®©y ®−îc hiÓu lµ thêi gian ch¹y cña thuËt to¸n lµ thêi gian ®a thøctheo log p. ThuËt to¸n Schoof cã thêi gian ch¹y kho¶ng O((log p)8) phÐp tÝnhtrªn bÝt vµ cã thÓ thùc hiÖn ®èi víi c¸c sè nguyªn tè p cã vµi tr¨m ch÷ sè). B©y giê gi¶ sö cã thÓ tÝnh ®−îc #E. VÊn ®Ò tiÕp theo lµ ph¶i t×m métnhãm con cyclic trong E sao cho bµi to¸n DL trong nã lµ khã. Bëi vËy taph¶i biÕt mét vµi ®iÒu vÒ cÊu tróc cña nhãm E. §Þnh lý sau ®©y cung cÊp métth«ng tin ®¸ng kÓ vÒ cÊu tróc nhãm cña E.§Þnh lý 5.1 Cho E lµ mét ®−êng cong elliptic trªn Zp, p lµ sè nguyªn tè > 3. Khi®ã, tån t¹i c¸c sè nguyªn n1 vµ n2 sao cho E lµ ®¼ng cÊu víi Zn1×Zn2. Ngoµira n2 | n1 vµ n2 | (p-1). Bëi vËy nÕu cã thÓ tÝnh ®−îc c¸c sè n1 vµ n2 th× ta sÏ biÕt r»ng E cãmét nhãm con cyclic ®¼ng cÊu víi Zn1 vµ cã thÓ dïng E ®Ó thiÕt lËp mét hÑemËt Elgamal. Chó ý lµ nÕu n2 = 1 th× E lµ mét nhãm cyclic. Còng vËy, nÕu #E lµ métsè nguyªn tè hoÆc lµ tÝch cña c¸c sè nguyªn tè kh¸c nhau th× E lµ nhãmcyclic cã chØ sè nhãm cyclic. C¸c thuËt to¸n Shanks vµ Pohlig - Hellman cã thÓ ¸p dông cho bµito¸n rêi r¹c trªn ®−êng cong Elliptic song tíi nay vÉn ch−a cã mét thuËt to¸n Trang 26Vietebooks Nguyễn Hoàng CươngthÝch hîp cho ph−¬ng ph¸p tÝnh chØ sè ®èi víi c¸c ®−êng cong Elliptic.Tuynhiªn, ®· cã mét ph−¬ng ph¸p khai th¸c ®¼ng cÊu mét c¸ch t−êng minh gi÷ac¸c ®−êng cong Elliptic trong tr−êng h÷u h¹n. Ph−¬ng ph¸p nµy dÉn ®Õn c¸cthuËt to¸n h÷u hiÖu ®èi víi mét sè líp c¸c ®−êng cong Elliptic. Kü thuËt nµydo Menezes, Okamoto vµ Vanstone ®−a ra vµ cã thÓ ¸p dông cho mét sètr−êng hîp riªng trong mét líp ®Æc biÖt c¸c ®−êng cong Elliptic (®−îc gäi lµc¸c ®−êng cong siªu biÕn, chóng ®· ®−îc kiÕn nghÞ sö dông trong c¸c hÖthèng mËt m·). Tuy nhiªn, nÕu tr¸nh c¸c ®−êng cong siªu biÕn th× l¹i xuÊthiÖn mét ®−êng cong Elliptic cã mét nhãm con cyclic cì 2160 , ®−êng congnµy sÏ cho phÐp thiÕt lËp an toµn mét hÖ mËt miÔn lµ bËc cña nhãm con ph¶ilµ béi cña Ýt nhÊt mét thõa sè nguyªn tè lín ( nh»m b¶o vÖ hÖ mËt kháiph−¬ng ph¸p tÊn c«ng cña Pohlig - Hellman). XÐt mét vÝ dô vÒ phÐp m· Elgamal sö dông ®−êng cong elliptic nªutrªn vÝ dô 5.7.VÝ dô 5.8. Gi¶ sö α = (2,7) vµ sè mò mËt cña Bob lµ a = 7. Bëi vËy: β = 7α = (7,2)PhÐp m· ho¸ thùc hiÖn nh− sau eK(x,k) = (k(2,7),x+k(7,2))trong ®ã x∈E vµ 0 ≤ k ≤ 12 cßn phÐp gi¶i m· thùc hiÖn nh− sau: dK(y1,y2) = y2-7y1 Gi¶ sö Alice muèn m· b¶n tin x = (10,9) ( lµ mét ®iÓm trªn E). NÕu c«chän gi¸ trÞ ngÉu nhiªn k=3 th× c« tÝnh y1 = 3(2,7) = (8,3)vµ y2 = (10,9) + 3(7,2) = (10,9) + (3,5) = (10,2) Bëi vËy, y = ((8,3),(10,2)). B©y giê nÕu Bob nhËn ®−îc b¶n m· y th×anh ta gi¶i m· nh− sau: x = (10,2) - 7(8,3) = (10,2) - (3,5) = (10,2) + (3,6) = (10,9)§©y chÝnh lµ b¶n râ ®óng. Trªn thùc tÕ cã mét sè khã kh¨n khi ¸p dông hÖ mËt Elgamal trªn®−êng cong Elliptic. HÖ thèng nµy ®−îc ¸p dông trong Zp ( hoÆc trongGF(pn) víi n > 1) sÏ cã hÖ sè më réng b¶n tin lµ 2. ViÖc ¸p dông ®−êng cong Trang 27Vietebooks Nguyễn Hoàng CươngElliptic sÏ cã thõa sè më réng kho¶ng 4 lÇn. §iÒu nµy lµ do cã xÊp xØ p b¶nrâ, nh−ng mçi b¶n m· l¹i gæm bèn phÇn tö cña tr−êng. Mét trë ng¹i lµ kh«nggian b¶n râ chøa c¸c ®iÓm trªn ®−êng cong E vµ kh«ng cã ph−¬ng ph¸p nµox¸c ®Þnh t−êng minh c¸c ®iÓm trªn E Menezes vµ Vanstone ®· t×m ra mét ph−¬ng ¸n hiÖu qu¶ h¬n. theoph−¬ng ¸n nµy ®−êng cong Elliptic dïng ®Ó che dÊu, cßn c¸c b¶n râ vµ b¶nm· hîp lÖ lµ c¸c cÆp ®−îc s¾p tïy ý c¸c phÇn tö kh¸c kh«ng cña tr−êng( tøclµ chóng kh«ng ®ßi hái ph¶i lµ c¸c ®iÓm trªn E). §iÒu nµy s ...