Vižnerova šifra

Vižnerova šifra je dobila ime po Blezu de Vižneru.

Vižnerova šifra je metod šifrovanja azbučnog teksta korišćenjem serije Cezarovih šifara, zasnovanih na slovima ključa. Ovo je prosti oblik šifre polialfabetske zamene.

Vižnerova šifra je otkrivana više puta. Metod je prvi opisao Đovan Batista Belazo (ital. Giovan Battista Bellaso); međutim, kasnije, u 19. veku je ta šema pogrešno pripisana Blezu de Vižneru (franc. Blaise de Vigenère), tako da je sad poznata kao „Vižnerova šifra“.

Šifra je dobro poznata zato što, iako je laka za razumevanje i primenu, početnicima izgleda kao neprobojna; tako je i dobila epitet franc. le chiffre indéchiffrable - непробојна шифра. Stoga su mnogi pokušavali da primene šeme šifrovanja, koje su u osnovi Vižnerova šifra.

Istorija

Prva polialfabetska šifra, koju je napravio Leon Batista Alberti (ital. Leon Battista Alberti) oko 1467, je koristila metalnu šifarsku ploču za zamenu šifarskih alfabeta. Albertijev sistem je menjao alfabete posle nekoliko reči, a zamena je označavana slovom odgovarajućeg alfabeta u šifratu. Kasnije, Johan Tritemijus (nem. Johannes Trithemius - Јохан Хајденберг, по месту рођења Јохан из Тритенхајма) u svom delu iz 1508. Polygraphia je izumeo kvadratnu tablicu (lat. tabula recta), ključnu komponentu Vižnerove šifre. Međutim, on je dao samo rastući, krut i predvidljiv sistem zamene šifarskih alfabeta.

Ono što je sada poznato pod imenom Vižnerove šifre je prvobitno opisao Belazo 1553. u svojoj knjizi ital. La cifra del. Sig. Giovan Battista Bellaso. Napravio je prema Tritemijusovoj tablici, ali je dodao ponavljajući ključ za promenu šifarskog alfabeta za svako slovo.

Blez de Vižner je 1586. objavio svoj opis slične, ali jače šifre sa „autoključem“ pred dvorom Anrija III (kralj Francuske i Poljske). Kasnije, u 19. veku, pronalazak Belazoove šifre je pogrešno pripisan Vižneru. Dejvid Kan, u svojoj knjizi engl. The Codebreakers - Разбијачи кодова, kaže da je istorija „ignorisala ovaj važan doprinos i nazvala regresivnu i osnovnu šifru po njemu [Vižneru], iako on ništa nema sa tim“.

Reprodukcija šifarskog diska Konfederacije. Poznato je da postoji samo pet originala.

Vižnerova šifra je stekla reputaciju kao izuzetno jaka. Poznati pisac i matematičar Čarls Latvidž Dodžson (poznatiji kao Luis Kerol) je Vižnerovu šifru nazvao neprobojnom u svom delu iz 1868. engl. The Alphabet Cipher - Алфабетска шифра u dečjem časopisu. Časopis engl. Scientific American je 1917. opisao Vižnerovu šifru kao „nemoguća za prevod“. Ova reputacija je nezaslužena, jer je Kaziski još u 19. veku potpuno razbio šifru, a poznato je da su je neki kriptoanalitičari povremeno razbijali još u 16. veku.

Vižnerova šifra je dovoljno jednostavna za poljsku upotrebu ako se koristi u sprezi sa šifarskim diskovima. Konfederativne Američke Države, na primer, su koristile bronzane šifarske diskove za primenu Vižnerove šifre za vreme Američkog građanskog rata. Poruke Konfederacije su bile daleko od tajne i Unija je redovno razbijala njihove poruke. Za vreme rata, vođe Konfederacije su se prvenstveno oslanjale na tri ključa, engl. Manchester Bluff, Complete Victory, Come Retribution (ova poslednja pri kraju rata).

Gilbert Vernem je pokušao da popravi razbijenu šifru (kreirajući Vernem-Vižnerovu šifru 1918), ali i bez obzira na to, šifra je za kriptoanalitičare i dalje bila ranjiva. Međutim, Vernamov rad je doveo do "jednokratne beležnice" (engl. one-time pad), provereno neprobojne šifre.

Opis

Vižnerova tablica, takođe poznata i kao tabula recta, može da se koristi za šifrovanje i dešifrovanje.

Kod Cezarove šifre, svako slovo alfabeta se pomera za neki broj mesta; na primer, sa pomakom 3, slovo A postaje D, B postaje E itd. Vižnerova šifra se sastoji od niza nekoliko Cezarovih šifara sa različitim pomacima.

