[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Sveučilište Harvard]
[Ovo je CS50.] [CS50.TV]
Idemo pogledati RSA, naširoko koristi algoritam za šifriranje podataka.
Šifriranje algoritmi poput Cezara i Vigenère šifre nisu vrlo siguran.
Uz Cezarova šifra, napadač samo treba probati 25 različite tipke
dobiti poruku o običan tekst.
Dok Vigenère šifra je sigurniji nego Cezarova šifra
zbog većeg pretraživanje prostora za ključeve, nekad napadač
zna duljinu ključa u Vigenère šifra,
što se može utvrditi putem analize uzoraka u šifriranom tekstu,
the Vigenère šifra nije da je puno više siguran od Cezarova šifra.
RSA, s druge strane, nije ranjiv na napade kao što je ovaj.
The Cezarova šifra i Vigenère šifra koristiti isti ključ
na obje kriptirali i dešifriraju poruke.
Ova nekretnina čini ove šifre simetrične ključnih algoritama.
Temeljni problem s simetrične ključnih algoritama
je da se oslanjaju na jedan kriptiranje i slanje poruke
i jedan prima i dešifriranjem poruku
da već dogovorena unaprijed na ključu oni će oboje koristiti.
Ali imamo malo pokretanja problem ovdje.
Kako dva računala koja žele komunicirati uspostaviti tajni ključ između njih?
Ako je ključ mora biti tajna, onda trebamo način za šifriranje i dešifriranje tipke.
Ako je sve što imamo je simetrični ključ kriptografija
onda smo samo vratiti na isti problem.
RSA, s druge strane, koristi par ključeva,
jedan za šifriranje i drugi za dešifriranje.
Jedna se zove javni ključ, a drugi je privatni ključ.
Javni ključ se koristi za šifriranje poruka.
Kao što ste mogli pogoditi po nazivu, možemo podijeliti naš javni ključ s
tko želimo bez ugrožavanja sigurnosti šifriranom porukom.
Poruke šifrirana koristeći javni ključ
može biti samo dešifriraju s odgovarajućim privatnim ključem.
Iako možete podijeliti svoj javni ključ, uvijek biste trebali držati svoj privatni ključ tajnu.
i samo privatni ključ se može koristiti za dekriptiranje poruke
ako dvije korisnici žele slati poruke šifrirane s RSA
natrag i naprijed i korisnik morati imati svoj javni i privatni ključ par.
Poruke iz jednog korisnika do korisnika 2
koristiti samo Korisnik 2 je par ključeva i poruke od korisnika 2 na 1 korisnika
koristiti samo Korisnik 1 ključ par.
Činjenica da postoje dvije odvojene tipke za šifriranje i dešifriranje poruka
čini RSA asimetrični ključ algoritam.
Mi ne trebamo za šifriranje javnog ključa kako bi ga poslati na drugo računalo
jer ključ je javni svejedno.
To znači da RSA ne imati istu problema pri pokretanju
kao simetrične ključnih algoritama.
Dakle, ako želim poslati poruku koristeći RSA enkripciju
to Rob, ja prvo ćete morati Rob je javni ključ.
Za generiranje par ključeva, Rob treba pokupiti dvije velike prostih brojeva.
Ove brojke će se koristiti u oba javnih i privatnih ključeva,
ali javni ključ će koristiti samo proizvod tih dvaju brojeva,
nisu brojevi sami.
Jednom sam šifrirana poruka koristeći Rob je javni ključ
Ja mogu poslati poruku Rob.
Za računala, faktoring brojevi je težak problem.
Javni ključ, sjetite se, koristio proizvod dva prostih brojeva.
Ovaj proizvod onda mora imati samo dva faktora,
koji se dogoditi da se brojevi koji čine privatni ključ.
Kako bi dešifrirati poruku, RSA će koristiti ovaj privatni ključ
ili brojevi množe zajedno u procesu stvaranja javni ključ.
Budući da je računski teško faktor broj
koriste u javnim ključem u dvije brojeva koji se koriste u privatnim ključem
to je teško za napadač shvatiti privatni ključ
koje će biti potrebno za dekriptiranje poruke.
Sada idemo u nekim nižim razinama detalja RSA.
Idemo prvi put vidjeti kako možemo generirati par ključeva.
Prvo, mi ćemo morati dva prostih brojeva.
Nazvat ćemo ove dvije brojke p i q.
Kako odabrati p i q, u praksi smo pseudorandomly bi generirati
veliki broj, a zatim koristiti test za utvrđivanje je li ili ne
ti brojevi su vjerojatno premijera.
Možemo zadržati generiranja slučajnih brojeva iznova i iznova
dok imamo dva primes koje možemo koristiti.
Ovdje ćemo pokupiti p = 23 i q = 43.
Sjetite se, u praksi, p i q trebao biti puno veći broj.
Koliko mi znamo, veći broj, to je teže
ispucati šifriranu poruku.
No, to je i skuplji za šifriranje i dešifriranje poruka.
Danas se često preporučuje da p i q su najmanje 1024 bita,
koji stavlja svaki broj na više od 300 decimalnih znamenki.
No, mi ćemo pokupiti ove male brojeve za ovaj primjer.
Sada ćemo pomnožiti p i q zajedno kako bi dobili treći broj,
koje ćemo nazvati n.
U našem slučaju, n = 23 * 43, koji = 989.
Mi smo n = 989.
Sljedeća ćemo pomnožiti P - 1 sa q - 1
dobiti četvrti broj, koji ćemo nazvati m.
U našem slučaju, m = 22 * ​​42, koji = 924.
Imamo m = 924.
Sada ćemo morati brojčanu e koji je relativno premijera do m
i manje od m.
Dva su brojevi relativno premijera ili coprime
ako je jedini pozitivni cijeli broj koji ih dijeli i ravnomjerno je 1.
Drugim riječima, najveći zajednički djelitelj e i m
mora biti jedan.
U praksi, to je uobičajeno za e biti prost broj 65537
dok je taj broj se ne dogodi da bude faktor metara.
Za naše ključeva, mi ćemo pokupiti e = 5
od 5 je relativno premijera na 924.
Konačno, trebat ćemo još jedan broj, koji ćemo nazvati d..
D mora biti neka vrijednost koja zadovoljava jednadžbu de = 1 (mod m).
Ovaj mod m označava ćemo koristiti nešto što se zove modularna aritmetika.
U modularnom aritmetikom, kad broj dobiva više nego neki gornja granica
ona će završiti natrag oko 0.
Sat, na primjer, koristi modularni aritmetiku.
Jednu minutu nakon 01:59, na primjer, 02:00,
ne 1:60.
Skazaljka je omotan oko 0
nakon dostizanja gornju granicu od 60 godina.
Dakle, možemo reći 60 je ekvivalent 0 (mod 60)
i 125 je ekvivalent do 65 je ekvivalent 5 (mod 60).
Naš javni ključ će biti par e i n
gdje je u ovom slučaju je e 5 i n je 989.
Naš privatni ključ će biti par d i n,
koja je u našem slučaju je 185 i 989.
Uočite da naš izvorni primes p i q ne pojavljuju
nigdje u našim privatnim ili javnim ključevima.
Sada imamo par ključeva, ajmo pogledati kako možemo kodirati
i dešifriranje poruka.
Želim poslati poruku da Rob,
tako da će on biti jedan generirati ovaj par ključeva.
Onda ću pitati Rob za svoj javni ključ, koji ću koristiti
za šifriranje poruku da pošalje k ​​njemu.
Zapamtite, to je potpuno u redu za Rob podijeliti svoj javni ključ sa mnom.
No, to ne bi bilo u redu da dijele njegov privatni ključ.
Ja nemam pojma što je njegov privatni ključ je.
Možemo slomiti našu m poruke na nekoliko komade
sve manji od n, a zatim šifriranje svaki od tih komade.
Mi ćemo kodirati niz CS50, što možemo razbiti u komade, 4
jedan po pismu.
Kako za šifriranje moju poruku, ja ću ga morati pretvoriti u
neka vrsta numeričkom reprezentacije.
Ajmo spojite ASCII vrijednosti s likovima u moje poruke.
Kako za šifriranje dao m poruke
Ja ću morati izračunati c = m do e (mod n).
Ali m mora biti manji od n,
inače puna poruka ne može se izraziti modulu n.
Možemo razbiti m na nekoliko komade, koji su svi manji od n,
i šifriranje svaki od tih komade.
Šifriranje svaki od tih komade, dobili smo c1 = 67 do 5 (mod 989)
koje = 658.
Za naš drugi komad imamo 83 do 5 (mod 989)
koje = 15.
Za naš treći komad imamo 53 do 5 (mod 989)
koje = 799.
I na kraju, za našeg posljednjeg komad imamo 48 do 5 (mod 989)
koje = 975.
Sada možemo poslati preko ove šifrirane vrijednosti Rob.
Evo, Rob.
Iako je naša poruka je u letu, ajmo uzeti drugi izgled
na koliko smo dobili tu vrijednost za d.
Naš broj d potrebno zadovoljiti 5D = 1 (mod 924).
To čini d. multiplikativni inverz 5 modulo 924.
S obzirom na dva cijela broja, A i B, proširena Euklidova algoritma
se može koristiti kako bi pronašli najveći zajednički djelitelj tih dvaju brojeva.
Također će nam dati dvije druge brojeve, X i Y,
koji zadovoljavaju jednadžbu ax + by = najveći zajednički djelitelj od A i B.
Kako nam to pomoći?
Pa, uključivanjem u E = 5 za
i m = 924 za b
Već znamo da su ti brojevi su coprime.
Njihov najveći zajednički djelitelj je 1.
To nam daje 5x + 924y = 1
ili 5x = 1 - 924y.
Ali ako mi samo briga o svemu modulo 924
onda možemo ispustiti - 924y.
Think natrag na sat.
Ako minuta ruka na jednoj, a zatim točno 10 sati prolaze,
znamo minuta ruka će i dalje biti na jednom.
Ovdje ćemo početi na jednom i onda zaokrenuti točno y puta,
tako da smo i dalje ćete biti na jednom.
Imamo 5x = 1 (mod 924).
I ovdje je ovo x je isti kao d smo bili u potrazi za prije,
pa ako mi koristimo proširenu Euklidova algoritma
da biste dobili ovaj broj x, to je broj bismo trebali koristiti kao naš d.
Sada ćemo pokrenuti proširena Euklidova algoritma za a = 5
i b = 924.
Mi ćemo koristiti metodu zvanu tablica metoda.
Naš stol će imati 4 stupce, X, Y, d, k.
Naš stol započinje s dva reda.
U prvom redu moramo 1, 0, tada je naša vrijednost, što je 5,
i naš drugi red je 0, 1, i naša vrijednost za B, koji je 924.
Vrijednost 4. stupcu, K, će biti rezultat
podjele vrijednost D u redu iznad njega s vrijednosti d
u istom retku.
Imamo pet podijeljeno 924 je 0 s nekim ostatak.
To znači da imamo k = 0.
Sada vrijednost svake druge stanice će biti vrijednost staničnih 2 reda iznad njega
minus vrijednost retka iznad nje puta k.
Počnimo s d u 3. redu.
Imamo 5-924 * 0 = 5.
Sljedeća imamo 0-1 * 0 koji je 0
i 1-0 * 0 što je 1.
Nije loše, pa krenimo na sljedeći red.
Prvo moramo našu vrijednost k.
924 podijeljeno 5 = 184 s nekim ostatak,
tako da naša vrijednost za k je 184.
Sada 924-5 * 184 = 4.
1-0 * 184 je 1 i 0-1 * 184 je -184.
U redu, idemo napraviti sljedeći redak.
Naša vrijednost k će biti jedan, jer
5 podijeljen 4 = 1 s nekim ostatak.
Ajmo ispuniti u drugim stupcima.
5-4 * 1 = 1.
0-1 * 1 = -1.
I 1-184 * 1 185.
Idemo vidjeti što naš sljedeći vrijednost k će biti.
Pa, to izgleda kao da smo četiri podijeljena jedan, što je četiri.
U ovom slučaju gdje smo razdjelnom do 1. tako da je k jednak
vrijednost d u gornjem redu znači da smo učinili s našim algoritam.
Možemo vidjeti da se ovdje imamo x = 185 y = -1 i u zadnjem redu.
Idemo sada vratiti našem izvornom cilja.
Reći da je vrijednost od x kao rezultat trčanje ovaj algoritam
će biti multiplikativni inverz a (mod b).
To znači da je 185 multiplikativni inverz 5 (mod 924)
što znači da ćemo imati vrijednost 185 za d.
Činjenica da je d = 1 u zadnjem redu
provjerava da e je coprime da m.
Da nije bilo jednog onda bismo morali odabrati novu e.
Sada ćemo vidjeti da li je Rob je dobio moju poruku.
Kada vam netko pošalje mi šifriranu poruku
dok sam držao moje privatni ključ tajnu
Ja sam jedini koji može dekriptirati poruku.
Za dekriptiranje komad c mogu izračunati izvornu poruku
jednaka je komad do d snage (mod n).
Sjetite se da je d i n su iz mog privatnog ključa.
Da biste dobili punu poruku od svojih komade smo dešifrirati svaki komad
i spojite rezultate.
Točno kako je siguran RSA?
Istina je, ne znamo.
Sigurnost se temelji na tome koliko dugo će potrajati napadača ispucati poruku
kodirana s RSA.
Sjetite se da je napadač ima pristup vašem javnog ključa,
koji sadrži i e i n.
Ako napadač uspio uzet n u svoje dvije primes, p i q,
onda je ona mogla izračunati d koristeći prošireni Euklidova algoritma.
To joj daje privatni ključ, koji se može koristiti za dekriptiranje bilo koju poruku.
No, koliko brzo možemo uzet cijeli brojevi?
Opet, ne znamo.
Nitko nije pronašao brzo način to rade,
što znači da je dano dovoljno velik n
da bi se napadač nerealno dugo
za faktor broja.
Ako je netko otkrio brz način factoring brojeva
RSA bi biti slomljena.
Ali čak i ako cijeli faktorizacija je inherentno spor
RSA algoritam još uvijek može imati neki nedostatak u njemu
koji omogućuje jednostavnu dešifriranje poruka.
Nitko nije pronašao i otkrio takav propust ipak,
ali to ne znači da netko ne postoji.
U teoriji, netko bi mogao biti vani čita sve podatke kriptirani s RSA.
Tu je još malo privatnosti pitanju.
Ako Tommy šifrira neke poruke koristeći moj javni ključ
i napadač šifrira istu poruku koristeći svoj javni ključ
napadač će vidjeti da su dvije poruke su identične
i tako znati što je Tommy kodiran.
Kako bi se to spriječilo, poruke su obično podstavljena s slučajnih bitova
prije kodiran, tako da je ista poruka kriptirani
više puta će izgledati drugačije dok padding na poruke je drugačiji.
Ali zapamtite kako moramo podijeliti poruke na komade
tako da je svaki komad je manji od n?
Padding the komade znači da ćemo morati podijeliti stvari
na još više komade od podstavljene komad mora biti manji od n.
Šifriranje i dešifriranje su relativno skup s RSA,
i tako trebaju razbiti poruku u mnogim komade može biti vrlo skupo.
Ako velika količina podataka treba biti kodiran i dešifriraju
možemo kombinirati prednosti simetrične ključnih algoritama
s onima RSA dobiti i sigurnost i učinkovitost.
Iako nećemo ići u nju ovdje,
AES je simetrični ključ algoritam kao Vigenère i Caesar šiframa
ali mnogo teže ispucati.
Naravno, ne možemo koristiti AES bez uspostave zajednički tajni ključ
između dva sustava, a vidjeli smo problema s tim prije.
No, sada možemo koristiti RSA uspostaviti zajednički tajni ključ između dva sustava.
Mi ćemo pozvati računalo slanja podataka pošiljatelja
i računalo prima podatke prijemnik.
Prijemnik ima RSA par ključeva i šalje
javni ključ pošiljatelja.
Pošiljatelj generira AES ključ,
to šifrira sa prijemnika RSA javni ključ,
i šalje AES ključ na prijemnik.
Prijemnik dekriptira poruku sa svojim privatnim ključem RSA.
I pošiljatelj i primatelj sada imaju zajedničku AES ključ između njih.
AES, što je mnogo brže šifriranje i dešifriranje nego RSA,
sada se može koristiti za šifriranje velike količine podataka i poslati ih na prijemnik,
tko može dekriptirati koristeći istu tipku.
AES, što je mnogo brže šifriranje i dešifriranje nego RSA,
sada se može koristiti za šifriranje velike količine podataka i poslati ih na prijemnik,
tko može dekriptirati koristeći istu tipku.
Mi samo potrebno RSA prenijeti zajednički ključ.
Mi više ne trebate koristiti RSA uopće.
Čini se kao da sam dobio poruku.
To ne smeta ako netko pročitati ono što je na papiru aviona prije nego što sam ga uhvatio
jer ja sam jedini s privatnim ključem.
Ajmo dešifriranje svaki od komade u poruci.
Prvi blok, 658, dižemo se d vlasti, što je 185,
mod n, koji je 989, je jednaka 67,
što je slovo C u ASCII.
Sada, na drugo komad.
Drugi blok ima vrijednost 15,
koje smo podići na 185. vlast,
mod 989, a to je jednako na 83
što je slovo S u ASCII.
Sada za treći blok, koji ima vrijednost 799, dižemo do 185,
mod 989, a to je jednako 53,
što je vrijednost znaka 5 u ASCII.
Sada za zadnji komad, koja ima vrijednost 975,
možemo podići na 185, 989, mod
i to je jednaka do 48, što je vrijednost znakova 0 u ASCII.
Moje ime je Rob Bowden, a ovo je CS50.
[CS50.TV]
RSA uopće.
RSA uopće. [Smijeh]
Na sve.