[Powered by Google Translate] [Vigenère Cipher] [Nate Hardison - Harvarduniversitetet] [Detta är CS50. - CS50.TV] Möt Alice. Alice har en crush på Bob. Lyckligtvis för Alice har Bob också ögonen för henne. Tyvärr för deras spirande romans, inte bara ogillar Alice föräldrar av Bob, men Alice bästa vän, Evelyn, har en hemlig fruktdryck på Bob och själviskt vill hålla isär dem till varje pris. Om du vill skicka hemliga meddelanden till varandra att Alice föräldrar inte kan förstå, 

Alice och Bob har använt en Caesar chiffer, som fungerar genom att flytta alfabetet med ett visst antal bokstäver som ett sätt att generera en ny alfabet. Varje bokstav i det ursprungliga alfabetet sedan ersätts med motsvarande bokstav i den skiftade nya alfabetet. Alice favorit nummer är 3, som Bob vet, så hon använder 3 som sin nyckel. När hon flyttar det engelska alfabetet med 3 bokstäver, A blir D, blir B-E, C blir F, och så vidare. 

När hon får till slutet av alfabetet - till bokstäverna X, Y och Z - Hon sveper runt tillbaka till början av alfabetet och substitut X med A, Y med B och Z med C. Så när Alice går att kryptera sin hemliga budskap till Bob, nämligen "Möt mig i parken vid 11:00," Hon gör bara lämpliga substitutioner. M blir P blir E H, och så vidare tills hon okrypterade oformaterad text omvandlas till krypterad chiffertext: "Phhw ph dw DY sdun dw hohyhq DP" är definitivt inte den mest romantiska klingande, men Alice tror att det kommer att göra. 

Alice ger meddelandet till Evelyn leverera till Bob hus. Men Evelyn tar istället tillbaka till sitt rum och försöker knäcka koden. En av de första saker Evelyn meddelanden är att bokstaven H förekommer 7 gånger i meddelandet, många fler gånger än någon annan bokstav. Att veta att bokstaven E är den vanligaste på engelska, förekommer nästan 13% av tiden, Evelyn gissar att H har ersatts för E för att göra den hemliga meddelandet och försöker med hjälp av en nyckel 3 att dekryptera det. 

Inom några minuter, siffror Evelyn ut Alice planer och elakt kallar Alice föräldrar. Hade Alice och Bob tagit CS50, skulle de ha känt till detta frekvens-analys attack mot Caesar chiffer, vilket gör att den kan brytas ganska snabbt. De skulle också ha vetat att chiffret är lätt föremål för en brute-force attack, där Evelyn kunde har försökt alla möjliga 25 tangenter, eller förskjutningar av det engelska alfabetet, För att dechiffrera meddelandet. Varför 25 tangenter och inte 26? 

Tja, försök flytta en bokstav med 26 positioner, och du kommer att se varför. Hur som helst skulle en brute-force attack tagit Evelyn lite längre men inte tillräckligt länge för att hålla henne från att motarbeta Alice och Bob planer, speciellt om Evelyn har hjälp av en dator vilket kan rippa genom alla 25 fall i ett ögonblick. Så detta problem plågas också andra som använde Caesar chiffer, och därför människor började experimentera med mer komplexa substitution chiffer som använder flera skift värden i stället för bara en. En av de mest välkända av dessa kallas Vigenère chiffer. Hur får vi flera skift värderingar? Tja, i stället för att använda ett antal som nyckeln använder vi ett ord för nyckeln. Vi kommer att använda varje bokstav i nyckeln för att generera ett antal, och effekten är att vi kommer att ha flera Caesar chiffer-stil nycklar för att flytta bokstäver. 

Låt oss se hur det fungerar genom att kryptera Alice budskap till Bob: Möt mig i parken vid 11:00 Jag personligen tycker bacon är läcker, så låt oss använda det som nyckeln. Om vi ​​tar budskapet i dess okrypterat, vanlig textformat, ser vi att det är 25 bokstäver långa. Bacon har bara 5 bokstäver, så vi måste upprepa det 5 gånger att göra det matchar längden av klartext. 

