Lý thuyết mật mã - Chương 4.1

Tài liệu tham khảo về lý thuyết mật mã, cách làm và giải mật mã an toàn.
Nội dung trích xuất từ tài liệu:
Lý thuyết mật mã - Chương 4.1KiÓm tra tÝnh nguyªn tè x¸c suÊt §Ó thiÕt lËp hÖ mËt RSA, ta ph¶i t¹o ra c¸c sè nguyªn tè ngÉunhiªn lín (ch¼ng h¹n cã 80 ch÷ sè). Trong thùc tÕ, ph−¬ng c¸ch thùchiÖn ®iÒu nµy lµ: tr−íc hÕt ph¶i t¹o ra c¸c sè ngÈu nhiªn lín, sau ®ãkiÓm tra tÝnh nguyªn thuû cña chóng b»ng c¸ch dïng thuËt to¸n x¸csuÊt Monte- Carlo thêi gian ®a thøc (ch¼ng h¹n nh− thuËt to¸nMiller- Rabin hoÆc lµ thuËt to¸n Solovay- Strasen). C¶ hai thuËt to¸ntrªn ®Òu ®−îc tr×nh bµy trong phÇn nµy. Chóng lµ c¸c thuËt to¸nnhanh (tøc lµ mét sè nguyªn n ®−îc kiÓm tra trong thêi ®a thøc theolog2n, lµ sè c¸c bÝt trong biÓu diÖn nhÞ ph©n cña n). Tuy nhiªn, vÉn cãkh¶ n¨ng lµ thuËn to¸n cho r»ng n lµ sè nguyªn tè trong khi thùc tÕ nlµ hîp lÖ sè. Bëi vËy, b»ng c¸ch thay ®æi thuËt to¸n nhiÒu lÇn, cã thÓgi¶m x¸c suÊt sai sè d−íi mét møc ng−ìng cho phÐp (sau nµy sÏ th¶oluËn kü h¬n mét chót vÒ vÊn ®Ò nµy). Mét vÊn ®Ò quan träng kh¸c: lµ cÇn ph¶i kiÓm tra bao nhiªu sènguyªn ngÉu nhiªn (víi kÝch th−¬c x¸c ®Þnh)cho tíi khi t×m ®−îc métsè nguyªn tè. Mét kÕt qu¶ nçi tiÕng trong lý thuyÕt sè (®−îc gäi lµ®Þnh lý sè nguyªn tè) ph¸t biÓu r»ng: sè c¸c sè nguyªn tè kh«ng lính¬n N xÊp xØ b»ng N/ln N. Bëi vËy, nÕu p ®−îc chän ngÉu nhiªn th×x¸c suÊt p lµ mét sè nguyªn tè sÏ vµo kho¶ng 1/ln p. Víi mét mo®un512 bÝt, ta cã 1/ln p ≈ 1/77. §iÒu nµy cã nghÜa lµ tÝnh trung b×nh, c−177 sè nguyªn ngÉu nhiªn p víi kÝch th−íc t−¬ng øng sÏ cã mét sè lµsè nguyªn tè. DÜ nhiªn, nÕu chÜ h¹n chÕ xÐt c¸c sè nguyªn lÎ th× x¸csuÊt sÏ t¨ng gÊp ®«i tíi kho¶ng 2/177). Bìi vËy trªn thùc tÕ, hoµntoµn cã kh¶ n¨ng t¹o ®−îc c¸c nguyªn tè ®ñ lín vµ do ®ã vÒ mÆt thùcthÓ ta cã thÓ thiÕt lËp ®−îc mét hÖ mËt RSA. Sau ®©y sÏ tiÕp tôc xemxÐt ®iÒu nµy ®−îc thùc hiªn nh− thÕ nµo.Mét bµi to¸n quyÕt ®Þnh lµ mét bµi to¸n to¸n trong ®ã mét c©u háicÇn ®−îc tr¶ lêi “cã” hoÆc “kh«ng”. Mét thuËt to¸n x¸c suÊt lµ métthuËt to¸n bÊt kú cã sö dông c¸c sè ngÉu nhiªn (ng−îc l¹i, thuËt to¸nkh«ng sö dông c¸c sè ngÉu nhiªn sÏ ®−îc gäi lµ mét thuËt to¸n tÊt®Þnh). C¸c ®Þnh nghÜa sau cã liªn quan tíi c¸c thuËt to¸n x¸c suÊt choc¸c bµi to¸n quyÕt ®Þnh.§Þnh nghÜa 4.1 ThuËt to¸n Monte Carlo ®Þnh h−íng “cã” lµ mét thuËt to¸n x¸csuÊt cho mét bµi to¸n quyÕt ®Þnh, trong ®ã c©u tr¶ lêi “cã” lu«n lu«nlµ ®óng cßn c©u tr¶ lêi “kh«ng” cã thÓ lµ sai. ThuËt to¸n Monte Carlo®Þnh h−íng “kh«ng“ còng ®−îc ®Þnh nghÜa theo c¸ch t−¬ng tù.Chóng ta nãi r»ng, mét thuËt to¸n Monte Carlo ®Þnh h−íng “cã” cãx¸c suÊt sai b»ng ε nÕu víi bÊt kú mæt tr−êng hîp nµo mµ c©u tr¶ lêilµ “cã” th× thuËt to¸n cã c©u tr¶ lêi sai “kh«ng” víi x¸c suÊt kh«nglín h¬n ε (x¸c suÊt nµy ®−îc tÝnh trªn mäi phÐp chon ngÉu nhiªn, cãthÓ thùc hiªn bëi thuËt to¸n víi mét c©u vµo ®· cho). Bµi to¸n quyÕt ®Þnh ë ®©y lµ bµi to¸n hîp lÖ sè m« t¶ ë h×nh4.5.CÇn chó ý r»ng mét thuËt to¸n quyÕt ®Þnh chØ cã c©u tr¶ lêi “cã” hoÆc“kh«ng” ®Æc biÖt trong bµi to¸n hîp lÖ sè lµ ta kh«ng yªu cÇu thuËtto¸n tÝnh tÝch thõa sè khi n lµ hîp lÖ sè. Tr−íc tiªn ta sÏ m« t¶ thuËt to¸n Soloway- Strasson. §©y lµmét thuËt to¸n Monte- Carlo ®Þnh h−íng “cã” cho bµi to¸n hîp sè cãTr−íc tiªn ta sÏ m« t¶ thuËt to¸n Soloway- Strasson. §©y lµ métthuËt to¸n Monte-Carlo ®Þnh h−íng “cã” cho bµi to¸n hîp sè vµ x¸cxuÊt sai 1/2. Bëi vËy, nÕu thuËt to¸n tr¶ lêi “cã” th× n lµ hîp sè;ng−îc l¹i nÕu n lµ hîp sè th× thuËt to¸n tr¶ lêi “cã” víi x¸c xuÊt tèithiÓu 1/2. H×nh 4.5. Bµi to¸n hîp sè. §Æc tr−ng cña bµi to¸n: mét sè nguyªn d−¬ng n ≥ 2 C©u hái: n cã ph¶i lµ hîp sè kh«ng ? H×nh 4.6. Bµi to¸n vÒ c¸c thÆng d− bËc hai. §Æc tr−ng cña bµi to¸n: cho p lµ mét sè nguyªn tè lÎ vµ mét sè nguyªn x sao cho 0 ≤ x ≤ p-1 C©u hái: x cã ph¶i lµ thÆng d− bËc hai phÐp modulo p ? MÆc dï thuËt to¸n Miller-Rabin (ta sÏ xÐt sau) nhanh h¬nthuËt to¸n Soloway-Strasson (S-S) nh−ng ta sÏ xÐt thuËt to¸n S-Str−íc v× nã dÔ hiÓu h¬n vÒ kh¸i niÖm, ®ång thêi l¹i liªn quan tíi métsè vÊn ®Ò cña lý thuyÕt sè (mµ ta sÏ cßn dïng trong c¸c ch−¬ng tr×nhsau). Ta sÏ x©y dùng mét sè nÒn t¶ng s©u s¾c h¬n trong lý thuyÕt sètr−íc khi m« t¶ thuËt to¸n.§Þnh nghÜa 4.2. Gi¶ sö p lµ mét sè nguyªn tè lÎ vµ x lµ mét sè nguyªn, 1 ≤ x ≤p-1. x ®−îc gäi lµ thÆng d− bËc hai theo modulo p nÕu ph−¬ng tr×nh®ång d− y2 ≡ x (modulo p) cã mét nghiÖm y∈Zp x ®−îc gäi lµ thÆngd− kh«ng bËc hai theo modulo p nÕu x ??? 0 (mod p) vµ x kh«ng ph¶ilµ thÆng d− bËc hai theo modulo p.VÝ dô 4.6.C¸c thÆng d− bËc hai theo modulo 11 lµ 1,3,4,5 vµ 9. CÇn ®Ó ý r»ng,(±1)2=1, (±5)2=3, (±2)2=4, (±4)2=5, (±3)2=9 (ë ®©y tÊt c¶ c¸c phÐp sèhäc ®Òu thùc hiÖn trong Z11). Bµi to¸n quyÕt ®Þnh thÆng d− bËc hai ®−îc tr×nh bµy trªn h×nh4.6 sÏ ®−îc thÊy mét c¸ch t−¬nngf minh nh− sau: Tr−íc hÕt, ta sÏ chøng minh mét kÕt qu¶- tiªu chuÈn Euler –t¹o nªn thuËt to¸n tÊt ®Þnh theo thêi gian ®a thøc cho bµi to¸n vÒ c¸cthÆng d− bËc hai.§Þnh lý 4.8. (Tiªu chuÈn Euler) Gi¶ sö p lµ mét sè nguyªn tè, khi ®ã x lµ mét thÆng d− bËc haitheo modulo p khi vµ chØ khi: x(p-1)/2 ≡1 (mod p)Chøng minh: Tr−íc hÕt gi¶ sö r»ng, x≡y2(mod p). Theo hÖ qu¶ 4.6, nÕu p lµsè nguyªn tè th× xp-1≡1 (mod p) víi mäi x ≡ 0 (mod p). Bëi vËy ta cã : x(p-1)/2 ≡ (y2)(p-1)/2 (mod p) ≡yp-1(mod p) ≡1 (mod p) Ng−îc l¹i, gi¶ sö r»ng x(p-1)/2≡1 (mod p). Cho p lµ mét phÇn tönguyªn thuû theo modulo p. Khi ®ã x≡bi (mod p) víi gi¸ trÞ i nµo ®ã.Ta cã x(p-1)/2 ≡ (bi)(p-1)/2 (mod p) ≡bi(p-1)/2(mod p) V× p cã bËc b»ng p-1 nªn p-1 ph¶i lµ −íc cña i(p-1)/2. Bëi vËy i lµ sèch½n vµ nh− vËy c¨n bËc hai cña x lµ ±bi/2. §Þnh lý 4.8 sÏ dÉn tíi mét thuËt to¸n thêi gian ®a thøc cho c¸cthÆng d− bËc hai nhê sö dông kü thuËt “b×nh ph−¬ng vµ nh©n” chophÐp lÊy luü thõa theo modulo p. §é phøc t¹p cña thuËt to¸n kho¶ngO((log p)3).Sau ®©y tiÕp tôc ®−a r ...