Keď Vernam nebol prvým

Detail z Predslovu (s.4), Telegrafický kód určený k zabezpečeniu súkromia a utajenia pri prenose telegramov,
(angl. Telegraphic Code to insure privacy and secrecy in the transmission of telegrams, 1882) 

Prepíše objav v starej telegrafnej kódovej knihe históriu kryptografie? Až do nedávnej doby bol všeobecne prijímaným vynálezcom jednorázového heslového bloku, (angl. one-time pad) prvého teoreticky aj prakticky nerozlúštiteľného šifrovacieho systému, telegrafný inžinier Gilbert Vernam. Jeho mechanicko-elektrický systém dôverného prenášania správ na diaľku bol neskôr vylepšený Josephom Mauborgneom a ručné verzie systémov sa neskôr všeobecne používali pre šifrovanie diplomatickej a vojenskej korešpondencie.

Kódové knihy, ako táto pochádzajúca z r.1896
radikálne znižovali cenu telegramov, ktorej
výška závisela od počtu slov.

Prednedávnom obletela svet správa, že Steve Bellovin, profesor počítačovej vedy na Kolumbijskej univerzite, objavil telegrafnú kódovú knihu z r. 1882 náhodne v Kongresovej knižnici vo Washingtone. Táto kódová kniha bola zostavená istým Frankom Millerom a popisuje v nej systém prešifrovania telegrafických kódov pomocou náhodne volených "posuvných čisiel", ktoré by sa nemali opakovať. A preto je zaujímavá otázka, či Bellovin objavil dôkaz, že jednorázový šifrovací systém bol objavený už pred 35 rokmi a mala by sa preto história kryptografie ohľadom jednorázovej šifry prepísať nanovo?
Poďme si však najprv v stručnosti vysvetliť na čo sa v skutočnosti prišlo. Telegrafné kódové knihy boli v 19. storočí veľmi populárne hlavne kvôli tomu, že pri ich používaní sa znižovali poplatky za telegramy. Bežne používané slová a vety v telegrafnom styku sa značne skrátili pri prevode na kódové slová a na kombinácie písmen alebo číslic. Kódové knihy, ktoré si používatelia v telegrafnom styku mohli bežne zakúpiť, neposkytovali takmer žiadnu kryptografickú bezpečnosť. Preto boli niekedy tieto kódy prešifrované (ako dodatočná šifrovacia vrstva nad kódom) s krátkym heslom čím relatívne vzrástla dôvernosť komunikácie. Millerova kódová kniha obsahuje 14000 slov alebo fráz (niektoré sú bez významu, slúžiace len ako tzv."výplň") spolu so zodpovedajúcimi kódovým slovami a sériovým číslom. Doposiaľ to teda nie je nič nové.

V tejto kódovej knihe sa však taktiež popisujú inštrukcie pre prešifrovanie. Tieto inštrukcie sú vlastne tým, čo jeho prácu robí mimoriadnou. V predslove tejto kódovej knihy Miller píše: "odosielateľ a príjemca musia "čísla posuvu" zakaždým čo najskôr po použití zahodiť". A daľej píše, že "ak odosielatelia zistia, že výsledok pričítania hesla (k sériovému číslu) je vyšší ako najväčšie možné sériové čislo (14000) v tejto knihe, musí od daného výsledku odčítať dané posledné sériové číslo (14000)". Ak príjemca zistí, že zašifrované slovo "je menšie než kľúč, ktorým sa dá odšifrovať, musí dočasne pričítať k danému sériovému číslu v tejto knihe (14000) a od tejto sumy odčítať kľúč".
A teraz si to skúsme zrekapitulovať: na výpočet šifrového textu odosielateľ pričítáva kľúč (čísla posuvu) ku kódovým číslam otvoreného textu (sériovým číslam). Keď je výsledok väčší ako 14000 potom odčíta od neho číslo 14000. Pri dešifrovaní príjemca od šifrového textu kľúč odčítava. Samozrejme ak je číslo šifrového textu menšie než kľúč, najprv k nemu pripočíta číslo 140000 a následne odčíta kľúč. Toto je v podstate tzv. aditívny šifrovací systém podľa modulu 14000.
V ďalšom Miller popisuje čísla posuvu ako "zoznam nepravidelne sa vyskytujúcich čísel" a "diferencia medzi takýmito číslami sa nesmie vyskytovať pravidelne". Taktiež tu vysvetľuje, že keď sa číslo posuvu použije, malo by sa vyškrtnúť zo zoznamu a už znova nepoužiť. Potom sa popisujú rôzne príklady použitia, v ktorých sa slová nahradzujú ich ekvivalentmi v podobe sériových čísel (otvoreného textu) a pričítava sa k nim číslo posuvu (kľúč). A toto je v podstate gro šifrovania jednorázovým kľúčom. Text sa prevedie na čísla, s ktorými sa sčíta v rámci modulárnej aritmetiky náhodný kľúč a tento kľúč sa nesmie použiť znovu. Naviac Miller vysvetľuje že každý korešpondent by si mal spísať čiernym atramentom do knihy svoj vlastný zoznam "čísel posuvu" a na opačnú stranu červeným atramentom zoznam "čísel posuvu" pre príjemcu. Jasne rozlišuje čierne (šifrant) a červené (dešifrant) "čísla posuvu". A práve týmto sa vyhýba simultánnemu použitiu rovnakých posuvných čísiel čo sa môže veľmi ľahko stať, ak obaja korešpondenti používajú jedne jediný zoznam posuvných číslic.

