Mažoritarinės funkcijos kriptografinių savybių tyrimas

Įvadas

Svarbus kriptografinių sistemų analizės etapas – matematinio modelio sudarymas ir šifro mazgų aprašymas diskretinėmis, dažniausiai Bulio, funkcijomis. Atliekant kriptoanalizę, diskretinė funkcija yra naudingas matematinis modelis, kuriuo galima pavaizduoti informacijos keitimą srautiniuose šifruose. Šis modelis patogus tuo, kad srautinius šifrus galima analizuoti diskretinės matematikos pagrindu, prieš tai tinkamai įvertinus kriptografines Bulio funkcijos savybes. Bulio funkcija, susidedanti iš n kintamųjų, – tai n-matės vektorinės erdvės F₂ⁿ atvaizdavimas vienmatėje erdvėje F₂ = {0,1} [2]:

Svarbus Bulio funkcijų analizės metodas – Walsho transformacija W_f(u). Funkcijos f Walsho transformacija, esant vektoriui uЄF₂ⁿ vadinama skaitinė vertė [2]:

Viena iš esminių kriptografinių savybių yra subalansavimas. Reikalavimai subalansavimui remiasi Golombo postulatais. Funkcija f (x) vadinama subalansuota, jei

čia wt( f ) yra funkcijos f (x) Є F₂ⁿ Hemingo svoris, t.y. skaičius x rinkmenų, tenkinančių lygybę f (x) = 1. Subalansuotos funkcijos Walsho transformacijos vertė, esant nuliniam vektoriui:

Kita kriptografinė Bulio funkcijos savybė yra netiesiškumas. Funkcijos tiesiškumas suprantamas kaip matematinio uždavinio efektyvaus sprendinio buvimas. Todėl kriptografinių sistemų netiesiškumas yra fundamentali ir neatskiriama savybė. Konkretus netiesiškumo traktavimas ir jį aprašantys parametrai gali būti įvairūs.

Dažniausiai netiesiškumas apibrėžiamas funkcijos Hemingo atstumu iki afiniųjų funkcijų visumos. Pagal Mebuso transformacijos teorema kiekvieną Bulio funkciją galima vienareikšmiškai išreikšti ANF (algebrinės normalinės formos) polinomu [4]:

Polinomo laipsnis deg f – tai netiesiškumo laipsnis. Jei polinomo laipsnis deg f = 1, tai tokia funkcija vadinama afiniąja funkcija[4]:

čia – skaliarinė sandauga. Netiesiškumo parametras nusako galimybę analizuojamąją funkciją pakeisti afiniuoju analogu. Šis atstumas vadinamas funkcijos netiesiškumu ir žymimas taip:

Funkcijos f Hemingo atstumas iki afiniųjų funkcijų dist( f , A_n ) [2] susijęs su Walsho transformacijos koeficientais tokia išraiška:

Remiantis tiesinės sandoros funkcijos apibrėžimu įvesta absoliučiai netiesinių funkcijų sąvoka. Absoliučiai netiesinė funkcija yra tada, kai . Ši savybė absoliučiai netiesines funkcijas sutapatina su kombinatorinėmis bent funkcijomis, todėl šios funkcijos kriptografijoje vadinamos bent funkcijomis. Bent funkcijos yra labai naudingos kriptografinės funkcijos, kadangi jos tuo pat metu turi maksimalų

atstumą iki visų tiesinių funkcijų ir maksimalų 2ⁿ⁻² atstumą iki visų funkcijų, turinčių tiesinę sandarą. Generatoriai, sukurti bent funkcijų pagrindu, yra atsparūs tiesinei sintezei. Kadangi Walsho transformacijos koeficientai yra sveikieji skaičiai, todėl maksimaliai netiesinės funkcijos egzistuoja tik esant lyginiam kintamųjų skaičiui.

Srautinio šifro modelio tyrimas

Dideliam kriptografiniam atsparumui pasiekti srautinių šifrų konstruktoriai naudoja mazgus postūmio registro judesio netolydumui didinti. Vienas tokių sprendimų yra R. Rueppelio pasiūlyta mažoritarinė LFSR pakopų sinchronizacija (1 pav.).

Šis būdas įgyvendintas A5/1 šifre. A5/1 šifras yra išnagrinėtas ir jo kriptoanalizė atlikta, tačiau ji remiasi bendraisiais šifrų analizės metodais: gimimo dienos paradoksu, laiko ir atminties pakeitimo ataka, ypatingų padėčių ataka ir t. t., tai yra buvo pasinaudota konstrukciniais šifro trūkumais, bet nebuvo sudarytas šios schemos matematinis modelis, nenustatyta šifravimo gamos generuojančioji funkcija ir neįvertintos jos kriptografinės charakteristikos ir kriterijai.