Za šifrovanje može da se koristi tablica alfabeta, nazvana tabula recta, Vižnerova tablica ili Vižnerov kvadrat. Sastoji se od alfabeta napisanog 26 puta u novom redu, svaki red rotiran ulevo u odnosu na prethodni, odgovarajući svim mogućim kombinacijama (26) Cezarove šifre. U pojedinoj tački procesa šifrovanja, šifra koristi drugi alfabet iz jednog od redova. Koji će se red koristiti zavisi od ponavljajućeg ključa.

Na primer, recimo da je otvoreni tekst koji treba da se šifruje:

ATTACKATDAWN

Osoba koja šalje poruku bira ključ i ponavlja ga onoliko puta koliko je potrebno da odgovara dužini otvorenog teksta, npr, ključ LEMON:

LEMONLEMONLE

Prvo slovo otvorenog teksta A se šifruje koristeći alfabet iz reda L, koje je prvo slovo ključa. To se radi tako što se traži slovo u redu L i koloni A Vižnerove tablice, odnosno traženo slovo je L. Za sledeće slovo otvorenog teksta se koristi sledeće slovo ključa, slovo u preseku reda E i kolone T je traženo slovo X. Po tom sistemu se nastavlja do kraja otvorenog teksta: Otvoreni tekst: ATTACKATDAWN Ključ: LEMONLEMONLE Šifrat: LXFOPVEFRNHR

Dešifrovanje se vrši traženjem mesta šifrovanog slova u redu tabele, a kao slovo otvorenog teksta se uzima naslov kolone. Na primer, u redu L, šifrovano L se nalazi u koloni sa naslovom A, koji se uzima kao prvo slovo otvorenog teksta. Sledeće slovo se dešifruje traženjem slova X u redu E - ono se nalazi u koloni T i to je traženo slovo otvorenog teksta.

Vižnerova šifra može da se predstavi i algebarski. Ako se slovima abecede A do Z dodele vrednosti 0 do 25 i izvrši sabiranje po modulu 26, šifrovanje može da se napiše kao

$S_{i}\equiv O_{i}+K_{i}{\pmod {26}}$

a dešifrovanje kao

$O_{i}\equiv S_{i}-K_{i}{\pmod {26}}$

(O - otvoreni tekst, S - šifrat, K - ključ)

Kriptoanaliza

Vižnerova šifra je efikasna jer maskira karaktersitičnu frekvenciju slova otvorenog teksta, ali određeni uzorak ipak ostaje.

Snaga Vižnerove šifre, kao i svih polialfabetskih šifara, je njena sposobnost otežavanja frekventne analize. Frekventna analiza je veština dekriptovanja poruke brojanjem frekvencije slova šifrata i upoređivanje sa frekvencijom slova normalnog teksta. Na primer, ako se slovo K javlja najveći broj puta u šifratu čiji je otvoreni tekst na srpskom, može se pretpostaviti da K odgovara slovu A, jer je slovo A najčešće u srpskom jeziku. Korišćenjem Vižnerove šifre, slovo A će se zamenjivati različitim slovima alfabeta na različitim mestima u poruci i tako onemogućiti prostu frekventnu analizu.

Osnovna slabost Vižnerove šifre je njen reklativno kratak i ponavljajući ključ. Ako kriptoanalitičar otkrije dužinu ključa, onda šifrat može da se posmatra kao serija Cezarovih šifara, koje se zatim pojedinačno jednostavno razbijaju. Testovi Kaziskog i Fridmena pomažu u određivanju dužine ključa.

Kaziskijev test

Fridrih Kaziski je 1863. prvi objavio uspešan napad na Vižnerovu šifru, ali Čarls Bebidž je još 1854. razvio isti test. Za razbijanje Vižnerove šifre Bebidž je bio podstaknut kad je Džon Hol Brok Tvejts objavio „novu“ šifru u časopisu Journal of the Society of the Arts: Kad je Bebidž objavio da je to samo još jedna varijanta Vižnerove šifre, Tvejts se razljutio i izazvao Bebidža da razbije šifru. Bebidž je uspeo da dekriptuje uzorak, za koji se ispostavilo da je pesma „Vizija greha“ Alfreda Tenisona, a korišćen je ključ "Emily", ime Tenisonove žene..

Test Kaziskog koristi činjenicu da će pojedine česte reči verovatno biti šifrovane istim slovima ključa, pa će se u šifratu pojaviti ponovljene grupe slova. Na primer, poruka šifrovana ključem ABCDEF neće šifrovati crypto isto svaki put kad se pojavi u otvorenom tekstu:

Ključ: ABCDEF AB CDEFA BCD EFABCDEFABCD Otvoreno: CRYPTO IS SHORT FOR CRYPTOGRAPHY Šifrat: CSASXT IT UKSWT GQU GWYQVRKWAQJB

Šifrat u ovom primeru nema ponovljene nizove slova koji odgovaraju ponovljenim nizovima otvorenog teksta. Međutim, ako je dužina ključa različita, kao u ovom primeru:

Ključ: ABCDAB CD ABCDA BCD ABCDABCDABCD Otvoreno: CRYPTO IS SHORT FOR CRYPTOGRAPHY Šifrat: CSASTP KV SIQUT GQU CSASTPIUAQJB

onda je Kaziskijev test efikasan. Kod dužih poruka je test tačniji, jer obično sadrži više ponovljenih segmenata. Sledeći šifrat ima nekoliko ponovljenih segmenata i omogućava kriptoanalitičaru da otkrije dužinu ključa:

Šifrat: DYDUXRMHTVDVNQDQNWDYDUXRMHARTJGWNQD Rastojanje između ponovljenog DYDUXRMH je 18. Stoga, pretpostavljajući da ponovljeni segmenti predstavljaju ponovljene segmente otvorenog teksta, nagoveštava da ključ ima dužinu od 18, 9, 6, 3 ili 2 znaka. Razmak između NQD je 20 znakova. To znači da bi dužina ključa mogla da bude 20, 10, 5, 4 ili 2 znaka (svi delioci rastojanja su moguće dužine ključa - ključ dužine 1 je obična šifra pomeranja, gde je kriptoanaliza mnogo jednostavnija). Korišćenjem preseka ova dva skupa, može da se zaključi da je dužina ključa (gotovo sigurno) 2. Naravno, u praksi se nikad neće koristiti ključ dužine 1 ili 2, ovde je naveden samo radi ilustracije.

Fridmenov test

