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

Vietebooks Nguyễn Hoàng Cương

Trang 26

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:

ViÖc tÝnh to¸n chÝnh x¸c gi¸ trÞ cña #E cã khã h¬n nh−ng ®· cã mét

thuË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÷u

hiÖu ë ®©y ®−îc hiÓu lµ thêi gian ch¹y cña thuËt to¸n lµ thêi gian ®a thøc

theo log p. ThuËt to¸n Schoof cã thêi gian ch¹y kho¶ng O((log p)8

) phÐp tÝnh

trª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ét

nhãm con cyclic trong E sao cho bµi to¸n DL trong nã lµ khã. Bëi vËy ta

ph¶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ét

th«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µi

ra 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Ñe

mË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ét

sè nguyªn tè hoÆc lµ tÝch cña c¸c sè nguyªn tè kh¸c nhau th× E lµ nhãm

cyclic cã chØ sè nhãm cyclic.

C¸c thuËt to¸n Shanks vµ Pohlig - Hellman cã thÓ ¸p dông cho bµi

to¸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

p + 1− 2 p ≤#E ≤ p + 1+ 2 p