[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvardo universiteto]
[Tai CS50.] [CS50.TV]
Paimkime RSA, plačiai naudojama duomenų šifravimo algoritmas atrodo.
Šifravimo algoritmai, kaip Cezaris ir Vigenere šifrai yra nelabai saugi.
Su Cezario šifras, užpuolikas tik reikia išbandyti 25 skirtingų kodų
gauti Message paprastą tekstą.
Nors Vigenere šifras yra saugesnis nei Cezario šifras
dėl didesnių paieškos vietos raktams, kai užpuolikas
žino į Vigenere šifravimo rakto ilgį,
tai galima nustatyti per saugiame teksto analizės modelius,
Vigenere šifras yra ne tai, kad daug saugesnis nei Cezario šifras.
RSA, kita vertus, nėra pažeidžiama atakų, kaip šis.
Cezario šifras ir Vigenere šifras naudoti tą patį klavišą
užšifruoti ir iššifruoti pranešimų.
Ši savybė leidžia šias šifrai simetriškai pagrindinius algoritmus.
Pagrindinė problema, su simetrinių pagrindinių algoritmų
yra tai, kad jie remiasi šifravimo ir siunčia pranešimą
ir vienas, priėmimo ir iškodavimo pranešimą
jau susitarė iš anksto, ant klavišo jie abu naudoti.
Bet mes turime šiek tiek paleisties problemos čia.
Kaip 2 kompiuteriai, kurie nori bendrauti nustatyti slaptą raktą tarp jų?
Jei raktas turi būti paslaptis, tada mes turime būdą, užšifruoti ir iššifruoti raktą.
Jei viskas, ką turime, yra simetriška rakto kriptografija
tada mes tiesiog grįžti į tą pačią problemą.
RSA, kita vertus, naudoja raktų porą,
viena, kai šifravimui ir kito iššifravimo.
Vienas yra vadinamas viešasis raktas, o kitas privatus raktas.
Viešasis raktas naudojamas šifruoti laiškus.
Kaip jūs galite atspėti jo pavadinimo, mes galime pasidalinti savo viešąjį raktą su
kiekvienas norime nepakenkiant laiškas užšifruotas saugumą.
Pranešimai šifruojami naudojant viešąjį raktą
gali būti iššifruoti su savo atitinkamas privataus rakto.
Nors galite pasidalinti savo viešą raktą, jūs visada turėtų išlaikyti savo asmeninio rakto paslaptis.
ir tik privatus raktas gali būti naudojamas iššifruoti pranešimų
jei norite siųsti pranešimus, saugiame su RSA 2 vartotojai
pirmyn ir atgal, abu vartotojai turi turėti savo viešojo ir privataus raktų porą.
Pranešimai user 1 2 Vartotojo
naudoti tik Vartotojas 2 raktų porą ir pranešimus nuo 1 vartotojui 2 Vartotojo
naudoti tik user 1 raktų porą.
Faktas, kad yra 2 atskiri raktai, užšifruoti ir iššifruoti messages
daro RSA asimetrinis rakto algoritmas.
Mums nereikia šifruoti viešąjį raktą, kad būtų galima siųsti į kitą kompiuterį
nes svarbiausia yra viešas vistiek.
Tai reiškia, kad "RSA neturi tą patį paleisties problemą
Simetrinių pagrindinių algoritmų.
Taigi, jei aš noriu, kad siųsti žinutę naudojant RSA šifravimo
apiplėšti, aš pirmiausia reikia Rob viešą raktą.
Norėdami generuoti raktų porą, Rob reikia pasirinkti 2 dideli paprastų skaičių.
Šie skaičiai bus naudojamas tiek viešojo ir privataus raktų,
o viešasis raktas bus panaudoti tik 2 numeriai produktą,
ne patys skaičiai.
Kai aš užšifruoti pranešimą, naudojant Rob viešąjį raktą
Galiu siųsti pranešimą Rob.
Už kompiuterį, faktoringo numeriai yra sudėtingas uždavinys.
Viešasis raktas, atminkite, 2 paprastais skaičiais produktą.
Šis produktas turi turėti tik 2 veiksnius,
, kurie atsitiktų būti skaičiai, kurie sudaro privatų raktą.
Kad iššifruoti laiško, RSA naudoti šį privatų raktą
arba skaičiai dauginama kartu kuriant viešąjį raktą.
, Nes jis skaičiavimais sunku veiksnys numerį
naudojamas viešojo rakto į 2 numerių, naudojamų privataus rakto
sunku užpuolikas privatų raktą, išsiaiškinti,
kad reikės iššifruoti laiško.
Dabar eikime į kai žemesnio lygio informacijos apie RSA.
Pirmiausia pažiūrėkime, kaip mes galime sukurti raktų porą.
Pirma, mums reikia 2 paprastų skaičių.
Mes paskambinsime šių 2 numeriai P ir Q.
Siekiant gauti P ir Q, praktikoje mes pseudorandomly generuoti
daug ir tada naudokite kriterijų, skirtą nustatyti, ar
šie skaičiai yra turbūt svarbiausias.
Mes galime išlaikyti generuoti atsitiktinius numerius vėl ir vėl
kol mes turime 2 primes, kad mes galime naudoti.
Čia leiskite pasirinkti p = 23 ir Q = 43.
Atminkite, kad praktikoje, p ir q turi būti daug didesni skaičiai.
Kiek mes žinome, tuo didesnis skaičių, tuo sunkiau
nulaužti šifruotą pranešimą.
Bet jis taip pat brangesnis užšifruoti ir iššifruoti pranešimų.
Šiandien tai dažnai rekomenduojama, kad p ir q yra bent 1024 bitų,
kuris nurodo kiekvieno numerio ne daugiau kaip 300 ženklų po kablelio.
Bet mes pasirinkti šiuos mažus skaičius šiame pavyzdyje.
Dabar mes daugintis P ir Q gauti 3rd numerį,
kuriuos mes vadiname n.
Mūsų atveju, n = 23 * 43 = 989.
Mes n = 989.
Kitas mes daugintis su q p - 1 - 1
gauti 4. skaičių, kurį mes vadiname m.
Mūsų atveju m = 22 * ​​42 = 924.
Mes turime M = 924.
Dabar mums reikia, kad yra gana pagrindinis numeris El m
ir mažiau nei m.
Du skaičiai yra gana pagrindinis arba tarpusavyje paprastųjų
jei tik teigiamas sveikasis skaičius, kad dalybos juos abu tolygiai yra 1.
Kitaip tariant, didžiausias bendras daliklis e ir m
turi būti 1.
Iš tikrųjų, tai dažnai e būti pirminis skaičius 65.537
tol, kol tai neįvyks būti M faktorius.
Mūsų raktus, mes pasiimti e = 5
yra gana pagrindinis nuo 5 iki 924.
Galiausiai, mes jums reikia dar vieną numerį, kurį mes vadiname d.
D turi būti kai vertė, kuri atitinka lygtį = 1 (mod m).
Šis mod m reiškia, mes naudoti kažką vadinama modulinė aritmetinis.
Modulinės aritmetinis, kai skaičius tampa didesnis, nei kai viršutinė riba
jis bus užbaigtas apie 0.
Laikrodis, pavyzdžiui, naudoja modulinę aritmetiką.
Viena minutė po 1:59, pavyzdžiui, 2:00,
ne 1:60.
Minučių ranka apvynioti aplink 0
sulaukę viršutinė riba 60.
Taigi, mes galime pasakyti, 60 yra lygus 0 (mod 60)
ir 125 yra lygiavertis 65 atitinka 5 (mod 60).
Mūsų viešasis raktas bus pora e ir n
kur šiuo atveju e yra 5 ir n yra 989.
Mūsų privatus raktas bus pora d ir n,
kuri mūsų atveju yra 185 ir 989.
Atkreipkite dėmesį, kad mūsų originalus paprastų p ir q neatrodo
bet mūsų privačių ar viešųjų raktų.
Dabar, mes turime savo raktų porą, galime pažvelgti kaip mes galime užšifruoti išvaizdą
ir iššifruoti žinutę.
Noriu siųsti žinutę Rob,
, kad jis bus vienas generuojame šį raktų porą.
Tada aš paklausti Rob savo viešąjį raktą, kurį aš naudoti
užšifruoti žinutę siųsti jam.
Atminkite, kad tai yra visiškai gerai, Rob pasidalinti savo viešąjį raktą su manimi.
Bet tai nebūtų gerai pasidalinti savo privatų raktą.
Aš neturiu jokio supratimo, ką jo privatus raktas yra.
Mes galime sulaužyti mūsų žinia m į kelis gabaliukus
visi mažesnis nei n ir tada užšifruoti kiekvienas iš šių gabaliukus.
Mes užšifruoti eilutę CS50, kuriuos mes galime išeiti į 4 gabaliukus,
vieną kiekvienai raidei.
Tam, kad užkoduoti mano pranešimą, aš reikia ją konvertuoti į
kažkoks Skaitinė atstovavimas.
Leiskite Jungiant su savo pranešimo simbolių ASCII reikšmes.
Tam, kad užkoduoti tam tikrą pranešimą m
Man reikės apskaičiuoti C = M e (mod n).
Bet m, turi būti mažesnės nei n,
ar kitur visą pranešimas negali būti išreikštas pagal modulis n.
Mes galime sulaužyti m iki į kelis gabaliukus, visi, kurie yra mažesni nei n
ir šifruoti kiekvieną iš šių gabaliukus.
Šifravimo kiekvieną iš šių gabaliukus, kurią mes gauname c1 5 67 = (mod 989)
= 658.
Mūsų antra riekė nuo 83 iki 5 (mod 989)
= 15.
Mūsų trečiosios riekė nuo 53 iki 5 (mod 989)
= 799.
Ir, pagaliau, mūsų paskutinio riekė mes turime nuo 48 iki 5 (mod 989)
kuris = 975.
Dabar mes galime išsiųsti per šiuos saugiame vertybes Rob.
Čia jūs einate, Rob.
Nors mūsų žinia skrydžio metu, tegul kitą išvaizdą
, kaip mes turime, kad D vertę.
Mūsų numeris d reikia patenkinti 5D = 1 (mod 924).
Tai daro d Multiplikacinis atvirkštinis 924 5 modulį.
Atsižvelgiant į 2 sveikieji skaičiai a ir b pratęstas Euklido algoritmas
gali būti naudojama ir siekiant rasti 2 sveikųjų skaičių didžiausias bendras daliklis.
Jis taip pat suteiks mums 2 kiti numeriai, X ir Y,
kurios atitinka lygtis ax + = didžiausias bendras daliklis A ir B.
Kaip tai gali mums padėti?
Na, kaiščiais e = 5
m = 924 b
mes jau žinome, kad šie skaičiai yra tarpusavyje paprastųjų.
Jų didžiausias bendras daliklis yra 1.
Tai suteikia mums 5x + 924y = 1
arba 5x = 1 - 924y.
Bet jei mes tik rūpintis apie viską modulį 924
tada mes galime lašas - 924y.
Pagalvokite atgal į laikrodį.
Jei yra 1 minutę ranka ir tada lygiai 10 valandoms,
mes žinome, minutę ranka vis dar bus ant 1.
Čia mes pradedame 1 ir tada wrap aplink tiksliai y kartus,
todėl mes vis dar gali būti "1".
Mes turime 5x = 1 (mod 924).
Čia x yra tas pats kaip mes ieškojome prieš d,
todėl, jei mes naudojame pratęstas Euklido algoritmas
gauti šią numeris X, tai numeris, kurį reikia naudoti, nes mūsų d.
Dabar galime paleisti pratęstas Euklido algoritmas = 5
ir b = 924.
Mes naudojame metodą, vadinamą lentelės metodas.
Mūsų lentelė turės 4 stulpelius, x, y, d ir k.
Mūsų stalas prasideda su 2 eilučių.
Pirmoje eilutėje turime 1, 0, tada mūsų vertė, kuri yra 5,
ir mūsų antra eilutė yra 0, 1, ir mūsų vertė b, kuris yra 924.
4-ame stulpelyje, K, vertė bus rezultatas
D reikšmę dalijant D reikšmę virš jo eilės
toje pačioje eilutėje.
Mes turime 5, padalytas iš 924 yra 0 su tam tikru likusios.
Tai reiškia, kad turime k = 0.
Dabar kiekvieno kito elemento reikšmė bus 2 ląstelių eilių virš jo vertė
atėmus eilutėje virš datos k vertę.
Pradėkime d 3 eilutėje.
Mes turime 5 - 924 * 0 = 5.
Toliau mes turite 0 - 1 * 0 yra 0
ir 1 - 0 * 0 1.
Nėra labai blogai, todėl galime pereiti į kitą eilutę.
Pirmiausia mes turime mūsų vertę k.
924, padalytas iš 5 = 184, su kai kuriais likusiam
todėl mūsų k vertė yra 184.
Dabar 924-5 * 184 = 4.
1 - 0 * 184 yra 1 ir 0 - 1 * 184 yra -184.
Viskas gerai, darykime kitą eilutę.
Mūsų Koeficiento k vertė bus 1, nes
5, padalytas iš 4 = 1 su kai kurių likusių.
Tegul užpildyti kitų stulpelių.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
Ir 1-184 * 1 185.
Pažiūrėkime, ką būtų mūsų kitas Koeficiento k vertė.
Na, atrodo, kaip mes turime, 4, padalytas iš 1, kuris yra 4.
Šiuo atveju, kai mes dalijama iš 1 toks, kad k yra lygus
D vertė virš eilutės reiškia, kad mes su mūsų algoritmas.
Mes galime pamatyti, kad mes turime x = 185 ir y = -1 paskutinę eilutę.
Tegul dabar grįžti prie pradinio tikslo.
Mes sakėme, kad x vertė, nes dėl paleisti šį algoritmą
būtų Multiplikacinis atvirkštinis (mod b).
Tai reiškia, kad 185 yra didinamasis atvirkštinis 5 (mod 924)
, o tai reiškia, kad mes turime vertę 185 D.
Tai, kad d = 1 paskutine eilute
tikrina, kad e tarpusavyje paprastųjų iki m.
Jei tai buvo ne 1, tada mes turėtume pasirinkti naują el.
Dabar pažiūrėkime,, jei Rob gavo mano laišką.
Kai kas nors atsiunčia man šifruotą pranešimą
kaip ilgai, kaip aš išlaikė savo privatų raktą, paslaptį
Aš esu vienintelis, kuris gali iššifruoti pranešimą.
Iššifruoti riekė a galima apskaičiuoti pirminį pranešimą
yra lygus gautu D galia (mod n).
Atminkite, kad d ir n yra iš mano privataus rakto.
Gauti visą pranešimą iš savo gabaliukus iššifruoti kiekviena riekė
ir Jungiant rezultatus.
Tiksliai, kaip saugi yra RSA?
Tiesa yra tai, mes nežinome.
Saugumas yra pagrįstas, kiek laiko užtruktų užpuolikas nulaužti pranešimą
užšifruoti su RSA.
Atminkite, kad užpuolikas turi priėjimą prie savo viešąjį raktą,
kuri yra tiek E ir N.
Jei užpuolikas sugeba į jo 2 primes, P ir Q faktorius N,
tada ji galėtų apskaičiuoti ð naudodama pratęstas Euklido algoritmas.
Tai suteikia jai privatų raktą, kuris gali būti naudojamas iššifruoti bet kokį pranešimą.
Bet kaip greitai mes galime veiksnys sveikieji skaičiai?
Vėlgi, mes nežinome.
Niekas rado greitas būdas tai daryti,
o tai reiškia, kad skiriamas pakankamai didelis, n
ji imsis užpuolikas nerealiai ilgai
veiksnys numerį.
Jei kas nors paaiškėjo, greitas būdas faktoringo sveikaisiais skaičiais
RSA bus sulaužyta.
Bet net jei sveikasis skaičius Faktorizavimas iš esmės yra lėtas
RSA algoritmas gali dar šiek tiek trūkumas jame
kuri leidžia lengvai iššifravimas pranešimų.
Niekas rado ir atskleidė tokį trūkumas dar
bet tai nereiškia, kad jo nėra.
Teoriškai, nors galėtų būti ten skaityti visus duomenis užšifruoti su RSA.
Yra dar vienas šiek tiek privatumo klausimas.
Jei Tomas užšifruoja tam tikrą pranešimą naudodami savo viešąjį raktą
ir užpuolikas užšifruoja savo viešąjį raktą naudojant tą patį pranešimą
užpuolikas bus matyti, kad 2 pranešimai yra vienodi
ir taip žino, ką Tommy užšifruoti.
Siekiant užkirsti kelią, pranešimai paprastai kamšalu su atsitiktinių bitų
prieš užkoduojama taip, kad tas pats pranešimas šifruojamas
kelis kartus tol, kol atrodys kitaip, kaip pranešimo išklojimui skiriasi.
Bet prisiminti, kaip mes turime padalinti į gabaliukus pranešimus
taip, kad kiekviena riekė yra mažesnis nei n?
Prikimšti į gabaliukus reiškia, kad mes galime padalinti things up
į dar daugiau gabaliukus, nes kamšalu riekė turi būti mažesnis nei n.
Šifravimo ir dešifravimo yra gana brangus su RSA,
ir todėl reikia lūžti pranešimą į daugelį gabaliukus, gali būti labai brangus.
Jei didelės duomenų apimties turi būti šifruojamas ir iššifruoti
mes galime sujungti simetrinių pagrindinių algoritmų privalumus
su RSA gauti tiek saugumą ir efektyvumą.
Nors mes ne eiti į jį,
AES simetriškai rakto algoritmas kaip Vigenere ir Caesar šifrai
bet daug sunkiau nulaužti.
Žinoma, mes negalime naudoti AES be įtvirtinant bendrą slaptą raktą
tarp 2 sistemų, ir mes matėme su šia problema anksčiau.
Bet dabar mes galime naudoti RSA nustatyti bendrą slaptą raktą tarp 2 sistemų.
Mes paskambinsime kompiuterį Siunčiant duomenis siuntėją
ir kompiuteris duomenis gaunanti imtuvą.
Imtuvas turi RSA raktų porą ir siunčia
viešojo rakto gavėjui.
Siuntėjas sukuria AES raktą,
šifravimas su gavėjo RSA viešojo rakto,
ir siunčia AES raktą į imtuvą.
Imtuvas iššifruoja pranešimą su RSA raktas.
Tiek siuntėjas, ir gavėjas dabar turi bendrą AES raktą tarp jų.
AES, kuri yra daug greičiau šifravimui ir iššifravimui nei RSA,
dabar gali būti naudojama užšifruoti didelius duomenų kiekius ir siųsti juos į imtuvą,
kas gali iššifruoti naudojant tą patį raktą.
AES, kuri yra daug greičiau šifravimui ir iššifravimui nei RSA,
dabar gali būti naudojama užšifruoti didelius duomenų kiekius ir siųsti juos į imtuvą,
kas gali iššifruoti naudojant tą patį raktą.
Mes tiesiog reikia RSA perkelti rakto.
Mums nebereikia naudoti RSA ne visi.
Atrodo, kad aš gavo pranešimą.
Nesvarbu, jei kas nors perskaityti, kas ant popieriaus lėktuvo, kol aš sugauti jį
nes aš tik vienas su privataus rakto.
Leiskite iššifruoti kiekvienas pranešimo gabaliukus.
Pirmasis riekė, 658, mes keliame D galia, kuri yra 185,
mod n, kuris yra 989, yra lygus 67,
kuri yra įrašyta raidė C, ASCII.
Dabar į antrąjį riekė.
Antrasis riekė turi vertę 15,
, kuriuos mes keliame 185. galios,
mod 989, ir tai yra lygus 83
kuris yra raidė S ASCII.
Dabar trečią riekė, kuri turi vertę 799, mes keliame 185
mod 989, ir tai yra lygus 53,
kuris yra charakterio vertė ASCII 5.
Dabar už paskutinį gabalą, kuriame yra reikšmė, 975,
mes keliame iki 185, mod 989
ir ji yra lygi 48, kuris vertė 0 ASCII simbolių.
My name is Rob Bowden, ir tai yra CS50.
[CS50.TV]
RSA ne visi.
RSA ne visi. [Juokas]
Ne visiems.