[Powered by Google Translate] [Vigenère Cipher] [Nate Hardison - Harvard University] [Dette er CS50. - CS50.TV] Møt Alice. Alice er forelsket i Bob. Heldigvis for Alice, har Bob også øyne for henne. Dessverre for deres gryende romanse, ikke bare godkjenne Alice foreldre av Bob, men Alice beste venn, Evelyn, har en hemmelig forelsket i Bob og ønsker selfishly å holde dem fra hverandre på alle kostnader. Hvis du vil sende hemmelige meldinger til hverandre at Alice foreldre ikke kan forstå, 

Alice og Bob har brukt en Caesar siffer, som virker ved å forskyve alfabetet ved et visst antall bokstaver som en måte å generere et nytt alfabetet. Hver bokstav i den opprinnelige alfabetet så satt ved sin tilsvarende brev i den nye skiftet alfabetet. Alice favoritt nummer er 3, som Bob vet, så hun bruker 3 som hennes nøkkel. Når hun flytter det engelske alfabetet med tre bokstaver, En blir D, blir B E, C blir F, og så videre. 

Når hun kommer til slutten av alfabetet - til bokstavene X, Y og Z - hun wraps rett rundt tilbake til begynnelsen av alfabetet og erstatter X med A, Y med B, og Z med C. Så når Alice går å kryptere hennes hemmelige budskap til Bob, nemlig "Møt meg i parken klokken elleve a.m.," hun gjør bare nødvendige endringer. M blir P, blir E H, og så videre til henne ukryptert vanlig tekstmelding er omgjort til kryptert uleselig tekst: "Phhw ph dw GHW sdun dw hohyhq dp" er definitivt ikke den mest romantiske lød, men Alice tror at det vil gjøre. 

Alice gir beskjed til Evelyn å levere til Bob hus. Men Evelyn tar i stedet tilbake til sin plass og forsøker å knekke koden. En av de første tingene Evelyn merknader er at bokstaven H oppstår 7 ganger i meldingen, mange flere ganger enn noen annen bokstav. Å vite at bokstaven E er den vanligste i det engelske språket, forekommende nesten 13% av tiden, Evelyn gjetninger at H er substituerte for E for å gjøre den hemmelige melding og prøver å bruke en nøkkel 3 for å dekryptere den. 

Innen minutter, tall Evelyn ut Alice planer og evilly kaller Alice foreldre. Hadde Alice og Bob tatt CS50, ville de ha kjent til dette frekvens-analyse angrep på Caesar cipher, som gjør at den kan brytes ganske raskt. De ville også ha visst at chiffer er lett utsatt for en brute-force angrep, hvor Evelyn kunne ha prøvd alle mulige 25 taster, eller skift det engelske alfabetet, for å dechiffrere meldingen. Hvorfor 25 taster og ikke 26? 

Vel, prøv å skifte en bokstav med 26 posisjoner, og du vil se hvorfor. Uansett, ville en brute-force angrep har tatt Evelyn litt lenger men ikke lenge nok til å holde henne fra thwarting Alice og Bob planer, spesielt hvis Evelyn har ved hjelp av en datamaskin som kan rippe gjennom alle 25 tilfeller på et øyeblikk. Så dette problemet også plaget andre som brukte Caesar cipher, og derfor folk begynte å eksperimentere med mer komplekse substitusjon ciphers som bruker flere skift verdier i stedet for bare én. En av de mest kjente av disse kalles Vigenère chiffer. Hvordan får vi flere skift verdier? Vel, i stedet for å bruke et tall som nøkkelen, bruker vi et ord for nøkkelen. Vi vil bruke hver bokstav i nøkkelen til å generere et nummer, og effekten er at vi vil ha flere Caesar cipher-stil nøkler for skiftende bokstaver. 

La oss se hvordan dette fungerer ved å kryptere Alice budskap til Bob: Møt meg i parken klokken elleve på morgenen Jeg, personlig, tror bacon er deilig, så la oss bruke den som nøkkelen. Hvis vi tar meldingen i sin ukryptert, rent tekstformat, Vi ser at det er 25 tegn lang. Bacon har bare 5 bokstaver, så vi trenger å gjenta det 5 ganger å gjøre det samsvarer lengden på ren tekst. 

