Các hệ thống khóa công khai thác phần 3
Số trang: 5
Loại file: pdf
Dung lượng: 136.08 KB
Lượt xem: 14
Lượt tải: 0
Xem trước 2 trang đầu tiên của tài liệu này:
Thông tin tài liệu:
Đã có nhiều nghiên cứu phân tích mò mẫm nhiều kiểu thuật toán khác nhau. Với giả thiết hợp lý, Thời gian chạy tiệm cận của giai đoạn tiền tính toán này cỡ và thời gian để tính một giá trị logarithm rời rạc riêng là khoảng.
Nội dung trích xuất từ tài liệu:
Các hệ thống khóa công khai thác phần 3Vietebooks Nguyễn Hoàng Cương B©y giê ta cã 3 ®ång d− thøc theo 3 gi¸ trÞ log ch−a biÕt. Gi¶i c¸cph−¬ng tr×nh ®ång d− nµy, ta cã log52 = 6578, log53 = 6190, log57 = 1301. B©y giê gi¶ sö ta cÇn t×m log59451, ta chän sè mò ngÉu nhiªns=7736 vµ tÝnh: 9451×57736 mod 10007 = 8400V× 8400 = 24315271 c¸c thõa sè trong B nªn ta nhËn ®−îc: log59451 = 4log52 + log53 + log55 + log57 - s mod 10006 = 4×6578 + 6190 + 2×1 + 1310 - 7736 mod 10006 = 6057.KiÓm tra l¹i ta thÊy r»ng 56057 ≡ 9451 ( mod 10007). §· cã nhiÒu nghiªn cøu ph©n tÝch mß mÉm nhiÒu kiÓu thuËt to¸n kh¸cnhau. Víi gi¶ thiÕt hîp lý, Thêi gian ch¹y tiÖm cËn cña giai ®o¹n tiÒn tÝnhto¸n nµy cìvµ thêi gian ®Ó tÝnh mét gi¸ trÞ logarithm rêi r¹c riªng lµ kho¶ngH×nh 5.5. BÝt thø i cña logarithm rêi r¹c. B¶n chÊt cña bµi to¸n: I = (p, α, β, i) trong ®ã p lµ sè nguyªn tè , α∈Zp* lµ phÇn tö nguyªn thuû, β ∈ Zp* vµ i lµ mét sè nguyªn sao cho 1 ≤ i ≤ ⎣log2(p-1)⎦. Môc tiªu:TÝnh Li(β) lµ bÝt thÊp nhÊt thø i cña logαβ. (víi α vµ p cho tr−íc)5.1.2. §é b¶o mËt t−ng bÝt cña c¸c logarithm rêi r¹c. B©y giê ta xem xÐt vÊn ®Ò vÒ th«ng tin bé phËn cña c¸c logarithm rêir¹c vµ thö xem viÖc tÝnh c¸c bÝt riªng cña c¸c logarithm rêi r¹c lµ khã hay dÔ.Cô thÓ , xÐt bµi to¸n tr×nh bµy trªn h×nh 5.5. Bµi to¸n nµy ®−îc gäi lµ bµi to¸nvÒ bÝt thø i. Trang 11Vietebooks Nguyễn Hoàng Cương Tr−íc tiªn, ta sÏ chØ ra r»ng, bÝt thÊp nhÊt cña c¸c logarithm rêi r¹c rÊtdÔ tÝnh to¸n. Nãi c¸ch kh¸c, nÕu i = 1 th× bµi to¸n vÒ bÝt thø i cã thÓ gi¶i®−îc mét c¸ch hiÖu qu¶. §iÒu nµy rót ra tõ tiªu chuÈn Euler liªn quan ®ÕnthÆng d− b×nh ph−¬ng theo modulo p, víi p lµ sè nguyªn tè . XÐt ¸nh x¹ f: Zp* Zp* ®−îc ®Þnh nghÜa nh− sau: f(x) = x2 mod pNÕu kÝ hiÖu QR(p) lµ tËp c¸c thÆng d− b×nh ph−¬ng theo modulo p th× QR(p) = { x2 mod p : x ∈ Zp*}Tr−íc tiªn ta thÊy r»ng, f(x) = f(p-x). TiÕp theo xÐt thÊy: w2 ≡ x2 mod pkhi vµ chØ khi p | (w-x)(w+x)®iÒu nµy sÏ x¶y ra khi vµ chØ khi w ≡ ± x mod p. Tõ ®©y rót ra: | f-1(y) | = 2víi mäi y ∈ QR(p) vµ bëi vËy: | QR(p) = (p-1)/2§iÒu ®ã cã nghÜa lµ cã ®óng mét n÷a c¸c thÆng d− trong Zp* lµ c¸c thÆng d−b×nh ph−¬ng vµ mét n÷a kh«ng ph¶i. B©y gië gi¶ sö r»ng, α lµ mét phÇn tö nguyªn thuû cña Zp* . Khi ®ãαa∈QR(p) nÕu a ch½n. V× (p-1)/2 phÇn tö α0 mod p, α2 mod p,. . .,αp-3 mod p®Òu lµ c¸c phÇn tö kh¸c nhau nªn: QR(p) = {α2i mod p: 0 ≤ i ≤ (p-3)/2}Bëi vËy, β lµ thÆng d− b×nh ph−¬ng khi vµ chØ khi logαβ lµ ch½n, tøc khi vµchØ khi L1(β) = 0. Tuy nhiªn theo tiªu chuÈn Euler β lµ thÆng d− b×nh ph−¬ngkhi vµ chØ khi β(p-1)/2 ≡ 1 (mod p) Trang 12Vietebooks Nguyễn Hoàng CươngNh− vËy, ta ®· cã c«ng thøc h÷u hiÖu sau ®Ó tÝnh L1(β): nÕu β(p-1)/2 ≡ 1( mod p) 0 L1(β)= 1 trong c¸c tr−êng hîp cßn l¹i B©y giê xÐt viÖc tÝnh Li(β) víi i > 1. Gi¶ sö p-1 = 2s ttrong ®ã t lµ sè lÎ. Khi ®ã cã thÓ chØ ra r»ng, dÔ dµng tÝnh ®−îc Li(β) nÕu1≤s. MÆt kh¸c, viÖc tÝnh Ls+1(β) ch¾c ch¾n lµ khã nÕu dïng thuËt to¸n gi¶®Þnh bÊt k× cho viÖc tÝnh Ls+1(β) ®Ó tÝnh c¸c logarithm rêi r¹c trong Zp. Ta sÏ chøng minh kÕt qu¶ nµy trong tr−êng hîp s = 1. ChÝnh x¸c h¬n,nÕu p ≡ 3 (mod 4)lµ sè nguyªn tè th× ta sÏ chØ ra c¸ch sö dông mét thuËt to¸ngi¶ ®Þnh bÊt k× tÝnh L2(β) ®Ó gi¶i bµi to¸n logarithm rêi r¹c trong Zp. NÕu β lµ mét thÆng d− b×nh ph−¬ng trong Zp vµ p ≡ 3 ( mod 4) th×±β(p+1)/2 mod p lµ hai gi¸ trÞ c¨n bËc hai cña modulo p. Mét chó ý còng quanträng lµ víi bÊt k× β ≠ 0: L1(β) ≠ L1(p-β).nÕu p ≡ 3 (mod 4). Ta sÏ thÊy ®iÒu ®ã nh− sau. Gi¶ sö αa ≡ β (mod p) αa+(p-1)/2 ≡ -β (mod p)th×V× p ≡ 3 (mod 4) nªn sè nguyªn (p-1)/2 lµ mét sè lÎ. Tõ ®©y rót ra kÕt qu¶. B©y giê gi¶ sö β = αa víi sè mò ch½n a (ch−a biÕt) nµo ®ã. Khi ®ãhoÆc: β(p+1)/4 ≡ αa/2 (mod p)hoÆc -β(p+1)/4 ≡ αa/2 (mod p)Ta cã thÓ x¸c ®Þnh gi¸ trÞ nµo trong hai gi¸ trÞ cã thÓ nµy lµ ®óng nÕu biÕt gi¸trÞ L2(β), v× L2(β) = L1(αa/2)§iÒu nµy ®−îc khai th¸c trong thuËt to¸n ®−îc m« t¶ trong h×nh 5.6. ë cuèi thuËt to¸n, c¸c gi¸ trÞ xi lµ c¸c bÝt biÓu diÔn nhÞ ph©n cñalogαβ, nghÜa lµ: ...
Nội dung trích xuất từ tài liệu:
Các hệ thống khóa công khai thác phần 3Vietebooks Nguyễn Hoàng Cương B©y giê ta cã 3 ®ång d− thøc theo 3 gi¸ trÞ log ch−a biÕt. Gi¶i c¸cph−¬ng tr×nh ®ång d− nµy, ta cã log52 = 6578, log53 = 6190, log57 = 1301. B©y giê gi¶ sö ta cÇn t×m log59451, ta chän sè mò ngÉu nhiªns=7736 vµ tÝnh: 9451×57736 mod 10007 = 8400V× 8400 = 24315271 c¸c thõa sè trong B nªn ta nhËn ®−îc: log59451 = 4log52 + log53 + log55 + log57 - s mod 10006 = 4×6578 + 6190 + 2×1 + 1310 - 7736 mod 10006 = 6057.KiÓm tra l¹i ta thÊy r»ng 56057 ≡ 9451 ( mod 10007). §· cã nhiÒu nghiªn cøu ph©n tÝch mß mÉm nhiÒu kiÓu thuËt to¸n kh¸cnhau. Víi gi¶ thiÕt hîp lý, Thêi gian ch¹y tiÖm cËn cña giai ®o¹n tiÒn tÝnhto¸n nµy cìvµ thêi gian ®Ó tÝnh mét gi¸ trÞ logarithm rêi r¹c riªng lµ kho¶ngH×nh 5.5. BÝt thø i cña logarithm rêi r¹c. B¶n chÊt cña bµi to¸n: I = (p, α, β, i) trong ®ã p lµ sè nguyªn tè , α∈Zp* lµ phÇn tö nguyªn thuû, β ∈ Zp* vµ i lµ mét sè nguyªn sao cho 1 ≤ i ≤ ⎣log2(p-1)⎦. Môc tiªu:TÝnh Li(β) lµ bÝt thÊp nhÊt thø i cña logαβ. (víi α vµ p cho tr−íc)5.1.2. §é b¶o mËt t−ng bÝt cña c¸c logarithm rêi r¹c. B©y giê ta xem xÐt vÊn ®Ò vÒ th«ng tin bé phËn cña c¸c logarithm rêir¹c vµ thö xem viÖc tÝnh c¸c bÝt riªng cña c¸c logarithm rêi r¹c lµ khã hay dÔ.Cô thÓ , xÐt bµi to¸n tr×nh bµy trªn h×nh 5.5. Bµi to¸n nµy ®−îc gäi lµ bµi to¸nvÒ bÝt thø i. Trang 11Vietebooks Nguyễn Hoàng Cương Tr−íc tiªn, ta sÏ chØ ra r»ng, bÝt thÊp nhÊt cña c¸c logarithm rêi r¹c rÊtdÔ tÝnh to¸n. Nãi c¸ch kh¸c, nÕu i = 1 th× bµi to¸n vÒ bÝt thø i cã thÓ gi¶i®−îc mét c¸ch hiÖu qu¶. §iÒu nµy rót ra tõ tiªu chuÈn Euler liªn quan ®ÕnthÆng d− b×nh ph−¬ng theo modulo p, víi p lµ sè nguyªn tè . XÐt ¸nh x¹ f: Zp* Zp* ®−îc ®Þnh nghÜa nh− sau: f(x) = x2 mod pNÕu kÝ hiÖu QR(p) lµ tËp c¸c thÆng d− b×nh ph−¬ng theo modulo p th× QR(p) = { x2 mod p : x ∈ Zp*}Tr−íc tiªn ta thÊy r»ng, f(x) = f(p-x). TiÕp theo xÐt thÊy: w2 ≡ x2 mod pkhi vµ chØ khi p | (w-x)(w+x)®iÒu nµy sÏ x¶y ra khi vµ chØ khi w ≡ ± x mod p. Tõ ®©y rót ra: | f-1(y) | = 2víi mäi y ∈ QR(p) vµ bëi vËy: | QR(p) = (p-1)/2§iÒu ®ã cã nghÜa lµ cã ®óng mét n÷a c¸c thÆng d− trong Zp* lµ c¸c thÆng d−b×nh ph−¬ng vµ mét n÷a kh«ng ph¶i. B©y gië gi¶ sö r»ng, α lµ mét phÇn tö nguyªn thuû cña Zp* . Khi ®ãαa∈QR(p) nÕu a ch½n. V× (p-1)/2 phÇn tö α0 mod p, α2 mod p,. . .,αp-3 mod p®Òu lµ c¸c phÇn tö kh¸c nhau nªn: QR(p) = {α2i mod p: 0 ≤ i ≤ (p-3)/2}Bëi vËy, β lµ thÆng d− b×nh ph−¬ng khi vµ chØ khi logαβ lµ ch½n, tøc khi vµchØ khi L1(β) = 0. Tuy nhiªn theo tiªu chuÈn Euler β lµ thÆng d− b×nh ph−¬ngkhi vµ chØ khi β(p-1)/2 ≡ 1 (mod p) Trang 12Vietebooks Nguyễn Hoàng CươngNh− vËy, ta ®· cã c«ng thøc h÷u hiÖu sau ®Ó tÝnh L1(β): nÕu β(p-1)/2 ≡ 1( mod p) 0 L1(β)= 1 trong c¸c tr−êng hîp cßn l¹i B©y giê xÐt viÖc tÝnh Li(β) víi i > 1. Gi¶ sö p-1 = 2s ttrong ®ã t lµ sè lÎ. Khi ®ã cã thÓ chØ ra r»ng, dÔ dµng tÝnh ®−îc Li(β) nÕu1≤s. MÆt kh¸c, viÖc tÝnh Ls+1(β) ch¾c ch¾n lµ khã nÕu dïng thuËt to¸n gi¶®Þnh bÊt k× cho viÖc tÝnh Ls+1(β) ®Ó tÝnh c¸c logarithm rêi r¹c trong Zp. Ta sÏ chøng minh kÕt qu¶ nµy trong tr−êng hîp s = 1. ChÝnh x¸c h¬n,nÕu p ≡ 3 (mod 4)lµ sè nguyªn tè th× ta sÏ chØ ra c¸ch sö dông mét thuËt to¸ngi¶ ®Þnh bÊt k× tÝnh L2(β) ®Ó gi¶i bµi to¸n logarithm rêi r¹c trong Zp. NÕu β lµ mét thÆng d− b×nh ph−¬ng trong Zp vµ p ≡ 3 ( mod 4) th×±β(p+1)/2 mod p lµ hai gi¸ trÞ c¨n bËc hai cña modulo p. Mét chó ý còng quanträng lµ víi bÊt k× β ≠ 0: L1(β) ≠ L1(p-β).nÕu p ≡ 3 (mod 4). Ta sÏ thÊy ®iÒu ®ã nh− sau. Gi¶ sö αa ≡ β (mod p) αa+(p-1)/2 ≡ -β (mod p)th×V× p ≡ 3 (mod 4) nªn sè nguyªn (p-1)/2 lµ mét sè lÎ. Tõ ®©y rót ra kÕt qu¶. B©y giê gi¶ sö β = αa víi sè mò ch½n a (ch−a biÕt) nµo ®ã. Khi ®ãhoÆc: β(p+1)/4 ≡ αa/2 (mod p)hoÆc -β(p+1)/4 ≡ αa/2 (mod p)Ta cã thÓ x¸c ®Þnh gi¸ trÞ nµo trong hai gi¸ trÞ cã thÓ nµy lµ ®óng nÕu biÕt gi¸trÞ L2(β), v× L2(β) = L1(αa/2)§iÒu nµy ®−îc khai th¸c trong thuËt to¸n ®−îc m« t¶ trong h×nh 5.6. ë cuèi thuËt to¸n, c¸c gi¸ trÞ xi lµ c¸c bÝt biÓu diÔn nhÞ ph©n cñalogαβ, nghÜa lµ: ...
Tìm kiếm theo từ khóa liên quan:
tài liệu window thủ thuật window tài liệu bảo mật bí quyết bảo mật phương pháp bảo mậtTài liệu có liên quan:
-
Cách phân tích thiết kế hệ thống thông tin quan trọng phần 4
13 trang 246 0 0 -
Các cách phát hiện PC và email của bạn có bị theo dõi hay không?
8 trang 85 0 0 -
Giáo trình tin học : Tìm hiểu một sơ đồ chữ kí số phần 8
6 trang 72 0 0 -
Cách bảo mật cho máy chủ web Apache
10 trang 39 0 0 -
Báo cáo thực tập: Ứng dụng Ddos để khai thác thông tin
49 trang 39 0 0 -
Giáo trình tin học quản lý phần 10
11 trang 37 0 0 -
Lịch sử và các bản phân phối HĐH Linux từ trước đến nay phần 8
6 trang 34 0 0 -
Thủ thuật Windows XP: Tăng tốc tắt máy
1 trang 32 0 0 -
Lưu giữ các thông tin quan trọng
14 trang 30 0 0 -
Thủ thuật Windows XP ( phần 5)
7 trang 28 0 0