[Powered by Google Translate] [RSA] [Rob Bowden] [Tommy MacWilliam] [Universitato Harvard] [Jen CS50.] [CS50.TV] Ni rigardu RSA, vaste uzata algoritmo por encrypting datumoj. Ĉifrado algoritmoj kiel Cezaro kaj Vigenère ĉifroj estas ne tre sekura. Kun la cezaro kodita, atacante nur bezonas provi 25 malsamaj ŝlosiloj por ricevi la mesaĝon de simpla teksto. Dum la Vigenère estas pli sekura ol la cezaro kodita pro la pli grandaj serĉo spaco por klavoj, fojo atacante konas la longecon de la ŝlosilon en Vigenère, kiu povas esti difinita per analizo de ŝablonoj en la kodita teksto, la Vigenère ne estas tiel multe pli sekura ol la cezaro ĉifro. RSA, aliflanke, ne estas vundebla al atakoj kiel ĉi tio. Cezaro kodita kaj Vigenère uzi la saman ŝlosilon al ambaŭ ĉifri kaj malĉifri mesaĝon. Ĉi tiu propraĵo faras tiuj koditaj simetriaj ŝlosilaj algoritmoj. Fundamenta problemo kun simetria ŝlosilo algoritmoj estas ke ili fidas la encrypting kaj sendante la mesaĝon kaj la ricevo kaj decrypting la mesaĝo esti jam konsentis antaŭenirita sur la klavo ili ambaŭ uzas. Sed ni havas iom de lanĉo problemon ĉi tie. Kiel 2 komputiloj kiuj volas komuniki establi sekreta ŝlosilo inter ili? Se la ŝlosilo devas esti sekreta, do ni bezonas vojon por kodi kaj deĉifri la ŝlosilon. Se ĉiuj ni havas estas simetria ŝlosila ĉifriko tiam ni ĵus revenis al la sama problemo. RSA, aliflanke, uzas paron de klavoj, unu por ĉifrado kaj alia por malĉifro. Unu estas nomata la publika ŝlosilo, kaj la alia estas la privata ŝlosilo. La publika ŝlosilo estas uzata por kodi mesaĝojn. Kiel vi eble konjektas por lia nomo, oni povas dividi niajn publika ŝlosilo kun neniu ni volas sen kompromiti la sekurecon de ĉifrita mesaĝo. Mesaĝoj ĉifrita uzante publikan ŝlosilon nur povas deĉifrita kun lia responda privata ŝlosilo. Dum vi povas dividi viajn publika ŝlosilo, vi devus ĉiam subteni viajn privatajn ŝlosilo sekreto. Ekde la privata ŝlosilo devus gardi sekreta kaj nur la privata ŝlosilo povas esti uzata por malĉifri mesaĝojn, se 2 uzantoj volas sendi mesaĝojn kodita kun RSA tien kaj reen ambaŭ uzantoj bezonas havi sian propran publikaj kaj privataj ŝlosilo paron. Mesaĝoj de uzanto 1 ĝis uzanto 2 uzi nur uzanto 2 La ŝlosila paro, kaj mesaĝoj de uzanto 2 al uzanto 1 nur uzi uzanto 1-oj ŝlosilo paron. La fakto ke estas 2 apartaj klavoj por kodi kaj deĉifri mesaĝojn faras RSA nesimetria ŝlosila algoritmo. Ni ne bezonas por kodi la publika ŝlosilo por sendi ĝin al alia komputilo ekde la klavo estas publika ĉiuokaze. Tio signifas, ke RSA ne havas la saman problemon kiel lanĉo simetria ŝlosilo algoritmo. Kiel fari 2 komputiloj kiuj volas komuniki establi sekreta ŝlosilo inter ili? Se la ŝlosilo devas esti sekreta, do ni bezonas vojon por kodi kaj deĉifri la ŝlosilon. Se ĉiuj ni havas estas simetria ŝlosila ĉifriko tiam ni ĵus revenu al la sama problemo. RSA, aliflanke, uzas paron de klavoj, unu por ĉifrado kaj alia por malĉifro. Unu estas nomata la publika ŝlosilo, kaj la alia estas la privata ŝlosilo. La publika ŝlosilo estas uzata por kodi mesaĝojn. Kiel vi eble konjektas por lia nomo, oni povas dividi niajn publika ŝlosilo kun iu ni volas sen kompromiti la sekurecon de ĉifrita mesaĝo. Mesaĝoj ĉifrita uzante publikan ŝlosilon nur povas deĉifrita kun lia responda privata ŝlosilo. Dum vi povas dividi viajn publika ŝlosilo, vi devus ĉiam subteni viajn privatajn ŝlosilo sekreto. Ekde la privata ŝlosilo devus gardi sekreta kaj nur la privata ŝlosilo povas esti uzata por malĉifri mesaĝojn se 2 uzantoj volas sendi mesaĝojn ĉifrita kun RSA tien kaj reen ambaŭ uzantoj bezonas havi sian propran publikaj kaj privataj ŝlosilo paron. Mesaĝoj de uzanto 1 ĝis uzanto 2 nur uzi uzanto 2 La ŝlosila paro, kaj mesaĝoj de uzanto 2 al uzanto 1 nur uzi uzanto 1-oj ŝlosilo paron. La fakto ke estas 2 apartaj klavoj por kodi kaj deĉifri mesaĝojn faras RSA nesimetria ŝlosila algoritmo. Ni ne bezonas por kodi la publika ŝlosilo por sendi ĝin al alia komputilo ekde la klavo estas publika ĉiuokaze. Tio signifas, ke RSA ne havas la saman problemon lanĉo kiel la simetria ŝlosilo algoritmoj. Do se mi volas sendi mesaĝon uzante RSA ĉifrado al Rob, mi unue bezonas Rob publika ŝlosilo. Por generi paro de klavoj, Rob bezonas repreni 2 grandaj primoj. Ĉi tiuj numeroj estos uzata en ambaŭ la publika kaj privata klavoj, sed la publika ŝlosilo nur uzi la produkton de tiuj 2 nombroj, ne la nombra sin. Iam mi ĉifrita la mesaĝon uzante Rob publika ŝlosilo Mi povas sendi la mesaĝon al Rob. Por komputilo, faktoranta nombroj estas malmola problemo. La publika ŝlosilo, memoru, uzita la produkto de 2 primoj. Tiu produkto devas tiam havi nur 2 faktoroj, kiu hazarde estas la numeroj, kiuj konsistigas la privata ŝlosilo. Por deĉifri la mesaĝon, RSA uzos ĉi privata ŝlosilo aŭ la numeroj multiplikita kune en la procezo de kreado la publika ŝlosilo. Ĉar estas kompute peza al faktorigi la nombro uzata en publika ŝlosila en la 2 nombroj uzita en la privata ŝlosilo ĝi estas malfacila por atacante elŝeligi la privata ŝlosilo ke estos necesa por deĉifri la mesaĝon. Nun ni iru al iu malsupera nivelo detaloj de RSA. Ni unue vidu kiel ni povas generi paro de ŝlosiloj. Unue, ni bezonos 2 primoj. Ni vokos tiuj 2 nombroj p kaj q. Por repreni p kaj q, en la praktiko ni pseudorandomly generi grandaj nombroj kaj tiam uzi testo por determini ĉu aŭ ne tiuj nombroj estas probable primo. Ni povas gardi generi hazardaj nombroj denove kaj denove gxis ni havas 2 primoj ke ni povas uzi. Jen ni elektu p = 23 kaj q = 43. Memoru, en la praktiko, p kaj q devas esti multe pli granda nombro. Koncerne ni scias, la pli granda la nombroj, la pli malfacila estas por fendi ĉifrita mesaĝo. Sed estas ankaŭ pli multekosta por kodi kaj deĉifri mesaĝojn. Hodiaŭ ĝi estas ofte rekomendis ke p kaj q estas almenaŭ 1024 bitoj, kiu metas ĉiun numeron ĉe super 300 decimaloj. Sed ni elektu tiujn malgrandajn numerojn por ĉi tiu ekzemplo. Nun ni multigos p kaj q kune akiri 3rd numeron, kiuj ni vokos n. En nia kazo, n = 23 * 43, kiu = 989. Ni n = 989. Sekva ni multigos p - 1 kun q - 1 akiri 4th nombro, kiun ni nomas m. En nia kazo, m = 22 * ​​42, kiu = 924. Ni havas m = 924. Nun ni bezonas nombro e kiu estas prima al m kaj malpli ol m. Du nombroj estas relative primo aŭ interprimo se la sola pozitiva entjero kiu dividas ilin ambaŭ egale estas 1. En aliaj vortoj, la plej granda komuna divizoro de e kaj m devas esti 1. En la praktiko, estas komuna por e esti la prima 65537 tiel longe kiel ĉi numero ne hazarde estas faktoro de m. Por nia klavoj, ni elektu kaj = 5 ekde 5 estas relative primo al 924. Fine, ni bezonos pli da, kiujn ni vokos d. D devas esti iu valoro kiu kontentigas la ekvacion de = 1 (mod m). Ĉi mod m signifas ni uzos iun nomita modula aritmetiko. En modula aritmetiko, unufoje nombro prenas pli altaj ol iu supera baro ĝi envolver reen ĉirkaŭ al 0. Horloĝo, ekzemple, uzas modula aritmetiko. Unu minuton poste 1:59, ekzemple, estas 2:00, ne 1:60. La minuto mano envolvis ĉirkaŭ al 0 sur atingi supera baro de 60. Do, ni povas diri 60 estas ekvivalento al 0 (_mod_ 60) kaj 125 estas ekvivalenta al 65 estas ekvivalenta al 5 (mod 60). Nia publika ŝlosilo estos la paro e kaj n kie en ĉi tiu kazo e estas 5 kaj n estas 989. Nia privata ŝlosilo estos la paro d kaj n, kiu en nia kazo estas 185 kaj 989. Rimarku ke nia originala primoj p kaj q ne aperas ie ajn en nia privata aŭ publika klavoj. Nun ke ni havas niajn paro de klavoj, ni rigardu kiel ni povas ĉifri kaj malĉifri mesaĝon. Mi volas sendi mesaĝon al Rob, do li estos por generi ĉi ŝlosila paro. Do mi petos al Rob por lia publika ŝlosilo, kiun mi uzas por kodi mesaĝon por sendi al li. Memoru, estas tute bone por Rob dividi sian publikan ŝlosilon kun mi. Sed tio ne estus bone por dividi lia privata ŝlosilo. Mi ne havas ajnan ideon kion lia privata ŝlosilo estas. Ni povas rompi nian mesaĝon m supren en pluraj pecoj ĉiuj malgrandaj ol n kaj tiam ĉifri ĉiu de tiuj pecoj. Ni ĉifri la kordo CS50, kiun ni povas rompi en 4 pecoj, unu po litero. Por kodi mia mesaĝo, mi devas konverti ĝin en ia nombra prezento. Ni concatenate la ASCII valoroj kun la gravuloj en mia mesaĝo. Por kodi donita mesaĝo m Mi bezonos komputi c = m al la e (mod n). Sed m ​​devas esti pli malgranda ol n, alie la plenan mesaĝon ne povas esti esprimita module n. Ni povas rompi m supren en pluraj pecoj, ĉiuj el kiuj estas pli malgrandaj ol n, kaj ĉifri ĉiu de tiuj pecoj. Encrypting ĉiu el tiuj pecoj, ni preni c1 = 67 al la 5 (mod 989) kio = 658. Por nia dua bloko ni havas 83 al la 5 (mod 989) kio = 15. Por nia tria bloko ni havas 53 al la 5 (mod 989) kio = 799. Kaj fine, por nia lasta bloko ni havas 48 al la 5 (mod 989) kio = 975. Nun ni povas sendi super tiuj koditaj valoroj al Rob. Ĉi tie vi iros, Rob. Dum nia mesaĝo estas en flugo, ni prenu alian rigardon ĉe kio ni akiris tiun valoron por d. Nia nombro d bezonataj por satigi 5d = 1 (mod 924). Tio igas d la multiplika inverso de 5 module 924. Donita 2 entjeroj a kaj b, la etendita Eŭklida algoritmo povas esti uzata por trovi la plej granda komuna divizoro de tiuj 2 entjeroj. Ĝi ankaŭ donas al ni 2 aliaj nombroj, x kaj y, kiuj kontentigas la ekvacion ax + by = la plej granda komuna divizoro de a kaj b. Kiel tiu ĉi helpi nin? Nu, ŝtopanta en e = 5 por kaj m = 924 por b ni jam scias ke ĉi tiuj nombroj estas interprimoj. Ilia plej granda komuna divizoro estas 1. Ĉi tiu donas ni 5x + 924y = 1 aŭ 5x = 1 - 924y. Sed se ni nur zorgas pri ĉio module 924 tiam ni povas faligi la - 924y. Pensu reen al la horloĝo. Se la minuto mano estas la 1 kaj poste ĝuste 10 horoj pasas, ni konas la minuto mano estos ankoraŭ esti sur la 1. Ĉi tie ni starti je 1 kaj tiam envolver ĉirkaŭ ĝuste y tempoj, do ni ankoraŭ esti je 1. Ni havas 5x = 1 (mod 924). Kaj tie ĉi x estas la sama kiel la d ni serĉas antaŭe, do se ni uzas la etendita Eŭklida algoritmo atingi tiun nombro x, jen la nombro ni devus uzi kiel nia d. Nun ni kuras la etendita Eŭklida algoritmo por a = 5 kaj b = 924. Ni uzu metodon nomata tablo metodo. Nia tablo havos 4 kolumnoj, x, y, d, kaj k. Nia tablo dividu kun 2 vicoj. En la unua vico ni havas 1, 0, tiam nia valoro de, kiu estas 5, kaj nia dua vico estas 0, 1, kaj nia valoro por b, kiu estas 924. La valoro de la 4a kolumno, k, estos la rezulto la dividadon de la valoro de d en la vico super ĝi kun la valoro de d en la sama vico. Ni havas 5 dividite per 924 estas 0 kun iu restaĵo. Tio signifas ke ni havas k = 0. Nun la valoro de ĉiu alia ĉelo estos la valoro de la ĉelo 2 vicojn super ĝi minus la valoro de la vico super ĝi tempoj k. Ni komencu per d en la 3a linio. Ni havas 5 - 924 * 0 = 5. Ni tuj havi 0 - 1 * 0 kio estas 0 kaj 1 - 0 * 0 kiu estas 1. Ne tro malbona, do ni movi al la venonta vico. Unue ni bezonas nian valoron de k. 924 dividite per 5 = 184 kun iuj resto, tial nia valoro por k estas 184. Nun 924 - 5 * 184 = 4. 1 - 0 * 184 estas 1 kaj 0 - 1 * 184 estas -184. Bone, ni do la sekva vico. Nia valoro de k estos 1 ĉar 5 dividita per 4 = 1 kun iuj ceteraj. Ni plenigu la aliaj kolumnoj. 5 - 4 * 1 = 1. 0 - 1 * 1 = -1. Kaj 1 - 184 * 1 estas 185. Ni vidu kion nia venonta valoro de k estus. Nu, tio aspektas kiel ni havas 4 dividite per 1, kiu estas 4. En ĉi tiu kazo kie ni dividanta per 1 tia ke k estas egala al la valoro de d en la supra vico signifas ke ni faris kun niaj algoritmo. Ni povas vidi ĉi tie ke ni havi x = 185 kaj y = -1 en la lasta vico. Ni nun revenu al nia originala celo. Ni diris, ke la valoro de x kiel rezulto de kuri ĉi tiu algoritmo estus la multiplika inverso de a (mod b). Tio signifas ke 185 estas la multiplika inverso de 5 (mod 924) kio signifas, ke ni havas valoro de 185 por d. La fakto ke d = 1 en la lasta vico kontrolu ke TTT estis interprimo al m. Se ne estus 1 tiam ni devus elekti novan kaj. Nun ni vidu se Rob ricevis mian mesagxon. Kiam iu sendas al mi ĉifrita mesaĝo tiel longe, kiel mi observis mian privata ŝlosilo sekreta Mi estas la sola kiu povas deĉifri la mesaĝon. Por malĉifri eron c mi povas kalkuli la originala mesaĝo estas egala al la bloko al d povo (mod n). Memoru ke d kaj n estas el mia privata ŝlosilo. Por ricevi plenan mesaĝon de lia pecoj ni malĉifri ĉiu bloko kaj concatenate la rezultojn. Ĝuste kiel sekura estas RSA? La vero estas, ni ne scias. Sekureco estas bazita sur kiom longe necesus atacante por fendi mesaĝon kodita kun RSA. Memoru ke atakanto havas aliron al via publika ŝlosilo, kiu enhavas ambaŭ e kaj n. Se la atakanto sukcesas faktoro n enen ĝia 2 primoj, p kaj q, tiam ŝi povus kalkuli d uzanta la etendita Eŭklida algoritmo. Tio donas al ŝi la privata ŝlosilo, kiun oni povas uzi por deĉifri ajna mesaĝo. Sed kiel rapide oni povas faktorigi entjeroj? Denove, ni ne scias. Neniu trovita rapida maniero fari ĝin, kio signifas ke donita sufiĉe granda n necesus atacante unrealistically longa al faktorigi la nombron. Se iu malkaŝis rapida vojo de faktoranta entjeroj RSA estus rompita. Sed eĉ se entjera faktorigo estas propre malrapida la RSA algoritmo povus ankoraŭ havas iujn difekto en ĝi kiu permesas por facila malĉifro de mesaĝoj. Neniu trovita kaj malkaŝis tian difekton tamen, sed tio ne signifas unu ne ekzistas. En teorio, iu povus tie legi cxiujn datumoj kodita kun RSA. Ekzistas alia iom de privacidad temo. Se Tommy encrypts iuj mesaĝon per mia publika ŝlosilo kaj atakanto encrypts la saman mesaĝon per mia publika ŝlosilo la atakanto vidos ke la 2 mesaĝoj identa kaj tiel scii kion Tommy ĉifrita. Por malhelpi tion, mesaĝoj estas tipe vatitaj kun hazarda bitoj antaŭ esti ĉifrita por ke la sama mesaĝo ĉifrita plurfoje aspektos malsamaj dum la Plenigado sur la mesaĝo estas malsama. Sed memoru kiom ni devas dividi mesaĝojn en pecoj tiel ke ĉiu bloko estas pli malgranda ol n? Plenigado la pecoj signifas ke ni devas dividi aĵojn en ankoraŭ pli pecojn de la vatita chunk devas esti pli malgranda ol n. Ĉifrado kaj malĉifro estas relative multekostaj kun RSA, kaj tiel bezoni por rompi mesaĝon en multajn pecojn eblas tre peniga. Se granda volumo de datumoj bezonas esti kodita kaj deĉifrita ni povas kombini la profitoj de simetria ŝlosilo algoritmoj kun tiuj de RSA akiri ambaŭ sekureco kaj efikeco. Kvankam ni ne iros en ĝin ĉi tie, AES estas simetria ŝlosilo algoritmo kiel la Vigenère kaj Cezaro ĉifroj sed multe pli malfacila por fendi. Kompreneble, ni ne povas uzi AES sen establi dividita sekreta ŝlosilo inter la 2 sistemoj, kaj ni vidis la problemon kun tiu antaŭe. Sed nun ni povas uzi RSA por establi la dividita sekreta ŝlosilo inter la 2 sistemoj. Ni vokos la komputilo sendas la informon de la sendinto kaj la komputilo ricevis la datumojn de la ricevilo. La ricevilo havas RSA ŝlosilo paro kaj sendas la publika ŝlosilo al la sendinto. La sendinto generas AES ŝlosilo, encrypts ĝin kun la ricevilo de RSA publikan ŝlosilon, kaj sendas la AES ŝlosilo al la ricevilo. La ricevilo decrypts la mesaĝon kun lia RSA privata ŝlosilo. Tiel la sendinto kaj la ricevilo havas nun dividita AES ŝlosilo inter ili. AES, kiu estas multe pli rapida, je ĉifrado kaj malĉifro ol RSA, povas nun esti uzata por kodi la grandaj volumoj de datumoj kaj sendi ilin al la ricevilo, kiu povas deĉifri uzante la saman ŝlosilon. AES, kiu estas multe pli rapida, je ĉifrado kaj malĉifro ol RSA, povas nun esti uzata por kodi la grandaj volumoj de datumoj kaj sendi ilin al la ricevilo, kiu povas deĉifri uzante la saman ŝlosilon. Ni nur bezonas RSA kopii la dividis ŝlosilo. Ni ne plu bezonas uzi RSA ajn. Ĝi aspektas kiel Mi havas mesaĝon. Ne gravas se iu legas kio estas sur la papero aviadilo antaux mi kaptis ĝin ĉar mi estas la sola kun la privata ŝlosilo. Ni deĉifri ĉiu el la pecoj en la mesaĝo. La unua bloko, 658, ni levas al la d potencon, kiu estas 185, mod n, kiu estas 989, egalas al 67, kiu estas la litero C en ASCII. Nun, sur la dua bloko. La dua bloko havas valoro 15, kiuj ni supreniri la 185th potenco, mod 989, kaj ĉi tiu estas egala al 83 kiu estas la litero S en ASCII. Nun por la tria bloko, kiu havas valoro 799, ni levas al 185, mod 989, kaj ĉi tiu estas egala al 53, kiu estas la valoro de la karaktero 5 en ASCII. Nun por la lasta bloko, kiu havas valoro 975, ni supreniri 185, mod 989, kaj ĉi tiu estas egala al 48, kio estas valoro de la karaktero 0 en ASCII. Mia nomo estas Rob Bowden, kaj ĉi tiu estas CS50. [CS50.TV] RSA ajn. RSA ajn. [Ridado] Tute ne.