Gilbert Sandford Vernam

Gilbert Sandford Vernam (3. dubna 18907. ú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ě.

Gilbert Sandford Vernam
Narození 3. dubna 1890
Brooklyn
Úmrtí 7. února 1960 (ve věku 69 let)
Alma mater Worcester Polytechnic Institute
Některá data mohou pocházet z datové položky.
Chybí svobodný obrázek.

Vernamův patentEditovat

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

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 19. 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“. Shannnon 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 šifraEditovat

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 AB
+ +
+ +
+ +

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

OdkazyEditovat

ReferenceEditovat

V tomto článku byl použit překlad textu z článku Gilbert Vernam na anglické Wikipedii.

  1. Klein, p. 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.”
  2. Shannon 1949
  3. Klein, p. 2

LiteraturaEditovat

  • KLEIN, Melville. Securing Record Communications: The TSEC/KW-26. [s.l.]: [s.n.] Dostupné v archivu pořízeném z originálu dne 2012-03-15. (anglicky) 
  • 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. (anglicky) 
  • TUTTE, W. T. Fish and I. [s.l.]: [s.n.], 19 June 1998. Dostupné online. (anglicky)  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. (anglicky) 
  • VERNAM, Gilbert S. An Automatic Concentration Unit for Printing Telegraph Circuits. Electrical Communication. April 1932, s. 200. (anglicky) 
  • VERNAM, Gilbert S. Printing Telegraph Operation of Way Wires. AIEE Transactions. July 1938, s. 365. DOI:10.1109/t-aiee.1938.5057823. (anglicky) 
  • VERNAM, Gilbert S. Printing Telegraph Systems For Secret Wire and Radio Telegraphic Communications. Western Union Technical Review. April 1958, s. 37. (anglicky)  Also in VERNAM, Gilbert S. Automatic Telegraph Switching System Plan 55-A. AIEE Transactions on Communication and Electronics. May 1958, s. 239. (anglicky)