KAOTIČNI KRIPTOGRAFSKI SISTEM Z UPORABO VEZIJ FPGA Bojan Jarc, Matej Šalamon Univerza v Mariboru, Fakulteta za elektrotehniko računalništvo in informatiko, Maribor, Slovenija Kjučne besede; kriptografski sistemi, kaos, digitalni filtri, vezja FPGA. Izvleček: \/ naslednjem prispevku predstavljamo kaotični kriptografski sistem In možnost njegove strojne izvedbe. Jedro kriptografskega sistema predstavljata multipomična šifrirna oz. dešifrirna funkcija (enačbe 2, 3, 4) in generator psevdo-kaotične sekvence (slika 3), realiziran z digitalnim sitom drugega reda. Razmeroma enostavna struktura in izvajanje preprostih matematičnih operacij (seštevanje, odštevanje, množenje s skalarjem) dopuščajo strojno realizacijo sistema, ki omogoča hitro delovanje. Kriptografski sistem sestavlja šifrirno in dešlfrirno vezje (slika 5). Pri njegovi realizaciji smo uporabili 16 bitno aritmetiko s stalno vejico In vezje FPGA XC3S500E družine Spartan-3E. Enota odprtega sporočila je bila 16 bitna. Pri načrtovanju smo uporabili kombinirani grafični opis In opis z visokonivojskim jezikom VHDL (slika 6). Maksimalna frekvenca ure, pri kateri je bila inverznost med operacijo šifriranja In dešifriranja še zagotovljena, je znašala 25 MHz (sliki 8 a, b). Pri 7-kratnl (N= 7) ponovitvi šifrirne funkcije je bila maksimalna frekvenca šifriranja 3,125 MHz. Ocenili smo tudi hitrost delovanja sistema pri uporabi drugih vezij FPGA (tabela 1). Ugotovili smo, da bi lahko z vezji družine Virtex 4 dosegli hitrost šifriranja 77,71 MHz pri N-1. Chaotic Cryptographic System Using FPGA Circuits Key v/ords: cryptographic systems, chaos, digital filters, FPGA circuits. Abstract: In this paper we present a chaotic cryptographic system and its hardware realization. The core of chaotic cryptographic system Is a multi-shift cipher (eq. 2, 3) or decipher (eq. 4) and pseudo-chaotic sequence generator (fig. 3), realized with second order digital filter. Relatively simple structure and executions of simple mathematical functions (addition, subtraction, scalar multipllcatlon) allows us to use a hardware realization, suitable for high frequencies. A chaotic cryptographic system Is composed of cipher and decipher circuit (fig. 5). For its realization we have used 16 bit fixed point arithmetic and FPGA XC3S500E circuit of Spartan 3E family. Plaintext digits was 16 bit long. At designing stage we have used combined schematic and language VHDL description approach (fig. 6). Maximum clock frequency at which cipher and decipher were Inversive was 25 MHz (fig. 8 a, b). Choosing the multi-shift function repetition number N = 7, allows us to encrypt the plaintext with frequency 3,125 MHz Performance was estimated for other FPGA circuits (table 1). For Virtex 4 FPGAs we've achieved maximal clock frequency 77,71 MHz atN-^ 1.. 1. Uvod Nekoč zgolj zanimiv fenomen determinističnega kaosa, je postal v zadnjem desetletju tudi praktično uporaben. Na področju digitalnih komunikacijskih sistemov je apliciran v različnih kompresijskih, šifrirnih in modulacijskih gradnikih, potrebnih pri prenosu informacij. Znani so npr. različni načini pretvorbe informacijskega signala v kaotičnega na oddajni strani in izločitev informacijskega signala iz kaotičnega na sprejemni strani. Med najpomembnejše sodijo: kaotično maskiranje, kaotično preklapljanje in kaotična modulacija. Med leti 1990 in 1995 je bil cilj številnih raziskav, razviti sistem, ki bo omogočal modulacijo in šifriranje s pomočjo enega samega kaotičnega sistema. Ob tem sta se formirali dve različni raziskovalni področji: področje kaotične mod-ulacije in kaotična kriptografija /1/. Kriptografija je matematična disciplina, ki s ukvarja z varnostjo informacij, šifriranjem, avtentičnostjo in avtorizaci-jo. Z njo so običajno povezani: simetrični blokovni šifrirni sistemi, generatorji naključnih števil, tokovni šifrirni sistemi in asimetrični šifrirni sistemi oziroma šifrirni sistemi z javnim ključem /4/. Apliciranje kaosa v kriptografiji oziroma pojav ti. kaotičnih kriptografskih sistemov se je pojavilo z odkritjem možnosti sinhronizacije kaotičnih oscilacij identičnih kaotičnih sistemov/3/. Sinhronizacija dveh identičnih kaotičnih sistemov je uspešna, če je mogoče, kljub njuni hiperobčutljivosti na začetne pogoje, zagotoviti njuno identično kaotično oscili-ranje. Sinhroniziranost kaotičnih sistemov na šifrirni in deši-frirni strani je namreč potreben pogoj za reverzibilnost oddajne in sprejemne strani kaotičnega kriptografskega sistema. Kaotični sistemi se v kriptografiji uporabljajo kot generatorji naključnih števil za generiranje kriptografskih ključev in za naključno inicializacijo posameznih spremenljivk v kriptografskih algoritmih. Z odkritjem obstoja kaosa v digitalnih sistemih se v kriptografiji pojavlja vse več psevdo-ka-otičnih sistemov. Ti sistemi imajo končno število različnih stanj, zato lahko generirajo le navidezno naključne oziroma psevdo-kaotične sekvence števil, ki so sicer periodične, periode ponavljanja pa so običajno zelo velike. V prispevku predstavljamo kaotični kriptografski sistem, v katerem smo za generiranje naključnih sekvenc uporabili kaotično digitalno sito II. reda, za šifrirno in dešifrirno funkcijo pa posebno multipomično funkcijo. Opis digitalnega sita kot generatorja psevdo-naključnih sekvenc je opisan v drugem poglavju. Tretje poglavje je namenjeno opisu predlaganega šifrirnega in dešifrirnega algoritma, ki omogoča ti. tokovno šifriranje in dešifriranje. Implementacija celotnega kriptografskega sistema v vezju FPGA je opisana v četrtem poglavju, peto poglavje pa opisuje rezultate meritev. 2. Generator psevdo-kaotične sekvence Generator naključnih sekvenc je zraven šifrirne in dešifrirne funkcije najpomembnejši del vsakega kriptografskega sistema. Resnično naključne sekvence je mogoče dobiti le s pomočjo naključnih fizikalnih procesov kot je npr. metanje kovanca, termični šum na uporu ali Zener diodi itd. Med nje se pogosto uvrščajo tudi kaotični procesi, z značilno deterministično naključnostjo. Kernaključni procesi niso ponovljivi, z njimi ni mogoče zagotoviti potrebne reverzibilnosti šifrirnega in dešifrirnega algoritma, saj sta za njo potrebna dva popolnoma enaka vira naključnih sekvenc. Večina današnjih kriptografskih sistemov uporablja generatorje psevdo-naključnih sekvenc. Ti lahko zaradi končnega števila različnih stanj, generirajo le navidez naključna oziroma psevdo-naključna zaporedja števil. Takšna zaporedja so sicer periodična, njihova perioda pa zelo velika^ in običajno vnaprej izračunljiva. Psevdo-naključne sekvence z majhno periodo za šifrirne namene niso primerne, saj omogočajo hitro razkritje tajnega ključa. Zelo znan je preprost način generiranja psevdo-naključnih sekvenc s pomičnimi registri in povratno zanko LFSR^ /4/. Med psevdo-naključne sekvence se velikokrat uvrščajo tudi psevdo-kaotične sekvence /5/, čeprav je med njimi kar nekaj razlik /6/. V generatorju psevdokaotičnega signala poteka hiperobčutljiv iterativni proces, na osnovi katerega se generira psevdokaotična sekvenca števil, ki je paradok- Vhod=0 o-► f(*)-seštevanje v aritmetiki z dvojiškim komplementom Slika 1: Nelinearni model digitalnega sita drugega reda. Fig. 1: Second order digital filter nonlinear model. salno urejeno neurejena. Kaotično naključni proces je namreč v primerjavi s povsem naključnim procesom bolj urejen oziroma manj naključen. Urejeno neurejenost potrjujejo urejene fraktalne podobe, ki pri resnično naključnih procesih ne obstajajo. Eden izmed sistemov, ki se lahko obnaša kaotično, je tudi digitalno sito II. reda. Čeprav je njegovo obnašanje natančno obravnavano v prispevkih /7/, na tem mestu omenimo le nekatere pomembnejše ugotovitve, ki bodo omogočile lažje razumevanje, v nadaljevanju predstavljenega, kaotičnega kriptografskega sistema. Slika 1 prikazuje nelinearni model digitalnega sita II. reda, ki se lahko ob določenih pogojih obnaša kaotično. a=0.5; &=-1; x2=-xl=0,S15: št. it8tacij=lCC»a3 x1 : Slika 2: Kaotična trajektorija. Fig. 2: Chaotic trajectory. ■1 -0.8 -O.S -0.4 .0.2 o 0,2 0.4 0.6 0.8 ! 1 Periode psevdo-naključnih sekvenc, uporabljenih v kriptografskih sistemih znašajo in več. 2 LFSR- Linear Feedback Shift Registers. Za to morajo biti izpolnjeni naslednji pogoji /7/: na vhodu mora biti ničelni signal; koeficienta a in ö morata biti izbrana tako, da sistem deluje na robu stabilnosti; za začetni stanji xi(0) in X2{0) morata veljati: x,(0) = -x^iQ) = X, >i-(2-fl)'" = 0,612372435695... (1) Kaotično obnašanje sita predstavlja trajektorija, ki v ravnini X1-X2 opisuje fraktalno geometrijo elips. Takšna trajektorija je prikazana na sliki 2. Dobili smo jo na osnovi simulacije 16-bitne strukture pri naslednjih parametrih sita: a=0,5; Ö=-1;X2(0)=-xi(0)=0,615. V primeru 16-bitne strukture je število vseh različnih stanj oziroma vrednosti spremenljivk xi in X2 2^® = 65536. Te vrednosti se pojavljajo psevdo-naključno. Velikost period je spremenljiva in odvisna od začetnega stanja spremenljivk stanj xi in X2 ter števila bitov, s katerimi spremenljivki predstavimo. Predstavljeno digitalno sito lahko v kaotičnem režimu delovanja uporabimo kot generator psevdo-naključne sek-vence (slika 3), ki je generirana na osnovi začetnih stanj spremenljivk xi in X2 ter koeficientov a in b. Te vrednosti predstavljajo seme oziroma začetno stanje za algoritem, ki opisuje delovanje sita. SEME GENERATOR PSEVDO-NAKLJUČNIH SEKVENC Slika 3: Generator psevdo-kaotičnih sekvenc. Fig. 3: Pseudo-chaotic stream generator 3. Kaotični kriptografski sistem Klasičnim kriptografskim sistemom se v zadnjih nekaj letih pridružujejo novi kaotični kriptografski sistemi, ki temeljijo na fenomenu determinističnega kaosa oziroma na zelo pre- prostih, vendar hiperobčutljivih iterativnih postopkih. Ker je področje determinističnega kaosa še precej neraziskano, je razumljivo, daje tudi t.i. kaotična kriptografija relativno nov subjekt raziskav, vezana na metode in standarde, ki so šele v razvojni fazi. Danes zasledimo tako tokovne kot blokovne kaotične kriptografske sisteme. V tokovnih simetričnih šifrirnih sistemih so generatorji psev-donaključne sekvence uporabljeni kot generatorji tokovnega ključa, kar pomeni, da se šifriranje odprtega sporočila izvaja bit za bitom, in sicer tako, da se tokovni ključ kombinira z biti odprtega sporočila. Ti sistemi so zelo hitri in izvajajo šifriranje manjših enot odprtega sporočila, kot je npr. bit ali znak (8-bitov) v datoteki, točka v digitalni sliki itd. Druga vrsta šifrirnih sistemov so blokovni. Pri teh se odprto sporočilo razdeli na tako dolge bloke, kot jih zahteva algoritem^, nato pa se biti posameznega bloka, v skladu s šifrirnim algoritmom, premeščajo in kombinirajo s tajnim ključem, generiranim z generatorjem naključnih sekvenc. V nadaljevanju obravnavamo tokovni kaotični kriptografski sistem, ki temelji na multipomični šifrirni/dešifrirni funkciji. Tokovni ključ je generiran s pomočjo prej predstavljenega kaotičnega digitalnega sita. Blokovna shema celotnega kriptografskega sistema je prikazana na sliki 4. Si/ri/ rti sislent AI.GO RITEM GE,\ERA TOR TOKOVI\'EOA kuuCA Dašijrifiti sistem DE^IERtRNl Al.CORlTEM CENERA TOR TOKOI'iSEOA KLJUČA Tajni hljn^ K' 'Tcijni kljuC Slika 4: Blokovna shema kriptografskega sistema. Fig. 4: Cryptographic system block scheme. Šifriranje odprtega sporočila / se izvaja postopoma po korakih (slika 5). /V-ti vzorec odprtega sporočila i{n) in psev-donaključne vrednosti k(n), se s pomočjo tajnega ključa K in posebne nelinearne, rekurzivne, multipomične funkcije, pretvori v šifriran vzorec tajnopisa s{n). Multipomične šifrirno funkcijo /8/ opisuje enačba: = ('■(«). k(n)), k{n)),...k{n)) + k{n +1) (2) pri čemer je N poljubno število iteracij nelinearne funkcije ff. \x + k)+2-h ~2-h<(x + k)<-h (x + k) ~h<{x + k) 1, se frekvenca šifriranja odprtega sporočila ustrezno zmanjša. Na sliki 7 je prikazan primer za A/ = 7, kjer je šifriranje besede odprtega sporočila trajalo 320 ns oz. s frekvenco 3,125 MHz. Enak čas je potreben tudi za dešifriranje (signal des na sliki 7). 5. Rezultati meritev Pravilno delovanje vezja potrjujejo rezultati meritev. Čeprav lahko šifriramo poljubne podatke kot so tekst, digitalizirani avdio ali video signal, smo delovanje kriptografskega sistema preverili s pomočjo šifriranja in dešifriranja sinusnega signala. Digitalizirane vrednosti smo zapisali v pomnilnik ROM (slika 6). Primerjavo med odprtim sporočilom in tajnopisom smo izvedli s pomočjo 12 bitnega serijskega DA pretvornika LTC2624, ki je na voljo na razvojni plošči. Sliki 8 a) in b) prikazujeta izmerjene odzive. a) fS 2 ps ■C: 3.............. 58 ns 2 ps iii:m— 2 ps —47mW BNL t 2 MS 0,1 v oc r» 2.1 v oc ä 3.1 v oc ž 4 50 mV OC ,1 üt J20.OB ns lät, 3. 1258 MHz Ext flC Q.OQ V 1MQ 5B |.JS BWL 1.1 V DC ä 2.1 V DC ;<, 3.1 V DC ž Ö SB rnV DC f. 62.00 kite Freq Ext flC 0.08 U IMO Slika 8: Rezultati meritev: a) Časovni odzivi šifrirnega sistema, b) Časovna poteka tajnopisa in dešifriranega odprtega sporočila, ter njuna amplitudna spektra. Fig. 8: Measured waveforms: a) Cypher circuit waveforms, b) Waveforms Simulated waveforms of cryptographic system realized in FPGA circuit. Slika 8 a) prikazuje: časovni potek signala ure clk_fx, izsek signala signal res_sft, signal pon, izsek signala pon, odprto sporočilo/nf (sinusni signal) in tajnopiss. Slika 8 b) prikazuje dešifrirano sporočilo (potek A), njegov amplitud-ni spekter (potek B), časovni potek šifriranega signala (potek 4) in njegov amplitudni spekter (potek C). V amplitudnem spektru šifriranega signala ni mogoče prepoznati oprtega sporočila. Maksimalna dopustna frekvenca delovanja kriptografskega sistema je veliki meri odvisna od razmestitve elementov, dolžine povezav v vezju FPGA in od izbranega vezja FPGA oz. tipičnih zakasnitev logičnih blokov ter povezav. V procesu načrtovanja običajno uporabljamo postopke avtomatskega razmeščanja in povezovanja na katere lahko vplivamo. S vhodnimi parametri in z določitvijo časovnih omejitev, ki jih morajo izpolnjevati elementi vezja in povezave, lahko vplivamo na doseženo maksimalno frekvenco delovanja. Tako smo s postopkom Fmax /10/ poiskali vhodne nastavitve algoritmov avtomatskega razmeščanja in povezovanja, ki maksimirajo hitrost delovanja šifrirnih, vezij realiziranih na petih različnih platformah. Rezultate prikazuje tabela 1. Družina Vezje FPGA Frekv. [MHzl Spartan 3E XC3S500E-4 39,44 Spartan 3E XC3S400-5 39,83 Virtex 2P XC2VP2-7 57,62 Virtex 4 XC4VLX25-12 77,23 Virtex 4 XC4VFX12-12 77,71 Tabela 1. Predvidene maksimalne frekvence delovanja šifrirnega vezja glede na izbrano vezje FPGA. Table 1. Expected maximum clock frequency of cipher circuit depending on chosen FPGA circuit. Maksimalne frekvence delovanja smo le ocenili, saj dejanskega delovanja nismo preizkusili. Najvišji hitrosti delovanja lahko pričakujemo v primeru uporabe vezij družine Virtex 4. Najnovejše družine Virtex 5 nismo preizkusili, saj je razvojno orodje ISE WebPack ne podpira. 6. Zaključek v prispevku smo predstavili kaotični kriptografski sistem in možnost njegove strojne realizacije. Šifrirni in dešifrirni sistem sestavljata multipomična šifrirna oz. dešifrirna funkcija in generator psevdo-kaotičnih sekvenc, realiziran s kaotičnim digitalnim sitom. Oba sistema smo izvedli v istem vezju FPGA družine Spartan 3E. Struktura šifrirnega sistema je bila 16 bitna. Bistvena prednost predlagane strojne izvedbe pred programsko, je hitrost izvajanja šifrirnega in dešifrirnega algoritma. Za generiranje psevdo-kaotične vrednosti je potrebna le ena perioda urinega signala. V našem primeru sta bili 21888875446 operaciji šifriranja in dešifriranja še inverzni, čeje bilafrel^-venca ure 25 MHz. Mal