Možnosti použití neuronových sítí pro šifrování

20.09.2000 | Odborné konference

Možnosti použití neuronových sítí pro šifrování

Application of neural networks in cryptography

Autor: ArnoštVeselý

Abstrakt v češtině:

V příspěvku je diskutována možnost použití neuronových sítí v kryptografii. Je navržen způsob jednoduchého použití vrstvené neuronové sítě pro šifrování symetrickým klíčem a pro podpis privátním klíčem. Na tomto jednoduchém případě jsou demonstrovány výhody a nevýhody neuronového přístupu.

Abstrakt v angličtině:

In this article the posibility of utilization of neural networks in cryptography is discussed. A method of application of layered neural network for symetric key cryptography and for private key signature is described. On this simple example advantedges and disadvantages of neural network approach are demonstrated.

Klíčová slova:

vrstvenáneuronová síť, algoritmus zpětného šíření chyby, šifrování, kryptografie se symetrickým klíčem, kryptografie s veřejným a privátním klíčem.

Keywords:

layered neural network, back propagatin of error algorithm, enciphering, symetric key cryptography, cryptografy with public and private key.

Úvod:

V posledních letech je při používání počítačů kladen stále větší důraz na bezpečnost. Souvisí to s rozvojem rozsáhlých a veřejně přístupných počítačových sítí, s používáním počítačů pro uchovávání a přenos velkého množství citlivých informací, s používáním počítačů při bankovních operacích a v poslední době i s jejich použitím v rychle se rozvíjejím elektronickém obchodu. Důležitou součástí problematiky bezpečnosti je kryptografické zabezpečení dat. V kryptografii existují dva základní přístupy k zabezpečení dat: přístup používající symetrický klíč a přístup, který používá nesymetrický klíč. Nesymetrický klíč tvoří dvojice klíčů, z nichž jeden se nazývá soukromý (privátní) klíč (private key) a druhý se nazývá veřejný klíč (public key).

V kryptografii se symetrickým i nesymetrickým klíčem se používá celá řada algoritmů umožňujících šifrování, autentizaci a zabezpečení integrity dat. Autorovi tohoto příspěvku není zatím znám žádný algoritmus spočívající ve využití neuronové sítě. Cílem tohoto příspěvku je ukázat, jak lze neuronové algoritmy v kryptografii použít.

Cíle a metody:

Při hledání neuronového kryptografického algoritmu vyjdeme z dobře známé a používané aplikace neuronových sítí pro kompresi dat. Princip použití neuronové sítě pro kompresi dat je jednoduchý. Použije se vrstvená síť s jednou skrytou vrstvou. Počet neuronů vstupní a výstupní vrstvy musí být stejný, řekněme n. Počet neuronů skryté vrstvy se volí m, kde mn . Obvykle se volí m = n/4. Označíme-li vektor hodnot na výstupech receptorů sítě x, výstupech neuronů skryté vrstvy z a výstupech neuronů výstupní vrstvy y, lze psát

z = f(x)

y = g(z) = g (f(x)) ,

kde funkce f(x) a g(z) závisí na váhových vektorech neuronů skryté a výstupní vrstvy (viz obr. 1).

Síť se adaptuje na učebních vzorech x tak, aby její výstup y byl přibližně roven jejímu vstupu x. Adaptace se obvykle provádí metodou zpětného šíření chyby. Po adaptaci platí:

x y = g(z)

a původní vektor x tedy lze přibližně rekonstruovat z vektoru z , který má menší dimezi než původní vektor x. Jinak řečeno, data reprezentovaná vektorem x, byla pomocí neuronové sítě komprimována do vektoru z , ze kterého je lze opět pomocí sítě přibližně rekonstruovat.

Komprese se obvykle používá při přenosu dat, aby se snížily nároky na kvalitu přenosového kanálu. Pokud obě strany, které se účastní přenosu, mají k dispozici konfiguraci výše uvedeným způsobem naučené sítě (tj. znají její architekturu a váhy), může přenos mezi nimi probíhat podle obr. 2.

Na první pohled by se mohlo zdát, že podobný postup jako při kompresi dat, lze použít i pro šifrování. Klíčem by byla konfigurace neuronové sítě. Počet neuronů skryté vrstvy by se rozšířil tak, aby neuronovou síť bylo možné naučit na výstupu věrně reprodukovat vstupní vektory. Šifrovaný text by byly zakódované stavy neuronů skryté vrstvy a dešifrovat by ho mohl pouze ten, kdo by znal konfiguraci neuronové sítě, respektive část této konfigurace. Pokud by obě strany znaly celou konfiguraci neuronové sítě, šifrování pomocí neuronové sítě by představovalo šifrování symetrickým klíčem.

