Giáo trình Mật mã và ứng dụng: Chương 4

Chia sẻ: Huỳnh Văn Thống | Ngày: | Loại File: PDF | Số trang:58

Thêm vào BST

Báo xấu

132
lượt xem 28
download

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

Giáo trình Mật mã và ứng dụng - Chương 4: Hệ mật Rsa và vấn đề phân tích thừa số, trình bày các nội dung: giới thiệu về hệ mật khóa công khai, một số vấn đề sâu hơn về lý thuyết số, hệ mật Rsa, thực hiện hệ mật Rsa, kiểm tra tính nguyên tố xác suất, các phương pháp tấn công hệ mật Rsa,... Đây là tài liệu tham khảo dành cho sinh viên Công nghệ thông tin.

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình Mật mã và ứng dụng: Chương 4

Ch−¬ng 4 HÖ mËt RSA v vÊn ®Ò ph©n tÝch thõa sè 4.1. Giíi thiÖu vÒ hÖ mËt kho¸ c«ng khai Trong m« h×nh mËt m cæ ®iÓn tr−íc ®©y m hiÖn nay ®ang ®−îc nghiªn cøu Alice (ng−êi göi) v Bob (ng−êi nhËn) chän mét c¸ch bÝ mËt kho¸ K. Sau ®ã dïng K ®Ó t¹o luËt m ho¸ ekv luËt gi¶i m dk. Trong hÖ mËt n y dk hoÆc gièng nh− ek hoÆc dÔ d ng nhËn ®−îc tõ nã (vÝ dô trong hÖ DES qu¸ tr×nh gi¶i m ho n to n t−¬ng tù nh− qu¸ tr×nh m nh−ng thñ tôc kho¸ ng−îc l¹i). C¸c hÖ mËt thuéc lo¹i n y ®−îc gäi l hÖ mËt kho¸ bÝ mËt, nÕu ®Ó lé ek th× l m cho hÖ thèng mÊt an to n. Nh−îc ®iÓm cña hÖ mËt n y l nã yªu cÇu ph¶i cã th«ng tin tr−íc vÒ kho¸ K gi÷a Alice v Bob qua mét kªnh an to n tr−íc khi göi mét b¶n m bÊt kú. Trªn thùc tÕ ®iÒu n y rÊt khã ®¶m b¶o. Ch¼ng h¹n khi Alice v Bob ë c¸ch xa nhau v hä chØ cã thÓ liªn l¹c víi nhau b»ng th− tÝn ®iÖn tö (Email). Trong t×nh huèng ®ã Alice v Bob kh«ng thÓ t¹o mét kªnh b¶o mËt víi gi¸ ph¶i ch¨ng. ý t−ëng x©y dùng mét hÖ mËt kho¸ c«ng khai (hay kho¸ dïng chung) l t×m mét hÖ mËt kh«ng cã kh¶ n¨ng tÝnh to¸n ®Ó x¸c ®Þnh dkkhi biÕt ek. NÕu thùc hiÖn ®−îc nh− vËy th× quy t¾c m ek cã thÓ ®−îc c«ng khai b»ng c¸ch c«ng bè nã trong mét danh b¹ (bëi vËy nªn cã thuËt ng÷ hÖ mËt kho¸ c«ng khai). ¦u ®iÓm cña hÖ mËt kho¸ c«ng khai l ë chç Alice (hoÆc bÊt k× mét ai) cã thÓ göi mét b¶n tin ® m cho Bob (m kh«ng cÇn th«ng tin tr−íc vÒ kho¸ mËt) b»ng c¸ch dïng luËt m c«ng khai ek. Ng−êi nhËn A sÏ l ng−êi duy nhÊt cã thÓ gi¶i ®−îc b¶n m n y b»ng c¸ch sö dông luËt gi¶i m bÝ mËt dk cña m×nh. Cã thÓ h×nh dung hÖ mËt n y t−¬ng tù nh− sau. Alice ®Æt mét vËt v o mét hép kim lo¹i v råi kho¸ nã l¹i b»ng mét kho¸ sè do Bob ®Ó l¹i. ChØ cã Bob l ng−êi duy nhÊt cã thÓ më ®−îc hép v× chØ cã anh ta míi biÕt tæ hîp m cña kho¸ sè cña m×nh.
ý t−ëng vÒ mét hÖ mËt kho¸ c«ng khai ® ®ùoc Diffie v Hellman ®−a ra v o n¨m 1976. Cßn viÖc hiÖn thùc ho¸ nã th× do Rivesrt, Shamir v Adleman ®−a ra ®Çu tiªn v o n¨m 1977, hä ® t¹o nªn hÖ mËt næi tiÕng RSA (sÏ ®−îc nghiªn cøu trong ch−¬ng n y). KÓ tõ ®ã mét sè hÖ ®−îc c«ng bè, ®é mËt cña chóng dùa trªn c¸c b i to¸n tÝnh to¸n kh¸c nhau. Sau ®©y l c¸c hÖ mËt kho¸ c«ng khai quan träng : + HÖ mËt RSA: §é b¶o mËt cña hÖ RSA dùa trªn ®é khã cña viÖc ph©n tÝch ra thõa sè nguyªn tè c¸c sè nguyªn lín. HÖ n y sÏ ®−îc m« t¶ trong phÇn 4.3. + HÖ mËt xÕp ba l« Merkle - Hellman: HÖ n y v c¸c hÖ liªn quan dùa trªn tÝnh khã gi¶i cña b i to¸n tæng c¸c tËp con (b i to¸n n y l b i to¸n NP ®Çy ®ñ – l mét líp kh¸ lín c¸c b i to¸n kh«ng cã thuËt gi¶i ®−îc biÕt trong thêi gian ®a thøc). Tuy nhiªn tÊt c¶ c¸c hÖ mËt xÕp ba l« kh¸c nhau ®Òu ® bÞ chøng tá l kh«ng mËt (ngo¹i trõ hÖ mËt Chor – Rivest sÏ ®−îc nªu d−íi ®©y). HÖ mËt n y ®−îc xÐt ë ch−¬ng 5. + HÖ mËt McEliece: HÖ n y dùa trªn lý thuyÕt m ®¹i sè v vÉn cßn ®−îc coi l an to n. HÖ mËt McEliece dùa trªn b i to¸n gi¶i m cho c¸c m tuyÕn tÝnh (còng l mét b i to¸n NP ®Çy ®ñ). HÖ mËt McEliece ®−îc tr×nh b y ë ch−¬ng 5. + HÖ mËt Elgamal: HÖ mËt Elgamal dùa trªn tÝnh khã gi¶i cña b i to¸n logarithm rêi r¹c trªn c¸c tr−êng h÷u h¹n (xem trong ch−¬ng 5). + HÖ mËt Chor - Rivest: HÖ mËt Chor - Rivest còng ®−îc xem nh− mét lo¹i hÖ mËt xÕp ba l«. Tuy nhiªn nã vÉn ®−îc coi l an to n. + HÖ mËt trªn c¸c ®−êng cong Elliptic C¸c hÖ mËt n y l biÕn t−íng c¶u c¸c hÖ mËt kh¸c (ch¼ng h¹n nh− hÖ mËt Elgamal) , chóng l m viÖc trªn c¸c ®−êng cong Elliptic chø kh«ng ph¶i l trªn c¸c tr−êng h÷u h¹n. HÖ mËt n y ®¶m b¶o ®é mËt víi kho¸ sè nhá h¬n c¸c hÖ mËt kho¸ c«ng khai kh¸c (xem ch−¬ng 5). Mét chó ý quan träng l mét hÖ mËt kho¸ c«ng khai kh«ng bao giê cã thÓ ®¶m b¶o ®−îc ®é mËt tuyÖt ®èi (an to n v« ®iÒu kiÖn). Së dÜ nh− vËy v× ®èi ph−¬ng khi nghiªn cøu mét b¶n m y cã thÓ m lÇn l−ît c¸c b¶n râ b»ng luËt m c«ng khai ek cho tíi khi anh ta t×m ®−îc b¶n râ duy nhÊt x ®¶m b¶o y = ek
(x). B¶n râ n y chÝnh l kÕt qu¶ gi¶i m cña y. Bëi vËy ta chØ nghiªn cøu ®é mËt vÒ mÆt tÝnh to¸n cña c¸c hÖ mËt n y. Mét kh¸i niÖm cã Ých khi nghiªn cøu hÖ mËt kho¸ c«ng khai l kh¸i niÖm vÒ h m cöa sËp mét chiÒu. Ta ®Þnh nghÜa kh¸i niÖm n y mét c¸ch kh«ng h×nh thøc. H m m kho¸ c«ng khai ek cña Bob ph¶i l mét h m dÔ tÝnh to¸n. Song viÖc t×m h m ng−îc (h m gi¶i m ) ph¶i rÊt khã kh¨n (®èi víi bÊt kú ai kh«ng ph¶i l Bob). §Æc tÝnh dÔ tÝnh to¸n nh−ng khã tÝnh to¸n h m ng−îc th−êng ®−îc gäi l ®Æc tÝnh mét chiÒu. Bëi vËy ®iÒu kiÖn c©n thiÕt l ek ph¶i l h m mét chiÒu. C¸c h m mét chiÒu ®ãng vai trß quan träng trong mËt m häc: chóng rÊt quan trong c¸c hÖ mËt kho¸ c«ng khai v trong nhiÒu lÜnh vùc kh¸c. §¸ng tiÕc l mÆc dï cã rts nhiÒu h m ®−îc coi l h m mét chiÒu nh−ng cho tíi nay vÉn kh«ng tån t¹i mét h m n o cã thÓ chøng minh ®−îc l h m mét chiÒu. Sau ®©y l mét vÝ dô vÒ mét h m ®−îc coi l h m mét chiÒu. Gi¶ sö n l tÝch cña hai sè nguyªn tè lín p v q, gi¶ sö b l mét sè nguyªn d−¬ng. Khi ®ã ta x¸c ®Þnh ¸nh x¹ f : Zn Zn l f(x) = xb mod n (víi b v n ® ®−îc chän thÝch hîp th× ®©y chÝnh l h m m RSA, sau n y sÏ cßn nãi nhiÒu vÒ nã). §Ó x©y dùng mét hÖ mËt kho¸ c«ng khai th× viÖc t×m ®−îc mét h m mét chiÒu vÉn ch−a ®ñ. Ta kh«ng muèn ek l h m mét chiÒu ®èi víi Bob v× anh ta ph¶i cã kh¶ n¨ng gi¶i m c¸c b¶n tin nhËn ®−îc mét c¸ch hiÖu qu¶. §iÒu cÇn thiÕt l Bob ph¶i cã mét cöa sËp chøa th«ng tin bÝ mËt cho phÐp dÔ d ng t×m h m ng−îc cña ek. Nh− vËy Bob cã thÓ gi¶i m mét c¸ch h÷u hiÖu v× anh ta cã mét hiÓu biÕt tuyÖt mËt n o ®ã vÒ K. Bëi vËy mét h m ®−îc gäi l cöa sËp mét chiÒu nÕu nã l h m mét chiÒu v nã trë nªn dÔ tÝnh ng−îc nÕu biÕt mét cöa sËp mhÊt ®Þnh. Ta sÏ xÐt c¸ch t×m mét cöa sËp ®èi víi h m f nªu ë trªn trong phÇn 4.3. C¸c t×m n y sÏ dÉn ®Õn hÖ mËt RSA.
4.2. mét sè vÊn ®Ò s©u h¬n vÒ lý thuyÕt sè Tr−íc khi m« t¶ hÖ mËt RSA l m viÖc ra sao cÇn ph¶i xem xÐt mét sè yÕu tè liªn quan ®Õn lý thuyÕt sè v sè häc modulo. Hai kÕt qu¶ cÇn biÕt l thuËt to¸n Euclide v ®Þnh lý phÇn d− China. 4.2.1 ThuËt to¸n Euclide Trong ch−¬ng 1 ® xÐt Zn l mét v nh víi sè nguyªn d−¬ng bÊt kú n. Ta còng ® chøng tá r»ng phÇn tö b ∈ Zn cã phÇn tö nghÞch ®¶o (phÇn tö ng−îc cña phÐp nh©n) khi v chØ khi −CLN(b,n) = 1 v c¸c sè nguyªn d−¬ng nhá h¬n n v nguyªn tè cïng nhau víi n b»ng φ (n). TËp c¸c thÆng d− theo modulo n v nguyªn tè cïng nhau víi n ®−îc ký hiÖu l Zn* .Kh«ng khã kh¨n cã thÓ thÊy r»ng Zn* sÏ t¹o nªn mét nhãm Abel ®èi víi phÐp nh©n. Ta còng biÕt r»ng, phÐp nh©n theo modulo n l giao ho¸n v kÕt hîp v phÇn tö ®¬n vÞ l 1. Mét phÇn tö bÊt kú trong Zn*®Òu cã nghÞch ®¶o béi (còng n»m trong Zn*). Cuèi cïng Zn* l ®ãng ®èi víi phÐp nh©n v× xy l nguyªn tè cïng nhau víi n khi x v y nguyªn tè cïng nhau víi n. (H y chøng minh ®iÒu n y!) Cho tíi b©y giê ta chØ biÕt r»ng mét phÇn tö b bÊt k× ∈ Zn* ®Òu cã nghÞch ®¶o b-1 song viÖc tÝnh nã vÉn ch−a nãi ®Õn. Mét thuËt to¸n nh− vËy ®−îc gäi l thuËt to¸n Euclide më réng. Tr−íc tiªn ta sÏ m« t¶ thuËt to¸n Euclide, th«ng th−êng thuËt to¸n n y ®−îc dïng ®Ó tÝnh −íc sè chung lín nhÊt (−CLN) cña hai sè nguyªn d−¬ng r0 v r1 víi r0 > r1.ThuËt to¸n Euclide bao gåm viÖc thùc hiÖn c¸c phÐp to¸n nh− sau: r0 = q1 r1 +r2 0 < r2 < r1 r1 = q2 r2 +r3 0 < r3 < r2 . . rm -2 = qm -1 rm -1 +rm 0 < rm -1 < rm rm -1 = qm rm Khi ®ã dÔ d ng chøng tá ®−îc r»ng −CLN(r0 , r1 ) = −CLN(r1 , r2 ) = . . . −CLN(rm-1 , rm ) = rm
Bëi vËy −CLN(r0 , r1 ) = rm V× thuËt to¸n Euclide tÝnh c¸c −CLN nªn cã thÓ ¸p dông nã ®Ó x¸c ®Þnh xem liÖu mét sè nguyªn d−¬ng b < n cã nghÞch ®¶o theo modulo n kh«ng b»ng c¸ch b¾t ®Çu víi r0 = n v r1 = b. Tuy nhiªn thuËt to¸n n y kh«ng cho phÐp tÝnh gi¸ trÞ cña phÇn tö nghÞch ®¶o (nÕu nã tån t¹i). B©y giê gi¶ sö ®Þnh nghÜa mét d y sè t0 , t1 ,.... ,tm theo c¸c c«ng thøc truy to¸n sau (trong ®ã c¸c gi¸ trÞ qj ® ®−îc x¸c ®Þnh ë trªn) t0 = 0 t1 = 1 tj = tj-2- qj-1 tj-1 mod r0 nÕu j ≥ 2 Ta cã kÕt qu¶ quan träng sau §Þnh lý 4.1. Víi 0 ≤ j ≤ m, ta cã rj ≡ tjr1 (mod r0), trong ®ã c¸c gi¸ trÞ qj v rj ®−îc x¸c ®Þnh theo thuËt to¸n Euclide cßn c¸c gi¸ trÞ tj ®−îc x¸c ®Þnh theo c«ng thøc truy to¸n ë trªn. Chøng minh: Ta chøng minh b»ng c¸ch quy n¹p theo j. §Þnh lý hiÓn nhiªn ®óng víi j = 0 v j = 1. Gi¶ sö ®Þnh lý còng ®óng víi j = i-1 v j = i-2, trong ®ã i ≥ 2; sau ®©y ta sÏ chøng tá ®Þnh lý ®óng víi j = i. Theo quy n¹p ta cã ri-2 ≡ ti-2 r1 (mod r0) v ri-1 ≡ ti-1 r1 (mod r0) B©y giê ta tÝnh ri = ri-2 - qi-1 ri-1 ≡ ti-2 r1 - qi-1 ti-1 r1 (mod r0) ≡ (ti-2 - qi-1 ti-1)r1 (mod r0) ≡ ti r1 (mod r0) Bëi vËy theo quy n¹p ®Þnh lý l ®óng. HÖ qu¶ rót ra trùc tiÕp tõ ®Þnh lý trªn. HÖ qu¶ 4.2:
Gi¶ sö −CLN (r0,r1) = 1, khi ®ã tm = r1-1 mod r0. H×n 2.1 ThuËt to¸n Euclide më réng: 1. n0 = n 2. b0 = b 3. t0 = 0 4. t=1 5. q = n0 /b0 6. r = n0 - q×b0 7. While r > 0 do 8. temp = t0 -q×t 9. if temp ≥ 0 then temp = temp mod n 10. if temp < 0 then temp = n - ((- temp) mod n) 11. t0 = t 12. t = temp 13. n0 = b 0 14. b0 = r 15. q = n0 /b0 16. r = n0 - q×b0 17. if b0 ≠ 1 then b kh«ng cã nghÞch ®¶o theo modulo n -1 else b = t mod n . XÐt thÊy d y c¸c sè t0, t1, . . . , tm cã thÓ ®−îc tÝnh to¸n trong thuËt to¸n Euclide ®ång thêi nh− c¸c gi¸ trÞ qj v rj. H×nh 4.1 tr×nh b y thuËt to¸n Euclide më réng ®Ó tÝnh nghÞch ®¶o cña b theo modulo n (nÕu nã tån t¹i). Trong thuËt to¸n n y kh«ng ph¶i dïng m¶ng (array) ®Ó ghi c¸c gi¸ trÞ qj, rj v tj v× chØ cÇn nhí hai gi¸ trÞ cuèi cïng trong mçi d y n y ë mét ®iÓm bÊt k× trong thuËt to¸n. Trong b−íc 10 cña thuËt to¸n ta ® viÕt biÓu thøc cho biÕn temp theo c¸ch ®Ó phÐp rót gän theo modulo n ®−îc thùc hiÖn ®èi víi sè d−¬ng. (Tr−íc ®©y ® biÕt r»ng viÖc rót gän theo modulo cña c¸c sè ©m sÏ dÉn ®Õn c¸c kÕt qu¶ ©m ë nhiªï ng«n ng÷ m¸y tÝnh; cßn ë ®©y ta muèn kÕt thóc víi kÕt qu¶ d−¬ng). ë b−íc 12 lu«n cã tb ≡ r (mod n) (kÕt qu¶ n y ® ®−îc chøng minh ë ®Þnh lý 4.1).
Sau ®©y l mét vÝ dô nhá ®Ó minh ho¹ VÝ dô 4.1. Gi¶ sö ta cÇn tÝnh 28-1 mod 75. ThuËt to¸n Euclide më réng thùc hiÖn nh− sau: 75 = 2 × 28 +29 b−íc 6 73 × 28 mod 75 = 19 b−íc 12 28 = 1 × 19 + 9 b−íc 16 3 × 28 mod 75 = 9 b−íc 12 19 = 2 × 9 + 1 b−íc 16 67 × 28 mod 75 = 1 b−íc 12 9=9×1 b−íc 16 V× thÕ 28-1 mod 75 = 67. 4.2.2. §Þnh lý phÇn d− China §Þnh lý n y thùc sù l mét ph−¬ng ph¸p gi¶i c¸c hÖ ph−¬ng tr×nh ®ång d−. Gi¶ sö m1, . . . , mr l c¸c sè nguyªn tè cïng nhau tõng ®«i mét (tøc −CLN(mi,mj)=1 nÕu j≠i). Gi¶ sö a1,. . ., ar l c¸c sè nguyªn xÐt hÖ ph−¬ng tr×nh ®ång d− sau: x ≡ a1 (mod m1) x ≡ a2 (mod m2) . . x ≡ ar (mod mr) §Þnh lý phÇn d− China kh¼ng ®Þnh r»ng hÖ n y cã nghiÖm duy nhÊt theo modulo M = m1×m2×. . . ×mr. Ta sÏ chøng minh kÕt qu¶ ®ã trong phÇn n y v còng m« t¶ mét thuËt to¸n h÷u hiÖu ®Ó gi¶i hÖ ®ång d− thøc d¹ng trªn. §Ó thuËn tiÖn, xÐt h m π : ZM Zm1× . . .×Zmr. H m n y ®−îc ®Þnh nghÜa nh− sau: π(x) = (x mod m1, . . . , x mod mr )
VÝ dô 4.2 Gi¶ sö r = 2, m1 = 5 v m2 = 3, bëi vËy M = 15. Khi ®ã h m π cã gi¸ trÞ sau π(0) = (0,0) π(1) = (1,1) π(2) = (2,2) π(3) = (3,0) π(4) = (4,1) π(5) = (0,2) π(6) = (1,0) π(7) = (2,1) π(8) = (3,2) π(9) = (4,0) π(10) =(0,1) π(11) =(1,2) π(12) =(2,0) π(13) =(3,1) π(14) =(4,2) ViÖc chøng minh ®Þnh lý phÇn d− China t−¬ng ®−¬ng víi viÖc chøng minh r»ng h m π l mét song ¸nh. §iÒu n y cã thÓ dÔ d ng thÊy ®−îc ë vÝ dô 4.2. Trong thùc tÕ cã thÓ ®−a ra mét c«ng thøc t−êng minh tæng qu¸t cho h m ng−îc π-1. Víi 1 ≤ i ≤ r, ®Þnh nghÜa: Mi = M/mi Khi ®ã, dÔ d ng thÊy r»ng −CLN(Mi,mi) = 1 víi 1 ≤ i ≤ r. TiÕp theo, víi 1 ≤ i ≤ r, ®Þnh nghÜa yi = Mi-1 mod mi (phÇn tö nghÞch ®¶o n y tån t¹i do −CLN(Mi,mi) = 1 v cã thÓ t×m ®−îc b»ng thuËt to¸n Euclide). CÇn ®Ó ý r»ng Miyi ≡ 1 (mod mi) víi 1 ≤ i ≤ r. B©y giê ta ®Þnh nghÜa h m ρ: Zm1 × . . . × Zmr ZM nh− sau ( )r ρ a ,...a r = ∑ a M y mod 1 M i=1 i i i Ta sÏ chøng tá r»ng ρ = π-1 , tøc l nã cho mét c«ng thøc t−êng minh ®Ó gi¶i hÖ ®ång d− thøc ban ®Çu. KÝ hiÖu X = ρ(a1, . . . ,ar) v cho 1 ≤ j ≤ r. XÐt sè h¹ng aiMiyi trong tæng trªn khi rót gän theo modulo mj. NÕu i = j th× aiMiyi ≡ ai (mod mi)
v× Miyi ≡ 1 (mod mi) MÆt kh¸c, nÕu i ≠ j th× aiMiyi ≡ 0(mod mj) do mi Mi trong tr−êng hîp n y. Bëi vËy chóng ta cã X ≡ ∑ a iM i y i (mod m j ) ≡ a i (mod m j ) Do ®iÒu n y ®óng ®èi víi mäi j, 1 ≤ j ≤ r, nªn X l nghiÖm cña hÖ ph−¬ng tr×nh ®ång d−. Tíi lóc n y cÇn ph¶i chøng tá r»ng nghiÖm X l duy nhÊt theo modulo M v ®iÒu n y cã thÓ ®−îc chøng tá b»ng c¸ch tÝnh to¸n ®¬n gi¶n. π l h m tõ mét miÒn cã lùc l−îng M sang mét miÒn cã lùc l−îng M. Ta võa míi chøng tá r»ng π l mét to n ¸nh. Bëi vËy π ph¶i còng l mét ®¬n ¸nh (tøc l phÐp t−¬ng øng 1 - 1) do miÒn x¸c ®Þnh v miÒn gi¸ trÞ cã cïng lùc l−îng. §iÒu ®ã kÐo theo π l mét song ¸nh v π-1 = p. Còng cÇn chó ý l π-1 l mét h m tuyÕn tÝnh cña c¸c biÕn a1,. . ., ar. Sau ®©y l mét vÝ dô lín h¬n ®Ó minh ho¹ VÝ dô 4.3 Gi¶ sö r = 3, m1 = 7, m2 = 11 v m3 = 13. Khi ®ã M = 1001. Ta tÝnh M1 = 143, M2 = 91 v M3 = 77 v sau ®ã tÝnh y1 = 5, y2 = 4 v y3 = 12. Khi ®ã h m π-1: Z7×Z11×Z13 Z1001 cã d¹ng: π-1(a1,a2,a3) = 715a1 +364a2 + 924a3 mod 1001 VÝ dô, nÕu x ≡ 5 (mod 7), x ≡ 3 (mod 11) v x ≡ 10 (mod 13) th× c«ng thøc trªn sÏ cho ta biÕt r»ng x = 715 × 5 + 364 × 3 + 924 × 10 mod 1001 = 13907 mod 1001 = 894 mod 1001 §iÒu n y cã thÓ kiÓm tra ®−îc b»ng c¸ch rót gän 894 theo modulo 7, 11 v 13. §Ó tham kh¶o sau n y, ta sÏ ghi c¸c kÕt qu¶ ë phÇn n y d−íi d¹ng mét ®Þnh lý
§Þnh lý 4.3 (§Þnh lý phÇn d− China) Gi¶ sö m1, . . . ,mr l c¸c sè nguyªn d−¬ng nguyªn tè cïng nhau tõng ®«i mét v cho a1, . . ., ar l c¸c sè nguyªn. Khi ®ã, hÖ r ®ång d− thøc x ≡ ai (mod mi) (1 ≤ i ≤ r ) sÏ cã mét nghiÖm duy nhÊt theo modulo M = m1× . . . × mr ®−îc cho theo c«ng thøc r x = ∑ a i M i y i mod M i =1 trong ®ã Mi = M/mi v yi = Mi-1 mod mi, víi 1 ≤ i ≤ r. 4.2.3. C¸c kiÕn thøc cÇn thiÕt kh¸c Sau ®©y sÏ nh¾c tíi mét kÕt qu¶ kh¸c trong lý thuyÕt nhãm s¬ cÊp: ®Þnh lý Lagrange. §Þnh lý n y cã liªn quan ®Õn c¸ch ®Ò cËp vÒ hÖ mËt RSA. Víi mét nhãm nh©n h÷u h¹n G, ta ®Þnh nghÜa cÊp cña mét phÇn tö g ∈ G l sè nguyªn d−¬ng m bÐ nhÊt sao cho gm = 1. Ta cã kÕt qu¶ sau ®©y (kh«ng chøng minh ). §Þnh lý 4.4 (Lagrange ) Gi¶ sö G l mét nhãm cÊp n v g ∈ G. Khi ®ã cÊp cña g l −íc cña n. Víi môc ®Ých ®−a ra, hÖ qu¶ sau rÊt quan träng. HÖ qu¶ 4.5 NÕu b ∈ Zn* th× bφ(n) ≡ 1 (mod n) Chøng minh: Zn* l nhãm nh©n cÊp φ(n). HÖ qu¶ 4.6 (Ferma) Gi¶ sö p l sè nguyªn tè v b ∈ Zp. Khi ®ã bp ≡ b (mod p). Chøng minh: NÕu p l sè nguyªn tè th× φ(n) = p-1. Bëi vËy, víi b≡0(mod p), kÕt qu¶ trªn ®−îc rót ra tõ hÖ qu¶ 4.5. Víi b ≡ 0 (mod p), kÕt qu¶ trªn vÉn ®óng do 0p ≡ 0 (mod 0). Cho tíi giê ta ® biÕt r»ng, nÕu p l sè nguyªn tè th× Zp* l mét nhãm cÊp p-1 v mét phÇn tö bÊt k× trong Zp* sÏ cã bËc l −íc cña p-1. Tuy nhiªn, nÕu p l sè nguyªn tè th× nhãm Zp* l nhãm cyclic: tån t¹i mét phÇn tö α ∈ Zp*
cã cÊp b»ng p-1. Ta kh«ng chøng minh kÕt qu¶ quan träng n y nh−ng sÏ ghi l¹i ®Ó tham kh¶o sau n y. §Þnh lý 4.7. NÕu p l sè nguyªn tè th× Zp* l nhãm cyclic. Mét phÇn tö α cã cÊp p-1 ®−îc gäi l phÇn tö nguyªn thuû modulo p. XÐt thÊy α l phÇn tö nguyªn thuû khi v chØ khi: {αi : 0 ≤ i ≤ p-2} = Zp* B©y giê gi¶ sö p – nguyªn tè v α - phÇn tö nguyªn thuû modulo p. Mét phÇn tö bÊt k× β ∈ Zp* cã thÓ ®−îc viÕt nh− sau: β = αi, trong ®ã 0 ≤ i ≤ p-2 (theo mét c¸ch duy nhÊt ). Kh«ng khã kh¨n cã thÓ chøng tá r»ng cÊp cña β = αi l : p -1 UCLN(p - 1, i) Nh− vËy b¶n th©n β l phÇn tö nguyªn thuû khi v chØ khi −CLN (p-1,i) = 1. §iÒu ®ã dÉn ®Õn l sè c¸c phÇn tö nguyªn thuû theo modulo p = φ(p-1). VÝ dô 4.4: Gi¶ sö p=13. B»ng c¸ch tÝnh c¸c luü thõa liªn tiÕp cña 2 ta cã thÓ thÊy r»ng 2 l phÇn tö nguyªn thuû theo modulo 13: 20 mod 13 =1 21 mod 13 =2 22 mod 13 =4 23 mod 13 =8 24 mod 13 =3 25 mod 13 =6 26 mod 13 =12 27 mod 13 =11 28 mod 13 =9 29 mod 13 =5 210 mod 13 =10 211 mod 13 =7 PhÇn tö 2i l nguyªn thuû khi v chØ khi −CLN(i,12) = 1; nghÜa l khi v chØ khi i = 1, 5, 7 hoÆc 11. Bëi vËy c¸c phÇn tö nguyªn thuû theo modulo 13 l 2, 6, 7 v 11. 4.3. hÖ mËt RSA B©y giê chóng ta cã thÓ m« t¶ hÖ mËt RSA. HÖ mËt n y sö dông c¸c tÝnh to¸n trong Zn, trong ®ã n l tÝch cña 2 sè nguyªn tè ph©n biÖt p v q. Ta nhËn thÊy r»ng φ(n) = (p-1)(q-1).
M« t¶ h×nh thøc cña hÖ mËt ®−îc cho trong h×nh 4.2 . Ta h y kiÓm tra xem c¸c phÐp m v gi¶i m cã ph¶i l c¸c phÐp to¸n nghÞch ®¶o cña nhau hay kh«ng. V× ab ≡ 1 (mod φ(n)) nªn ta cã ab = t φ(n) + 1 víi mét sè nguyªn t ≥ 1 n o ®ã. Gi¶ sö x ∈ Zp*; khi ®ã ta cã: (xb)a ≡ xtφ(n)+1 (mod n) ≡ (xφ(n))t x (mod n) ≡ 1t x (mod n) ≡ x (mod n) H×nh 4.2: HÖ mËt RSA Cho n = p.q trong ®ã p v q l c¸c sè nguyªn tè. §Æt P = C = Zn v ®Þnh nghÜa K = {(n,p,q,a,b): n = p.q, p,q l c¸c sè nguyªn tè, ab ≡ 1(mod φ(n))} Víi K = (n,p,q,a,b) ta x¸c ®Þnh eK (x) = xb mod n v dK (y) = ya mod n (x,y) ∈ Zn. C¸c gi¸ trÞ n v b ®−îc c«ng khai , c¸c gi¸ trÞ p,q,a ®−îc gi÷ bÝ mËt. ®óng nh− mong muèn. Xem nh− mét b i tËp, b¹n ®äc h y chøng tá r»ng (xb)a ≡ x (mod n) nÕu x ∈ Zn\ Zp*. Sau ®©y l mét vÝ dô nhá (tÊt nhiªn l kh«ng mËt ) vÒ hÖ mËt RSA. VÝ dô 4.5: Gi¶ sö Bob chän p = 101 v q = 113. Khi ®ã n = 11413 v φ(n) = 100×112 = 11200. V× 11200 = 26527, nªn cã thÓ dïng mét sè nguyªn b nh− mét sè mò m ho¸ khi v chØ khi b kh«ng chia hÕt cho 2, 5 hoÆc 7. (V× thÕ trong thùc tÕ Bob sÏ kh«ng ph©n tÝch φ(n), anh ta sÏ kiÓm tra ®iÒu kiÖn −CLN(φ(n),b) = 1 b»ng thuËt to¸n Euclide. Gi¶ sö Bob chän b = 3533, khi ®ã theo thuËt to¸n Euclide më réng: b-1 = 6597 mod 11200
Bëi vËy sè mò mËt ®Ó gi¶i m cña Bob l a = 6597. Bob sÏ c«ng bè n = 11413 v b = 3533 trong mét danh b¹. B©y giê, gi¶ sö Alice muèn göi b¶n râ 9726 tíi Bob. C« ta tÝnh 97263533 mod 11413 = 5761 råi göi b¶n m 5761 trªn kªnh. Khi ®ã Bob nhËn ®−îc b¶n m 5761, anh ta sö dông sè mò a mËt ®Ó tÝnh: 57616597 mod 11413 = 9762 (cho tíi lóc n y, c¸c phÐp m v gi¶i m cho hÖ mËt ® kh¸ phøc t¹p, tuy nhiªn ta sÏ th¶o luËn vÒ c¸c thuËt to¸n h÷u hiÖu cho c¸c phÐp to¸n n y ë phÇn sau). §é mËt cña hÖ RSA ®−îc dùa trªn gi¶ thiÕt l h m m ek(x)= xb mod n l h m mét chiÒu. Bëi vËy th¸m m sÏ kh«ng cã kh¶ n¨ng vÒ mÆt tÝnh to¸n ®Ó gi¶i m mét b¶n m . Cöa sËp cho phÐp Bob gi¶i m ®−îc chÝnh l th«ng tin vÒ phÐp ph©n tÝch thõa sè n (n = pq). V× Bob biÕt ph©n tÝch n y, anh ta cã thÓ tÝnh φ(n) = (p-1)(q-1) v råi tÝnh sè mò gi¶i m a b»ng c¸ch sö dông thuËt to¸n Euclide më réng. Sau n y chóng ta sÏ cßn tiÕp tôc nãi thªm vÒ vÊn dÒ n y. 4.4. Thùc hiÖn hÖ mËt RSA Cã nhiÒu khÝa c¹nh cÇn th¶o luËn vÒ hÖ mËt RSA bao gåm c¸c chi tiÕt vÒ viÖc thiÕt lËp hÖ mËt, tÝnh hiÖu qu¶ cña phÐp m v gi¶i m v ®é mËt cña hÖ. §Ó thiÕt lËp hÖ thèng, Bob sÏ tu©n theo c¸c b−íc ®−îc nªu trong h×nh 4.3. H×nh 4.3 ThiÕt lËp hÖ mËt RSA 1. Bob t¹o hai sè nguyªn tè lín p v q 2. Bob tÝnh n = p.q v φ(n) = (p-1)(q-1) 3. Bob chän mét sè ngÉu nhiªn b (0< b < φ(n)) sao cho −CLN(b,φ(n)) = 1 4. Bob tÝnh a = b-1 mod φ(n) b»ng c¸ch dïng thuËt to¸n Euclide 5. Bob c«ng bè n v b trong mét danh b¹ v chóng l m kho¸ c«ng khai.
ViÖc Bob tiÕn h nh c¸c b−íc n y nh− thÕ n o sÏ cßn ®−îc tiÕp tôc th¶o luËn trong ch−¬ng n y. C¸ch tÊn c«ng dÔ thÊy nhÊt hÖ mËt n y l th¸m m cè g¾ng ph©n tÝch n ra c¸c thõa sè nguyªn tè. NÕu thùc hiÖn ®−îc viÖc n y th× cã thÓ dÔ d ng tÝnh ®−îc φ(n) = (p-1)(q-1) råi tÝnh sè mò a tõ b nh− Bob l m (ng−êi ta pháng ®o¸n r»ng, viÖc ph¸ hÖ mËt RSA l t−¬ng ®−¬ng ®a thøc víi viÖc ph©n tÝch n, tuy nhiªn ®iÒu n y vÉn cßn ch−a ®−îc chøng minh. Hai b i to¸n ®−îc gäi l t−¬ng ®−¬ng ®a thøc nÕu tån t¹i mét thuËt to¸n thêi gian ®a thøc cho b i to¸n n y sÏ suy ra ®−îc sù tån t¹i mét thuËt to¸n thêi gian ®a thøc cho b i to¸n kia). V× thÕ hÖ mËt RSA ®−îc coi l mËt th× nhÊt thiÕt n = pq ph¶i l mét sè ®ñ lín ®Ó viÖc ph©n tÝch nã kh«ng cã kh¶ n¨ng vÒ mÆt tÝnh to¸n. C¸c thuËt to¸n ph©n tÝch hiÖn thêi cã kh¶ n¨ng ph©n tÝch c¸c sè cã 130 ch÷ sè thËp ph©n (chi tiÕt h¬n vÒ b i to¸n ph©n tÝch thõa sè nguyªn tè xem trong phÇn 4.8). V× vËy ®Ó ®¶m b¶o an to n nªn chän c¸c sè p v q chõng 100 ch÷ sè, khi ®ã n sÏ cã tíi 200 ch÷ sè. Mét v i ¸p dông phÇn cøng cña RSA sö dông m« ®un cã ®é d i 512 bit. Tuy nhiªn mét m« ®un 512 bit t−¬ng øng víi mét sè cã 154 ch÷ sè thËp ph©n (v× sè c¸c bit trong biÓu diÔn nhÞ ph©n cña mét sè nguyªn b¨ng log210 lÇn cña c¸c ch÷ sè thËp ph©n) v× vËy kh«ng ®ñ ®¶m b¶o an to n l©u d i. B©y giê t¹m thêi g¸c l¹i vÊn ®Ò t×m c¸c sè nguyªn tè cã 100 ch÷ sè ®Ó xem xÐt viÖc thùc hiÖn c¸c phÐp to¸n sè häc trong m v gi¶i m . PhÐp m (hoÆc gi¶i m ) sÏ xoay quanh phÐp lÊy luü thõa theo modulo n. V× n l mét sè rÊt lín nªn ta ph¶i sö dông sè häc lÊy chÝnh x¸c nhiÒu lÇn (multi – precision) ®Ó thùc hiÖn c¸c tÝnh to¸n trong Zn v thêi gian tÝnh to¸n cÇn thiÕt sÏ phô thuéc v o sè c¸c bÝt trong biÓu diÔn nhÞ ph©n cña n. Gi¶ sö n cã k bit trong biÓu diÔn nhÞ ph©n, tøc l k = log2 n + 1. Sö dông kÜ thuËt sè häc ë bËc trung häc, dÔ d ng thÊy r»ng mét phÐp céng hai sè nguyªn k bit cã thÓ thùc hiÖn trong thêi gian O(k) v mét phÐp nh©n cã thÓ thùc hiÖn trong thêi gian O(k2). Còng vËy, phÐp rót gän mét sè nguyªn theo modulo n (sè n y cã nhiÒu nhÊt l 2K bÝt )cã thÓ thùc hiÖn trong thêi gian O(k2) (®Ó thùc hiÖn phÐp chia v phÐp t×m phÇn d−). B©y giê gi¶ sö r»ng x,y∈Zn (ë ®©y xem r»ng 0 ≤ x,y ≤ n-1). Khi ®ã cã thÓ tÝnh xy mod n tr−íc tiªn b»ng viÖc tÝnh tÝch xy (l mét sè nguyªn 2k bÝt), råi rót gän cho modulo n. Hai b−íc n y cã thÓ thùc hiÖn trong thêi gian O(k2). Ta gäi phÐp tÝnh n y l nh©n modulo. B©y giê xÐt phÐp lÊy luü thõa theo modulo (tøc l tÝnh h m d¹ng xc mod n). Nh− nhËn xÐt ë trªn, c¶ hai phÐp m v gi¶i m trong RSA ®Òu l c¸c phÐp
luü thõa theo modulo. ViÖc tÝnh xc mod n cã thÓ thùc hiÖn b»ng c-1 phÐp nh©n modulo, tuy nhiªn khi c lín th× c¸ch tÝnh n y rÊt cång kÒnh. Chó ý r»ng c lín cì nh− φ(n) -1 (l mét sè lín cÊp luü thõa so víi k). Sö dông biÖn ph¸p "b×nh ph−¬ng v nh©n" ® biÕt sÏ l m gi¶m sè phÐp nh©n modulo cÇn thiÕt, ®Ó tÝnh x mod n nhiÒu nhÊt l 2l, trong ®ã l l sè c¸c bit trong biÔu diÔn nhÞ ph©n cña c. V× l ≤ k nªn cã thÓ coi xc mod n ®−îc thùc hiÖn trong thêi gian O(k3). V× thÕ c¸c phÐp m v gi¶i m ®−îc thùc hiÖn theo thêi gian ®a thøc (nh− mét h m cña k l sè c¸c bÝt trong mét b¶n râ (hoÆc b¶n m ). Trong thuËt to¸n “ b×nh ph−¬ng v nh©n”, ta coi r»ng sè mò b ®−îc biÓu thÞ ë d¹ng nhÞ ph©n nh− sau: l -1 b = ∑ bi 2i 2 i =0 Trong ®ã bi = 0 hoÆc 1, 0 ≤ i ≤ l-1. ThuËt to¸n ®Ó tÝnh z = xb mod n ®−îc m« t¶ ë h×nh 4.4. H×nh 2.5 ThuËt to¸n b×nh ph−¬ng v nh©n ®Ó tÝnh xb mod n 1. z=1 2. for i = l-1 down to 0 do 3. z = z2 mod n 4. if bi = 1 then z = z.x mod n DÔ d ng tÝnh ®−îc sè c¸c phÐp nh©n modulo thùc hiÖn bëi thuËt to¸n trªn. Lu«n lu«n ph¶i thùc hiÖn l phÐp b×nh ph−¬ng (ë b−íc 3). Sè phÐp nh©n trong b−íc 4 b»ng sè c¸c bit "1" trong biÓu diÔn nhÞ ph©n cña b (sè n y thuéc kho¶ng tõ 0 tíi l). Bëi vËy tæng sè phÐp nh©n modulo cÇn thùc hiÖn n»m trong kho¶ng tõ l tíi 2l. Ta sÏ minh ho¹ c¸ch sö dông thuËt to¸n trªn b»ng c¸ch quay trë l¹i vÝ dô 4.5. VÝ dô 4.5 (tiÕp):
Ta cã n = 11413 v sè mò m ho¸ c«ng khai b = 3533. Alice sÏ m ho¸ b¶n râ 9726 b»ng c¸ch tÝnh 97263533 mod 11413 theo thuËt to¸n “b×nh ph−¬ng v nh©n” nh− sau: i bi z 11 1 12× 9726 = 9726 10 1 97262 × 9726 = 2659 9 0 26592 = 5634 8 1 56342 × 9726 = 9167 7 1 91672 × 9726 = 4958 6 1 49582 × 9726 = 7783 5 0 77832 = 6298 4 0 62982 = 4629 3 1 46292 × 9726 = 10185 2 1 101852 × 9726 = 105 1 0 1052 = 11025 0 1 110252 × 9726 = 5761 Nh− vËy b¶n m l 5761. CÇn ph¶i nhÊn m¹nh r»ng, nh÷ng øng dông phÇn cøng hiÖu qu¶ nhÊt hiÖn thêi cña RSA chØ ®¹t ®−îc tèc ®é m ho¸ chõng 600Kb/s (sö dông c¸c m« ®un 512 bÝt) so víi DES cã tèc ®é 1 Gb/s. Nãi c¸ch kh¸c RSA chËm h¬n kho¶ng 1500 lÇn so víi DES. §Õn ®©y, ta chØ míi xÐt ®−îc c¸c phÐp m ho¸ v gi¶i m cho RSA. §Ó thiÕt lËp hÖ mËt RSA, ta cßn ph¶i xÐt viÖc t¹o c¸c sè nguyªn tè p v q (b−íc 1), b−íc n y sÏ ®−îc nghiªn cøu ë phÇn sau. B−íc 2 kh¸ ®¬n gi¶n v ®−îc thùc hiÖn trong thêi gian O((log n)2). C¸c b−íc 3 v 4 xoay quanh thuËt to¸n Euclide, v× thÕ sÏ xÐt qua vÒ ®é phøc t¹p cña thuËt to¸n n y. Gi¶ sö ta ph¶i tÝnh −CLN cña r0 v r1, trong ®ã r0 > r1 . Trong mçi b−íc lÆp ®Òu ph¶i tÝnh th−¬ng v phÇn d−, ®iÒu n y cã thÓ thùc hiÖn ®−îc trong thêi gian O((log r0)2). NÕu t×m ®−îc giíi h¹n trªn cho sè phÐp lÆp th× ta sÏ cã ®−îc giíi h¹n cho ®é phøc t¹p cña thuËt to¸n. KÕt qu¶ n y ® ®−îc nªu trong ®Þnh lý LamÐ. §Þnh lý kh¼ng ®Þnh r»ng nÕu s l sè c¸c phÐp lÆp th× f3+2 ≤ r0 , trong ®ã fi l sè Fibonacci thø i . V×
1 + 5  fi =   2     Nªn ®iÒu ®ã kÐo theo s l O(log r0). §iÒu n y chøng tá r»ng thêi gian ch¹y cña thuËt to¸n Euclide l O((log n)3) (trªn thùc tÕ, b»ng c¸c ph©n tÝch chi tiÕt h¬n, cã thÓ chøng tá r»ng thêi gian ch¹y chØ l O((log n)2). 4.5. 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è). Trong thùc tÕ, ph−¬ng c¸ch thùc hiÖ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¸c suÊt Monte- Carlo thêi gian ®a thøc (ch¼ng h¹n nh− thuËt to¸n Miller- Rabin hoÆc l thuËt to¸n Solovay- Strasen). C¶ hai thuËt to¸n trªn ®Òu ®−îc tr×nh b y trong phÇn n y. Chóng l c¸c thuËt to¸n nhanh (tøc l mét sè nguyªn n ®−îc kiÓm tra trong thêi ®a thøc theo log2n, 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Ët to¸n cho r»ng n l sè nguyªn tè trong khi thùc tÕ n l hîp 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¶o luË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ét sè 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ín h¬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®un 512 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¸c suÊt sÏ t¨ng gÊp ®«i tíi kho¶ng 2/177). Bìi vËy trªn thùc tÕ, ho n to n cã kh¶ n¨ng t¹o ®−îc c¸c nguyªn tè ®ñ lín v do ®ã vÒ mÆt thùc thÓ ta cã thÓ thiÕt lËp ®−îc mét hÖ mËt RSA. Sau ®©y sÏ tiÕp tôc xem xÐ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 trong ®ã mét c©u hái cÇn ®−îc tr¶ lêi “cã” hoÆc “kh«ng”. Mét thuËt to¸n x¸c suÊt l mét thuËt to¸n bÊt kú cã sö dông c¸c sè ngÉu nhiªn (ng−îc l¹i, thuËt to¸n kh«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 cho c¸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¸c suÊt cho mét b i to¸n quyÕt ®Þnh, trong ®ã c©u tr¶ lêi “cã” lu«n lu«n l ®ó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êi l “cã” th× thuËt to¸n cã c©u tr¶ lêi sai “kh«ng” víi x¸c suÊt kh«ng lí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×nh 4.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Ët to¸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ét thuËt to¸n Monte-Carlo ®Þnh h−íng “cã” cho b i to¸n hîp sè v x¸c xuÊ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èi thiÓ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¬n thuËt to¸n Soloway-Strasson (S-S) nh−ng ta sÏ xÐt thuËt to¸n S-S tr−íc v× nã dÔ hiÓu h¬n vÒ kh¸i niÖm, ®ång thêi l¹i liªn quan tíi mét sè vÊn ®Ò cña lý thuyÕt sè (m ta sÏ cßn dïng trong c¸c ch−¬ng tr×nh sau). 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Æng d− kh«ng bËc hai theo modulo p nÕu x ??? 0 (mod p) v x kh«ng ph¶i l 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) =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 2 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×nh 4.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¸c thÆ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 hai theo 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× b 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¸c thÆng d− bËc hai nhê sö dông kü thuËt “b×nh ph−¬ng v nh©n” cho phÐp lÊy luü thõa theo modulo p. §é phøc t¹p cña thuËt to¸n kho¶ng O((log p)3). Sau ®©y tiÕp tôc ®−a ra mét sè ®Þnh nghÜa tõ lý thuyÕt sè: § Þnh nghÜa 4.3 Gi¶ sö p l mét sè nguyª n tè lÎ. Víi mét sè nguyª n bÊt kú a ≥ 0 , a ta dÞnh nghÜa ký hiÖu Legendre   nh− sau :  p 0 nÕu a ≡ 0 (mod p) a   = 1 nÕu a l thÆng d− bËc hai theo modulo p  p - 1 nÕu a l thÆng d− kh«ng bËc hai theo modulo p Ta ® biÕt l a(p-1)/2≡ 1 (mod p) khi v chØ khi a l mét thÆng d− bËc hai theo modulo p. NÕu a l béi cña p th× râ r ng a(p-1)/2≡ 0(mod p). Cuèi cïng, nÕu a l mét thÆng d− kh«ng bËc hai theo modulo p th× a(p-1)≡ -1 (mod p) v× ap- 1 ≡1(mod p). Bëi vËy, ta cã kÕt qu¶ cho phÐp x©y dùng mét thuËt to¸n h÷u hiÖu ®Ó ®¸nh gi¸ c¸c ký hiÖu Legendre nh− sau §Þnh Lý 4.9. a   Gi¶ sö p l mét sè nguyªn tè. Khi ®ã p   ≡ a(p-1)/2 (mod p). Sau ®©y l mét ®Þnh nghÜa tæng qu¸t ho¸ cho ký hiÖu Legendre. §Þnh nghÜa 4.4. Gi¶ sö n l mét sè nguyªn d−¬ng lÎ v ph©n tÝch theo c¸c luü thõa nguyªn tè cña n l p1e1 ....... pKek . Gi¶ sö a ≥ 0 l mét sè nguyªn. a   r