[Powered by Google Translate] [Vigenère Cipher]
[Nate Hardison - Harvard University]
[Dette er CS50. - CS50.TV]
Svarende til Alice.
Alice har en crush på Bob.
Heldigvis for Alice, Bob har også øje for hende.
Desværre for deres spirende romance,
ikke kun Alices forældre misbilliger Bob,
men Alice bedste ven, Evelyn, har en hemmelig crush på Bob
og egoistisk ønsker at holde dem fra hinanden på alle omkostninger.
For at sende hemmelige beskeder til hinanden, at Alices forældre ikke kan forstå,
>> Alice og Bob har brugt en Caesar cipher,
der virker ved forskydning alfabetet af et vist antal bogstaver
som en måde at generere et nyt alfabet.
Hvert bogstav i det oprindelige alfabet derefter erstattet af dens tilsvarende brev
i det nye forskudt alfabet.
Alices favorit nummer er 3, som Bob ved,
så hun bruger 3 som hendes nøgle.
Da hun flytter det engelske alfabet med 3 bogstaver,
A bliver D, B bliver E, C bliver F,
og så videre.
>> Når hun kommer til slutningen af ​​alfabetet - til bogstaverne X, Y og Z -
hun bare vikles rundt tilbage til begyndelsen af ​​alfabetet
og erstatninger X med A, Y med B, og Z med C.
Så da Alice går til at kryptere sin hemmelige besked til Bob,
nemlig "Mød mig i parken ved 11:00,"
hun bare gør de nødvendige udskiftninger.
M bliver P, E bliver H, og så videre indtil hendes ukrypteret meddelelse i almindelig tekst
omdannes til krypteret cipher tekst:
"Phhw ph dw WLO sdun dw hohyhq dp"
er bestemt ikke den mest romantiske klingende,
men Alice tror, ​​at det vil gøre.
>> Alice giver besked til Evelyn til at levere til Bobs hus.
Men Evelyn i stedet tager det tilbage til hendes værelse og forsøger at knække koden.
En af de første ting, Evelyn bekendtgørelser er, at bogstavet H optræder 7 gange i meddelelsen,
mange flere gange end nogen anden bogstav.
Vel vidende, at bogstavet E er den mest almindelige i det engelske sprog,
forekommer næsten 13% af tiden,
Evelyn gætter på, at H er erstattet af E for at gøre den hemmelige meddelelse
og forsøger ved hjælp af en nøgle på 3 for at dekryptere den.
>> Inden for få minutter, tal Evelyn ud Alice planer og ondt kalder Alices forældre.
Havde Alice og Bob taget CS50, ville de have vidst det
frekvens-analyse angreb på Caesar cipher,
som tillader den at blive brudt ganske hurtigt.
De ville også have vidst, at cipher er nemt underlagt en brute-force angreb,
hvorved Evelyn kunne have prøvet alle de mulige 25 taster,
eller forskydninger af det engelske alfabet,
for at dekryptere meddelelsen.
Hvorfor 25 taster, og ikke 26?
>> Tja, prøv at flytte helst bogstav med 26 positioner, og du vil se hvorfor.
Anyway, ville en brute-force angreb har taget Evelyn lidt længere
men ikke længe nok til at holde hende fra at modarbejde Alice og Bob planer,
især hvis Evelyn har hjælp af en computer
som kunne rip gennem alle 25 sager på et øjeblik.
Så dette problem også plaget andre, der brugte den Caesar cipher,
og derfor folk begyndte at eksperimentere med mere komplekse substitution ciphers
at brugen af ​​flere skift værdier i stedet for kun én.
Et af de mest kendte af disse kaldes Vigenère cipher.
Hvordan får vi flere skift værdier?
Nå, i stedet for at bruge et nummer som nøgle, bruger vi et ord for nøglen.
Vi vil bruge hvert bogstav i nøglen til at generere et nummer,
og effekten er, at vi vil have flere Caesar cipher-tasterne til at flytte breve.
>> Lad os se, hvordan det fungerer ved at kryptere Alices besked til Bob:
Mød mig på park ved 11:00
Jeg, personligt, mener bacon er lækre,
så lad os bruge det som nøgle.
Hvis vi tager budskabet i sin ukrypteret, almindelig tekst format,
vi se, at det er 25 bogstaver.
Bacon har kun 5 bogstaver, så vi er nødt til at gentage det 5 gange
at gøre det svarer til længden af ​​klartekst.
>> Bacon bacon bacon bacon bacon.
Som en kort side, hvis antallet af breve i klartekst
ikke dividere rent med antallet af bogstaver i nøglen,
vi bare ende den endelige gentagelse af vores nøgle tidligt,
bruger kun de breve, vi havde brug for at få det hele passer sammen.
Nu går vi om at finde de skiftværdier.
>> Vi vil gøre dette ved hjælp af placeringen af ​​hvert bogstav i vores nøgle - bacon -
i A til Z alfabet.
Da vi er dataloger, vi gerne begynde at tælle ved nul i stedet for 1,
så vil vi sige, at placeringen af ​​det første bogstav i bacon - B -
er i position 1 i nul-indekseret A til Z alfabet,
ikke 2, og positionen af ​​A er nul, ikke 1.
Under anvendelse af denne algoritme, kan vi finde skift værdier for hvert bogstav.
>> Til at kryptere almindelig tekst og generere cipher tekst,
vi bare flytte hvert bogstav i klartekst med den angivne mængde,
ligesom vi gør med Cæsar cipher, indpakning fra Z tilbage til A, hvis det er nødvendigt.
M bliver forskydes med 1 sted at blive N.
Den første E ikke skifter på alle, men vi flytter den anden E med 2 pladser til G
og T med 14 pladser til H.
Hvis vi arbejder gennem almindelig tekst, vi ender med,
"Negh zf av HUF pcfx bt gzrwep ounce"
Igen, ikke meget romantisk klingende men absolut kryptisk.
Hvis Alice og Bob havde kendt til Vigenère cipher,
ville de have været sikkert fra Evelyns nysgerrige øjne?
Hvad mener du?
Vil du ønsker at logge ind på din bankkonto, hvis din bank besluttede at bruge
>> Vigenère cipher at kryptere din kommunikation ved hjælp af din adgangskode som din nøgle?
Hvis jeg var dig, ville jeg ikke.
Og mens Evelyn kunne holdes travlt længe nok til Alice og Bob at få deres møde op,
det er ikke det værd for Alice og Bob at chance det.
Vigenère cipher er forholdsvis let at bryde, hvis du kender længden af ​​nøglen
fordi så kan du behandle den krypterede cipher tekst
som produktet af et par sammenflettede Cæsar ciphers.
>> Finde længden af ​​nøglen er ikke frygtelig hårdt, enten.
Hvis den oprindelige klartekst-meddelelsen er lang nok til, at nogle ord forekommer flere gange,
sidste ende vil du se gentagelse dukker op i den krypterede cifferliste tekst,
som i dette eksempel, MONCY hvor du kan se optræder to gange.
Derudover kan du udføre en brute-force angreb på cipher.
Det tager betydeligt længere tid end en brute-force angreb på Caesar cipher,
hvilket kan gøres næsten øjeblikkeligt med en computer
siden i stedet for 25 tilfælde at kontrollere du har fået 26 ⁿ - 1 muligheder,
hvor n er længden af ​​ukendt nøgle.
>> Dette skyldes, at hvert bogstav i nøglen kunne være enhver af de 26 bogstaver,
A til Z, og et smart person ville forsøge at anvende en nøgle, der ikke kan findes i en ordbog,
hvilket betyder, at du er nødt til at teste alle de underlige bogstavkombinationer, ligesom ZXXXFF,
og ikke bare et par hundrede tusind ord i ordbogen.
Den minus 1 kommer ind i matematik, fordi du ikke ønsker at bruge en nøgle med kun A'er,
siden med vores nul-indekseret alfabet, som vil give dig den samme effekt
som bruger en Caesar cipher med en nøgle på nul.
Anyway, 26 ⁿ - ikke 1 få stor ret hurtigt,
men mens du absolut ikke ønsker at prøve at bryde en cipher med hånden på denne måde,
dette er absolut doable med en computer.
Heldigvis for Alice og Bob, og for online banking,
kryptografer har udviklet mere sikre måder at kryptere hemmelige beskeder
mod nysgerrige blikke.
>> Men det er et emne til en anden gang.
Mit navn er Nate Hardison. Det er CS50.