Bacon bacon bacon bacon bacon. Som en kort side, hvis antall bokstaver i ren tekst ikke dele rent med antall bokstaver i nøkkelen, vi bare avslutte endelig repetisjon av våre viktigste tidlig, med bare bokstavene vi trengte å gjøre alt passer sammen. Nå går vi om å finne de skiftet verdier. 

Vi kommer til å gjøre dette ved hjelp av posisjonen hver bokstav i våre viktigste - bacon - i A til Z alfabetet. Siden vi er dataforskere, vi liker å begynne å telle på null i stedet for 1, så vi kommer til å si at plasseringen av den første bokstaven i bacon - B - er i posisjon 1 i null-indeksert A til Z alfabetet, ikke 2 og stillingen av A er null, ikke en. Ved hjelp av denne algoritmen, kan vi finne skiftet verdier for hver bokstav. 

Å kryptere klartekst og generere uleselig tekst, vi bare skifte hver bokstav i klartekst med den angitte beløpet, akkurat som vi gjør med Caesar cipher, innpakning fra Z tilbake til A om nødvendig. M blir forskjøvet med en plass å bli N. Den første E skifter ikke i det hele tatt, men vi skiftet den andre E med 2 steder å G og T med 14 plasser til H. Hvis vi jobber gjennom ren tekst, ender vi opp med, "Negh zf AV HUF pcfx bt gzrwep oz." Igjen, ikke veldig romantisk-klingende men definitivt kryptisk. Hvis Alice og Bob hadde visst om Vigenère chiffer, ville de ha vært trygg fra Evelyns nysgjerrige øyne? Hva tror du? Ville du ønsker å logge inn på din bankkonto hvis banken din bestemte seg for å bruke 

Vigenère cipher å kryptere kommunikasjonen med passordet ditt som nøkkel? Hvis jeg var deg, ville jeg ikke. Og mens Evelyn kan bli holdt opptatt lenge nok for Alice og Bob å ha sine møte opp, det er ikke verdt det for Alice og Bob å sjanse det. Vigenère chiffer er relativt lett å bryte hvis du vet lengden på nøkkelen fordi da kan du behandle den krypterte uleselig tekst som produktet av noen sammenvevde Caesar chifre. 

Finne lengden på nøkkelen er ikke veldig vanskelig, enten. Hvis den opprinnelige vanlig tekstmelding er lang nok til at noen ord forekommer flere ganger, til slutt vil du se repetisjon dukket opp i den krypterte uleselig tekst, som i dette eksempelet, der du ser MONCY vises to ganger. I tillegg kan du utføre en brute-force angrep på chiffer. Dette tar betydelig lengre enn en brute-force angrep på Caesar cipher, som kan gjøres nesten momentant med en datamaskin siden i stedet for 25 tilfeller å sjekke at du har fått 26 ⁿ - en muligheter, der n er lengden av den ukjente tasten. 

Dette er fordi hver bokstav i nøkkelen kan være noen av de 26 bokstavene, A til Z, og en smart person ville prøve å bruke en nøkkel som ikke kan finnes i en ordbok, noe som betyr at du må teste alle de rare bokstavkombinasjoner, som ZXXXFF, og ikke bare et par hundre tusen ord i ordboken. Den minus 1 kommer inn i matematikk fordi du ikke ønsker å bruke en nøkkel med bare A-er, siden med vår null-indeksert alfabetet som vil gi deg den samme effekten som å bruke en Caesar cipher med en nøkkel på null. Uansett, 26 ⁿ - får en stor ganske raskt, men mens du definitivt ikke ønsker å prøve å bryte et siffer for hånd på denne måten, dette er definitivt gjennomførbart med en datamaskin. Heldigvis for Alice og Bob, og for nettbank, kryptografer har utviklet sikrere måter å kryptere hemmelige meldinger fra nysgjerrige øyne. 

Men det er et emne for en annen tid. Mitt navn er Nate Hardison. Dette er CS50.