[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[Aquesta és CS50.] [CS50.TV]
Anem a fer una ullada a RSA, un algorisme utilitzat per xifrar dades.
Els algorismes de xifrat com César i sistemes de xifrat Vigenère no són molt segures.
Amb el xifrat César, un atacant només necessita tractar 25 diferents claus
per obtenir text sense format del missatge.
Mentre que el sistema de xifrat Vigenère és més segur que el xifrat César
per l'espai de consulta ample per les claus, una vegada que un atacant
coneix la longitud de la clau en un sistema de xifrat Vigenère,
que es pot determinar a través d'una anàlisi dels patrons en el text xifrat,
el xifrat Vigenère no és molt més segur que el xifrat César.
RSA, d'altra banda, no és vulnerable als atacs d'aquest tipus.
El xifrat César i xifrat Vigenère utilitzar la mateixa clau
per xifrar i desxifrar un missatge.
Aquesta propietat fa que aquests algorismes xifrats simètrics clau.
Un problema fonamental amb algorismes de clau simètrica
és que es basen en la codificació i l'enviament del missatge
i el que rep i desxifra el missatge
que ja han acordat per avançat en la clau que tots dos utilitzen.
Però tenim una mica d'un problema d'inici aquí.
Com dos equips que volen comunicar establir una clau secreta entre ells?
Si la clau ha de ser secret, llavors necessitem una manera de xifrar i desxifrar la clau.
Si tot el que tenim és la criptografia de clau simètrica
llavors he tornat al mateix problema.
RSA, d'altra banda, utilitza un parell de claus,
una per encriptació i un altre per desencriptació.
Un es diu la clau pública, i l'altre és la clau privada.
La clau pública s'utilitza per xifrar missatges.
Com es pot endevinar pel seu nom, podem compartir la nostra clau pública amb
qualsevol persona que vulgui sense comprometre la seguretat d'un missatge xifrat.
Els missatges xifrats amb una clau pública
només es pot desxifrar amb la seva clau privada corresponent.
Mentre que vostè pot compartir la seva clau pública, sempre s'ha de mantenir en secret la seva clau privada.
i només la clau privada es pot utilitzar per desxifrar els missatges
2 usuaris per enviar missatges de xifrat amb RSA
d'anada i tornada els usuaris necessiten tenir el seu propi parell de claus pública i privada.
Missatges d'usuari 1 a usuari 2
només utilitzen parell de claus d'usuari 2, i els missatges d'usuari a usuari febrer 1
només utilitzen un parell de claus d'usuari.
El fet que hi ha 2 tecles separades per xifrar i desxifrar missatges
RSA fa un algorisme de clau asimètrica.
No necessitem per xifrar la clau pública amb la finalitat d'enviar a un altre ordinador
ja que la clau pública és de totes maneres.
Això vol dir que RSA no té el mateix problema d'inici
com els algoritmes de clau simètrica.
Així que si vull enviar un missatge utilitzant xifrat RSA
a Rob, primer tindràs la clau pública de Rob.
Per generar un parell de claus, Rob ha de triar dos nombres primers grans.
Aquests números s'utilitzen tant en les claus públiques i privades,
però la clau pública només s'utilitza el producte d'aquests números 2,
no els números.
Quan hagi xifrat el missatge amb la clau pública de Rob
Puc enviar el missatge a Rob.
Per a un equip, els números de factoring és un problema difícil.
La clau pública, recorda, utilitza el producte de dos nombres primers.
Aquest producte ha de tenir només 2 factors,
que resulten ser els nombres que componen la clau privada.
Per tal de desxifrar el missatge, RSA s'utilitza aquesta clau privada
o els números multiplicats entre si en el procés de creació de la clau pública.
Com que és computacionalment difícil factoritzar el nombre
utilitzat en una clau pública en els 2 números utilitzats en la clau privada
és difícil per a un atacant desxifrar la clau privada
que serà necessari per desxifrar el missatge.
Ara entrarem en alguns detalls de menor nivell de RSA.
Primer veurem com podem generar un parell de claus.
En primer lloc, anem a necessitar dos nombres primers.
Anem a trucar a aquests números 2 p i q.
Per tal de recollir p i q, en la pràctica seudoaleatoria generaria
grans quantitats i aleshores utilitzar una prova per determinar si existeix o no
aquests nombres són probablement millor moment.
Podem mantenir la generació de nombres aleatoris i una altra
fins que tinguem dos cosins que podem utilitzar.
Aquí anem a escollir p = q = 23 i 43.
Recordeu, a la pràctica, p i q ha de ser un nombre molt més gran.
Pel que sabem, com més grans siguin els números, més difícil serà
per trencar un missatge xifrat.
Però també és més car per xifrar i desxifrar missatges.
Avui dia és sovint es recomana que p i q són almenys 1024 bits,
que posa a cada nombre en més de 300 dígits decimals.
Però anem a recollir aquests petits nombres d'aquest exemple.
Ara anem a multiplicar p i q en conjunt per obtenir un nombre de 3 º,
que anomenarem n.
En el nostre cas, n = 23 * 43, que = 989.
Tenim n = 989.
A continuació multiplicar p - 1 amb q - 1
per obtenir un nombre de quart, que anomenarem m.
En el nostre cas, m = 22 * ​​42, que = 924.
Comptem amb m = 924.
Ara anem a necessitar un nombre i que és primer amb m
i menys de m.
Dos nombres són primers relatius o primers entre si,
si el nombre enter únic positiu que els divideix de manera uniforme tant: 1.
En altres paraules, el màxim comú divisor de i i m
ha de ser 1.
A la pràctica, és comú que i sigui el nombre primer 65537
sempre que aquest nombre no passa de ser un factor de m.
Per a les claus, anem a recollir i = 5
ja que 5 és primer amb 924.
Finalment, anem a necessitar un nombre més, que anomenarem d.
D ha de ser un valor que satisfà l'equació de = 1 (mod m).
Aquest mod m significa que farem servir una cosa anomenada aritmètica modular.
En l'aritmètica modular, una vegada que rep un nombre més alt que algunes límit superior
que baixés a 0.
Un rellotge, per exemple, utilitza l'aritmètica modular.
Un minut després de 1:59, per exemple, és 2:00,
no 1:60.
El minutera s'ha embolicat al voltant de 0
en arribar a un límit superior de 60.
Per tant, podem dir que 60 és equivalent a 0 (mod 60)
i 125 és equivalent a 65 és equivalent a 5 (mod 60).
La nostra clau pública serà el parell electrònic i núm
on en aquest cas i és 5 i n a 989.
La nostra clau privada serà el parell d i n,
que en el nostre cas és de 185 i 989.
Observi que el nostre original de nombres primers p i q no apareixen
arreu de les nostres claus privades o públiques.
Ara que tenim el nostre parell de claus, anem a fer una ullada a com podem xifrar
i desxifrar un missatge.
Vull enviar un missatge a Rob,
pel que serà el de generar aquest parell de claus.
Llavors vaig a demanar Rob la seva clau pública, que utilitzaré
per xifrar un missatge per enviar a ell.
Recorda, és totalment acceptable per Rob per compartir la seva clau pública amb mi.
Però no estaria bé compartir la seva clau privada.
No tinc ni idea del que la seva clau privada.
Podem dividir el nostre missatge m cap amunt en diversos trossos
tot menor que n i després encriptar cada un dels trossos.
Anem a xifrar la cadena CS50, que podem dividir en 4 trossos,
un per cada lletra.
Per xifrar el missatge, vaig a haver de convertir-lo en
algun tipus de representació numèrica.
Anem a concatenar els valors ASCII amb els personatges del meu missatge.
Per tal de xifrar un missatge donat m
Vaig a haver de calcular c = ma l'E (mod n).
Però m ha de ser menor que n,
o bé el missatge complet no pot ser expressat mòdul núm.
Podem trencar m fins a diversos trossos, tots els quals són més petites que n,
i xifrar cada un dels trossos.
Xifrat de cada un d'aquests trossos, obtenim c1 = 67 a la 5 (mod 989)
que = 658.
Per al nostre segon fragment que tenim 83 a la 5 (mod 989)
que = 15.
Per al nostre tros 3 tenim 53 a la 5 (mod 989)
que és = 799.
I finalment, per al nostre tros fi tenim 48 a la 5 (mod 989)
que = 975.
Ara podem enviar a través d'aquests valors xifrats a Rob.
Aquí tens, Rob.
Mentre que el nostre missatge està en vol, anem a fer un altre cop d'ull
en com hem arribat fins a aquest valor per d.
El nostre número d necessària per satisfer 5d = 1 (mod 924).
Això fa que d l'invers multiplicatiu de 5 mòdul 924.
Atès 2 sencers, A i B, l'algorisme d'Euclides estès
es pot utilitzar per trobar el màxim comú divisor d'aquests 2 nombres enters.
També ens donen 2 altres números, x i i,
que satisfan l'equació ax + by = el màxim comú divisor de a i b.
Com ens ajuda?
Bé, connectar i = 5 per a una
i m = 924 per b
ja sabem que aquests nombres són primers entre si.
El seu màxim comú divisor és 1.
Això ens dóna 5x + 924y = 1
o 5x = 1 - 924y.
Però si només es preocupen per tot mòdul 924
llavors podem abandonar la - 924y.
Penseu en el rellotge.
Si el minuter està en 1 i després passar exactament 10 hores,
sabem que la maneta dels minuts encara serà al 1.
Aquí comencem a 1 i després embolicar vegades exactament de i,
de manera que encara estarà en 1.
Tenim 5x = 1 (mod 924).
I aquí aquesta x és el mateix que el d buscàvem abans,
pel que si s'utilitza l'algorisme d'Euclides estès
per obtenir aquest nombre x, que és el número que ha d'usar com el nostre d.
Ara anem a executar l'algorisme estès d'Euclides per a = 5
i b = 924.
Utilitzarem un mètode anomenat mètode de la taula.
La taula comptarà amb 4 columnes, x, i, d, k.
La nostra taula comença amb 2 files.
A la primera fila tenim 1, 0, llavors el nostre valor de a, que és 5,
i la nostra segona fila és 0, 1, i el nostre valor de b, que és 924.
El valor de la columna quarta, k, és el resultat
de dividir el valor de d a la fila de dalt amb el valor de d
en la mateixa fila.
Tenim 5 dividit per 924 és 0 amb alguna resta.
Això vol dir que tenim k = 0.
Ara el valor de totes les altres cèl · lules és el valor de la cel · la 2 files per sobre del
menys el valor de la fila per sobre d'ella k vegades.
Anem a començar amb d en la 3 ª fila.
Tenim 5-924 * 0 = 5.
Següent Tenim 0 - 1 * 0 que és 0
i 1 - 0 * 0 que és 1.
No està malament, així que passarem a la següent fila.
En primer lloc tenim el nostre valor de k.
924 dividit per 5 = 184 amb alguna resta,
pel que el nostre valor de k és 184.
Ara 924-5 * 184 = 4.
1-0 * 184 és 1 i 0 - 1 * 184 és -184.
Molt bé, farem la següent fila.
El nostre valor de k serà 1 perquè
5 dividit per 4 = 1 amb alguna resta.
Anem a omplir les altres columnes.
5-4 * 1 = 1.
0-1 * 1 = -1.
I 1-184 * 1 és de 185.
Anem a veure el que el nostre següent valor de k seria.
Bé, sembla que tenim 4 dividit per 1, que és 4.
En aquest cas en el qual estem dividint per 1 tal que k és igual a
el valor de d a la fila de dalt vol dir que hem acabat amb el nostre algorisme.
Podem veure aquí que tenim x = 185 iy = -1 en l'última fila.
Ara anem a tornar a la nostra meta original.
Hem dit que el valor de x, com a resultat de l'execució d'aquest algorisme
seria l'invers multiplicatiu d'un (b mod).
Això vol dir que 185 és l'invers multiplicatiu de 5 (mod 924)
el que significa que tenen un valor de 185 per d.
El fet que d = 1 en l'última fila
verifica que el correu va ser primers entre si a m.
Si no fos 1, llavors hauríem de triar un correu nou.
Ara veurem si Rob ha rebut el meu missatge.
Quan algú m'envia un missatge xifrat
sempre que he mantingut la meva clau privada en secret
Jo sóc l'única persona que pot desxifrar el missatge.
Per desxifrar un tros c puc calcular el missatge original
és igual a la quantitat de potència d (mod n).
Recordeu que d i n són de la meva clau privada.
Per obtenir un missatge ple dels seus fragments de desxifrar cada bloc
i concatenar els resultats.
Exactament què tan segur és RSA?
La veritat és que no ho sé.
La seguretat es basa en el temps que li prendria a un atacant desxifrar un missatge
encriptada amb RSA.
Recordeu que un atacant té accés a la seva clau pública,
que conté tant i i n.
Si l'atacant aconsegueix factoritzar n en els seus 2 cosins, p i q,
llavors podria calcular d usant el algorisme d'Euclides estès.
Això li dóna la clau privada, que es pot utilitzar per desxifrar qualsevol missatge.
Però la rapidesa podem factoritzar sencers?
Un cop més, no ho sé.
Ningú ha trobat una manera ràpida de fer-ho,
el que significa que donat n prou gran
que portaria a un atacant irrealment llarg
factoritzar el nombre.
Si algú revela una forma ràpida de factoritzar sencers
RSA es trencaria.
Però fins i tot si factorització d'enters és inherentment lent
l'algoritme RSA encara podria tenir algun defecte-hi
que permet la fàcil desxifrat de missatges.
Ningú ha trobat i revela una falla, però,
però això no vol dir que no n'hi ha un.
En teoria, algú podria estar per aquí llegint totes les dades xifrades amb RSA.
Hi ha una mica d'un problema de privacitat.
Si Tommy encripta algun missatge amb el meu clau pública
i un atacant xifra el missatge mateix amb la meva clau pública
l'atacant es veurà que els dos missatges són idèntics
i així saber el que Tommy xifrat.
Per tal d'evitar això, els missatges són típicament emplenat amb bits aleatoris
abans de ser xifrats perquè el mateix missatge xifrat
múltiples vegades serà diferent, sempre que el farciment en el missatge és diferent.
Però recorda com hem de dividir els missatges en trossos
de manera que cada fragment és menor que n?
Farciment els trossos vol dir que haguem de dividir les coses
en trossos encara més des del tros encoixinat ha de ser menor que n.
El xifrat i desxifrat són relativament cars amb RSA,
i per tant necessitat de trencar un missatge en trossos molts pot ser molt costós.
Si un gran volum de dades ha de ser xifrats i desxifrats
podem combinar els beneficis d'algorismes de clau simètrica
amb els de RSA per obtenir la seguretat i l'eficiència.
Encara que no vaig a entrar-hi aquí,
AES és un algorisme de clau simètrica com el xifrat Vigenère i César
però molt més difícil de rosegar.
Per descomptat, no podem usar AES sense establir una clau secreta compartida
entre els 2 sistemes i vam veure el problema amb això abans.
Però ara podem utilitzar RSA per establir la clau secreta compartida entre els 2 sistemes.
Anomenarem a l'ordinador que envia les dades del remitent
i l'equip que rep les dades del receptor.
El receptor té un parell de claus RSA i envia
la clau pública al remitent.
L'emissor genera una clau d'AES,
xifra amb la clau pública RSA del receptor,
i envia la clau AES per al receptor.
El receptor desxifra el missatge amb la seva clau privada RSA.
Tant l'emissor com el receptor tenen ara una clau compartida AES entre ells.
AES, que és molt més ràpid en el xifrat i desxifrat de RSA,
Ara es pot utilitzar per a xifrar les grans volums de dades i enviar-los al receptor,
que pot desxifrar utilitzant la mateixa clau.
AES, que és molt més ràpid en el xifrat i desxifrat de RSA,
Ara es pot utilitzar per a xifrar les grans volums de dades i enviar-los al receptor,
que pot desxifrar utilitzant la mateixa clau.
Només necessitàvem RSA per transferir la clau compartida.
Ja no necessita utilitzar RSA en absolut.
Sembla que tinc un missatge.
Tant se val si algú llegeix el que hi ha a l'avió de paper abans que em va cridar
perquè jo sóc l'únic que té la clau privada.
Anem a desxifrar cada un dels trossos en el missatge.
El primer tros, 658, elevem a la potència d, que és de 185,
mod n, que a 989, és igual a 67,
que és la lletra C en ASCII.
Ara, en el segon fragment.
El segon fragment té un valor 15,
que elevem a la potència 185,
mod 989, i això és igual a 83
que és la lletra S en ASCII.
Ja pel tros tercer, que té un valor 799, elevem a 185,
mod 989, i això és igual a 53,
que és el valor del caràcter ASCII en 5.
Ara, per a l'últim fragment, que té un valor 975,
elevem a 185, mod 989,
i això és igual a 48, que és el valor de 0 en el caràcter ASCII.
El meu nom és Rob Bowden, i això és CS50.
[CS50.TV]
RSA en absolut.
RSA en absolut. [Rialles]
En totes.