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

Chia sẻ: AFASFAF FSAFASF | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

94
lượt xem 16
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

Vietebooks Nguyễn Hoàng Cương mç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 qc 0 ≤ 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 + qcs ví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 6
Vietebooks 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íi ví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 = β α-ao vµ kÝ hiÖu x1 = logαβ1 mod qc DÔ dµng thÊy r»ng V× thÕ dÉn ®Õn Nh− vËy ta sÏ tÝnh β1(p-1)/q2 mod p vµ råi t×m i sao cho Khi ®ã 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µy c-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. Trong thuË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 7
Vietebooks Nguyễn Hoàng Cương ThuËt to¸n tÝnh c¸c gi¸ trÞ a0, . . ., ac-1 trong ®ã logαβ mod qc H×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 +1 Chó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.71 Gi¶ sö α = 2 vµ β = 18. Ta ph¶i x¸c ®Þnh a = log218. Tr−íc tiªn tÝnh a mod 4 rå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 29 vµ = 214 mod 29 = 28 TiÕp theo δ = β28/2 mod 29 = 1814 mod 29 = 28 V× a0 = 1. TiÕp theo ta tÝnh: β1 = β0α-1 mod 29 =9 vµ β128/4 mod 29 = 97 mod 29 = 28 Trang 8
Vietebooks Nguyễn Hoàng Cương V× γ1 ≡ 28 mod 29 Ta 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/7 vµ = 24 mod 29 = 16. γ 2 = 24 Sau ®ã tÝnh: γ3 = 7 γ 4 = 25 Bë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õa sè 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µy chØ 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ña phÇ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Ï x©y dùng C = B +10 ®ång d− thøc theo modulo p nh− sau: αxj ≡ p1a1jp2a2j. . . pBaBj(mod p) 1 ≤ j ≤ C. CÇn ®Ó ý r»ng, c¸c ®ång d− nµy cã thÓ viÕt t−¬ng ®−¬ng nh− sau: xj ≡ a1jlogαp1+ . . . + aBjlogαpB (mod p-1) 1 ≤ j ≤ C. C ®ång d− thøc ®−îc cho theo B gi¸ trÞ logαpi (1 ≤ i ≤ B) ch−a biÕt. Ta hy väng r»ng, cã mét nghiÖm duy nhÊt theo modulo p-1. NÕu ®óng nh− vËy th× cã thÓ tÝnh c¸c logarithm cña c¸c phÇn tö theo c¬ së nh©n tö. Trang 9
Vietebooks Nguyễn Hoàng Cương Lµm thÕ nµo ®Ó t¹o c¸c ®ång d− thøc cã d¹ng mong muèn?. Mét ph−¬ng ph¸p s¬ ®¼ng lµ chän mét sè ngÉu nhiªn x, tÝnh αx mod p vµ x¸c ®Þnh xem liÖu αx mod p cã tÊt c¶ c¸c thõa sè cña nã trong B hay kh«ng. (VÝ dô b»ng c¸ch chia thö). B©y giê gi¶ sö r»ng ®· thùc hiÖn xong b−íc tiªn tÝnh to¸n, ta sÏ tÝnh gi¸ trÞ mong muèn logαβ b»ng thuËt to¸n x¸c suÊt kiÓu Las Vegas. Chän mét sè ngÉu nhiªn s ( 1 ≤ s ≤ p-2) vµ tÝnh : γ = β αs mod p B©y giê thö ph©n tÝch γ theo c¬ së B. NÕu lµm ®−îc ®iÒu nµy th× ta tÝnh ®−îc ®ång d− thøc d¹ng: βαs = p1c1p2c2. . . pBcB (mod p) §iÒu ®ã t−¬ng ®−¬ng víi logαβ + s ≡ c1logαp1+ . . . + cBlogαpB ( mod p-1) V× mäi gi¸ trÞ ®Òu ®¶ biÕt trõ gi¸ trÞ logαβ nªn cã thÓ dÔ dµng t×m ®−îc logαβ. Sau ®©y lµ mét vÝ dô minh ho¹ 2 b−íc cña thuËt to¸n. VÝ dô 5.4. Gi¶ sö p =10007 vµ α = 5 lµ mét phÇn tö nguyªn thuû ®−îc dïnglµm c¬ së cña c¸c logarithm theo modulo p. Gi¶ sö lÊy B = {2, 3, 5, 7} lµm c¬ së. HiÓn nhiªn lµ log55 = 1 nªn chØ cã 3 gi¸ trÞ log cña c¸c phÇn tö trong c¬ së cÇn ph¶i x¸c ®Þnh. §Ó lµm vÝ dô, chän mét vµi sè mò "may m¾n" sau: 4063, 5136 vµ 985. Víi x = 4063, ta tÝnh 54063 mod 10007 = 2×3×7 øng víi ®ång d− thøc log52 + log53 + log57 ≡ 4063 ( mod 10006). T−¬ng tù, v× 55136 mod 10007 = 54 = 2×33 59865 mod 10007 = 189 = 33×7 vµ ta t×m ®−îc hai ®ång d− thøc n÷a: log52 + 3log53 ≡ 5136 ( mod 10006) 3log53 + log57 ≡ 9865 ( mod 10006) Trang 10