[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.
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.