Gilbert Sandford Vernam
| Gilbert Sandford Vernam | |
|---|---|
| Narození | 3. dubna 1890 Brooklyn |
| Úmrtí | 7. února 1960 (ve věku 69 let) |
| Alma mater | Worcester Polytechnic Institute |
| Povolání | kryptograf, matematik a inženýr |
| Některá data mohou pocházet z datové položky. Chybí svobodný obrázek. | |
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
[editovat | editovat zdroj]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)
[editovat | editovat zdroj]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
[editovat | editovat zdroj]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
[editovat | editovat zdroj]Reference
[editovat | editovat zdroj]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
[editovat | editovat zdroj]- KLEIN, Melville. Securing Record Communications: The TSEC/KW-26. [s.l.]: [s.n.] Dostupné v archivu pořízeném dne 2012-03-15.
- 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.
- TUTTE, W. T. Fish and I. [s.l.]: [s.n.], 19 June 1998. Dostupné online. 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.
- VERNAM, Gilbert S. An Automatic Concentration Unit for Printing Telegraph Circuits. Electrical Communication. April 1932, s. 200.
- VERNAM, Gilbert S. Printing Telegraph Operation of Way Wires. AIEE Transactions. July 1938, s. 365. DOI 10.1109/t-aiee.1938.5057823.
- VERNAM, Gilbert S. Printing Telegraph Systems For Secret Wire and Radio Telegraphic Communications. Western Union Technical Review. April 1958, s. 37. Also in VERNAM, Gilbert S. Automatic Telegraph Switching System Plan 55-A. AIEE Transactions on Communication and Electronics. May 1958, s. 239.