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

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 2, 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 2Vietebooks Nguyễn Hoàng Cươngmçi i, 1 ≤ i ≤ k, th× cã thÓ tÝnh a mod (p-1) theo ®Þnh lý phÇn d− China. §Óthùc hiÖn diÒu ®ã ta gi¶ sö r»ng q lµ sè nguyªn tè. p-1 ≡ 0 (mod qc) p-1 ≡ 0 (mod qc+1)Ta sÏ chØ ra c¸ch tÝnh gi¸ trÞ x = a mod qc0 ≤ x ≤ qc-1. Ta cã thÓ biÓu diÔn x theo c¬ sè q nh− sau:trong ®ã 0 ≤ ai ≤ q-1 víi 0 ≤ i ≤ c-1. Còng cã thÓ biÓu diÔn nh− sau: a = x + qcsvíi s lµ mét sè nguyªn nµo ®ã. B−íc ®Çu tiªn cña thuËt to¸n tÝnh a0. KÕt qu¶ chÝnh ë ®©y lµ: β(p-1)/q ≡ α(p-1)a0/q(mod p)§Ó thÊy râ ®iÒu ®ã cÇn chó ý r»ng:§iÒu nµy ®ñ ®Ó cho thÊy:KÕt qu¶ nµy ®óng khi vµ chØ khi:Tuy nhiªn Trang 6Vietebooks Nguyễn Hoàng Cương§ã chÝnh lµ ®iÒu cÇn chøng minh. Do ®ã ta sÏ b¾t ®Çu b»ng viÖc tÝnh β(p-1)/q mod p. NÕu β(p-1)/q ≡ 1 (mod p)th× a0=0. Ng−îc l¹i chóng ta sÏ tÝnh liªn tiÕp c¸c gi¸ trÞ: γ = α(p-1)/q mod p, γ2 mod p,. . ., γi ≡ β(p-1)/q (mod p).cho tíivíi mét gi¸ trÞ i nµo ®ã. Khi ®iÒu nµy x¶y ra ta cã a0 =i. B©y giê nÕu c = 1 th× ta ®· thùc hiÖn xong. Ng−îc l¹i, nÕu c > 1 th×ph¶i tiÕp tôc x¸c ®Þnh a1. §Ó lµm ®iÒu ®ã ta ph¶i x¸c ®Þnh β1 = β α-aovµ kÝ hiÖu x1 = logαβ1 mod qcDÔ dµng thÊy r»ngV× thÕ dÉn ®ÕnNh− vËy ta sÏ tÝnh β1(p-1)/q2 mod p vµ råi t×m i sao choKhi ®ã a1 = i. NÕu c =2 th× c«ng viÖc kÕt thóc; nÕu kh«ng, ph¶i lÆp l¹i c«ng viÖc nµyc-2 lÇn n÷a ®Ó t×m a2,. . .,ac-1. H×nh 5.4 lµ m« t¶ gi¶i m· cña thuËt to¸n Pohlig - Hellman. TrongthuËt to¸n nµy, α lµ phÇn tö nguyªn thuû theo modulo p, q lµ sè nguyªn tè . p-1 ≡ 0 (mod qc)vµ p-1 ≡ 0 (mod qc+1) Trang 7Vietebooks Nguyễn Hoàng CươngThuËt to¸n tÝnh c¸c gi¸ trÞ a0, . . ., ac-1 trong ®ãlogαβ mod qcH×nh 5.4. ThuËt to¸n Pohlig - Hellman ®Ó tÝnh logαβ mod qc. 1. TÝnh γ = α(p-1)/q mod p víi 0 ≤ i ≤ q-1 2. §Æt j = 0 vµ βj = β 3. While j ≤ c-1 do TÝnh δ = βj(p-1)/q j+1 mod p 4. T×m i sao cho δ = γi 5. 6. aj = i βj+1 = βj α-aj qj mod p 7. 8. j = j +1Chóng ta minh ho¹ thuËt to¸n Pohlig - Hellman (P - H) qua mét vÝ dô nhá.VÝ dô 5.3 Gi¶ sö p=29; khi ®ã n = p-1 = 28 = 22.71Gi¶ sö α = 2 vµ β = 18. Ta ph¶i x¸c ®Þnh a = log218. Tr−íc tiªn tÝnh a mod 4råi tÝnh a mod 7.Ta sÏ b¾t ®Çu b»ng viÖc ®Æt q = 2, c = 2. Tr−íc hÕt γ0 = 1 γ1 = α28/2 mod 29vµ = 214 mod 29 = 28TiÕp theo δ = β28/2 mod 29 = 1814 mod 29 = 28V× a0 = 1. TiÕp theo ta tÝnh: β1 = β0α-1 mod 29 =9vµ β128/4 mod 29 = 97 mod 29 = 28 Trang 8Vietebooks Nguyễn Hoàng CươngV× γ1 ≡ 28 mod 29Ta cã a1 = 1. Bëi vËy a ≡ 3 ( mod 4). TiÕp theo ®Æt q = 7 vµ c = 1, ta cã β28/7 mod 29 = 184 mod 29 = 25 γ1 = α mod 29 28/7vµ = 24 mod 29 = 16. γ 2 = 24Sau ®ã tÝnh: γ3 = 7 γ 4 = 25Bëi vËy a0 = 4 vµ a ≡ 4 ( mod 7) Cuèi cïng gi¶i hÖ ph−¬ng tr×nh a ≡ 3 ( mod 4) a ≡ 4 ( mod 7)b»ng ®Þnh lý phÇn d− China, ta nhËn ®−îc a ≡ 11( mod 28). §iÒu nµy cãnghÜa lµ ®· tÝnh ®−îc log218 trong Z29 lµ 11.Ph−¬ng ph¸p tÝnh to¸n chØ sè. Ph−¬ng ph¸p tÝnh chØ sè kh¸ gièng víi nhiÒu thuËt to¸n ph©n tÝch thõasè tèt nhÊt. Trong phÇn nµy sÏ xÐt tãm t¾t vÒ ph−¬ng ph¸p. Ph−¬ng ph¸p nµychØ dïng mét c¬ së nh©n tö lµ tËp B chøa c¸c sè nguyªn tè nhá. Gi¶ sö B ={p1,p2,. . ., pB}. B−íc ®Çu tiªn ( b−íc tiÒn xö lý) lµ t×m c¸c logarithm cña B sènguyªn tè trong c¬ së nh©n tö. B−íc thø hai lµ tÝnh c¸c logarithm rêi r¹c cñaphÇn tö β b»ng c¸ch dïng c¸c hiÓu biÕt vÒ c¸c log cña c¸c phÇn tö trong c¬së. Trong qu¸ tr×nh tiÒn xö lý, ta s ...