[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Universitatea Harvard]
[Acest lucru este CS50.] [CS50.TV]
Să aruncăm o privire la RSA, un algoritm utilizat pe scară largă pentru criptarea datelor.
Algoritmi de criptare, cum ar fi Cezar și cifruri Vigenere nu sunt foarte sigure.
Cu cifru Cezar, un atacator trebuie doar să încercați 25 chei diferite
pentru a obține textul mesajului simplu.
În timp ce cifrul Vigenere este mai sigură decât cifrul Cezar
din cauza spațiul de căutare mai mare pentru chei, odată ce un atacator
stie lungimea cheie într-un cifru Vigenere,
care poate fi determinată printr-o analiză a modelelor în textul criptat,
cifrul Vigenere nu este atât de mult mai sigure decât cifrul Cezar.
RSA, pe de altă parte, nu este vulnerabil la atacuri de acest gen.
Cifrul Vigenere Cifrul Cezar și să utilizeze aceeași cheie
atât cripta și decripta un mesaj.
Aceasta proprietate face ca aceste cifruri simetrice algoritmi cheie.
O problemă fundamentală cu algoritmi cu chei simetrice
este faptul că acestea se bazează pe o criptare și trimiterea mesajului
și cel care a primit și decriptarea mesajului
au convenit să deja în avans pe tasta se vor folosi ambele.
Dar avem un pic de o problemă de pornire aici.
Cum 2 calculatoare care doresc să comunice stabili o cheie secretă între ele?
Dacă cheia trebuie să fie secretă, atunci avem nevoie de o modalitate de a cripta și decripta cheia.
Dacă tot ce avem este criptografia simetrică cheie
apoi ne-am întors doar la aceeași problemă.
RSA, pe de altă parte, folosește o pereche de chei,
unul pentru criptare și decriptare pentru un alt.
Unul se numește cheie publică, iar cealaltă este cheia privată.
Cheia publică este utilizată pentru a cripta mesajele.
Așa cum s-ar putea ghici dupa numele acestuia, putem împărtăși cheia noastră publică cu
cineva ne-o dorim, fără a compromite securitatea unui mesaj criptat.
Mesajele criptate folosind o cheie publică
poate fi decriptat cu cheia sa privată corespunzătoare.
În timp ce aveți posibilitatea să partajați cheia dvs. publică, ar trebui să păstreze întotdeauna tău secret cheia privată.
și numai cheia privată poate fi utilizată pentru a decripta mesaje
în cazul în care utilizatorii doresc să 2 trimite mesaje criptate cu RSA
înainte și înapoi, atât pentru utilizatorii trebuie să aibă propriul lor pereche de public și privat cheie.
Mesaje de la 1 la ghidul de utilizare 2
utilizați numai 2 perechi utilizatorului cheie, și mesaje de la utilizator la utilizator 1 2
utilizați numai pereche de chei utilizator 1 lui.
Faptul că există 2 taste separate pentru a cripta și decripta mesaje
RSA face un algoritm asimetric cheie.
Nu avem nevoie pentru a cripta cheia publică, în scopul de a-l trimite la un alt calculator
deoarece cheia este public, oricum.
Acest lucru înseamnă că RSA nu are aceeași problemă de pornire
ca algoritmi cu chei simetrice.
Deci, dacă vreau să trimiteți un mesaj utilizând criptarea RSA
la Rob, am nevoie de o cheie publică prima lui Rob.
Pentru a genera o pereche de chei, Rob trebuie să aleagă 2 numere prime mari.
Aceste numere vor fi utilizate în ambele taste public și privat,
dar cheia publică va folosi numai produsul acestor 2 numere,
nu și numerele în sine.
După ce am criptat mesajul folosind cheia publică a lui Rob
Eu pot trimite mesajul Rob.
Pentru un calculator, numere de factoring este o problemă grea.
Cheia publică, amintiți-vă, folosit produsul de 2 numere prime.
Acest produs trebuie să aibă, apoi doar 2 factori,
care se întâmplă să fie numerele care alcătuiesc cheia privată.
În scopul de a decripta mesajul, RSA va folosi această cheie privată
sau numerele de înmulțit împreună în procesul de creare a cheii publice.
Pentru că e greu de calcul a factorului complementar, numărul
utilizate într-o cheie publică în cele 2 numere utilizate în cheia privată
E dificil pentru un atacator pentru a descoperi cheia privată
care va fi necesară pentru a decripta mesajul.
Acum hai să mergem în unele detalii de nivel inferior ale RSA.
Să vedem mai întâi cum putem genera o pereche de chei.
În primul rând, vom avea nevoie de 2 numere prime.
Vom numi aceste 2 numere p și q.
În scopul de a alege p și q, în practică ne-ar genera pseudorandomly
numere mari și apoi utilizați un test pentru a determina dacă este sau nu
aceste numere sunt, probabil, prim.
Putem păstra generarea de numere aleatoare de peste si peste din nou
până când vom avea 2 numere prime pe care le putem folosi.
Aici sa aleg p = 23 și q = 43.
Amintiți-vă, în practică, p și q trebuie să fie număr mult mai mare.
În ceea ce știm, mai mare de numere, mai greu este
pentru a sparge un mesaj criptat.
Dar este, de asemenea, mult mai scumpe pentru a cripta și decripta mesaje.
Astăzi este adesea recomandat ca p și q sunt de cel puțin 1024 biți,
care pune fiecare număr de la peste 300 de cifre zecimale.
Dar vom alege aceste numere mici, pentru acest exemplu.
Acum ne vom multiplica p și q împreună pentru a obține un număr de 3,
pe care o vom numi nr.
În cazul nostru, n = 23 * 43, care = 989.
Ne-am n = 989.
Apoi, vom multiplica p - 1 cu q - 1
pentru a obține un număr de 4, pe care o vom numi m.
În cazul nostru, m = 22 * ​​42, care = 924.
Avem m = 924.
Acum, vom avea nevoie de un număr care e este relativ prim cu m
și mai mică de metri.
Două numere sunt prime între ele sau relativ prim
în cazul în întreg numai pozitiv pe care le imparte in mod egal, atât este de 1.
Cu alte cuvinte, cea mai mare divizor comun al e și m
trebuie să fie 1.
În practică, este comun pentru e să fie numar prim 65537
atâta timp cât acest număr nu se întâmplă să fie un factor de metri.
Pentru cheile noastre, vom alege e = 5
din 5 este relativ prim la 924.
În cele din urmă, vom avea nevoie de un număr mai, pe care vom numi d.
D trebuie să fie o valoare care satisface ecuația de = 1 (mod m).
Acest lucru semnifică m mod vom folosi ceva numit aritmetica modulara.
În aritmetica modulara, o dată un număr devine mai mare decât unele legat de sus
aceasta se va încadra în jurul valorii de înapoi la 0.
Un ceas, de exemplu, folosește aritmetica modulara.
La un minut după 1:59, de exemplu, este 2:00,
not 1:60.
Minutarul a înfășurat în jurul valorii de la 0
la atingerea o limită superioară de 60.
Deci, putem spune 60 este echivalent cu 0 (mod 60)
și 125 este echivalent cu 65 de ani este echivalentă cu 5 (mod 60).
Cheia noastră publică va fi perechea e și n
în cazul în care, în acest caz, e este 5 și n este 989.
Cheia noastră privată va fi perechea d și n,
care, în cazul nostru este de 185 și 989.
Observați că noastră originală prime p și q nu apar
oriunde în cheile noastre publice sau private.
Acum, că avem pereche de chei nostru, haideți să aruncăm o privire la modul în care putem cripta
și decripta un mesaj.
Vreau să trimit un mesaj la Rob,
deci el va fi cel care va genera această pereche de chei.
Atunci voi cere Rob pentru cheia sa publică, pe care voi folosi
pentru a cripta un mesaj pentru a trimite la el.
Amintiți-vă, e cu totul bine pentru Rob pentru a permite accesul cheia sa publica cu mine.
Dar nu ar fi bine să împărtășească cheia sa privată.
Eu nu am nici o idee despre ceea ce cheia sa privată este.
Ne putem rupe m mesajul nostru în sus, în bucăți mai multe
toate mai mici decât n și apoi cripta fiecare dintre aceste bucăți.
Vom cripta CS50 șir, pe care ne putem rupe în sus, în 4 bucăți,
unul pentru fiecare literă.
În scopul de a cripta mesajul meu, am avea nevoie să-l transforme în
un fel de reprezentare numerică.
Să concatena valorile ASCII cu caracterele din mesajul meu.
În scopul de a cripta un mesaj m dat
Am nevoie pentru a calcula c = m de la e (mod n).
Dar m trebuie să fie mai mic decât n,
sau altceva mesajul complet nu poate fi exprimat modulo n.
Ne putem rupe m în sus, în bucăți mai multe, toate din care sunt mai mici decât n,
și cripta fiecare dintre aceste bucăți.
Criptarea fiecare din aceste bucăți, se obține C1 = 67 la 5 (mod 989)
care = 658.
Pentru bucată a doua noastră, avem 83 la 5 (mod 989)
care = 15.
Pentru a treia bucată avem 53 la 5 (mod 989)
care = 799.
Și, în sfârșit, pentru bucata ultima noastră avem 48 la 5 (mod 989)
care = 975.
Acum putem trimite peste aceste valori criptate cu Rob.
Aici te duci, Rob.
În timp ce mesajul nostru este în zbor, să aruncăm o privire
la modul în care am ajuns ca valoarea pentru d.
Noastră numărul d necesară pentru a satisface 5d = 1 (mod 924).
Acest lucru face ca d inversul multiplicativ de 5 modulo 924.
Având în vedere 2 numere intregi, A și B, algoritmul euclidian extins
poate fi folosit pentru a găsi cea mai mare divizor comun al acestor 2 numere întregi.
Acesta va oferi, de asemenea, ne 2 numere, alte x și y,
care satisfac ecuația ax + by = cea mai mare divizor comun a a și b.
Cum acest lucru ne va ajuta?
Ei bine, conectarea la e = 5 pentru un
și m = 924 pentru b
știm deja că aceste numere sunt prime între ele.
Lor mai mare divizor comun este 1.
Acest lucru ne dă 5x + 924y = 1
sau 5x = 1 - 924y.
Dar, dacă ne pasă doar despre tot modulo 924
atunci putem picătură - 924y.
Gandeste-te la ceas.
Dacă minutarul este pe 1 și apoi exact 10 Orele trec,
știm minutarul va fi în continuare de la 1.
Aici, vom începe de la 1 și apoi înfășurați în jurul valorii de ori exact y,
deci vom fi în continuare la 1.
Avem 5x = 1 (mod 924).
Și aici, în această x este aceeași ca și d am fost cautati înainte,
așa că, dacă vom folosi algoritmul extins euclidiene
pentru a obține acest număr de x, care e numărul de noi ar trebui să utilizeze ca d nostru.
Acum, haideți să ruleze algoritmul euclidian extins pentru un termen de 5 =
și b = 924.
Vom folosi o metoda numita metoda de masa.
Masa noastră va avea 4 coloane, x, y, d, și k.
Masa noastră începe cu 2 rânduri.
În primul rând, avem 1, 0, atunci valoarea noastră de a, care este de 5,
și rândul al doilea este 0, 1, și valoarea noastră pentru b, care este 924.
Valoarea coloanei 4, K, va fi rezultatul
din împărțirea valorii d în rândul de mai sus, cu o valoare de d
pe același rând.
Avem 5 împărțit la 924 este 0, cu unele restul.
Asta înseamnă că avem k = 0.
Acum, valoarea fiecarei celule altele, vor fi valoarea celulei de 2 rânduri de mai sus,
minus valoarea rândului de mai sus, ori k.
Să începem cu d în rândul treia.
Avem 5 - 924 * 0 = 5.
Apoi, avem 0 - 1 * 0, care este 0
și 1 - 0 * 0, care este de 1.
Nu prea rău, așa că hai să trecem la rândul următor.
În primul rând avem nevoie de valoarea noastra de k.
924 împărțit la 5 = 184 cu unele rest,
astfel încât valoarea noastră pentru k este 184.
Acum 924 - 5 * 184 = 4.
1 - 0 * 184 este de 1 și 0 - 1 * 184 este -184.
În regulă, hai să facem rândul următor.
Valoarea noastră de k va fi 1 deoarece
5 împărțit la 4 = 1 cu unele restul.
Să completați în celelalte coloane.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
Și 1 la 184 * 1 este de 185.
Să vedem ce valoare a lui k următoarea noastră ar fi.
Ei bine, se pare ca avem 4, împărțită cu 1, care este de 4.
În acest caz, în cazul în care suntem împărțirea la 1, astfel încât k este egal cu
valoarea d în rândul de mai sus înseamnă că am terminat cu algoritmul nostru.
Putem vedea aici că avem x = 185 si y = -1 în ultimul rând.
Să vină acum la scopul nostru inițial.
Am spus că valoarea lui x, ca urmare a executării acestui algoritm
ar fi inversul multiplicativ de (mod b).
Asta înseamnă că 185 este inversul multiplicativ de 5 (mod 924)
ceea ce înseamnă că avem o valoare de 185 pentru d.
Faptul că d = 1 în ultimul rând
verifică faptul că e la m a fost prime între ele.
În cazul în care nu au fost cu 1, atunci am avea de a alege un nou e.
Acum, să vedem dacă Rob a primit mesajul meu.
Atunci când cineva trimite-mi un mesaj criptat
atâta timp cât am păstrat cheia privată un secret
Eu sunt singurul care poate decripta mesajul.
Pentru a decripta o bucată c pot calcula mesajul original
este egal cu bucată la putere d (mod n).
Amintiți-vă că d și n sunt de la cheia mea privată.
Pentru a obține un mesaj plin de bucăți de ei ne decripta fiecare bucată
și înlănțui rezultatele.
Exact cum sigur este RSA?
Adevărul este, nu știm.
Securitatea se bazează pe cât de mult va dura un atacator pentru a sparge un mesaj
criptate cu RSA.
Amintiți-vă că un atacator are acces la cheia dvs. publică,
care conține atât e și n.
În cazul în care atacatorul reușește să factor N în cele 2 prime, p și q,
atunci ea ar putea calcula cu ajutorul d algoritmul extins euclidian.
Acest lucru îi dă cheia privată, care poate fi folosit pentru a decripta orice mesaj.
Dar cât de repede putem factoriza numere întregi?
Din nou, nu știm.
Nimeni nu și-a găsit o modalitate rapidă de a face aceasta,
ceea ce înseamnă că, având suficient de mare n
ar fi nevoie de un atacator nerealist de timp
să țină numărul.
Dacă cineva a relevat o modalitate rapidă de numere întregi de factoring
RSA-ar fi rupt.
Dar, chiar dacă factorizare întreg este în mod inerent lentă
Algoritmul RSA ar putea avea încă unele defect în ea
care permite decriptarea pentru ușoară a mesajelor.
Nimeni nu a găsit și a descoperit un astfel de defect încă,
dar asta nu înseamnă că nu există.
În teorie, cineva ar putea fi acolo citind toate datele criptate cu RSA.
Există un alt pic de o problemă de confidențialitate.
În cazul în care unele Tommy criptează mesaj utilizând cheia mea publică
și un atacator criptează același mesaj folosind cheia mea publică
atacatorul va vedea că cele 2 mesaje sunt identice
și știu, astfel, ceea ce Tommy criptat.
În scopul de a preveni acest lucru, mesajele sunt de obicei căptușite cu biți aleatorii
înainte de a fi criptat, astfel încât același mesaj criptat
de mai multe ori va arăta diferit atâta timp cât padding pe mesajul este diferit.
Dar amintiți-vă cum trebuie să împartă mesaje în bucăți
astfel încât fiecare bucată este mai mic decât n?
Padding bucatile înseamnă că am putea avea de a împărți lucrurile
în bucăți și mai multe de la bucată căptușit trebuie să fie mai mic decât n.
Criptarea și decriptarea sunt relativ scumpe cu RSA,
și astfel au nevoie pentru a rupe în bucăți un mesaj in mai multe pot fi foarte costisitoare.
În cazul în care un volum mare de date trebuie să fie criptate și decriptate
putem combina beneficiile algoritmi cu chei simetrice
cu cele ale RSA pentru a obține atât securitatea și eficiența.
Deși nu vom intra în ea aici,
AES este un algoritm simetric cheie cum ar fi Vigenere și cifruri Cezar
dar mult mai greu de spart.
Desigur, nu putem folosi AES, fără a stabili o cheie partajată secretă
între cele 2 sisteme, și am văzut problema cu asta înainte.
Dar acum putem folosi RSA pentru a stabili cheia secretă partajată între cele 2 sisteme.
Vom suna la calculatorul care trimite datele expeditorului
și computerul care primește datele receptorului.
Receptorul are o pereche de chei RSA și trimite
cheia publică a expeditorului.
Expeditorul generează o cheie AES,
criptează cu cheia publică a receptorului RSA,
și trimite cheia AES la receptor.
Receptorul decriptează mesajul cu cheia privată RSA său.
Atât expeditor și destinatar au acum o comună cheie AES între ele.
AES, care este mult mai rapid la criptare și decriptare decât RSA,
poate fi acum folosit pentru a cripta volume mari de date și le trimite la receptor,
care poate decripta folosind aceeași cheie.
AES, care este mult mai rapid la criptare și decriptare decât RSA,
poate fi acum folosit pentru a cripta volume mari de date și le trimite la receptor,
care poate decripta folosind aceeași cheie.
Am avut nevoie de doar RSA pentru a transfera cheie partajată.
Nu mai avem nevoie de a utiliza RSA deloc.
Se pare ca am primit un mesaj.
Nu contează dacă cineva citește ceea ce este pe hârtie înainte de avion l-am prins
pentru că eu sunt singurul cu cheia privată.
Să decripta fiecare dintre bucăți în mesaj.
Bucată în primul rând, 658, vom ridica la putere d, care este de 185,
mod n, care este 989, este egală cu 67,
care este litera C în ASCII.
Acum, pe bucată secunde.
Bucată doilea are valoarea de 15,
care ne ridica la putere 185th,
Mod 989, iar acest lucru este egal cu 83
care este litera S în ASCII.
Acum, pentru bucată treia, care are o valoare 799, ne ridica la 185,
Mod 989, iar acest lucru este egal cu 53,
care este valoarea caracterului 5 în ASCII.
Acum, pentru ultima bucată, care are o valoare 975,
ne ridica la 185, Mod 989,
și acest lucru este egal cu 48, care este valoarea 0 caractere în ASCII.
Numele meu este Rob Bowden, iar acest lucru este CS50.
[CS50.TV]
RSA, la toate.
RSA, la toate. [Râsete]
La toate.