Các thuật toán phân tích thừa số

Chia sẻ: Nguyen Hoang Tung Tung | Ngày: | Loại File: DOC | Số trang:17

Thêm vào BST

Báo xấu

125
lượt xem 12
download

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

Đã có một khối lượng khổng lồ các tìa liệu về các thuật toán phân tích thừa số và việc nghiên cứu kỹ lưỡng sẽ đòi hỏi phải có một cuốn sách dày hơn quyển sách này. ở đây chỉ cố gắng đưa ra một cái nhìn khái quát bao gồm việc thảo luận sơ lược về các thuật toán phân tichs thừa số tốt nhất hiện thời và cách sử dụng chúng trong thực tế. Ba thuật toán hiệu quả nhất trên các số thật lớn là sàng bậc hai, thuật toán đường cong elliptic và sàng trường số....

Chủ đề:

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

Lưu

Nội dung Text: Các thuật toán phân tích thừa số

H×nh 4.14. Ph©n tÝch modulus cña rabin víi mét ch¬ng tr×nh con gi¶i m· cho tríc. 1. Chän mét sè ngÉu nhiªn r , 1≤ r ≤ n- 1 2- 2 2. TÝnh y = r B /4 mod n 3. Gäi ch¬ng tr×nh con A(y) ®Ó t×m b¶n gi¶i m· x 4. TÝnh x1 = x+B/2 5. If x1 ≡ ± r (mod n) then quit (kh«ng thµnh c«ng) Else UCLN(x1+r,n)=p hoÆc q (thµnh c«ng) Bëi vËy gi¸ trÞ x sÏ thu ®îc ë bíc 3. TiÕp theo xÐt bíc 4. NhËn thÊy r»ng x12 = r2 (mod n). §iÒu ®ã dÉn tíi x1 ≡ ± r (mod n) hoÆc x1 ≡ ± wr (mod n), trong ®ã w lµ mét trong c¸c c¨n bËc hai kh«ng tÇm thêng cña 1 modulo n. Trong trêng hîp thø hai ta cã : n 1-r )(x1+r) (x song n kh«ng ph¶i lµ íc cña mét thõa sè nµo ë vÕ ph¶i. Bëi vËy, viÖc tÝnh UCLN(x1 +r,n)(hoÆc UCLN(x1-r, n)) ph¶i dÉn tíi hoÆc p hoÆc q, vµ nh vËy phÐp ph©n tÝch n ®îc hoµn thµnh. Ta sÏ tÝnh x¸c suÊt thµnh c«ng cña thuËt to¸n nµy trªn tÊt c¶ (n-1) phÐp chän ngÉu nhiªn r. Víi hai thÆng d kh¸c kh«ng r1 vµ r2 , ®Þnh nghÜa: r1 ~ r2 ⇔ r12 ≡ r22 (mod n) DÔ dµng thÊy r»ng r ~ r víi mäi r, r1 ~ r2 còng cã nghÜa lµ r2 ~ r1; r1 ~ r2 vµ r2 ~ r3 th× r1 ~ r3 . §iÒu ®ã cho ta thÊy r»ng quan hÖ ~ lµ mét quan hÖ t¬ng ®¬ng. C¸c líp t¬ng ®¬ng cña Zn\{0} ®Òu cã bèn phÇn tö, líp t¬ng ®¬ng chøa r lµ tËp [r] = {± r, ± wr (mod n)}
trong ®ã w lµ c¨n bËc hai kh«ng tÇm thêng cña 1 modulo n. Trong thuËt to¸n ®îc tr×nh bµy ë h×nh 4.14, hai gi¸ trÞ r bÊt kú trong cïng mét líp t¬ng ®¬ng sÏ dÉn tíi cïng mét gi¸ trÞ y. B©y giê xÐt gi¸ trÞ x thu ®îc tõ ch¬ng tr×nh con A khi ®· biÕt y. Ta cã: [y]={± y, ± wy} NÕu r=± y th× thuËt to¸n kh«ng thµnh c«ng; trong khi nÕu r=± wy th× thuËt to¸n sÏ thµnh c«ng. V× r ®îc chän ngÉu nhiªn, nªn mét gi¸ trÞ bÊt kú trong bèn gi¸ trÞ cã thÓ ®Òu cïng kh¶ n¨ng. Ta kÕt luËn r»ng x¸c suÊt thµnh c«ng cña thuËt to¸n lµ 1/2. §iÒu thó vÞ lµ hÖ mËt rabin lµ an toµn ®èi víi ph¬ng ph¸p tÊn c«ng b¶n râ chän läc, mhmg hÖ nµy l¹i hoµn toµn kh«ng an toµn®èi víi ph¬ng ph¸p tÊn c«ng b¶m m· chän läc. ThuËt to¸n ë h×nh 4.14, phÇn dïng ®Ó chøng minh sù an toµn ®èi víi phÐp tÊn c«ng b¶n râ chän läc còng cã thÓ ®îc dïng ®Ó ph¸ hÖ mËt Rabin khi thùc hiÖn tÊn c«ng b¶n m· chän läc!. Trong ph¬ng ph¸p tÊn c«ng b¶n m· chän läc, ch¬ng tr×nh con A ®îc thay b»ng thuËt to¸n gi¶i m· cña Bob. 4.8. C¸c thuËt to¸n ph©n tÝch thõa sè. §· cã mét khèi lîng khæng lå c¸c t×a liÖu vÒ c¸c thuËt to¸n ph©n tÝch thõa sè vµ viÖc nghiªn cøu kü lìng sÏ ®ßi hái ph¶i cã mét cuèn s¸ch dµy h¬n quyÓn s¸ch nµy. ë ®©y chØ cè g¾ng ®a ra mét c¸i nh×n kh¸i qu¸t bao gåm viÖc th¶o luËn s¬ lîc vÒ c¸c thuËt to¸n ph©n tichs thõa sè tèt nhÊt hiÖn thêi vµ c¸ch sö dông chóng trong thùc tÕ. Ba thuËt to¸n hiÖu qu¶ nhÊt trªn c¸c sè thËt lín lµ sµng bËc hai, thuËt to¸n ®êng cong elliptic vµ sµng trêng sè. C¸c thuËt to¸n næi tiÕng kh¸c (nh÷ng thuËt to¸n to¸n cã tríc) bao gåm ph¬ng ph¸p ρ vµ thuËt to¸n p-1 cña Pollard, thuËt to¸n p+1 cña Williams, thuËt to¸n liªn ph©n sè vµ dÜ nhiªn c¶ nh÷ng phÐp chia thö.
Trong toµn bé phÇn nµy, xchóng ta cá×ng sè nguyªn n cÇn ph©n tÝch ra thõa sè lµ mét sè lÎ. PhÐp chia thö bao gåm viÖc chia n cho tõng sè nguyªn lÎ cho tíi [ n] . NÕu n < 10 12 th× ®©y lµ mét ph¬ng ph¸p ph©n tÝch thõa sè hîp lý mét c¸ch hoµn h¶o, tuy nhiªn víi n lín h¬n nãi chung ta ph¶i dïng c¸c kü thuËt tinh tÕ h¬n. 4.8.1. Ph¬ng ph¸p p-1 ThuËt to¸n p-1 cña Pollar (®a ra vµo n¨m 1947) lµ mét thÝ dô vÒ mét thuËt to¸n ®¬n gi¶n ®¬n khi ®îc ¸p dông víi c¸c sè nguyªn lín. ThuËt to¸n nµy (tr×nh bµy trªn h×nh 4.15) cã hai ®Çu vµo: sè nguyªn lÎ n cÇn ®îc ph©n tÝch vµ mét cËn B. Cã thÓ m« t¶ thuËt to¸n nh sau: H×nh 4.15. ThuËt to¸n ph©n tÝch thõa sè p-1. §Çu vµo: n vµ B 1. a=2 2. For j=2 to B do a = aj mod n 3. d = UCLN(a-1,n) 4. if 1 < d < n then d lµ mét thõa sè cña n else kh«ng t×m ®îc thõa sè cña n (kh«ng thµnh c«ng) Gi¶ sö p lµ íc mhuyªn tè cña n vµ q ≤ B , víi mçi mò nguyªn tè p(p-1). Khi ®ã (p-1)B! ë cuèi vßng lÆp for (bíc 2)
a ≡ 2B! (mod n) nªn a ≡ 2B! (mod p) v× p nªn theo ®Þnh ý Fermat ta cã : n. ≡  ≡   ≡ 135979 × 115979 Trong trêng hîp nµy, phÐp ph©n tÝch sÏ thµnh c«ng do 135978 chØ gåm c¸c thõa sè nguyªn tè nhá: V× thÕ 135978 = 2 × 3 × 131 × 173 nÕu lÊy B ≥ 173 th× ch¾c ch¨n r»ng 135978 nh mong B! muèn. Trong thuËt to¸n cã (B-1) luü thõa theo modulo, mçi luü cÇn nhiÒu nhÊt lµ 2log2B phÐp nh©n modulo dïng thuËt to¸n b×nh ph¬ng vµ nh©n. ViÖc tÝnh íc chung lín nhÊt cã thÓ thùc hiÖn trong thêi gian O((log n)3) b»ng thuËt to¸n Euclide. Bëi vËy, ®é phøc t¹p cña thuËt to¸n lµ O(B logB (log n) 2 +(log n)3). NÕu B lµ O((log n)i) víi mét sè nguyªn i x¸c ®Þnh nµo ®ã th× thuËt to¸n thùc sù lµ thuËt to¸n thêi gian ®a thøc, tuy nhiªn víi phÐp chän B nh vËy, x¸c suÊt thµnh c«ng sÏ rÊt nhá. MÆt kh¸c, nÕu t¨ng kÝch thíc cña B lªn thËt lín (ch¼ng h¹n tíi ?????????????? ) th× thuËt to¸n sÏ thµnh c«ng nhng nã sÏ kh«ng thùc hiÖn nhanh h¬n phÐp chia thö. Nh vËy, ®iÓm bÊt lîi cña thuËt to¸n nµy lµ nã yªu cÇu n ph¶i cã íc nguyªn tè p sao cho (p-1) chØ c¸c thõa sè nguyªn tè bÐ. Ta cã thÓ dÔ dµng x©y dùng ®îc hÖ mËt RSA víi modulus n= pq h¹n chÕ ®îc viÖc ph©n tÝch theo ph¬ng ph¸p nµy. Tríc tiªn t×m mét sè nguyªn tè lín p1 sao cho p= 2p1+1 còng lµ mét sè nguyªn tè vµ mét sè nguyªn tè lín q1 sao cho q= 2q1+1 còng lµ mét sè nguyªn tè (nhê dïng mét trong c¸c thuËt to¸n kiÓm tra tÝnh nguyªn tè Monte-Carlo nªu trong phÇn 4.5). Khi ®ã modulo cña RSA n= pq sÏ chèng ®îc c¸ch ph©n tÝch theo ph¬ng ph¸p p-1.
ThuËt to¸n ®êng cong elliptic m¹nh h¬n (®îc Lenstra x©y dùng vµo nh÷ng n¨m 1980) trªn thùc tÕ lµ sù tæng qu¸t ho¸ cña ph¬ng ph¸p p-1. Ta sÏ kh«ng th¶o luËn vÒ lý thuyÕt ë ®©y mµ chØ nhÊn m¹nh r»ng, thµnh c«ng cña ph¬ng ph¸p ®- êng cong elliptic tuú thuéc vµo t×nh huèng t¬ng tù : mét sè nguyªn “gÇn víi” p chØ cã c¸c thõa sè nguyªn tè bÐ. Trong khi ph¬ng ph¸p p-1 phô thuéc vµo quan hÖ trong Zp th× ph¬ng ph¸p ®êng cong elliptic phô thuéc vµo c¸c nhãm x¸c ®Þnh trªn c¸c ®êng cong elliptic theo modulo n. 4.8.2. ThuËt to¸n Dixon vµ sµng bËc hai ThuËt to¸n Dixon ®îc x©y dùng trªn ý tëng ®¬n gi¶n mµ ta ®· thÊy trong hÖ mËt Rabin. ý tëng ®ã lµ: nÕu t×m ®îc x ≠ ± y (mod n) sao cho x2≡ y2 (mod n) th× UCLN(x-y,n) lµ íc kh«ng tÇm thêng cña n. Ph¬ng ph¸p nµy sö dông c¬ së nh©n tö lµ mét tËp b chøa c¸c sè nguyªn tè bÐ. Tríc tiªn ta nhËn ®îc mét vµi sè nguyªn x sao cho tÊt c¶ c¸c thõa sè nguyªn tècña x2 (mod n) n»m trong c¬ së b (c¸ch thùc hiÖn ®iÒu nµy sÏ ®îc th¶o luËn sau). ý tëng thùc hiªn ë ®©y lµ lÊy tÝch cña mét vµi gi¸ trÜ sao cho mçi sè nguyªn tè trong c¬ së ®îc sö dông mét sè ch½n lÇn. §iÒu nµy dÉn ®Õn mét ®ång d thøc d¹ng mong muèn x2 ≡ y2 (mod n) mµ ta hy väng sÏ ®a ®Õn viÖc ph©n tÝch n. Ta sÏ minh ho¹ b»ng mét vÝ dô ®· ®îc dù tÝnh kü lìng. VÝ dô 4.15 Gi¶ sö n=15770708441(gi¸ trÞ n nµy ®· dïng trong vÝ dô 4.14). Gi¶ sö b = {2,3,5,7,11,13}. XÐt ba ®ång thøc sau: 8340934156 2 ≡ 3 × 7 (mod n) 12044942944 2 ≡ 1 × 7 × 13 (mod n) 2773700011 2 =2 × 3 × 13 (mod n) NÕu lÊy tÝch cña ba ®ång d thøc trªn:
(8340934156 × 2044942944× 2773700011) 2 ≡ (2× 3× 7× 13)2 (mod n) Rót gän c¸c biÓu thøc bªn trong c¸c dÊu ngÆc theo modulo n, ta cã: 9503435785 2 ≡ 5462 (mod n) Sau ®ã tÝnh: UCLN(9503435785-546, 15770708441)=115759 Ta thÊy 115759 lµ mét thõa sè cña n. Gi¶ sö B = {p1, . . . .pB}lµ mét c¬ së nh©n tö. Gi¶ sö c lín h¬n B mét chót (ch¼ng h¹n C=B+10) vµ gi¶ sö ta ®· cã C ®ång d thøc: α α α xj2 ≡ p1 1j × p2 2j × . . .× pB Bj(mod n) víi 1≤ j ≤ C. Víi mçi j xÐt vÐctor : aj = (α1j mod 2, α2j mod 2, . . ., αBj mod 2) ∈ (Z2)B NÕu cã thÓ t×m ®îc mét tËp con c¸c aj sao cho tæng theo modulo 2 lµ vector (0,. . ., 0) th× tÝch cña c¸c xj t¬ng øng sÏ sö dông mçi nh©n tö trong B mét sè ch½n lÇn. Ta sÏ minh ho¹ b»ng c¸ch trë l¹i vÝ dô 4.15. Trong trêng hîp nµy nÕu C < B, vÉn t×m ®îc sù phô thuéc tuyÕn tÝnh. VÝ dô 4.15 (tiÕp) Cho 3 vector a1, a2, a3 : a1 =(0, 1, 0, 1, 0, 0) a2 =(1, 0, 0, 1, 0, 1) a3 = (1, 1, 0, 0, 0, 1) DÔ dµng thÊy r»ng: a1 +a2 + a3 = (0, 0, 0, 0, 0, 0) mod 2
§©y lµ lý do cho thÊy ®ång d thøc (thiÕt lËp theo tÝch) sÏ ph©n tÝch thµnh c«ng ®îc n. NhËn thÊy r»ng, bµi to¸n t×m mét tËp con C vector a1, a2, . . ., aC sao cho tæng theo modulo 2 lµ mét vector toµn chøa sè 0 chÝnh lµ bµi to¸n t×m sù phô thuéc tuyÕn tÝnh (trªn Z2) cña c¸c vector nµy. Víi C > B, sù phô thuéc tuyÕn tÝnh nµy nhÊt ®Þnh ph¶i tån t¹i vµ ta cã thÓ dÔ dµng t×m ®îc b»ng ph- ¬ng ph¸p lo¹i trõ Gaux. Lý do gi¶i thÝch t¹i sao lÊy C > B+1 lµ do kh«ng cã g× b¶o ®¶m ®Ó mét ®ång d thøc cho tríc bÊt kú sÏ t¹o ®îc ph©n tÝch n. Kho¶ng 50% thuËt to¸n cho ra x ≡ ± y (mod n). Tuy nhiªn nÕu C > B+1 th× cã thÓ nhËn ®îc mét vµi ®ång d thøc nh vËy. (N¶y sinh tõ c¸c phô thuéc tuyÕn tÝnh kh¸c cña c¸c aj). Hy väng lµ Ýt nhÊt mét trong c¸c ®ång d thøc kÕt qu¶ sÏ dÉn ®Õn viÖc ph©n tÝch n. VÊn ®Ò cßn l¹i lµ ph¶i lµm thÕ nµo ®Ó nhËn ®îc c¸c sè nguyªn xj mµ c¸c gi¸ trÞ xj2 mod n cã thÓ ph©n tÝch hoµn toµn trªn c¬ së b. Mét vµi ph¬ng ph¸p cã thÓ thùc hiÖn ®îc ®iÒu ®ã. BiÖn ph¸p sµng bËc hai do Pomerance ®a ra dïng c¸c sè nguyªn d¹ng xj=j +n [ ] ,j=1,2...... Tªn “sµng bËc hai” lÊy tõ thñ tôc sµng (kh«ng m« t¶ ë ®©y) dïng ®Ó x¸c ®Þnh c¸c xj ph©n tÝch ®îc trªn b. ë ®©y dÜ nhiªn lµ mét sù tho¶ hiÖp: nÕu B = | B | lµ mét sè lín th× thÝch hîp h¬n c¶ lµ nªn ph©n tÝch sè nguyªn x j trªn b. Tuy nhiªn khi B cµng lín th× ta cµng ph¶i gom nhiÒu ®ång d thøc h¬n tríc khi cã thÓ t×m ®îc mét quan hÖ phô thuéc. Lùa chän tèi u cho B xÊp xØ b»ng ?????????????????? vµ ®iÒu nµy dÉn ®Õn thêi gian thùc hiÖn cì ?????????????????????????? Sµng trêng sè lµ thuËt to¸n ph©n tÝch míi h¬n (tõ cuèi nh÷ng n¨m 80) ThuËt to¸n nµy còng ph©n tÝch n b»ng c¸ch
x©y dùng mét ®ång d thøc x2 ≡ y2 (mod n), song nã ®îc thùc hiÖn b»ng c¸c tÝnh to¸n trªn vµnh c¸c sè ®¹i sè. 4.8.3.C¸c thuËt to¸n ph©n tÝch trªn thùc tÕ. Thêi gian ch¹y tiÖm cËn cña c¸c thuËt to¸n sµng bËc hai, ®¬ng cong elliptic vµ sµng trêng sè nh sau: Sµng bËc hai O?????????????// §êng cong elliptic ?????????????? Sµng trêng sè ????????????????? trong ®ã O(1) lµ hµm cña n, hµm nµy tiÕn tíi 0 khi n ∞ vµ p lµ thõa sè nguyªn tè nhá nhÊt cña n. Trong trêng hîp xÊu nhÊt p ≈ ?????????, thêi gian ch¹y tiÖm cËn cña c¸c thuËt to¸n ®êng cong elliptic vµ sµng bËc hai c¬ b¶n nh nhau. Tuy nhiªn trong trêng hîp nµy, ph¬ng ph¸p sµng bËc hai nãi chung tréi h¬n ph¬ng ph¸p ®êng cong elliptic. Ph¬ng ph¸p ®¬ng cong elliptic hiÖu qu¶ h¬n nÕu c¸c thõa sè nguyªn tè cña n cã kÝch thíc kh¸c nhau. Mét sè rÊt lín ®· ®îc ph©n tÝch b»ng ph¬ng ph¸p ®êng cong elliptic lµ tham sè Fermat (22048-1) (®îc Brent thùc hiÖn n¨m 1988) . §Ó ph©n tÝch c¸c modulo RSA (trong ®ã n=pq, p vµ q lµ c¸c sè nguyªn tè cã cïng kÝch thíc), sµng bËc hai lµ mét thuËt to¸n thµnh c«ng nhÊt hiÖn nay. Sau ®©y lµ mét sè kÕt qu¶ quan träng. Vµo n¨m 1983, thuËt to¸n sµng bËc hai ®· ph©n tÝch thµnh c«ng mét sè cã 69 ch÷ sè, sè nµy lµ mét thõa sè cña 2251-1 (do Davis, Holdredye vµ Simmons thùc hiÖn). Qu¸ tr×nh nµy tiÕp tôc trong nh÷ng n¨m 80 vµ ®Õn n¨m 1989 ®· cã thÓ ph©n tÝch ®îc c¸c sè cã tíi 106 ch÷ sè theo ph¬ng ph¸p nµy( do Lenstra vµ Manasse thùc hiÖn) nhê ph©n bè c¸c phÐp tÝnh cho hµng tr¨m tr¹m lµm viÖc t¸ch biÖt (ngêi ta gäi ph¬ng ph¸p nµy lµ “ph©n tÝch thõa sè b»ng th ®iÖn tö”). GÇn ®©y h¬n, 4/1994 Atkins, Graff, Lenstra vµ Leyland ®· ph©n tÝch ®îc mét sè 129 ch÷ sè (®îc gäi lµ RSA-129) nhê sö dông sµng bËc hai (c¸c sè RSA-100, RSA-110,....,RSA-500 lµ mét danh s¸ch c¸c modulo RSA ®îc c«ng bè trªn internet nh lµ sù th¸ch ®è cho c¸c thuËt to¸n ph©n tÝch. Mçi mét sè [ n]
RSA-d lµ mét sè d ch÷ sè, sè nµy lµ tÝch cña hai sè nguyªn tè cã kÝch thíc xÊp xØ nhau). ViÖc ph©n tÝch sè RSA-129 cÇn hµng tr¨m tÝnh to¸n víi m¸y tÝnh 5000 MIPS (triÖu lÖnh/s) ®îc thùc hiÖn bëi 600 nhµ nghiªn cøu trªn toµn thÕ giíi. Sµng trêng sè lµ mét thuËt to¸n míi nhÊt trong ba thuËt to¸n to¸n. Nã cã vÎ cã tiÒm n¨ng lín do thêi gian ch¹y tiÖm cËn cña nã nhanh h¬pn c¶ hai thuËt to¸n trªn. ThuËt to¸n nµy hiÖn vÉn cßn trong thêi k× nghiªn cøu, tuy nhiªn ngêi ta ®· dù ®o¸n lµ sµng trêng sè ph¶i chøng tá lµ nhanh h¬n víi c¸c sè cã trªn 125-130 ch÷ sè. N¨m 1990, Lenstra, Manase vµ Pollaid ®· dïng sµng trêng sè ®Ó ph©n tÝch (2512 - 1) thµnh ba sè nguyªn tè cã 7, 49 vµ 99 ch÷ sè. 4.9. chó gi¶i vµ tai liªu dÉn ý tëng vÒ mËt m· kho¸ c«ng khai ®· ®îc Diffie vµ Hellman nªu ra vµo 1976. MÆc dï [HD 76A] lµ tµi liÖu ®îc trÝch dÉn nhiÒu nhÊt nh÷ng bµi b¸o Héi nghÞ [DH 76] thùc tÕ ®· xuÊt hiÖn sím h¬n mét chót. HÖ mËt RSA ®îc Rivest, Shamis vµ Adleman [RSA 78] ph¸t minh. HÖ mËt Rabin ®îc m« t¶ trong [RA 79]: mét hÖ t¬ng tù víi phÐp gi¶i m· kh«ng mËp mê ®· ®îc Willians t×m ra trong [Wi 80]. B¹n ®äc nÕu tham kh¶o [Di 92] lµ mét bµi b¸o tæng qu¸t vµ mÆt m· kho¸ c«ng khai cña Diffie. PhÐp thö Solovay- Stassen lÇn ®Çu tiªn m« t¶ trong [SS 77]. PhÐp thö Miller- Rabin ®îc nªu trong[Mi 76] vµ [Ra 80]. Th¶o luËn cña chóng ta vÒ c¸c x¸c suÊt sai dùa trªn c¸c nhËp xÐt cña Brassard vµ Bratly [BB 88A,ξ 8.6] (còng cã thÓ trong[BBCGP 88]. C¸c cËn tèi nhÊt hiÖn thêi vÒ x¸c suÊt sai cña thuËt to¸n Miller- Rabin cã thÓ t×m thÊy trong [DLP 93]. Néi dung cña phÇn 4.6 dùa trªn quan ®iÓm cña Salomaa [SA 90, c¸c trang 143-154]. PhÐp ph©n tÝch n víi sè mò gi¶i m· cho tríc ®îc nªu trong [DE 84]: c¸c kÕt qu¶ vÒ th«ng tin riªng bÞ lé bëi RSA lÊy tõ [GMT 82]. Nh ®· nãi trªn, ®· cã rÊt nguån tµi liÖu vÒ c¸c thuËt to¸n ph©n tÝch. Pomerance [Po 90]lµ tæng qu¸t vÒ phÕp ph©n tÝch. Lenstra vµ Lenstra [LL 90] lµ mét b¸o c¸o hay lµ vÒ c¸c thuËt to¸n lý thuyÕt nãi chung. Bressoud [Br 89] lµ mét gi¸o
tr×nh s¬ cÊp vÒ phÐp ph©n tÝch thõa sè vµ phÐp kiÓm tra tÝnh nguyªn tè. C¸c gi¸o trinh vÒ mËt m· cã chó träng tíi lý thuyÕt sè lµ c¸c s¸ch cña Koblitz [Ko 87] vµ cña Kranakis [Kr 86]. Cßn s¸ch cña Lenstra vµ Lenstra [LL 93] lµ mét chuyªn th¶o tèt vÒ sµng trêng sè. C¸c bµi tËp 4.7- 4.9 cho mét sè vÝ dô vÒ trôc trÆc trong giao thøc (protocol). VÒ vÊn ®Ò nµy cã thÓ xem mét bµi b¸o rÊt hay cña Moore [Mo 92]. Bµi tËp 4.1. H·y dïng thuËt to¸n Euclide mì réng ®Ó tÝnh c¸c phÇn tö nghÞch ®¶o rau: -1 a) 17 mod 101 -1 b) 357 mod 1234 -1 c) 3125 mod 9987 4.2. Gi¶i hÖ ph¬ng tr×nh ®ång d sau: x ≡ 12 (mod 25) x ≡ 9 (mod 26) x ≡ 23 (mod 27) 4.3. Gi¶i hÖ ph¬ng tr×nh ®ång d sau 13x ≡ 4 (mod 99) 15x ≡ 56 (mod 101) gîi ý: tríc tiªn h·y dïng thuËt to¸n Euclide mì r«ng råi ¸p dông ®Þnh lý phÇn d cña China. 4.4. Ta nghiªn cøu mét sè tÝnh chÊt cña c¸c c¨n nguyªn thuû a) 97 lµ mét sè nguyen tè. H·y chøng minh r»ng x ≠ 0 lµ mét c¨n nguyªn thuû theo modulo 97 khi vµ chØ khi x32 ≡ 1 (mod 97) vµ x48 ≡ 1 (mod 97) b) H·y dïng ph¬ng ph¸p nµy ®Ó t×m c¨n nguyªn thuû nhá nhÊt theo modulo 97. c) Gi¶ sö p lµ mét sè nguyªn tè vµ p-1 cã phÇn tÝch ra c¸c mò nguyªn tè sau : n e 1 p − 1= ∏ p i =1 i
ë ®©y pi lµ c¸c sè nguyªn tè kh¸c nhau. H·y chøng minh tá r»ng x ≠ 0 lµ mét c¨n nguyªn thuû theo modulo p khi vµ chØ khi x(p-1)/p ≡ 1 (mod p ) víi 1 ≤ i ≤ n i 4.5. Gi¶ sö n =pq, p vµ aq lµ c¸c sè nguyªn tè lÎ ph©n biÖt vad ab ≡ 1 (mod (p-1)(q-1)). PhÐp to¸n m· ho¸ RSA lµ e(x) = xb mod n vµ phÐp to¸n gi¶i m· lµ d(y) = ya mod n. Ta ®· chøng tá r»ng d(e(x)) = 1 nÕu x ∈ Zn *. H·y chøng tá r»ng kh¼ng ®Þnh trªn lµ ®óng ®èi víi bÊt kú x ∈ Zn. ChØ dÉn: H·y dïng kÕt qu¶ : x1 ≡ x1 (mod pq) khi vµ chØ khi x1 ≡ x1 (mod p) vµ x1 ≡ x1(mod q). §iÒu nµy rót ra tõ ®Þnh lý phÇn d China. 4.6. Hai vÝ dô vÒ b¶n m· RSA ®îc nªu ë c¸c b¶ng 4.1 vµ b¶ng 4.2. NhiÖm vô cña b¹n lµ ph¶i gi¶i m· chóng. C¸c tham sè c«ng khai cña hÖ thèng lµ n =18923 vµ b = 1261 (b¶ng 4.1) vµ n = 31313, b = 4913 (víi b¶ng 4.2). PhÐp gi¶i m¶ c¸o thÓ thùc hiÖn nh sau. Tríc hÕt hü ph©n tÝch n (®iÒu nµy kh¸ dÓ v× n qu¸ nhá). Sau ®ã tÝnh sè mò a tõ φ(n) vµ cuèi cïng sÏ gi¶i m· b¶n m·. H·y dïng thuËt to¸n b×nh ph¬ng vµ nh©n ®Ó lÊy luü thõa theo modulo n. B¶ng 4.1 B¶n m· RSA 12423 11524 7243 7459 14303 6127 10964 16399 9792 13692 14407 18817 18830 13556 3159 16647 5300 13951 91 8986 8007 13167 10022 17213 2264 9553 18194 3830 2664 13998 12501 18873 13236 5300 13951 8850 12129 6091 18110 3332 15061 12347 7817 7946 11675 13924 13892 18031
2620 6276 8500 201 8850 11178 16477 10161 3533 13842 7537 12259 18110 44 2364 15570 3460 9886 8687 4481 11231 7547 11383 17910 12867 13203 5102 4742 5053 15407 2976 9330 12192 56 2471 14334 841 13995 13297 8186 2430 9741 11675 242 6686 738 13874 8186 7913 6246 14301 1144 9056 15967 7328 13203 796 195 9872 16979 15404 14130 9105 2001 9792 14251 1498 11296 1105 4502 16979 1105 56 4118 11302 5988 3363 15827 6928 4191 4277 10617 874 13211 1182 3090 18110 44 2364 15570 3460 9886 9988 3798 1158 9872 16979 15404 6127 9872 3652 14838 7437 2540 1367 2512 14407 5053 1521 297 10935 17137 2186 9433 13293 7555 13618 13000 6490 5310 18676 4782 11375 446 4165 11634 3846 14611 2364 6789 11634 4493 4063 4576 17955 7965 11748 14616 11453 17666 925 56 4118 18031 9522 14838 7437 3880 11476 8305 5102 2999 18628 14326 9175 9061 650 18110 8720 15404 2951 722 15334 841 15610 2443 11056 2186 §Ó chuyÓn b¶n râ trë vÒ v¨n b¶n tiÕng Anh th«ng th- êng, b¹n cÇn ph¶i c¸c ký tù ®· ®îc “m· ho¸” thµnh c¸c phÇn tö trong Zn nh thÕ nµo. Mçi phÇn tö cña Zn sÏ biÓu thÞ ba ký tù nh trong c¸c vÝ dô sau: DOG  3 × 262 + 14 × 26 +6 = 2398 CAT  2 × 262 + 0 × 26 + 19 = 1371 ZZ  25 × 262 + 25 × 26 + 25 = 17575 Bíc cuèi cïng trong ch¬ng tr×nh cña b¹n lµ lµm ngîc l¹i qu¸ tr×nh trªn. B¶n râ ®Çu lÊy trong cuèn “The diary of Samuel M¶chbankls” cña Robertson Davies, 1947. B¶n râ thø hai lÊy tõ cuèn “Lake Wobegon Days” cña Garrison Keillor, 1985. 4.7. Bµi tËp nµy m« t¶ c¸i ®îc gäi lµ sù trôc trÆc vÒ thñ tôc. §©y lµ mét vÝ dô vÒ mét b¶n mµ cã thÓ bÞ ®èi ph¬ng gi¶i mµ kh«ng cÇn ph¶i x¸c ®Þnh kho¸ nÕu dïng thiªó thËn träng hÖ mËt ( v× ®èi ph¬ng kh«ng ph¶i x¸c ®Þnh
B¶ng 4.2 B¶n m· RSA 6340 8309 14010 8936 2735 25023 16481 25809 8 23316 7135 24996 30596 2757 26486 30388 9395 0 27584 14999 4517 12146 2942 26439 1606 17881 1 25774 7647 23901 7372 2577 18436 12056 13547 4 7908 8635 2149 1908 2207 7372 8686 1307 6 4082 11803 5314 107 7359 22470 7372 22827 15698 30317 4685 14696 3038 8671 29956 15705 8 1417 26905 25809 28347 2627 7879 20240 21519 7 12437 1108 27106 18743 2414 10685 25234 30155 4 23055 8267 9917 7994 9694 2149 10042 27705 15930 29748 8635 23645 1173 24591 20240 27212 8 27486 9741 2149 29329 2149 5501 14015 30155 18154 22319 27705 20321 2325 13624 3249 5443 4 2149 16975 16087 14600 2770 19386 7325 26277 0 5 19554 23614 7553 4734 8091 23973 14015 107 3183 17347 25234 4595 2149 6360 19837 8463 8 6000 31280 29413 2066 369 23204 8425 7792 25973 4477 30989 Kho¸ nªn nÕu gäi lµ th¸m m· th× kh«ng ®îc chÝnh x¸c l¾m). Tinh thÇn ë ®©y lµ dïng hÖ mËt “ an toµn toµn” vÉn cha ®ñ ®Ó ®¶m b¶o liªn l¹c an toµn toµn. Gi¶ sö Bob cã mét hÖ mËt RSA cã modulo n lín ®Ó viÖc ph©n tÝch n kh«ng thÓ thùc hiªn trong mét thêi gian chÊp nhËn ®îc. Gi¶ sö Alice göi mét thong b¸o cho Bob b»ng
c¸ch biÓu thÞ mét ký tù b»ng mét sè nguyªn trong kho¶ng 0- 25 (ch¼ng h¹n A↔0, B ↔1,…) vµ råi m· ho¸ tõng ký tù cña b¶n râ. a) H·y m« t¶ c¸ch Oscar cã thÓ gi¶i m· dÔ dµng c¸c b¶n m· ®îc m· nh c¸ch trªn. b) Minh ho¹ c¸ch tÊn c«ng qua viÖc gi¶i m· b¶n m· sau (b¶n nµy ®· ®îc m· b»ng hÖ mËt RSA víi n = 18721 vµ b = 25) mµ kh«ng cÇn ph¶i ph©n tÝch n: 365,0,4845,14930,2608,2608,0 4.8. Bµi tËp nµy m« t¶ mét vÝ dô kh¸c vÒ sù trôc trÆc thñ tôc (theo Simons)trong RSA ®îc gäi lµ trôc trÆc thñ tôc modulo chung. Gi¶ sö Bob cã hÖ m©t RSA víi modulo n, sè mò ho¸ b1 cßn Charlie cã hÖ m©t RSA víi cïng modulo n, sè mò ho¸ b2. Gi¶ sö UCLN(b1,b2) =1. B©y giê ta h·y xÐt t×nh h×nh x¶y ra nÕu Alice m· ho¸ cïng mét b¶n râ x ®Ó göi cho c¶ Bob vµ Charlie. Nh vËy, Alice sÏ tÝnh y1 =xb mod n vµ y2 =xb mod n vµ råi göi y1 cho Bob 1 2 vµ göi y2 cho Charlie. Gi¶ sö Oscar thu ®îc y1 vµ y2 vµ thùc hiÖn c¸c tÝnh to¸n ®îc nÕu ë h×nh 4.16 sau. H×nh 4.16. trôc trÆc thñ tôc modulo chung. §Çu vµo : n, b1, b2, y1, y2 -1 1. TÝnh c1 = b1 mod b2 2. TÝnh c2 = (c1b1- 1)/b2 c c -1 3. TÝnh x1 = y1 (y2 ) mod n 1 2 a) H·y chøng tá r»ng gi¸ trÞ x1 tÝnh ®îc ë bíc 3 cña h×nh 4.16 thùc tÕ lµ b¶n râ x cña Alice. Bëi vËy, Oscar cã thÓ gi¶i m· ®îc th«ng b¸o mµ Alice ®· göi, ngay c¶ khi b¶n râ ®îc göi qua hÖ mËt ®îc coi lµ an toµn.
b) Minh ho¹ c¸ch tÊn c«ng qua viÖc tÝnh x theo ph¬ng ph¸p nµy nÕu n = 18721,b 1 = 945, b2 = 7717, y1 = 12677 vµ y2 = 14702. 4.9 §©y l¹i lµ mét vÝ dô kh¸c vÒ sù trôc trÆc thñ tôc xoay quanh hÖ mËt RSA. Gi¶ sö cã ba ngêi dïng trong m¹ng lµ Bob, Bar vµ Bert, hä ®Òu cã sè mò m· ho¸ b =3. C¸c modulo t¬ng øng n1, n2, n3. Gi¶ sö Alice m· ho¸ cïng mét b¶n râ x ®Ó göi cho Bob, Bar vµ Bert. Khi ®ã Alice tÝnh yi = x3 mod ni , 1≤ i ≤ 3 H·y m« t¶ c¸ch tnhs x cña Oscar khi anh ta ®· biÕt y1, y2, y3, mµ kh«ng cÇn ph¶i ph©n tÝch bÊt cø ni nµo. 4.10. B¶n râ x ®îc gäi lµ cè ®Þnh nÕu ek(x) = x. H·y chøng tá r»ng ®èi víi hÖ mËt RSA, sè c¸c b¶n râ cè ®Þnh x ∈ Zn* b»ng UCLN(b-1, p-1) × UCLN(b-1, p-1) ChØ dÉn: xÐt hÖ hai ph¬ng tr×nh ®ång d: eK (x1) ≡ x (mod p), eK(x2) ≡ x (mod p). 4.11. Gi¶ sö A lµ mét thuËt to¸n tÊt ®Þnh cã ®Çu vµo lµ mét RSA modulo n vµ b¶n m· y. A sÏ hoÆc gi¶i m· y hoÆc kh«ng cã lêi gi¶i. Gi¶ sö r»ng cã ε × n b¶n m· mµ cã thÓ gi¶i, hay chØ râ c¸ch dïng A lµm mét ch¬ng con trong thuËt to¸n gi¶i m· Las Vegas cã x¸c suÊt kh«ng thµnh c«ng lµ ε. ChØ dÉn: sö dung tÝnh chÊt nh©n cña RSA lµ eK (x1) eK(x2) = eK(x1x2) trong ®ã tÊt c¶ c¸c phÐp to¸n sè häc lµ theo modulo n. 4.12. ViÕt mét ch¬ng tr×nh ®Ó ®¸nh gi¸ c¸c ký hiÖu Jacobi b»ng c¸ch dïng bèn tÝnh chÊt ®îc nªu ë phÇn 4.5. Ch- ¬ng tr×nh kh«ng thùc hiÖn viÖc ph©n tÝch thõa sè trõ viÖc ph©n ra c¸c luü thõa bËc hai. H·y kiÓm tra ch¬ng tr×nh cña b¹n qua viÖc tÝnh c¸c ký hiÖu Jacobi sau:
 610   20964  1234567   ,  ,    987   1987   111111.11 4.13. H·y viÕt mét ch¬ng tr×nh tÝnh sè c¸c sè gi¶ nguyªn tè Euler theo c¸c c¬ së 837, 851 vµ 1189. 4.14. Môc ®Ých cña bµi tËp nµy lµ ph¶i chøng tá r»ng: x¸c suÊt cña kiÓm tra tÝnh nguyªn tè Solovay- Strassen nhiÒu nhÊt lµ 1/2 . Gi¶ sö Zn* lµ nhãm c¸c phÇn tö kh¶ nghÞch theo modulo n. Ta ®Þnh nghÜa: { ∈ a ≡ a)   n ≠ | | ≤ | | ≤ ≥ ≡ ≡ ≡ … kh«ng bËc hai theo modulo p1. (Chó ý r»ng, a nh vËy tån t¹i theo ®Þnh lý phÇn d China). H·y chøng minh r»ng: ≡ -1 (mod n) nhng a(n-1)/2 ≡ 1 (mod p2p3…ps) nªn a(n-1)/2 ≡ -1 9mod n) b) NÕu n lµ mét sè hîp sè lÎ, chøng minh r»ng : | G(n) | ≤ (n- 1) /2 c) Tæng hîp c¸c kÕt qu¶ trªn, h·y chøng minh r»ng x¸c suÊt sai cña phÐp kiÓm tra tÝnh nguyªn tè Solovay- Strassen nhiÒu nhÊt lµ 1/2. 4.15. Gi¶ sö ta cã thuËt to¸n Las-Vegas víi x¸c suÊt sai ε. a) H·y chøng minh r»ng, x¸c suÊt thµnh c«ng lÇn ®Çu sau phÐp thö thø n lµ : Pn = εn-1 (1-ε) b) Sè phÐp thö trung b×nh ®Ó ®¹t thµnh c«ng lµ :