Sukurkime šifrą, kurio LFSR pakopos būtų sinchronizuojamos mažoritarine funkcija , o šifro raktų erdvė pakankamai nedidelė, kad galėtume atlikti išsamią statistinę šio šifro analizę. Galimas tokios konstrukcijos pavyzdys pateiktas 2 pav.

Ši srautinio šifro schema turi trijų, keturių ir penkių skilčių ilgio LFSR. Registrų ilgiai ir jų atvadai parinkti taip, kad išėjimo gama, nesant mažoritarinės sinchronizacijos, turėtų didžiausią periodą. Pirmasis registras generuoja maksimalią ilgio seką, kurios periodas 7, antrasis atitinkamai – 15, trečiasis – 31 periodo seką. Tokio generatoriaus raktų ilgis 12 bitų, o visa raktų erdvė– 212 , arba 4096, skirtingi raktų variantai.

Perrinkime visas galimas raktų kombinacijas ir atlikime generuojamos gamos statistinę analizę: apskaičiuokime generuojamos sekos periodą ir tiesinį kompleksiškumą Berlekamp ir Massey algoritmu. Rezultatus surašome į lentelę.

Sudarydami matematinį modelį, remsimės tik paskutinės skilties rezultatais, o kitus paneigsime dėl šių priežasčių:

1. 89 bitų ilgio sekos nagrinėjamoje grupėje yra kriptografiniu požiūriu stipriausios;

2. Likusios sekos – tai ypatingi atvejai: pirmojoje skiltyje yra tos raktų kombinacijos, kurių bent du registrai užpildyti nuliais, antrojoje skiltyje – kai trečiojo registro visos skiltys užpildytos nuliais , trečiojoje – kai antrojo, ir ketvirtojoje – kai trečiojo. Ypatingų atvejų susidarymo dažnis priklauso nuo registrų ilgių. Tikimybė, kad trumpiausio registro visos skiltys yra nuliai, lygi 1/2ⁿ, tad realiomis sąlygomis, kai registro ilgis viršija 20, ypatingų atvejų skaičius bus palyginti nereikšmingas.

Šis generatorius 3149 atvejais generuoja periodinę 89 bitų ilgio seką, kuri konkrečiam raktui skiriasi faze:

Norėdami rasti generuojančiąją sekos funkciją, tam tikslui analizuojamą schemą pakeiskime rekurentiniu generatoriumi, kuris generuotų tokią seką (3 pav.).

Rekurentinės sekos, generuojančios funkcijos kintamųjų skaičių, apibrėžia ilgiausio pasikartojančio segmento ilgis generuojamoje sekoje. Randame ilgiausią pasikartojantį segmentą:{0001110101}. Jo ilgis yra 10 bitų, vadinasi, turi būti 11 inicialinių generuojančiosios sekos bitų.

Tokios sekos generuojančiosios funkcijos f (x₁,...x₁₁) didžiausias polinomo laipsnis būtų 11, o teisingumo lentelės verčių matrica turėtų 2¹¹ elementų, iš jų: nulių matrica [F⁰ ] – 38 elementus , vienetų matrica [F¹] – 51 elementą, neapibrėžtų reikšmių matrica [F^d ] turėtų likusius 1959 elementus. Tokios funkcijos analizė yra ypač sudėtinga ir pareikalautų labai didelių skaičiavimo ir laiko išteklių.

Kriptografiniu požiūriu prasminga rasti tokią generuojančiąją funkciją, kuri generuotų seką, artimą nagrinėjamai (santykinis Hemingo atstumas < 0,5), o polinomo laipsnis būtų kiek galima mažesnis. Akivaizdu, kad 89 bitų periodinę seką generuotų funkcija, kurios kintamųjų skaičius būtų bent 7 ( 2⁷ −1 > 89).

Transformuokime analizuojamąją seką, pakeisdami kai kuriuos sekos elementus taip, kad ilgiausias pasikartojantis fragmento ilgis neviršytų 7 bitų, o Hemingo atstumas tarp sekų būtų ne didesnis kaip 44. Galimas tokios sekos variantas:

Šios sekos ilgiausio pasikartojančio fragmento ilgis yra septyni bitai, o Hemingo atstumas nuo pradinės sekos – 12 bitų. Tokią seką generuotų septynių kintamųjų Bulio funkcija f (x₁,..x₇ ) , maksimalus polinomo laipsnis yra 7. Šios funkcijos teisingumo lentelė yra 8× 2⁷ matmenų. Bet kuri 8 bitų sekos atkarpa yra funkcijos teisingumo lentelės viena eilutė , kurios pirmieji septyni bitai – tai funkcijos argumentų vertės, o aštuntas bitas – funkcijos vertė.

