Vigenèrova šifra

Vigenèrova šifra je polyalfabetickou šifrou, ve které šifrovaný text vzniká modulárním přičtením hesla k otevřenému textu. Šifrování lze proto vyjádřit vzorcem

C_{i} \equiv T_{i} + K_{i} \pmod {m}
Ci - i-tý znak šifrovaného textu
Ti - i-tý znak otevřeného textu
Ki - i-tý znak hesla textu (v případě, že je heslo kratší než text (což je obvyklé) dochází k opakování hesla)
m - délka abecedy

Dešifrování

K dešifrování dochází analogicky - modulárním odečtením hesla od šifrovaného textu.

T_{i} \equiv C_{i} - K_{i} \pmod {m}
Ti - i-tý znak otevřeného textu
Ci - i-tý znak šifrovaného textu
Ki - i-tý znak hesla textu (v případě, že je heslo kratší než text (což je obvyklé) dochází k opakování hesla)
m - délka abecedy

Vigenèrův čtverec

Pro zjednodušení modulárních operací se často používá tzv. Vigenèrův čtverec. Svojí logikou zcela odpovídá vzorcům uvedeným výše. Při šifrování vždy nalezneme znak otevřeného textu na vodorovné a znak hesla na svislé ose, jejich průsečíkem je znak šifrovaného textu. Při dešifrování v řádku odpovídajícímu příslušnému písmenu hesla nalezneme dané písmeno šifrovaného textu, otevřený text pak odpovídá označení sloupce.

ABCDEFGHIJKLMNOPQRSTUVWXYZ
AABCDEFGHIJKLMNOPQRSTUVWXYZ
BBCDEFGHIJKLMNOPQRSTUVWXYZA
CCDEFGHIJKLMNOPQRSTUVWXYZAB
DDEFGHIJKLMNOPQRSTUVWXYZABC
EEFGHIJKLMNOPQRSTUVWXYZABCD
FFGHIJKLMNOPQRSTUVWXYZABCDE
GGHIJKLMNOPQRSTUVWXYZABCDEF
HHIJKLMNOPQRSTUVWXYZABCDEFG
IIJKLMNOPQRSTUVWXYZABCDEFGH
JJKLMNOPQRSTUVWXYZABCDEFGHI
KKLMNOPQRSTUVWXYZABCDEFGHIJ
LLMNOPQRSTUVWXYZABCDEFGHIJK
MMNOPQRSTUVWXYZABCDEFGHIJKL
NNOPQRSTUVWXYZABCDEFGHIJKLM
OOPQRSTUVWXYZABCDEFGHIJKLMN
PPQRSTUVWXYZABCDEFGHIJKLMNO
QQRSTUVWXYZABCDEFGHIJKLMNOP
RRSTUVWXYZABCDEFGHIJKLMNOPQ
SSTUVWXYZABCDEFGHIJKLMNOPQR
TTUVWXYZABCDEFGHIJKLMNOPQRS
UUVWXYZABCDEFGHIJKLMNOPQRST
VVWXYZABCDEFGHIJKLMNOPQRSTU
WWXYZABCDEFGHIJKLMNOPQRSTUV
XXYZABCDEFGHIJKLMNOPQRSTUVW
YYZABCDEFGHIJKLMNOPQRSTUVWX
ZZABCDEFGHIJKLMNOPQRSTUVWXY
Vigenèrův čtverec

Frekvenční analýza Vigenèrovy šifry

Pokud známe délku hesla (X), tak můžeme provést frekvenční analýzu na každém X-tém znaku (heslo se opakuje). Nyní postupujeme stejně jako u analýzy Caesarovy šifry - porovnáním frekvence znaků otevřeného a šifrovaného textu zjistíme posun (písmeno hesla) a jsme schopni okamžitě dešifrovat.

Příklad

OT: KULTURNIATASEJESPION
Heslo: PES
26 znaků abecedy

Šifrování

K + P = 10 + 15 = 25 = Z
U + E = 20 + 4 = 24 = Y
L + S = 11 + 18 = 29 = 3 = D
T + P = 19 + 15 = 34 = 8 = I
U + E = 20 + 4 = 24 = Y
R + S = 17 + 18 = 35 = 9 = J
N + P = 13 + 15 = 28 = 2 = C
I + E = 8 + 4 = 12 = M
A + S = 0 + 18 = 18 = S
T + P = 19 + 15 = 34 = 8 = I
A + E = 0 + 4 = 4 = E
S + S = 18 + 18 = 36 = 10 = K
E + P = 4 + 15 = 19 = T
J + E = 9 + 4 = 13 = N
E + S = 4 + 18 = 22 = W
S + P = 18 + 15 = 33 = 7 = H
P + E = 15 + 4 = 19 = T
I + S = 8 + 18 = 26 = 0 = A
O + P = 14 + 15 = 19 = 3 = D
N + E = 13 + 4 = 17 = R

ŠT: ZYDIYJCMSIEKTNWHTADR

Dešifrování

ŠT: ZYDIYJCMSIEKTNWHTADR
Heslo: PES
26 znaků abecedy