∞ ∑ n=1 (n × pn) . H·y chøng tá r»ng gi¸ trÞ nµy b»ng 1/(1-ε) c) Gi¶ sö δ lµ mét sè d¬ng thùc nhá h¬n 1. H·y chøng tá r»ng sè c¸c phÐp lÆp cÇn thiÕt ®Ó gi¶m x¸c suÊt sai tèi ®a δ lµ:  log 2δ     log 2ε  4.16. Gi¶ sö thiÕu trÇn träng, Bob ®· ®Ó lé sè mò gi¶i m· cña m×nh lµ a = 14039 trong hÖ mËt RSA víi khoa c«ng khai n = 36581 vµ b = 4679. ¸p dông dông thuËt to¸n s¸c suÊt ®Ó ph©n tÝch n theo th«ng tin ®îc biÕt nµy. H·y kiÓm tra thuËt toan cña b¹n víi c¸c phÐp chän ngÉu nhiªn w = 9983 vµ w = 13461. H·y chØ ra tÊt c¶ c¸c tÝnh to¸n . 4.17. H·y chøng minh c¸c ph¬ng tr×nh 4.1 vµ 4.2 cã liªn quan ®Õn c¸c hµm half vµ parity. 4.18. gi¶ sö p = 199, q = 211 vµ b = 1357 trong hÖ mËt Rabin. H·y thùc hiÖn tÝnh to¸n sau: a) X¸c ®Þnh 4 c¨n bËc hai cña modulo n, trong ®ã n =pq. b) TÝnh phÐp m· y = ek(32767) c) X¸c ®Þnh 4 b¶n gi¶ m· cã thÓ cña b¶n m· y ®· cho. 4.19. H·y ph©n tÝch ra thõa sè c¸c sè 262063 vµ 9420457 b»ng ph¬ng ph¸p p-1. Trong mçi trêng hîp, ®Ó thµnh c«ng ph¶i chän B l¬n nh thÕ nµo?.