[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[Dit is CS50.] [CS50.TV]
Laten we eens een kijkje nemen op RSA, een veel gebruikte algoritme voor het versleutelen van gegevens.
Encryptie-algoritmen, zoals Caesar en Vigenère cijfers zijn niet erg veilig.
Met de Caesar cipher, een aanvaller hoeft alleen om te proberen 25 verschillende sleutels
om het bericht platte tekst te krijgen.
Terwijl de Vigenère cijfer is veiliger dan de Caesar cipher
vanwege de grotere zoekruimte voor sleutels, als een aanvaller
kent de lengte van de sleutel in een Vigenère cipher,
kan worden bepaald via een analyse van patronen in de versleutelde tekst,
de Vigenère cijfer is niet veel veiliger dan de Caesar cipher.
RSA, anderzijds, is niet gevoelig voor aanvallen als deze.
De Caesar cipher en Vigenère cipher dezelfde sleutel gebruiken
voor zowel coderen en decoderen van een bericht.
Deze eigenschap maakt deze cijfers symmetrische sleutel algoritmen.
Een fundamenteel probleem met symmetrische sleutel algoritmen
is dat ze op de een vercijferinrichting en te verzenden
en een ontvangende en decoderen van het bericht
reeds zijn overeengekomen vooraf op de toets zullen ze beide gebruiken.
Maar we hebben een beetje een opstartprobleem hier.
Hoe twee computers die willen communiceren vaststelling van een geheime sleutel tussen hen?
Als de sleutel moet geheim, dan moeten we een manier vinden om te coderen en decoderen van de sleutel.
Als alles wat we hebben is symmetrische sleutel cryptografie
dan hebben we gewoon terug naar het zelfde probleem.
RSA, anderzijds, gebruikt een sleutelpaar,
een voor codering en een voor decryptie.
Heet de publieke sleutel en de andere is de private sleutel.
De openbare sleutel wordt gebruikt om berichten te coderen.
Zoals je kunt raden door zijn naam, kunnen we onze publieke sleutel delen met
iedereen die we willen zonder afbreuk te doen aan de veiligheid van een gecodeerd bericht.
Berichten gecodeerd met een publieke sleutel
kunnen alleen worden gedecodeerd met de overeenkomstige prive sleutel.
Terwijl u kunt uw publieke sleutel te delen, moet u altijd uw persoonlijke sleutel geheim.
en alleen de private sleutel kan worden gebruikt voor het decoderen berichten
als 2 gebruikers willen om berichten te verzenden gecodeerd met RSA
heen en weer zowel de gebruikers nodig hebben om hun eigen publieke en private sleutelpaar hebben.
Berichten van gebruiker 1 naar gebruiker 2
alleen gebruik maken van de gebruiker 2's sleutelpaar, en berichten van gebruiker 2 naar gebruiker 1
alleen gebruik maken van sleutelpaar gebruiker 1's.
Het feit dat er twee afzonderlijke sleutels voor het coderen en decoderen van berichten
maakt RSA een algoritme voor asymmetrische sleutels.
We hoeven niet de openbare sleutel te versleutelen om het naar een andere computer
omdat de sleutel is publiek toch.
Dit betekent dat RSA niet hetzelfde opstartprobleem
als de symmetrische sleutel algoritmen.
Dus als ik een bericht met behulp van RSA-encryptie versturen
aan Rob, ik moet eerst de publieke sleutel van Rob.
Voor het genereren van een paar sleutels, Rob moet halen 2 grote priemgetallen.
Deze nummers worden gebruikt in zowel de publieke als private sleutels,
maar de publieke sleutel zal alleen gebruik maken van het product van deze 2 nummers,
niet de getallen zelf.
Zodra ik heb gecodeerd het bericht met behulp van de openbare sleutel van Rob
Ik kan het bericht naar Rob.
Voor een computer, factoring nummers is een moeilijk probleem.
De publieke sleutel weet, gebruikt het product van twee priemgetallen.
Dit product moet dan slechts twee factoren,
die toevallig de getallen die het private sleutel.
Om het bericht te ontcijferen, zal RSA Gebruik deze private sleutel
of de getallen met elkaar vermenigvuldigd in het maken van de openbare sleutel.
Omdat het rekenkundig moeilijk factor wordt het aantal
gebruikt in een publieke sleutel in de 2 referentienummers in de private key
het is moeilijk voor een aanvaller te achterhalen van de private sleutel
dat nodig zal het bericht te ontcijferen.
Laten we nu eens gaan in een aantal lager niveau details van RSA.
Laten we eerst eens kijken hoe we een paar sleutels te genereren.
Ten eerste, moeten we twee priemgetallen.
We noemen deze 2 getallen p en q.
Om p en q, neemt in de praktijk zouden we pseudorandomly genereren
grote aantallen en gebruik vervolgens een test voor het bepalen van het al dan niet
deze getallen zijn waarschijnlijk prime.
We kunnen het genereren van willekeurige getallen te houden over en weer
totdat we hebben 2 priemgetallen die we kunnen gebruiken.
Hier laten we pick p = 23 en q = 43.
Herinner in de praktijk moeten p en q veel grotere aantallen.
Voor zover we weten, hoe groter de getallen, hoe moeilijker het is
een versleuteld bericht kraken.
Maar het is ook duurder om te coderen en decoderen van berichten.
Vandaag de dag is vaak aanbevolen dat p en q zijn minstens 1024 bits,
die legt elk nummer op meer dan 300 decimale cijfers.
Maar we halen deze kleine aantallen voor dit voorbeeld.
Nu we samen vermenigvuldigen p en q om een ​​3e nummer te krijgen,
die we bellen n.
In ons geval n = 23 * 43, 989 =.
We hebben n = 989.
Nu gaan we vermenigvuldigen p - 1 met q - 1
naar een 4e nummer, dat we bellen m te verkrijgen.
In ons geval m = 22 * ​​42 = 924 hetgeen.
We hebben m = 924.
Nu gaan we behoefte aan een aantal e dat relatief priem om m
en minder dan m.
Twee nummers zijn relatief priem of relatief priem
als het enige positieve integer die hen scheidt beide gelijkmatig 1.
Met andere woorden, de grootste gemene deler van e en m
moet 1.
In de praktijk is het vaak voor e als de priemgetal 65537
Zolang dit nummer niet toevallig een factor m bedragen.
Voor onze sleutels, we halen e = 5
sinds 5 is relatief priem tot 924.
Tot slot, moeten we nog een nummer, dat we bellen d.
D moet een waarde die de vergelijking voldoet aan zijn de = 1 (mod m).
Deze mod m betekent dat we zullen gebruiken iets genaamd modulaire rekenkunde.
In modulaire rekenkunde, zodra een aantal wordt hoger dan sommige bovengrens
het zal wrap terug rond naar 0.
Een klok, gebruikt bijvoorbeeld modulaire rekenkunde.
Een minuut na 1:59, is bijvoorbeeld 2:00,
niet 1:60.
De minutenwijzer zijn rond naar 0
bij het bereiken van een bovengrens van 60.
Dus kunnen we zeggen 60 is gelijk aan 0 (mod 60)
en 125 is gelijk aan 65 is gelijk aan 5 (mod 60).
Onze publieke sleutel zal het paar e en n zijn
waarbij in dit geval is e n is 5 en 989.
De prive-sleutel zal het paar d en n,
in ons geval is 185 en 989.
Merk op dat onze oorspronkelijke priemgetallen p en q niet verschijnen
overal in onze private of publieke sleutels.
Nu dat we onze paar toetsen hebben, laten we eens kijken hoe we kunnen coderen
en decoderen van een bericht.
Ik wil een bericht sturen naar Rob,
dus hij zal de eerste om dit sleutelpaar genereren.
Dan zal ik vragen Rob voor zijn publieke sleutel, die ik gebruik
een bericht te sturen om hem te coderen.
Vergeet niet, het is helemaal goed voor Rob om zijn publieke sleutel met mij te delen.
Maar het zou niet goed is om zijn private sleutel te delen.
Ik heb geen idee wat zijn prive-sleutel is.
We kunnen breken onze boodschap m in meerdere stukken
alle kleiner dan n en coderen elk van deze brokken.
We coderen de string CS50, die we kunnen opbreken in 4 stukken,
een per letter.
Met het oog op mijn bericht te versleutelen, zal ik nodig om het om te zetten in
een soort numerieke weergave.
Laten we samenvoegen van de ASCII-waarden met de personages in mijn boodschap.
Om een ​​bepaald bericht m versleutelen
Ik moet c = m berekenen de e (mod n).
Maar m moet kleiner zijn dan n,
of anders het volledige bericht kan niet worden uitgedrukt modulo n.
We kunnen breken m in meerdere stukken, die kleiner zijn dan n,
en coderen elk van deze brokken.
Coderen elk van deze stukjes, krijgen we c1 = 67 naar de 5 (mod 989)
waarin = 658.
Voor ons tweede stuk hebben we 83 tot en met de 5 (mod 989)
waarin = 15.
Voor onze derde stuk hebben we 53 tot de 5 (mod 989)
die = 799.
En tenslotte, voor onze laatste stuk hebben we 48 tot en met de 5 (mod 989)
waarin = 975.
Nu kunnen we sturen deze gecodeerde waarden aan Rob.
Hier ga je, Rob.
Terwijl onze boodschap is tijdens de vlucht, laten we nog eens kijken
hoe we die waarde voor d.
Ons nummer d nodig is om 5d = 1 (mod 924) voldoen.
Hierdoor d de multiplicatieve inverse modulo van 5 924.
Gezien 2 gehele getallen a en b, de uitgebreide Euclidische algoritme
kunnen worden gebruikt om de grootste gemene deler van deze twee getallen te vinden.
Het zal ons ook twee andere getallen x en y,
dat voldoet aan de vergelijking ax + by = de grootste gemene deler van a en b.
Hoe werkt dit ons helpen?
Nou, het aansluiten van e = 5 voor een
en m = 924 voor b
we weten al dat deze aantallen relatief priem zijn.
Hun grootste gemene deler is 1.
Dit geeft ons 5x + 924y = 1
of 5x = 1 - 924y.
Maar als we alleen de zorg over alles modulo 924
dan kunnen we laten vallen - 924y.
Denk terug aan de klok.
Als de grote wijzer is op 1 en vervolgens precies 10 uur zijn verstreken,
we weten dat de minutenwijzer nog steeds op 1.
Hier zijn we beginnen bij 1 en daar dan omheen wikkelen precies y keer,
dus we zullen nog steeds op 1.
We hebben 5x = 1 (mod 924).
En hier deze x is hetzelfde als de d die we zochten voor,
dus als we gebruik maken van de uitgebreide Euclidische algoritme
om dit getal x, dat is het nummer dat we moeten gebruiken als onze d.
Laten we nu lopen de uitgebreide Euclidische algoritme voor a = 5
en b = 924.
We zullen gebruik maken van een methode genaamd de tafel methode.
De tabel zal 4 kolommen, x, y, d en k.
Onze tafel begint met 2 rijen.
In de eerste rij die we hebben 1, 0, dan is onze waarde van een, dat is 5,
en de tweede rij 0, 1 en onze waarde b, wat 924.
De waarde van de 4e kolom k, zal het resultaat
verdelen de waarde van d in de rij erboven met de waarde van d
op dezelfde rij.
We hebben 5 gedeeld door 924 is 0 met wat rest.
Dat betekent dat we k = 0.
Nu de waarde van iedere andere cel wordt de waarde van de cel 2 rijen boven het
minus de waarde van de rij erboven keer k.
Laten we beginnen met d in de 3e rij.
We hebben 5 tot 924 * 0 = 5.
Vervolgens hebben we 0 - 1 * 0 die is 0
en 1 - 0 * 0 dat 1.
Niet al te slecht, dus laten we verder gaan naar de volgende rij.
Eerst moeten we onze waarde van k.
924 gedeeld door 5 = 184 met enige overige
zodat onze waarde voor k is 184.
Nu 924-5 * 184 = 4.
1 tot 0 * 184 is 1 en 0 - 1 * 184 is -184.
Oke, laten we het doen de volgende rij.
De waarde van k is 1 omdat
5 gedeeld door 4 = 1 met enkele rest.
Laten we vullen in de andere kolommen.
5-4 * 1 = 1.
0-1 * 1 = -1.
En 1 - 184 * 1 185.
Laten we eens kijken wat onze volgende waarde van k zou zijn.
Nou, het lijkt erop dat we hebben 4 gedeeld door 1, dat is 4.
In dit geval we delen door 1 zodanig dat k gelijk is aan
de waarde van d in de bovenstaande rij betekent dat we klaar zijn met ons algoritme.
We kunnen hier zien dat we x = 185 en y = -1 hebben in de laatste rij.
Laten we nu terugkeren naar onze oorspronkelijke doel.
We zeggen dat de waarde van x als gevolg van dit algoritme draait
zou de multiplicatieve inverse van een (b mod) zijn.
Dat betekent dat 185 is de multiplicatieve inverse van 5 (mod 924)
Dit betekent dat we een waarde van 185 voor d hebben.
Het feit dat d = 1 in de laatste rij
controleert of e werd relatief priem aan m.
Als het niet 1 dan zouden we een nieuwe e kiezen.
Laten we nu eens kijken of Rob heeft ontvangen mijn boodschap.
Wanneer iemand mij een gecodeerd bericht
Zolang ik hield mijn persoonlijke sleutel een geheim
Ik ben de enige die dat kan het bericht decoderen.
Te decoderen een stuk c ik kan berekenen het originele bericht
gelijk is aan het stuk om d vermogen (mod n).
Vergeet niet dat d en n van mijn persoonlijke sleutel.
Om een ​​volledige boodschap van haar brokken we decoderen elk blok
en samenvoegen van de resultaten.
Precies hoe veilig is RSA?
De waarheid is, weten we niet.
De beveiliging is gebaseerd op hoe lang het zou een aanvaller om een ​​bericht te kraken
versleuteld met RSA.
Vergeet niet dat een aanvaller toegang heeft tot uw publieke sleutel heeft,
welke bevat zowel e en n.
Als de aanvaller erin slaagt om n factor in de 2 priemgetallen, p en q,
dan kon ze berekenen d met behulp van de uitgebreide Euclidische algoritme.
Dit geeft haar private sleutel, die kunnen worden gebruikt voor het decoderen van een bericht.
Maar hoe snel kunnen we factor gehele getallen?
Nogmaals, weten we niet.
Niemand heeft gevonden een snelle manier van doen,
hetgeen betekent dat bij voldoende grote n
het zou een aanvaller onrealistisch lange
het aantal factor.
Als iemand bleek een snelle manier van factoring gehele getallen
RSA zou worden verbroken.
Maar zelfs als integer factorisatie is inherent traag
het RSA-algoritme wel wat fout nog steeds in het
dat zorgt voor eenvoudige decodering van berichten.
Niemand heeft gevonden en onthulde zulke fouten nog niet,
maar dat betekent niet dat deze niet bestaat.
In theorie zou iemand er uit het lezen van alle data versleuteld met RSA.
Er is nog een beetje een privacy probleem.
Als Tommy versleutelt een boodschap met behulp van mijn publieke sleutel
en een aanvaller versleutelt dezelfde boodschap met behulp van mijn publieke sleutel
de aanvaller zal zien dat de 2 berichten identiek zijn
en dus weet wat Tommy gecodeerd.
Om dit te voorkomen, worden berichten meestal gevuld met willekeurige bits
alvorens te worden gecodeerd, zodat het dezelfde boodschap gecodeerd
meerdere keren zal anders uitzien zolang de inleg van het bericht anders.
Maar vergeet niet hoe we moeten boodschappen te splitsen in stukken
zodat elk blok kleiner is dan n?
Opvulling van de brokken betekent dat we zouden hebben om dingen te splitsen
in nog meer stukken, omdat de gecapitonneerde stuk moet kleiner zijn dan n.
Encryptie en decryptie zijn relatief duur met RSA,
en dus om breken Bericht in vele stukjes kunnen zeer kostbaar zijn.
Indien een grote hoeveelheid gegevens moet worden gecodeerd en gedecodeerd
we kunnen de voordelen van symmetrische sleutelalgoritmen
met die van RSA om zowel de veiligheid en efficiëntie te krijgen.
Hoewel we hier niet op in,
AES is een symmetrische sleutel algoritme, zoals de Vigenère en Caesar cijfers
maar veel moeilijker te kraken.
Natuurlijk kunnen we geen gebruik maken van AES zonder de oprichting van een gedeelde geheime sleutel
tussen de 2 systemen, en we zagen het probleem met dat vóór.
Maar nu kunnen we gebruik maken van RSA om de gedeelde geheime sleutel tussen de 2 systemen op te zetten.
We bellen de computer het versturen van de gegevens van de afzender
en de computer die de gegevens van de ontvanger.
De receiver heeft een RSA-sleutelpaar en stuurt
de publieke sleutel van de verzender.
De zender genereert een AES toets
versleutelt het met RSA de ontvanger de publieke sleutel,
en stuurt de AES om de ontvanger.
De ontvanger decodeert het bericht met zijn private sleutel RSA.
Zowel de zender als de ontvanger hebben nu een gedeelde AES-sleutel tussen hen.
AES, die veel sneller op dan encryptie en decryptie RSA,
kan nu gebruikt worden om de grote hoeveelheden data te versleutelen en verzenden naar de ontvanger,
wie kan decoderen met behulp van dezelfde toets.
AES, die veel sneller op dan encryptie en decryptie RSA,
kan nu gebruikt worden om de grote hoeveelheden data te versleutelen en verzenden naar de ontvanger,
wie kan decoderen met behulp van dezelfde toets.
We moesten RSA om de gedeelde sleutel over te dragen.
We hoeven niet langer te RSA te gebruiken.
Het lijkt erop dat ik heb een boodschap.
Het maakt niet uit of iemand lezen wat er op het papier vliegtuig voordat ik ving hem
want ik ben de enige met de private sleutel.
Laten decoderen elk van de blokken in het bericht.
De eerste stuk, 658, verhogen we de d macht, die is 185,
mod n, die 989, gelijk aan 67,
dat is de letter C in ASCII.
Nu, op de tweede brok.
De tweede stuk heeft waarde 15,
dat we te maken tegen de 185e macht
mod 989, en dit is gelijk aan 83
dat is de letter S in ASCII.
Nu voor de derde stuk, welke waarde 799 heeft, we verhogen tot 185,
mod 989, en dit is gelijk aan 53,
Dit is de waarde van het teken 5 in ASCII.
Nu voor de laatste brok, dat heeft waarde 975,
we verhogen tot 185, mod 989,
en dit is gelijk aan 48, die van het teken 0 in ASCII.
Mijn naam is Rob Bowden, en dit is CS50.
[CS50.TV]
RSA helemaal.
RSA helemaal. [Gelach]
Helemaal.