[Powered by Google Translate] [Vigenère Cipher] [Nate Hardison - Harvard Universiteit] [Hierdie is CS50. - CS50.TV] Ontmoet Alice. Alice het 'n drukgang op Bob. Gelukkig vir Alice, Bob het ook oë vir haar. Ongelukkig vir hulle ontluikende romanse, Alice se ouers nie net afkeur van Bob, maar Alice se beste vriend, Evelyn, het 'n geheime crush op Bob en wil selfsugtig om hulle uitmekaar te hou ten alle koste. Om geheime boodskappe te stuur aan mekaar dat Alice se ouers kan nie verstaan ​​nie, 

Alice en Bob het al met behulp van 'n keiser cipher, wat werk deur die verskuiwing van die alfabet deur 'n sekere aantal letters as 'n manier om 'n nuwe alfabet te genereer. Elke letter in die oorspronklike alfabet word dan vervang deur die ooreenstemmende letter in die nuwe verskuif alfabet. Alice se gunsteling nommer is 3, wat Bob weet, so sy gebruik 3 as haar sleutel. Toe sy skuif die Engelse alfabet deur 3 letters, A word D, B word E, C word F, en so meer. 

Wanneer sy aan die einde van die alfabet - die letters X, Y en Z - sy vou net om terug na die begin van die alfabet en plaasvervangers X met A, Y met B, en Z met C. So wanneer Alice gaan haar geheime boodskap te enkripteer Bob, naamlik "Ontmoet my by die park op 11:00," sy maak net die toepaslike substitusies. M word P, E word H, en so aan totdat haar ongeënkripteerde plain text boodskap is aangeskakel in geïnkripteer cipher teks: "Phhw ph dw GH sdun dw hohyhq dp" is beslis nie die mees romantiese klinkende, maar Alice glo wat dit sal doen. 

Alice gee die boodskap aan Evelyn na Bob se huis te lewer. Maar Evelyn neem plaas dit terug na haar kamer en probeer om die kode te kraak. Een van die eerste dinge Evelyn kennisgewings is dat die letter H voorkom 7 keer in die boodskap, baie meer kere as enige ander letter. Wetende dat die letter E is die mees algemene in die Engelse taal, plaasgevind het byna 13% van die tyd, Evelyn raai dat H vir E is vervang ten einde die geheime boodskap te maak en probeer om met behulp van 'n sleutel van 3 te dekripteer. 

Binne minute, Evelyn figure uit Alice se planne en kwaad noem Alice se ouers. Het Alice en Bob geneem CS50, sou hulle geweet het van hierdie frekwensie-analise aanval op die keiser cipher, wat toelaat dat dit redelik vinnig gebreek word. Hulle sou ook geweet het dat die cipher maklik is onderhewig aan 'n brute krag aanval, waardeur Evelyn kon probeer het al van die moontlike 25 sleutels, of verskuiwings van die Engelse alfabet, ten einde die boodskap te ontsyfer. Waarom 25 sleutels en nie 26? 

Wel, probeer om die verskuiwing van 'n brief deur 26 posisies, en jy sal sien waarom. In elk geval, 'n brute krag aanval sou geneem het Evelyn 'n bietjie langer maar nie lank genoeg om haar te hou van die thwarting van Alice en Bob se planne, veral as Evelyn het die hulp van 'n rekenaar wat kan rip deur al 25 gevalle in 'n oomblik. So, hierdie probleem het ook ander wat die keiser cipher gebruik geteister, en dus mense het begin eksperimenteer met meer komplekse vervanging getalle wat gebruik verskeie verskuiwing waardes in plaas van net een. Een van die mees bekende van hierdie Vigenère cipher genoem. Hoe kry ons verskeie verschuiving waardes? Wel, in plaas van die gebruik van 'n getal as die sleutel, gebruik ons ​​'n woord vir die sleutel. Ons sal elke letter in die sleutel gebruik om 'n getal te genereer, en die effek is dat ons verskeie Caesar cipher-styl sleutels sal vir die verskuiwing van letters. 

Kom ons kyk hoe dit werk deur versleutelen Alice se boodskap Bob: Ontmoet my by die park op 11:00 Ek, persoonlik, dink spek is heerlik, so laat gebruik as die sleutel. As ons die boodskap in sy ongeënkripteerde, plain-text formaat, sien ons dat dit is 25 letters lank. Bacon het slegs 5 letters, sodat ons nodig het om dit 5 keer te herhaal om dit te laat ooreenstem met die lengte van die plain text. 

