[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[Dette er CS50.] [CS50.TV]
La oss ta en titt på RSA, en mye brukt algoritme for å kryptere data.
Krypteringsalgoritmer som Caesar og Vigenère ciphers er ikke veldig sikker.
Med Caesar cipher, må en angriper bare å prøve 25 forskjellige nøkler
å få budskapet er ren tekst.
Mens Vigenère chiffer er mer sikker enn Caesar cipher
på grunn av den større søket plass for nøkler, en gang en angriper
kjenner lengden på nøkkelen i en Vigenère siffer,
som kan bestemmes via en analyse av mønstre i den krypterte teksten,
den Vigenère chiffer er ikke så mye sikrere enn Caesar cipher.
RSA, derimot, er ikke utsatt for angrep som dette.
Caesar cipher og Vigenère cipher bruke samme nøkkel
både kryptere og dekryptere en melding.
Denne egenskapen gjør disse ciphers symmetriske nøkkel algoritmer.
Et grunnleggende problem med symmetriske nøkkel algoritmer
er at de er avhengige av en kryptering og sende meldingen
og den som mottar og dekryptere meldingen
å ha blitt enige på forhånd om nøkkelen de vil ta i bruk.
Men vi har litt av en oppstart problem her.
Hvordan etablere to datamaskiner som ønsker å kommunisere gjør en hemmelig nøkkel mellom dem?
Hvis nøkkelen må være hemmelig, så vi trenger en måte å kryptere og dekryptere nøkkelen.
Hvis alt vi har er symmetrisk nøkkel kryptografi
så vi har nettopp kommet tilbake til det samme problemet.
RSA, derimot, bruker et par nøkler,
ett for kryptering og en annen for dekryptering.
En kalles den offentlige nøkkel, og den andre er den private nøkkelen.
Den offentlige nøkkelen brukes til å kryptere meldinger.
Som du kanskje skjønner av navnet, kan vi dele vår offentlige nøkkel med
noen vi ønsker uten at sikkerheten av en kryptert melding.
Meldinger kryptert ved hjelp av en offentlig nøkkel
kan kun dekrypteres med tilhørende private nøkkel.
Selv om du kan dele din offentlige nøkkel, bør du alltid holde din private nøkkel hemmelig.
og bare den private nøkkelen kan brukes for å dekryptere meldinger
hvis 2 brukere ønsker å sende meldinger kryptert med RSA
frem og tilbake både brukere må ha sin egen offentlig og privat nøkkelpar.
Meldinger fra brukeren en til bruker 2
bare bruke bruker 2s nøkkelpar, og meldinger fra bruker 2 til bruker 1
bare bruke bruker 1-nøkkelpar.
Det faktum at det er 2 separate taster for å kryptere og dekryptere meldinger
gjør RSA en asymmetrisk nøkkel algoritme.
Vi trenger ikke å kryptere den offentlige nøkkelen for å sende den til en annen datamaskin
siden nøkkelen er offentlig allikevel.
Dette betyr at RSA ikke har samme oppstartsproblemet
som den symmetriske nøkkel algoritmer.
Så hvis jeg ønsker å sende en melding ved hjelp av RSA kryptering
til Rob, jeg må først Rob offentlige nøkkel.
For å generere et par nøkler, må Rob å plukke to store primtall.
Disse tallene vil bli brukt i både offentlige og private nøkler,
men den offentlige nøkkelen vil bare bruke produktet av disse to tallene,
ikke tallene selv.
Når jeg har kryptert melding ved hjelp av Rob offentlige nøkkel
Jeg kan sende meldingen til Rob.
For en datamaskin, er factoring tall et vanskelig problem.
Den offentlige nøkkelen, må du huske, brukte produktet av to primtall.
Dette produktet må da ha bare 2 faktorer,
som tilfeldigvis er tallene som utgjør den private nøkkelen.
For å dekryptere meldingen, vil RSA bruke denne private nøkkelen
eller tallene multiplisert sammen i prosessen med å lage den offentlige nøkkelen.
Fordi det er beregningsmessig vanskelig å faktor tallet
brukes i en offentlig nøkkel inn i to tallene som brukes i den private nøkkelen
det er vanskelig for en angriper å finne ut den private nøkkelen
som vil være nødvendig for å dekryptere meldingen.
Nå la oss gå inn i noen lavere nivå detaljer om RSA.
La oss først se hvordan vi kan generere et par nøkler.
Først må vi to primtall.
Vi vil kalle disse to tallene p og q.
For å plukke p og q, i praksis vi ville pseudorandomly generere
store tall og deretter bruke en test for å avgjøre hvorvidt
disse tallene er sannsynligvis primtall.
Vi kan holde generere tilfeldige tall over og over igjen
før vi har to primtall som vi kan bruke.
Her la oss plukke p = 23 og q = 43.
Husk at i praksis bør p og q være mye større antall.
Så vidt vi vet, jo større tall, jo vanskeligere er det
å knekke en kryptert melding.
Men det er også dyrere å kryptere og dekryptere meldinger.
I dag er det ofte anbefalt at p og q er minst 1024 biter,
som setter hvert nummer på over 300 desimaler.
Men vi vil plukke disse små tall for dette eksemplet.
Nå skal vi multiplisere p og q sammen for å få en tredje nummer,
som vi kaller n.
I vårt tilfelle, n = 23 * 43, som = 989.
Vi har n = 989.
Neste vi vil formere p - 1 med q - 1
for å få et fjerde nummer, som vi kaller m.
I vårt tilfelle, m = 22 * ​​42, som = 924.
Vi har m = 924.
Nå trenger vi en rekke e som er relativt prime til m
og mindre enn m.
To tall er relativt prime eller coprime
hvis den eneste positive heltall som deler dem begge jevnt er en.
Med andre ord, den største felles divisor av e og m
må være en.
I praksis er det vanlig for e å være primtall 65537
så lenge dette nummeret ikke tilfeldigvis være en faktor av m.
For våre keys, vil vi plukke e = 5
siden 5 er relativt prime til 924.
Til slutt vil vi trenger en mer tall, som vi kaller d.
D må være noen verdi som tilfredsstiller likningen de = 1 (mod m).
Denne mod m betyr vi vil bruke noe som kalles modulær aritmetikk.
I modulær aritmetikk, får en gang et nummer høyere enn noen øvre grense
det vil bryte tilbake rundt til 0.
En klokke, for eksempel, bruker modulær aritmetikk.
Ett minutt etter 01:59, for eksempel, er 2:00,
ikke 1:60.
Minuttviseren har pakket rundt til 0
ved å nå en øvre grense på 60 år.
Så kan vi si 60 tilsvarer 0 (mod 60)
og 125 tilsvarer 65 tilsvarer 5 (mod 60).
Vår offentlige nøkkel blir paret e og n
hvor i dette tilfellet e er 5 og n er 989.
Våre private nøkkel vil være paret d og n,
som i vårt tilfelle er 185 og 989.
Legg merke til at vår opprinnelige primtall p og q ikke vises
hvor som helst i våre private eller offentlige nøkler.
Nå som vi har vår nøkkelpar, la oss ta en titt på hvordan vi kan kryptere
og dekryptere en melding.
Jeg ønsker å sende en melding til Rob,
så han vil være en å generere denne nøkkelpar.
Da vil jeg spørre Rob for hans offentlige nøkkel, som jeg skal bruke
å kryptere en melding for å sende ham.
Husk, det er helt greit for Rob å dele sin offentlige nøkkel med meg.
Men det ville ikke være greit å dele sin private nøkkel.
Jeg har ikke noen anelse om hva hans private nøkkelen er.
Vi kan bryte vårt budskap m opp i flere biter
alle mindre enn n og deretter kryptere hver av disse biter.
Vi vil kryptere strengen CS50, som vi kan bryte opp i fire biter,
én per bokstav.
For å kryptere meldingen min, jeg trenger å konvertere den til
en slags numerisk representasjon.
La oss sette sammen de ASCII-verdier med karakterene i mitt budskap.
For å kryptere en gitt melding m
Jeg må beregne c = m til e (mod n).
Men m må være mindre enn n,
ellers hele meldingen ikke kan uttrykkes modulo n.
Vi kan bryte m opp i flere biter, som alle er mindre enn n,
og kryptere hver av disse biter.
Kryptering hver av disse biter, får vi c1 = 67 til 5 (mod 989)
som = 658.
For våre andre del har vi 83 til 5 (mod 989)
som = 15.
For vår tredje del har vi 53 til 5 (mod 989)
som = 799.
Og til slutt, for vår siste del har vi 48 til 5 (mod 989)
som = 975.
Nå kan vi sende over disse krypterte verdier til Rob.
Her du går, Rob.
Mens vårt budskap er i flukt, la oss ta en titt
på hvordan vi fikk denne verdien for d.
Vårt nummer d trengs for å oppfylle 5d = 1 (mod 924).
Dette gjør d multiplikativ inverse av 5 modulo 924.
Gitt to heltall, A og B, den utvidede Euklids algoritme
kan brukes til å finne den største felles divisor av disse to heltall.
Det vil også gi oss 2 andre tall, x og y,
som tilfredsstiller ligningen ax + by = største felles divisor av a og b.
Hvordan hjelper dette oss?
Vel, koble e = 5 for en
og m = 924 for b
Vi vet allerede at disse tallene er coprime.
Deres største felles divisor er 1..
Dette gir oss 5x + 924y = 1
eller 5x = 1 - 924y.
Men hvis vi bare bryr seg om alt modulo 924
så kan vi slippe - 924y.
Tenk tilbake til klokken.
Hvis minutt hånd er på 1 og deretter nøyaktig 10 timer passere,
vi vet minuttviseren vil fortsatt være på en.
Her starter vi på en og deretter vikle rundt akkurat y ganger,
så vi vil fortsatt være på en.
Vi har 5x = 1 (mod 924).
Og her denne x er det samme som D vi leter etter før,
så hvis vi bruker den utvidede Euklids algoritme
å få dette nummeret x, er at antallet vi bør bruke som d vår.
Nå la oss kjøre den utvidede Euklids algoritme for a = 5
og b = 924.
Vi vil bruke en metode som kalles tabellen metoden.
Vårt bord vil ha 4 kolonner, x, y, d, og k..
Vårt bord starter med to rader.
I den første raden har vi 1, 0, så vår verdien av en, som er 5,
og våre andre rad er 0, 1, og vår verdi for b, som er 924.
Verdien av fjerde kolonnen, k, vil være et resultat
av å dele verdien av d i raden over den med verdien av d
på samme rad.
Vi har 5 delt på 924 er 0 med noen rest.
Det betyr at vi har k = 0.
Nå verdien av annenhver celle vil være verdien av cellen 2 rader over det
minus verdien av raden over det ganger K.
La oss starte med d i 3. rad.
Vi har 5-924 * 0 = 5.
Neste vi har 0-1 * 0 som er 0
og 1-0 * 0 som er en.
Ikke så ille, så la oss gå videre til neste rad.
Først må vi vår verdi av k.
924 delt på 5 = 184 med noen resten,
så vår verdi for k er 184.
Nå 924-5 * 184 = 4.
1-0 * 184 er 1 og 0 - 1 * 184 er -184.
Greit, la oss gjøre den neste raden.
Vår verdi av k vil være en grunn
5 delt på 4 = 1 med noen rest.
La oss fylle de andre kolonnene.
5-4 * 1 = 1.
0-1 * 1 = -1.
Og 1 - 184 * 1 er 185.
La oss se hva vår neste verdien av k ville være.
Vel, det ser ut som vi har 4 delt på 1, som er 4.
I dette tilfellet hvor vi dividere med 1 slik at k er lik
verdien av d i ovennevnte rad betyr at vi er ferdig med algoritmen vår.
Vi ser her at vi har x = 185 og y = -1 i den siste raden.
La oss nå komme tilbake til vårt opprinnelige mål.
Vi sa at verdien av x som følge av kjøre denne algoritmen
ville være multiplikativ inverse av en (mod b).
Det betyr at 185 er multiplikativ inverse av 5 (mod 924)
noe som betyr at vi har en verdi på 185 for d.
Det faktum at d 1 = i siste rad
bekrefter at e ble coprime til minnekort.
Hvis det ikke var en så vi måtte plukke en ny e.
Nå la oss se om Rob har mottatt budskapet mitt.
Når noen sender meg en kryptert melding
så lenge jeg har holdt min private nøkkel hemmelig
Jeg er den eneste som kan dekryptere meldingen.
Til dekryptere en del c kan jeg beregne den opprinnelige meldingen
er lik den del til d strøm (mod n).
Husk at d og n er fra min private nøkkel.
Å få en full melding fra sine biter vi dekryptere hver del
og sette sammen resultatene.
Nøyaktig hvor sikker er RSA?
Sannheten er, vet vi ikke.
Sikkerhet er basert på hvor lang tid det ville ta en angriper å knekke en melding
kryptert med RSA.
Husk at en angriper får tilgang til den offentlige nøkkelen,
som inneholder både e og n.
Hvis angriperen klarer å faktor n i sine to primtall, p og q,
så hun kunne beregne d med utvidede Euklids algoritme.
Dette gir henne den private nøkkelen, som kan brukes for å dekryptere en melding.
Men hvor raskt vi kan faktor heltall?
Igjen, vi vet ikke.
Ingen har funnet en rask måte å gjøre det,
som betyr at gitt stort nok n
det ville ta en angriper urealistisk lang
å faktor nummeret.
Hvis noen avslørte en rask måte å factoring heltall
RSA ville bli brutt.
Men selv om heltall faktorisering er iboende treg
RSA algoritmen kan fortsatt ha noen feil i det
som gjør det enkelt dekryptering av meldinger.
Ingen har funnet og avdekket en slik feil ennå,
men det betyr ikke at man ikke eksisterer.
I teorien kan noen være der ute å lese alle data kryptert med RSA.
Det er en annen bit av en personvern problemet.
Hvis Tommy krypterer noen melding med min offentlige nøkkel
og en angriper krypterer den samme meldingen med min offentlige nøkkel
angriperen vil se at de to meldingene er identiske
og dermed vet hva Tommy kryptert.
For å unngå dette, er meldinger typisk polstret med tilfeldige biter
før blir kryptert slik at den samme meldingen krypteres
flere ganger vil se annerledes så lenge polstring på meldingen er forskjellig.
Men husk hvor vi må dele meldinger i biter
slik at hver del er mindre enn n?
Padding biter betyr at vi kanskje må dele ting opp
inn enda flere biter siden den polstrede del må være mindre enn n.
Kryptering og dekryptering er relativt dyrt med RSA,
og så ønsker å bryte opp en melding i mange biter kan være svært kostbare.
Hvis store mengder data må krypteres og dekrypteres
vi kan kombinere fordelene med symmetriske nøkkel algoritmer
med de av RSA å få både sikkerhet og effektivitet.
Selv om vi ikke vil gå inn på det her,
AES er en symmetrisk nøkkel algoritme som Vigenère og Caesar chifre
men mye vanskeligere å knekke.
Selvfølgelig kan vi ikke bruke AES uten å etablere en felles hemmelig nøkkel
mellom de to systemene, og vi så problemet med det før.
Men nå kan vi bruke RSA å etablere felles hemmelig nøkkel mellom de 2 systemene.
Vi kaller datamaskinen som sender data avsenderen
og datamaskinen som mottar dataene mottakeren.
Mottakeren har en RSA-nøkkelpar og sender
den offentlige nøkkelen til avsenderen.
Avsenderen genererer en AES nøkkel,
krypterer den med mottakerens RSA offentlig nøkkel,
og sender AES nøkkel til mottakeren.
Mottakeren dekrypterer meldingen med sin RSA private nøkkelen.
Både avsender og mottaker har nå en felles AES nøkkel mellom dem.
AES, som er mye raskere på kryptering og dekryptering enn RSA,
kan nå brukes til å kryptere store mengder data og sende dem til mottakeren,
som kan dekryptere med samme nøkkel.
AES, som er mye raskere på kryptering og dekryptering enn RSA,
kan nå brukes til å kryptere store mengder data og sende dem til mottakeren,
som kan dekryptere med samme nøkkel.
Vi trengte RSA å overføre delt nøkkel.
Vi trenger ikke lenger å bruke RSA i det hele tatt.
Det ser ut som jeg har fått en melding.
Det spiller ingen rolle om noen leser hva som står på papiret flyet før jeg fanget den
fordi jeg er den eneste med den private nøkkelen.
La oss dekryptere hver av biter i meldingen.
Den første del, 658, øker vi til d makt, som er 185,
mod n, som er 989, er lik 67,
som er bokstaven C i ASCII.
Nå, på den andre del.
Den andre del har verdi 15,
som vi heve til ett hundre og åttifemte makt,
989 mod, og dette er lik 83
som er bokstaven S i ASCII.
Nå for tredje del, som har verdi 799, øker vi til 185,
989 mod, og dette er lik 53,
som er verdien for tegnet 5 i ASCII.
Nå for siste blings, har hvilke verdi 975,
Vi høyner til 185, mod 989,
og dette er lik 48, som er verdien for tegnet 0 i ASCII.
Mitt navn er Rob Bowden, og dette er CS50.
[CS50.TV]
RSA hele tatt.
RSA hele tatt. [Latter]
I det hele tatt.