[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. Siden den private nøkkelen bør holdes hemmelig, og bare den private nøkkelen kan brukes til å dekryptere meldinger, hvis 2 brukere ønsker å sende meldinger kryptert med RSA 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 bruker bare 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 en symmetrisk nøkkel algoritme. Hvordan to datamaskiner som ønsker å kommunisere etablere 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 kryptografi så vi har bare komme 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 med en offentlig nøkkel kan bare dekrypteres med tilhørende private nøkkelen. Selv om du kan dele din offentlige nøkkel, bør du alltid holde din private nøkkel hemmelig. Siden den private nøkkelen bør holdes 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.