[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[Detta är CS50.] [CS50.TV]
Låt oss ta en titt på RSA, en allmänt använd algoritm för kryptering av data.
Krypteringsalgoritmer som Caesar och Vigenère chiffer är inte mycket säker.
Med Caesar chiffer, behöver en angripare bara för att prova 25 olika nycklar
att få ut budskapet är oformaterad text.
Medan Vigenère chiffer är säkrare än Caesar chiffer
på grund av den större sökrymden för nycklar, när en angripare
vet längden på nyckeln i en Vigenère chiffer,
vilket kan avgöras genom en analys av mönster i den krypterade texten,
den Vigenère chiffer är inte så mycket säkrare än Caesar chiffer.
RSA, å andra sidan, är inte sårbar för attacker som denna.
Caesar chiffer och Vigenère chiffer använda samma nyckel
både kryptera och dekryptera ett meddelande.
Denna egenskap gör dessa chiffer symmetriska nyckel algoritmer.
Ett grundläggande problem med symmetrisk nyckel algoritmer
är att de förlitar sig på en kryptering och skicka meddelandet
och en mottagande och dekryptering av meddelandet
att redan överenskomna förskott på nyckeln kommer de båda använder.
Men vi har en bit av en start problem här.
Hur skapa 2 datorer som vill kommunicera en hemlig nyckel mellan dem?
Om nyckeln måste vara hemliga, så vi behöver ett sätt att kryptera och dekryptera nyckeln.
Om allt vi har är symmetrisk nyckel kryptografi
då vi har precis kommit tillbaka till samma problem.
RSA, å andra sidan, använder ett nyckelpar,
en för kryptering och en annan för dekryptering.
Den ena kallas den publika nyckeln, och den andra är den privata nyckeln.
Den offentliga nyckeln används för att kryptera meddelanden.
Som du kan gissa av namnet, kan vi dela med oss ​​av publika nyckel med
vem vi vill utan att äventyra säkerheten för ett krypterat meddelande.
Meddelanden som krypteras med en publik nyckel
kan endast dekrypteras med motsvarande privata nyckel.
Även om du kan dela din publika nyckel, bör du alltid hålla din privata nyckel hemlig.
och endast den privata nyckeln kan användas för att dekryptera meddelanden
Om 2 användare vill skicka meddelanden krypterade med RSA
fram och tillbaka både användare måste ha sin egen offentliga och privata nyckelpar.
Meddelanden från användare 1 till användare 2
endast använda användarens 2 är nyckelpar och meddelanden från användare 2 till användare 1
Använd endast användare 1: s nyckelpar.
Det faktum att det finns 2 separata nycklar för att kryptera och dekryptera meddelanden
gör RSA en asymmetrisk nyckel algoritm.
Vi behöver inte kryptera den publika nyckeln för att skicka den till en annan dator
eftersom nyckeln är öppen ändå.
Detta innebär att RSA inte har samma startproblemet
som de symmetriska nyckel algoritmer.
Så om jag vill skicka ett meddelande med RSA-kryptering
att Rob, jag måste först Robs publika nyckel.
För att generera ett nyckelpar behöver Rob att plocka 2 stora primtal.
Dessa siffror kommer att användas i både den offentliga och privata nycklar,
men den publika nyckeln kommer endast att använda produkten av dessa 2 siffror,
inte själva siffran.
När jag har krypterat meddelandet med Rob publika nyckel
Jag kan skicka meddelandet till Rob.
För en dator är factoring nummer ett svårt problem.
Den publika nyckeln, kom ihåg, använde produkten av 2 primtal.
Denna produkt måste sedan ha bara 2 faktorer,
som råkar vara de nummer som utgör den privata nyckeln.
För att dekryptera meddelandet kommer RSA att använda denna privata nyckel
eller siffrorna multipliceras tillsammans i processen för att skapa den publika nyckeln.
Eftersom det är beräkningsmässigt svårt att räkna antalet
används i en publik nyckel till de 2 numren som används i den privata nyckeln
det är svårt för en angripare att räkna ut den privata nyckeln
som kommer att vara nödvändig för att dekryptera meddelandet.
Nu går i vissa lägre nivå detaljer i RSA.
Låt oss först se hur vi kan skapa ett nyckelpar.
Först behöver vi 2 primtal.
Vi ringer dessa 2 nummer p och q.
För att plocka p och q, i praktiken skulle vi pseudoslumpmässigt generera
stort antal och sedan använda ett test för att bestämma huruvida eller ej
dessa siffror är förmodligen Prime.
Vi kan fortsätta generera slumptal om och om igen
tills vi har 2 primtal som vi kan använda.
Här ska vi plocka p = 23 och q = 43.
Kom ihåg att, i praktiken, bör p och q vara mycket större antal.
Så vitt vi vet, desto större siffrorna, desto svårare är det
att knäcka ett krypterat meddelande.
Men det är också dyrare att kryptera och dekryptera meddelanden.
Idag är det ofta rekommenderas att p och q är minst 1024 bitar,
som sätter varje nummer på över 300 decimaler.
Men vi hämtar dessa små siffror för detta exempel.
Nu ska vi multiplicera p och q tillsammans för att få en 3: e nummer,
som vi kallar n.
I vårt fall, n = 23 * 43, vilket = 989.
Vi har n = 989.
Nästa vi multiplicera p - 1 med q - 1
att få en 4: e nummer, som vi kallar m..
I vårt fall, m = 22 * ​​42, vilket = 924.
Vi har m = 924.
Nu ska vi behöva ett antal e som är relativt prima till m
och mindre än m..
Två nummer är relativt prima eller coprime
om det enda positiva heltal som delar dem båda jämnt är 1.
Med andra ord, den största gemensamma delaren av e och m
måste vara 1.
I praktiken är det vanligt att e att vara primtal 65.537
så länge detta nummer inte råkar vara en faktor av m.
För våra nycklar, vi plockar e = 5
sedan 5 är relativt primtal till 924.
Slutligen behöver vi en mer nummer, som vi kallar d..
D måste vara ett värde som uppfyller ekvationen de = 1 (mod m).
Denna mod m innebär att vi kommer att använda något som kallas modulär aritmetik.
I modulär aritmetik, får gång ett nummer högre än vissa övre gräns
det kommer att svepa tillbaka runt till 0.
En klocka, till exempel, använder modulär aritmetik.
En minut efter 1:59, till exempel, är 2:00,
inte 1:60.
Minutvisaren har fastnat runt till 0
på att nå en övre gräns på 60.
Så kan vi säga 60 motsvarar 0 (mod 60)
och 125 är ekvivalent med 65 motsvarar 5 (mod 60).
Vår offentliga nyckel blir paret e och n
där i detta fall e är 5 och n är 989.
Vår privata nyckel blir paret d och n,
som i vårt fall är 185 och 989.
Observera att vår ursprungliga primtal p och q visas inte
någonstans i våra privata eller offentliga nycklar.
Nu när vi har vår nyckelpar, låt oss ta en titt på hur vi kan kryptera
och dekryptera ett meddelande.
Jag vill skicka ett meddelande till Rob,
så han kommer att vara en att skapa detta nyckelpar.
Då ska jag be Rob för hans publika nyckel, som jag kommer att använda
att kryptera ett meddelande att skicka till honom.
Kom ihåg, det är helt okej för Rob att dela sin publika nyckel med mig.
Men det skulle inte vara okej att dela hans privata nyckel.
Jag har ingen aning om vad hans privata nyckel är.
Vi kan bryta vårt budskap m upp i flera bitar
alla mindre än n och sedan kryptera varje av dessa bitar.
Vi ska kryptera strängen CS50, som vi kan bryta upp i 4 bitar,
en per bokstav.
För att kryptera mitt budskap, jag behöver konvertera den till
någon form av numerisk representation.
Låt oss slå samman de ASCII-värden med karaktärerna i mitt budskap.
För att kryptera ett givet meddelande m
Jag behöver att beräkna c = m till e (mod n).
Men m måste vara mindre än n,
annars hela meddelandet inte kan uttryckas modulo n.
Vi kan bryta m upp i flera bitar, som alla är mindre än n,
och kryptera varje av dessa bitar.
Kryptera alla dessa bitar får vi c1 = 67 till 5 (mod 989)
vilken = 658.
För vår andra bit har vi 83 till 5 (mod 989)
vilket = 15.
För vår tredje bit har vi 53 till 5 (mod 989)
vilket = 799.
Och slutligen, för vår sista bit har vi 48 till 5 (mod 989)
som = 975.
Nu kan vi skicka över dessa krypterade värden till Rob.
Här har du, Rob.
Medan vårt budskap är i luften, låt oss ta en titt
hur vi fick det värdet för d.
Vår nummer d behövs för att uppfylla 5d = 1 (mod 924).
Detta gör d. den multiplikativa inversen av 5 modulo 924.
Med tanke på 2 heltal, A och B, den förlängda Euklides algoritm
kan användas för att hitta den största gemensamma nämnaren för dessa 2 heltal.
Det kommer också att ge oss 2 andra tal, x och y,
som uppfyller ekvationen ax + by = den största gemensamma delaren av a och b.
Hur hjälper det oss?
Tja, koppla in e = 5 för en
och m = 924 för b
Vi vet redan att dessa siffror är coprime.
Deras största gemensamma delare är 1.
Detta ger oss 5x + 924y = 1
eller 5x = 1 - 924y.
Men om vi bryr bara om allt modulo 924
då kan vi släppa - 924y.
Tänk tillbaka till klockan.
Om minutvisaren är på 1 och sedan exakt 10 timmar ska
vi vet minutvisaren fortfarande kommer att vara på 1.
Här börjar vi på 1 och sedan linda runt exakt y gånger,
så vi kommer fortfarande vara 1.
Vi har 5x = 1 (mod 924).
Och här i x är samma som d vi letade efter innan,
så om vi använder den förlängda Euklides algoritm
att få det här numret X, det är det antal vi ska använda som vår d..
Nu ska vi köra den utökade Euklides algoritm för a = 5
och b = 924.
Vi kommer att använda en metod som kallas tabell metoden.
Vårt bord har 4 kolumner, x, y, d och k..
Vårt bord börjar med 2 rader.
I den första raden har vi 1, 0, då vår värdet av en, vilket är 5,
och våra andra raden är 0, 1 och vårt värde för b, vilket är 924.
Värdet på den 4: e kolumnen, k, blir resultatet
att dela upp värdet på d i raden ovanför det med värdet av d
på samma rad.
Vi har 5 delat med 924 är 0 med viss resten.
Det innebär att vi har k = 0.
Nu värdet på varje annan cell blir värdet på cellen 2 rader ovanför det
minus värdet på raden ovanför den tid k..
Låt oss börja med d i 3: e raden.
Vi har från 5 till 924 * 0 = 5.
Sedan har vi från 0 till 1 * 0, som är 0
och 1 - 0 * 0, som är 1.
Inte alltför illa, så låt oss gå vidare till nästa rad.
Först behöver vi vårt värde på K.
924 dividerat med 5 = 184 med viss resten,
så vårt värde för k är 184.
Nu 924 till 5 * 184 = 4.
1 till 0 * 184 är 1 och 0 till 1 * 184 är -184.
Okej, låt oss göra nästa rad.
Vår värdet av k blir 1 eftersom
5 dividerat med 4 = 1 med vissa resten.
Låt oss fylla i de andra kolumnerna.
5 till 4 * 1 = 1.
0 till 1 * 1 = -1.
Och 1 - 184 * 1 är 185.
Låt oss se vad vår nästa värde på k skulle vara.
Det ser ut som om vi har 4 delat med 1, vilket är 4.
I det här fallet där vi dividera med 1 så att k är lika med
Värdet på d i ovanstående raden betyder att vi är klara med vår algoritm.
Vi kan här se att vi har x = 185 och y = -1 i den sista raden.
Låt oss nu komma tillbaka till vår ursprungliga målsättning.
Vi sa att värdet på x som en följd av att köra denna algoritm
skulle vara den multiplikativa inversen av en (mod B).
Det innebär att 185 är den multiplikativa inversen av 5 (mod 924)
vilket innebär att vi har ett värde på 185 för d.
Det faktum att d = 1 i den sista raden
verifierar att e var coprime till m.
Om det inte vore 1 då vi skulle behöva välja en ny e.
Nu ska vi se om Rob har fått mitt budskap.
När någon skickar mig ett krypterat meddelande
så länge jag har hållit min privata nyckel hemlig
Jag är den enda som kan dekryptera meddelandet.
För att dekryptera en bit c jag kan räkna det ursprungliga meddelandet
är lika med den bit till d effekt (mod n).
Kom ihåg att d och n är från min privata nyckel.
För att få en fullständig budskap från sina bitar vi dekryptera varje bit
och konkatenera resultaten.
Exakt hur säker är RSA?
Sanningen är, vet vi inte.
Säkerhet bygger på hur lång tid det skulle ta en angripare att knäcka ett meddelande
krypteras med RSA.
Kom ihåg att en angripare har tillgång till din publika nyckel,
vilken innehåller både e och n.
Om angriparen lyckas faktor N i sina 2 primtal, p och q,
då kunde hon räkna d med den utökade Euklides algoritm.
Detta ger henne den privata nyckeln, som kan användas för att dekryptera ett meddelande.
Men hur snabbt kan vi räkna heltal?
Återigen vet vi inte.
Ingen har hittat ett snabbt sätt att göra det,
vilket innebär att givet tillräckligt stora n
det skulle ta en angripare orealistiskt lång
att räkna antalet.
Om någon visade ett snabbt sätt för factoring heltal
RSA skulle brytas.
Men även om heltal faktorisering sig är långsam
RSA-algoritmen kan fortfarande ha några fel i den
som möjliggör enkel dekryptering av meddelanden.
Ingen har hittat och avslöjade en sådan brist ännu,
men det betyder inte att man inte existerar.
I teorin kan någon vara där ute läser alla data krypteras med RSA.
Det finns en annan lite privatliv fråga.
Om Tommy krypterar några budskap med min publika nyckel
och en angripare krypterar samma meddelande med min publika nyckel
angriparen kommer att se till att de 2 meddelanden är identiska
och därmed vet vad Tommy krypterad.
För att förhindra detta är meddelanden oftast vadderade med slumpmässiga bitar
innan de krypteras så att samma meddelande krypteras
flera gånger kommer att se annorlunda så länge stoppning på meddelandet är annorlunda.
Men kom ihåg att vi måste dela upp meddelanden i bitar
så att varje bit är mindre än n?
Utfyllnad bitarna innebär att vi kanske måste dela upp saker
till ännu fler bitar sedan stoppade bit måste vara mindre än n.
Kryptering och dekryptering är relativt dyra med RSA,
och så behöva bryta upp ett budskap i många bitar kan bli mycket kostsamt.
Om en stor mängd data måste krypteras och dekrypteras
Vi kan kombinera fördelarna med symmetrisk nyckel algoritmer
med de RSA för att få både säkerhet och effektivitet.
Även om vi inte kommer att gå in i det här,
AES är en symmetrisk nyckel algoritm som Vigenère och Caesar chiffer
men mycket svårare att knäcka.
Naturligtvis kan vi inte använda AES utan att etablera en gemensam hemlig nyckel
mellan de 2 systemen, och vi såg problem med det förut.
Men nu kan vi använda RSA för att upprätta den delade hemliga nyckeln mellan de 2 systemen.
Vi ringer den dator som skickar uppgifterna avsändaren
och datorn som mottar data mottagaren.
Mottagaren har en RSA-nyckelpar och skickar
den publika nyckeln till avsändaren.
Avsändaren genererar en AES-nyckel,
krypterar det med mottagarens RSA publik nyckel,
och sänder AES-nyckel till mottagaren.
Mottagaren dekrypterar meddelandet med sin privata RSA-nyckel.
Både avsändaren och mottagaren har nu en gemensam AES-nyckel mellan dem.
AES, vilket är mycket snabbare på kryptering och dekryptering än RSA,
kan nu användas för att kryptera de stora datamängder och skicka dem till mottagaren,
som kan dekryptera med samma nyckel.
AES, vilket är mycket snabbare på kryptering och dekryptering än RSA,
kan nu användas för att kryptera de stora datamängder och skicka dem till mottagaren,
som kan dekryptera med samma nyckel.
Vi behövde bara RSA för att överföra den delade nyckeln.
Vi behöver inte längre använda RSA alls.
Det ser ut som jag har ett meddelande.
Det spelar ingen roll om någon läser vad som finns på papper flygplan innan jag fick det
eftersom jag är den enda med den privata nyckeln.
Låt oss dekryptera varje bitar i meddelandet.
Den första bit, 658, höjer vi till d makten, vilket är 185,
mod n, vilket är 989, är lika med 67,
vilket är bokstaven C i ASCII.
Nu, på den andra bit.
Den andra bit har värdet 15,
som vi höjer till 185. effekt,
mod 989, och detta är lika med 83
vilket är bokstaven S i ASCII.
Nu för tredje bit, som har värdet 799, höjer vi till 185,
mod 989, och detta är lika med 53,
vilket är värdet av tecknet 5 i ASCII.
Nu till den sista bit, som har värdet 975,
Vi höjer till 185, mod 989,
och detta är lika med 48, vilket är värdet av tecknet 0 i ASCII.
Mitt namn är Rob Bowden, och detta är CS50.
[CS50.TV]
RSA alls.
RSA alls. [Skratt]
Alls.