An toàn thông tin - Chủ đề 4: Mã hóa bất đối xứng

Nội dung text: An toàn thông tin - Chủ đề 4: Mã hóa bất đối xứng

1. ChChủđủđềề4:4: MãMã hĩahĩa bbấấtt đốđốixixứứngng
2. MMởđởđầầuu VVấấnn đđềề phpháátt sinhsinh trongtrong ccáácc hhệệ ththốốngng mãmã hhĩĩaa quyquy ưướớcc llàà viviệệcc quyquy ưướớcc chungchung mãmã khkhĩĩaa kk gigiữữaa ngngưườờii ggửửii AA vvàà ngngưườờii nhnhậậnn B.B. TrênTrên ththựựcc ttếế,, nhunhu ccầầuu thaythay đđổổii nnộộii dungdung ccủủaa mãmã khkhĩĩaa kk llàà ccầầnn thithiếếtt,, dodo đđĩĩ,, ccầầnn ccĩĩ ssựự traotrao đđổổii thơngthơng tintin vvềề mãmã khkhĩĩaa kk gigiữữaa AA vvàà B.B. ĐĐểể bbảảoo mmậậtt mãmã khkhĩĩaa kk,, AA vvàà BB phphảảii traotrao đđổổii vvớớii nhaunhau trêntrên mmộộtt kênhkênh liênliên llạạcc ththậậtt ssựự anan totồànn vvàà bbíí mmậậtt TuyTuy nhiênnhiên,, rrấấtt khkhĩĩ ccĩĩ ththểể bbảảoo đđảảmm đưđượợcc ssựự anan totồànn ccủủaa kênhkênh liênliên llạạcc nênnên mãmã khkhĩĩaa kk vvẫẫnn ccĩĩ ththểể bbịị phpháátt hihiệệnn bbởởii ngngưườờii C!C!
3. MMởđởđầầuu ÝÝ ttưưởởngng vvềề hhệệ ththốốngng mãmã hhĩĩaa khkhĩĩaa cơngcơng ccộộngng đưđượợcc MartinMartin Hellman,Hellman, RalphRalph MerkleMerkle vvàà WhitfieldWhitfield DiffieDiffie ttạạii ĐĐạạii hhọọcc StanfordStanford gigiớớii thithiệệuu vvààoo nnăămm 1976.1976. SauSau đđĩĩ,, phphươươngng phpháápp DiffieDiffie HellmanHellman ccủủaa MartinMartin HellmanHellman vvàà WhitfieldWhitfield DiffieDiffie đđãã đưđượợcc cơngcơng bbốố NNăămm 1977,1977, trêntrên bbááoo ""TheThe ScientificScientific AmericanAmerican",", nhnhĩĩmm ttáácc gigiảả RonaldRonald RivestRivest,, AdiAdi ShamirShamir vvàà LeonardLeonard AdlemanAdleman đđãã cơngcơng bbốố phphươươngng phpháápp RSA,RSA, phphươươngng phpháápp mãmã hhĩĩaa khkhĩĩaa cơngcơng ccộộngng nnổổii titiếếngng vvàà đưđượợcc ssửử ddụụngng rrấấtt nhinhiềềuu hihiệệnn naynay trongtrong ccáácc ứứngng ddụụngng mãmã hhĩĩaa vvàà bbảảoo vvệệ thơngthơng tintin
4. MMởđởđầầuu MMộộtt hhệệ ththốốngng khkhĩĩaa cơngcơng ccộộngng ssửử ddụụngng haihai loloạạii khkhĩĩaa trongtrong ccùùngng mmộộtt ccặặpp khkhĩĩaa:: khkhĩĩaa cơngcơng ccộộngng (public(public key)key) đưđượợcc cơngcơng bbốố rrộộngng rãirãi vvàà đưđượợcc ssửử ddụụngng trongtrong mãmã hhĩĩaa thơngthơng tin,tin, khkhĩĩaa riêngriêng (private(private key)key) chchỉỉ dodo mmộộtt ngngưườờii nnắắmm gigiữữ vvàà đưđượợcc ssửử ddụụngng đđểể gigiảảii mãmã thơngthơng tintin đđãã đưđượợcc mãmã hhĩĩaa bbằằngng khkhĩĩaa cơngcơng ccộộngng CCáácc phphươươngng phpháápp mãmã hhĩĩaa nnààyy khaikhai ththáácc nhnhữữngng áánhnh xxạạ ff mmàà viviệệcc ththựựcc hihiệệnn áánhnh xxạạ ngngưượợcc ff –1 rrấấtt khkhĩĩ soso vvớớii viviệệcc ththựựcc hihiệệnn áánhnh xxạạ ff ChChỉỉ khikhi bibiếếtt đưđượợcc mãmã khkhĩĩaa riêngriêng ththìì mmớớii ccĩĩ ththểể ththựựcc hihiệệnn đưđượợcc áánhnh xxạạ ngngưượợcc ff –1
5. MãMã hhĩahĩĩaa khkkhhĩaĩĩaa cơngccơngơng ccộộngng
6. PhPhươươngng pháppháp RSARSA NNăămm 1978,1978, R.L.RivestR.L.Rivest,, A.ShamirA.Shamir vvàà L.AdlemanL.Adleman đđãã đđềề xuxuấấtt hhệệ ththốốngng mãmã hhĩĩaa khkhĩĩaa cơngcơng ccộộngng RSARSA ((hhayay cịncịn đưđượợcc ggọọii llàà ““hhệệ ththốốngng MITMIT””).). TrongTrong phphươươngng phpháápp nnààyy,, ttấấtt ccảả ccáácc phphéépp ttíínhnh đđềềuu đưđượợcc ththựựcc hihiệệnn trêntrên ZZn vvớớii nn llàà ttííchch ccủủaa haihai ssốố nguyênnguyên ttốố llẻẻ pp vvàà qq khkháácc nhaunhau KhiKhi đđĩĩ,, tata ccĩĩ φφ((nn)) == ((pp––1)1) ((qq––1)1)
7. PhPhươươngng pháppháp mãmã hĩahĩa RRSASA nn == pqpq vvớớii pp vvàà qq llàà haihai ssốố nguyênnguyên ttốố llẻẻ phânphân bibiệệtt ChoCho PP == CC == ZZn vvàà đđịịnhnh nghnghĩĩaa:: KK == {({((n,(n, p,p, q,q, a,a, bb):): nn == pqpq,, pp,, qq llàà ssốố nguyênnguyên ttốố,, abab ≡≡ 11 (mod(mod φφ((nn))}))} VVớớii mmỗỗii kk == (n,(n, p,p, q,q, a,a, bb)) ∈∈ KK,, đđịịnhnh nghnghĩĩaa:: b a eek((xx)) == xx modmod nn vvàà ddk((yy)) == yy modmod nn,, vvớớii xx,, yy ∈∈ ZZn GiGiáá trtrịị nn vvàà bb đưđượợcc cơngcơng bbốố (public(public key)key) GiGiáá trtrịị pp,, qq,, aa đưđượợcc gigiữữ bbíí mmậậtt (private(private key)key)
8. SSửử ddụụngng phphươươngng pháppháp RSARSA PhPháátt sinhsinh haihai ssốố nguyênnguyên ttốố ccĩĩ gigiáá trtrịị llớớnn pp vvàà qq TTíínhnh nn == pqpq vvàà φφ((nn)) == ((pp –– 1)1) ((qq –– 1)1) ChChọọnn ngngẫẫuu nhiênnhiên mmộộtt ssốố nguyênnguyên bb (1(1 << bb << φφ((nn)))) ththỏỏaa gcd(gcd(bb,, φφ((nn)))) == 11 TTíínhnh gigiáá trtrịị aa == bb–1 modmod φφ((nn)) ((bbằằngng thuthuậậtt totốánn EuclideEuclide mmởở rrộộngng)) GiGiáá trtrịị nn vvàà bb đưđượợcc cơngcơng bbốố ((khkhĩĩaa cơngcơng ccộộngng)) gigiáá trtrịị pp,, qq,, aa đưđượợcc gigiữữ bbíí mmậậtt ((khkhĩĩaa riêngriêng))
9. VíVí ddụụ p=5 & q=7 n=5*7=35 và φ(n) =(4)*(6) = 24 b = 5 a = 29 , (29x5 –1) chia hết cho 24 Cặp khĩa được xác định như sau: Khĩa cơng cộng: (n,b) = (35,5) Khĩa riêng: (n,a) = (35, 29) Mã hĩa từ love sử dụng cơng thức (e = xb mod n) Giả sử các ký tự Alphabet nằm trong khoảng từ 1Ỉ26 Plain Text Numeric xb Cipher Text (e = xb Representation mod n) l 12 248832 17 o 15 759375 15 v 22 5153632 22 e 5 3125 10
10. VíVí ddụụ Giải mã từ love sử dụng cơng thức (d = ya mod n) n = 35, a=29 Cipher ya (d = ya Plain Text mod n) Text 17 481968572106750915091411825223072000 12 l 15 12783403948858939111232757568359400 15 o 22 852643319086537701956194499721110000000 22 v 10 100000000000000000000000000000 5 e
11. MMộộtstsốố phphươươngng pháppháp ttấấnn ccơngơng RSARSA TTíínhnh chchấấtt anan totồànn ccủủaa phphươươngng phpháápp RSARSA ddựựaa trêntrên ccơơ ssởở chichi phphíí chocho viviệệcc gigiảảii mãmã bbấấtt hhợợpp llệệ thơngthơng tintin đđãã đưđượợcc mãmã hhĩĩaa ssẽẽ ququáá llớớnn nênnên xemxem nhnhưư khơngkhơng ththểể ththựựcc hihiệệnn đưđượợcc VVìì khkhĩĩaa llàà cơngcơng ccộộngng nênnên viviệệcc ttấấnn cơngcơng bbẻẻ khkhĩĩaa phphươươngng phpháápp RSARSA ththưườờngng ddựựaa vvààoo khkhĩĩaa cơngcơng ccộộngng đđểể xxáácc đđịịnhnh đưđượợcc khkhĩĩaa riêngriêng ttươươngng ứứngng ĐĐiiềềuu quanquan trtrọọngng llàà ddựựaa vvààoo nn đđểể ttíínhnh pp,, qq ccủủaa nn,, ttừừ đđĩĩ ttíínhnh đưđượợcc dd
12. PhPhươươngng pháppháp ssửử ddụụngng φφ((nn)) GiGiảả ssửử ngngưườờii ttấấnn cơngcơng bibiếếtt đưđượợcc gigiáá trtrịị φφ((nn).). KhiKhi đđĩĩ viviệệcc xxáácc đđịịnhnh gigiáá trtrịị pp,, qq đưđượợcc đưđưaa vvềề viviệệcc gigiảảii haihai phphươươngng trtrììnhnh sausau nn == pp ⋅⋅ qq ThayThay qq == nn//pp,, tata đưđượợcc phphươươngng trtrììnhnh bbậậcc haihai φ(n) = (p −1)(q −1) p 2 − (n −φ(n)+1)p + n = 0 pp,, qq chchíínhnh llàà haihai nghinghiệệmm ccủủaa phphươươngng trtrììnhnh bbậậcc haihai nnààyy TuyTuy nhiênnhiên vvấấnn đđềề phpháátt hihiệệnn đưđượợcc gigiáá trtrịị φφ((nn)) cịncịn khkhĩĩ hhơơnn viviệệcc xxáácc đđịịnhnh haihai ththừừaa ssốố nguyênnguyên ttốố ccủủaa nn
13. ThuThuậậtt ttốnốn phânphân ttíchích rraa tthhừừasasốố pp-1-1 NhNhậậpp nn vvàà BB 1.1. aa == 22 2.2. forfor jj == 22 toto BB dodo aa == aaj modmod nn 3.3. dd == gcd(gcd(aa −− 1,1, nn)) 4.4. ifif 11 << dd << nn thenthen dd llàà ththừừaa ssốố nguyênnguyên ttốố ccủủaa nn ((ththàànhnh cơngcơng)) elseelse khơngkhơng xxáácc đđịịnhnh đưđượợcc ththừừaa ssốố nguyênnguyên ttốố ccủủaa nn ((ththấấtt bbạạii))
14. ThuThuậậtt ttốnốn phânphân ttíchích rraa tthhừừasasốố pp-1-1 ThuThuậậtt totốánn PollardPollard pp 11 (1974)(1974) llàà mmộộtt trongtrong nhnhữữngng thuthuậậtt totốánn đơđơnn gigiảảnn hihiệệuu ququảả ddùùngng đđểể phânphân ttííchch rara ththừừaa ssốố nguyênnguyên ttốố ccáácc ssốố nguyênnguyên llớớnn ThamTham ssốố đđầầuu vvààoo ccủủaa thuthuậậtt totốánn llàà ssốố nguyênnguyên ((llẻẻ)) nn ccầầnn đưđượợcc phâphânn ttííchch rara ththừừaa ssốố nguyênnguyên ttốố vvàà gigiáá trtrịị gigiớớii hhạạnn BB GiGiảả ssửử nn == p.qp.q ((pp,, qq chchưưaa bibiếếtt)) vvàà BB llàà mmộộtt ssốố nguyênnguyên đđủủ llớớnn,, vvớớii mmỗỗii ththừừaa ssốố nguyênnguyên ttốố kk,, k ≤ B ∧ k (p −1) ⇒ ()p −1 B!
15. ThuThuậậtt ttốnốn phânphân ttíchích rraa tthhừừasasốố pp-1-1 ỞỞ cucuốốii vịngvịng llặặpp ((bbưướớcc 2),2), tata ccĩĩ aa ≡≡ 22B! (mod(mod nn)) SuySuy rara:: aa ≡≡ 22B! (mod(mod pp)) DoDo pp||nn nênnên theotheo đđịịnhnh lýlý Fermat,Fermat, tata ccĩĩ :: 22p-1 ≡≡ 11 (mod(mod pp)) DoDo ((pp 1)|1)|BB!,!, nênnên ởở bbưướớcc 33 ccủủaa thuthuậậtt totốánn,, tata ccĩĩ:: aa ≡≡ 11 (mod(mod pp)) VVìì ththếế,, ởở bbưướớcc 4:4: pp|(|(aa −− 1)1) vvàà pp||nn nênnên nnếếuu dd == gcd(gcd(aa −− 1,1,nn)) ththìì dd == pp
16. ThuThuậậtt ttốnốn phânphân ttíchích rraa tthhừừasasốố pp-1-1 VVíí ddụụ:: GiGiảả ssửử nn == 15770708441.15770708441. ÁÁpp ddụụngng thuthuậậtt totốánn pp –– 11 vvớớii BB == 180,180, chchúúngng tata xxáácc đđịịnhnh đưđượợcc aa == 1162022142511620221425 ởở bbưướớcc 33 ccủủaa thuthuậậtt totốánn vvàà xxáácc đđịịnhnh đưđượợcc gigiáá trtrịị dd == 135979.135979. TrongTrong trtrưườờngng hhợợpp nnààyy,, viviệệcc phânphân ttííchch rara ththừừaa ssốố nguyênnguyên ttốố ththàànhnh cơngcơng dodo gigiáá trtrịị 135978135978 chchỉỉ ccĩĩ ccáácc ththừừaa ssốố nguyênnguyên ttốố nhnhỏỏ khikhi phânphân ttííchch rara ththừừaa ssốố nguyênnguyên ttốố:: 135978135978 == 22 ×× 33 ×× 131131 ×× 173173 DoDo đđĩĩ,, khikhi chchọọnn BB ≥≥ 173173 ssẽẽ đđảảmm bbảảoo đđiiềềuu kikiệệnn 135978135978⏐⏐ BB!!
17. ThuThuậậtt ttốnốn phânphân ttíchích rraa tthhừừasasốố pp-1-1 TrongTrong thuthuậậtt totốánn pp −− 11 ccĩĩ BB −− 11 phphéépp ttíínhnh llũũyy ththừừaa modulo,modulo, mmỗỗii phphéépp đđịiịi hhỏỏii ttốốii đđaa 2log2log2BB phphéépp nhânnhân modulomodulo ssửử ddụụngng thuthuậậtt totốánn bbììnhnh phphươươngng vvàà nhânnhân ViViệệcc ttíínhnh USCLNUSCLN ssửử ddụụngng thuthuậậtt totốánn EuclideEuclide ccĩĩ đđộộ phphứứcc ttạạpp OO((log((log nn))3).). NhNhưư vvậậyy,, đđộộ phphứứcc ttạạpp ccủủaa thuthuậậtt totốánn llàà OO((BB loglog BB(log(log nn))2 ++ (log(log nn))3))
18. ThuThuậậtt ttốnốn phânphân ttíchích rraa tthhừừasasốố pp-1-1 XXáácc susuấấtt chchọọnn gigiáá trtrịị BB ttươươngng đđốốii nhnhỏỏ vvàà ththỏỏaa đđiiềềuu kikiệệnn llàà rrấấtt ththấấpp KhiKhi ttăăngng gigiáá trtrịị BB ((chchẳẳngng hhạạnn nhnhưư B ≈ n )) ththìì gigiảảii thuthuậậtt ssẽẽ ththàànhnh cơngcơng,, nhnhưưngng thuthuậậtt totốánn nnààyy ssẽẽ khơngkhơng nhanhnhanh hhơơnn gigiảảii thuthuậậtt chiachia ddầầnn nhnhưư trtrììnhnh bbààyy trêntrên
19. ThuThuậậtt ttốnốn phânphân ttíchích rraa tthhừừasasốố pp-1-1 GiGiảảii thuthuậậtt nnààyy chchỉỉ hihiệệuu ququảả khikhi ttấấnn cơngcơng phphươươngng phpháápp RSARSA trongtrong trtrưườờngng hhợợpp nn ccĩĩ ththừừaa ssốố nguyênnguyên ttốố pp mmàà ((pp −− 1)1) chchỉỉ ccĩĩ ccáácc ưướớcc ssốố nguyênnguyên ttốố rrấấtt nhnhỏỏ ChChúúngng tata ccĩĩ ththểể ddễễ ddààngng xâyxây ddựựngng mmộộtt hhệệ ththốốngng mãmã hhĩĩaa khkhĩĩaa cơngcơng ccộộngng RSARSA anan totồànn đđốốii vvớớii gigiảảii thuthuậậtt ttấấnn cơngcơng pp −− 1.1. CCááchch đơđơnn gigiảảnn nhnhấấtt llàà ttììmm mmộộtt ssốố nguyênnguyên ttốố pp1 llớớnn,, mmàà pp == 22pp1 ++ 11 ccũũngng llàà ssốố nguyênnguyên ttốố,, ttươươngng ttựự ttììmm qq1 nguyênnguyên ttốố llớớnn vvàà qq == 22qq1 ++ 11 nguyênnguyên ttốố
20. BBẻẻ khĩakhĩa ddựựaa ttrênrên cáccác ttấấnn ccơngơng llặặplplạạii SimonsSimons vvàà Norris:Norris: hhệệ ththốốngng RSARSA ccĩĩ ththểể bbịị ttổổnn ththươươngng khikhi ssửử ddụụngng ttấấnn cơngcơng llặặpp liênliên titiếếpp NNếếuu đđốốii ththủủ bibiếếtt ccặặpp khkhĩĩaa cơngcơng ccộộngng {{nn,, bb}} vvàà ttừừ khkhĩĩaa CC ththìì ccĩĩ ththểể ttíínhnh chuchuỗỗii ccáácc ttừừ khkhĩĩaa sausau:: e C1=C (mod n) e C2=C1 (mod n) e Ci=Ci-1 (mod n) NNếếuu ccĩĩ mmộộtt phphầầnn ttửử CCj trongtrong chuchuỗỗii CC1,, CC2,, CC3,, .,., CCi saosao chocho CCj == CC ththìì khikhi đđĩĩ ssẽẽ ttììmm đưđượợcc MM == CCj-1 vvìì e Cj = Cj-1 (mod n) C = Me (mod n)
21. BBẻẻ khĩakhĩa ddựựaa ttrênrên cáccác ttấấnn ccơngơng llặặplplạạii VVíí ddụụ:: GiGiảả ssửử anhanh tata bibiếếtt {{nn,, bb,, CC}={35,}={35, 17,17, 3},3},anhanh tata ssẽẽ ttíínhnh:: e CC1 == CC ((modmod nn)) == 317317 ((modmod 35)35) == 3333 e CC2 == CC1 (mod(mod nn)) == 33173317 (mod(mod 35)35) == 33 VVìì CC2 == CC nênnên MM == CC1 == 3333
22. SSựự cheche ddấấuu tthơnghơng tintin trongtrong hhệệ ththốốngng RSARSA HHệệ ththốốngng RSARSA ccĩĩ đđặặcc đđiiểểmm llàà thơngthơng tintin khơngkhơng phphảảii luơnluơn đưđượợcc cheche ddấấuu GiGiảả ssửử ngngưườờii ggởởii ccĩĩ ee == 17,17, nn == 35.35. NNếếuu anhanh tata mumuốốnn ggởởii bbấấtt ccứứ ddữữ liliệệuu nnààoo thuthuộộcc ttậậpp sausau {1,{1, 6,6, 7,7, 8,8, 13,13, 14,14, 15,15, 20,20, 21,21, 22,22, 27,27, 28,28, 29,29, 34}34} ththìì kkếếtt ququảả ccủủaa viviệệcc mãmã hhĩĩaa llạạii chchíínhnh llàà ddữữ liliệệuu banban đđầầuu NghNghĩĩaa llàà,, MM == MMe modmod nn CịnCịn khikhi pp == 109,109, qq == 97,97, ee == 865865 ththìì hhệệ ththốốngng hohồànn totồànn khơngkhơng ccĩĩ ssựự cheche ddấấuu thơngthơng tin,tin, bbởởii vvìì:: ∀∀MM,, MM == MM865 modmod (109*97)(109*97)
23. SSựự cheche ddấấuu tthơnghơng tintin trongtrong hhệệ ththốốngng RSARSA VVớớii mmỗỗii gigiáá trtrịị nn,, ccĩĩ íítt nhnhấấtt 99 trtrưườờngng hhợợpp kkếếtt ququảả mãmã hhĩĩaa chchíínhnh llàà ddữữ liliệệuu ngunguồồnn banban đđầầuu ThThậậtt vvậậyy,, MM == MMe modmod nn hayhay:: MM == MMe modmod pp vvàà MM == MMe modmod qq (*)(*) VVớớii mmỗỗii ee,, mmỗỗii đđẳẳngng ththứứcc trongtrong (*)(*) ccĩĩ íítt nhnhấấtt baba gigiảảii phpháápp thuthuộộcc ttậậpp {0,{0, 1,1, 1}.1}. SSốố thơngthơng đđiiệệpp khơngkhơng đưđượợcc cheche ddấấuu ((khơngkhơng bbịị thaythay đđổổii sausau khikhi mãmã hhĩĩaa):): mm == [1+[1+gcdgcd((ee 1,1, pp 1)][1+1)][1+gcdgcd((ee 1),1), qq 1]1]
24. NhNhậậnxnxéétt MMấấuu chchốốtt đđểể ccĩĩ ththểể gigiảảii mãmã đưđượợcc thơngthơng tintin llàà ccĩĩ đưđượợcc gigiáá trtrịị pp vvàà qq ttạạoo nênnên gigiáá trtrịị nn KhiKhi ccĩĩ đưđượợcc haihai gigiáá trtrịị nnààyy,, tata ccĩĩ ththểể ddễễ ddààngng ttíínhnh rara đưđượợcc φφ((nn)) == ((pp –– 1)(1)(qq –– 1)1) vvàà gigiáá trtrịị aa == bb–1 modmod φφ((nn)) theotheo thuthuậậtt totốánn EuclideEuclide mmởở rrộộngng NNếếuu ssốố nguyênnguyên nn ccĩĩ ththểể đưđượợcc phânphân ttííchch rara ththừừaa ssốố nguyênnguyên ttốố,, ttứứcc llàà gigiáá trtrịị pp vvàà qq ccĩĩ ththểể đưđượợcc xxáácc đđịịnhnh ththìì xemxem nhnhưư ttíínhnh anan totồànn ccủủaa phphươươngng phpháápp RSARSA khơngkhơng cịncịn đưđượợcc bbảảoo đđảảmm nnữữaa
25. NhNhậậnxnxéétt NhNhưư vvậậyy,, ttíínhnh anan totồànn ccủủaa phphươươngng phpháápp RSARSA ddựựaa trêntrên ccơơ ssởở ccáácc mmááyy ttíínhnh ttạạii ththờờii đđiiểểmm hihiệệnn ttạạii chchưưaa đđủủ khkhảả nnăăngng gigiảảii quyquyếếtt viviệệcc phânphân ttííchch ccáácc ssốố nguyênnguyên rrấấtt llớớnn rara ththừừaa ssốố nguyênnguyên ttốố NNăămm 1994,1994, PeterPeter ShorShor,, mmộộtt nhnhàà khoakhoa hhọọcc ttạạii phịngphịng ththíí nghinghiệệmm AT&T,AT&T, đđãã đưđưaa rara mmộộtt thuthuậậtt totốánn ccĩĩ ththểể phânphân ttííchch mmộộtt ccááchch hihiệệuu ququảả ccáácc ssốố nguyênnguyên rrấấtt llớớnn trêntrên mmááyy ttíínhnh llưượợngng ttửử
26. VVấấnn đềđề ssốố nguyênnguyên ttốố ĐĐểể bbảảoo đđảảmm anan totồànn chocho hhệệ ththốốngng mãmã hhĩĩaa RSA,RSA, ssốố nguyênnguyên nn == pqpq phphảảii đđủủ llớớnn đđểể khơngkhơng ththểể ddễễ ddààngng titiếếnn hhàànhnh viviệệcc phânphân ttííchch nn rara ththừừaa ssốố nguyênnguyên ttốố HiHiệệnn ttạạii,, ccáácc thuthuậậtt totốánn phânphân ttííchch ththừừaa ssốố nguyênnguyên ttốố đđãã ccĩĩ ththểể gigiảảii quyquyếếtt đưđượợcc ccáácc ssốố nguyênnguyên ccĩĩ trêntrên 130130 chchữữ ssốố ((ththậậpp phânphân).). ĐĐểể anan totồànn,, ssốố nguyênnguyên ttốố pp vvàà qq ccầầnn phphảảii đđủủ llớớnn,, vvíí ddụụ nhnhưư trêntrên 100100 chchữữ ssốố VVấấnn đđềề đđặặtt rara ởở đđâyây llàà gigiảảii quyquyếếtt bbààii totốánn:: llààmm ththếế nnààoo đđểể kikiểểmm tratra mmộộtt ccááchch nhanhnhanh chchĩĩngng vvàà chchíínhnh xxáácc mmộộtt ssốố nguyênnguyên ddươươngng nn llàà ssốố nguyênnguyên ttốố hayhay hhợợpp ssốố??
27. VVấấnn đềđề ssốố nguyênnguyên ttốố TheoTheo đđịịnhnh nghnghĩĩaa,, mmộộtt ssốố nguyênnguyên ddươươngng nn llàà ssốố nguyênnguyên ttốố khikhi vvàà chchỉỉ khikhi nn chchỉỉ chiachia hhếếtt chocho 11 vvàà nn ((ởở đđâyây chchỉỉ xxéétt ccáácc ssốố nguyênnguyên ddươươngng).). TTừừ đđĩĩ suysuy rara,, nn llàà ssốố nguyênnguyên ttốố khikhi vvàà chchỉỉ khikhi nn khơngkhơng ⎡⎤2, , ⎡ n⎤ ccĩĩ ưướớcc ssốố ddươươngng nnààoo thuthuộộcc đđooạạnn ⎣⎦⎣ ⎦ NhNhưư vvậậyy,, tata ccĩĩ:: nn llàà ssốố nguyênnguyên ttốố ⇔∀in∈⎡⎤2, , ⎡⎤,¬ n≡0 modi ⎣⎦⎣⎦ ()()
28. VVấấnn đềđề ssốố nguyênnguyên ttốố ViViệệcc kikiểểmm tratra mmộộtt ssốố nguyênnguyên ddươươngng nn llàà ssốố nguyênnguyên ttốố theotheo phphươươngng phpháápp trêntrên ssẽẽ đưđưaa rara kkếếtt ququảả hohồànn totồànn chchíínhnh xxáácc TuyTuy nhiênnhiên,, ththờờii giangian xxửử lýlý ccủủaa thuthuậậtt totốánn rõrõ rrààngng llàà rrấấtt llớớnn,, hohoặặcc ththậậmm chchíí khơngkhơng ththểể ththựựcc hihiệệnn đưđượợcc,, trongtrong trtrưườờngng hhợợpp nn ttươươngng đđốốii llớớnn
29. ThuThuậậtt ttốnốn MMiller-Rabiniller-Rabin TrênTrên ththựựcc ttếế,, viviệệcc kikiểểmm tratra mmộộtt ssốố nguyênnguyên ddươươngng nn llàà ssốố nguyênnguyên ttốố ththưườờngng áápp ddụụngng ccáácc phphươươngng phpháápp thuthuộộcc nhnhĩĩmm thuthuậậtt totốánn MonteMonte Carlo,Carlo, vvíí ddụụ:: thuthuậậtt totốánn SolovaySolovay StrassenStrassen hayhay thuthuậậtt totốánn MillerMiller Robin;Robin; thuthuậậtt totốánn MillerMiller RobinRobin ththưườờngng đưđượợcc ssửử ddụụngng phphổổ bibiếếnn hhơơnn
30. ThuThuậậttttoốántnthhuuộộcc nhĩmnhĩm MonteMonte CarloCarlo ThuThuậậtt totốánn thuthuộộcc nhnhĩĩmm MonteMonte CarloCarlo đưđượợcc ssửử ddụụngng trongtrong viviệệcc khkhẳẳngng đđịịnhnh hayhay phphủủ đđịịnhnh mmộộtt vvấấnn đđềề nnààoo đđĩĩ ThuThuậậtt totốánn luơnluơn đưđưaa rara câucâu trtrảả llờờii vvàà câucâu trtrảả llờờii thuthu đưđượợcc chchỉỉ ccĩĩ khkhảả nnăăngng hohoặặcc llàà ““CCĩĩ”” (yes)(yes) hohoặặcc llàà ““KhơngKhơng”” (no)(no) ThuThuậậtt totốánn ““yesyes biasedbiased MonteMonte CarloCarlo”” llàà thuthuậậtt totốánn MonteMonte Carlo,Carlo, trongtrong đđĩĩ,, câucâu trtrảả llờờii ““CCĩĩ”” (Yes)(Yes) luơnluơn chchíínhnh xxáácc nhnhưưngng câucâu trtrảả llờờii ““KhơngKhơng”” (No)(No) ccĩĩ ththểể khơngkhơng chchíínhnh xxáácc
31. ThuThuậậtt ttốnốn MMiller-Rabiniller-Rabin ƯƯuu đđiiểểmm:: XXửử lýlý nhanhnhanh ((ssốố nguyênnguyên ddươươngng nn ccĩĩ ththểể đưđượợcc kikiểểmm tratra trongtrong ththờờii giangian ttỉỉ llệệ vvớớii loglog2nn,, ttứứcc llàà ssốố llưượợngng ccáácc bitbit trongtrong bibiểểuu didiễễnn nhnhịị phânphân ccủủaa nn)) CCĩĩ khkhảả nnăăngng kkếếtt luluậậnn ccủủaa thuthuậậtt totốánn khơngkhơng hohồànn totồànn chchíínhnh xxáácc,, nghnghĩĩaa llàà ccĩĩ khkhảả nnăăngng mmộộtt hhợợpp ssốố nn llạạii đưđượợcc kkếếtt luluậậnn llàà ssốố nguyênnguyên ttốố,, mmặặcc ddùù xxáácc susuấấtt xxảảyy rara kkếếtt luluậậnn khơngkhơng chchíínhnh xxáácc llàà khơngkhơng caocao CCĩĩ ththểể khkhắắcc phphụụcc bbằằngng ccááchch ththựựcc hihiệệnn thuthuậậtt totốánn nhinhiềềuu llầầnn đđểể gigiảảmm khkhảả nnăăngng xxảảyy rara kkếếtt luluậậnn saisai xuxuốốngng ddưướớii ngngưưỡỡngng chocho phphéépp ỴỴ kkếếtt luluậậnn ccĩĩ đđộộ tintin ccậậyy caocao
32. ThuThuậậtt ttốnốn MMiller-Rabiniller-Rabin Phân tích số nguyên dương n = 2km + 1 với m lẻ Chọn ngẫu nhiên số nguyên dương a ∈ {1, 2, , n – 1} Tính b = am mod p if b ≡ 1 (mod p) then Kết luận “p là số nguyên tố” và dừng thuật tốn end if for i = 0 to k − 1 if b ≡ p − 1 (mod p) then Kết luận “p là số nguyên tố” và dừng thuật tốn else b = b2 mod p end if end for Kết luận “p là hợp số”
33. ThuThuậậtt ttốnốn MMiller-Rabiniller-Rabin ThuThuậậtt totốánn MillerMiller RabinRabin llàà thuthuậậtt totốánn ““yesyes biasedbiased MonteMonte CarloCarlo”” đđốốii vvớớii phpháátt bibiếếuu ““ssốố nguyênnguyên ddươươngng nn llàà hhợợpp ssốố”” XXáácc susuấấtt xxảảyy rara kkếếtt luluậậnn saisai,, nghnghĩĩaa llàà thuthuậậtt totốánn đưđưaa rara kkếếtt luluậậnn ““nn llàà ssốố nguyênnguyên ttốố”” khikhi nn ththậậtt ssựự llàà hhợợpp ssốố,, chchỉỉ ttốốii đđaa llàà 25%.25%. NNếếuu áápp ddụụngng thuthuậậtt totốánn kk llầầnn vvớớii ccáácc gigiáá trtrịị aa khkháácc nhaunhau mmàà tata vvẫẫnn thuthu đưđượợcc kkếếtt luluậậnn ““nn llàà ssốố nguyênnguyên ttốố”” ththìì xxáácc susuấấtt chchíínhnh xxáácc ccủủaa kkếếtt luluậậnn nnààyy llàà 11 44-k ỈỈ 11,, vvớớii kk đđủủ llớớnn
34. XXửử lýlý ssốố hhọọcc Tính giá trị của biểu thức z = xb mod n Thuật tốn “bình phương và nhân” Biểu diễn b dạng nhị phân bl-1bl-2 b1b0, bi∈{0, 1}, 0≤ i<l z = 1 x = x mod n for i = l-1 downto 0 z = z2 mod n if bi = 1 then z = z×x mod n end if end for
35. MãMã hĩahĩa đốđốixixứứngng VSVS mãmã hĩahĩa bbấấtt đốđốixixứứngng CCáácc phphươươngng phpháápp mãmã hhĩĩaa quyquy ưướớcc ccĩĩ ưưuu đđiiểểmm xxửử lýlý rrấấtt nhanhnhanh soso vvớớii ccáácc phphươươngng phpháápp mãmã hhĩĩaa khkhĩĩaa cơngcơng ccộộngng DoDo khkhĩĩaa ddùùngng đđểể mãmã hhĩĩaa ccũũngng đưđượợcc ddùùngng đđểể gigiảảii mãmã nênnên ccầầnn phphảảii gigiữữ bbíí mmậậtt nnộộii dungdung ccủủaa khkhĩĩaa vvàà mãmã khkhĩĩaa đưđượợcc ggọọii llàà khkhĩĩaa bbíí mmậậtt (secret(secret key).key). NgayNgay ccảả trongtrong trtrưườờngng hhợợpp khkhĩĩaa đưđượợcc traotrao đđổổii trtrựựcc titiếếpp ththìì mãmã khkhĩĩaa nnààyy vvẫẫnn ccĩĩ khkhảả nnăăngng bbịị phpháátt hihiệệnn VVấấnn đđềề khkhĩĩ khkhăănn đđặặtt rara đđốốii vvớớii ccáácc phphươươngng phpháápp mãmã hhĩĩaa nnààyy chchíínhnh llàà bbààii totốánn traotrao đđổổii mãmã khkhĩĩaa
36. MãMã hĩahĩa đốđốixixứứngng VSVS mãmã hĩahĩa bbấấtt đốđốixixứứngng phí i h C 1K 2K 4K 64 512 128 256 Độ dài mã khóa (bits) Đồ thị so sánh chi phí cơng phá khĩa bí mật và khĩa cơng cộng
37. MãMã hĩahĩa đốđốixixứứngng VSVS mãmã hĩahĩa bbấấtt đốđốixixứứngng KhKhĩĩaa cơngcơng ccộộngng ddễễ bbịị ttấấnn cơngcơng hhơơnn khkhĩĩaa bbíí mmậậtt ĐĐểể ttììmm rara đưđượợcc khkhĩĩaa bbíí mmậậtt,, ngngưườờii gigiảảii mãmã ccầầnn phphảảii ccĩĩ thêmthêm mmộộtt ssốố thơngthơng tintin liênliên quanquan đđếếnn ccáácc đđặặcc ttíínhnh ccủủaa vvăănn bbảảnn ngunguồồnn trtrưướớcc khikhi mãmã hhĩĩaa đđểể ttììmm rara manhmanh mmốốii gigiảảii mãmã thaythay vvìì phphảảii ssửử ddụụngng phphươươngng phpháápp vvéétt ccạạnn mãmã khkhĩĩaa NgoNgồàii rara,, viviệệcc xxáácc đđịịnhnh xemxem thơngthơng đđiiệệpp sausau khikhi gigiảảii mãmã ccĩĩ đđúúngng llàà thơngthơng đđiiệệpp banban đđầầuu trtrưướớcc khikhi mãmã hhĩĩaa hayhay khơngkhơng llạạii llàà mmộộtt vvấấnn đđềề khkhĩĩ khkhăănn ĐĐốốii vvớớii ccáácc khkhĩĩaa cơngcơng ccộộngng,, viviệệcc cơngcơng phpháá hohồànn totồànn ccĩĩ ththểể ththựựcc hihiệệnn đưđượợcc vvớớii đđiiềềuu kikiệệnn ccĩĩ đđủủ ttààii nguyênnguyên vvàà ththờờii giangian xxửử lýlý