[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvardi Ülikool]
[See on CS50.] [CS50.TV]
Võtame pilk RSA, kasutatakse laialdaselt algoritmi andmete krüpteerimiseks.
Krüpteerimisalgoritmid nagu Caesar ja Vigenère ciphers ei ole väga turvaline.
Mis Caesar salakiri, ründaja peab ainult proovida 25 erinevat võtmed
saada sõnumi lihttekstina.
Kuigi Vigenère salakiri on turvalisem kui Caesar salakiri
sest suurem otsing ruumi võtmed, kui ründaja
teab võtme pikkus on Vigenère salakiri,
mida saab kindlaks analüüsi teel mustrid krüpteeritud teksti,
Vigenère salakiri ei ole, et palju turvalisem kui Caesar salakiri.
RSA, teiselt poolt, ei ole haavatavaks niimoodi.
Caesar salakiri ja Vigenère salakiri kasutada sama võtit
nii krüpteerimiseks ja dekrüpteerimiseks sõnum.
See majutusasutus muudab need ciphers sümmeetriline võti algoritme.
Põhiprobleem sümmeetriline võti algoritme
on see, et need tuginevad ühelt krüptimine ja sõnumi saatmist
ja ühe vastuvõtva ja dekrüpteerimiseks sõnum
et juba kokkulepitud kohe algul peamiste nad mõlemad kasutavad.
Aga meil on natuke käivitamisel probleem siin.
Kuidas 2 arvutit, et tahavad suhelda luua salajane võti nende vahel?
Kui võti peab olema salajane, siis peame viis krüpteerimiseks ja dekrüpteerimiseks võti.
Kui kõik meil on sümmeetriline võtme krüptograafia
siis tuleme just tagasi sama probleem.
RSA, teiselt poolt, kasutab võtmepaari,
üks krüpteerimist ja teine ​​dekodeerimiseks.
Üks on nn avaliku võtme, ja teine ​​on isiklik võti.
Avalikku võtit kasutatakse sõnumite krüptimiseks.
Nagu te võite arvata, mida tema nimi, saame jagada oma avaliku võtme
keegi tahame ohustamata turvalisust krüpteeritud sõnum.
Sõnumid krüpteeritakse, kasutades avaliku võtme
saab lahti krüptida ja sellele vastava isikliku võtme.
Kuigi saate jagada oma avaliku võtme, siis tuleb alati hoida oma isikliku võtme saladus.
ja ainult isikliku võtmega saab kasutada dekrüpteerimiseks sõnumeid
kui 2 inimest tahavad sõnumeid saata krüptitud RSA
edasi ja tagasi nii kasutajad peavad olema oma avaliku ja erasektori võtmepaari.
Sõnumid kasutajaks 1 kasutajaks 2
kasutada ainult kasutaja 2'e võtmepaari ja sõnumeid kasutaja 2. kasutajaks 1
kasutada ainult kasutajaks 1 aasta võtmepaari.
Asjaolu, et on olemas 2 eraldi võtmeid krüpteerimiseks ja dekrüpteerimiseks sõnumeid
teeb RSA asümmeetrilise võtme.
Me ei vaja krüptida avaliku võtme, et saata see teise arvutisse
kuna võti on avalik niikuinii.
See tähendab, et RSA ei ole sama käivitus probleem
nagu sümmeetriline võti algoritme.
Nii et kui ma tahan saata sõnum kasutades RSA krüpteerimisega
Rob, ma kõigepealt Rob avaliku võtme.
Et tekitada võtmepaari, Rob vaja valida 2 suurt algarvu.
Need arvud kasutada nii avaliku ja erasektori võtmed,
kuid avalik võti on ainult toodet kasutada neid 2 numbrit,
ei numbrid ise.
Kui olen krüpteeritud sõnumi Rob avaliku võtme
Võin saata kiri Rob.
Sest arvuti, faktooring numbrid on raske probleem.
Avalik võti, mäletan, kasutatud toodet 2 algarvud.
See toode peab siis olema ainult 2 tegureid,
mis juhtub olema numbrid, mis moodustavad isiklik võti.
Et lahti krüptida, RSA kasutab seda isikliku võtme
või numbrid korrutatakse koos loomise protsessis avaliku võtme.
Sest see on arvutuslikult raske tegur arv
kasutatakse avaliku võtme 2 numbrit kasutatakse isikliku võtme
see on raske ründaja välja mõelda isikliku võtme
et on vaja lahti krüptida.
Lähme nüüd mõnda madalamal tasemel üksikasjad RSA.
Vaatame kõigepealt, kuidas me saame luua võtmepaari.
Esiteks, me peame 2 algarvud.
Me kutsume neid 2 numbrit p ja q.
Et valida p ja q, tegelikkuses me pseudorandomly tekitada
suured numbrid ja siis kasuta selle kindlakstegemine, kas
need numbrid on ilmselt peamine.
Saame hoida teeniva juhuslikke numbreid ikka ja jälle
kuni meil on 2 PRIMES, et saame kasutada.
Siin olgem valida p = 23 ja q = 43.
Pea meeles, et praktikas p ja q olema palju suuremad numbrid.
Niipalju kui me teame, et mida suurem number, seda raskem on
crack krüpteeritud sõnum.
Aga see on ka kallim krüpteerimiseks ja dekrüpteerimiseks sõnumeid.
Täna on sageli soovitatakse, et p ja q on vähemalt 1024 bitti,
mis paneb iga arv üle 300 murdarvud.
Aga me tuleme väikest arvu Selle näite.
Nüüd me korrutame p ja q kokku saada 3. number,
mis me kutsume n.
Meie puhul n = 23 * 43, mis = 989.
Oleme n = 989.
Järgmine me korrutame lk - 1, kus q - 1
saada 4. arv, mis me kutsume m.
Meie puhul m = 22 * ​​42, mis = 924.
Meil on m = 924.
Nüüd vajame arv e, mis on suhteliselt peaminister, et m
ja vähem kui m.
Kaks numbrid on suhteliselt peaministri või coprime
kui ainult positiivne täisarv, mis jagub neid nii ühtlaselt on 1.
Teisisõnu, suurim ühistegur e-ja m
peab olema 1.
Praktikas on tavaline, e olla algarv 65537
nii kaua, kui see arv ei juhtu olema tegur m.
Sest meie võtmed, me tuleme e = 5
alates 5 on suhteliselt peaministri kuni 924.
Lõpuks me vajame veel üks number, mis me kutsume d.
D Peab olema mingi väärtus, mis rahuldab võrrandit de = 1 (mod m).
See mod m tähendab me kasutame midagi, mida nimetatakse modulaarne aritmeetika.
Aasta modulaarne aritmeetika, kui number on kõrgem kui mõned ülemise
see murrab tagasi umbes 0-ga.
Kell, näiteks kasutab modulaarne aritmeetika.
Üks minut pärast 01:59 Näiteks on 2:00,
ei 1:60.
Minut käsi on pakitud ümber kuni 0
jõudmisel ülemise 60.
Nii võime öelda 60 on võrdne 0 (mod 60)
ja 125 on võrdub 65 vastab 5 (mod 60).
Meie avalik võti on paar e ja n
kus antud juhul e on 5 ja n on 989.
Meie isiklik võti on paar d ja n
mis meie puhul on 185 ja 989.
Pange tähele, et meie algne PRIMES p ja q ei kuvata
kõikjal meie era-või avalikke võtmeid.
Nüüd, kui oleme meie võtmepaari, võtame pilk kuidas me saame krüptida
ja dekrüpteerimiseks sõnum.
Ma tahan saata kiri Rob,
nii et ta saab ühe luua selle võtmepaari.
Siis ma küsin Rob tema avalik võti, mis ma kasutan
krüpteerimiseks sõnum saata talle.
Pea meeles, et see on täiesti okei Rob jagada oma avaliku võtme minuga.
Aga see ei oleks okei jagada oma isiklikku võtit.
Mul ei ole aimu, mida tema isiklik võti on.
Saame murda oma sõnum m mitmeks tükkideks
kõik väiksemad n ja seejärel krüptimiseks kõik need tükkideks.
Me krüptida string CS50, mida me ei lahku arvesse 4 tükkideks,
üks täht.
Selleks, et varjata oma sõnum, mul on vaja muuta selle
mingi arvuna.
Olgem concatenate ASCII väärtused tegelased minu sõnum.
Selleks, et varjata antud sõnum m
Ma vajan arvutada c = m e (mod n).
Aga m peab olema väiksem kui n,
või siis kogu sõnum ei saa väljendada mooduli n.
Me ei saa murda m mitmeks tükkideks, mis kõik on väiksemad kui N,
ja krüptida kõik need tükkideks.
Encrypting kõik need tükkideks, saame c1 = 67 kuni 5 (mod 989)
mis = 658.
Sest meie teine ​​patakas on meil 83 5 (mod 989)
mis = 15.
Sest meie kolmas patakas on meil 53 kuni 5 (mod 989)
mis = 799.
Ja lõpuks, meie viimane patakas on meil 48 kuni 5 (mod 989)
mis = 975.
Nüüd on võimalik saata üle need krüpteeritud väärtused Rob.
Ole lahke, Rob.
Kuigi meie sõnum on lennus, võtame teise ilme
kuidas me saime selle raha d.
Meie number d täitmiseks vajalikke 5D = 1 (mod 924).
See muudab d multiplikatiivses vastupidine 5 mooduli 924.
Manustatakse 2 täisarvud a ja b, laiendatud Eukleidese algoritm
saab leida suurim ühistegur neist 2 täisarvud.
Samuti annab meile 2 teised numbrid, x ja y,
mis rahuldavad võrrandit ax + by = suurim ühistegur ja b.
Kuidas see meid aitab?
Noh, ühendades e = 5
ja m = 924 B
me juba teame, et need numbrid on coprime.
Nende suurim ühistegur on 1.
See annab meile 5x + 924y = 1
või 5x = 1 - 924y.
Aga kui me ainult hoolid kõik modulo 924
siis saame tilk - 924y.
Mõtle tagasi kella.
Kui minut käsi on 1. ja siis täpselt 10 tundi edasi,
me teame minut käsi ikkagi edasi 1.
Siin me stardivad 1 ja seejärel murtakse täpselt y korda,
nii me jääme ikka kell 1.
Meil on 5x = 1 (mod 924).
Ja siin see x on sama mis d otsisime enne,
nii et kui me kasutada laiendatud Eukleidese algoritm
saada see arv x, et see number peaksime kasutama meie d.
Nüüd lähme jooksma laiendatud Eukleidese algoritm = 5
ja b = 924.
Me kasutame meetodit nimetatakse tabelit meetod.
Meie tabel on 4 veergu, x, y, d ja k.
Meie laud hakkab liikuma 2 rida.
Esimeses reas on meil 1, 0, siis meie väärtus, mis on 5,
ja meie teine ​​rida on 0, 1, ja meie raha b, mis on 924.
Väärtus 4. veerus, k, saab tulemuse
jagamise väärtust d reas selle kohal väärtusega d
samas reas.
Meil on 5 jagatuna 924 on 0. mõned ülejäänud.
See tähendab, et meil on k = 0.
Nüüd väärtuse iga teine ​​lahter on väärtus lahtris 2 rida kõrgemal
miinus väärtus rida eespool see korda k.
Alustame d 3. rida.
Meil on 5-924 * 0 = 5.
Järgmine on meil 0-1 * 0, mis on 0.
ja 1 - 0 * 0 mis on 1.
Mitte liiga halb, et liigume edasi järgmisele reale.
Esiteks peame meie k väärtus.
924 jagatud 5 = 184 mõned ülejäänud,
nii meie raha k on 184.
Nüüd 924-5 * 184 = 4.
1-0 * 184 1 ja 0 - 1 * 184 -184.
Olgu, teeme järgmisel real.
Meie k väärtus on 1, sest
5 jagatud 4 = 1 mõned ülejäänud.
Olgem täita muid veerge.
5-4 * 1 = 1.
0-1 * 1 = -1.
Ja 1-184 * 1 on 185.
Vaatame, mis meie kõrval k väärtus oleks.
Noh, tundub, et meil on 4 jagada 1, mis on 4.
Sellisel juhul, kui me jagame 1 selline, et k on võrdne
D väärtus ülaltoodud rida tähendab, et me oleme valmis meie algoritm.
Me näeme siin, et meil on x = 185 ja y = -1 viimases reas.
Lähme nüüd tagasi meie algse eesmärgi.
Me ütlesime, et x väärtus tõttu töötab see algoritm
oleks kordades pöördvõrdeline (mod b).
See tähendab, et 185 on kordades pöördvõrdeline 5 (mod 924)
mis tähendab, et meil on väärtus 185 d.
Asjaolu, et d = 1 viimases reas
kontrollib, et e oli coprime m.
Kui see ei oleks 1, siis oleks meil valida uue e.
Nüüd vaatame, kui Rob on saanud minu sõnum.
Kui keegi saadab mulle krüpteeritud sõnum
nii kaua kui ma olen hoidnud minu isiklik võti saladus
Ma olen ainus, kes saab lahti krüptida.
Dekrüpteerimiseks patakas c võin arvutada algne sõnum
võrdub tüki d võimsus (mod n).
Pea meeles, et d ja n on minu isiklik võti.
Et saada täielikku sõnum selle tükkideks me dekrüpteerida iga tüki
ja concatenate tulemusi.
Täpselt kuidas turvaline on RSA?
Tõde on, me ei tea.
Turvalisus põhineb, kui kaua see võtab ründaja murda sõnum
krüptitud RSA.
Pea meeles, et ründaja on juurdepääs teie avalik võti,
mis sisaldab nii e ja n.
Kui ründaja suudab tegur n arvesse oma 2 PRIMES p ja q,
siis ta võiks arvutada d kasutades laiendatud Eukleidese algoritm.
See annab tema isiklik võti, mida saab kasutada dekrüpteerimiseks sõnum.
Aga kui kiiresti me saame tegur täisarvud?
Jällegi, me ei tea.
Keegi on leidnud kiire viis seda teha,
mis tähendab, et antud piisavalt suur n
see võtab ründaja ebareaalselt pikk
silmas pidada mitmeid.
Kui keegi näitas kiire viis faktooring täisarvud
RSA oleks katki.
Aga isegi kui täisarv lahutus on oma olemuselt aeglane
RSA algoritm võiks veel mõned viga see
mis võimaldab lihtsa dekodeerimiseks sõnumeid.
Keegi on leidnud ja selgus selline viga veel,
kuid see ei tähenda veel ei ole.
Teoreetiliselt keegi võiks seal loed kõik andmed krüpteeritud RSA.
Seal on veel natuke puutumatuse küsimusega.
Kui Tommy krüpteerib mingit sõnumit kasutades minu avalik võti
ja ründaja krüpteerib sama sõnumi oma avaliku võtme
ründaja näed, et 2 sõnumit on identsed
ja seega tean, mida Tommy krüpteeritud.
Et seda vältida, sõnumid on tavaliselt polsterdatud juhuslikku bitti
enne krüpteeritakse, nii et sama sõnum krüpteeritud
mitu korda välja erinevad nii kaua kui polster sõnum on erinev.
Aga mäletan, kuidas meil on jagada lugemiseks tükkideks
nii, et iga tüki on väiksem kui n?
Polster tükkideks tähendab, et meil oleks jagada asju
isegi rohkem tükkideks, sest polsterdatud patakas peab olema väiksem kui n.
Kodeerimiseks ja dekodeerimiseks on suhteliselt kallid RSA,
ja nii oleks vaja lõhkuda sõnum paljudesse tükkideks võib olla väga kulukas.
Kui andmete suur hulk peab olema krüpteeritud ja lahtikrüptitud
saame kombineerida kasu sümmeetriline võti algoritme
omadega RSA saada nii turvalisuse ja tõhususe.
Kuigi me ei hakka seda siin,
AES on sümmeetriline võtme algoritmi nagu Vigenère ja Caesar ciphers
kuid palju raskem murda.
Loomulikult ei saa me kasutada AES ilma kehtestatakse jagatud võtit
vahel 2 süsteeme, ja me nägime probleem, et enne.
Aga nüüd saame kasutada RSA luua jagatud salajane võti vahel 2 süsteeme.
Me kutsume arvuti andmete saatmise saatja
ja arvuti andmed saanud vastuvõtja.
Vastuvõtja on RSA võtmepaari ja saadab
avaliku võtme saatjale.
Saatja genereerib AES võtmega,
krüpteerib selle saaja RSA avalik võti,
ja saadab AES võti vastuvõtja.
Vastuvõtja decrypts sõnum tema RSA avalik võti.
Nii saatja kui vastuvõtja on nüüd ühine AES võti nende vahel.
AES, mis on palju kiirem on kodeerimiseks ja dekodeerimiseks kui RSA,
Nüüd saab kasutada krüptimiseks suuri andmemahtusid ja saadab vastuvõtja,
kes saab dekrüpteerida kasutades sama võtit.
AES, mis on palju kiirem on kodeerimiseks ja dekodeerimiseks kui RSA,
Nüüd saab kasutada krüptimiseks suuri andmemahtusid ja saadab vastuvõtja,
kes saab dekrüpteerida kasutades sama võtit.
Me lihtsalt vaja RSA kanda jagatud võti.
Me ei pea enam kasutama RSA üldse.
Tundub, et ma pean kirja.
Ei ole oluline, kui keegi lugeda, mida on paberil lennuk enne, kui ma püütud seda
sest ma olen ainus, kellel isiklik võti.
Teeme lahti iga tükkideks sõnumis.
Esimese tüki, 658, tõstame kuni d võimsus, mis on 185,
mod n, mis on 989, on võrdne 67
mis on täht C ASCII.
Nüüd, peale teise patakas.
Teine rahn on väärtus 15
mis me tõstame kuni 185. võimu
mod 989, ja see on võrdne 83
mis on kirjas S ASCII.
Nüüd juba kolmandat patakas, mis on väärtus 799, tõstame kuni 185,
mod 989, ja see võrdub 53,
mis on väärtus iseloomu 5 ASCII.
Nüüd viimase tüki, mis on väärtus 975,
me tõstame 185, mod 989,
ja see võrdub 48, mis on väärtus tegelaskuju 0 ASCII.
Minu nimi on Rob Bowden, ja see on CS50.
[CS50.TV]
RSA üldse.
RSA üldse. [Naer]
Üldse.