Bohužel tímto přímočarým způsobem nelze neuronovou síť pro šifrování použít. Aby se neuronová síť naučila na výstupu věrně reprodukovat vstupní vektory, musí jí být ve fázi učení předloženy všechny možné vstupní vektory a to obvykle vícekrát. Proto vstupní šifrované bloky by nemohly být příliš veliké. Dá se předpokládat, že by bylo možné naučit neuronovou síť věrně reprodukovat bloky o velikosti 16 až 20 bitů. Při takto malých blocích by ale bylo snadné šifru prolomit hrubou silou. Velikost bloků 64 bitů a více, která je pro bezpečné šifrování třeba, by nebylo možné z výše uvedených důvodů použít.

Plyne z toho, že neuronové sítě pro šifrování nelze vůbec použít? Autor se domnívá, že nikoliv a pro podporu tohoto tvrzení podává vlastní návrh jednoho možného řešení. Dá se předpokládat, že výzkum v této oblasti povede k rafinovanějším a efektivnějším řešením. Cílem tohoto příspěvku je pouze ukázat, že řešení jsou principielně možná a že lze taková řešení v budoucnu očekávat.

Výsledky:

Následující navrhované řešení lze použít k šifrování symetrickým klíčem a k podpisu privátním klíčem. Pro jednoduchost výkladu budeme v dalším hovořit pouze o šifrování. Jak tuto metodu použít pro podpis privátním klíčem je zřejmé.

Pro tyto účely se použije neuronová síť N se třemi skrytými vrstvami. Vstupní vektor označíme x, výstupní vektor z a vektor popisující stav neuronů prostřední skryté vrstvy y. Na neuronovou síť N lze také pohlížet jako na dvě neuronové sítě N1 a N2 s jednou skrytou vrstvou, které jsou zapojeny za sebou. To jest výstup z neuronové sítě N1 je zároveň vstupem neuronové sítě N2 (viz obr. 3). Abychom se přiblížili terminologii standardně používané v kryptografii, označíme výstupy neuronových sítí N1 a N2 takto:

y = K( N1, x)

z = K( N2, y)

Neuronová síť N1 má jednu skrytou vrstvu a je proto schopna realizovat libovolné zobrazení z prostoru hodnot vektorů x do prostoru hodnot vektorů y. Funkce y = K( N1, x) tedy může být libovolná. Totéž platí pro neuronovou síť N2.

Aby nebylo možné šifru snadno prolomit, použijeme dostatečnou velikost bloku, řekněme 64 bitů. Neuronové sítě N1 a N2 naučíme realizovat netriviální funkci. Provedeme to tak, že je budeme po určitou dobu učit algoritmem back propagation of error realizovat náhodně zvolené dvojice hodnot (x, y), respektive (y, z). Počáteční konfigurace sítí N1 a N2 zvolíme náhodně.

Natrénovanou neuronovou síť N = {N1, N2} lze použít pro šifrování symetrickým klíčem následujícím způsobem (viz také obr. 4) :

Zpráva, která se bude šifrovat, bude rozdělena do bloků x, které budou postupně přiváděny na vstup neuronové sítě N = {N1, N2}. Vektor x , bude zakódován podsítí N1 do vektoru y = K( N1, x) a celou sítí N do vektoru z = K(N2 , K( N1, x)). Pokud vektory x a z mají stejnou dimenzi, lze na nich po bitech provést operaci XOR ( ) a jako výsledek dostaneme vektor

w = xK(N2 , K( N1, x))

Zašifrovaným blokem x bude dvojice hodnot (w, y) a ta se bude přenášet k příjemci.

Příjemce provede dešifrování zprávy následujícím způsobem:

1. Pomocí podsítě N2 a druhé části šifry y spočte hodnotu

z = K( N2, y)

2. Potom pomocí první části šifry a hodnoty z spočte hodnotu

wz = xK(N2 , K( N1, x)) K( N2, y) =

xK(N2 , y) K(N2 , y) = x

( Platnost poslední rovnosti je založena na tautologii ab b = a .)

