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 1', 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ả
AMBIENT/
Chủ đề:
Nội dung Text: Tìm hiểu hệ mật ELGAMAL và các LOGARITHM rời rạc phần 1
- Vietebooks Nguyễn Hoàng Cương
Ch−¬ng 5
Giáo trình tin học: Tìm hiểu hệ mật ELGAMAL và các LOGARITHM rời rạc
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ña c¸c cÆp nµy, ta sÏ thu ®−îc mét danh s¸ch L1
3. TÝnh βα-i mod p, 0 ≤ i ≤ m-1
4. S¾p xÕp m cÆp thø tù (i, βα-i mod p) cã l−u ý tíi c¸c to¹ ®é thø hai
cña c¸c cÆp ®−îc s¾p nµy, ta sÏ thu ®−îc mét danh s¸ch L2
5. T×m mét cÆp (j,y) ∈ L1 vµ mét cÆp (i,y) ∈ L2 ( tøc lµ mét cÆp cã t¹o
®é thø hai nh− nhau).
6. X¸c ®Þnh logαβ = mj + i mod (p-1)
7.
- NÕu cÇn, c¸c b−íc 1 vµ 2 cã thÓ tÝnh to¸n tr−íc ( tuy nhiªn, ®iÒu nµy
kh«ng ¶nh h−ëng tíi thêi gian ch¹y tiÖm cËn)
- TiÕp theo cÇn ®Ó ý lµ nÕu (j,y) ∈ L1 vµ (i,y) ∈ L2 th×
αmj = y = βα-i
Bëi vËy
αmj+i = β
nh− mong muèn. Ng−îc l¹i, ®èi víi β bÊt k× ta cã thÓ viÕt
logαβ = mj+i
trong ®ã 0 ≤ j,i ≤ m-1. V× thÕ phÐp t×m kiÕm ë b−íc 5 ch¾c ch¾n thµnh c«ng.
Cã thÓ ¸p dông thuËt to¸n nµy ch¹y víi thêi gian O(m) vµ víi bé nhí
cì O(m) ( bá qua c¸c thõa sè logarithm). Chó ý lµ b−íc 5 cã thÓ thùc hiÖn
mét c¸ch ( ®ång thêi ) qua tõng danh s¸ch L1 vµ L2.
Sau ®©y lµ mét vÝ dô nhá ®Ó minh ho¹.
VÝ dô 5.2.
Gi¶ sö p = 809 vµ ta ph¶i t×m log3525. Ta cã α = 3, β = 525 vµ m =
⎡√808⎤ = 29. Khi ®ã:
Trang 4
- Vietebooks Nguyễn Hoàng Cương
α29 mod 809 = 99
Tr−íc tiªn tÝnh c¸c cÆp ®−îc s¾p (j,99j mod 809) víi 0 ≤ j≤28. Ta nhËn
®−îc danh s¸ch sau:
(0,1) (1,99) (2,93) (3,308) (4,559)
(5,329) (6,211) (7,664) (8,207) (9,268)
(10,644) (11,654) (12,26) (13,147) (14,800)
(15,727) (16,781) (17,464) (18,314) (19,275)
(20,582) (21,496) (22,564) (23,15) (24,676)
(25,586) (26,575) (27,295) (28,81)
Danh s¸ch nµy sÏ ®−îc s¾p xÕp ®Ó t¹o L1.
Danh s¸ch thø hai chøa c¸c cÆp ®−îc s¾p (i,525×(3i)-1 mod 809), víi 0
≤ i ≤ 28. Danh s¸ch nµy gåm:
(0,525) (1,175) (2,328) (3,379) (4,396)
(5,132) (6,44) (7,554) (8,724) (9,511)
(10,440) (11,686) (12,768) (13,256) (14,,355)
(15,388) (16,399) (17,133) (18,314) (19,644)
(20,754) (21,496) (22,564) (23,15) (24,676)
(25,356) (26,658) (27,489) (28,163)
Sau khi s¾p xÕp danh s¸ch nµy, ta cã L2 .
B©y giê nÕu xö lý ®ång thêi qua c¶ hai danh s¸ch, ta sÏ t×m ®−îc ( 10,644)
trong L1 vµ (19,644) trong L2. B©y giê ta cã thÓ tÝnh
log3525 = 29×10+19
= 309
Cã thÓ kiÓm tra thÊy r»ng qu¶ thùc 3309 ≡ 525 (mod 809).
ThuËt to¸n Pohlig - Hellman.
ThuËt to¸n tiÕp theo mµ ta nghiªn cøu lµ thuËt to¸n Pohlig - Hellman. Gi¶ sö
pi lµ sè nguyªn tè ®Æc biÖt. Gi¸ trÞ a = logαβ ®−îc x¸c ®Þnh mét c¸ch duy
nhÊt theo modulo p-1. Tr−íc hÕt nhËn xÐt r»ng, nÕu cã thÓ tÝnh a mod pici víi
Trang 5
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
