Prírodou inšpirované algoritmy

História spojenia celulárnych automatov a kryptografie

Dynamické systémy sa študujú intenzívnejšie hlavne v posledných dvoch desaťročiach, pričom za dynamický systém sa všeobecne považuje množina stavov systému a pravidlo, ktoré mapuje každý z týchto stavov k ďalším, dopredne v čase.

Medzi výrazne študované dynamické systémy patria logistické mapy. Stavy systému sú reálne čísla x a pravidlo, podľa ktorého sa stav x(t) v čase t dostane do stavu x(t+1) je daný vzťahom x(t+1)=4.L.x(t).(1-x(t)) , kde L je reálne číslo z intervalu <0,1>. Logistická mapa ukazuje buď jednoduché alebo komplexné správanie závisiace na hodnote parametra L.

Koncom 90-tych rokov sa urobil prieskum, ktorý mal nájsť pokusy o aplikovanie dynamických systémov (celulárnych automatov) ako základu pre kryptografické systémy. Výsledkom tohto snaženia bolo nájdenie troch systémov (teórii), ktoré vynikali nad všetkými ostatnými.

• patentovaný systém (US patent 5,048,086) od M.Bianca a D.Reeda
• systém prezentovaný v materiály Proceedings of Crypto \'85 (str. 429-432) od S. Wolframa
• systém prezentovaný v materiály Cellular Automatom Pubblic-Key Cryptosystems od P. Guana

Ukázalo sa, že prvé dva sú si podobné a preto boli ďalej popisované spoločne, kdežto tretí sa v niekoľkých veciach a prístupoch líšil, a preto bol popisovaný samostatne.

Prvé dve zo spomínanych pokusov používajú na šifrovanie metódu doprednej iterácie dynamického systému pre vygenerovanie prúdu pseudo-náhodných čísel. Tento prúd sa následne kombinuje s otvoreným textom (plaintext - pôvodný text) využívajúc operáciu XOR pre vyprodukovanie zašifrovaného text (ciphertext). Príjmač generátora pseudo-náhodných čísel môže opätovne vygenerovať prúd, ktorý bol použitý na šifrovanie opätovnou doprednou iteráciou dynamického systému. Pseudo-náhodné čísla môžu byť potom opäť použité na funkciu XOR spolu so šifrovaným textom na obnovenie pôvodného textu (plaintext). To je napríklad rozdiel oproti systému CA-1.1 (je popísaný samostatne), ktorý využíva ako doprednú, tak aj spätnú iteráciu, ktorá môže byť použitá pre šifrovanie aj dešifrovanie.

Prvé dve schémy sa od seba odlišujú hlavne podľa toho, ktorý dynamický systém je použitý pre generovanie pseudo-náhodných čísel. V patente 5,048,086 je na generovanie týchto pseudo-náhodných čísel použitá logistická mapa. Klúč systému potom zlučuje zdroj pseudo-náhodného čísla a hodnotu parametra L. V článku, ktorý napísal Wolfram, je ako generátor pseudo-náhodných čísel použitý konkrétny celulárny automat známy ako pravidlo 30. Inicializačným stavom celulárneho automatu je kľúč. systémy oproti tretiemu trpia niektorými nedostatkami, z ktorých najvýraznejšie sú:

• nie je dobre zavedená kvalita generátora náhodných čísel. Aj keď Wolfram uskutočnil niekoľko rozsiahlych štatistických testov na kvalitu generovania pseudo-náhodných čísel pomocou pravidla 30 (rok 1986), neboli nájdené žiadne matematické dôkazy. Ešte horšia je situácia pre patent 5,048,086 - odkedy bolo známe, že vygenerovaná bitová sekvencia využívajúca logistickú mapu nebude náhodná pre niektoré výbery parametra v mape. To nebolo žiadúce pretože štruktúra vo vygenerovaných bitových reťazcoch by mohla byť využitá \"lámačmi kódov\" na odhalenie klúča a rozlúštenie správy.
• kvalita šifrovania môže byť premenlivá v závislosti od toho aký klúč bol vybratý. A preto aj vybratie dobrých klúčov by mohlo byť veľmi tažké.
• tieto systémy podobne ako aj iné, ktoré využívajú funkciu XOR s otvoreným textom (plaintext) a bitovým reťazcom sú zranitelné na niektoré druhy útokov.

Guanov kryptografický systém je mierne podobný kryptografickému systému CA-1.1, ktorý vyvinul Howard Gutowitz a je samostatne opísaný v kapitole jemu venovanej. Guanov systém (typ celulárneho automatu) je veľmi dobre premyslený, takže celulárny automat, ktorý je inverziou k pôvodnému sa dá nájsť avšak po veľmi náročných a zložitých výpočtoch systému polynomiálnych rovníc. Šifrovanie sa uskutoční aplikovaním celulárneho automatu avšak len jedným použitím. Podobne dešifrovanie využíva len jedno aplikovanie celulárneho automatu (teraz už inverzného) na zašifrovaný text. Bezpečnosť systému závisí na náročnosti výpočtu inverzného celulárneho automatu. Krátka charakteristika Guanovho kryptografického systému:

• pracuje s verejným kľúčom
• využíva doprednú iteráciu celulárneho automatu pre šifrovanie a doprednú iteráciu už iného celulárneho automatu pre fázu dešifrovania
• nevyužíva pridanie náhodnej informácie k otvorenému textu vo váze šifrovania na produkciu kvalitnejšieho výstupu v podobe zašifrovaného textu ako to napríklad už používa CA-1.1
• využíva nehomogénne celulárne automaty
• vyžaduje veľmi pozorný výber celulárneho automatu, ktorý bude použitý ako kľúče
• Guanova metóda celulárnych automatov v skutočnosti nevyužíva dynamické systémy. Počaš fázy šifrovania a dešifrovania sa kľúče celulárneho automatu použijú iba raz
• fáza dešifrovania si vyžaduje veľmi náročné riešenie systémy polynomiálnych rovníc
• a ďalšie

Táto časť mala ukázať systémy, ktoré sa snažili aplikovať princípy celulárnych automatov v kryptografii v období 90-tych rokov, teda v čase keď sa táto kombinácia začala pozornejšie skúmať a hľadali sa čo možno najlepšie spojenia charakteristických čŕt oboch disciplín. Ako bolo ukázané na ich stručných charakteristikách, tieto systémy mali niektoré nedostatky, ktoré už novšie systémy majú vyriešené rôznymi spôsobmi. To ako by mal vizerať už lepší kryptografický systém spolu s krátkou charakteristikou je uvedené v kapitole CA-1.1. Ide o systém, ktorý pochádza z roku 1995, no aj napriek tomu dátumu vzniku má mnoho predností oproti predchádzajúcim.