Số học thuật toán P3

Chia sẻ: Trần Bá Trung4 | Ngày: | Loại File: PDF | Số trang:44

Thêm vào BST

Báo xấu

200
lượt xem 103
download

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

Số học thuật toán P3 là tài liệu tham khảo, rất hay để các bạn đam mê toán tham khảo, tài liệu bao gồm các kiến thức chuyên sâu về toán. Chúc các bạn học tốt.

Chủ đề:

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

Lưu

Nội dung Text: Số học thuật toán P3

phÐp tÝnh bit ®−îc thùc hiÖn khi nh©n hai phÇn tö cña tr−êng Fq lµ: O(r2log2 p+rlog3 p)=O((rlogp)3)=O(log3 q). Kh¼ng ®Þnh cña ®Þnh lÝ ®−îc chøng minh ®èi víi phÐp nh©n. XÐt phÐp chia c¸c phÇn tö cña Fq. §Ó chøng minh r»ng cã thÓ hiÖn phÐp chia sau O(log3 q) phÐp tÝnh bit, ta chØ cÇn chøng tá r»ng, nghÞch ®¶o cña mét phÇn tö t×m ®−îc bëi O(log3 q) phÐp tÝnh bit, råi ¸p dông kÕt qu¶ ®· chøng minh ®èi víi phÐp nh©n. Gi¶ sö ta cÇn t×m nghÞch ®¶o cña phÇn tö Q ∈Fq (lµ mét ®a thøc bËc nhá h¬n r, hÖ sè trong Fp). Dïng thuËt chia Euclid cho c¸c ®a thøc trªn tr−êng Fq, ta cÇn biÓu diÔn 1 nh− lµ tæ hîp tuyÕn tÝnh cña ®a thøc P(x) vµ Q(x). §iÒu nµy lµm ®−îc bëi O(r) phÐp chia c¸c ®a thøc bËc nhá h¬n r. Mçi phÐp chia nh− vËy cÇn O(r2log2 p+rlog3 p)=O(r2log3 p) phÐp tÝnh bit. Nh− vËy, ta cÇn tÊt c¶ lµ O(r3log3 p)=O(log3 q) phÐp tÝnh bit, ®iÒu ph¶i chøng minh. om m Cßn ph¶i xÐt phÐp tÝnh n©ng lªn luü thõa bËc k. Ta cã thÓ dïng ph−¬ng ph¸p b×nh ph−¬ng liªn tiÕp, vµ nh− vËy, sè phÐp nh©n vµ b×nh ph−¬ng cÇn thùc hiÖn lµ O(log k). o Sè phÐp tÝnh bit cÇn thiÕt trong tr−êng hîp nµy lµ O(log klog3 q). §Þnh lÝ ®−îc chøng minh. .C .C §4. Sù t−¬ng tù gi÷a sè nguyªn vµ ®a thøc. thh Sù ph¸t triÓn cña sè häc, ®Æc biÖt lµ trong nh÷ng thËp kØ gÇn ®©y, chÞu ¶nh h−ëng rÊt at lín cña sù t−¬ng tù gi÷a sè nguyªn vµ ®a thøc. Nãi c¸ch kh¸c, khi cã gi¶ thuyÕt nµo a ®ã ch−a chøng minh ®−îc ®èi víi c¸c sè nguyªn, ng−êi ta cè g¾ng chøng minh sù kiÖn t−¬ng tù cho c¸c ®a thøc. §iÒu ®ã th−êng dÔ lµm h¬n, cã lÏ nguyªn nh©n chñ nM M yÕu lµ v×, ®èi víi c¸c ®a thøc, ta cã phÐp tÝnh ®¹o hµm, trong khi mét kh¸i niÖm t−¬ng tù ch−a cã ®èi víi c¸c sè nguyªn. Trong tiÕt nµy, chóng t«i cè g¾ng th«ng qua mét vµi vÝ dô ®¬n gi¶n, minh häa vai trß quan träng cña sù t−¬ng tù nãi trªn trong c¸c nghiªn cøu vÒ sè häc. n Tr−íc hÕt, chóng ta thÊy râ, gi÷a tËp hîp c¸c sè nguyªn vµ tËp hîp c¸c ®a thøc cã V nh÷ng tÝnh chÊt rÊt gièng nhau sau ®©y: V 1) C¸c qui t¾c céng, trõ, nh©n, chia hoµn toµn nh− nhau cho c¶ hai tËp hîp. 2) NÕu ®èi víi c¸c sè nguyªn, ta cã c¸c sè nguyªn tè, th× víi c¸c ®a thøc, ta cã c¸c ®a thøc bÊt kh¶ quy. 3) §èi víi hai sè nguyªn, còng nh− ®èi víi hai ®a thøc, cã thÓ ®Þnh nghÜa −íc chung lín nhÊt. H¬n n÷a, trong c¶ hai tr−êng hîp, −íc chung lín nhÊt nµy t×m ®−îc b»ng thuËt to¸n Euclid. 4) Mçi sè nguyªn cã ph©n tÝch thµnh c¸c thõa sè nguyªn tè, mçi ®a thøc cã ph©n tÝch thµnh c¸c ®a thøc bÊt kh¶ quy. 5) C¸c sè h÷u tû t−¬ng øng víi c¸c hµm h÷u tû. 90
Chóng t«i dµnh cho ®éc gi¶ viÖc kÐo dµi b¶ng danh s¸ch nµy. ë ®©y, chóng t«i sÏ ®i vµo mét vµi t−¬ng tù khã nh×n thÊy h¬n. Ta ®Ó ý ®Õn sù t−¬ng tù gi÷a ph©n tÝch ra thõa sè nguyªn tè vµ ph©n tÝch bÊt kh¶ quy. NÕu gi¶ thiÕt r»ng tr−êng k lµ ®ãng ®¹i sè, th× mçi ®a thøc Q(x) ∈ k[x] cã thÓ ph©n tÝch ®−îc d−íi d¹ng sau: a a a Q(x)= P1 1 P2 2 ... Pn n , trong ®ã Pi(x)=(x- α i), α i ∈k. Nh− vËy, cã thÓ thÊy r»ng, trong sù t−¬ng tù gi÷a ph©n tÝch bÊt kh¶ quy vµ ph©n tÝch ra thõa sè nguyªn tè c¸c nghiÖm cña ®a thøc t−¬ng øng víi c¸c −íc nguyªn tè cña sè nguyªn. Do ®ã, sè c¸c nghiÖm ph©n biÖt cña mét ®a thøc cã vai trß t−¬ng tù nh− sè c¸c −íc nguyªn tè cña mét sè nguyªn. Tõ nhËn xÐt ®ã, ta ®i ®Õn ®Þnh nghÜa sau ®©y. om m §Þnh nghÜa 5.5. Cho a lµ mét sè nguyªn. Ta ®Þnh nghÜa c¨n cña a, kÝ hiÖu qua N0(a), lµ tÝch c¸c −íc nguyªn tè cña a: o N0(a)= ∏ p . p |a .C .C Ta sÏ thÊy r»ng, sù t−¬ng tù trªn ®©y cïng víi c¸c tÝnh chÊt cña ®a thøc gîi më mét con ®−êng nhiÒu hy väng ®Ó ®i ®Õn chøng minh ®Þnh lÝ Fermat. N¨m 1983, R. C. Mason chøng minh ®Þnh lÝ rÊt ®Ñp sau ®©y vÒ c¸c ®a thøc. thh §Þnh lÝ 5.6. Gi¶ sö a(t), b(t), c(t) lµ c¸c ®a thøc víi hÖ sè phøc, nguyªn tè cïng nhau tõng cÆp vµ tho¶ m·n hÖ thøc at a a(t)+ b(t)= c(t) Khi ®ã, nÕu kÝ hiÖu qua n0(f) sè nghiÖm ph©n biÖt cña mét ®a thøc f, th× ta cã nM M max{ deg a, deg b, deg c} ≤ n0(abc)-1. Tr−íc khi ®i vµo chøng minh ®Þnh lÝ, ta chøng minh hÖ qu¶ sau ®©y cña ®Þnh lÝ n Mason. HÖ qu¶ 5.7. Kh«ng tån t¹i c¸c ®a thøc a, b, c, kh¸c h»ng sè, nguyªn tè cïng nhau, V V tho¶ m·n ph−¬ng tr×nh an + bn = cn víi n ≥ 3. Chøng minh. GØa sö c¸c ®a thøc a, b, c tho¶ m·n ph−¬ng tr×nh nãi trªn. Râ rµng sè nghiÖm ph©n biÖt cña ®a thøc anbncn kh«ng v−ît qu¸ deg a + deg b + deg c. ¸p dông ®Þnh lÝ Mason ta cã n deg a ≤ deg a + deg b + deg c - 1 ViÕt ®¼ng thøc trªn víi b, c, råi céng tõng vÕ ba bÊt ®¼ng thøc ta ®−îc : n(deg a + deg b + deg c) ≤ 3 (deg a + deg b + deg c) - 3 91
Ta cã m©u thuÉn nÕu n ≥ 3. Nh− vËy, ®Þnh lÝ Mason cho ta mét chøng minh ®¬n gi¶n cña ®Þnh lÝ Fermat cho c¸c ®a thøc. Sau ®©y, ta chøng minh ®Þnh lÝ Mason. Chøng minh ®Þnh lÝ Mason. §Æt f = a/b, g= a/c, ta cã: f+g=1. LÊy ®¹o hµm hai vÕ cña ph−¬ng tr×nh nµy, ta ®−îc: f’+g’=0. Nh»m môc ®Ých xÐt sè c¸c nghiÖm cña ®a thøc, ta xÐt c¸c th−¬ng cña ®¹o hµm vµ hµm sè. Ta cã: b f ' /f (f’/f)f+(g’/g)g=0, =− . a g ' /g MÆt kh¸c, gi¶ sö R(t) lµ mét hµm h÷u tû cã ph©n tÝch sau ®©y R(t)= ∏ (t − ϑ i ) qi , qi ∈Z . om m TÝnh to¸n ®¬n gi¶n cho ta: qi R’/R= ∑ t −ϑ . o i B©y giê gi¶ sö a, b, c t−¬ng øng cã c¸c nghiÖm ph©n biÖt lµ α i , β j , γ k . Ta cã: .C .C a(t)= ∏ (t − α i ) mi , b(t ) = ∏ (t − β j ) j , c(t ) = ∏ (t − γ k ) rk . n h Nh− vËy, th mi rk ∑ t −α −∑ at b f ' /f t −γ k a =− =− i a g ' /g nj r ∑ t − β − ∑ t − kγ nM M j k MÉu sè chung cña c¸c ph©n sè trong phÇn tö sè vµ mÉu sè cña th−¬ng sau cïng lµ N0= ∏ (t − α i )∏ (t − β j )∏ (t −γ k ). n §ã lµ mét ®a thøc cã bËc lµ n0(abc). Nh− vËy, N0f’/f vµ N0g’/g lµ c¸c ®a thøc cã bËc V V kh«ng qu¸ n0(abc)-1. MÆt kh¸c ta cã: b N f ' /f =− 0 a N 0 g ' /g V× a, b nguyªn tè cïng nhau nªn tõ ®¼ng thøc nµy suy ra bËc cña a vµ bËc cña b ®Òu kh«ng v−ît qu¸ n0(abc)-1. §iÒu t−¬ng tù còng ®óng ®èi víi c do vai trß ®èi xøng cña a, b, c trong ph−¬ng tr×nh xuÊt ph¸t. §Þnh lÝ ®−îc chøng minh. Tõ ®Þnh lÝ Mason, ta cã thÓ suy ra nhiÒu hÖ thøc gi÷a c¸c ®a thøc. Ch¼ng h¹n, mét trong nh÷ng hÖ qu¶ lµ ®Þnh lÝ sau ®©y: §Þnh lÝ Davenport. Gi¶ sö f(t), g(t) lµ c¸c ®a thøc, sao cho f 3 ≠ g2. Khi ®ã ta cã deg(f 3-g2) ≥ 1/2 deg f+1 92
Chóng t«i dµnh chøng minh ®Þnh lÝ nµy cho ®éc gi¶. Kh¼ng ®Þnh t−¬ng tù ®èi víi c¸c sè nguyªn vÉn cßn ch−a ®−îc chøng minh. Ta cã: Gi¶ thuyÕt Hall. Gi¶ sö x, y lµ c¸c sè nguyªn d−¬ng sao cho x3 ≠ y2. Khi ®ã, víi mäi ε >0, tån t¹i C>0 chØ phô thuéc ε sao cho | y2-x3|>Cx1/2- ε Cã thÓ nãi thªm r»ng, bÊt ®¼ng thøc trong ®Þnh lÝ Davenport lµ tèt nhÊt cã thÓ: ®èi víi c¸c ®a thøc f(t)=t6+4t4+10t2+6, g(t)=t9+6t7+21t5+35t3+63/2t ta cã: deg(f3-g2)=1/2degf+1. N¨m 1982, L. V. Danilov còng ®· chøng minh r»ng, sè mò 1/2 trong gi¶ thuyÕt Hall lµ tèt nhÊt cã thÓ. §Þnh lÝ Mason vµ t−¬ng tù gi÷a c¸c sè nguyªn vµ ®a thøc ®· gîi ý cho gi¶ thuyÕt sau ®©y: om m Gi¶ thuyÕt abc (OesterlÐ, 1986). Gi¶ sö a, b, c lµ c¸c sè nguyªn, nguyªn tè cïng nhau vµ tho¶ m·n hÖ thøc a+b=c. Khi ®ã, víi mäi ε >0, tån t¹i sè C sao cho max(|a|, |b|, |c|)
Bµi tËp vµ tÝnh to¸n thùc hµnh ch−¬ng 5 I. Bµi tËp 5.1. Gi¶ sö K lµ tr−êng ®Æc tr−ng p. Chøng minh r»ng, ®èi víi c¸c phÇn tö cña tr−êng K, ta cã: (a+b)p=ap+bp. 5.2. X©y dùng tr−êng F9 tõ tr−êng F3 bëi c¸c ®a thøc sau: 1) x2+1 om m 2)x2-x-1. 5.3. Dïng thuËt to¸n EP ®Ó t×m ¦CLN cña c¸c ®a thøc P,Q trong tr−êng Fp, vµ biÓu diÔn d¹ng d=uP+vQ: o 1) P=x3+x+1, Q=x2+x+1, p=2. .C .C 2) P=x6+x5+x4+x3+x2+x+1, Q=x4+x2+x+1, p=2. 3) P=x3-x+1, Q=x2+1, p=3. 4) x5+x4+x3-x2-x+1, Q=x3+x2+x+1, p=3. thh 5) x5+88x4+73x3+83x2+51x+67, Q=x3+97x2+40x+38, p=101. at 5.4. Víi mçi d ≤ 6, t×m tÊt c¶ c¸c ®a thøc bÊt kh¶ quy bËc d trªn tr−êng F2. a 5.5. Nh÷ng ®a thøc nµo trong Fp[x] cã ®¹o hµm ®ång nhÊt b»ng 0? nM M 5.6. Chøng minh r»ng tõ gi¶ thuyªt “abc” suy ra ®Þnh lÝ Fermat tiÖm cËn. 5.7. Chøng minh ®Þnh lÝ Davenport. n 5.8. Cho f, g lµ c¸c ®a thøc víi hÖ sè nguyªn, sao cho f 3-g4 kh«ng ®ång nhÊt b»ng 0. Chøng minh r»ng V deg(f3-g4) ≥ 5/3deg g+1. V Ph¸t biÓu kÕt luËn t−¬ng tù cho c¸c sè nguyªn. 5.9. Dùa vµo ®Þnh lÝ Mason, t×m nh÷ng hÖ thøc míi liªn quan ®Õn bËc cña c¸c ®a thøc hÖ sè nguyªn (t−¬ng tù bµi tËp trªn ®©y). Thö ph¸t biÓu vµ chøng minh kÕt luËn t−¬ng tù dèi víi c¸c sè nguyªn. 5.10. Thö ®−a ra mét ®Þnh nghÜa vÒ ®¹o hµm cña mét sè nguyªn. II. Thùc hµnh trªn m¸y tÝnh II. 1. Thùc hµnh tÝnh sè ®a thøc bÊt kh¶ quy bËc d trªn tr−êng h÷u h¹n 94
§Ó tÝnh sè ®a thøc bÊt kh¶ quy bËc n trªn tr−êng h÷u h¹n cã ®Æc sè p ta thùc hiÖn dßng lÖnh nh− sau; [>mipolys(n, p); Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ xuÊt hiÖn sè ®a thøc cÇn t×m. ThÝ dô: TÝnh sè c¸c ®a thøc bÊt kh¶ quy bËc 6 trªn tr−êng cã ®Æc sè 2. Ta thùc hiÖn lÖnh sau: [>mipolys(6, 2); 9 Nh− vËy cã 9 ®a thøc bÊt kh¶ quy trªn tr−êng F2. om II. 2. Thùc hµnh t×m −íc chung lín nhÊt cña c¸c ®a thøc trªn tr−êng m h÷u h¹n Cho P, Q lµ c¸c ®a thøc biÕn x víi hÖ sè trªn tr−êng h÷u h¹n cã ®Æc sè p. §Ó t×m −íc o chung lín nhÊt D cña P vµ Q vµ biÓu diÔn d−íi d¹ng D=sP+tQ ta thùc hiÖn dßng lÖnh sau: .C .C [> Gcdex(P,Q,x,’s’,’t’) mod p; Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ xuÊt hiÖn mét ®a thøc, ®ã chÝnh lµ −íc chung lín nhÊt cña P, Q. TiÕp tôc thùc hiÖn lÖnh: thh [>s,t; at Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ xuÊt hiÖn hai ®a thøc s, t cÇn t×m. a Chó ý lÖnh “Gcdex” ch÷ “G” lµ ch÷ viÕt hoa. nM M ThÝ dô1: T×m −íc chung lín nhÊt D cña c¸c ®a thøc P, Q trªn tr−êng F2 vµ biÓu diÔn d−íi d¹ng D=sP+tQ, trong ®ã P=x3+x+1, Q=x2+x+1. Ta thùc hiÖn dßng lÖnh: n [> Gcdex(x^3+x+1,x^2+x+1,x,’s’,’t’) mod 2; 1 V V [>s,t; 1+x,x2 VËy 1=(1+x)P+x2Q. ThÝ dô2: T×m −íc chung lín nhÊt D cña c¸c ®a thøc P, Q trªn tr−êng F101 vµ biÓu diÔn d−íi d¹ng D = sP + tQ, trong ®ã x5 + 88x4 + 73x3 + 83x2 + 51x + 67, Q=x3+97x2+40x+38 Ta thùc hiÖn dßng lÖnh: [>Gcdex(x^5+88*x^4+73*x^3+83*x^2+51*x+67,x^3+97*x^2+40*x +38,x,'s','t') mod 101; 95
x + 78 [> s,t; 50x + 20, 51x3 + 26x2 + 27x + 4 VËy x+78=(50x+20)P+(51x3+26x2+27x+4)Q. II. 3. Thùc hµnh t×m −íc chung lín nhÊt, béi chung nhá nhÊt cña c¸c ®a thøc trªn tr−êng h÷u tû Cho P, Q lµ c¸c ®a thøc biÕn x víi hÖ sè trªn tr−êng h÷u tû. 1. §Ó t×m −íc chung lín nhÊt D cña P vµ Q ta thùc hiÖn dßng lÖnh sau: [> gcd(P,Q); om m Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ xuÊt hiÖn kÕt qu¶, ®ã chÝnh lµ −íc chung lín nhÊt cña P, Q. ThÝ dô1: T×m −íc chung lín nhÊt D cña c¸c ®a thøc P, Q trªn tr−êng h÷u tû trong ®ã o P=x2-y2, Q=x3-y3. .C Ta thùc hiÖn dßng lÖnh: .C [> gcd(x^2-y^2,x^3-y^3); -y+x thh VËy −íc chug lín nhÊt cña P vµ Q lµ -y+x at 2. §Ó t×m béi chung nhá nhÊt cña P, Q ta thùc hiÖn dßng lÖnh nh− sau: a [> lcm(P,Q); Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ xuÊt hiÖn kÕt qu¶, ®ã chÝnh lµ béi nM M chung nhá nhÊt cña P,Q. ThÝ dô 2: T×m béi chung nhá nhÊt cña c¸c ®a thøc P, Q trªn tr−êng h÷u tû trong ®ã P=x2-y2, Q=x3-y3. n Ta thùc hiÖn dßng lÖnh: V V [> lcm(x^2-y^2,x^3-y^3); -yx3+y4-x4+xy3 VËy béi chung nhá nhÊt cña P vµ Q lµ -yx3+y4-x4+xy3 96
Ch−¬ng 6 Vµi øng dông vµo lÝ thuyÕt mËt m· Cho ®Õn kho¶ng cuèi nh÷ng n¨m 70, sè häc vÉn ®−îc xem lµ mét trong nh÷ng ngµnh lÝ thuyÕt thuÇn tuý nhÊt cña to¸n häc, v× hÇu nh− kh«ng cã øng dông thùc tÕ. Quan niÖm ®ã thay ®æi h¼n sau khi sè häc ®−îc ¸p dông ®Ó x©y dùng nh÷ng hÖ mËt m· kho¸ c«ng khai. C¸c lÝ thuyÕt míi cña sè häc, ®Æc biÖt lµ sè häc thuËt to¸n, t×m thÊy nh÷ng øng dông trùc tiÕp vµo thùc tiÔn. V× thÕ chóng t«i dµnh mét ch−¬ng tr×nh bµy nh÷ng ®iÓm c¬ b¶n cña lÝ thuyÕt mËt m·, ®Ó qua ®ã, ®éc gi¶ cã thÓ thÊy ®−îc vai trß om m quan träng cña nh÷ng vÊn ®Ò xÐt ®Õn trong lÝ thuyÕt sè thuËt to¸n, nh− vÊn ®Ò ®é phøc t¹p cña c¸c thuËt to¸n ph©n tÝch mét sè nguyªn d−¬ng ra thõa sè, hay vÊn ®Ò kiÓm tra nguyªn tè. o .C §1. M· Ceasar. .C h Cã thÓ nãi, mËt m· ®· cã tõ thêi cæ ®¹i. Ng−êi ta cho r»ng, ng−êi ®Çu tiªn ¸p dông th mËt m· mét c¸ch cã hÖ thèng ®Ó ®¶m b¶o bÝ mËt th«ng tin qu©n sù lµ nhµ qu©n sù thiªn tµi cña La M· cæ ®¹i, Julius Ceasar. Sù ph¸t triÓn cña x· héi dÉn ®Õn viÖc ngµy at nay mËt m· kh«ng nh÷ng chØ ®−îc dïng trong bÝ mËt qu©n sù vµ ngo¹i giao, mµ cßn a dïng, vµ cã thÓ chñ yÕu lµ dïng trong bÝ mËt kinh tÕ, th−¬ng m¹i. V× thÕ xuÊt hiÖn nh÷ng ®ßi hái míi ®èi víi c¸c hÖ mËt m· hiÖn ®¹i, kh¸c vÒ nguyªn t¾c so víi mËt nM M m· th−êng dïng tr−íc ®©y. Kh¸c víi ho¹t ®éng qu©n sù hoÆc ngo¹i giao, trong ho¹t ®éng kinh doanh, sè l−îng ®¬n vÞ ph¶i cïng trao ®æi th«ng tin th−êng lµ rÊt lín. ThËm chÝ, nh÷ng ng−êi ch−a hÒ quen biÕt nhau còng cã nhu cÇu trao ®æi nh÷ng th«ng tin mËt víi nhau. Bëi thÕ, nh÷ng hÖ thèng mËt m· x©y dùng theo nguyªn t¾c n cò khã cã thÓ thÝch hîp: trong c¸c hÖ m· ®ã, khi ®· biÕt kho¸ lËp m·, ta dÔ dµng t×m ra kho¸ gi¶i m·. HiÓn nhiªn, muèn göi mét th«ng b¸o mËt cho mét ®èi t−îng nµo ®ã, V ta cÇn ph¶i biÕt kho¸ lËp m· cña hä, v× thÕ, nh÷ng ng−êi cïng dïng mét hÖ m· ®Òu V biÕt hÕt bÝ mËt cña nhau. Khi mét bÝ mËt cã qu¸ nhiÒu ng−êi biÕt th× kh«ng cßn lµ bÝ mËt n÷a. C¸c hÖ thèng mËt m· hiÖn ®¹i, mËt m· kho¸ c«ng khai, kh¾c phôc ®−îc nh÷ng nh−îc ®iÓm ®ã: mçi ng−êi tham gia trong hÖ thèng chØ cÇn gi÷ bÝ mËt kho¸ gi¶i m· cña m×nh, trong khi kho¸ lËp m· ®−îc th«ng b¸o c«ng khai. ViÖc biÕt kho¸ lËp m· kh«ng cho phÐp t×m ra kho¸ gi¶ m· trong mét thêi gian chÊp nhËn ®−îc, ngay c¶ khi sö dông nh÷ng m¸y tÝnh hiÖn ®¹i nhÊt. Nh÷ng mËt m· kho¸ c«ng khai t×m thÊy ®Çu tiªn lµ nh÷ng mËt m· dïng hµm sè häc. Cã mét ®iÌu hÕt søc thó vÞ lµ, nãi cho cïng, nh÷ng hÖ mËt m· hiÖn ®¹i còng chØ lµ sù c¶i tiÕn mËt m· cña Ceasar! V× thÕ chóng t«i b¾t ®Çu viÖc tr×nh bµy mËt m· Ceasar. Tr−íc hÕt chóng ta cÇn thèng nhÊt mét sè danh tõ. 97
V¨n b¶n tøc lµ th«ng b¸o cÇn chuyÓn, ®−îc viÕt b»ng ng«n ng÷ th«ng th−êng. ë ®©y, ta sÏ xem c¸c v¨n b¶n ®Òu ®−îc viÕt b»ng tiÕng ViÖt. ViÖc chuyÓn th«ng b¸o ®ã thµnh d¹ng mËt m· ®−îc gäi lµ m· hãa. B¶n ®· m· ho¸ cña v¨n b¶n ®−îc gäi lµ v¨n b¶n mËt. Gi¶i m· tøc lµ chuyÓn mét v¨n b¶n mËt thµnh v¨n b¶n ban ®Çu. Ceasar chuyÓn th«ng b¸o mËt b»ng c¸ch sau ®©y. Tr−íc tiªn, lËp t−¬ng øng mçi ch÷ c¸i víi mét sè. Nhê b¶ng t−¬ng øng ®ã, ta cã thÓ chuyÓn mét v¨n b¶n thµnh d¹ng ch÷ sè. Sau ®ã ta céng thªm 3 vµo mçi ch÷ sè nhËn ®−îc. L¹i nhê b¶ng t−¬ng øng gi÷a ch÷ vµ sè, ta biÕn b¶ng ch÷ sè míi nµy vÒ d¹ng ch÷ viÕt. Nh− vËy ta nhËn ®−îc mét v¨n b¶n mËt cÇn chuyÓn ®i. §©y lµ qu¸ tr×nh m· ho¸. Khi nhËn ®−îc v¨n b¶n mËt, ta gi¶i m· b»ng c¸ch biÕn nã thµnh d¹ng ch÷ sè nhê om m b¶ng t−¬ng øng gi÷a ch÷ vµ sè, sau ®ã trõ ®i 3 ë mçi ch÷ sè vµ l¹i chuyÓn nã vÒ d¹ng ch÷ ®Ó l¹i cã v¨n b¶n ban ®Çu. Chó ý r»ng khi phÐp céng hoÆc trõ ®i 3 ®−a ta v−ît khái giíi h¹n cña b¶ng t−¬ng o øng, ta thay sè ®ã b»ng thÆng d− d−¬ng bÐ nhÊt modulo sè c¸c phÇn tö cña b¶ng t−¬ng øng gi÷a ch÷ vµ sè. .C .C Sau ®©y ta sÏ xÐt trªn mét vÝ dô cô thÓ. Tr−íc hÕt ta lËp t−¬ng øng c¸c ch÷ c¸i víi c¸c sè theo b¶ng sau: h a ¨ © b c d ® e ª g h th 1 2 3 4 5 6 7 8 9 10 11 at a i k l m n o « ¬ p q nM M 12 13 14 15 16 17 18 19 20 21 n r s t u − v x y 22 23 24 25 26 27 28 29 V V B¶ng 1 DÜ nhiªn ta cã thÓ thªm c¸c sè ®Ó chØ dÊu, nh−ng ®Ó ®¬n gi¶n , ë ®©y ta t¹m thêi viÕt c¸c v¨n b¶n kh«ng dÊu. Nh− vËy m· Ceasar ®−îc thµnh lËp theo c«ng thøc sau: C ≡ P+3(mod 29) (6.1) trong ®ã P lµ ch÷ sè trong v¨n b¶n, cßn C lµ ch÷ sè t−¬ng øng trong v¨n b¶n mËt. Ch¼ng h¹n ta muèn m· ho¸ th«ng b¸o sau ®©y: 98
LY THUY£T M¢T MA KH¤NG CO GI KHO Tr−íc hÕt nh»m n©ng cao tÝnh b¶o mËt, ta t¸ch th«ng b¸o thµnh tõng nhãm 5 ch÷ c¸i, ®Ó tr¸nh viÖc mét sè tõ cña th«ng b¸o dÔ bÞ ph¸t hiÖn c¨n cø vµo sè ch÷ c¸i. Nh− vËy th«ng b¸o cÇn m· ho¸ lµ: LYTHU Y£TM¢ TMAKH ¤NGCO GIKHO Nhê b¶ng 1, ta chuyÓn th«ng b¸o thµnh d¹ng ch÷ sè: 14 29 24 11 25 29 8 24 15 1 24 15 1 13 11 18 16 10 5 18 10 12 13 11 18 Ap dung c«ng thøc (6.1), b¶ng ch÷ sè trªn ®−îc chuyÓn thµnh: 17 3 27 14 28 3 11 27 18 3 27 18 4 16 14 21 19 13 8 21 13 15 16 14 21 §Ó cã v¨n b¶n mËt, ta chØ cÇn chuyÓn l¹i thµnh d¹ng ch÷ c¸i theo B¶ng 1: om m O¢VLU ¢HV¤¢ V¤BNL Q¥KEQ KMNLQ Sè 3 trong c«ng thøc (6.1) ®−îc gäi lµ kho¸ cña m· Ceasar, v× nã ®−îc dïng ®Ó m· o ho¸ còng nh− gi¶i m·. Ta còng cã thÓ lËp mét hÖ mËt m· míi b»ng c¸ch thay sè 3 trong c«ng thøc (6.1) .C .C b»ng mét sè k tuú ý kh¸c gi÷a 1 vµ 29: C ≡ P+k (mod 29) (6.2) Trong tr−êng hîp nµy, kho¸ cña m· lµ k. ViÖc m· ho¸ vµ gi¶i m· ®−îc tiÕn hµnh thh hoµn toµn t−¬ng tù nh− trªn. at Ta cã thÓ lËp m· tæng qu¸t h¬n chót Ýt b»ng c¸ch thay c«ng thøc (6.2) bëi c«ng thøc a sau ®©y: C ≡ aP+b(mod 29), nM M trong ®ã a, b lµ c¸c sè nguyªn, vµ (a, 29)=1. Nh÷ng m· nh− vËy ®−îc gäi lµ m· biÕn ®æi aphin. ViÖc gi¶i m· ®−îc tiÕn hµnh b»ng c¸ch gi¶i ph−¬ng tr×nh ®ång d− (6.2), khi ®· biÕt c, a, b. n Ph©n tÝch sau ®©y cho thÊy tÝnh b¶o mËt cña m· Ceasar lµ kh«ng cao. Khi b¾t ®−îc mét v¨n b¶n mËt, ng−êi ta cã thÓ dùa vµo tÇn suÊt xuÊt hiÖn cña c¸c ch÷ c¸i ®Ó ®o¸n V V ra kho¸ cña m·. Ch¼ng h¹n nÕu ch÷ a nãi chung xuÊt hiÖn nhiÒu nhÊt trong c¸c v¨n b¶n th× ch÷ c¸i nµo cã mÆt nhiÒu nhÊt trong v¨n b¶n mËt cã nhiÒu kh¶ n¨ng lµ ch÷ a, tõ ®ã ®o¸n ra kho¸. H¬n n÷a, chØ cã 29 c¸ch kh¸c nhau ®Ó chän kho¸ cho lo¹i m· nãi trªn, nªn ®Ó dµng t×m ra kho¸ cña m·, nhÊt lµ khi ¸p dông m¸y tÝnh. §èi víi m· biÕn ®æi aphin, chØ cÇn dùa vµo tÇn suÊt xuÊt hiÖn tõ ®Ó t×m ra hai ch÷ c¸i t−¬ng øng víi 2 ch÷ nµo ®ã trong v¨n b¶n mËt, ta cã thÓ t×m ra a, b b»ng c¸ch gi¶i hÖ hai ph−¬ng tr×nh ®ång d−. Ngoµi ra, viÖc gi¶i nh÷ng hÖ m· biÕn ®æi aphin còng qu¸ dÔ dµng ®èi víi m¸y tÝnh. Nh− vËy, víi nh÷ng yªu cÇu vÒ b¶o mËt cao h¬n, ng−êi ta ph¶i dïng nh÷ng hÖ mËt m· phøc t¹p h¬n. Sau ®©y lµ mét vµi hÖ m· th−êng dïng, tõ ®¬n gi¶n ®Õn phøc t¹p. 99
§2. M· khèi. M· khèi xuÊt hiÖn nh»m chèng l¹i viÖc sö dông tÇn suÊt xuÊt hiÖn cña c¸c ch÷ c¸i trong v¨n b¶n ®Ó dß ra kho¸ gi¶i m·. Kh¸c víi c¸c hÖ m· tr×nh bµy ë môc trªn, ta kh«ng m· ho¸ tõng ch÷ c¸i cña v¨n b¶n, mµ m· ho¸ tõng khèi ch÷ c¸i. Tr−íc tiªn ta xÐt tr−êng hîp m· khèi 2 ch÷. §Ó dÔ hiÓu ta xÐt vÝ dô sau ®©y. Gi¶ sö th«ng b¸o cÇn m· ho¸ lµ KH¤NG CO §I£U BI M¢T NAO GI¦ §¦¥C L¢U Tr−íc hÕt ta t¸ch th«ng b¸o trªn thµnh khèi hai ch÷: KH ¤N GC O§ £U BI M¢ TN AO GI ¦§ ¦¥ CL ¢U Sau ®ã c¸c ch÷ c¸i ®−îc chuyÓn thµnh c¸c ch÷ sè t−¬ng øng: om m 13 11 18 15 10 5 17 7 9 25 4 12 16 3 24 15 1 17 1012 26 19 5 14 3 25 o Víi mçi m· khèi hai ch÷, ta chän mét ma trËn cÊp hai lµm kho¸ cña m·. Ch¼ng h¹n ma trËn .C .C  23 11 A=   9 12  Khi ®ã c¸c khèi hai ch÷ sè P1P2 trong v¨n b¶n ®−îc chuyÓn thµnh c¸c khèi hai ch÷ thh sè C1C2 trong v¨n b¶n mËt theo c«ng thøc sau ®©y: at C1 ≡ 23P1+11P2(mod 29) a C2 ≡ 9P1+12P2(mod 29) (6.3) nM Nh− vËy th«ng b¸o trªn ®©y ®· ®−îc chuyÓn thµnh: M 14 17 28 23 24 5 4 5 18 4 21 6 21 19 7 10 14 2 24 27 8 10 25 8 Trë l¹i c¸c ch÷ c¸i t−¬ng øng, ta ®−îc v¨n b¶n mËt: n LO XS TC BC ¤B QD TD Q¥ §G LI TV EG UE V §Ó gi¶i m·, ta cÇn gi¶i hÖ ph−¬ng tr×nh ®ång d− (6.3) ®Ó t×m P1,P2. §iÒu ®ã thùc hiÖn V ®−îc nhê ®Þnh lÝ sau ®©y: §Þnh lÝ 6.1. Cho hÖ ph−¬ng tr×nh ®ång d− ax+by ≡ r(mod m) cx+dy ≡ s(mod m) §Æt ∆ =ad-bc (mod m). Khi ®ã, nÕu ( ∆ ,m)=1 th× hÖ ph−¬ng tr×nh ®ang xÐt tån t¹i nghiÖm duy nhÊt modulo m, cho bëi c«ng thøc sau: x ≡ ∆ -1(dr-bs) (mod m), y ≡ ∆ -1(as-cr) (mod m), 100
trong ®ã ∆ -1 lµ nghÞch ®¶o cña ∆ modulo m. §Þnh lÝ trªn ®©y ®−îc chøng minh hoµn toµn t−¬ng tù nh− trong ®¹i sè tuyÕn tÝnh (chØ cÇn thay ®iªï kiÖn ( ∆ ,m)=1 bëi ®iÒu kiÖn ∆ ≠ 0). Trong vÝ dô trªn ®©y, ∆ ≡ 3(mod 29), ∆ -1 ≡ 10(mod 29). Nh− vËy, khi cã khèi C1C2 trong v¨n b¶n mËt vµ ®· biÕt m· kho¸ lµ ma trËn A, ta t×m ®−îc khèi ch÷ t−¬ng øng trong v¨n b¶n lµ P1P2 theo c«ng thøc sau: P1=10(12C1-11C2) ≡ 4C1+6C2(mod 29) P2=10(23C2-9C1) ≡ 26C1+27C2(mod 29). Tãm l¹i, viÖc m· ho¸ vµ gi¶i m· ®−îc tiÕn hµnh nhê c¸c c«ng thøc:  C1   23 11  P1   P1   4 6   C1    =  ;   =  om   m  C2   9 12  P2   P2   26 27  C2  Nh− vËy, viÖc sö dông m· khèi ®· n©ng cao rÊt nhiÒu tÝnh b¶o mËt. Tuy vËy, kho¸ o cña m· vÉn cã thÓ bÞ kh¸m ph¸ nhê viÖc nghiªn cøu tÇn suÊt xuÊt hiÖn cña c¸c khèi ch÷ c¸i. Ch¼ng h¹n nÕu ta dïng m· khèi hai ch÷, th× cã c¶ th¶y 292=641 khèi trong tiÕng ViÖt, vµ nh− vËy vÉn cßn kh¶ n¨ng kh¸m ph¸ ra kho¸ cña m· nhê c¸c m¸y tÝnh .C .C hiÖn ®¹i. Trong tr−êng hîp ta sö dông m· khèi víi nh÷ng khèi nhiÒu ch÷ c¸i, viÖc t×m ra kho¸ b»ng tÇn suÊt c¸c khèi ch÷ trªn thùc tÕ lµ kh«ng sö dông ®−îc: Ch¼ng h¹n khi dïng m· khèi 10 ch÷ c¸i, sè khèi ch÷ sÏ lµ 2910, v−ît qu¸ kh¶ n¨ng th¨m dß tÇn suÊt xuÊt hiÖn c¸c khèi ch÷ ®ã trong ng«n ng÷. thh C¸c m· khèi n ch÷ c¸i ®−îc lËp vµ gi¶i hoµn toµn t−¬ng tù nh− trªn, trong ®ã c¸c ma at trËn C,P lµ c¸c ma trËn n cét, A lµ ma trËn vu«ng cÊp n. Ma trËn nghÞch ®¶o cña A a tån t¹i khi ®Þnh thøc cña A nguyªn tè cïng nhau víi 29, vµ ma trËn P sÏ ®−îc tÝnh b»ng quy t¾c Kramer nh− trong ®¹i sè tuyÕn tÝnh (chØ cÇn thay dÊu = bëi ≡ (mod nM 29)). M Sau ®©y ta tr×nh bµy mét lo¹i hÖ m· míi, mét mÆt nã cã tÝnh b¶o mËt rÊt cao, MÆt kh¸c lµ c¬ së cho nh÷ng hÖ m· hoµn toµn míi: c¸c hÖ m· kho¸ c«ng khai. n §3. M· mò. HÖ m· nµy ®−îc Pohlig vµ Hellman ®−a ra n¨m 1978. V V Gi¶ sö p lµ mét sè nguyªn tè lÎ, vµ gi¶ sö kho¸ lËp m· e lµ mét sè nguyªn d−¬ng sao cho (e,p-1)=1. Còng nh− tr−íc ®©y, ®Ó m· ho¸ mét th«ng b¸o, tr−íc tiªn ta chuyÓn c¸c ch÷ c¸i thµnh d¹ng c¸c ch÷ sè t−¬ng øng (thªm sè 0 vµo tr−íc nh÷ng sè cã mét ch÷ sè). Ta dïng b¶ng sau ®©y: a ¨ © b c d ® e ª g h 01 02 03 04 05 06 07 08 09 10 11 i k l m n o « ¬ p q 12 13 14 15 16 17 18 19 20 21 101
r s t u − v x y 22 23 24 25 26 27 28 29 Sau ®ã ta nhãm c¸c sè nhËn ®−îc thµnh tõng nhãm 2m ch÷ sè theo nguyªn t¾c sau: 2m lµ sè nguyªn ch½n lín nhÊt sao cho mäi sè t−¬ng øng víi m ch÷ c¸i (xÐt nh− lµ mét sè nguyªn cã 2m ch÷ sè) ®Òu nhá h¬n p. §Ó dÔ hiÓu, ta gi¶ sö p lµ sè nguyªn tè trong kho¶ng 2929
Sau khi m· ho¸ toµn bé v¨n b¶n, ta nhËn ®−îc v¨n b¶n mËt cÇn chuyÓn lµ: 898 2674 1003 746 1786 2614 §Ó gi¶i m· mét khèi C trong v¨n b¶n mËt, ta cÇn biÕt kho¸ gi¶i m· d. §ã lµ sè d tho¶ m·n de ≡ 1(mod p-1), cã nghÜa lµ d lµ mét nghÞch ®¶o cña e modulo p-1. NghÞch ®¶o ®ã tån t¹i do gi¶ thiÕt (e,p-1)=1. §Ó t×m l¹i ®−îc khèi C trong v¨n b¶n, ta chØ viÖc n©ng khèi C lªn luü thõa d modulo p. ThËt vËy, Cd ≡ (Pe)d ≡ Pde ≡ Pk(p-1)+1 ≡ P(mod p) trong ®ã de=k(p-1)+1 ®èi víi sè nguyªn k nµo ®ã, bëi v× de ≡ 1(mod p-1). VÝ dô. §Ó gi¶i m· mét khèi trong v¨n b¶n mËt ®−îc m· ho¸ b»ng c¸ch sö dông modulo p=2938 vµ kho¸ lËp m· e=31, ta cÇn t×m sè nghÞch ®¶o cña e=31 modulo p-1=2938. ThôËt to¸n Euclid më réng gióp ta dÔ dµng t×m ®−îc d. ThËt vËy, theo c¸c om m kÝ hiÖu cña thuËt to¸n Euclid më réng, ta ®Æt: u=2938, v=31. TÝnh to¸n theo thuËt to¸n ®ã, ta ®−îc kÕt qu¶ sau ®©y: q u1 u2 u3 v1 v2 v3 o - 1 0 2938 0 1 31 94 1 0 1 .C .C 1 -94 31 24 1 -1 -94 95 24 7 h 3 -1 95 7 4 -379 3 th 2 4 -379 3 -9 853 1 at 3 -9 853 1 31 -2938 0 a nM M Nh− vËy, ta cã: 31.853-9.2938=1, vµ d=853 §Ó gi¶i m· khèi C ta dïng c«ng thøc P ≡ C853(mod 2938). n V V §é phøc t¹p cña thuËt to¸n lËp m· vµ gi¶i m· ®èi víi m· mò. Víi mét khèi P trong v¨n b¶n, ta m· ho¸ b»ng c¸ch tÝnh Pe(mod p), sè c¸c phÐp tÝnh bit cÇn thiÕt lµ O((log2 p)3). §Ó gi¶i m· tr−íc hÕt ta ph¶i t×m nghÞch ®¶o d cña e modulo p-1. §iÒu nµy thùc hiÖn ®−îc víi O(log3 p) phÐp tÝnh bit, vµ chØ cÇn lµm mét lÇn. TiÕp theo ®ã, ®Ó t×m l¹i ®−îc khèi P cña v¨n b¶n tõ khèi C cña v¨n b¶n mËt, ta chØ cÇn tÝnh thÆng d− nguyªn d−¬ng bÐ nhÊt cña Cd modulo p: sè c¸c phÐp tÝnh bit ®ßi hái lµ O((log2 p)3). Nh− vËy, thuËt to¸n lËp m· vµ gi¶i m· ®−îc thùc hiÖn t−¬ng ®èi nhanh b»ng m¸y tÝnh. 103
Tuy nhiªn ta sÏ chøng tá r»ng, viÖc gi¶i m· mét v¨n b¶n mËt ®−îc m· ho¸ b»ng mò nãi chung kh«ng thÓ lµm ®−îc nÕu nh− kh«ng biÕt kho¸ e. ThËt vËy, gi¶ sö ta ®· biÕt sè nguyªn tè p dïng lµm modun khi lËp m·, vµ h¬n n÷a, gi¶ sö ®· biÕt khèi C nµo ®ã trong v¨n b¶n mËt t−¬ng øng víi khèi P trong v¨n b¶n, tøc lµ ta ®· biÕt mét ®ång d− thøc C ≡ Pe(mod p) VÊn ®Ò cßn l¹i lµ x¸c ®Þnh e tõ c«ng thøc trªn. Sè e tho¶ m·n ®iÒu kiÖn ®ã ®−îc gäi lµ l«garÝt c¬ sè P cña C modulo p. Cã nhiÒu thuËt to¸n kh¸c nhau ®Ó t×m l«garit c¬ sè ®· cho modulo mét sè nguyªn tè. ThuËt to¸n nhanh nhÊt ®−îc biÕt hiÖn nay ®ßi hái kho¶ng exp( log p log log p) phÐp tÝnh bit. §Ó t×m logarit modulo mét sè nguyªn tè cã n ch÷ sè thËp ph©n, c¸c thuËt to¸n nhanh nhÊt còng ®ßi hái sè phÐp tÝnh bit xÊp xØ sè phÐp tÝnh bit cÇn dïng khi ph©n tÝch mét sè nguyªn n ch÷ sè thµnh thõa om m sè. Nh− vËy, nÕu lµm viÖc víi c¸c m¸y tÝnh cã tèc ®é 1 triÖu phÐp tÝnh trong mét gi©y, khi p cã kho¶ng 100 ch÷ sè thËp ph©n, viÖc t×m logarit modulo p cÇn kho¶ng 74 n¨m, cßn trong tr−êng hîp p cã kho¶ng 200 ch÷ sè, thêi gian cÇn thiÕt lµ 3,8 tû n¨m! o CÇn ph¶i l−u ý r»ng, cã nh÷ng tr−êng hîp viÖc t×m ra logarit modulo p ®−îc thùc .C hiÖn b»ng nh÷ng thuËt to¸n nhanh h¬n rÊt nhiÒu. Ch¼ng h¹n khi p-1 chØ cã nh÷ng .C −íc nguyªn tè nhá, tån t¹i nh÷ng thuËt to¸n ®Æc biÖt cho phÐp tÝnh logarit modulo p víi O(log2 p) phÐp tÝnh bit. Râ rµng nh÷ng sè nguyªn tè nh− vËy kh«ng thÓ dïng ®Ó lËp m·. Trong tr−êng hîp ®ã, ta cã thÓ lÊy q víi p=2q+1, nÕu sè q còng lµ sè nguyªn thh tè (khi ®ã q-1 kh«ng thÓ cã c¸c −íc nguyªn tè nhá). M· mò vµ hÖ thèng cã nhiÒu c¸ thÓ tham gia. at a Mét trong nh÷ng −u ®iÓm cña hÖ m· mò lµ trong mét hÖ thèng cã nhiÒu c¸ thÓ cïng tham gia trao ®æi th«ng tin, tõng cÆp c¸ thÓ hoÆc tõng nhãm nhá c¸ thÓ vÉn cã kh¶ nM n¨ng sö dông kho¸ mËt m· ®ang dïng ®Ó t¹o nh÷ng kho¸ mËt m· chung, bÝ mËt ®èi M víi c¸c c¸ thÓ cßn l¹i cña hÖ thèng. Gi¶ sö p lµ mét sè nguyªn tè lín vµ a lµ mét sè nguyªn, nguyªn tè cïng nhau víi p. Mçi c¸ thÓ trong hÖ thèng chän mét sè k nguyªn tè cïng nhau víi p-1 lµm kho¸ cho n m×nh. Khi hai c¸ thÓ víi c¸c kho¸ k1, k2 muèn lËp mét kho¸ chung ®Ó trao ®æi th«ng tin, c¸ thÓ thø nhÊt göi cho c¸ thÓ thø hai sè nguyªn y1 tÝnh theo c«ng thøc: V V y1 ≡ a k1 (mod p), 0 < y1 < p C¸ thÓ thø hai sÏ t×m ra kho¸ chung k b»ng c¸ch tÝnh k2 k ≡ y1 ≡ a k1k2 (mod p), 0 < k < p T−¬ng tù c¸ thÓ thø hai göi cho c¸ thÓ thø nhÊt sè nguyªn y2 y 2 ≡ a k2 (mod p), 0 < y 2 < p vµ c¸ thÓ thø nhÊt t×m ra kho¸ chung k theo c«ng thøc k2 k ≡ y2 ≡ a k1k2 (mod p) 104
Ta l−u ý r»ng, trong c¸ch lËp kho¸ chung trªn ®©y, c¸c c¸ thÓ thø nhÊt vµ thø hai kh«ng cÇn biÕt kho¸ mËt m· cña nhau, mµ chØ sö dông kho¸ mËt riªng cña m×nh. MÆt kh¸c, c¸c c¸ thÓ cßn l¹i cña mét hÖ thèng còng kh«ng thÓ t×m ra kho¸ chung k ®ã trong mét thêi gian chÊp nhËn ®−îc, v× ®Ó lµm viÖc ®ã, hä ph¶i tÝnh logarit modulo p. Trªn ®©y lµ c¸ch lËp kho¸ chung cña hai c¸ thÓ. Hoµn toµn t−¬ng tù nh− vËy, tõng nhãm c¸c thÓ cã thÓ lËp kho¸ chung. §4. C¸c hÖ mËt m· kho¸ c«ng khai. om Trong tÊt c¶ c¸c hÖ mËt m· tr×nh bµy trªn ®©y, c¸c kho¸ lËp m· ®Òu ph¶i ®−îc gi÷ bÝ m mËt, v× nÕu kho¸ lËp m· bÞ lé th× ng−êi ta cã thÓ t×m ra kho¸ gi¶i m· trong mét thêi gian t−¬ng ®èi ng¾n. Nh− vËy nÕu trong mét hÖ thèng cã nhiÒu cÆp c¸ thÓ hoÆc nhiÒu nhãm c¸ thÓ cÇn trao ®æi th«ng tin mËt víi nhau, sè kho¸ mËt m· chung cÇn gi÷ bÝ o mËt lµ rÊt lín, vµ nh− vËy, khã cã thÓ b¶o ®¶m ®−îc. HÖ m· mµ chóng ta nghiªn cøu d−íi ®©y ®−îc lËp theo mét nguyªn t¾c hoµn toµn míi, trong ®ã viÖc biÕt kho¸ lËp .C .C m· kh«ng cho phÐp t×m ra kho¸ gi¶i m· trong mét thêi gian chÊp nhËn ®−îc. V× thÕ, mçi c¸ thÓ chØ cÇn gi÷ bÝ mËt kho¸ gi¶i m· cña riªng m×nh, trong khi kho¸ lËp m· ®−îc th«ng b¸o c«ng khai. Trong tr−êng hîp mét trong c¸c c¸ thÓ bÞ lé kho¸ gi¶i m· cña m×nh, bÝ mËt cña c¸c c¸ thÓ cßn l¹i kh«ng hÒ bÞ ¶nh h−ëng. LÝ do cña viÖc cã thÓ thh x©y dùng nh÷ng hÖ m· nh− vËy chÝnh lµ ®iÒu ta ®· nãi ®Õn khi xÐt c¸c hÖ m· mò: ®é phøc t¹p cña thuËt to¸n t×m logarit modulo p lµ qu¸ lín. at Tr−íc hÕt, ta nãi s¬ qua vÒ nguyªn t¾c cña c¸c hÖ m· kho¸ c«ng khai. Gi¶ sö trong a hÖ thèng ®ang xÐt cã n c¸ thÓ cïng trao ®æi c¸c th«ng tin mËt. Mçi c¸c thÓ chän cho m×nh mét kho¸ lËp m· k vµ mét c«ng thøc m· ho¸ E(k), ®−îc th«ng b¸o c«ng khai. nM M Nh− vËy cã n kho¸ lËp m· c«ng khai k1, k2,...,kn. Khi c¸ thÓ thø i muèn göi th«ng b¸o cho c¸ thÓ thø j, còng nh− tr−íc ®©y, mçi ch÷ trong th«ng b¸o ®−îc chuyÓn thµnh sè, nhãm thµnh tõng khèi víi ®é dµi nµo ®ã. Sau ®ã, mçi khèi P trong v¨n b¶n ®−îc m· ho¸ b»ng kho¸ lËp m· E(kj) cña c¸ thÓ thø j (®· th«ng b¸o c«ng khai), vµ göi ®i d−íi n d¹ng C=E(kj)(P). §Ó gi¶i m· th«ng b¸o nµy, c¸ thÓ thø j chØ cÇn dïng kho¸ gi¶i m· (bÝ mËt riªng cho m×nh) Dk j V V Dk j (C)= Dk j E k j ( P) = P , bëi v× Dk j vµ E k j lµ c¸c kho¸ gi¶i m· vµ lËp m· cña cïng c¸ thÓ thø j. C¸c c¸ thÓ trong hÖ thèng, nÕu nhËn ®−îc v¨n b¶n mËt, còng kh«ng thÓ nµo gi¶i m·, v× viÖc biÕt kho¸ lËp m· E k j kh«ng cho phÐp t×m ra kho¸ gi¶i m· Dk j . §Ó cô thÓ ho¸ nguyªn t¾c võa tr×nh bµy, ta xÐt vÝ dô trªn hÖ m· kho¸ c«ng khai ®−îc t×m thÊy ®Çu tiªn n¨m 1978 bëi Rivest, Shamir vµ Adleman (xem[ RSA]) (th−êng ®−îc gäi lµ hÖ m· RSA). HÖ RSA ®−îc x©y dùng trªn c¬ së m· mò, trong ®ã kho¸ lµ cÆp (e,n), gåm sè mò e vµ modun n. Sè n ®−îc dïng ë ®©y lµ tÝch cña hai sè nguyªn tè rÊt lín nµo ®ã, n=pq, 105
sao cho (e, φ (n))=1, trong ®ã φ (n) lµ hµm Euler. §Ó m· ho¸ mét th«ng b¸o, tr−íc tiªn ta chuyÓn c¸c ch÷ c¸i thµnh c¸c sè t−¬ng øng vµ nhãm thµnh c¸c khèi víi ®é dµi lín nhÊt cã thÓ (tuú thuéc kh¶ n¨ng tÝnh to¸n) víi mét sè ch½n ch÷ sè. §Ó m· ho¸ mét khèi P trong v¨n b¶n, ta lËp khèi C trong v¨n b¶n mËt b»ng c«ng thøc: E(P) ≡ C ≡ Pe(mod n), 0
B©y giê ta chØ ra r»ng, hÖ m· RSA tho¶ m·n c¸c nguyªn t¾c cña hÖ m· kho¸ c«ng khai nãi ë ®Çu tiÕt nµy. Tr−íc tiªn, ta chó ý r»ng, mçi c¸ thÓ ph¶i chän hai sè nguyªn tè lín p vµ q, cì chõng 100 ch÷ sè thËp ph©n. §iÒu nµy cã thÓ lµ trong Ýt phót nhê mét m¸y tÝnh. Khi c¸c sè nguyªn tè p vµ q ®· ®−îc chän, sè mò dïng ®Ó m· ho¸ e sÏ ®−îc lÊy sao cho (e, φ (qp))=1. Nãi chung nªn chän e lµ sè nguyªn tè tuú ý lín h¬n q vµ p. Sè e ®−îc chän nhÊt thiÕt ph¶i tho¶ m·n 2e>n=pq. NÕu ®iÒu kiÖn nµy kh«ng ®−îc tho¶ m·n, ta cã C=Pen ®−îc tho¶ m·n, mäi khèi P kh¸c 0 vµ 1 ®Òu ®−îc m· ho¸ b»ng c¸ch n©ng lªn luü thõa vµ lÊy ®ång d− theo modulo n. Ta cÇn ph¶i chøng tá r»ng, viÖc biÕt kho¸ lËp m· (c«ng khai) (e,n) kh«ng ®Én ®Õn viÖc t×m ®−îc kho¸ gi¶i m· (d,n). Chó ý r»ng, ®Ó t×m nghÞch ®¶o d cña e modulo φ (n), tr−íc tiªn ph¶i t×m ®−îc φ (n). om ViÖc t×m φ (n) kh«ng dÔ h¬n so víi ph©n tÝch n, bëi v×, mét khi biÕt φ (n) vµ n, ta sÏ m ph©n tÝch ®−îc n=pq. ThËt vËy, ta cã: o p+q=n- φ (n)+1 .C .C p-q= ( p + q ) 2 − 4qp = ( p + q ) 2 − 4n Tõ c¸c c«ng thøc ®ã t×m ®−îc q vµ p. thh NÕu ta chän c¸c sè p vµ q kho¶ng 100 ch÷ sè thËp ph©n, th× n sÏ cã kho¶ng 200 ch÷ sè thËp ph©n. §Ó ph©n tÝch mét sè nguyªn cì lín nh− thÕ, víi c¸c thuËt to¸n nhanh at nhÊt hiÖn nay vµ víi nh÷ng m¸y tÝnh hiÖn ®¹i nhÊt, ta mÊt kho¶ng 3,8 tû n¨m! a Cã mét vµi ®iÒu cÇn l−u ý khi chän c¸c sè p vµ q ®Ó tr¸nh r¬i vµo tr−êng hîp tÝch pq bÞ ph©n tÝch nhanh nhê nh÷ng thuËt to¸n ®Æc biÖt: q vµ p cÇn chän sao cho p-1 vµ q-1 nM M chØ cã c¸c thõa sè nguyªn tè lín, (p-1,q-1) ph¶i nhá, q vµ p ph¶i cã sè ch÷ sè trong khai triÓn thËp ph©n kh¸c nhau kh«ng nhiÒu. Cã thÓ n¶y ra c©u hái: trong mét hÖ thèng nhiÒu c¸ thÓ tham gia, c¸c kho¸ lËp m· ®· n l¹i ®−îc c«ng khai, lµm sao cã thÓ tr¸nh ®−îc tr−êng hîp mét c¸ thÓ nµy “m¹o danh” mét c¸ thÓ kh¸c ®Ó göi th«ng b¸o cho mét c¸ thÓ thø ba? Nãi c¸ch kh¸c lµm sao cã V thÓ “kÝ tªn” d−íi c¸c th«ng b¸o mËt? VÊn ®Ò nµy ®−îc gi¶i quyÕt ®¬n gi¶n nh− sau: V Gi¶ sö “«ng I” cÇn kÝ tªn d−íi th«ng b¸o göi “«ng J”. Khi ®ã, tr−íc tiªn, «ng I tÝnh S ≡ D (I) ≡ I d i (mod n ). ki i Chó ý r»ng chØ cã «ng I lµm ®−îc viÖc nµy, v× trong c«ng thøc sö dông kho¸ gi¶i m· cña «ng I. Sau ®ã, I sÏ göi cho J th«ng b¸o e C ≡ E k j ( S ) = S j (mod n j ) , trong ®ã (ej,nj) lµ kho¸ lËp m· cña J. Khi nhËn ®−îc, ®Ó gi¶ m·, J tr−íc tiªn dïng kho¸ gi¶i m· riªng cña m×nh ®Ó nhËn ra S: 107
Dk j (C ) ≡ Dk j ( E k j ( S )) ≡ S §Ó x¸c minh S ®Ých thùc lµ ch÷ kÝ cña I, J chØ cßn viÖc ¸p dông vµo S kho¸ lËp m· c«ng khai cña I: E ki ( S ) ≡ E ki Dki ( I ) ≡ I Chó ý c¸ch lµ nh− trªn thÝch hîp khi nj>ni, v× khi ®ã ta lu«n cã S
Bµi tËp vµ tÝnh to¸n thùc hµnh ch−¬ng 6. I. Bµi tËp 6.1. BiÕt r»ng th«ng b¸o sau ®©y ®· ®−îc m· ho¸ b»ng m· Ceasar (víi kho¸ k nµo ®ã trong kho¶ng 1-29), h·y t×m kho¸ vµ gi¶i m·: S¤EMR IEIEH USSOT SLU¥I EI¤HE ITSA¢ U¥IEI ¤LU¥I ES¤YB SOS¤E MRDEI EI¤X¢ EI¤BS ORMCE SXS¤L GDES¤ MBSO¡ ¤MTMR 6.2. Dïng m· khèi ®Ó m· ho¸ c©u om CO C¤NG MAI S¡T CO NGAY N£N KIM m víi kho¸ ma trËn lµ  24 22 o    11 10 .C .C 6.3. Gi¶i m· c©u sau ®©y, biÕt r»ng nã ®−îc m· ho¸ b»ng khèi víi ma trËn  8 4    17 11 thh OD O¢ XC ¥¥ EP Y¥ NR EY at 6.4. Cã thÓ lËp m· khèi theo c¸ch sau ®©y. Gi¶ sö A, B lµ c¸c ma trËn vu«ng cÊp hai. a Qu¸ tr×nh m· ho¸ ®−îc thùc hiÖn bëi c«ng thøc nM C ≡ AP+B(mod 29). M H·y viÕt c«ng thøc gi¶ m· vµ cho mét vÝ dô cô thÓ. 6.5. M· ho¸ c©u sau ®©y b»ng m· mò víi p=3137, e=31: n §£N N¥I AN TOAN V V 6.6. H·y gi¶i m· v¨n b¶n mËt sau ®©y, nÕu biÕt nã ®−îc m· ho¸ b»ng m· mò víi p=3137, e=31: 0206 0248 1345 2200 6.7. Chøng minh r»ng, khi lËp m· RSA, nÕu xÈy ra tr−êng hîp cã mét tõ P nµo ®ã trong th«ng b¸o kh«ng nguyªn tè cïng nhau víi kho¸ n=pq ®· chän, vµ tõ nµy bÞ ph¸t hiÖn, th× nh©n viªn ph©n tÝch m· cã thÓ ph©n tÝch ®−îc n ra thõa sè nguyªn tè, vµ do ®ã, t×m ®−îc kho¸ gi¶i m·. 6.8. Chøng minh r»ng, nÕu c¸c sè q, p ®−îc chän ®ñ lín th× tr−êng hîp “rñi ro” nãi trong bµi tËp 6.7 x¶y ra víi x¸c suÊt rÊt nhá. 6.9. Dïng kho¸ víi n=3233, e=17 ®Ó m· ho¸ c©u 109