[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[Dette er CS50.] [CS50.TV]
Lad os tage et kig på RSA, et udbredt algoritme til at kryptere data.
Krypteringsalgoritmer som Cæsar og Vigenère ciphers er ikke meget sikker.
Med Caesar cipher, kun en angriber skal prøve 25 forskellige nøgler
at få budskabet er almindelig tekst.
Mens Vigenère cipher er mere sikker end den Caesar cipher
på grund af den større søgerummet til nøgler, når en hacker
kender længden af ​​nøglen i en Vigenère cipher,
som kan bestemmes via en analyse af mønstrene i den krypterede tekst,
Den Vigenère cifferliste er ikke så meget mere sikker end Cæsar ciffer.
RSA, på den anden side, er ikke sårbare over for angreb lignende.
The Caesar cipher og Vigenère cipher bruge den samme nøgle
både kryptere og dekryptere en meddelelse.
Denne egenskab gør disse ciphers symmetriske nøgle algoritmer.
Et grundlæggende problem med symmetriske nøgle algoritmer
er, at de er afhængige af en kryptering og sender meddelelsen
og den ene modtager og dekryptering af meddelelsen
allerede at have aftalt på forhånd på tasten de begge vil bruge.
Men vi har lidt af et startproblemet her.
Hvordan 2 computere, der ønsker at kommunikere etablere en hemmelig nøgle mellem dem?
Hvis nøglen skal være hemmelig, så har vi brug for en måde at kryptere og dekryptere nøglen.
Hvis alt vi har, er symmetriske nøgle kryptografi
så vi er lige kommet tilbage til det samme problem.
RSA, på den anden side bruger et sæt nøgler,
en for krypteringen og en anden for dekrypteringen.
En kaldes den offentlige nøgle, og den anden er den private nøgle.
Den offentlige nøgle bruges til at kryptere meddelelser.
Som du kan gætte med sit navn, kan vi dele vores offentlige nøgle med
nogen, vi ønsker, uden at kompromittere sikkerheden i en krypteret meddelelse.
Meddelelser krypteret med en offentlig nøgle
kan kun dekrypteres med den tilhørende private nøgle.
Mens du kan dele din offentlige nøgle, bør du altid holde din private nøgle hemmelighed.
og kun den private nøgle kan bruges til at dekryptere beskeder
hvis 2 brugere ønsker at sende meddelelser krypteret med RSA
frem og tilbage begge brugere er nødt til at have deres egne offentlige og private nøglepar.
Meddelelser fra bruger 1 til bruger 2
kun bruge bruger 2 s nøglepar, og beskeder fra bruger 2 til bruger 1
kun bruge bruger 1 s nøglepar.
Det faktum, at der er 2 separate taster til at kryptere og dekryptere beskeder
gør RSA asymmetrisk nøglealgoritme.
Vi behøver ikke at kryptere den offentlige nøgle for at sende den til en anden computer
da nøglen er offentlig alligevel.
Dette betyder, at RSA ikke har den samme startproblemet
som de symmetriske nøgle algoritmer.
Så hvis jeg ønsker at sende en besked ved hjælp af RSA-kryptering
til Rob, jeg først nødt Rob offentlige nøgle.
For at generere et sæt nøgler, Rob nødt til at vælge 2 store primtal.
Disse tal vil blive anvendt i både den offentlige og private nøgler,
men den offentlige nøgle vil kun bruge produktet af disse 2 numre,
ikke tallene selv.
Når jeg har krypteret beskeden ved hjælp af Rob offentlige nøgle
Jeg kan sende beskeden til Rob.
For en computer, er factoring numre en hård problem.
Den offentlige nøgle, husk, der anvendes produktet af to primtal.
Dette produkt skal derefter have kun 2 faktorer,
som tilfældigvis er de numre, der udgør den private nøgle.
For at dekryptere meddelelsen, vil RSA bruge denne private nøgle
eller antallet multipliceres og i processen med at skabe den offentlige nøgle.
Fordi det er beregningsmæssigt vanskeligt at faktor det antal
bruges i en offentlig nøgle i 2 numre anvendes i private nøgle
Det er svært for en hacker at finde ud af den private nøgle
der vil være nødvendigt til at dekryptere meddelelsen.
Lad os nu gå ind i nogle lavere niveau detaljer om RSA.
Lad os først se, hvordan vi kan skabe et sæt nøgler.
Først vil vi brug for 2 primtal.
Vi kalder disse 2 numre p og q.
For at samle p og q i praksis ville vi pseudorandomly genererer
store tal og derefter bruge en test til bestemmelse af, om eller ej
disse numre er sandsynligvis prime.
Vi kan holde generere tilfældige tal igen og igen
indtil vi har 2 primtal, som vi kan bruge.
Her lad os plukke p = 23 og q = 43.
Husk, i praksis, bør p og q er meget større tal.
Så vidt vi ved, jo større tal, jo sværere er det
at knække en krypteret meddelelse.
Men det er også dyrere at kryptere og dekryptere beskeder.
Dag er det ofte anbefales, at p og q er mindst 1024 bit,
der sætter hvert nummer på over 300 decimaler.
Men vi henter disse små tal for dette eksempel.
Nu vil vi formere p og q sammen for at få en 3. nummer,
som vi kalder n..
I vores tilfælde, n = 23 * 43, hvilket = 989.
Vi har n = 989.
Næste vi vil mangedoble p - 1 med q - 1
at opnå en 4. tal, som vi vil kalde m.
I vores tilfælde, m = 22 * ​​42, hvilket = 924.
Vi har m = 924.
Nu vil vi have en række e, der er relativt prime til m
og mindre end m.
To numre er relativt prime eller primiske
hvis det eneste positive heltal, der skiller dem begge jævnt er 1.
Med andre ord, den største fælles divisor af e og m
skal være 1.
I praksis er det fælles for e at være primtal 65.537
så længe et sådant ikke tilfældigvis er en faktor m.
For vores nøgler, vil vi vælge e = 5
siden 5 er relativt prime til 924.
Endelig får vi brug for en mere antal, som vi vil kalde d.
D skal være en værdi, der tilfredsstiller ligningen de = 1 (mod m).
Denne mod m betyder vi vil bruge noget, der hedder modulær aritmetik.
I modulær aritmetik, får en gang et tal højere end nogle øvre grænse
Det vil automatisk gå tilbage rundt til 0.
Et ur, for eksempel anvender modulær aritmetik.
Et minut efter 1:59, for eksempel er 02:00,
ikke 1:60.
Minutviseren har svøbt omkring til 0
efter at have nået en øvre grænse på 60.
Så kan vi sige 60 svarer til 0 (mod 60)
og 125 svarer til 65 svarer til 5 (mod 60).
Vores offentlige nøgle bliver parret e og n
hvor i dette tilfælde e er 5, og n er 989.
Vores private nøgle bliver parret d og n,
hvilket i vores tilfælde er 185 og 989.
Bemærk, at vores oprindelige primtal p og q ikke vises
overalt i vores private eller offentlige nøgler.
Nu hvor vi har vores sæt nøgler, så lad os tage et kig på, hvordan vi kan kryptere
og dekryptere en meddelelse.
Jeg ønsker at sende en besked til Rob,
så han vil være en til at generere denne nøglepar.
Så vil jeg bede Rob for hans offentlige nøgle, som jeg vil bruge
til at kryptere en besked at sende til ham.
Husk, det er helt okay for Rob at dele sin offentlige nøgle med mig.
Men det ville ikke være okay at dele sin private nøgle.
Jeg har ikke nogen idé om, hvad hans private nøgle er.
Vi kan bryde vores budskab m op i flere bidder
alle mindre end n og derefter kryptere hver af disse stykker.
Vi vil kryptere strengen CS50, som vi kan bryde op i 4 stykker,
en per bogstav.
For at kryptere mit budskab, vil jeg nødt til at konvertere det til
en slags numerisk repræsentation.
Lad os sammenkæde ASCII værdier med personerne i mit budskab.
For at kryptere en given meddelelse m
Jeg bliver nødt til at beregne c = m til e (mod n).
Men m skal være mindre end n,
eller også hele meddelelsen ikke kan udtrykkes modulo n.
Vi kan bryde m op i flere stykker, som alle er mindre end n,
og kryptere hver af disse stykker.
Kryptering af hver af disse stykker, fås c1 = 67 til 5 (mod 989)
Heraf = 658.
For vores anden luns har vi 83 til 5 (mod 989)
hvilket = 15.
For vores tredje luns har vi 53 til 5 (mod 989)
Heraf = 799.
Og endelig, for vores sidste luns har vi 48 til 5 (mod 989)
hvilket = 975.
Nu kan vi sende over disse krypterede værdier til Rob.
Værsgo, Rob.
Mens vores budskab er på flugt, lad os tage endnu et kig
på, hvordan vi fik denne værdi for d.
Vores nummer d nødvendige for at dække 5d = 1 (mod 924).
Dette gør d det multiplikative inverse af 5. modulo 924.
Da 2 heltal, a og b, den udvidede Euklidiske algoritme
kan anvendes til at finde den største fælles divisor af disse 2 heltal.
Det vil også give os 2 andre numre, x og y,
der opfylder ligningen ax + by = den største fælles divisor af a og b.
Hvordan kan dette hjælpe os?
Nå, tilslutte e = 5 for en
og m = 924 for b
Vi ved allerede, at disse tal er indbyrdes primiske.
Deres største fælles divisor er 1.
Dette giver os 5x + 924y = 1
eller 5x = 1 - 924y.
Men hvis vi kun interesserer os for alt modulo 924
så kan vi droppe - 924y.
Tænk tilbage på uret.
Hvis minutviseren er på 1 og derefter præcis 10 timer, skal
vi ved minutviseren vil stadig være på 1.
Her starter vi på 1 og derefter indhyllingsafstand præcis y gange,
så vi vil stadig være på 1.
Vi har 5x = 1 (mod 924).
Og her i x er det samme som d vi søgte før,
så hvis vi bruger den udvidede Euklidiske algoritme
at få dette nummer x, det er det antal, vi skal bruge som vores d..
Nu lad os køre den udvidede Euklidiske algoritme til a = 5
og b = 924.
Vi bruger en metode kaldet tabellen metoden.
Vores tabel har 4 søjler, x, y, d og k.
Vores tabel starter med 2 rækker.
I den første række har vi 1, 0, så vores værdi af en, der er 5,
og vores anden række er 0, 1, og vores værdi for b, der er 924.
Værdien af ​​den 4. kolonne, k, bliver resultatet
for at dividere værdien af ​​d i rækken over den med værdien af ​​d
på samme række.
Vi har 5 divideret med 924 er 0 med nogle resten.
Det betyder, at vi har k = 0.
Nu værdien af ​​hver celle bliver værdien af ​​cellen 2 p ovenover
minus værdien af ​​rækken ovenover gange k.
Lad os starte med d i 3. række.
Vi har 5 til 924 * 0 = 5.
Næste vi har 0 - 1 * 0, hvilket er 0
og 1 - 0 * 0 der er 1.
Ikke alt for dårlig, så lad os gå videre til den næste række.
Først har vi brug for vores værdi af k.
924 divideret med 5 = 184 med en vis resterende,
så vores værdi for k er 184.
Nu 924 til 5 * 184 = 4.
1 til 0 * 184 er 1 og 0 - 1 * 184 er -184.
Okay, lad os gøre den næste række.
Vores værdi af k vil være 1, fordi
5 divideret med 4 = 1 med nogle resten.
Lad os udfylde de andre kolonner.
5-4 * 1 = 1.
0-1 * 1 = -1.
Og fra 1 til 184 * 1 185.
Lad os se, hvad vores næste værdi af k ville være.
Tja, det ser ud som om vi har 4 divideres med 1, hvilket er 4.
I dette tilfælde, hvor vi dividere med 1, således at k er lig med
værdien af ​​d i ovenstående række, betyder, at vi er færdige med vores algoritme.
Vi kan se her, at vi har x = 185 og y = -1 i den sidste række.
Lad os nu vende tilbage til vores oprindelige mål.
Vi sagde, at værdien af ​​x som et resultat af at køre denne algoritme
vil være det multiplikative inverse af en (mod b).
Det betyder, at 185 er det multiplikative inverse af 5 (mod 924)
hvilket betyder, at vi har en værdi på 185 for d.
Den kendsgerning, at d = 1 i den sidste række
bekræfter, at e var indbyrdes primiske til m.
Hvis det ikke var 1 så ville vi nødt til at vælge en ny e.
Lad os nu se, om Rob har modtaget min besked.
Når en person sender mig en krypteret meddelelse
så længe jeg har holdt min private nøgle en hemmelighed
Jeg er den eneste, der kan dekryptere meddelelsen.
For at dekryptere en luns c jeg kan beregne den oprindelige meddelelse
er lig med bid til d effekt (mod n).
Husk, at d og n er fra min private nøgle.
For at få en fuld besked fra sine bidder vi dekryptere hver luns
og sammenkæde resultaterne.
Præcis hvordan sikker er RSA?
Sandheden er, ved vi ikke.
Sikkerhed er baseret på hvor lang tid det ville tage en hacker at knække en besked
krypteret med RSA.
Husk, at en hacker har adgang til din offentlige nøgle,
der indeholder både e og n.
Hvis hackeren formår at faktor n i sine 2 primtal, p og q,
så hun kunne beregne d med den udvidede Euklidiske algoritme.
Dette giver hende den private nøgle, som kan anvendes til at dekryptere en meddelelse.
Men hvor hurtigt kan vi faktor heltal?
Igen, ved vi ikke.
Ingen har fundet en hurtig måde at gøre det,
hvilket betyder, at given stor nok n
det ville tage en hacker urealistisk lang
til faktor nummeret.
Hvis nogen afslørede en hurtig måde at factoring heltal
RSA ville blive brudt.
Men selv hvis heltal faktorisering er i sagens natur langsom
RSA algoritmen kunne stadig have nogle fejl i det
der tillader let dekryptering af meddelelser.
Ingen har fundet og afsløret en sådan fejl endnu,
men det betyder ikke en ikke eksisterer.
I teorien kunne nogen være derude læse alle data krypteret med RSA.
Der er en anden lidt af et privat anliggende.
Hvis Tommy krypterer nogle besked ved hjælp af min offentlige nøgle
og en angriber krypterer det samme budskab ved hjælp af min offentlige nøgle
angriberen vil se, at de 2 budskaber er identiske
og dermed ved, hvad Tommy krypteret.
For at forhindre dette, er meddelelser typisk foret med tilfældige bits
før de krypteres, så den samme meddelelse krypteres
flere gange ser anderledes ud, så længe polstring på meddelelsen er forskellig.
Men huske, hvordan vi er nødt til at opdele beskeder i stykker
således at hvert stykke er mindre end n?
Polstring de klumper betyder, at vi måske nødt til at splitte tingene op
ind i endnu flere bidder, da det polstrede luns skal være mindre end n..
Kryptering og dekryptering er relativt dyre med RSA,
og så behøver at bryde op en besked i mange stykker kan være meget dyrt.
Hvis en stor mængde data skal være krypteret og dekrypteret
vi kan kombinere fordelene ved symmetriske nøgle algoritmer
med de RSA at få både sikkerhed og effektivitet.
Selv om vi ikke vil gå ind i det her,
AES er en symmetrisk nøglealgoritme som Vigenère og Cæsar ciphers
men meget sværere at knække.
Selvfølgelig kan vi ikke bruge AES uden at etablere en fælles hemmelig nøgle
mellem de 2 systemer, og vi oplevede det problem med det før.
Men nu kan vi bruge RSA til at etablere den delte hemmelige nøgle mellem de 2 systemer.
Vi ringer til computer, der sender data afsenderen
og computeren modtager dataene modtageren.
Modtageren har en RSA-nøglepar og sender
den offentlige nøgle for afsenderen.
Afsenderen genererer en AES nøgle,
krypterer den med modtagerens RSA offentlige nøgle,
og sender AES nøglen til modtageren.
Modtageren dekrypterer meddelelsen med sin RSA private nøgle.
Både afsender og modtager har nu en delt AES nøgle mellem dem.
AES, som er meget hurtigere ved kryptering og dekryptering end RSA,
kan nu bruges til at kryptere de store mængder af data og sende dem til modtageren,
der kan dekryptere med den samme nøgle.
AES, som er meget hurtigere ved kryptering og dekryptering end RSA,
kan nu bruges til at kryptere de store mængder af data og sende dem til modtageren,
der kan dekryptere med den samme nøgle.
Vi har bare brug for RSA at overføre den delte nøgle.
Vi vil ikke længere nødt til at bruge RSA overhovedet.
Det ser ud som jeg har fået en besked.
Det betyder ikke noget, om nogen læse hvad der er på papirflyver før jeg fangede det
fordi jeg er den eneste med den private nøgle.
Lad os dekryptere hver af klumper i meddelelsen.
Den første bid, 658, hæver vi til d magt, hvilket er 185,
mod n, hvilket er 989, er lig med 67,
der er bogstavet C i ASCII.
Nu, på det andet stykke.
Det andet stykke har værdien 15,
som vi hæve til 185. strøm,
mod 989, hvilket svarer til 83
der er bogstavet S i ASCII.
Nu til den tredje bid, der har værdi 799, rejser vi til 185,
mod 989, og dette er lig med 53,
som er værdien for tegnet 5 i ASCII.
Nu til den sidste bid, har hvilken værdi 975,
vi rejser til 185, mod 989,
og dette er lig med 48, som er værdien af ​​den karakter 0 i ASCII.
Mit navn er Rob Bowden, og dette er CS50.
[CS50.TV]
RSA overhovedet.
RSA overhovedet. [Latter]
Overhovedet.