Bacon spek spek spek spek. 'N kort ter syde stel, indien die aantal letters in die plain text nie skoon verdeel deur die aantal letters in die sleutel, ons net die einde van die laaste herhaling van ons belangrikste vroeg, met behulp van slegs die letters wat ons nodig het om te maak alles grootgeword het. Nou gaan ons oor die vind van die verskuiwing waardes. 

Ons gaan om dit te doen deur gebruik te maak van die posisie van elke letter van ons sleutel - spek - in die A tot Z alfabet. Aangesien ons rekenaar wetenskaplikes, ons wil om te begin tel by nul in plaas van 1, so ons gaan om te sê dat die posisie van die eerste letter van die spek - B - is in posisie 1 in die nul-indexed A tot Z alfabet, nie 2, en die posisie van 'n nul is nie 1. Die gebruik van hierdie algoritme, kan ons die verskuiwing waardes vir elke letter. 

Die gewone teks te enkripteer en genereer cipher teks, ons net skuif elke letter in die plain text deur die gespesifiseerde bedrag net soos ons met die keiser cipher, wikkel van Z terug aan A indien nodig. M kry verskuif deur 1 plek om N. Die eerste e nie op alle skuif, maar ons skuif die tweede E 2 plekke tot G en T deur 14 plekke tot H. As ons werk deur die plain text, ons eindig met "Negh ZF av HUF pcfx bt gzrwep oz." Weereens, nie baie romanties klink, maar beslis kriptiese. As Alice en Bob het bekend oor Vigenère cipher, sou hulle gewees het veilig van Evelyn se gierige oë? Wat dink jy? Sou jy wil om aan te meld in jou bankrekening as jou bank besluit om te gebruik 

Vigenère cipher jou kommunikasie te enkripteer met jou wagwoord as jou sleutel? As ek jy was, sou ek nie. En terwyl Evelyn kan gehou word lank genoeg besig vir Alice en Bob om hul ontmoet-up, dit is nie die moeite werd vir Alice en Bob kans. Vigenère cipher is relatief maklik om te breek as jy die lengte van die sleutel want dan kan jy die geïnkripteer cipher teks behandel as die produk van 'n paar verweef Caesar getalle. 

Vind die lengte van die sleutel is nie vreeslik moeilik nie. As die oorspronklike plain-text boodskap is lank genoeg dat sommige woorde kom verskeie kere, uiteindelik sal jy sien herhaling opduik in die geïnkripteer cipher teks, soos in hierdie voorbeeld, waar jy sien MONCY twee keer verskyn. Verder kan jy 'n brute krag aanval op die cipher verrig. Dit beteken neem aansienlik langer as 'n brute krag aanval op die keiser cipher, wat byna onmiddellik kan gedoen word met 'n rekenaar want in plaas van 25 gevalle om seker te maak jy 26 ⁿ het - 1 moontlikhede, waar n die lengte van die onbekende sleutel. 

Dit is omdat elke letter in die sleutel kan wees enige van die 26 letters, A deur Z, en 'n slim persoon sal probeer om 'n sleutel te gebruik wat nie gevind word in 'n woordeboek, wat beteken dat jy wil hê al die vreemde letter kombinasies, soos ZXXXFF te toets, en nie net 'n paar honderd duisend woorde in die woordeboek. Die minus 1 kom in die wiskunde, omdat jy nie wil hê om 'n sleutel te gebruik met net 'n is, want met ons zero-indexed alfabet wat jou sal gee jou dieselfde effek as die gebruik van 'n keiser cipher met 'n sleutel van nul. In elk geval, 26 ⁿ - nie 1 kry groot redelik vinnig, maar terwyl jy sal beslis nie wil om te probeer om te breek van 'n cipher met die hand op hierdie manier, dit is beslis uitvoerbaar met 'n rekenaar. Gelukkig vir Alice en Bob, en vir aanlyn bankdienste, cryptografen het ontwikkel meer veilige maniere om geheime boodskappe te enkripteer van die gierige oë. 

Maar dit is 'n onderwerp vir 'n ander tyd. My naam is Nate Hardison. Dit is CS50.