Bacon bacon bacon bacon bacon. Som en kort undan, om antalet bokstäver i klartext inte dela rent av antalet bokstäver i nyckeln, Vi avslutar bara den sista upprepning av vår nyckel tidigt, endast med de bokstäver som vi behövde för att göra allting stämmer. Nu går vi om att hitta de skiftvärden. 

Vi ska göra detta genom att använda läget för varje bokstav i vår nyckel - bacon - i A till Z alfabetet. Eftersom vi är datavetare, vill vi börja räkna på noll i stället för 1, så vi kommer att säga att läget för den första bokstaven i bacon - B - är i position 1 i den noll-indexerade A till Z alfabetet, inte 2, och placeringen av A är noll, inte 1. Med hjälp av denna algoritm kan vi hitta skift värden för varje bokstav. 

Att kryptera klartext och generera chiffertext, Vi skiftar bara varje bokstav i klartext med angivet belopp, precis som vi gör med Caesar chiffer, omslag från Z till A om det behövs. M blir skiftas med 1 plats för att bli N. Den första E skiftar inte alls, men vi skiftar den andra E med 2 platser till G och T med 14 platser till H. Om vi ​​arbetar igenom klartext, hamnar vi med, "Negh ZF AV HUF pcfx BT gzrwep oz." Igen, inte mycket romantisk klingande men definitivt kryptiskt. Om Alice och Bob hade vetat om Vigenère chiffer, skulle de ha varit säker från Evelyns nyfikna ögon? Vad tycker du? Skulle du vill logga in på ditt bankkonto om din bank beslutat att använda 

Vigenère chiffer för att kryptera din kommunikation med lösenord som din nyckel? Om jag var du, skulle jag inte. Och medan Evelyn skulle hållas upptagen länge nog för Alice och Bob att få sina möta upp, det är inte värt det för Alice och Bob att chans det. Vigenère chiffer är relativt lätt att bryta om du vet längden på nyckeln för då kan du behandla den krypterade chiffertext som en produkt av ett fåtal sammanvävda Caesar chiffer. 

Hitta längden på nyckeln är inte särskilt svårt heller. Om den ursprungliga klartext meddelandet är långt nog att vissa ord förekommer flera gånger, så småningom kommer du se upprepning dyka upp i den krypterade chiffertext, som i detta exempel, där du ser visas MONCY två gånger. Dessutom kan du utföra en brute-force attack mot chiffer. Detta tar betydligt längre tid än en brute-force attack mot Caesar chiffer, vilket kan göras nästan omedelbart med en dator eftersom istället för 25 fall kontrollera att du har 26 ⁿ - 1 möjligheter, där n är längden av den okända nyckeln. 

Detta beror på att varje bokstav i nyckeln kan vara vilken som helst av de 26 bokstäverna, A till Z, och en smart person skulle försöka använda en nyckel som inte kan hittas i ett lexikon, vilket innebär att du måste testa alla de konstiga bokstavskombinationer, som ZXXXFF, och inte bara ett par hundra tusen ord i ordlistan. Minus 1 kommer in i matten eftersom du inte vill använda en nyckel med endast A är, eftersom med vår noll-indexerad alfabet som skulle ge dig samma effekt som använder en Caesar chiffer med en nyckel noll. Hur som helst, 26 ⁿ - blir 1 stor ganska snabbt, men medan du definitivt inte vill försöka bryta ett chiffer för hand på detta sätt, detta är definitivt genomförbart med en dator. Lyckligtvis för Alice och Bob, och för internetbanker, kryptografer har utvecklat säkrare sätt att kryptera hemliga meddelanden från nyfikna ögon. 

Men det är ett ämne för en annan tid. Mitt namn är Nate Hardison. Detta är CS50.