Nanešťastie Miller len veľmi krátko popisuje, že každé číslo posuvu by malo mať hodnotu v rozsahu od 0 do 14000. Nevenuje sa ani problému generovania náhodných čísel. Toto môže vo veľkej miere ovplyvniť bezpečnosť šifry, pretože používateľ môže byť z pohodlnosti zvádzaný k tomu, vyberať si menšie hodnoty posuvu nevyžadujúce ťažkopádne výpočty modulo 14000. Praktická zložitosť pri počítaní modulo 14000 mohla byť práve tým dôvodom, prečo jeho systém neupútal pozornosť a nezažil úspech, ktorý by si bol právom zaslúžil. Ak by sa jednotlivé číslice v sériových číslach brali ako nezávislé a na tieto by sa bolo použilo sčítanie podľa modulu 10 (tj. sčítanie bez prenosu, odčítanie bez výpožičky) bolo by to všetko oveľa ľahšie a rýchlejšie. Môžeme však len špekulovať o dôvode, prečo jednorázové šifrovanie Franka Millera sa nikdy nestalo verejne známe. Steve Bellovin špekuluje o tom, či sa Millerova práca mohla nejakým spôsobom nepriamo cez Parkera Hitta a Josepha Mauborgnea dostať k Gilbertovi Vernamovi. Samozrejme Vernam ako elektrotechnický inžinier pristupoval k jednorázovému šifrovaniu z úplne iného uhla pohľadu a objavil úplne odlišné riešenie pozostávajúce z telegrafu založenom na 5-bitových kódoch vydierovaných na papierových diernych páskach a sčítanie sa vykonávalo v rámci každého bitu podľa modulu 2. Neodškriepiteľnou skutočnosťou je, že Millerov objav upadol do zabudnutia.
Je neoddiskutovateľné, že Frank Miller bol prvým, kto objavil šifrovanie pomocou jednorázového heslového bloku, hoci menej praktického než akým je jeho použitie v súčasnosti. O 35 rokov neskôr Gilbert Vernam objavil úplne odlišný elektromechanický šifrovací systém, ktorý mimochodom má rovnaké matematické vlastnosti ako Millerova ručná šifra. A napokon boli to nemeckí kryptológovia Werner Kunze, Rudolf Schauffler a Erich Langlotz, ktorí vyvinuli jednorázový šifrovací systém ktorý sa používal pomocou ceruzky a papiera v konečnom dôsledku znovu objavili šifrovaciu schému Franka Millera. Takže záverom by sme mohli konštatovať, že Miller ako aj Vernam navzájom nezávisle objavili princíp jednorázovej šifry a obaja si za rovnaký počin, hoci v úplne inej forme zaslúžia ocenenie. Ale napokon musíme priznať prvenstvo tohto objavu Frankovi Millerovi. I keď treba nadôvažok s trpkosťou podotknúť, že podľa dostupných historických údajov tento jeho mimoriadny výkon nemal vplyv na následné dejiny kryptografie. Napriek tomu sa týmto prepisujú historické anály. A konečne netreba zabudnúť na to, že Stevovi Bellovinovi patrí vďaka za odhalenie tohto skoro zabudnutého príbehu objaviteľa jednorázovej šifry.
Viac informácii o Millerovej telegrafnej kódovej knihe z r. 1882 môžete získať v článku Steva Bellovina o Frankovi Millerovi (predbežná verzia vo formáte .pdf), ktorý napokon vyšiel aj v tohtoročnom júlovom čísle časopisu Cryptologia. O kódových knihách, používaných v druhej polovici 19. a začiatkom 20. storočia sa môžete dozvedieť čo to zaujímavé, prípadne si ich aj stiahnuť vo formáte .pdf na stránke Nicka Gesslera.