Nemáte prístup k Vášmu heslu?
Vernamova šifra
Matematicky dokázaná nerozlúštiteľná šifra - na používanie ktorej vám stačí ceruzka a papier.
Asi všetci poznajú jednoduchú tzv. Vigenerovu šifru. Hrá dôležitú úlohu napríklad v románe Julesa Verna 800 míľ po Amazone. Namiesto vysvetľovania príklad. Kľúčom je číselný reťazec, ktorý sa stále opakuje - 3375. Algoritmom je jednoduché sčítavanie, resp. posúvanie podľa abecedy.
T O T O J E S T R A S N E T A J N A S P R A V A
3 3 7 5 3 3 7 5 3 3 7 5 3 3 7 5 3 3 7 5 3 3 7 5
---------------------------------------------------------
W R A T M H Z Y U D Z S H W H O Q D Z U U D C F
Pre tých, ktorí si nepamätajú abecedu: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Pre duševne unavených:
T+3=W
(T, U - V - W).
Dešifrovanie prebieha opačne.
Táto triviálna šifra sa mení na nerozlúštiteľnú, pokiaľ splníme nasledovné podmienky:
a/ Kľúč je rovnako dlhý ako správa
b/ Kľúč je tvorený zaručene náhodným reťazcom
c/ Kľúč sa použije jediný raz.
Takáto šifra sa nazýva Vernamova, alebo one-time-pad.
Vigenerova šifra a jej realizácia v Exceli
Šifrovanie je písanie správ dohodnutými znakmi, heslami, číslicami podľa
určitého kľúča. Takto pozmenená pôvodná správa sa nazýva zašifrovaná správa.
Francúz Blaise de Vigenere nahrádzal jednotlivé znaky pôvodnej správy (vzory)
inými znakmi (obrazmi, šiframi) tak, že používal tabuľku 1. Používal len veľké
písmená anglickej abecedy tak, ako sú uvedené v hlavičke tabuľky 1. Medzery
a diakritika sa ignorujú.
Definície
• Znak je jedno písmeno Vigenerovej tabuľky.
• Šifra je zašifrovaný znak.
• Správa je usporiadaná množina znakov (text).
• Dĺžka správy je počet jej znakov. Pôvodná správa a zašifrovaná správa majú
rovnakú dĺžku.
3
• Dĺžka kľúča je počet jeho znakov.
• Kód znaku je ASCII kód tohoto znaku. Kód(A)=65, kód(B) =66, ..., kód(Z) = 90.
• Pseudovzdialenosť
dvoch susedných znakov je rozdiel ich kódov.
Pseudovzdialenosť môže nadobúdať kladné aj záporné celé čísla.
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
A 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
B 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 A
C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z Z 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
Tab. 1. De Vigenerova tabuľka
Príklad. Posiela sa správa PRIDEM a použije sa kľúč KLUC.
Šifrovanie. Začne sa na riadku K a v stĺpci P. V ich priesečníku je znak Z. To je prvý
znak zašifrovanej správy. Druhý znak dostaneme na riadku L a v stĺpci R. V ich
priesečníku je znak C. Ďalšie znaky sa šifrujú analogicky. Správa PRIDEM sa
zašifruje ako ZCCFOX. Znaky kľúča sú v prvom stĺpci tabuľky podčiarknuté. Znaky
šifry sú podčiarknuté vo vnútri tabuľky.
Dešifrovanie. Adresát zašifrovanej správy musí poznať kľúč, podľa ktorého bola
správa zašifrovaná. Kľúč sa odosiela inou cestou ako šifra alebo sa vopred dohodne
s odosielateľom. Inak by bolo po utajení. Podľa tohoto kľúča (v našom prípade
KLUC) sa správa dešifruje tak, že v riadku K sa vyhľadá znak Z. V hlavičke nad
znakom Z je znak P. Je to prvý znak pôvodnej správy. V riadku L sa vyhľadá znak C.
4
V hlavičke nad znakom C je znak R. Je to druhý znak pôvodnej správy. Ostatné
znaky sa dešifrujú analogicky.
Vigenerova šifra je substitučná šifra, pretože sa každý znak správy nahradí
iným znakom (ktorý leží v priesečníku riadka znaku kľúča a stĺpca znaku správy).
Kľúč má byť dostatočne dlhý. Ak je kratší ako správa, opakujú sa jeho znaky.
Používajú sa aj transpozičné šifry. Pri transpozičnom šifrovaní sa pôvodné znaky
nemenia, ale sa zmení ich poradie podľa vopred dohodnutého kľúča. Učinné je
používať kombináciu substitučnej a transpozičnej šifry, krátke správy a dlhé kľúče.
Správy sa šifrovali už v staroveku. Napríklad Caesarova šifra je zvláštny prípad
Vigenerovej šifry. Je to prípad, keď dĺžka kľúča je 1 (t. j. kľúč má iba jeden znak,
ktorý sa opakuje). Šifra sa ľahko rozlúšti, pretože znaky správy sa „posunú“ vždy
o rovnakú pseudovzdialenosť. Pri dostatočne dlhej správe sa posunutie určí analýzou
frekvencie výskytu znakov v bežnom texte. Pre každý jazyk je táto frekvencia iná
a preto je dôležité vedieť, v akom jazyku bola napísaná pôvodná správa.
Vigenerova šifra vznikla v 16. storočí. Až do začiatku 20. storočia sa pokladala
za neprekonateľnú. Existujú aj iné spôsoby šifrovania, ale tie nie sú až tak
elementárne ako Vigenerova šifra.
Realizácia Vigenerovej šifry v Exceli
Spôsob šifrovania uvedený v predošlej časti je pomalý a ťažkopádny. Zvykli
sme si na rýchle a ľahké metódy. Pri použití tabuľkového procesora Excel sa
šifrovanie podľa Vigenera zrýchli a zjednoduší. Na našej www stránke nájdete
jednoduchú aplikáciu tejto šifry v Exceli.
Arnold Dávid