Giải thuật mã hóa mật mã RSA

Chöông I: Toång quan A. Môû ñaàu I. Baûo maät : Baûo maät thoâng tin ñaõ söû duïng trong lòch söû thôøi ñaïi La Maõ trong vieäc trao ñoåi thoâng tin vaø nhaø quaân söï chieán löôïc taøi ba Cesar ñaõ söû duïng nhaèm baûo veä thoâng tin, khoâng muoán keû ñòch bieát ñöôïc muïc ñích cuûa mình vaø oâng ñaõ maõ hoùa caùc thoâng baùo cuûa mình vaø chæ nhöõng ngöôøi trong nhoùm cuûa oâng môùi bieát ñöôïc quy taéc maõ hoùa vaø giaûi maõ thoâng baùo ñoù maø ngöôøi khaùc khoâng theå naøo bieát ñöôïc. Ngaøy nay, nhu caàu baûo maät caùc thoâng tin veà kinh teá, quaân söï, ngoaïi giao caøng taêng thì vieäc baûo veä thoâng tin caøng ñöôïc naâng cao. Caùc keânh truyeàn thoâng cuûa nhöõng buoåi ban ñaàu coøn ñôn giaûn, noù ít ñöôïc nhieàu ngöôøi quan taâm, vaø noù ñöôïc truyeàn ñi bôûi “nhöõng ngöôøi ñöa tin” ñöôïc tin caäy toát, thì ngaøy nay ñeå traùnh nhöõng ruûi ro coù theå xaûy ra vaø söï linh hoaït trong vieäc truyeàn ñi nhöõng thoâng baùo ñöôïc an toaøn hôn ngaønh maõ hoùa maät maõ ñöôïc öùng duïng roäng raõi. Theá kyû 20, theá kyû cuûa thôøi ñaïi thoâng tin, ñaõ coù raát nhieàu thay ñoåi, con ngöôøi lieân heä trao ñoåi thoâng tin vôùi nhau thoâng qua maïng toaøn caàu Internet, vaø chính vieäc tham gia naøy ñaõ laøm thay ñoåi raát nhieàu trong vaán ñeà baûo maät. Veà döõ lieäu, chuùng ta caàn quan taâm ñeán nhöõng yeáu toá sau: tính baûo maät, tính toaøn veïn vaø tính kòp thôøi. Caùc heä thoáng maùy tính baûo maät ñöôïc phaân chia theo thôøi gian vaø caùc maïng maùy tính coù quan heä chaët cheõ vôùi vieäc baûo maät caùc keânh truyeàn thoâng vôùi nhau. Ñaëc tính cuûa keânh truyeàn laø moâi tröôøng truyeàn thoâng truy xuaát chung neân vieäc baûo maät veà maët vaät lyù ñöôïc ñeà caäp, do ñoù phaûi thoâng qua öùng duïng cuûa ngaønh baûo maät. Nhieäm vuï chính cuûa baûo maät laø maõ hoaù. Ôû ñaây vieäc maõ hoùa ñöôïc quan taâm ôû möùc ñoä laø chuyeån ñoåi döõ lieäu thaønh maät maõ. Cho ñeán cuoái nhöõng naêm 70 soá hoïc vaãn ñöôïc xem nhö laø moät trong nhöõng ngaønh lyù thuyeát thuaàn tuyù nhaát cuûa toaùn hoïc. Quan nieäm ñoù thay ñoåi khi noù ñöôïc aùp duïng ñeå xaây döïng nhöõng heä maät maõ khoùa coâng khai. Caùc lyù thuyeát môùi cuûa soá hoïc thuaät toaùn ñöôïc öùng duïng vaøo thöïc tieãn. Maät maõ khoâng chæ duøng trong bí maät quaân söï, nhö thôøi kyø cuûa nhaø quaân söï thieân taøi Cesar ñaõ aùp duïng, maø coøn duøng trong ngoaïi giao, kinh teá vaø thöông maïi. Maät maõ hieän ñaïi coù nhöõng ñoøi hoûi môùi mang tính nguyeân taéc hôn so vôùi maät maõ thöôøng duøng tröôùc ñaây. Khaùc vôùi hoaït ñoäng quaân söï hoaëc ngoaïi giao, trong kinh doanh thì soá löôïng caùc ñôn vò phaûi cuøng trao ñoåi nhöõng thoâng tin maät raát lôùn. Nhöõng heä thoáng maät maõ cuõ khi bieát ñöôïc khoaù laäp maõ cuûa hoï ta deã daøng tìm ra khoaù giaûi maõ. Hieån nhieân muoán göûi moät thoâng baùo maät cho moät ñoái töôïng naøo ñoù ta caàn phaûi bieát khoùa laäp maõ cuûa hoï, vì vaäy nhöõng ngöôøi cuøng moät heä maõ ñeàu bieát bí maät cuûa nhau. Nhieàu ngöôøi cuøng söû duïng moät heä maõ thì khoâng coøn laø bí maät nöõa. Caùc heä thoáng maät maõ hieän ñaïi töùc laø caùc heä maät maõ khoùa coâng khai ñaõ khaéc phuïc ñöôïc nhöõng nhöôïc ñieåm ñoù: ngöôøi tham gia trong heä thoáng chæ caàn giöõ bí maät khoùa giaûi maõ rieâng cuûa mình trong khi khoùa laäp maõ ñöôïc thoâng baùo coâng khai. Vieäc bieát khoùa laäp maõ khoâng cho pheùp tìm ra khoùa giaûi maõ trong moät thôøi gian chaáp nhaän ñöôïc, ngay caû khi söû duïng caû maùy tính hieän ñaïi vôùi haøng tæ pheùp tính trong moät giaây. II. Nhieäm vuï: Nhieäm vuï cuûa ñeà taøi naøy laø nghieân cöùu veà giaûi thuaät maõ hoaù maät maõ RSA , xaây döïng moät chöông trình duøng giaûi thuaät RSA ñeå maõ hoaù vaø giaûi maõ moät taäp tin.txt. Chöông trình naøy chæ giôùi haïn söû duïng treân maùy ñôn. III. Boá cuïc: Chöông 1 : Toång quan. Chöông 2 : Tìm hieåu veà RSA. Chöông 3 : Giao dieän cuûa chöông trình. Chöông 4 : Keát luaän. B. Tìm hieåu maät maõ. 1. Maät maõ: Maät maõ laø ngheä thuaät cuûa chöõ vieát bí maät ñöôïc xuaát phaùt töø chöõ vieát cuûa caùc töø Hy Laïp. Caùi chính laø maät maõ coù khaû naêng göûi thoâng tin giöõa hai ngöôøi vôùi nhau vaø ngaên chaën nhöõng ngöôøi khaùc can thieäp vaøo. Maät maõ ñöôïc duøng ñeå baûo veä bí maät thoâng tin khi thoâng tin ñöôïc truyeàn ñi. Moät vaên baûn ñöôïc maõ hoùa ñöôïc bieåu thò baèng M hay laø P. Noù coù theå laø moät chuoãi caùc bít, moät taäp tin vaên baûn, moät aûnh, moät chuoãi soá hoùa aâm thanh, moät hình aûnh phim kyõ thuaät soá… vaø hôn theá nöõa. Trong chöøng möïc cuûa moät maùy tính coù lieân quan ñeán, M laø döõ lieäu nhò phaân ñôn giaûn. Vaên baûn ñöôïc maõ hoùa coù muïc ñích laø truyeàn ñi hay löu tröõ. Trong tình huoáng naøy, M laø thoâng baùo phaûi ñöôïc maõ hoùa. Vaên baûn ñaõ ñöôïc maõ hoùa ñöôïc bieåu thò baèng C. Noù cuõng laø döõ lieäu nhò phaân: ñoâi khi cuøng kích thöôùc vôùi M, vaø cuõng coù luùc lôùn hôn raát nhieàu. E ñöôïc bieåu thò cho coâng vieäc maõ hoùa vaø D duøng ñeå theå hieän vieäc giaûi maõ caùc thoâng baùo ñaõ ñöôïc maõ hoùa göûi ñeán. Ta coù: E (M) = C D (C) = M D (E(M)) =M Maät maõ hieän ñaïi giaûi quyeát vaán ñeà vôùi moät khoùa, khoùa naøy ñöôïc bieåu thò baèng K. Khoùa naøy coù theå laø moät trong nhöõng con soá lôùn coù giaù trò lôùn. Ta coù: EK (M) = C DK (C) = M DK (EK(M)) = M Quaù trình maõ hoùa vaø giaûi maõ duøng chung moät khoùa: Quaù trình maõ hoùa vaø giaûi maõ söû duïng hai khoùa khaùc nhau: Ví duï, moät ngöôøi muoán maõ hoùa nhöõng taäp tin treân oå cöùng ñeå ngaên chaën nhöõng keû xaâm nhaäp vaøo coù theå ñoïc ñöôïc döõ lieäu. Trong moät heä thoáng nhieàu ngöôøi söû duïng, vieäc maõ hoùa döõ lieäu cho pheùp baûo maät thoâng tin treân moät keânh truyeàn khoâng an toaøn. Trong moät ngöõ caûnh thoâng thöôøng: Lan muoán göûi moät thoâng baùo cho Nam nhöng khoâng muoán moät ai khaùc ngoaøi Nam coù theå ñoïc ñöôïc noù. Lan maõ hoùa döõ lieäu vôùi moät khoùa maõ hoùa, thoâng baùo ñaõ maõ hoùa ñaõ maõ hoùa göûi ñi cho Nam. Nam giaûi maõ thoâng baùo ñaõ maõ hoùa ñoù vôùi moät khoùa giaûi maõ vaø ñoïc ñöôïc noù. Moät ngöôøi coá laáy cho baèng ñöôïc khoùa giaûi maõ hoaëc coá tình chuyeån laïi tình traïng cuõ maø khoâng caàn phaûi coù khoùa baûo maät. Trong moät heä thoáng maõ hoùa an toaøn, thoâng tin ñaõ maõ hoùa khoâng theå chuyeån ñoåi laïi thaønh thoâng tin ban ñaàu maø khoâng coù khoùa giaûi maõ. Heä thoáng maät maõ ñoái xöùng chæ coù moät khoùa duy nhaát vöøa laø khoùa maõ hoùa vöøa laø khoùa giaûi maõ. 2. Giao thöùc maät maõ a. Giôùi thieäu veà giao thöùc: Maät maõ giaûi quyeát nhöõng vaán ñeà bao goàm tính baûo maät, tính xaùc thöïc, tính toaøn veïn. Baïn coù theå hoïc taát caû veà thuaät toaùn vaø kyõ thuaät maõ hoùa, nhöng ñoù laø nhöõng lyù thuyeát suoâng neáu baïn khoâng theå giaûi quyeát vaán ñeà. Ñoù lyù do chuùng ta quan taâm ñeán caùc giao thöùc soá nguyeân toá. Moät giao thöùc laø moät chuoãi caùc böôùc bao goàm hai hay nhieàu phaàn ñöôïc thieát keá ñeå thöïc hieän moät taùc vuï. Moät “chuoãi caùc böôùc “coù nghóa laø giao thöùc coù tính lieân tuïc, töø luùc baét ñaàu ñeán luùc keát thuùc. Moãi böôùc phaûi ñöôïc thöïc thi laàn löôït vaø böôùc sau khoâng theå thöïc thi khi böôùc tröôùc chöa thöïc thi xong. Giao thöùc maät maõ laø moät giao thöùc söû duïng maät maõ. Giao thöùc maät maõ bao goàm vaøi giaûi thuaät maät maõ nhöng nhìn chung muïc ñích cuûa giao thöùc ñôn giaûn chæ laø baûo maät. Baây giôø chuùng ta haõy xem xeùt ñeán moät giao thöùc ñöôïc öùng duïng trong maïng maùy tính ARPA ñeå xaây döïng moät keânh truyeàn daãn aûo ñöôïc baûo maät. Chuùng ta choïn lôùp maïng cuûa moâ hình tham chieáu maïng heä môû baûy taàng (OSI). Hình 1. Moâ hình tham chieáu maïng heä môû. Sô ñoà toång quaùt cho vieäc trao ñoåi thoâng tin cuûa giao thöùc naøy ñöôïc moâ taû theo hình ôû sau. Hình 2: Chuyeån ñoåi thoâng tin giöõa hai ngöôøi söû duïng laø A vaø B. Ngöôøi söû duïng chöông trình A duøng chöông trình maõ hoaù, thoâng qua heä ñieàu haønh ñeán maïng truyeàn thoâng. Thoâng qua giao dieän naøy, chöông trình qua heä ñieàu haønh cuûa ngöôøi söû duïng chöông trình B vaø ngöôøi B söû duïng chöông trình maõ hoaù ñeå cho ra thoâng ñieäp maø ngöôøi A göûi ñeán. b. Truyeàn thoâng söû duïng giao thöùc maõ hoùa ñoái xöùng. Maõ ñoái xöùng laø heä maät maõ söû duïng cuøng moät khoùa cho caû vieäc maõ hoaù cuõng nhö giaûi maõ moät thoâng ñieäp. Nhöõng heä thoáng maõ hoaù ñoái xöùng coù nhöõng vaán ñeà cho pheùp sau: Khoùa phaûi ñöôïc phaân boå moät caùch bí maät. Chuùng coù giaù trò cho taát caû caùc thoâng ñieäp ñöôïc maõ hoaù, bieát khoùa coù theå bieát heát taát caû caùc thoâng ñieäp. Neáu khoùa bò laáy caép thì ngöôøi thöù ba coù theå giaûi maõ ñöôïc caùc thoâng ñieäp ñaõ ñöôïc maõ hoùa vôùi moät khoùa. Ngöôøi naøy coù theå nguî taïo moät phaàn vaø taïo ra nhöõng thoâng ñieäp bò loãi ñeå löøa nhöõng ngöôøi khaùc. Moät khoùa bí maät ñöôïc söû duïng cho moät caëp ngöôøi tham gia treân moät maïng, toång soá nhöõng con soá caùc khoùa taêng moät caùch nhanh choùng khi soá löôïng ngöôøi söû duïng taêng leân. Moät maïng cuûa n ngöôøi söû duïng yeâu caàu n(n-1)/2 khoùa. Ví duï, vôùi 10 ngöôøi söû duïng yeâu caàu 45 khoùa khaùc nhau ñeå noùi chuyeän vôùi ngöôøi khaùc vaø 100 ngöôøi söû duïng caàn 4950 khoùa. Giaûi thuaät ñoái xöùng gioáng nhö moät keùt saét. Khoaù laø chìa khoaù duy nhaát ñeå môû keùt saét ñoù. Moät ngöôøi vôùi moät söï phoái hôïp coù theå môû keùt saét vaø ñöa döõ lieäu ra ngoaøi. Neáu coù khoaù naøy, baïn coù theå môû keùt saét ñeå ñöa döõ lieäu vaøo vaø khoaù keùt laïi. c. Haøm moät chieàu. Haøm moät chieàu laø haøm troïng taâm trong heä maät maõ duøng khoùa coâng khai. Haøm moät chieàu laø moät haøm cô baûn cho haàu heát nhöõng giao thöùc. Haøm cöûa baãy moät chieàu laø haøm moät chieàu ñaëc bieät, ñoùù laø moät cöûa baãy bí maät. Haøm naøy deã daøng tính toaùn theo moät höôùng nhaát ñònh vaø raát khoù khaên khi tính toaùn theo moät höôùng khaùc. Nhöng neáu baïn bieát bí maät thì baïn coù theå tính toaùn caùc haøm theo höôùng khaùc ñoù. d. Haøm aùnh xaï. Haøm aùnh xaï coù nhieàu teân: haøm giaûm, haøm thu goïn… Haøm naøy laø troïng taâm cuûa maät maõ hieän ñaïi. Haøm aùnh xaï laø moät haøm cô baûn cho nhieàu giao thöùc. Haøm aùnh xaï ñöôïc söû duïng trong ngaønh khoa hoïc maùy tính trong moät thôøi gian daøi. Haøm aùnh xaï laøm vieäc theo moät chieàu, deã daøng tính toaùn moät giaù trò baêm töø moät hình aûnh tröùôc ñoù. Maõ xaùc nhaän thoâng tin (MAC), coøn goïi laø maõ xaùc nhaän döõ lieäu, laø moät haøm aùnh xaï keøm theo moät khoùa bí maät. Baïn coù theå taïo ra moät MAC ngoaøi moät haøm aùnh xaï hay moät thuaät giaûi maõ hoùa. e. Truyeàn thoâng söû duïng nghi thöùc maõ khoùa coâng khai Heä maõ khoùa coâng khai hay coøn goïi laø heä maõ baát ñoái xöùng. Maõ baát ñoái xöùng laø heä maät maõ söû duïng moät caëp khoùa trong ñoù moät khoùa ñöôïc coâng boá roäng raõi goïi laø khoaù coâng khai vaø moät khoùa ñöôïc löu giöõ bí maät goïi laø khoùa rieâng. Caëp khoùa naøy duøng ñeå maõ hoaù cuõng nhö giaûi maõ döõ lieäu, trong ñoù khoùa coâng khai seõ duøng ñeå maõ hoùa vaø khoùa bí maät duøng ñeå giaûi maõ döõ lieäu ñaõ ñöôïc maõ hoùa. Trong maïng coù nhieàu ngöôøi söû duïng, heä maõ hoaù khoùa coâng khai môùi laø giaûi phaùp baûo maät toái öu. Ngöôøi söû duïng sôû höõu moät khoùa coâng khai vaø moät khoùa bí maät. Khoùa coâng khai ñoù ñöôïc phoå bieán trong cô sôû döõ lieäu ôû moät soá nôi. Treân thöïc teá, giaûi thuaät khoùa coâng khai khoâng phaûi laø söï thay theá cho giaûi thuaät ñoái xöùng. Chuùng khoâng ñöôïc söû duïng ñeå maõ hoùa thoâng tin, chuùng ñöôïc söû duïng ñeå maõ hoùa nhöõng khoùa chaúng haïn nhö khoaù DES. Giaûi thuaät khoùa coâng khai thöôøng chaäm. Nhöõng giaûi thuaät maõ hoùa ñoái xöùng noùi chung nhanh hôn raát nhieàu laàn laàn so vôùi giaûi thuaät maõ hoùa khoùa coâng khai. Vôùi nhöõng maùy tính coù boä xöû lyù cao vaø trong voøng nhöõng naêm tôùi coù theå duøng giaûi thuaät maät maõ khoùa coâng khai ñeå maõ hoaù vaø giaûi maõ döõ lieäu vôùi toác ñoä coù theå so saùnh vôùi maät maõ ñoái xöùng ngaøy nay. Vôùi baêng thoâng taêng leân vaø ñoù laø ñieàu caàn thieát ñeå maõ hoùa döõ lieäu nhanh hôn maät maõ khoùa coâng khai coù theå quaûn lyù. 3. Caùc cheá ñoä maät maõ. Giaûi thuaät maät maõ khoái maõ hoaù döõ lieäu theo nhöõng khoái. Kích thöôùc khoái thoâng duïng nhaát laø 8 byte. Maät maõ khoái baûo maät cao hôn maät maõ doøng, tuy nhieân nhöõng giaûi thuaät maät maõ khoái thöïc thi chaäm hôn nhöõng maät maõ khaùc. Nhöõng maät maõ khoái söû duïng cuøng moät giaûi thuaät maõ hoaù cho moãi khoái. Do ñoù, moät khoái vaên baûn thöôøng traû veà cuøng moät vaên baûn maät maõ khi maõ hoaù vôùi cuøng moät khoaù vaø moät giaûi thuaät. CBC ( Cipher Block Chaining mode): cheá ñoä maéc xích nhöõng khoái maõ hoùa. Cheá ñoä CBC giôùi thieäu veà thoâng tin phaûn hoài. Tröôùc khi moãi khoái vaên baûn thöôøng ñöôïc maõ hoaù, noù keát hôïp vôùi vaên baûn maät maõ cuûa khoái tröôùc baèng moät thao taùc OR ñoái vôùi töøng bít. Ñieàu naøy ñaûm baûo raèng ngay caû khi coù nhieàu khoái vaên baûn thöôøng gioáng nhau thì moãi khoái ñoù seõ ñöôïc maõ hoaù sang nhöõng khoái vaên baûn maät maõ khaùc nhau. Khôûi taïo ñöôïc keát hôïp vôùi khoái vaên baûn thöôøng soá nguyeân toá baèng thao taùc OR cho töøng bít tröôùc khi khoái ñöôïc maõ hoaù. Neáu coù moät bít ñôn cuûa khoái vaên baûn thöôøng bò hö, khoái vaên baûn thöôøng töông öùng cuõng seõ bò hö. Theâm vaøo ñoù, moät bít trong khoái theo sau, ôû cuøng moät vò trí nhö bít hö soá nguyeân toá seõ bò hö. Hình 3: Cheá ñoä maéc xích nhöõng khoái maõ hoùa. CFB (Cipher Feedback mode ): cheá ñoä phaûn hoài maät maõ. Cheá ñoä CFB naøy söû duïng moät thanh ghi dòch töøng khoái nhoû trong vaên baûn vaø ñöôïc chia thaønh nhieàu phaàn, khoâng xöû lyù nguyeân moät khoái lôùn. Ví duï, neáu kích thöôùc cuûa khoái laø 8 byte, vôùi 1 byte xöû lyù vaøo luùc ñaàu, thanh ghi dòch ñöôïc chia thaønh 8 phaàn vaø cheá ñoä naøy xöû lyù 8 phaàn. Neáu moät bít trong vaên baûn maät bò hö thì moät bít trong vaên baûn thöôøng cuõng bò hö vaø thanh ghi dòch bò sai laïc. Ñieàu naøy laøm cho nhieàu söï gia taêng cuûa vaên baûn thöôøng bò hö cho ñeán khi bít hö bò dòch ra khoûi thanh ghi dòch. CTS (Cipher Text Stealing mode) cheá ñoä sao cheùp nguyeân vaên maät maõ. Cheá ñoä CTS söû duïng moät chieàu daøi baát kyø cuûa vaên baûn thöôøng vaø taïo ra vaên baûn maät maõ coù chieàu daøi vôùi chieàu daøi cuûa vaên baûn tónh. Cheá ñoä naøy thöïc thi cuõng gioáng nhö cheá ñoä CBC nhöng khaùc vôùi hai khoái cuoái cuøng cuûa vaên baûn thöôøng. ECB ( Electronic Codebook mode): cheá ñoä caùc kyù hieäu ñieän töû Cheá ñoä ECB maõ hoaù moãi khoái moät caùch rieâng leû. Nghóa laø nhöõng khoái vaên baûn thöôøng baát kyø gioáng nhau vaø naèm trong cuøng moät thoâng baùo hoaëc naèm trong moät thoâng baùo khaùc ñöôïc maõ hoaù vôùi cuøng moät khoaù seõ bò bieán ñoåi thaønh nhöõng khoái vaên baûn maät maõ gioáng nhau. Hình 4: Quaù trình di chuyeån cuûa caùc kyù hieäu ñieän töû. Hình 5: Moâ hình maõ hoùa baèng caùc kyù hieäu ñieän töû. Neáu vaên baûn thöôøng ñöôïc maõ hoaù baûn sao quan troïng, noù seõ laøm cho vaên baûn maät maõ bò phaù vôõ moãi luùc moät khoái. Vaø keû ñòch coù theå thay ñoåi hoaëc trao ñoåi nhöõng khoái rieâng maø khoâng caàn phaûi doø tìm. Neáu 1 bít trong khoái vaên baûn maät maõ bò hö, toaøn boä khoái vaên baûn tónh töông öùng cuõng seõ bò hö. OFB ( Output Feedback mode): cheá ñoä phaûn hoài ñaàu ra. Cheá ñoä OFB töông töï nhö cheá ñoä CFB, söï khaùc bieät duy nhaát giöõa hai cheá ñoä naøy laø caùch maø thanh ghi dòch ñöôïc ñöa vaøo. Neáu moät bít trong vaên baûn maät maõ bò hö, bít töông ñöông cuûa vaên baûn thöôøng cuõng seõ bò hö. Tuy nhieân, neáu coù theâm hoaëc maát nhöõng bít töø vaên baûn maät maõ, vaên baûn thöôøng chæ bò hö töø vò trí ñoù. 4. Moät soá giaûi thuaät maät maõ: 4.1. Moät soá khaùi nieäm trong thuaät toaùn soá hoïc: 4.1.1. Soá nguyeân toá : Ñònh nghóa : Soá nguyeân toá laø soá nguyeân lôùn hôn 1, khoâng chia heát cho soá nguyeân döông naøo ngoaøi 1 vaø chính noù. Soá nguyeân lôùn hôn moät khoâng phaûi laø soá nguyeân toá ñöôïc goïi laø hôïp soá. b. Caùc tính chaát: - Moïi hôïp soá n ñeàu coù öôùc nguyeân toá nhoû hôn caên baäc 2 cuûa n. Thaät vaäy, vì n laø moät taäp hôïp soá neân ta coù theå vieát n = a b, trong ñoù a vaø b laø caùc soá nguyeân vôùi 1 < a ≤ b < n. Roõ raøng ta phaûi coù a hoaëc b khoâng vöôït quaù caên baäc hai cuûa n. - Moïi soá nguyeân lôùn hôn moät ñeàu phaân tích ñöôïc moät caùch duy nhaát thaønh tích caùc soá nguyeân toá, trong ñoù caùc thöøa soá ñöôïc vieát vôùi thöù töï khoâng giaûm. Phi haøm Euler : Caùc ñònh nghóa: - Phi – haøm Euler þ( n ) laø haøm soá hoïc coù giaù trò taïi n baèng soá caùc soá khoâng vöôït quaù n vaø nguyeân toá cuøng nhau vôùi n. Ví duï : þ( 1 ) = 1, þ( 2 ) = 1, þ( 3 ) = 2, þ( 4 ) = 2, þ( 5 ) = 4, … Töø ñònh nghóa ta coù heä quaû : Soá p laø soá nguyeân toá khi vaø chæ khi þ( p ) = p – 1. - Heä thaëng dö thu goïn modulo n laø taäp hôïp þ( n ) soá nguyeân sao cho moãi phaàn töû cuûa taäp hôïp nguyeân toá cuøng nhau vôùi n vaø khoâng coù hai phaàn töû naøo ñoàng dö vôùi nhau modulo n. Noùi caùch khaùc, trong heä thaëng dö ñaày ñuû modulo n, ta chæ giöõ laïi nhöõng giaù trò naøo nguyeân toá cuøng nhau vôùi n. Ví duï : Caùc soá 1, 2, 3, 4, 5, 6 laäp thaønh heä thaëng dö thu goïn modulo 7. Ñoái vôùi modulo, coù theå laáy taäp hôïp 1, 3, 5, 7. b. Caùc tính chaát: - Neáu r1, r2, r3, …, rþ(n) laø moät heä thaëng dö thu goïn modulo n vaø a laø soá nguyeân döông, ( a, n ) = 1 thì taäp hôïp a r1, a r2, a rþ(n) cuõng laø heä thaëng dö thu goïn modulo n. - Neáu m laø soá nguyeân döông vaø a nguyeân toá cuøng nhau vôùi m thì aþ(m) = 1 ( mod m ). - Giaû söû n = p1a1p2a2…pkak laø phaân tích cuûa n thaønh thöøa soá nguyeân toá. Khi ñoù ta coù : þ( n ) = n ( 1 – 1/ p1)( 1 – 1/p2) … ( n – 1/ pk ) Ñònh lyù Fermat: Neáu p laø soá nguyeân toá thì ap-1 1 (mod p) vôùi taát caû a Zp. 4.1.4. Ñònh lyù ñeä quy öôùc soá chung lôùn nhaát ( GCD): Vôùi baát kyø moät soá nguyeân khoâng aâm a vaø baát kyø soá nguyeân döông b thì Gcd (a, b)= gcd (b, a mod b) Moät soá thuaät giaûi söû duïng trong maõ hoaù. Söï phaùt trieån cuûa xaõ hoäi ngaøy nay maät maõ khoâng chæ duøng trong bí maät quaân söï nhö thôøi kyø cuûa nhaø quaân söï thieân taøi Cesar ñaõ aùp duïng maø coøn duøng trong ngoaïi giao, kinh teá vaø thöông maïi. Ngöôøi ta chia caùc heä maõ thaønh hai loaïi chính laø heä maõ coå ñieån vaø heä maõ hieän ñaïi. Vôùi nhöõng heä thoáng maät maõ cuõ khi bieát ñöôïc khoaù laäp maõ cuûa hoï ta deã daøng tìm ra khoaù giaûi maõ, hieån nhieân muoán göûi moät thoâng baùo maät cho moät ñoái töôïng naøo ñoù ta caàn phaûi bieát khoùa laäp maõ cuûa hoï, vì vaäy nhöõng ngöôøi cuøng moät heä maõ ñeàu bieát bí maät cuûa nhau daãn ñeán khoâng coøn laø bí maät nöõa. Caùc heä thoáng maät maõ hieän ñaïi töùc laø maät maõ khoùa coâng khai ñaõ khaéc phuïc ñöôïc nhöõng nhöôïc ñieåm ñoù: ngöôøi tham gia trong heä thoáng chæ caàn giöõ bí maät khoùa giaûi maõ rieâng cuûa mình trong khi khoùa laäp maõ ñöôïc thoâng baùo coâng khai. Vieäc bieát khoùa laäp maõ khoâng cho pheùp tìm ra khoùa giaûi maõ trong moät thôøi gian chaáp nhaän ñöôïc ngay caû khi söû duïng caû maùy tính hieän ñaïi. Nhöõng maät maõ khoùa coâng khai soá nguyeân toá tìm thaáy laø nhöõng maät maõ duøng ñeán caùc haøm soá hoïc. Maõ Ceasar. Maät maõ Cesar laø maät maõ maø moãi kyù töï thöù i trong baûng chöõ caùi ñöôïc dòch tôùi kyù töï thöù (i+j). Ta coù qui trình maät maõ nhö sau : Maõ hoùa : E : i ® i+j Giaûi maõ : D : i ® i-j Maõ Cesar chuyeån caùc thoâng baùo maät baèng caùch sau ñaây: Laäp baûng töông öùng moãi chöõ caùi moät soá. Nhôø baûng töông öùng ñoù ta coù theå chuyeån moät vaên baûn daïng chöõ soá. Sau ñoù ta coäng theâm k vaøo moãi chöõ soá nhaän ñöôïc, laïi nhôø vaøo baûng töông öùng giöõa chöõ vaø soá ta bieán ñoåi baûng chöõ soá môùi naøy thaønh daïng chöõ vieát. Ta ñaõ nhaän ñöôïc moät vaên baûn maät caàn chuyeån ñi. Ñaây chính laø quaù trình maõ hoùa. Sau khi nhaän ñöôïc vaên baûn maät ta giaûi maõ baèng caùch chuyeån caùc chöõ thaønh soá nhôø vaøo baûng töông öùng chöõ vaø soá, sau ñoù ta tröø ñi k ôû moãi chöõ soá vaø laïi chuyeån noù veà daïng chöõ ñeå coù laïi vaên baûn ban ñaàu. Quaù trình treân laø quaù trình giaûi maõ. Chuù yù: Khi pheùp coäng hoaëc tröø ñöa ta vöôït qua khoûi giôùi haïn cuûa baûng töông öùng ta thay soá ñoù baèng thaëng dö döông beù nhaát modulo soá vaø chöõ. Ví duï: Ta laäp baûng töông öùng caùc chöõ caùi theo baûng: ( ÔÛ ñaây ta xeùt theo kieåu chöõ cuûa Vieät Nam neân xuaát hieän caùc chöõ coù daáu, coøn neáu khi ta chuyeån maõ treân maïng thì ta seõ ñöa ra theo chuaån cuûa quoác teá.) A AÊ AÂ B C D Ñ E EÂ G 1 2 3 4 5 6 7 8 9 10 H I K L M N O OÂ Ô P 11 12 13 14 15 16 17 18 19 20 Q R S T U Ö V X Y 21 22 23 24 25 26 27 28 29 Soá nguyeân toá ta laäp baûng töông öùng, töø ñoù ta chuyeån vaên baûn sang daïng chöõ soá. Sau ñoù ta coäng theâm 3 vaøo moãi chöõ soá nhaän ñöôïc. Vaø thoâng qua baûng töông öùng chöõ vaø soá ta laïi ñöa ra daïng chöõ vieát. Ta nhaän ñöôïc moät vaên baûn maät caàn phaûi maõ hoùa. Ñoù laø quaù trình maõ hoùa. Khi nhaän ñöôïc vaên baûn maät ta giaûi maõ baèng caùch bieán noù thaønh daïng chöõ soá vaø döïa vaøo baûng töông öùng vaø sau ñoù ta tröø ñi 3. Chaúng haïn vaên baûn caàn göûi ñi laø: MOI BAN DI CHOI. Ta seõ chuyeån caâu treân sang daïng chöõ soá döïa vaøo baûng töông öùng beân treân: 15 17 12 4 1 16 7 12 5 11 17 12 (1) Ta laäp theo coâng thöùc sau: C P + 3(mod 29) (*) ( P laø vaên baûn, C laø chöõ soá töông öùng trong vaên baûn maät ) Ta coäng theâm 3 vaøo (1): 18 20 15 7 4 19 10 15 8 14 20 15 Chuyeån trôû laïi daïng chöõ ta ñöôïc vaên baûn nhö sau: OÂPMÑBÔGMELPM à vaên baûn maät ñöôïc maõ hoùa. Theo (*) thì 3 laø khoùa cuûa Cesar Coâng thöùc toång quaùt laø: C P + k(mod 29) k laø soá tuøy yù giöõa 1-29. 4.2.2. Maõ khoái. Khaùc vôùi heä maõ Cesar, ôû ñaây khoâng maõ hoùa töøng chöõ maø ta maõ hoùa caùc khoái chöõ caùi. Vieäc söû duïng maõ khoái ñaõ naâng cao raát nhieàu tính baûo maät nhöng khoùa cuûa maõ vaãn coù theå bò doø ra do vieäc nghieân cöùu taàn soá xuaát hieän cuûa caùc khoái chöõ caùi. Maõ khoái xuaát hieän nhaèm choáng laïi vieäc söû duïng taàn suaát cuûa caùc chöõ caùi trong vaên baûn ñeå doø ra khoùa giaûi maõ. Chuaån maät maõ maõ hoùa döõ lieäu DES ( Data Encryption Standard) Maõ hoaù döõ lieäu chuaån DES söû duïng caëp khoùa ñoái xöùng, maõ hoùa döõ lieäu theo töøng khoái. Khoùa ñoái xöùng: Vieäc baûo maät trong moät heä thoáng maät maõ coù hai vaán ñeà maø ta caàn quan taâm. Ñoù laø chieàu daøi cuûa giaûi thuaät vaø chieàu daøi khoaù. Nhöng neáu coù ñöôïc thì ñoái vôùi ngöoøi giaûi maõ khoâng coøn caùch naøo khaùc toát hôn ñeå phaù vôõ heä thoáng maät maõ laø thöû laàn löôït töøng khoaù baèng phöông phaùp taán coâng “söùc maïnh taøn baïo”, ñaây laø phöông phaùp giaûi quyeát moät baøi toaùn khoù baèng caùch laëp ñi laëp laïi nhieàu laàn moät thuû tuïc ñôn giaûn Chuaån naøy ñöôïc ñöa ra vaøo naêm 1977, ñöôïc söû duïng trong caùc öùng duïng treân ñaát nöôùc Myõ, vaø chuaån naâng cao hôn cuûa chuaån naøy laø DAE. Moät soá chính phuû cuûa moät soá nöôùc mong muoán ñöôïc söû duïng chuaån DEA naøy cho ñaát nöôùc mình vaøo caùc maïng ngaân haøng vaø thöông maïi taàm côõ quoác teá. Diffie vaø Hellman ñaõ döï ñoaùn chuaån DEA naøy seõ bò taán coâng bôûi nhöõng tin taëc hay moät maùy chuyeân duïng vôùi moät trieäu con chip trò giaù khoaûng 20 trieäu dollar, vaø maùy coù theå tìm ra maõ maät maõ baát kyø baèng caùch tìm heát khoâng gian khoùa trong moät ngaøy. Vaø vôùi toác ñoä ngaøy nay thì vieäc phaùt trieån ngaøy caøng cao cuûa coâng ngheä phaàn cöùng thì vieäc tìm ra khoùa khoâng coøn laø vaán ñeà nöõa. DES maõ hoùa caùc khoái döõ lieäu 64 bít vôùi khoùa 56 bít. Maõ hoaù duøng caëp khoùa ñoái xöùng theo töøng khoái. Hình 6: Maõ hoùa döõ lieäu vôùi caëp khoùa baûo maät ñoái xöùng. DES thöïc thi hieäu quaû trong phaàn cöùng nhöng trong phaàn meàm thì DES thöïc thi khoâng hieäu quaû laém. Maëc duø khoù thöïc hieän nhöõng coâng vieäc thöïc thi phaàn meàm, ngöôøi ta vaãn khaúng ñònh raèng DES ñöôïc thieát keá chuyeân bieät cho coâng vieäc naøy coù theå vì giôùi haïn vieäc söû duïng DES ñeå caùc toå chöùc coù theå coù ñuû nhöõng ñieàu kieän döïa treân phaàn cöùng hoaëc cuõng coù theå DES deã daøng ñieàu khieån tieáp can ñeán kyõ thuaät. Nhöõng tieán boä trong vieäc taïo ra caùc CPU laøm cho noù coù theå thöïc hieän DES trong phaàn meàm. Nhöõng tieán boä trong vieäc taêng toác ñoä chip vaø vieäc caùc khoùa DES bò phaù huyû baèng moät bít thoâng minh vaø söï tra cöùu toaøn dieän. Hieän nay ñaõ coù DES vôùi chieàu daøi khoùa leân ñeán 128 bít ñeå taêng theâm tính baûo maät trong thôøi ñaïi buøng noå cuûa coâng ngheä ngaøy caøng nhanh. 4.2.3. Maõ muõ. Heä maõ naøy ñöôïc Pohlig vaø Hellman ñöa ra naêm 1978. Giaû söû p laø moät soá nguyeân toá leû vaø khoaù laäp maõ e laø moät soá nguyeân döông sao cho (e, p-1)=1. Sau ñoù ta nhoùm thaønh töøng nhoùm 2m chöõ soá theo nguyeân taéc sau: 2m laø soá nguyeân chaún lôùn nhaát sao cho moïi soá töông öùng vôùi m chöõ caùi ñeàu nhoû hôn p. Moãi chöõ ñöôïc bieåu dieãn khoâng quaù 29. Moät soá coù m chöõ caùi seõ ñöôïc bieåu dieãn khoâng quaù m laàn soá 29 vieát lieân tieáp nhau. Laäp khoái chöõ töông öùng trong vaên baûn maät theo coâng thöùc sau: C Pe (mod p), 0 P< p Vaên baûn maät seõ chöùa nhöõng khoái chöõ soá caùc soá nguyeân nhoû hôn p. Ñeå giaûi maõ moät khoái C trong vaên baûn maät ta caàn bieát khoùa giaûi maõ d. Ñoù laø soá d thoûa maõn de=1(mod p -1) coù nghóa laø nghòch ñaûo cuûa e modulo p-1. Nghòch ñaûo ñoù toàn taïi do giaû thuyeát (e, p-1)=1. ñeå tìm laïi ñöôïc khoái P trong vaên baûn ta naâng khoái C leân luyõ thöøa d modulo p. Ta coù: Cd (Pe)d PdePk(p-1) +1 P(mod p) Trong ñoù: de=k(p-1) +1 ñoái vôùi soá nguyeân k naøo ñoù. Ñoä phöùc taïp cuûa thuaät toaùn laäp maõ vaø giaûi maõ ñoái vôùi maõ muõ. Vôùi moät khoái P trong vaên baûn, maõ hoùa baèng caùch tính Pe (mod p), caùc pheùp tính bít caàn thieát laø O((log2p)3). Ta tìm nghòch ñaûo d cuûa e modulo p-1. Sau ñoù ta tính thaëng dö nguyeân döông beù nhaát cuûa Cd modulo p: soá pheùp tính ñoøi hoûi laø O((log2p)3). Ñeå giaûi maõ moät vaên baûn ñöôïc maõ hoùa baèng maõ muõ khoâng theå tính ñöôïc neáu khoâng bieát khoùa e. Maõ muõ vaø heä thoáng coù nhieàu ñoái töôïng tham gia. Öu ñieåm cuûa heä maõ muõ laø trong heä thoáng coù nhieàu ñoái töôïng tham gia trao ñoåi thoâng tin töøng caëp ñoái töôïng hoaëc töøng nhoùm coù khaû naêng söû duïng khoùa maät maõ ñang duøng ñeå taïo ra nhöõng khoaù maät maõ chung, bí maät vôùi caùc ñoái töôïng coøn laïi. Giaû söû p laø moät soá nguyeân toá lôùn vaø a laø soá nguyeân cuøng nhau vôùi p. Moãi ñoái töôïng trong heä thoáng choïn moät soá k nguyeân toá cuøng nhau vôùi p-1 ñeå laøm khoùa cho mình. Khi hai ñoái töôïng vôùi caùc khoùa k1, k2 muoán laäp moät khoùa chung ñeå trao ñoåi thoâng tin ñoái töôïng thöù nhaát göûi cho ñoái töôïng thöù hai soá nguyeân toá yù theo coâng thöùc: (mod p) 0< < p Ñoái töôïng thöù hai seõ tìm khoùa chung k baèng caùch k(mod p) 0 < k < p Töông töï ñoái töôïng thöù theå thöù hai göûi cho ñoái töôïng thöù nhaát soá nguyeân : (mod p) 0< < p vaø ñoái töôïng thöù nhaát tìm ra khoùa chung k theo coâng thöùc: k(mod p) 4.2.4. Maõ khoùa coâng khai. Vôùi caùc heä maõ treân thì khoùa laäp maõ phaûi ñöôïc giöõ bí maät, neáu chaúng may khoùa naøy bò tìm ra thì vieäc giaûi maõ seõ khoâng gaëp khoù khaên laém. Moät nguyeân taéc môùi ñöôïc ñöa ra laø cho duø bieát ñöôïc khoùa laäp maõ nhöng chöa chaéc ñaõ tìm ra khoùa giaûi maõ trong moät thôøi gian coù theå chaáp nhaän. Moãi ñoái töôïng giöõ bí maät khoùa giaûi maõ rieâng cuûa mình trong luùc ñoù khoaù laäp maõ ñöôïc thoâng baùo coâng khai. Vaø neáu moät vaøi ñoái töôïng trong heä thoáng bò maát khoùa giaûi maõ thì caùc ñoái töôïng coøn laïi coù theå khoâng bò aûnh höôûng. Ñoù chính laø heä maõ muõ, ñoä phöùc taïp trong vieäc tìm logarit modulo p laø quaù lôùn. Trong moät heä thoáng coù nhieàu ñoái töôïng tham gia trao ñoåi thoâng tin vaø moãi ñoái töôïng choïn cho mình moät khoùa laäp maõ k vaø moät coâng thöùc maõ hoùa coâng khai E(k). Taát caû nhöõng ñoái töôïng coù khoùa laäp maõ coâng khai töø k1, k2, …, kn. Khi ñoái töôïng thöù i muoán göûi moät thoâng ñieäp cho ñoái töôïng thöù j, moãi chöõ ñöôïc chuyeån ñoåi thaønh soá vaø ñöôïc nhoùm thaønh töøng khoái vôùi ñoä daøi naøo ñoù. Sau ñoù, moãi khoái P trong vaên baûn ñöôïc maõ hoùa baèng khoùa laäp maõ E(kj) cuûa ñoái töôïng thöùj vaø göûi ñi döôùi daïng C= E(kj)(P). Giaûi maõ thoâng ñieäp naøy ñoái töôïng thöù j chæ vieäc duøng khoùa giaûi maõ Dkj: Dkj(C) = DkjEkj(P) =P Vì Dkj vaø Ekj laø khoùa giaûi maõ vaø khoùa laäp maõ cuûa cuøng ñoái töôïng thöù j. Caùc ñoái töôïng neáu nhaän ñöôïc vaên baûn maät cuõng khoâng theå naøo giaûi maõ ñöôïc vì cho duø bieát khoùa laäp maõ Ekj thì khoâng haún laø tìm ra khoùa giaûi maõ Dkj. 4.2.5. Sô löôïc veà RSA. RSA laø heä thoáng baûo maät khoùa coâng khai cho caû maõ hoùa vaø vieäc xaùc nhaän; ñöôïc phaùt minh vaøo naêm 1977 bôûi Ron Rivest, Adia vaø Leonard Adleman. Ñöôïc xaây döïng treân cô sôû maõ muõ trong ñoù khoùa laø caëp (e, n), goàm muõ e vaø modulo n. Soá n laø tích hai soá nguyeân toá lôùn nhaát naøo ñoù, n=pq, sao cho (e, (n)) = 1, trong ñoù (n) laø haøm Euler. Nhöõng kyõ thuaät ñaëc tröng söû duïng nhöõng thao taùc toaùn hoïc thaønh moät vaên baûn maõ. Nhöõng thao naøy goïi laø chöùc naêng moät chieàu, chöùc naêng töông ñoái deã thöïc hieän theo moät höôùng nhöng chuyeån ñoåi theo höôùng ngöôïc laïi thì khoù hôn nhieàu. Cheá ñoä baûo maät cuûa RSA döïa vaøo vieäc phaân tích nhöõng soá raát lôùn ra thöøa soá nguyeân toá. Baûng toùm taét quaù trình maõ hoaù RSA: Khoaù chung Khoaù rieâng Maõ hoaù Giaûi maõ n, tích hai soá nguyeân toá p, q e, nguyeân toá cuøng nhau vôùi (p-1)(q-1) c = me mod (p-1)(q-1) m = cd mod n Ôû ñaây, vì thôøi gian coù haïn chuùng toâi taäp trung tìm hieåu veà giaûi thuaät maõ hoaù RSA vaø öùng duïng cuûa giaûi thuaät naøy. Moät soá vaán ñeà lieân quan ñeán vieäc söû duïng khoùa: Vaên baèng chöùng nhaän söû duïng khoaù: Giaáy chöùng nhaän laø nhöõng vaên baèng kyõ thuaät soá ñöôïc chöùng thöïc ñeå lieân keát moät khoùa coâng khai vôùi moät caù nhaân hay nhöõng thöïc theå khaùc. Cho pheùp kieåm tra nhöõng yeâu caàu ñöa ra khoùa coâng khai treân thöïc teá ñöa ñeán moät caù nha._.ân. Vaên baèng chöùng nhaän ngaên chaën ngöôøi naøo ñoù töø moät khoùa giaû ñeå theå hieän döôùi daïng ngöôøi khaùc nöõa. Vaên baèng chöùng nhaän chöùa moät khoùa chung vaø moät caùi teân. Chuùng chöùa haïn söû duïng cuûa khoùa, teân cuûa nôi caáp vaên baèng chöùng nhaän coù lieân quan ñeán vaên baèng ñoù, soá saûn xuaát cuûa chöùng nhaän, vaø nhöõng thoâng tin khaùc nöõa. Haàu heát caùc vaên baèng naøy ñöôïc xaùc ñònh bôûi chuaån Quoác teá CCITT X.509; vaên baèng coù theå ñoïc hay vieát baèng nhieàu öùng duïng tuaân theo chuaån X.509. Xa hôn nöõa laø caûi tíeân ñaõ ñöôïc tìm thaáy trong chuaån PKCS vaø chuaån PEM. Chi tieát veà ñònh daïng cuûa vaên baèng cuõng ñöôïc tìm thaáy trong KEN. Moät vaên baèng ñöôïc ban haønh bôûi moät nhaø cung caáp baûn quyeàn vaø ñöôïc kyù vôùi khoùa baûo maät cuûa nhaø cung caáp naøy. Vaên baèng ñöôïc söû duïng nhö theá naøo? Moät vaên baèng coát loõi laø phaùt sinh nhöõng bí maät coù tính chaát phaùp lyù cuûa khoùa coâng khai. Ngöôøi naøo ñoù kieåm tra moät chöõ kyù cuõng coù theå kieåm tra vaên baèng chöùng nhaän cuûa ngöôøi kyù, ñeå ñaûm baûo raèng khoâng coù söï giaû maïo hay loãi ñöôïc tìm thaáy. Haàu heát baûo maät cuûa chöùng nhaän thöôøng bao goàm vieäc keøm theo moät hay nhieàu vaên baèng chöùng nhaän vaø moãi thoâng baùo ñöôïc kyù. Ngöôøi nhaän thoâng baùo coù theå kieåm tra vaên baèng baèng caùch söû duïng khoùa coâng khai cuûa vaên baèng vaø kieåm tra chöõ kyù cuûa thoâng baùo. Coù nhieàu vaên baèng keøm theo thoâng baùo, ñònh hình moät loaït caùc chuoãi xích coù traät töï, ôû moät khía caïnh naøo ñoù moät vaên baèng chöùng thöïc cho vieäc xaùc nhaän cuûa nhöõng vaên baèng tröôùc ñoù. Nhieàu ngöôøi göûi thì cuõng nhieàu ngöôøi nhaän hôn, nhu caàu ñoù laø göûi keøm theo, kieåm tra, xaùc nhaän. Chaúng haïn, neáu Alice göûi thoâng baùo ñeán cho Bob haøng ngaøy, Alice coù theå göûi keøm moät loaït caùc maéc xích vaên baèng töø nhöõng ngaøy ñaàu tieân maø Bob kieåm tra. Töø ñoù trôû ñi Bob chæ caàn löu tröõ khoùa coâng khai cuûa Alice vaø khoâng caàn thieát phaûi kieåm tra vaên baèng hay vieäc kieåm tra vaên baèng laø khoâng caàn thieát. Moät ngöôøi göûi laø ngöôøi cuûa coâng ty thì caàn bieát ngöôøi nhaän coù theå caàn göûi theo chæ chæ moät vaên baèng (ban haønh bôûi coâng ty ñoù), nhöng ngöôïc laïi moät ngöôøi göûi thuoäc coâng ty thì khoâng nhaän ra ñöôïc ngöôøi nhaän caàn göûi keøm theo hai vaên baèng. Thoùi quen toát laø göûi keøm theo phaûi nay ñuû moät loaït caùc vaên baèng chöùng nhaän ñeå ngöôøi ban haønh cuûa vaên baèng coù möùc ñoä cao nhaát trong chuoãi ñoù ñöôïc ngöôøi nhaän bieát ñeán. Theo nhö chuaån PKCS cho heä thoáng maõ hoaù duøng khoùa coâng khai, moãi chöõ kyù chæ ñeán moät vaên baèng chöùng nhaän ñaõ pheâ chuaån khoùa coâng khai cuûa ngöôøi kyù. Ñaëc bieät moãi chöõ kyù chöùa teân cuûa ngöôøi ban haønh vaên baèng vaø soá saûn xuaát cuûa vaên baèng. Do ñoù cho duø khoâng coù vaên baèng ñöôïc göûi keøm theo vôùi thoâng baùo ngöôøi keåim tra coù theå vaãn söû duïng moät loaït caùc vaên baèng ñeå kieåm tra tình traïng cuûa khoùa coâng khai. Nhaø cung caáp vaên baèng. Vaên baèng chöùng nhaän ñöôïc ban haønh bôûi nhaø cung caáp vaên baèng (goïi taét laø CA), ñöôïc söï uûy thaùc cuûa nhaø quaûn trò trung taâm saün saøng xaùc minh caùc ñaëc tính cuûa vaên baèng. Moät coâng ty coù theå phaùt haønh baèng chöùng nhaän cho nhaân vieân cuûa hoï, moät tröôøng ñaïi hoïc cung caáp cho sinh vieân, moät thaønh phoá cung caáp cho coâng daân cuûa hoï. Ñeå maø ngaên chaën vieäc giaû maïo vaên baèng, khoaù coâng khai cuûa cuûa CA ñaùng tin caäy: moät CA khoâng nhöõng phaûi coâng khai khoaù coâng khai cuûa hoï maø coøn cung caáp moät vaên baèng töø ôû möùc ñoä cao hôn ñeå chöùng nhaän tính phaùp lyù cuûa khoùa coâng khai cuûa hoï. Sau ñoù nhöõng giaûi quyeát ñöa ñeán caáp baäc cao hôn cuûa CA. Chaúng haïn nhö, Alice phaùt sinh caëp khoaù coâ ta sôû höõu vaø göûi khoùa coâng khai ñeán cho CA vôùi moät söï chöùng minh cuûa giaáy chöùng minh cuûa coâ ta. CA kieåm tra giaáy chöùng minh vaø ñöa tra nhöõng böôùc caàn thieát ñeå ñaûm baûo raèng nhöõng yeâu caàu ñöôïc ñöa ñeán töø Alice vaø roøi göûi cho coâ moät vaên baèng chöùng nhaän chöùng thöïc lieân keát giöõa coâ ta vaø khoùa coâng khai cuûa coâ ta, theo cuøng vôùi moät maéc xích caáp baäc ñeán khi naøo yeâu caàu ñeå chöùng minh tính hôïp phaùp cuûa khoùa coâng khai cuûa coâ ta. Nhöõng CA khaùc coù theå ban haønh nhöõng vaên baèng chöùng nhaän vôùi nhöõng möùc ñoä khaùc nhau cuûa nhöõng yeâu caàu nhaän dieän. Moät CA coù theå nhaát ñònh caàn giaáy ñaêng kyù cuûa ngöôøi ñieàu khieån, nhöõng CA khaùc muoán hình thöùc yeâu caàu vaên baèng phaûi ñöôïc coâng chöùng nhöng cuõng coù caùi phaûi baét coù daáu chæ ñieåm cuûa ngöôøi yeâu caàu moät vaên baèng. Moãi moät CA caàn ñöôïc coâng boá nhöõng chuaån vaø nhöõng ñieàu kieän chöùng nhaän maø noù sôû höõu, vì vaäy nhöõng ngöôøi kieåm tra caàn kieåm tra vaøo nhöõng möùc ñoä thích hôïp rieâng tö trong teân chöùng nhaän – lieân keát khoùa. Ví duï moät giao thöùc ban haønh vaên baèng chöùng nhaän laø Apple Computer's Open Collaborative Environment (OCE) (moâi tröôøng coäng taùc môû cuûa maùy tính Apple). Nhöõng ngöôøi söû duïng Apple OCE caàn phaùt sinh moät caëp khoùa vaø roài yeâu caàu vaø nhaän vaên baèng chöùng nhaän cho khoùa coâng khai; vaên baèng naøy yeâu caàu phaûi coù daáu chæ ñieåm. Chöùng nhaän ñôn vò chöõ kyù CSU (Certificate Signing Unit) Chöùng nhaän löu tröõ khoùa bí maät laø moät ñieàu voâ cuøng quan troïng, nhöõng khoùa bí maät cuûa toå chöùc chöùng nhaän ñaõ ñöôïc löu tröõ moät caùch bí maät, bôûi vì söï baøn baïc cho pheùp khoâng kieåm tra vieäc giaû maïo chöõ kyù. Vieäc baûo maät phaûi ñöôïc yeâu caàu laø löu tröõ khoùa trong moät hoäp choáng troäm caép; hoäp ñoù ñöôïc goïi laø Certificate Signing Unit hay CSU. Caùch toát nhaát laø CSU trieät phaù nhöõng nhöõng gì beân trong noù neáu moät khi noù bò môû vaø ñöôïc baûo veä ñeå choáng laïi nhöõng xaâm nhaäp söû duïng böùc xaï ñieän töø. Khoâng baát kyø nhaân vieân naøo cuûa toå chöùc chöùng nhaän coù theå truy caäp vaøo khoùa rieâng bí maät ñoù ñöôïc, nhöng chæ coù khaû naêng söû duïng khoùa bí maät ñoù trong vieäc caáp vaên baèng chöùng nhaän. Coù nhieàu thieát keá coù theå thöïc hieän ñöôïc cho CSU. CSU ñöôïc hoaït hoaù bôûi moät chuoãi caùc khoùa döõ lieäu ñoù laø nhöõng khoùa vaät lyù coù khaû naêng chöùa nhöõng thoâng tin kyõ thuaät soá. Nhöõng khoaù döõ lieäu söû duïng kyõ thuaät chia seû baûo maät do ñoù vaøi ngöôøi phaûi duïng taát caû nhöõng khoùa döõ lieäu cuûa hoï ñeå ñöôïc kích hoaït CSU. Ñieàu naøy ngaên chaën nhaân vieân CA cung caáp vaên baèng giaû. Chuù yù raèng neáu CSU bò phaù, trong hoaû hoaïn, khoâng baûo maät naøo bò xaâm phaïm. Vaên baèng chöùng nhaän ñaõ ñöôïc kyù bôûi CSU coù giaù trò toàn taïi maõi, cho ñeán khi naøo ngöôøi kieåm tra söû duïng ñuùng khoùa coâng khai. Aûnh höôûng cuûa nhöõng taán coâng vaøo toå chöùc caáp vaên baèng: Ngöôøi ta coù theå noùi veà nhieàu vuï taán coâng nhaém vaøo nhöõng toå chöùc cung caáp vaên baèng chöùng nhaän, do ñoù nhöõng toå chöùc naøy phaûi ñöôïc chuaån bò ñeå choáng laïi nhöõng taán coâng ñoù. Ta xem xeùt ñeán moät taán coâng sau. Giaû söû raèng Bob muoán giaû daïng Alice. Neáu Bob coù theå coù ñöôïc nhöõng thoâng baùo kyù nhö Alice, anh ta coù theå göûi thoâng baùo vaøo ngaân haøng cuûa Alice vaø noùi “ Toâi muoân ruùt ra 10000 $ töø taøi khoaûn cuûa toâi. Göûi tieàn cho toâi”. Ñeå taán coâng ñieàu naøy, Bob phaùt sinh moät caëp khoùa vaø göûi khoùa ñeán nôi cung caáp vaên baèng chöùng nhaän vaø noùi “Toâi laø Alice. Ñaây laø khoùa coâng khai cuûa toâi. Laøm ôn göûi cho toâi moät baèng chöùng nhaän”. Neáu nhö CA bò löøa vaø göûi ñeán cho anh ta moät vaên baèng vaø anh ta coù theå löøa ngaân haøng thì anh ta ñaõ taán coâng moät caùch thaønh coâng. Ñeå ngaên chaën vieäc taán coâng naøy CA phaûi kieåm tra baèng chöùng nhaän yeâu caàu thöïc teá cuûa ngöôøi taïo ra noù, nghóa laø noù phaûi theå hieän tính yeâu caàu thích ñaùng ñoù laø Alice thaät söï, ngöôøi ñang yeâu caàu vaên baèng chöùng nhaän. Vôùi ví duï naøy CA coù theå yeâu caàu Alice xuaát hieän vaø trình ra giaáy tôø chöùng minh mình laø Alice theå hieän ngaøy sinh cuûa coâ ta. Moät vaøi CA yeâu caàu moät soá nhaän daïng nhöng ngaân haøng khoâng caàn nhöõng thoâng baùo mang tính danh döï vôùi nhöõng baèng chöùng nhaän nhaân caùch thaáp. Moãi CA phaûi coâng boá tình traïng baûn thaân nhaän daïng yeâu caàu vaø moät soá ñieàu khoaûn, nhöõng caùi khaùc coù theå keøm theo moät möùc ñoä thích hôïp cuûa bí maät cuûa vieäc chöùng nhaän. Moät keû xaâm nhaäp coù theå phaùt hieän ra khoùa bí maät rieâng tö cuûa moät toå chöùc caáp baèng vaø roài giaû vaên baèng. Vôùi lyù do naøy, moät toå chöùc caáp vaên baèng phaûi phoøng ngöøa töø xa ñeå ngaên chaën nhöõng vieäc truy caäp baát hôïp phaùp ñeå laáy khoaù bí maät rieâng tö. Khoaù coâng khai cuûa toå chöùc caáp vaên baèng phaûi bao quaùt roäng raõi choáng laïi moïi taán coâng. Vôùi ñieàu naøy, nhöõng CA phaûi söû duïng raát nhieàu khoùa daøi, toát nhaát laø 1000 bít hay daøi hôn, vaø cuõng thay ñoåi khoùa moät caùch ñeàu ñaën. Nhöõng toå chöùc caáp baèng haøng ñaàu coù nhöõng ngoaïi tröø khoâng thöïc teá trong vieäc hoï thay ñoåi khoaù thöôøng xuyeân laø vì khoùa coù theå ñöôïc vieát trong phaàn meàm ñöôïc söû duïng bôûi moät soá raát lôùn cuûa nhöõng ngöôøi kieåm tra. Trong nhöõng tình huoáng taán coâng khaùc, Alice mua chuoäc Bob, ngöôøi laøm vieäc cho toå chöùc cung caáp vaên baèng, ñeå caáp cho coâ ta moät vaên baèng chöùng nhaän vôùi teân cuûa Fred. Hieän giôø Alice coù theå göûi nhöõng thoâng baùo ñöôïc kyù teân Fred vaø nhöõng ngöôøi khaùc nhaän nhöõng thoâng baùo seõ tin raèng thoâng baùo ñoù ñaùng tn caäy bôûi vì moät loaït caùc vaên baèng ñaày ñuû vaø coù theå ñöôïc kieåm tra seõ ñi keøm theo thoâng baùo. Taán coâng naøy coù theå gaây caûn trôû bôûi vieäc yeâu caàu söï coäng taùc chung cuûa hai hay nhieàu nhaân vieân ñeå phaùt sinh moät vaên baèng; baáy giôø keû taán coâng hoái loä hai hay nhieàu nhaân vieân nöõa. Chaúng haïn, trong vaøi CSU ngaøy nay, ba nhaân vieân phaûi ñöa moät khoùa döõ lieäu chöùa thoâng tin baûo maät uûy quyeàn cho CSU ñeå phaùt sinh vaên baèng. Khoâng may, coù nhieàu caùch ñeå phaùt sinh ra vaên baèng giaû bôûi vieäc hoái loä chæ moät nhaân vieân. Neáu moãi vaên baèng chæ yeâu caàu kieåm tra bôûi moät nhaân vieân thì nhaân vieân ñoù coù theå bò hoái loä vaø nheùt caùc yeâu caàu sai vaøo trong moät ngaên xeáp cuûa nhöõng yeâu caàu chöùng nhaän thaät söï. Chuù yù raèng nhöõng nhaân vieân ñöôïc hoái loä khoâng ñeå loä ra khoùa bí maät cuûa toå chöùc caáp vaên baèng chöùng nhaän ñeán khi naøo noù coù theå chöùa moät caùch hôïp leä. Nhöõng taán coâng khaùc bao goàm vieäc giaû maïo nhöõng taøi lieäu cuõ. Alice ñaõ coá gaéng tính toaùn moâñun cuûa toå chöùc caáp baèng. Noù seõ tieâu toán cuûa coâ ta khoaûng 15 naêm, nhöng cuoái cuøng coâ cuõng thaønh coâng, vaø hieän giôø coâ ta coù caû nhöõng khoùa bí maät cuõ cuûa toå chöùc caáp vaên baèng. Khoaù naøy ñaõ bò chaën vì ñaõ heát haïn, nhöng coâ ta coù theå giaû maïo moät vaên baèng coù ngaøy 15 naêm tröôùc ñoù chöùng minh moät khoùa coâng khai giaû, coâ ta coù theå giaû maïo moät taøi lieäu vôùi chöõ kyù cuûa Bob vôùi ngaøy 15 naêm tröôùc ñoù, coù leõ seõ di chuyeån nhöõng thoâng tin ñeán Alice. Nhöõng phaùt sinh ñöôïc baét nguoàn vôùi söï giaû maïo cho nhöõng taøi lieäu tröôùc ñoù nhieàu naêm. Chuù yù raèng : Nhöõng taán coâng vaøo nhöõng toå chöùc caáp vaên baèng khoâng ñe doïa ñöôïc nhöõng bí maät cuûa caùc thoâng baùo giöõa nhöõng ngöôøi söû duïng, vì haàu nhö moïi keát quaû ñeàu taán coâng vaøo trung taâm phaân boá nhöõng khoùa bí maät. Neáu khoùa cuûa toå chöùc caáp vaên baèng bò maát hay phaù huyû nhöng khoâng laøm xaâm phaïm, nhöõng vaên baèng ñöôïc kyù vôùi nhöõng khoaù cuõ vaãn toàn taïi cho ñeán khi naøo ngöôøi kieåm tra bieát söû duïng nhöõng khoaù coâng khai cuõ ñeå kieåm tra vaên baèng. Trong moät vaøi thieát keá CSU, sao cheùp nhöõng löu tröõ ñöôïc maõ hoaù cuûa nhöõng bí maät cuûa CA ñöôïc giöõ. Moät CA bò maát khoùa cuûa noù coù theå phuïc hoài laïi baèng caùch noù baèng caùch nhaäp vaøo nhöõng löu tröõ ñöôïc maõ hoaù beân trong CSU; löu tröõ maõ hoùa chæ coù theå giaûi maõ khi ñang söû duïng CSU. Neáu nhö baûn thaân CSU bò phaù huûy, nhaø saûn xuaát coù theå seõ cung caáp moät caùi khaùc coù thoâng tin beân trong töông töï do ñoù cho pheùp laáy laïi ñöôïc khoùa. Moät khoaù CA bò xaâm phaïm ôû moät tình traïng raát nguy hieåm. Moät keû taán coâng phaùt hieän ra khoaù bí maät cuûa CA coù theå phaùt sinh ra nhöõng vaên baèng giaû maïo trong teân cuûa CA maø cho pheùp khoâng kieåm tra söï giaû maïo; vôùi lyù do naøy, taát caû moïi söï phoøng ngöøa phaûi ñöôïc ngaên chaën vieäc laøm xaâm phaïm. Neáu moät xaâm phaïm naûy sinh thì CA phaûi laäp töùc ngöng vieäc cung caáp vaên baèng vôùi nhöõng khoùa cuõ vaø thay baèng nhöõng khoùa môùi. Neáu noù bò nghi ngôø thì vaøi vaên baèng giaû maïo thì raát caû nhöõng vaên baèng ñaõ ñöôïc caáp phaûi goïi laïi vaø ñöôïc caáp laïi khoùa CA môùi. Nhöõng vieäc löôøng tröôùc naøy khoâng caêng thaúng ñeán möùc neáu nhöõng vaên baèng ñaõ ñöôïc ñaêng kyù vôùi dòch vuï ñònh thôøi gian. Chuù yù raèng vieäc toån haïi cuûa moät khoaù CA khoâng laøm maát hieäu löïc cuûa khoùa cuûa nhöõng ngöôøi söû duïng, nhöng chæ nhöõng vaên baèng ñöôïc xaùc nhaän. Toån haïi cuûa moät khoùa cuûa CA haøng ñaàu caàn phaûi suy nghó chính chaén vì khoùa coù theå ñöôïc xaây döïng trong nhöõng öùng duïng kieåm tra nhöõng vaên baèng. Danh saùch thu hoài chöùng nhaän (Certificate Revocation List (CRL)) laø danh saùch nhöõng khoùa coâng khai bò thu hoài tröôùc khi noù heát haïn. Coù moät vaøi lyù do khoùa bò thu hoài vaø ñöa vaøo danh saùch CRL. Moät khoaù ñaõ bò xaâm phaïm. Moät khoaù ñöôïc söû duïng moät caùch thaønh thaïo bôûi moät caù nhaân trong moät coâng ty; ví duï teân chính thöùc ñöôïc lieân keát vôùi moät khoùa coù leõ laø “Alice Avery, Vice President, Argo Corp”. Neáu Alice ñaõ nhieät tình, coâng ty cuûa coâ aáy khoâng muoán coâ aáy coù theå seõ kyù teân nhöõng thoâng baùo vôùi khoùa ñoù vaø ñoù laø lyù do ñeå coâng ty dôøi khoaù vaøo trong CRL. Khi kieåm tra moät chöõ kyù, moät ngöôøi coù theå kieåm tra tính chính xaùc cuûa CRL ñeå chaéc chaén raèng khoùa cuûa ngöôøi kyù khoâng bò giaû maïo. Cho duø ñoù laø thôøi gian chính ñaùng ñeå thöïc thi kieåm tra naøy döïa treân taàm quan troïng cuûa taøi lieäu ñaõ ñöôïc kyù. CRL ñöôïc duy trì bôûi nhöõng CA vaø cung caáp thoâng tin veà nhöõng khoaù bò giaû maïo nhöõng vaên baèng nguyeân thuyû bôûi CA. Nhöõng CA chæ lieät keâ nhöõng khoùa hieän taïi vì nhöõng khoùa ñaõ heát haïn khoâng ñöôïc thöøa nhaän trong tröôøng hôïp naøy; khi moät khoùa giaû maïo vöôït qua nhöõng ngaøy heát haïn nguyeân thuyû cuûa noù thì noù ñöôïc di chuyeån ra khoûi CRL. Maëc duø CRL ñöôïc duy trì trong loaïi ñöôïc phaân boå, ñoù coù theå laø nôi phaân boå trung taâm cho CRL, ñoù laø nhöõng vò trí treân maïng chöùa nhöõng CRL môùi nhaát töø nhieàu toå chöùc khaùc nhau. Moät toå chöùc gioáng nhö moät ngaân haøng döôøng nhö muoán tieán haønh löu tröõ CRL ñeå taïo ra nhöõng nguyeân cöùu CRL khaû thi treân moãi giao dòch. Ñeå ñeà phoøng choáng laïi moät taán coâng tính toaùn vôùi giôùi haïn daøi, moãi khoùa phaûi coù ngaøy heát haïn sau ñoù noù khoâng coøn coù giaù trò nöõa. Vì vaäy thôøi gian ñeå heát haïn phaûi ngaén hôn thôøi gian tính toaùn hay töông ñöông, chieàu daøi khoaù phaûi ñuû daøi ñeå taïo ra söï thay ñoåi cuûa vieäc tính toaùn tröôùc vieäc heát haïn cöïc nhoû. Thôøi gian hôïp leä cho moät caëp khoùa cuõng döïa treân hoaøn caûnh vaø trong hoaøn caûnh naøy khoaù seõ ñöôïc söû duïng maëc duø seõ coù thôøi gian chuaån. Thôøi gian hôïp leä laãn vôùi giaù trò cuûa khoaù vaø ñaùnh giaù söùc maïnh cuûa moät taán coâng ñöôïc chôø ñôïi thì xaùc ñònh ñöôïc kích thöôùc khoùa thích hôïp. Ngaøy heát haïn cuûa moät khoaù ñi keøm vôùi khoaù coâng khai trong vaên baèng hay trong danh saùch thö muïc. Chöông trình kieåm tra chöõ kyù neân kieåm tra vieäc heát haïn vaø khoâng neân chaáp nhaän moät thoâng baùo ñöôïc kyù vôùi moät khoùa heát haïn. Ñieàu naøy coù nghóa laø khi moät ai ñoù sôû höõu khoaù heát haïn, moïi thöù ñaõ ñöôïc kyù seõ khoâng ñöôïc tính toaùn chu ñaoù. Taát nhieân ñoù seõ laø nhöõng tröôøng hôïp quan troïng ñoù laø nhöõng taøi lieäu ñaõ kyù ñöôïc xem xeùt hôïp lyù cho nhieàu chu kyø thôøi gian daøi hôn. Sau khi keát thuùc, ngöôøi söû duïng choïn moät khoùa môùi daøi hôn khoùa cuõ, coù leõ baèng vaøi con soá ñeå phaûn aùnh caû vieäc gia taêng thöïc thi cuûa phaàn cöùng maùy tính vaø vaøi söï caûi tieán gaàn ñaây trong nhöõng giaûi thuaät tính toaùn thöøa soá. Baûn phuï luïc chieàu daøi khoaù ñöôïc ñeà nghò seõ ñöôïc coâng boá. Moät ngöôøi söû duïng coù theå kieåm tra laïi moät khoaù ñaõ heát haïn chöa, neáu ñoù laø chieàu daøi thích hôïp vaø khoâng bò xaâm phaïm. Toå chöùc chöùng nhaän vaên baèng seõ phaùt sinh ra moät vaên baèng môùi cuøng khoùa, vaø taát caû nhöõng chöõ kyù môùi seõ ñöôïc ñieåm treân vaên baèng môùi thay cho caùi cuõ. Tuy nhieân, söï vieäc phaàn cöùng maùy tính tieáp tuïc caûi tieán chæ roõ cho vieäc thay theá nhöõng khoùa heát haïn vôùi nhöõng khoùa môùi vaø daøi hôn vaøi naêm. Vieäc thay theá khoùa co pheùp ngöôøi ta thaáy ñöôïc moái thuaän lôïi cuûa caûi tieán phaàn cöùng ñeå gia taêng tính baûo maät trong heä thoáng maõ hoùa. Phaàn cöùng nhanh hôn ñaõ aûnh höôûng ñeán vieäc gia taêng baûo maät, coù leõ meânh moâng nhöng chæ neáu chieàu daøi khoaù ñöôïc gia taêng thöôøng xuyeân. Neáu chaúng may khoùa bí maät cuûa baïn bò maát hay bò phaù huûy nhöng khoâng bò xaâm haïi, baïn coù theå khoâng kyù daøi hôn hay giaûi maõ nhöõng thoâng baùo nhöng vaøi caùi tröôùc ñoù ñaõ ñöôïc kyù vôùi khoùa bò maátvaãn coù giaù trò. Ñeàiu naøy coù theå xaûy ra, ví duï neáu baïn queân maät khaåu ñöôïc söû duïng ñeå try caäp khoùa cuûa baïn hay neáu oå cöùng maø treân ñoù khoùa ñöôïc löu tröõ ñaõ bò hö haïi. Baïn caàn phaûi choïn moät khoùa môùi ñuùng ngay laäp töùc, ñeå giaûm möùc toái thieåu soá nhöõng thoâng baùo moïi ngöôøi göûi baïn ñaõ maõ hoùa döôùi khoaù cuõ cuûa baïn, nhöõng thoâng baùo baïn khoâng caàn thieát phaûi ñoïc. Caùc vaán ñeà seõ xaûy ra neáu khoùa cuûa baïn bò xaâm nhaäp: Neáu chaúng may khoùa bí maät cuûa baïn bò xaâm nhaäp ñoù laø neáu baïn nghi ngôø moät keû taán coâng coù theå chöùa khoùa bí maät cuûa baïn thì baïn phaûi laøm boä ñeå vaøi keû ñòch cuûa baïn coù theå ñoïc ñöôïc nhöõng thoâng baùo ñöôïc maõ hoùa göûi ñeán baïn vaø giaû maïo teân baïn treân nhöõng taøi lieäu. Nhöõng haäu quaû nghieâm troïng keøm theo tính chaát quan troïng cuûa vieäc baûo veä khoaù bí maät cuûa baïn vôùi nhöõng cô caáu maïnh cöïc kyø. Ngay laäp töùc baïn phaûi khai baùo vôùi nôi caáp aên baèng vaø ñöa khoaù cuõ cuûa baïn vaøo CRL; ôû ñoù seõ thoâng baùo cho moïi ngöôøi laø khoaù ñaõ bò giaû maïo. Sau ñoù choïn moät khoùa môùi vaø thu ñöôïc nhöõng vaên baèng thích hôïp vôùi noù. Baïn coù theå söû duïng khoùa môùiñeå kyù laïi nhöõng taøi lieäu maø baïn ñaõ kyù vôùi khoùa bò toån haïi; nhöõng taøi lieäu ñaõ ñöôïc ñònh thôøi gian toát nhö ñöôïc kyù vaãn coøn coù giaù trò. Baïn cuõng neân thay ñoåi caùch löu tröõ khoaù bí maät cuûa baïn ngaên chaën söï xaâm phaïm khoùa môùi. Xaâm nhaäp vaøo heä thoáng RSA. Coù moät vaøi caùch hieåu cuûa vieäc “beû gaõy” RSA. Caùi nguy hieåm nhaát laø coù theå moät keû taán coâng phaùt hieän ra khoùa bí maät töông öùng vôùi khoùa coâng khai; ñaây laø ñeàiu cho pheùp keû xaâm nhaäp coù theå ñoïc taát caû caùc thoâng ñieäp ñaõ ñöôïc maõ hoùa vôùi khoùa coâng khai vaø chöõ kyù giaû maïo. Hieån nhieân ñaây laø caùch vieäc taán coâng naøy laø laáy thöøa soá cuûa moâñun coâng khai n, döïa vaøo hai thöøa soá soá nguyeân toá laø p vaø q. Töø p vaø q vaø e, laø soá muõ chung, keû xaâm nhaäp coù theå deã daøng laáy ñöôïc d laø khoaù bí maät. Phaàn khoù khaên nhaát vieäc phaân tích ra thöøa soá cuûa n, baûo maät RSA döïa treân vieäc phaân tích thaønh thöøa soá laø raát khoù. Thöïc teá taùc vuï cuûa vieäc tìm laïi khoùa bí maät töông ñöông vôùi taùc vuï phaân tích thöøa soá moâñun: baïn coù theå söû duïng d ñeå phaân tích ra n cuõng nhö vieäc phaân tích thöøa soá n ñeå tìm ra d. Caùch khaùc ñeå “beû gaõy”RSA laø tìm ra moät kyõ thuaät tính toùan caên thöù e () chia n laáy dö. Vì c= me neân laø thoâng baùo m. vôùi caùch taán coâng naøy cho pheùp baát kyø ai cuõng coù theå phuïc hoài nhöõng thoâng baùo ñaõ maõ hoaù vaø nhöõng chöõ kyù giaû maïo maø khoâng caàn bieát khoùa bí maät. Hieän nay chöa coù phöông thöùc naøo coù theå beû khoùa RSA baèng caùch naøy. Nhöõng taán coâng ñöôïc ñeà caäp phaûi laø caùch duy nhaát ñeå beû khoùa RSA nhö caùch coù theå phuïc hoàitaát caû caùc thoâng baùo ñöôïc maõ hoùa döôùi moät khoùa laáy ñöôïc. Tuy nhieân coù nhöõng phöôngthöùc khaùc coù muïc ñích laø phuïc hoàinhöõng thoâng baùo ñôn giaûn. Thaønh coângnhöng khoâng cho pheùp nhöõng keû xaâm nhaäp coù theå phuïc hoàinhöõng thoâng baùo khaùc cuøng moät khoùa. Taán coâng moät thoâng baùo rieâng leû ñôn giaûn nhaát laø taán coâng vaøo nhöõng vaên baûn ñöôïc ñoaùn tröôùc. Moät keû xaâm nhaäp coù theå thaáy vaên baûn maõ hoùa vieäc taán coâng ñoù döôøng nhö laø “taán coâng luùc bình minh” vaø maõ hoùa öôùc ñoaùn naøy vôùi khoùa coâng khai cuûa ngöôøi nhaän, baèng caùch so saùnh vôùi vaên baûn maõ hoùa thöïc teá, keû xaâm nhaäp bieát ñöôïc trong baát cöù tröôøng hôïp naøo öôùc ñoaùn ñoù ñuùng. Vieäc taán coâng naøo coù theå bò ngaên caám bôûi vieäc theâm nhieàu bít ngaãu nhieân vaøo thoâng baùo. Taán coâng vaøo thoâng baùo rieâng leû khaùc coù theå xuaát hieän neáu moät ai ñoù göûi thoâng baùo ñeán ba ngöôøi, ngöôøi maø coù soá muõ coâng khai laø e =3. Keû taán coâng bieát ñöôïc ñieàu naøy vaø thaáy ba thoâng baùo ñoù coù theå phuïc hoài thoâng baùo ñoù, caùch taán coâng naøy vaø caùch ñeå ngaên chaën noù ñaõ ñöôïc thaûo luaän bôûi Hastad. Taát nhieân cuõng coù nhieàu kieåu taán coâng nhaém khoâng chæ nhaém vaøo baûn thaân RSA maø coøn ñöa ra nhöõng boå sung cho RSA; ñieàu naøy khoâng tính nhö “ “ beû gaõy”RSA” bôûi vì noù khoâng phaûi laø nhöõng yeáu ñieåm cuûa giaûi thuaät RSA bò khai thaùc, nhöng laø moät yeáu ñieåm trong nhöõng boå sung ñaëc bieät. Chaúng haïn nhö, neáu moät ai ñoù löu tröõ khoùa bí maät cuûa anh ta moät caùch lô laø khoâng an toaøn thì moät keû taán coâng coù theå phaùt hieän ra ñeàu naøy. Moät ngöôøi naøo ñoù khoâng theå nhaán maïnh moät caùch maïnh meõ ñích thöïc nhöõng yeâu caàu baûo maät RSA moät baûo maät boå sung, veà maët toaùn hoïc (baûo maät caùc giôùi haïn, chaúng haïn nhö choïn kích thöôùc chieàu daøi khoùa, nhöng khoân g ñuû. Trong thöïc teá, haàu heát nhöõng vuï taán coâng thaønh coâng seõ gioáng nhö ñích taïi nhöõng nôi boå sung khoâng baûo maät vaø taïi nhöõng giai ñoaïn quaûn lyù khoùa cuûa heä thoáng RSA. Nhöõng taán coâng vaøo heä thoáng RSA. Moät giaûi thuaät muõ soá moâñun RSA coù theå ngaét heä thoáng maõ hoaù vaø cho pheùp moät vaøi thoâng baùo giaûi maõ ñöôïc. Tuy nhieân, cuõng coù nhieàu cuoäc taán coâng tinh vi maø khoâng ñoøi hoûi soá muõ moâñun. Hoï coù theå khoâng coù keát quaû trong vieäc beû gaõy heä thoáng maät maõ RSA nhöng trong vaøi tröôøng hôïp ñaëc bieät hoï coù ñuû thoâng tin ñeå giaûi maõ ñöôïc moät soá thoâng baùo. Ta coù theå xem xeùt 4 loaïi taán coângvaøo heä thoáng maät maõ RSA. 1 Laïm duïng quaù nhieàu RSA. 2 Nhöõng taán coângvaøo soá muõ bí maät quaù thaáp 3 Nhöõng taán coângvaøo soá muõ coâng khai quaù thaáp ( truyeàn ñi roäng quaù) 4 Taán coângvaøo nhöõng boå sung Ta bieát laø giaù trò töôùng öùng töø p vaø q. Roõ raøng hôn, coù p vaø q ta coù theå tính , cuõng nhö theá ta coù theå tính p vaø q döïa treân phöông trình töông öùng. (1) Vaø chuù yù raèng ta coù hai phöông trình vaø khoâng bieát caû hai (vì n laø do ngöôøi khaùc ñöa ra). Cuõng nhö theá, khoùa bí maät d laø phöông trình bieát ñöôïc muõ soá moâñun RSA, p vaø q. khi bieát ñöôïc p vaø q ta coù theå bieát ñöôïc d döïa treân ñònh nghóa: . Vaø k = (ed -1)/ 2s, k laø moät soá chöùa laëp cô soá 2 chia cho ed -1 vaø ta coù ñöôïc soá dö vaø s laø soá laàn ta chia. Boå ñeà: vôùi moïi soá nguyeân a, soá nguyeân toá n, ñöôïc saép xeáp trong :ak+n Z vaø thuoäc nhoùm (Z / n Z)* laø: . (ak+n Z laø soá nhoû nhaát, / (ak+n Z)l = 1+ nZ ) Chöùng minh: laáy moät soá nguyeân laø soá nguyeân toá n, baèng ñònh lyù giaûi maõ RSA Vì ed-1 = k2s, ta coù: . Do ñoù: (ak+n Z)2s = 1+ nZ. Laëp laïi (ak+n Z)2s = 1+ nZ neáu vaø chæ neáu 2s ñöôïc chia bôûi ak+n Z trong nhoùm (Z / n Z)* Cho neân ak+n Z thuoäc nhoùm (Z / n Z)* chia cho 2s Ñònh lyù: laáy a laø moät nguyeân laø soá nguyeân toá cuøng vôùi n. Neáu ak khaùc baäc chia laáy dö cho p vaø q thì , vôùi Chöùng minh: baèng nhöõng keát quaû tröôùc ñoù, vaø name trong khoaûng . WOOLOG cho raèng lôùn hôn . Laáy 2t thuoäc , vaø t < s, nhöng . Cho neân . Giaûi thuaät treân cho pheùp coù theå ñöôïc söû duïng ñeå laáy laïi p vaø q ñeå ñöa ra e, d vaø n. ( chuù yù raèng coù ba loãi trong giaûi thuaät ñöôïc theå hieän trong phaàn naøy.) Ví duï: Chuùng ta seõ tính n =253, e= 3 vaø d= 147. Do ñoù, ed -1 = 440, k=55 vaø s=3. 1. Choïn moät soá nguyeân a ngaãu nhieân trong chuoãi . Ta laáy ( a=2). 2. Tính toaùn . Neáu g > 1 thì g =p hay g=q vaø ta tính ñöôïc thöøa soá n.( ) 3. neáu g = 1 thì tính toaùn vôùi cho ñeán khi hay t = 0.(, .) 4. Neáu n>g>1 thì g=p hay g = q. Töø ñaây, thöøa soá cuûa n ñöôïc tìm thaáy vaø giaûi thuaät keát thuùc. Noùi caùch khaùc, giaûi thuaät khoâng thaønh coâng vôùi vieäc löïa choïn döïa treân a (n= 23x11=253). Neáu giaûi thuaät khoâng thaønh coâng vôùi vieäc choïn a thì chuùng ta chaïy noù laïi moät laàn nöõa. Ñònh lyù: soá löôïng soá nguyeân toá a ñeán n trong ñoaïn {1, 2, …n} vôùi moãi ak coù moät vaø khaùc nhoû nhaát taïi (p-1)(q-1)/2 Ñònh lyù bao haøm xaùc suaát thaønh coâng cuûa giaûi thuaät laø taïi ½. Do ñoù, xaùc suaát thaønh coâng sau r laø taïi 1- 1/2r. Laïm duïng: Moät ví duï cuûa moät taán coâng laïm duïng hieån nhieân laø moâñun chung. Giaû söû raèng moät ngöôøi phoøng ngöøa vieäc söû duïng moâñun khaùc n=pq cho moãi ngöôøi söû duïng vaø söû duïng moät n coá ñònh. Thay vì moãi ngöôøi söû duïng laáy moät khoùa coâng khai (n, ei) vaø moät khoaù bí maät rieâng tö di.. Tuy nhieân Bob coù heå söû duïng khoùa bí maät maø anh ta sôû höõu db ñeå tính toaùn thöøa soá n. Moät khi anh ta tìm ra p vaø q anh ta coù theå soá muõ khoùa coâng khai cuûa Alice ñeå tìm ra muõ soá rieâng tö cuûa coâ ta. Muõ soá bí maät thaáp Ñeå giaûm bôùt thôøi gian giaûi maõ, moät ngöôøi coù theå söû duïng d nhoû. Tuy nhieân nhöõng keát quaû naøy naèm trong toaøn boä vieäc beõ gaõy heä thoáng maõ hoaù. Ñònh lyù: laáy n=pq vôùi q<p<2q. Laáy . Ta coù (n, e) vôùi , thì nhöõng keû taán coâng coù theå thu hoài ñöôïc d moät caùch hieäu quaû. Ñoù laø moät vaán ñeà khi coù d thì coù theå thu hoài neáu . Muõ soá coâng khai thaáp. Ñeå giaûm thôøi gian maõ hoaù, e thöôøng xuyeân ñöôïc choïn laø 3. Tuy nhieân, nhöõng taán coâng thaát baïi con soá e = 216 + 1 = 65537 ñöôïc ñeà nghò söû duïng. Vôùi e naøy, chæ vôùi pheùp tính muõ 16 vaø moät pheùp tính nhaân caàn thieát ñeå maõ hoaù vieäc muõ hoùa nhanh. Taán coâng khaép nôi ñoøi hoûi Bob göûi moät baûn sao e cuûa nhöõng thoâng baùo töông töï söû duïng nhieàu moâñun RSA khaùc nhau. Trong tröôøng hôïp naøy, keû taán coâng coù theå tính toaùn hieäu quaû nhöõng thoâng baùo goác. Do ñoù, vieäc taïo ra e lôùn hôn soá löôïng thoâng baùo ñeå voâ hieäu taán coâng naøy. Thi haønh. Nhöõng khaùc nhau giöõa kieåu taán coângñaàu tieân, vieäc laïm duïng RSA vaø nhöõng taán coâng trong vieäc thöïc thi laø tính tinh vi cuûa taán coâng. Nhöõng taán coâng vaøo vieäc thöïc thi töông ñöông vôùi nhöõng ñieàu ngoaøi phim giaùn ñieäp. Xem xeùt nhöõng theû thoâng minh löu tröõ khoaù RSA bí maät. Baèng söï tìm toøi laáy theû thoâng minh ñeå thöïc hieän moät giaûi maõ RSA, moät keû taán coâng coù leõ coù theå phaùt hieän muõ soá giaûi maõ bí maät d. Ngoaøi ra d cuõng coù theå thöôøng xuyeân bò phaùt hieän bôûi vieäc ño löôøng söùc maïnh vieäc tieâu thuï cuûa theû thoâng minh. Chöông 2: Tìm hieåu veà RSA. 1. Ñònh nghóa RSA: Naêm 1977, Ron Rivest, Adia Shamir vaø Leonard Adleman ñaõ ñöa ra heä thoáng maõ hoùa döõ lieäu duøng khoùa coâng khai. Ñöôïc laøm vieäc theo nguyeân taéc sau: choïn hai soá lôùn soá nguyeân toá laø p vaø q, vaø tính theo coâng thöùc n= pq, n ñöôïc goïi laø moâñun. Choïn moät soá e nhoû hôn n, vaø soá naøy coù giaù trò töông ñoái laø (p-1)(q-1), vaø tìm ra soá nghòch ñaûo cuûa chuùng, ñoù laø d, mod (p-1)(q-1). Coù nghóa laø ed = 1 mod (p-1)(q-1), e vaø d ñöôïc goïi laø soá muõ chung vaø soá muõ rieâng töông öùng. Khoùa coâng khai laø moät caëp (n, e) vaø khoùa bí maät laø d. Thöøa soá p vaø q phaûi ñöôïc giöõ bí maät hoaëc laøm maät hieäu quaû khi söû duïng laàn sau. Thaät khoù ñoaùn ñeå coù theå tìm ra ñöôïc khoùa bí maät d töø khoùa chung (coâng khai) (n, e). Tuy nhieân neáu ai ñoù coù ñöôïc n döïa treân p vaø q thì coù theå tìm ra khoùa bí maät d. Nhö theá toaøn boä vieäc baûo maät cuûa RSA ñöôïc caên cöù vaøo söï xaùc nhaän vieäc phaân tích ra thöøa soá nguyeân toá laø raát khoù. Ñoù laø caùch RSA laøm vieäc cho vieäc baûo maät rieâng reõ vaø chöùng minh xaùc nhaän. Baûo maät RSA (maõ hoùa): giaû söû raèng Alice muoán göûi moät thoâng baùo rieâng tö laø m ñeán cho Bob. Alice taïo ra moät vaên baûn maõ hoùa ñöôïc bieåu dieãn döôùi daïng muõ c = m^e mod n, coù e vaø n laø khoùa coâng khai cuûa Bob. Ñeå maõ hoùa, Bob cuõng phaûi giaûi maõ haøm muõ m = c^d mod n, vaø chuyeån ñoåi laïi thaønh thoâng baùo nguyeân thuyû m. phaûi chaéc chaén raèng moái quan heä giöõa e vaø d phaûi ñuùng thì Bob môùi coù theå chuyeån ñoåi chính xaùc thoâng baùo ñoù ñöôïc. Vì chæ coù Bob môùi bieát ñöôïc d, vaø do ñoù cuõng chæ coù Bob môùi coù theå giaûi maõ ñöôïc. Chöùng minh xaùc thöïc cuûa RSA: giaû söû Alice muoán göûi moät taøi lieäu maät hieäu m ñeán cho Bob. Alice taïo ra moät chöõ kyù kyõ thuaät soá vaø cuõng ñöôïc bieåu dieãn döôùi daïng muõ s = m^d mod n, maø d vaø n caëp khoùa cuûa Alice. Coâ ta göûi s vaø m ñeán cho Bob. Ñeå kieåm tra chöõ kyù coù ñ._.