Ovaj test (poznat i kao „Kapa test") je 1920. otkrio Viljem Fridmen. Fridmen je za razbijanje šifre upotrebio "indeks podudarnosti" (engl. index of coincidence - I.C.), koji meri neravnomernost frekvencije slova šifre. Ako znamo verovatnoću $\kappa _{p}$ da u dva nasumično izabrana teksta slova budu ista (za engleski oko 0,067) i verovatnoću podudaranja nasumične selekcije alfabeta $\kappa _{r}$ (1/26 = 0.0385), dužina ključa može da se odredi kao

${\kappa _{p}-\kappa _{r}} \over {\kappa _{o}-\kappa _{r}}$

iz uočene mere podudarnosti

$\kappa _{o}={\frac {\sum _{i=1}^{c}n_{i}(n_{i}-1)}{N(N-1)}}$

gde je $c$ veličina alfabeta (26), $N$ je dužina teksta, a $n_{1}$ do $n_{c}$ su frekvencije slova šifrata.

Ovo je samo aproksimacija čija tačnost se povećava sa dužinom teksta. U praksi će se probati različite dužine ključeva bliskih procenjenoj. Bolji pristup za šifre sa ponovljenim ključem je da se šifrat kopira u tabelu koja ima onoliko kolona kolika je pretpostavljena dužina ključa, a zatim da se za svaku kolonu posebno izračuna indeks podudarnosti; kad se to uradi za svaku moguću dužinu ključa, najveći prosečni I.C. će odgovarati verovatnoj dužini ključa. Takav test se može dopuniti podacima iz Kaziskijevog testa.

Frekventna analiza

Kad se odredi dužina ključa, šifrat se deli u sekcije tako da svaka sekcija odgovara ključu za jedno slovo. Svaki deo je ekvivalentan šifratu jedne Cezarove šifre. Pomaci su određeni slovima ključa. Dalje se koristi metod kojim se razbija Cezarova šifra.

Varijanta Kaziskijevog testa je Kerkhofsov metod, određivanje ključa dedukcijom na osnovu frekvencije reči u uporednim šifratima.

Varijante

Varijanta Vižnerove šifre uzastopni ključ (engl. running key) je takođe nekad smatrana kao neprobojna. Ova verzija kao ključ koristi blok teksta dužine otvorenog teksta. Pošto je ključ dugačak kao i poruka, testovi Kaziskog i Fridmena više ne vrede - ključ se ne ponavlja. Fridmen je 1920. prvi otkrio slabost ove varijante. Problem kod Vižnerove šifre sa uzastopnim ključem je što kriptoanalitičar ima statističke informacije o ključu (pod pretpostavkom da je blok teksta iz poznatog jezika) i ta osobina će se odraziti u šifratu.

Ako se koristi ključ koji je potpuno slučajan, ako je dugačak kao poruka i koristi se samo jednom, Vižnerova šifra je teoretski neprobojna. U tom slučaju ključ, a ne šifra, obezbeđuje kriptografsku otpornost, i ti sistemi se zajednički zovu "jednokratna beležnica" (engl. one-time pad), nevezano za za to koja šifra je primenjena.

Vižner je u stvari otkrio jaču šifru, šifru sa autoključem, iako je njegovo ime vezano za jednostavniju polialfabetsku šifru. U stvari, te dve šifre se često mešaju, a obe su nekad imale epitet franc. le chiffre indéchiffrable. Bebidž je u stvari razbio jaču šifru sa autoključem, dok se Kaziskom načelno daje zasluga za prvo objavljeno rešenje polialfabetske šifre sa fiksnim ključem.

Otvoreno: SASTANAKUPODNE Ključ: KLJUC Autoključ: KLJUCSASTANAKU Šifrat: CLBNCFACNPBDXY

Prostija varijanta je da se šifrovanje izvodi po metodu dekripcije Vižnerove šifre, a dekriptovanje korišćenjem šifrovanja, metod koji je poznat kao „Boforova varijanta“ (Ser Fransis Bofort, engl. Francis Beaufort): S = K – O, a dešifrovanje kao O = K – S, uz korišćenje tzv. Sestrijeve (ital. Giovanni Sestri) tablice:

   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Z  Z Y X W V U T S R Q P O N M L K J I H G F E D C B A
Y  Y X W V U T S R Q P O N M L K J I H G F E D C B A Z

. . . . . . . . . . . . . . . . . . . . . . . . . . .

A  A Z Y X W V U T S R Q P O N M L K J I H G F E D C B

Uprkos očiglednoj jačini, Vižnerova šifra u Evropi nije bila u širokoj upotrebi. Gronsfeldova šifra je varijanta koja je identična Vižnerovoj šifri, osim što koristi 10 šifarskih alfabeta (koji odgovaraju ciframa 0 do 9). Šifra je pojačana jer ključ nije reč, ali je oslabljena jer koristi samo 10 šifarskih alfabeta. Uprkos toj slabosti, Gronsfeldova šifra je bila u širokoj upotrebi u Nemačkoj i u Evropi.

Vidi još

• Glosar kriptologije

Literatura

• Smith, Laurence D. (1943). „Substitution Ciphers”. Cryptography the Science of Secret Writing: The Science of Secret Writing. Dover Publications. str. 81. ISBN 978-0-486-20247-1. 
• David, Kahn (1999). „On the Origin of a Species”. The Codebreakers: The Story of Secret Writing. Simon & Schuster. ISBN 978-0-684-83130-5. 
• Knudsen, Lars R. (1998). „Block Ciphers— a survey”. Ur.: Bart Preneel and Vincent Rijmen. State of the Art in Applied Cryptography: Course on Computer Security and Industrial Cryptograph Leuven Belgium, June 1997 Revised Lectures. str. 29. ISBN 978-3-540-65474-2. 
• David, Kahn (1999). „Crises of the Union”. The Codebreakers: The Story of Secret Writing. Simon & Schuster. str. 217—221. ISBN 978-0-684-83130-5. 
• Singh, Simon (1999). „Chapter 2: Le Chiffre Indéchiffrable”. The Code Book. Anchor Book, Random House. str. 63—78. ISBN 978-0-385-49532-5. 
• Henk C.A. van Tilborg, ur. (2005). Encyclopedia of Cryptography and Security (1. izd.). Springer. str. 115. ISBN 978-0-387-23473-1. 

Spoljašnje veze

Članci

• History of the cipher from Cryptologia
• Basic Cryptanalysis at H2G2
• Lecture Notes on Classical Cryptology including an explanation and derivation of the Friedman Test

Programiranje

• Sharky's Online Vigenere Cipher – Encode and decode messages, using a known key, within a Web browser (JavaScript)
• PyGenere: an online tool for automatically deciphering Vigenère-encoded texts (6 languages supported)
• Tim's Vigenère Cracker Another tool for automatic decyphering using an entropy-based approach. English only.
• Crypt::Vigenere – a CPAN module implementing the Vigenère cipher
• Breaking the indecipherable cipher: Perl code to decipher Vigenère text, with the source in the shape of Babbage's head
• Vigenère Cipher, an implementation - Sources in Java and C (GNU GPL)
• Java Vigenere applet with source code (GNU GPL)