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

Vietebooks Nguyễn Hoàng Cương

Trang 16

®iÒu nµy kÐo theo

xi+1 = L2(βi

) , i≥0

V× 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¹i

hÖ mËt vµ c¸c giao thøc m· kh¸c nhau. Bµi to¸n DL ®· ®−îc nghiªn cøu

trong 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Ëp

kh¸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µi

to¸n DL lµ khã gi¶i. Ta ®· dïng nhãm nh©n Zp

*

tuy nhiªn c¸c nhãm kh¸c

cò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 DL

trong mét nhãm h÷u h¹n nãi chung G (h÷u h¹n) vµ ë ®ã kÝ hiÖu phÐp lÊy

nhã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¸ch

t−¬ng tù ®· m« t¶ trong Zp

*

vµ ®−îc tr×nh bµy trªn h×nh 5.9. Chó ý r»ng phÐp

m· ho¸ yªu cÇu dïng sè nguyªn k ngÉu nhiªn sao cho 0 ≤ k ≤ | H | - 1. Tuy

nhiª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µo

trong 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).