Při bližším pohledu na princip výše navrženého kódování vidíme, že neuronová síť zde byla použita pro reprezentaci booleovské funkce. Neuronová síť s jednou skrytou vrstvou je schopna realizovat libovolnou booleovskou funkci. Učení sítě na dvojicích náhodných vektorů vede k tomu, že booleovská funkce je náhodně vybrána z prostoru všech booleovských funkcí, kterých je . Při dostatečně velkém bloku, tj. při dostatečně velkém n je proto šifra těžko prolomitelná. Nevýhodou uvedeného algoritmu šifrování ale je, že zašifrovaný blok má dvojnásobný počet bitů ve srovnání s nezašifrovaným blokem. Velikost šifry by bylo možné zmenšit tak, že bychom zmenšili počet neuronů ve vrstvě y. Vrstva y by pak měla méně neuronů než vstupní a výstupní vrstvy x a z. O kolik by bylo možné snížit počet neuronů vrstvy y , aniž by to ohrozilo bezpečnost šifry, by bylo nutné zkoumat. Zároveň by bylo vhodné pokusit se najít jinou metodu šifrování neuronovou sítí, u které by šifra měla stejnou velikost jako původní text.

Diskuse:

Jaké jsou výhody a nevýhody neuronového šifrování se symetrickým klíčem ve srovnání s klasickým metodami šifrování pomocí symetrického klíče, které jsou obvykle modifikací algoritmu DES?

Nevýhodou neuronového šifrování je především větší délka šifry, než je délka původního textu. Tato nevýhoda ale bude ale možná v blízké době odstraněna. Další nevýhodou je podstatně větší velikost klíče. V roli klíče při neuronovém šifrování vystupuje celá konfigurace neuronové sítě, což fakticky znamená, že klíč bude mít řádově velikost jednotek až desítek kB. U algoritmů typu DES naproti tomu stačí jednotky až desítky bytů. Nutno tedy počítat s tím, že velikost klíče bude asi tisíckrát větší. To ale nemusí být považováno za podstatné, protože klíč se přenáší jen občas.

Vzniká otázka zda neuronové šifrování může přinést také nějaké výhody. Největší výhoda spočívá v paralelismu výpočtu neuronové sítě. Pokud neuronová síť bude simulována softwarovým programem a neuronový výpočet bude provádět procesor, výpočet bude sekvenční a tato výhoda se neprojeví. Neuronovou síť ale lze snadno realizovat hardwarově a šifrování a dešifrování by potom mohl provádět sám síťový adaptér bez účasti procesoru. V tomto případě by šifrování mohlo být přeneseno až na nejnižšší vrstvu komunikačního modelu, to jest do linkové vrstvy a šifrovaly a dešifrovaly by se odesílané nebo přijímané pakety.

Výše uvedenou metodu lze také použít pro podpis privátním klíčem. Privátní klíč zde tvoří konfigurace celé sítě N = {N1, N2} a veřejný klíč konfigurace podsítě N1. Kryptografie s veřejným klíčem je nezbytná pro celou řadu prudce se vyvíjejících komerčních aplikací. Kromě toho je v poslední době ohrožena právě bezpečnost kryptografie s veřejným klíčem. Ve výzkumných laboratořích se intenzivně pracuje na kvantovém počítači a odborníci předpovídají, že bude do deseti let realizován. Pro kvantový počítač vyvinul Shor na MIT algoritmus pro faktorizaci celých čísel, který je schopen faktorizovat velká celá čísla v relativně krátkém čase. Přitom právě na nemožnosti faktorizovat velká čísla spočívá bezpečnost současné kryptografie s veřejným klíčem. Navíc Shorův algoritmus lze realizovat na fyzikálním zařízení, které místo kvantového výpočtu provádí výpočet na základě interference elektromagnetického záření. Takové zařízení již bylo předvedeno na posledním kryptografickém kongresu v Praze. Bezpečnost kryptografie s veřejným klíčem může být proto v budoucnosti vážně ohrožena.

Protože sestrojení kvantového počítače je na obzoru, ve světě se velmi intenzivně hledají paralelní algoritmy realizovatelné na kvantovém počítači, které by řešily výpočetně složité úlohy. Zajímavé je, že přes všechno úsilí jsou známy pouze dva takové algoritmy, z nichž jeden je právě zmíněný Schorův algoritmus pro faktorizaci velkých čísel. V této situaci by nalezení neuronové realizace veřejného klíče jistě bylo významným krokem k bezpečnějšímu používání počítačů.