Z - P = 25 - 15 = 10 = K
Y - E = 24 - 4 = 20 = U
D - S = 3 - 18 = 11 = L
I - P = 8 - 15 = 19 = T
Y - E = 24 - 4 = 20 = U
J - S = 9 - 18 = 17 = R
C - P = 2 - 15 = 13 = N
M - E = 12 - 4 = 8 = I
S - S = 18 - 18 = 0 = A
I - P = 8 - 15 = 19 = T
E - E = 4 - 4 = 0 = A
K - S = 10 - 18 = 18 = S
T - P = 19 - 15 = 4 = E
N - E = 13 - 4 = 9 = J
W - S = 22 - 18 = 4 = E
H - P = 7 - 15 = 18 = S
T - E = 19 - 4 = 15 = P
A - S = 0 - 18 = 8 = I
D - P = 3 - 15 = 14 = O
R - E = 17 - 4 = 13 = N

OT: KULTURNIATASEJESPION

Kód

/**
 * Vigenerova sifra - demonstrace
 * @author Pavel Micka
 */
public class VigenereCipher {
    /**
     * Zasifruje text Vigenerovou sifrou
     * @param s otevreny text
     * @param key klic (jen velka pismena)
     * @return zasifrovany text (jen velka pismena)
     */
    public static String encipher(String s, String key){
        StringBuilder builder = new StringBuilder();
        for(int i = 0; i < s.length(); i ++){
            if(s.charAt(i) < 65 || s.charAt(i) > 90){ //znak v ASCII
                throw new IllegalArgumentException("" +
                        "Sifrovany retezec neobsahuje jen velka pismena");
            }
            //modularne pricteme shift
            char encyphered = s.charAt(i) + getShift(key, i) > 90 ? (char)((s.charAt(i) + getShift(key, i)) - 26) : (char)(s.charAt(i) + getShift(key, i));
            builder.append(encyphered);
        }
        return builder.toString();
    }
    /**
     * Desifruje dany zasiforvany text Vigenerovou sifrou
     * @param s zasifrovany text
     * @param key klic
     * @return otevreny text
     */
    public static String decipher(String s, String key){
        StringBuilder builder = new StringBuilder();
        for(int i = 0; i < s.length(); i ++){
            if(s.charAt(i) < 65 || s.charAt(i) > 90){ //znak v ASCII
                throw new IllegalArgumentException("" +
                        "Desifrovany retezec neobsahuje jen velka pismena");
            }
            //modularne odecteme shift
            char decyphered = s.charAt(i) - getShift(key, i) < 65 ? (char)((s.charAt(i) - getShift(key, i)) + 26) : (char)(s.charAt(i) - getShift(key, i));
            builder.append(decyphered);
        }
        return builder.toString();
    }
    /**
     * Zjisti shift
     * @param key klic
     * @param i pozice v textu
     * @return shift
     */
    private static int getShift(String key, int i) {
            if(key.charAt(i % key.length()) < 65 || key.charAt(i % key.length()) > 90){ //znak v ASCII
                throw new IllegalArgumentException("" +
                        "Klic retezec neobsahuje jen velka pismena");
            }
        return ((int)key.charAt(i % key.length())) - 65;
    }
    
    public static void main(String[] args){
        String text = "KULTURNIATASEJESPION";
        String key = "PES";
        String enciphered = encipher(text, key);
        System.out.println(enciphered);
        System.out.println(decipher(enciphered, key));
    }
}
{ zpětná vazba }
Delicious Delicious
Sdílet
Hodnocení (3): 3,67

Přečtěte si také

Diskuse





Pavel Mička14.4.2011
Ahoj,

se syntaxí Matlabu nejsem schopen poradit, neb jej aktuálně nemám nainstalovaný a vždy jsem v něm pracoval poněkud ad-hoc. Ale přijde mi jako nesmysl to počítat přes matici, když ta funkce lze zapsat pomocí modulární aritmetiky na jeden řádek (ta matice je spíš "jak to funguje", než že by se to přes ní mělo implementovat :-)).

To length by mělo fungovat, co si pamatuju... jenom nevím, jestli to bere velikost řádkového nebo sloupcového vektoru. Čili buď případně transponovat, nebo použit funkci size (která počítá velikost obdélníkové matice) a vzít rozměr v příslušné dimenzi.

petr13.4.2011
čau
zkouším vigenerovu šifru jako projekt do programování, pracujeme v prostředí matlab, ale nemám moc zkušeností, vigenèrův čtverec načítám jako matici... a můžu říct že mi háže error, ikdyž mám matici stilisticky dobře...
potřeboval bych proradit jak vytvořit ten program, mělo by to být přes funkci
já ji navthl
function [y] = sifrovani1 (h,z,t)
% h - zadané heslo
% z - proměnná dle které se vybírá funkce
% t - samostatný text na zasifrovani
a také mě vůbec nenapadá jak zjistit délku hesla zkoušel jsem to pře length(t)ale nic
po případně poradit nějaké jiné jednoduché téma na projekt
předem díky za pomoc
Pavel Mička29.1.2010
Tak jsem článek vylepšil, jak jsem slíbil :-).
Pavel Mička22.1.2010
Zkus si to pricist modularne...tenhle postup je zcela totozny (jen jiny zapis)...ale uznavam, ze by to melo byt nahore ve "clanku" (ted to neni moc clanek) lepe specifikovano.
tomy22.1.2010
Oceňujem takéto stránky, ale musím upozorniť na nepresnosť v postupe pri šifrovaní a dešifrovaní. Správny postup je takýto: 1)nad šifrovaný text sa zapíše šifrovací kľúč, ak je príliš krátky, periodicky sa opakuje 2)následne sa hľadajú priesečniky riadku a stĺpca príslušných dvojíc písmen vo Vigenerovom štvorci napr. heslo je kniha; šifrovaný text: matematika Kľúč knihakniha text matematika šifra wnblmkgqra