[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[To je CS50.] [CS50.TV]
Oglejmo si na JAR, se pogosto uporablja algoritem za šifriranje podatkov.
Algoritmi šifriranja, kot Cezar in Vigenère šifer niso zelo varna.
Z Cezarjeva šifra, napadalec potrebuje samo poskusiti 25 različnih ključev
da bi dobili sporočilo v golo besedilo.
Medtem ko je šifra Vigenère je bolj varna kot Cezarjeva šifra
zaradi večjega prostora za iskanje za ključe, potem ko napadalec
ve dolžino ključa v šifro Vigenère,
ki se lahko določi z analizo vzorcev v šifrirani besedila,
se številka Vigenère ni, da je veliko bolj varna kot Cezarjeva šifra.
RSA, na drugi strani pa ni ranljiv za napade, kot je ta.
Caesar šifra in Vigenère šifra uporabljati isti ključ
tako šifriranje in dešifriranje sporočila.
Ta lastnost naredi teh šifer simetričnega ključa algoritmov.
Temeljni problem pri simetričnih algoritmov ključnih
je, da se zanašajo na eni kriptiranjem in pošiljanje sporočil
in tisti, sprejemanje in dekodiranje sporočila
da so se že dogovorili vnaprej, na njej pa bosta uporabljali.
Toda imamo nekaj zagonskega problem tukaj.
Kako 2 računalnika, ki želijo vzpostaviti komunikacijo med njimi skrivni ključ?
Če mora biti ključ skrivnost, potem moramo način za šifriranje in dešifriranje ključ.
Če vse, kar imate, je simetrična ključi
Nato smo se pravkar vrnil z enako težavo.
RSA, na drugi strani pa uporablja par ključev,
enega za šifriranje in dešifriranje za drugo.
Ena se imenuje javni ključ, drugi pa je zasebni ključ.
Javni ključ se uporablja za šifriranje sporočil.
Kot ste lahko uganiti, s svojim imenom, lahko delimo naš javni ključ z
kdorkoli si želimo, ne da bi ogrozili varnost šifrirano sporočilo.
Sporočila kodirana z uporabo javnega ključa
lahko samo decrypted z ustreznim zasebnim ključem.
Medtem ko lahko delite svoj javni ključ, morate vedno svoj zasebni ključ v tajnosti.
in lahko samo zasebni ključ za dešifriranje sporočil
če 2 uporabniki želijo poslati sporočilo šifrirano z JAR
naprej in nazaj, tako uporabniki morajo imeti svoj javni in zasebni par ključev.
Sporočila uporabnika od 1 do 2 uporabnika
uporabljajte le Uporabnik 2 je par ključev, in sporočil od uporabnika do uporabnika 1 2
uporabljajte le par ključev 1 user je.
Dejstvo, da obstajajo 2 ločeni ključi za šifriranje in dešifriranje sporočila
Zaradi RSA asimetrična algoritem ključa.
Ne potrebujemo za šifriranje javnega ključa, da bi ga poslali v drug računalnik
saj je ključ javno vseeno.
To pomeni, da RSA nima enake težave pri zagonu
kot simetričnih ključnih algoritmov.
Torej, če želim poslati sporočilo z šifriranje RSA
Rob se bom najprej morali javni ključ Rob je.
Če želite ustvariti par ključev, Rob mora izbrati 2 velika praštevila.
Te številke se bodo uporabljali tako v javnih in zasebnih ključev,
ampak javni ključ uporablja samo proizvod teh 2 številk
ne številke same.
Ko sem šifrirano sporočilo z javnim ključem je Rob
Ne morem poslati sporočilo robu.
Za računalnik, faktoring številke je težko problem.
Javni ključ, se spomnite, ki se uporablja za izdelek 2 praštevila.
Ta izdelek je potem samo 2 dejavnike,
, ki se zgodi, da so številke, ki sestavljajo zasebni ključ.
Da bi dešifriranje sporočila, bo RSA uporabo tega zasebni ključ
ali številke pomnožijo skupaj v procesu oblikovanja javnega ključa.
Ker je računsko težko vključijo tudi število
uporabljajo javni ključ v 2 številkah v zasebni ključ
je težko za napadalca, da ugotovimo, zasebni ključ
da bo treba dešifrirati sporočila.
Zdaj pa pojdimo na nekaj nižji ravni podrobnosti JAR.
Naj najprej videti, kako lahko ustvarimo par ključev.
Najprej bomo potrebovali 2 praštevil.
Poklicali bomo te številke 2 p in q.
Za prevzem P in Q, v praksi bi si ustvarila pseudorandomly
Velike številke in nato uporabite test za ugotavljanje, ali
te številke so verjetno prime.
Mi lahko vodijo ustvarjanje naključnih števil, znova in znova
dokler ne bomo imeli 2 praštevila, ki jih lahko uporabite.
Tukaj pa si izberete p = 23 in q = 43.
Ne pozabite, da v praksi, bi p in q lahko veliko večje številke.
Kolikor vemo, je večje številke, težje je
crack šifrirano sporočilo.
Ampak to je tudi dražji za šifriranje in dešifriranje sporočil.
Danes je pogosto priporočljivo, da p in q vsaj 1024 bitov,
ki postavlja vsako številko na več kot 300 decimalnih mest.
Ampak bomo izbrali te majhne številke za ta primer.
Zdaj bomo pomnožimo P in Q skupaj, da bi dobili 3. številko,
ki bomo poklicali n.
V našem primeru je n = 23 * 43 = 989, ki.
Imamo n = 989.
Nato bomo pomnožimo P - 1 q - 1
pridobiti 4. številko, ki bomo poklicali m.
V našem primeru je m = 22 * ​​42 = 924, ki.
Imamo m = 924.
Zdaj bomo potrebovali številko E, ki je relativno prime, da m
in manj kot m.
Dva številke so relativno prime ali coprime
če le pozitivno celo, da jih je razdelil tako enakomerno je 1.
Z drugimi besedami, največji skupni delitelj E in M
mora biti 1.
V praksi je skupna za e, da je praštevilo 65537
Dokler se to število ne zgodi, da se faktor m.
Za naše tipk, bomo izbrali e = 5
od 5. relativno prime za 924.
Končno, bomo potrebovali še eno številko, ki bomo poklicali d.
D mora biti nekaj vrednost, ki ustreza enačbi de = 1 (mod m).
To pomeni, mod m bomo uporabili nekaj, kar ti modularna aritmetika.
V modularne aritmetike, ko postane številka višja od nekaterih zgornja meja
se bo sklenil nazaj okoli 0.
Ura, na primer, uporablja modularne aritmetike.
Minuto po 01:59, na primer, je 2:00,
Ne 1:60.
Minutni kazalec je ovita okoli 0
ob prihodu zgornja meja 60 let.
Torej lahko rečemo, 60 je enak 0 (mod 60)
in 125 je enaka 65 je enaka do 5 (mod 60).
Naš javni ključ bo par e in n
če v tem primeru e je 5 in n 989.
Naše zasebni ključ bo par d in n,
ki je v našem primeru 185 in 989.
Obvestilo, da je naša prvotna praštevil p in q se ne pojavljajo
kjerkoli v naših zasebnih ali javnih ključev.
Zdaj, ko imamo par ključev, pa si oglejte, kako lahko šifriranje
in dešifriranje sporočila.
Želim poslati sporočilo Rob,
Tako bo on tisti, ki bo generiral par ključev.
Potem bom vprašal Rob za njegov javni ključ, ki bom uporabo
za šifriranje sporočila, da pošlje k ​​njemu.
Ne pozabite, da je popolnoma v redu, Rob deliti svoje javni ključ z mano.
Ampak to ne bi bilo prav, da delijo svojim zasebnim ključem.
Nimam pojma, kaj je njegov zasebni ključ.
Mi lahko zlomiti sporočilo metrov v več kosih
vse manjša od n in nato šifriranje vsako od teh koščkih.
Mi bomo šifriranje niz CS50, ki ga lahko razdelite v 4 kose,
ena na pisma.
Za šifriranje moje sporočilo, bom potreboval, da se pretvori v
neke vrste številske predstavitve.
Naj spenjanje ASCII vrednosti z znaki v mojem sporočilu.
Za šifriranje določenega m sporočilo
Potreboval bom za izračun c = m na e (mod n).
Vendar mora biti manjši od m n
ali pa celotna sporočila ni mogoče izraziti modulo n.
Mi lahko razbije m v več kosih, vsi, ki so manjša od n,
šifriranje in vsako od teh koščkih.
Šifriranje vsako od teh koščkih, dobimo c1 = 67 do 5 (mod 989)
ki = 658.
Za naš drugi kos imamo 83 do 5 (mod 989)
ki = 15.
Za naše tretje bloku imamo 53 do 5 (mod 989)
ki = 799.
In končno, na našem zadnjem bloku imamo 48 do 5 (mod 989)
ki = 975.
Sedaj lahko pošljete preko te šifrirane vrednosti robu.
Tukaj imaš, no.
Čeprav je naše sporočilo, v letu, dajmo še enkrat pogledati
o tem, kako smo dobili to vrednost za d.
Naša številka d potrebne za zadovoljitev 5D ​​= 1 (mod 924).
To pomeni, d za množenje inverzna 5 modulo 924.
Glede na to, cela 2, A in B, razširjeni Evklidov algoritem
se lahko uporablja, da bi našli največji skupni delitelj teh števil 2.
To bo tudi nam 2 drugih številk, X in Y,
ki izpolnjuje enačbo ax + by = največji skupni delitelj a in b.
Kako nam to pomaga?
No, priklopom na e = 5 za
in m = 924 za B
že vemo, da so te številke coprime.
Njihov največji skupni delitelj 1.
To nam daje 5x + 924y = 1
ali 5x = 1 - 924y.
Ampak, če bomo samo skrbi vse modulo 924
potem bomo lahko spusti - 924y.
Pomisli nazaj na uro.
Če minutni kazalec je na 1 in potem točno 10 ur mimo,
Vemo minutni kazalec bo še vedno na 1.
Tu smo začeli na 1 in nato ovijte okoli točno y-krat,
tako da bomo še vedno na 1.
Imamo 5x = 1 (mod 924).
In tukaj je ta x je enak kot d smo iskali pred
tako da, če bomo uporabili razširjeno Evklidov algoritem
da se to število x, da je številka, da bi morali uporabiti kot naše d.
Zdaj pa teče razširjenega Evklidov algoritem za = 5
in b = 924.
Uporabili bomo metodo, ki se imenuje tabela način.
Naša miza bo imela 4 stolpce, X, Y, d, in k.
Naša miza prične z 2 vrstic.
V prvi vrsti moramo 1, 0, potem je naša vrednost, kar je za 5,
in naša druga vrsta je 0, 1, in naša vrednost za b, kar je 924.
Vrednost 4. stolpcu, k se bo rezultat
delitve vrednost d v vrstici nad njo z vrednostjo d
na isti vrsti.
Imamo 5 deljeno s 924 je 0 z nekaj ostanka.
To pomeni, da moramo k = 0.
Zdaj bo vrednost vsake druge celice je vrednost celice 2 vrstic nad njo
minus vrednost vrstici nad njo krat k.
Začnimo z d v 3. vrsti.
Imamo 5-924 * 0 = 5.
Nato imamo 0-1 * 0, ki je 0
in 1 - 0 * 0, ki je 1.
Ni slabo, tako da gremo na naslednjo vrstico.
Najprej moramo našo vrednost k.
924 deljeno s 5 = 184 z nekaj preostalega
Tako naša vrednost k je 184.
Zdaj 924-5 * 184 = 4.
1-0 * 184 je 1 in 0 - 1 * 184 je -184.
V redu, naredimo naslednjo vrstico.
Naša vrednost k bo 1, ker
5 deljeno s 4 = 1 z nekaj ostanka.
Naj izpolnijo v drugih stolpcih.
5-4 * 1 = 1.
0-1 * 1 = -1.
In 1-184 * 1 je 185.
Poglejmo, kaj bo naša naslednja vrednost k biti.
No, izgleda, da imamo 4 deli z 1, kar je 4.
V tem primeru, ko smo delila z 1, tako da je k enak
vrednost d v zgornji vrstici pomeni, da bomo končali z našim algoritmom.
Tukaj lahko vidimo, da imamo x = 185 in y = -1, v zadnji vrsti.
Pojdimo zdaj vrnil na naš prvotni cilj.
Rekli smo, da je vrednost x zaradi tega teče algoritem
bi bilo multiplikativni inverz a (mod b).
To pomeni, da 185 je multiplikativni inverz 5 (mod 924)
kar pomeni, da imamo v vrednosti 185 za d.
Dejstvo, da je d = 1 v zadnji vrsti
preveri, e je coprime m.
Če ne bi bilo 1, potem bi morali izbrati nov e.
Zdaj pa poglejmo, če je Rob prejel moje sporočilo.
Ko vam nekdo pošlje mi šifrirano sporočilo
tako dolgo, kot sem držal zasebnega ključa skrivnost
Jaz sem edini, ki lahko dešifrira sporočilo.
Za dešifriranje kosi C lahko jaz izračun izvirno sporočilo
je enak kos na d moči (mod n).
Ne pozabite, da d in n so iz mojega zasebnega ključa.
Da bi dobili celotno sporočilo iz svojih koščkih smo dešifriranje vsak kos
in združevanje rezultatov.
Točno, kako varna je RSA?
Resnica je, da ne vemo.
Varnost temelji na tem, kako dolgo bi trajalo, da bi onemogočili napadalca sporočilo
zaščiteni z JAR.
Zapomnite si, da napadalec nima dostopa do vašega javnega ključa,
, ki vsebuje tako e in n.
Če napadalec uspel faktor N v svoje praštevil 2, p in q,
potem bi ona izračun d s podaljšanim Evklidov algoritem.
To ji daje zasebni ključ, ki se lahko uporablja za dešifriranje vsako sporočilo.
Toda, kako hitro lahko dejavnik cela?
Še enkrat, ne vemo.
Nihče še ni našel hiter način delovanje,
kar pomeni, da daje dovolj velike n
da bi se z napadalcem nerealno dolgo
na faktorja številko.
Če nekdo pokazal hiter način faktoring celih
RSA bi zlomljen.
A tudi če celo Faktorizacija dokaj počasna
RSA algoritem lahko še nekaj pomanjkljivost v njej
ki omogoča enostavno dešifriranje sporočil.
Nihče še ni našel in pokazal takšno napako še,
vendar to ne pomeni, da to ne obstaja.
V teoriji bi lahko nekdo tam bere vse šifriranja podatkov z JAR.
Še en malo zasebnosti izdaje.
Če Tommy šifrira nekaj sporočilo z mojo javni ključ
in napadalec šifrira isto sporočilo z mojo javni ključ
napadalec bo videl, da so enaki 2 sporočil
in tako vedeli, kaj Tommy šifrirani.
Da bi to preprečili, so sporočila po navadi podložena z naključnimi bitov
pred šifrirane, tako da isto sporočilo šifrirano
večkrat bo videti drugačen, dokler oblazinjenje v sporočilu, je drugačen.
Ampak ne pozabite, kako moramo razdeliti na kose sporočil
tako, da vsak kos je manjši od n?
Oblazinjenje the kose pomeni, da bomo morali razdeliti stvari
v še bolj kose, saj mora biti oblazinjen kos biti manjše od n.
Šifriranje in dešifriranje relativno drago z RSA,
in tako da bi morali pustiti sporočilo na več koščkih zelo drago.
Če je prisotna velika količina podatkov, ki mora biti šifrirana in dešifrirajo
lahko združujejo prednosti simetričnih algoritmov ključnih
s tistimi iz JAR, da se tako varnost in učinkovitost.
Kljub temu, da ne bo šel v to tukaj,
AES je simetrični ključ algoritem kot Vigenère in šifer Caesar
ampak veliko težje crack.
Seveda ne moremo uporabljati AES brez vzpostavitve skupnega skrivni ključ
med 2 sistemov, in videli smo, da je problem s prej.
Ampak zdaj lahko uporabimo RSA vzpostaviti skupni tajni ključ med 2 sistemov.
Poklicali bomo računalnik pošlje podatke pošiljatelja
in računalnik, ki prejme podatke sprejemnik.
Sprejemnik ima RSA par ključev, ki ga pošlje
javni ključ pošiljatelju.
Pošiljatelja ustvari ključ AES,
ga šifrira z RSA sprejemnika javni ključ,
in pošlje ključ AES sprejemnik.
Sprejemnik dekodira sporočilo z RSA zasebnega ključa.
Tako je pošiljatelj, prejemnik pa ima zdaj skupno AES ključ med njimi.
AES, kar je precej hitrejši pri šifriranje in dešifriranje kot RSA,
se zdaj lahko uporablja za šifriranje velike količine podatkov in jih pošlje sprejemniku,
kdo lahko dešifrira z isto tipko.
AES, kar je precej hitrejši pri šifriranje in dešifriranje kot RSA,
se zdaj lahko uporablja za šifriranje velike količine podatkov in jih pošlje sprejemniku,
kdo lahko dešifrira z isto tipko.
Pravkar smo potrebni RSA za prenos v skupni rabi tipko.
Mi ni treba več uporabljati RSA sploh.
Izgleda, da sem dobil sporočilo.
Ni važno, če je kdo prebral, kaj je na papirju letala, preden sem ga ujel
ker sem edini, ki se z zasebnim ključem.
Naj dešifrirati vsako kose v sporočilu.
Prvi kos, 658, dvignemo na d moči, kar je 185,
mod n, ki je 989, ki je enak 67,
ki je črka C v ASCII.
Zdaj, na drugem bloku.
Drugi Blok ima vrednost 15,
ki smo jo dvigniti na 185. moči,
mod 989, kar je enako 83
ki je črka S, ki v ASCII.
Sedaj že tretje bloku, ki ima vrednost 799, se poveča na 185,
mod 989, kar je enako 53,
ki je vrednost značaja 5 v ASCII.
Zdaj za zadnji kos, ki ima vrednost 975,
bomo dvignili na 185, 989, mod
in to je enako 48, ki je vrednost 0 znakov v ASCII.
Moje ime je Rob Bowden, in to je CS50.
[CS50.TV]
RSA sploh.
RSA sploh. [Smeh]
Na vse.