Tokių atkarpų kartu su cikliniu postūmiu yra 89, o neapibrėžtų verčių matrica turi 39 elementus, vadinasi, yra 2³⁹ skirtingų funkcijų, kurios generuoja tokią seką. Priskirkime visus neapibrėžtų verčių matricos elementus nulių matricai. Kaip žinome, kiekvieną visiškai apibrėžtą funkciją galime išreikšti unikaliu ANF polinomu:

čia x^I – vienanaris, lygus

o a_u Є F₂ – tai teisingumo lentelės elementas. Sudarę rekurentinės sekos teisingumo lentelę, išvedame sekos ANF:

Įvertinkime funkcijos netiesiškumą Hemingo atstumu iki afiniųjų funkcijų. Išreikškime atstumą šios funkcijos Walsh ir Hadamard transformacijos koeficientais:

čia a_i ir f (x) – tai funkcijos teisingumo lentelės atitinkami elementai. 4 pav. pateikti funkcijos f (x₁,..x₇ ) Walsh ir Hadamardo transformacijos rezultatai – funkcijos energinis spektras. Abscisių ašyje leksikografine tvarka atidėtos funkcijos argumentų vertės, ordinatėje – atitinkamas Walsho ir Hadamardo transformacijos koeficientas W_f (a) .

Matome, kad maksimali transformacijos |W_f (a) | vertė lygi 42, kai x₁,..., x₇ = {0,0,0,1,1,0,1}.

Apskaičiuojame netiesiškumą:

Dabar, žinodami funkcijos f (x₁,..x₇ ) netiesiškumą, įvertinkime seką S₁,.., S_i generuojančios funkcijos f (x₁,...x₁₁) netiesiškumą. Kadangi Hemingo atstumas tarp dviejų sekų S₁,.., S_i ir yra 12 bitų, tai akivaizdu, kad f (x₁,...x₁₁) atstumas iki afiniųjų funkcijų

Matome, kad f (x₁,...x₁₁) nėra bent funkcija, kadangi maksimalus netiesiškumas

Išvados

Mažoritarinės funkcijos yra paprasto dizaino ir labai netiesiškos, todėl plačiai naudojamos srautiniams šiframs konstruoti. Atliktas tyrimas parodė kelis esminius tokių šifrų trūkumus. Generuojančioji funkcija yra nesubalansuota, t. y. gamoje yra „nuliukų“ ir „vienetukų“ disbalansas, todėl tokia seka yra jautri testinei analizei. Šifravimo gama yra ne maksimalaus 2^N-1, o tik ~2^(2/3)N bitų periodo, kur N – rakto ilgis, todėl ją keblu taikyti didesniems failams šifruoti. Tokio šifro generuojančioji funkcija nepriklauso bent funkcijų klasei, jos taikymas srautinių šifrų registrams valdyti neužtikrina maksimalaus netiesiškumo, todėl galima tokio šifro šifravimo gamos tiesinė sintezė. Mažoritarinės funkcijos neapibrėžtumų matrica turi 1959 elementus, vadinasi, egzistuoja 2¹⁹⁵⁹ funkcijų, kurios generuoja tokią seką, todėl tolesniam tyrimui svarbu turėti algoritmą mažiausio laipsnio funkcijos paieškai.

Literatūra

1. Rueppel R.A. Security Models and Notions for Stream Ciphers // Cryptography and Coding 11, C. Mitchell, ed.- Oxford: Clarendon Press, 1992. – P. 213–230.
2. Zhang X.M, Zheng Y. Normalized Measures for Cryptographic security // Journal of Universal Computer science. – 2002. – No. 1(5). – P. 316–333.
3. Menezes, P. van Oorschot and S.Vanstone. Handbook of Applied Cryptography // by A., CRC Press, 1996. – P. 169–190.
4. Pommerening K. Fourier Analysis of Boolean Maps. A Tutorial–Fachbereich Mathematik der Johannes-Gutenberg- Universitaet Saarstrasse 21 D-55099 Mainz.– 2003.– P. 3–41.
5. Wegener, John The Complexity of Boolean Functions // Wiley & Sons Ltd., and B.G. Teubner, Stuttgart July 1987. ISBN: 0471 -91555-6. –P. 243–249.

P. Nefas, A.Vobolis. Mažoritarinės funkcijos kriptografinių savybių tyrimas // Elektronika ir elektrotechnika. – Kaunas: Technologija, 2005. – Nr. 1(65). – P. 73–76.