Tìm hiểu hệ mật RSA và các nguyên tố xác suất

Kiể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ẫu nhiên lớn (chẳng hạn có 80 chữ số).
Nội dung trích xuất từ tài liệu:
Tìm hiểu hệ mật RSA và các nguyên tố xác suất Vietebooks Nguyễn Hoàng CươngHướng dẫn kiểm tra tính nguyênh−¬ng 4của hệ mật RSA C tố xác suất KiÓ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ù. Trang 1Vietebooks Nguyễn Hoàng CươngChó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. Trang 2Vietebooks Nguyễn Hoàng Cương§Þ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) ...