Gilbert Sandford Vernam (3. dubna 1890 – 7. února 1960) byl absolvent Worcester Polytechnic Institute (1914) a technik v Bellových laboratořích, který v roce 1917 vytvořil aditivní polyalfabetickou proudovou šifru a také se podílel na vývoji jednorázové tabulkové šifry. Vernam pracoval pro společnosti Postal Telegraph Company nebo Western Union a jeho pozdější práce se týkala především automatických přepínacích systémů pro telegrafické sítě.
Vernamův patent
Kombinační funkce Vernam, vydaná 22. července 1919, je logická operace XOR, aplikovaná na jednotlivé bity k zašifrování znaků v kódu Baudot. Vernam ve svém patentu nepoužil termín „XOR“, ale implentoval tuto operaci v relé logice. Ve Vernamově příkladu je prostý text „A“, zašifrovaný v kódu Baudot jako „++---“, a klíčový znak „B“, šifrovaný jako „+--++“. Výsledný šifrovaný text je potom „-+-++“, který se dešifruje jako znak „G“. Kombinací „G“ a klíčového znaku „B“ opět vznikne „++---“, tedy původní prostý text „A“. NSA nazvala tento patent jedním z nejdůležitějších v historii kryptografie.[1]
One-time pad (Jednorázová tabulková šifra)
Krátce poté Joseph Mauborgne, v té době kapitán US Army Signal Corps, navrhl, aby klíče na děrných páscích navíc obsahovaly náhodnou informaci. Spojením této a Vernamovy myšlenky vznikla implementace automatické formy one-time pad (ani jeden z tvůrců v té době toto označení nepoužíval). Šifra byla patentována v polovině 20. let 20. století.
Claude Shannon, také inženýr v Bellových laboratořích, dokázal ve svém výzkumu během druhé světové války, že jednorázová tabulková šifra je neprolomitelná, pokud je správně implementována. Výzkum byl později publikován v říjnu 1949 pod názvem „Communication Theory of Secrecy Systems“. Shannon také dokázal, že každý neprolomitelný systém musí mít stejné vlastnosti jako jednorázová tabulková šifra: klíč musí být náhodný, stejně dlouhý jako původní prostý text, vždy jedinečný v celém textu i jednotlivých částech a udržovaný v tajnosti.[2]
Vernamova šifra
Vernamova šifra je symetrická proudová šifra, ve které je šifrovaný text vytvořený kombinací prostého textu s náhodným nebo pseudonáhodným proudem dat stejné délky (tzv. „keystream“). Využívá logickou funkci XOR, symbolizovanou znakem ⊕[3] a je reprezentována následující tabulkou pravdivostních hodnot, kde znak + je „pravda“ a znak − je „nepravda“.
| VSTUP |
VÝSTUP
|
| A |
B |
A ⊕ B
|
| − |
− |
−
|
| − |
+ |
+
|
| + |
− |
+
|
| + |
+ |
−
|
Další názvy této funkce jsou: „Not equal (NEQ)“, součet modulo 2 (bez „přenosu“) a rozdíl modulo 2 (bez „výpůjčky“). Šifra je reciproční (symetrická), protože k zašifrování prostého textu i k jeho následnému dešifrování je použit identický „keystream“:
- prostý text ⊕ klíč = šifrovaný text
- šifrovaný text ⊕ klíč = prostý text
Pokud je „keystream“ skutečně náhodný a použitý pouze jednou, vznikne jednorázová tabulková šifra. Náhrada pseudonáhodnými daty generovanými kryptograficky bezpečným generátorem je běžná a efektivní konstrukce pro proudovou šifru. RC4 je příklad Vernamovy šifry, která je na internetu široce využívána. V případě, že je stejný „keystream“ použit pro dvě zprávy, může být jeho efekt eliminován aplikací funkce XOR na dané dva prosté texty.
- šifrovaný text 1 ⊕ šifrovaný text 2 = prostý text 1 ⊕ prostý text 2
Odkazy
Reference
V tomto článku byl použit překlad textu z článku Gilbert Vernam na anglické Wikipedii.
- ↑ Klein, s. 3 “Vernam had invented the unbreakable cipher: “one-time tape” (OTT) for on-line TTY encryption. In 1919 he was granted a patent, perhaps one of the most important in the history of cryptography.”
- ↑ Shannon 1949
- ↑ Klein, s. 2
Literatura
- KLEIN, Melville. Securing Record Communications: The TSEC/KW-26. [s.l.]: [s.n.] Dostupné v archivu pořízeném dne 2012-03-15. Je zde použita šablona
{{Citation}} označená jako k „pouze dočasnému použití“.
- SHANNON, C.E. Communication Theory of Secrecy Systems. Bell System Technical Journal. October 1949, s. 656–715. DOI 10.1002/j.1538-7305.1949.tb00928.x. Je zde použita šablona
{{Citation}} označená jako k „pouze dočasnému použití“.
- TUTTE, W. T. Fish and I. [s.l.]: [s.n.], 19 June 1998. Dostupné online. Je zde použita šablona
{{Citation}} označená jako k „pouze dočasnému použití“. Transcript of a lecture given by Prof. Tutte at the University of Waterloo
- VERNAM, Gilbert S. Cipher Printing Telegraph Systems For Secret Wire and Radio Telegraphic Communications. Journal of the IEEE. 1926, s. 109–115. Je zde použita šablona
{{Citation}} označená jako k „pouze dočasnému použití“.
- VERNAM, Gilbert S. An Automatic Concentration Unit for Printing Telegraph Circuits. Electrical Communication. April 1932, s. 200. Je zde použita šablona
{{Citation}} označená jako k „pouze dočasnému použití“.
- VERNAM, Gilbert S. Printing Telegraph Operation of Way Wires. AIEE Transactions. July 1938, s. 365. DOI 10.1109/t-aiee.1938.5057823. Je zde použita šablona
{{Citation}} označená jako k „pouze dočasnému použití“.
- VERNAM, Gilbert S. Printing Telegraph Systems For Secret Wire and Radio Telegraphic Communications. Western Union Technical Review. April 1958, s. 37. Je zde použita šablona
{{Citation}} označená jako k „pouze dočasnému použití“. Also in VERNAM, Gilbert S. Automatic Telegraph Switching System Plan 55-A. AIEE Transactions on Communication and Electronics. May 1958, s. 239. Je zde použita šablona {{Citation}} označená jako k „pouze dočasnému použití“.
