Lineaarinen siirtorekisteri palautteella. Lineaariset palautesiirtorekisterit näennäissatunnaislukugeneraattoreina Generaattorit epälineaarisilla muunnoksilla

Lineaarinen palautevaihtorekisteri(RSLOS, englanti) lineaarinen palautesiirtorekisteri, LFSR) on bittisanasiirtorekisteri, jossa syötetyn (siirretyn) bitin arvo on yhtä suuri kuin lineaarinen Boolen funktio rekisterin jäljellä olevien bittien arvoista ennen siirtoa. Voidaan järjestää sekä ohjelmiston että laitteiston mukaan. Sillä luodaan näennäissatunnaisia ​​bittisekvenssejä, joita käytetään erityisesti kryptografiassa.

Kuvaus

Rekisterin ohjaus laitteistototeutuksissa suoritetaan käyttämällä siirtopulssia (toisin sanoen kellotettu tai synkronointipulssi) kaikkiin soluihin. Rekisteriä ohjataan ohjelmistototeutuksissa silmukalla. Silmukan jokaisessa iteraatiossa palautefunktio lasketaan ja sanan bittejä siirretään.

Toimintaperiaate

Lineaarinen monimutkaisuus

Korrelaatioriippumattomuus

Yrittääkseen saavuttaa korkean lineaarisen monimutkaisuuden generoidussa sekvenssissä kryptografit yhdistävät epälineaarisesti useiden siirtorekisterien ulostulot. Tässä tapauksessa yksi tai useampi lähtösekvenssi (tai jopa yksittäisten LFSR:ien lähdöt) voidaan yhdistää yhteisellä virtauksella ja avata kryptanalyytikko. Tällaiseen haavoittuvuuteen perustuvaa hakkerointia kutsutaan korrelaatio ruumiinavaus. Tällaisen hakkeroinnin pääideana on havaita jokin korrelaatio generaattorin lähdön ja sen komponenttien lähtöjen välillä. Sitten ulostulosekvenssiä tarkkailemalla voidaan saada tietoa näistä välinastoista ja siten hakkeroida oskillaattori. Thomas Siegenthaler osoitti, että korrelaatioriippumattomuus on mahdollista määrittää tarkasti ja että korrelaatioriippumattomuuden ja lineaarisen kompleksisuuden välillä on kompromissi.

Ohjelmiston toteutus

LFSR:n ohjelmistototeutukset ovat melko hitaita ja toimivat nopeammin, jos ne on kirjoitettu assembly-kielellä. Yksi ratkaisu on 16 RLOS:n rinnakkaiskäyttö (tai 32, riippuen sanan pituudesta tietokonearkkitehtuurissa). Tällaisessa mallissa käytetään sanajoukkoa, jonka koko on yhtä suuri kuin siirtorekisterin pituus ja sanan jokainen bitti viittaa omaan RLOS:aan. Koska käytetään samoja väliottojärjestysnumeroita, tämä voi parantaa generaattorin suorituskykyä huomattavasti.

Fibonaccin kokoonpano

Harkitse 32-bittistä siirtorekisteriä. Sitä varten on napautusjakso (32 , 31 , 30 , 28 , 26 , 1) (\displaystyle \left(32,\;31,\;30,\;28,\;26,\;1\oikea)). Tämä tarkoittaa, että uuden bitin luomiseksi on tarpeen summata 31., 30., 29., 27., 25. ja 0. bitti käyttämällä XOR-toimintoa. Tuloksena olevalla LFSR:llä on enimmäisjakso 2 32 − 1 (\displaystyle 2^(32)-1). Tällaisen rekisterin koodi C:ssä on seuraava:

int LFSR_Fibonacci (tyhjä) ( staattinen etumerkitön pitkä S = 0x00000001; S = ((((S >> 31 ) ^ (S >> 30 ) ^ (S >> 29 ) ^ (S >> 27 ) ^ (S >> 25 ) ^ S ) & 0x00000001 )<< 31 ) | (S >> 1); palautus S & 0x00000001 ; )

Galois-kokoonpano

Tällä generaattorilla ei ole suurempaa salausvoimakkuutta, mutta se tarjoaa suorituskyvyn lisäyksen: kaikki XOR-operaatiot voidaan suorittaa yhdessä toiminnossa rinnakkaistoiminnolla, eikä peräkkäin peräkkäin, kuten Fibonacci-konfiguraatiossa. Tämä järjestelmä tarjoaa etuja myös laitteiston toteutuksessa.

C:n 32-bittisen siirtorekisterin koodi on seuraava:

int LFSR_Galois (tyhjä) ( staattinen etumerkitön pitkä S = 0x00000001 ; if (S & 0x00000001 ) ( S = (S ^ 0x80000057 >> 1 ) | 0x80000000 ; paluu 1 ;) 1 ; S >> = 0

On syytä huomata, että Galois-kokoonpanon LFSR_Galois-funktion kiinteän määrän kutsuja sisältävä silmukka toimii noin 2 kertaa nopeammin kuin LFSR_Fibonacci-funktio Fibonacci-kokoonpanossa (MS VS 2010 -kääntäjä Intel Core i5:ssä).

Luotu sekvenssiesimerkki

Fibonaccin kokoonpano

Olkoon RLOS annettu ominaispolynomilla x 3 + x + 1 (\displaystyle x^(3)+x+1). Tämä tarkoittaa, että lähtöbitit ovat 2 ja 0, ja polynomikaavan bitti tarkoittaa, että 0. bitti on tulobitti. Palautetoiminnolla on muoto S j = S j − 1 ⊕ S j − 3 (\displaystyle S_(j)=S_(j-1)\oplus S_(j-3)). Oletetaan, että siirtorekisterin alkuperäinen tila oli sekvenssi . Muut rekisteritilat näkyvät alla olevassa taulukossa:

Koska sisäinen tila seitsemännessä vaiheessa palasi alkuperäiseen tilaan, niin seuraavasta vaiheesta alkaen bitit toistetaan. Eli luotu sekvenssi on: [ 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 . . . ] (\displaystyle \left)(bittien järjestys sekvenssissä vastaa järjestystä, jossa LFSR on luonut ne). Näin ollen sekvenssin jakso on 7, eli suurin mahdollinen arvo, joka tapahtui annetun polynomin primitiivisyyden vuoksi.

Galois-kokoonpano

Otetaan sama ominaispolynomi, eli c 3 = c 1 = 1 (\displaystyle c_(3)=c_(1)=1), c 2 = 0 (\displaystyle c_(2)=0). Vain 1. bitti lisätään lähtöbittiin. Alkutila on sama. Rekisterin lisätiedot kertovat:

Rekisterin sisäinen tila seitsemännessä vaiheessa palasi alkuperäiseen tilaansa, joten sen jakso on myös 7. Toisin kuin Fibonacci-konfiguraatiossa, rekisterin sisäiset tilat osoittautuivat erilaisiksi, mutta generoitu sekvenssi on sama, vain siirretty 4 kellojaksolla: [ 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , . . . ] (\displaystyle \left)(bittien järjestys sekvenssissä vastaa järjestystä, jossa LFSR on luonut ne).

Luodaan primitiivisiä polynomia

Hyödyt ja haitat

Edut

• RSLOS:n perusteella luotujen salausalgoritmien (esimerkiksi virtasalaukset) korkea suorituskyky;
• vain yksinkertaisimpien yhteen- ja kertolaskuoperaatioiden käyttö, jotka on toteutettu laitteistossa lähes kaikissa tietokonelaitteissa;
• hyvät kryptografiset ominaisuudet (RSLOS voi tuottaa pitkän ajanjakson sekvenssejä, joilla on hyvät tilastolliset ominaisuudet);
• Rakenteensa ansiosta SFLO:t on helppo analysoida algebrallisilla menetelmillä.

Vikoja

Menetelmät generoitujen sekvenssien kryptografisen vahvuuden parantamiseksi

Generaattorit useilla siirtorekistereillä

Tämän tyyppinen oskillaattori koostuu useista lineaarisista takaisinkytkentäsiirtorekistereistä, jotka muodostavat bittejä x 1 , i , x 2 , i , … , x M , i (\näyttötyyli x_(1,i),\;x_(2,i),\;\pisteet ,\;x_(M,i)) vastaavasti. Seuraavaksi generoidut bitit muunnetaan jollakin Boolen funktiolla f (x 1 , i , x 2 , i , … , x M , i) (\näyttötyyli f(x_(1,i),\;x_(2,i),\;\pisteet ,\;x_(M) ,i))). On huomattava, että tämän tyyppisillä generaattoreilla on rekisteripituudet L i (\displaystyle L_(i)), i = 1 , 2 , … , M (\näyttötyyli i=1,\;2,\;\pisteet ,\;M), ovat keskenään yksinkertaisia.

Tämän generaattorin jakso on T = (2 L 1 − 1) ⋅ (2 L 2 − 1) ⋯ (2 L M − 1) ≲ 2 L (\näyttötyyli T=(2^(L_(1))-1)\cdot (2^( L_(2))-1)\cdots (2^(L_(M))-1)\lesssim 2^(L)), Missä L = ∑ i = 1 M L i (\displaystyle L=\sum \limits _(i=1)^(M)L_(i))- solujen kokonaismäärä. Näin ollen useiden RFLO:iden käyttö lisää generoidun sekvenssin jaksoa verrattuna yhteen rekisteriin, mikä lisää generaattorin kryptografista voimakkuutta. Lineaarinen kompleksisuus eli tiettyä generaattoria vastaavan lyhimmän rekisterin pituus myös kasvaa. Tällainen rekisteri löydetään käyttämällä Berlekamp-Massey-algoritmia käyttämällä generoitua sekvenssiä. Parhaimmillaan sen pituus on verrannollinen generoidun sekvenssin ajanjaksoon.

Generaattorit epälineaarisilla muunnoksilla

Tällaisen generaattorin lohkokaavio ei eroa edellisen generaattorin kaaviosta. Suurin ero on, että muunnoslaite määritellään epälineaarisella Boolen funktiolla f (x 1 , x 2 , … , x M) (\näyttötyyli f(x_(1),x_(2),\pisteet ,x_(M))). Sellaisena funktiona otamme esimerkiksi Zhegalkinin polynomin (Zhegalkinin lauseen mukaan mikä tahansa Boolen funktio voidaan yksilöllisesti esittää Zhegalkin-polynomilla).

Epälineaarinen generaattori voidaan toteuttaa myös käyttämällä epälineaarinen palautesiirtorekisteri. Hän voi antaa 2 2 L − 1 − L (\näyttötyyli 2^(2^(L-1)-L)) maksimijakson sekvenssivariantteja, joka on suurempi kuin SRSL:n.

Tämän generaattorin kryptografinen vahvuus kasvaa käytetyn funktion epälineaarisuuden vuoksi. Rekistereiden tilan määrittäminen generoidusta bittisekvenssistä on monimutkainen matemaattinen ongelma, koska ei ole tunnettua algoritmia, joka palauttaisi alkuperäiset tilat.

Tätä menetelmää käytetään mm Geff generaattori ja yleistetty Geff-generaattori, mutta tällaiset generaattorit voidaan kuitenkin hakkeroida korrelaatiohyökkäyksellä.

Generaattorit, joissa on eri vuororekisterien kellotus

Stop-and-go-generaattori

Stop-and-go-generaattori(eng. Stop-and-Go, Both-Piper) käyttää RLOS-1:n lähtöä ohjaamaan RLOS-2:n kellotaajuutta niin, että RLOS-2 muuttaa tilaansa jossain vaiheessa, vain jos RLOS-lähtö -1 tuolloin oli yhtä suuri kuin yksikkö. Tämä kaavio ei voinut vastustaa korrelaatiodissektiota.

Salauksen vahvuuden lisäämiseksi ehdotettiin sitä vuorotteleva stop-go generaattori. Se käyttää kolmea eripituista siirtorekisteriä. Tässä RSLOS-1 ohjaa 2. ja 3. rekisterin kellotaajuutta, eli RSLOS-2 muuttaa tilaansa, kun RSLOS-1:n lähtö on yhtä suuri, ja RSLOS-3, kun RSLOS-1:n lähtö on yhtä suuri nolla. Generaattorin lähtö on kahden lähdön RSLOS-2 ja RSLOS-3 modulo-lisäystoiminto. Tällä generaattorilla on pitkä jakso ja korkea lineaarinen monimutkaisuus. On olemassa menetelmä RSLOS-1:n korrelaatioavaukselle, mutta tämä ei heikennä suuresti generaattorin kryptografisia ominaisuuksia.

Siinä käytetään hienostunutta kellojärjestelmää kaksisuuntainen stop-go generaattori, joka käyttää kahta samanpituista siirtorekisteriä. Jos lähtö RLOS-1 jossain vaiheessa t i − 1 (\näyttötyyli t_(i-1))- yksi, silloin RSLOS-2 ei ole kellotettu tällä hetkellä t i (\displaystyle t_(i)). Jos RLOS-2:n lähtö tällä hetkellä t i − 1 (\näyttötyyli t_(i-1)) on yhtä suuri kuin nolla, ja ajanhetkellä t i − 2 (\näyttötyyli t_(i-2))- yksi, ja jos tämä rekisteri on kellotettu ajanhetkellä t i (\displaystyle t_(i)), silloin RLOS-1 ei ole kellotettu samalla hetkellä. Tämän piirin lineaarinen monimutkaisuus on suunnilleen yhtä suuri kuin generoidun sekvenssin jakso.

Itsestään hajottava generaattori

Moninopeuksinen oskillaattori sisätuotteella

Tämä generaattori käyttää kahta siirtorekisteriä RSLOS-1 ja RSLOS-2. RSLOS-2:n kellotaajuus d (\näyttötyyli d) kertaa enemmän kuin RSLOS-1. Tietyt näiden rekisterien bitit kerrotaan keskenään JA-operaatiolla. Kertolaskujen tulokset summataan XOR-operaatiolla tulossekvenssin tuottamiseksi. Tällä generaattorilla on korkea lineaarinen monimutkaisuus ja hyvät tilastolliset ominaisuudet. Sen tila voidaan kuitenkin määrittää pituisella lähtösekvenssillä L 1 + L 2 + log 2 ⁡ d (\näyttötyyli L_(1)+L_(2)+\log _(2)(d)), Missä L 1 (\displaystyle L_(1)) Ja L 2 (\displaystyle L_(2))- RSLOS-1:n ja RSLOS-2:n pituudet, ja d (\näyttötyyli d)- niiden kellotaajuuksien suhde.

Gollmannin kaskadi

Tämä piiri on parannettu versio stop-go-generaattorista. Se koostuu sarjasta LFSR:itä, joiden kunkin ajoitusta ohjaa edellinen LFSR. Jos RSLOS-1:n lähtö tällä hetkellä t i (\displaystyle t_(i)) on 1, sitten RLOS-2 on kellotettu. Jos RSLOS-2:n lähtö hetkellä t i (\displaystyle t_(i)) on 1, sitten RLOS-3 on kellotettu ja niin edelleen. Viimeisen LFSR:n lähtö on generaattorin lähtö. Jos kaikkien LFSR:ien pituus on sama ja yhtä suuri L (\displaystyle L), niin järjestelmän ajanjakso on alkaen M (\displaystyle M) RSLOS on yhtä suuri kuin (2 L − 1) M (\displaystyle (2^(L)-1)^(M)), ja lineaarinen monimutkaisuus on L (S) = L (2 L − 1) M − 1 (\näyttötyyli L(S)=L(2^(L)-1)^(M-1)) .

Tämä idea on yksinkertainen ja sitä voidaan käyttää luomaan jaksoja, joilla on valtavia jaksoja, suuria lineaarisia monimutkaisia ​​​​ja hyviä tilastollisia ominaisuuksia. Mutta valitettavasti he ovat herkkiä avaukselle nimeltä lukitus(englanniksi lock-in) milloin

Opetus- ja tiedeministeriö

VENÄJÄN VALTION SOSIAALINEN YLIOPISTO

INFORMAATIOTEKNIIKAN TIEDOKSI

TIETOSUOJALAITOS

Salausmenetelmät ja keinot tietoturvan varmistamiseksi

Kurssityöt

"R siirtorekisterit lineaarisella takaisinkytkellä näennäissatunnaisten lukugeneraattoreina"

Valmistunut:

3. vuoden opiskelija

ryhmä KZOI-D-3

Larionov I.P.

Tarkistettu:

Assoc. Baranova E.K.

Moskova 2011
SISÄLTÖ

Johdanto ……………………………..…………………………………….3

1. Työn teoreettinen perusta…………………………………………4
   1. Yleistä palautevuororekistereistä............4
      1. Tietoja RgSsLOS-pohjaisista suorasalauksista………………….………10
      2. Luodun näennäissatunnaisen sekvenssin lineaarisesta monimutkaisuudesta RgCsLOC…………………………………….……12
      3. Pseudosatunnaislukujen generoidun sarjan korrelaatioriippumattomuudesta PrCsLOC………..….13
      4. Tietoja muista keinoista avata generoitu pseudosatunnaislukujen sarja PrCsLOC…………………………………………………………..14
2. PrCsLOS:n ohjelmistototeutustorina….…………………………….15
   1. Algoritmin yleinen kaavio………………………………………15
   2. Ohjelmistomoduulien ja käyttöliittymän kuvaus.………………….16
   3. Käyttöohjeet………………………………………………20

Johtopäätös ………………………………………………………………22

Bibliografia………………………………………………….....23

Liite A ….………………………………………………………..24

JOHDANTO

Tämän työn tarkoituksena on kehittää ohjelmistosovellus, joka toteuttaa toiminnan palauterekistereillä. Tämän graafisen käyttöliittymän sovelluksen kehitys suoritetaan kielellä C++ Windows-käyttöjärjestelmälle.

Kun kryptografia kehittyi 1900-luvulla, kryptografien tehtävänä oli luoda salauslaitteita ja -koneita, jotka kykenivät salaamaan ja purkamaan viestit nopeasti ja luotettavasti. Tämän vaatimuksen täyttivät jo tuolloin avoimet symmetriset salausjärjestelmät, mutta niiden heikko kohta oli vahva riippuvuus avaimesta ja sen salassapito. Kätevin salausluokka, jota voidaan käyttää tähän tarkoitukseen, ovat gamma-salaukset. Ongelma syntyi gamman luomisesta, jota ei voitu havaita viestin salausta purettaessa. Teoriassa tämä oli mahdollista, jos gamma oli joka kerta satunnainen ja muuttui ajan myötä. Täysin satunnaisesti muuttuvaa gammaa käytettäessä viestin luotettavan salauksen ja salauksen purkamisen varmistaminen olisi kuitenkin vaikeaa. Kryptografit ryhtyivät ratkaisemaan tätä ongelmaa, jonka tarkoituksena oli löytää algoritmi, joka toteuttaa satunnaisen gamman generoinnin tietyn säännön mukaan; tällaisen sekvenssin tulisi sisältää nollia ja ykkösiä "oletettavasti" satunnaisissa paikoissa sekä ykkösten lukumäärä. ja nollien tulee olla suunnilleen samat. Tätä satunnaista sarjaa kutsuttiinnäennäissatunnaisuus,koska se luotiin tietyn säännön mukaan, ei satunnaisesti.

Ratkaisu löytyi pian. Siirtorekisterien ominaisuuksien tutkiminen mahdollisti sen, että palautesiirtorekisterit kykenevät generoimaan näennäissatunnaisia ​​sekvenssejä, jotka kestävät riittävän salauksen purkamista sisäisen rakenteensa vuoksi.

1. Työn teoreettinen perusta

1.1.Yleistä tietoa lineaarista palautetta käyttävistä siirtorekistereistä

Siirtorekisterisekvenssiä käytetään sekä kryptografiassa että koodausteoriassa. Heidän teoriansa on hyvin kehittynyt; vaihtorekistereihin perustuvat virtasalaukset olivat sotilassalauksen työhevonen kauan ennen elektroniikan tuloa.

Suljetun silmukan siirtorekisteri (jäljempänä RGSSOC) koostuu kahdesta osasta: siirtorekisteristä ja takaisinkytkentäfunktiosta.Siirtorekisteri on bittisarja. Bittien määrä määritetäänsiirtorekisterin pituus, jos pituus on n bittiä, niin rekisteriä kutsutaann-bittinen siirtorekisteri. Aina kun bitti on haettava, kaikki siirtorekisterin bitit siirtyvät oikealle 1 pisteen verran. Uusi vasemmanpuoleinen bitti on rekisterin kaikkien muiden bittien funktio. Siirtorekisterin lähtö on yksi, yleensä vähiten merkitsevä bitti.Vuororekisterijaksoon tuloksena olevan sekvenssin pituus ennen sen toiston alkamista.

Kuva Vaihtorekisteri palautteen kanssa

Vaihtorekistereille löydettiin nopeasti käyttöä stream-salauksissa, koska ne oli helppo toteuttaa digitaalisella laitteistolla. Vuonna 1965 Ernst Selmer, Norjan hallituksen johtava kryptografi, kehitti siirtorekisterisekvenssin teorian. Solomon Golomb, NSA:n matemaatikko, kirjoitti kirjan, joka esitteli joitakin hänen ja Selmerin tuloksia. Yksinkertaisin palautesiirtorekisterityyppi onlineaarinen palautesiirtorekisteri ( lineaarinen palautesiirtorekisteri, jäljempänä LFSR tai РгСсЛОС) . Tällaisten rekistereiden palaute on yksinkertaisesti joidenkin rekisteribittien XOR (modulo two additio), luettelo näistä bitteistä, jota kutsutaan väliottosekvenssiksi. Joskus tällaista rekisteriä kutsutaan Fibbonacci-konfiguraatioksi. Takaisinkytkentäsekvenssin yksinkertaisuuden vuoksi PrCsVOC:n analysointiin voidaan käyttää melko edistynyttä matemaattista teoriaa. Analysoimalla tuloksena olevia tulostussarjoja voit varmistaa, että sekvenssit ovat riittävän satunnaisia ​​ollakseen turvallisia. RGCCLOSia käytetään useammin kuin muita siirtorekistereitä kryptografiassa.

Kuva PrCsLOS Fibbonacci

Yleisesti ottaen n -bittinen PrCsLOS voi olla jossakin N = 2n -1 sisäinen tila. Tämä tarkoittaa, että teoriassa tällainen rekisteri voi generoida näennäissatunnaisen sekvenssin, jonka jakso on T=2 n -1 bittiä. (Sisäisten tilojen määrä ja jakso ovat yhtä suuret N = T max = 2 n -1, koska PrCcLOS:n täyttäminen nolilla saa siirtorekisterin tuottamaan loputtoman nollien sarjan, mikä on täysin hyödytöntä). Vain tietyissä haarajonoissa PrCsLOS kulkee syklisesti kaikkien 2:n läpi n -1 sisäiset tilat, kuten PrCsLOS ovatRgSsLOS maksimijaksolla. Tuloksena olevaa tulosta kutsutaanM-sekvenssi.

Esimerkki . Alla olevassa kuvassa näkyy 4-bittinen PrCCLOS, jossa ensimmäinen ja neljäs bitti on välitetty. Jos se alustetaan arvolla 1111, rekisteri saa seuraavat sisäiset tilat ennen toistamista:

Lähtösekvenssi on vähiten merkitsevien bittien merkkijono: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 jaksolla T = 15, mahdollisten sisäisten tilojen kokonaismäärä (paitsi nolla), N = 2 4 -1 = 16-1 = 15 = T max , siksi tulossekvenssi M -seuraus.

Jotta tietyllä PrCsLOS:lla olisi maksimijakso, väliottosekvenssistä ja vakiosta 1 muodostetun polynomin on oltava primitiivinen modulo 2. Polynomi esitetään potenssien summana, esimerkiksi astepolynomina. n näyttää tältä:

a n x n +a n-1 x n-1 +…+a 1 x 1 +a 0 x 0 =a n x n +a n-1 x n-1 +…+a 1 x+a 0, missä a i =(0, 1 ) kun i=1…n, a x i tarkoittaa numeroa.

Polynomin aste on siirtorekisterin pituus. N-asteen primitiivinen polynomi on redusoitumaton polynomi, joka on x:n jakaja 2n-1 +1, mutta se ei ole x:n jakaja d +1 kaikille d:lle, jotka ovat luvun 2 jakajia n -1. Vastaava matemaattinen teoria löytyy osoitteesta.

Yleisesti ottaen ei ole helppoa luoda tietyn asteen modulo 2 primitiivisiä polynomeja. Helpoin tapa on valita polynomi satunnaisesti ja tarkistaa, onko se primitiivinen. Tämä ei ole helppoa ja on vähän kuin sen tarkistamista, onko satunnaisesti valittu luku alkuluku - mutta monet matemaattiset ohjelmistopaketit voivat ratkaista tämän ongelman.

Jotkut, mutta eivät varmasti kaikki, eriasteiset polynomit, jotka ovat primitiivisiä modulo 2:ta, on annettu alla. Esimerkiksi äänittää

(32, 7, 5, 3, 2, 1, 0) tarkoittaa, että seuraava polynomi on primitiivinen modulo 2: x 32 + x 7 +x 5 + x 3 + x 2 + x + 1.

Tämä voidaan helposti yleistää PrCsVOC:ksi maksimijaksolla. Ensimmäinen numero on PrCsLOS:n pituus. Viimeinen numero on aina 0 ja se voidaan jättää pois. Kaikki luvut paitsi 0 määrittävät väliottosekvenssin, joka lasketaan siirtorekisterin vasemmasta reunasta. Toisin sanoen alemman asteen polynomin termit vastaavat paikkoja, jotka ovat lähempänä rekisterin oikeaa reunaa.

Jatkaen esimerkkiä, kirjoittaminen (32, 7, 5, 3, 2, 1, 0) tarkoittaa, että tietylle 32-bittiselle siirtorekisterille luodaan uusi bitti XOR-laskemalla 32., seitsemäs, viides, kolmas, toinen ja ensimmäinen bitti , tuloksena saadun PrCsLOS:n enimmäispituus on kierros 2 32 -1 arvot.

Kuva 4 32-bittinen PrCsLOC maksimipituudella

Tarkastellaan ohjelmakoodia PrCsLOS, jossa väliottosekvenssille on ominaista polynomi (32, 7, 5, 3, 2, 1, 0). C:ssä se näyttää tältä:

int LFSR() (

staattinen allekirjoittamaton pitkä ShiftRegister = 1;

/* Kaikki paitsi 0. */

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister >> 6)

^(ShiftRegister >> 4)

^(ShiftRegister >> 2)

^(ShiftRegister >> 1)

^ShiftRegister))

& 0x00000001)

<<31)

| (ShiftRegister >> 1) ;

palauta ShiftRegister & 0 x 00000001;)

Jos siirtorekisteri on pidempi kuin tietokonesana, koodista tulee monimutkaisempi, mutta ei paljon. Sovelluksessa B annetaan taulukko joistakin primitiivisistä polynomeista modulo 2, jota käytämme jatkossa näiden polynomien joidenkin ominaisuuksien tunnistamiseen sekä ohjelmistototeutuksessa väliottosekvenssin määrittämiseen.

Huomaa, että kaikilla taulukon elementeillä on pariton määrä kertoimia. Tämä pitkä taulukko on tarkoitettu jatkotyöskentelyä varten RgCsLOC:n kanssa, koska RgCsLOC:ta käytetään usein kryptografiaan virtasalauksilla ja näennäissatunnaisissa lukugeneraattoreissa. Meidän tapauksessamme voimme käyttää polynomeja, joiden korkein aste on enintään seitsemän.

Jos p(x) on primitiivinen, niin on myös x n p(1/x), joten jokainen taulukon elementti määrittelee itse asiassa kaksi primitiivistä polynomia. Esimerkiksi, jos (a, b, 0) on primitiivinen, niin (a, a-b, 0) on myös primitiivinen. Jos (a, b, c, d, 0) on primitiivinen, niin (a, a-d, a-c, a-b, 0) on myös primitiivinen. Matemaattisesti:

jos x on primitiivinen a +x b +1, niin x on myös primitiivinen a +x a-b +1,

jos x on primitiivinen a +x b +x c +x d +1, niin x on myös primitiivinen a +x a-d +x a-c +x a-b +1. Primitiiviset trinomit ovat nopeimmin toteutettavissa ohjelmistoissa, koska uuden bitin generoimiseksi sinun on XOR XOR vain kaksi siirtorekisterin bittiä (nollatermiä ei oteta huomioon, eli x 0 =1, katso esimerkki yllä). Todellakin, kaikki taulukossa annetut takaisinkytkentäpolynomit ovat harvassa, eli niillä on vähän kertoimia. Harvaus on aina heikkouden lähde, mikä joskus riittää rikkomaan algoritmin. Salausalgoritmeissa on paljon parempi käyttää tiheitä primitiivisiä polynomeja, sellaisia, joissa on monia kertoimia. Käyttämällä tiheitä polynomeja, erityisesti osana avainta, voidaan käyttää paljon lyhyempää PrCsLOS:ia.

Tiheiden primitiivisten polynomien modulo 2 generointi ei ole helppoa. Yleensä k-asteen primitiivisten polynomien luomiseksi sinun on tiedettävä luvun 2 tekijöihin jakaminen k -1.

PrCsLOS:t ovat itsessään hyviä pseudosatunnaisten sekvenssien generaattoreita, mutta niillä on joitain ei-toivottuja ei-satunnaisia ​​(deterministisiä) ominaisuuksia. Peräkkäiset bitit ovat lineaarisia, mikä tekee niistä hyödyttömiä salaukseen. PrCcLOS:lle, jonka pituus on n, sisäinen tila on generaattorin edellistä n lähtöbittiä. Vaikka takaisinkytkentäpiiri pidettäisiin salassa, se voidaan määrittää oskillaattorin 2n lähtöbitistä erittäin tehokkaalla Berlekamp-Massey-algoritmilla.

Lisäksi suuret satunnaisluvut, jotka on generoitu käyttämällä tämän sekvenssin peräkkäisiä bittejä, korreloivat voimakkaasti, eivätkä tietyntyyppisissä sovelluksissa ole ollenkaan satunnaisia. Tästä huolimatta RgCCLOS:ia käytetään usein salausalgoritmien luomiseen järjestelmien ja salausalgoritmien komponentteina.

1.2.Tietoja RgSSLOS-pohjaisista virtasalauksista

Peruslähestymistapa RgSSLOS-pohjaisen avainvirtageneraattorin suunnitteluun on yksinkertainen. Ensin otetaan yksi tai useampi PrCsLOS, yleensä eri pituuksilla ja erilaisilla takaisinkytkentäpolynomeilla. (Jos pituudet ovat koprimitiivisiä ja kaikki takaisinkytkentäpolynomit ovat primitiivisiä, generaattorilla on maksimipituus.) Avain on PrCcLOS-rekisterien alkutila. Joka kerta kun uusi bitti tarvitaan, siirrä PrCCLOC-rekistereitä hieman (tätä kutsutaan joskus kellotukseksi). Lähtöbitti on joidenkin PrCsLOS-rekisterien bittien funktio, edullisesti epälineaarinen. Tätä funktiota kutsutaan yhdistämisfunktioksi ja generaattoria kokonaisuudessaan yhdistelmägeneraattoriksi. (Jos lähtöbitti on yhden PrCCLOS:n funktio, oskillaattoria kutsutaan suodatinoskillaattoriksi.) Selmer ja Neal Zierler ovat kehittäneet suuren osan tämäntyyppisten laitteiden teoriasta. Voidaan aiheuttaa useita komplikaatioita. Jotkut oskillaattorit käyttävät eri kellotaajuuksia eri RgSsLOS:ille, joskus yhden oskillaattorin taajuus riippuu toisen lähdöstä. Nämä ovat kaikki sähköisiä versioita toista maailmansotaa edeltäneistä salauskoneideoista, joita kutsutaan kelloohjatuiksi oskillaattoriksi ( kelloohjatut generaattorit ). Kellon ohjaus voi olla myötäkytkentäistä, jossa yhden PrCcLOC:n lähtö ohjaa toisen PrCcLOC:n kellotaajuutta, tai takaisinkytkentä, jossa yhden PrCcLOC:n lähtö ohjaa omaa kellotaajuuttaan. Vaikka kaikki nämä generaattorit ovat ainakin teoriassa herkkiä pesimähyökkäyksille ja mahdollisille korrelaatioille, monet niistä ovat silti turvallisia.

Ian Cassells, entinen puhtaan matematiikan johtaja Cambridgessa ja kryptanalyytikko Bletchly Parkissa, sanoi, että "salakirjoitus on sekoitus matematiikkaa ja sekaannusta, ja ilman sekaannusta matematiikkaa voidaan käyttää sinua vastaan." Hän tarkoitti sitä, että virtasalauksissa tarvitaan tiettyjä matemaattisia rakenteita, kuten PrCcLOS, maksimaalisen pituuden ja muiden ominaisuuksien aikaansaamiseksi, mutta monimutkainen epälineaarinen kaaos on otettava käyttöön, jotta joku ei pääse saamaan rekisterin sisältöä ja rikkomaan algoritmia. Tämä neuvo koskee myös lohkoalgoritmeja.

Useimmat todelliset virtasalaukset perustuvat PrCsLOS:iin. Edes elektroniikan alkuaikoina niitä ei ollut vaikea rakentaa. Siirtorekisteri ei ole muuta kuin joukko bittejä, ja takaisinkytkentäsekvenssi on joukko XOR-portteja. Myös VLSI:tä käytettäessä PrCsLOC-pohjainen stream-salaus tarjoaa huomattavan suojan useiden logiikkaporttien avulla. PrSSLOSin ongelmana on, että niiden ohjelmistototeutus on erittäin tehotonta. Sinun tulee välttää harvaa palautepolynomeja - ne helpottavat korrelaatiohyökkäyksiä - ja tiheät palautepolynomit ovat tehottomia.

Tämä kryptografian ala kehittyy nopeasti ja on hallituksen valppaana valvonnassa N.S.A. . Suurin osa kehityksestä on luokiteltu - monet nykyään käytössä olevat armeijan salausjärjestelmät perustuvat RgSSLOS:iin. Itse asiassa useimmissa Cray-tietokoneissa (Cray 1, Cray X-MP, Cray Y-MP) on erittäin mielenkiintoinen ohje, jota yleensä kutsutaan "populaatiomääräksi". Se laskee ykkösten määrän rekisterissä ja sitä voidaan käyttää sekä laskemaan tehokkaasti Hamming-etäisyyttä kahden binäärisanan välillä että toteuttamaan PrCcLOS:n vektorisoitu versio. Tätä ohjetta pidetään kanonisena NSA-ohjeena, jonka on oltava lähes kaikissa tietokoneita koskevissa sopimuksissa.

Toisaalta yllättävän suuri määrä monimutkaisilta näyttäviä siirtorekisterigeneraattoreita on hakkeroitu. Ja tietysti NSA:n kaltaisten sotilaallisten kryptanalyyttisten virastojen hakkeroimien generaattoreiden määrä on vielä suurempi.

1.3.Pseudosatunnaislukujen generoidun sekvenssin lineaarisesta monimutkaisuudesta PrCsLOC

Stream-salaukset on usein helpompi analysoida kuin lohkosalaukset. Esimerkiksi tärkeä parametri, jota käytetään analysoitaessa generaattoreita PrCsLOS:iin perustuen, on lineaarinen kompleksisuus tai lineaarinen intervalli. Se määritellään lyhimmän PrCsLOS:n pituudeksi n, joka voi simuloida generaattorin lähtöä. Millä tahansa äärellisen automaattisen äärellisen kentän yli generoimalla sekvenssillä on äärellinen lineaarinen monimutkaisuus. Lineaarinen monimutkaisuus on tärkeää, koska käyttämällä yksinkertaista algoritmia, jota kutsutaan Berlekamp-Massey-algoritmiksi, on mahdollista määrittää tämä PrCcLOS tarkistamalla vain 2n bittiä avainvirrasta. Luomalla halutun PrCsLOS:n uudelleen murtat streamin salauksen.

Tämä ajatus voidaan laajentaa kentistä renkaisiin ja tapauksiin, joissa lähtösekvenssiä käsitellään numeroina parittomien ominaisuuksien kentässä. Lisälaajennus johtaa lineaarisen kompleksisuusprofiilin käsitteen käyttöönottoon, joka määrittää sekvenssin lineaarisen monimutkaisuuden sen pidentyessä. On olemassa myös pallomaisen ja neliömäisen monimutkaisuuden käsitteitä. Joka tapauksessa muista, että suuri lineaarinen monimutkaisuus ei välttämättä takaa generaattorin turvallisuutta, mutta pieni lineaarinen monimutkaisuus osoittaa, että generaattori ei ole tarpeeksi turvallinen.

1.4.Pseudosatunnaislukujen generoidun sekvenssin korrelaatioriippumattomuudesta PrCsLOS

Kryptografit yrittävät saavuttaa korkean lineaarisen monimutkaisuuden yhdistämällä epälineaarisesti joidenkin lähtösekvenssien tulokset. Vaara tässä on, että yksi tai useampi sisäinen ulostulosekvenssi - usein vain yksittäisten PrCsLOS:ien lähdöt - voidaan yhdistää yhteisellä avainvirralla ja avata lineaarista algebraa käyttäen. Tätä ruumiinavausta kutsutaan usein korrelaatio ruumiinavaukseksi tai hajota ja hallitse ruumiinavaukseksi. Thomas Siegenthaler osoitti, että korrelaatioriippumattomuus on mahdollista määritellä tarkasti ja että korrelaatioriippumattomuuden ja lineaarisen kompleksisuuden välillä on kompromissi.

Korrelaatiohyökkäyksen pääideana on havaita jokin korrelaatio generaattorin lähdön ja jonkin sen komponentin lähdön välillä. Sitten ulostulosekvenssiä tarkkailemalla voidaan saada tietoa tästä välilähdöstä. Näitä tietoja ja muita korrelaatioita käyttämällä voidaan kerätä tietoja muista välituloista, kunnes generaattori vaarantuu.

Korrelaatiohyökkäykset ja niiden muunnelmat, kuten nopeat korrelaatiohyökkäykset, tarjoavat kompromissin laskennan monimutkaisuuden ja tehokkuuden välillä, ja niitä on käytetty menestyksekkäästi monia PrCsLOS-pohjaisia ​​avainvirtageneraattoreita vastaan.

1.5.Tietoja muista menetelmistä generoidun näennäissatunnaisten lukujen sarjan PrCsLOS avaamiseksi

On muitakin tapoja rikkoa avainvirran generaattorit. Lineaarinen johdonmukaisuustesti yrittää löytää salausavaimen osajoukon matriisitekniikalla. On myös "meet-in-the-middle johdonmukaisuushyökkäys". Lineaarinen oireyhtymä-algoritmi perustuu kykyyn kirjoittaa fragmentti tulossekvenssistä lineaarisen yhtälön muodossa. On olemassa paras affininen approksimaatiohyökkäys ja johdettu sekvenssihyökkäys. Differentiaalisen ja lineaarisen krypta-analyysin menetelmiä voidaan soveltaa myös virtasalauksiin.

2. PrCsLOS:n ohjelmistototeutuksen kuvaustorina

2.1.Algoritmin yleinen kaavio

2.2.Ohjelmistomoduulien ja käyttöliittymän kuvaus

Alla kuva 3 näyttää ohjelmaikkunan.

Kuva Ohjelman käyttöliittymä

Valikossa on seuraavat toiminnot:

• Tiedosto-> Tallenna raportti

Tämä toiminto luo raporttitiedoston, johon tallennetaan PrCsLOS:n alkutila, väliottosekvenssi, vastaanotetun näennäissatunnaisen bittisekvenssin jakso, itse sekvenssi ja tilataulukko. Jos tiedoston tallennus onnistui, näyttöön tulee onnistuneesta tallennuksesta kertova viesti (kuva 4). Suositeltu raporttitiedostotunniste on *. txt.

Piirustus

• Tiedosto-> Poistu

Tämä ominaisuus varmistaa, että sovellus sulkeutuu.

• Aseta napautusjärjestys

Tämä toiminto luo napautusjakson lukemalla arvot ruuduista, jotka käyttäjä on valinnut näyttölomakkeella. Tämän jälkeen se ilmoittaa käyttäjälle napautusjakson luomisesta (kuva 5). Väliottosekvenssi määrittää, mitkä siirtorekisterin kiikut antavat palautetta. XOR luodaksesi offsetbitin. Oletusarvoisesti palaute ensimmäiseltä liipaisuudelta on aina asetettu; muiden yhteyksien puuttuessa suoritetaan siirtyminen vasemmalle alemman asteen bitin siirtyessä korkeamman asteen asentoon.

Piirustus

• Aseta alkuarvo

Tämä toiminto lukee käyttäjän toimittaman alkurekisteriarvon ikkunasta Muokata 1 ja tarkistaa syötetyn arvon määritettyjen ehtojen mukaisesti: syötetty merkkijono ei ole tyhjä (kuva 6), syötetyn merkkijonon pituus on kahdeksan (8 bittiä = 1 tavu, kuva 7), syötetty merkkijono sisältää vain nollia ja/tai ykkösiä (kuva 8), syötetty merkkijono on muu kuin nolla (kuva 9). Muussa tapauksessa näyttöön tulee virheilmoituksia, käyttäjän on korjattava ne ja painettava painiketta uudelleen. Jos tarkistus onnistuu, alkuarvo kirjoitetaan tilataulukkoon "Initial"-riville ja lähetetään ilmoitus (kuva 10).

Piirustus

Piirustus

Piirustus

Piirustus

Piirustus

• Vaihtokotelo

Tämä toiminto emuloi siirtorekisterin toimintaa. Suorittamalla peräkkäin 256 siirtoa, jokainen siirto generoi näennäissatunnaisen sekvenssin lähtöbitin ja uuden rekisteritilan. Heti kun rekisteritila on yhtä suuri kuin alkuperäinen, jakso lasketaan ja näytetään kentässä Muistio 1 tuloksena oleva näennäissatunnainen sekvenssi.

• Ohje->Tietoja ohjelmasta

Tämä toiminto näyttää lyhyen kuvauksen ohjelmasta ja ohjeet (Kuva 11).

Piirustus

• Ohje-> Tietoja kirjoittajasta

Tämä toiminto näyttää tiedot ohjelman tekijästä (Kuva 12).

Piirustus

2.3.Käyttäjän ohjeet

1. Aseta ensin rekisteri alkuperäiseen tilaan. Sen tulee sisältää kahdeksan binaarimerkkiä. Muussa tapauksessa näyttöön tulee virheilmoitus ja sinun on korjattava syötetty arvo. Napsauta "Aseta alkuarvo" -valikkokohtaa.
2. Valitse sitten rekisteripalautteiden valintaruudut (napauta järjestystä). Napsauta "Aseta kosketusjärjestys" -valikkokohtaa.
3. Napsauta seuraavaksi "Case Shift" -valikkokohtaa. Ennen kuin teet tämän, varmista, että olet suorittanut vaiheet 1 ja 2, muuten tapahtuu ohjelmistovirhe.
4. Saatuasi tulokset, voit tallentaa ne napsauttamalla valikkokohtaa ”Tiedosto->Tallenna raportti”. Ennen kuin teet tämän, varmista, että olet suorittanut vaiheet 1-3, muuten tapahtuu ohjelmistovirhe.
5. Saat apua napsauttamalla valikkokohtia "Tiedosto->Tietoja ohjelmasta", "Tiedosto->Tietoja tekijästä".
6. Nähdäksesi rekisterin toiminnan muiden väliottosekvenssin arvojen kanssa ja rekisterin alkutilan, toista vaiheet 1-3 ja syötä muut parametrit.

PÄÄTELMÄ

Tässä työssä PrCsLOS:ia pidettiin näennäissatunnaisten lukugeneraattoreina. Ohjelma voi toimia visuaalisena esittelynä siirtorekisterien toimintaperiaatteista lineaarisen palautteen avulla XOR . Sen avulla voit tutkia näennäissatunnaisen bittisekvenssin muodostamisen periaatetta, rekisterin alkuarvon ja näennäissatunnaisen sekvenssin arvon välistä suhdetta, väliottosekvenssiä ja jaksoa. Tuloksena olevaa näennäissatunnaista gammaa voidaan käyttää toisessa ohjelmistosovelluksessa (esimerkiksi gammasalauksen ohjelmistototeutuksessa).

Tällä hetkellä näitä rekistereitä ei käytetä itsenäisinä pseudosatunnaislukujen generaattoreina, vaan ne ovat osa monimutkaisempia laitteita. He kuitenkin avasivat uusia suuntauksia matematiikassa (primitiivisten polynomien etsiminen äärellisistä kentistä, matemaattiset menetelmät näennäissatunnaislukugeneraattoreiden hakkerointiin). Ilman PrSSLOS-pohjaisten generaattoreiden toimintaperiaatteiden tuntemusta on mahdotonta ymmärtää monimutkaisempien laitteiden toimintaa. Yksinkertaisen laitteistototeutuksensa vuoksi niitä käytetään laajalti tekniikassa. RgCCOS:n tutkimus johti uusien salausten - lohko- ja stream - syntymiseen, jotka perustuvat tämäntyyppisiin rekistereihin (liikkuva permutaatiosalaus, DES ja niin edelleen.; EDS, hash-funktiot).

Yleisesti ottaen tämän alan tutkimus on johtanut vakavasti kryptografian ja kryptanlytiikan, tietokoneiden ja laitteiden kehittämiseen ja mahdollistanut myös useiden muiden hyödyllisten toimintojen (esimerkiksi syklisten koodien korjaamisen) toteuttamisen.

KIRJASTUS

1. Schneier Bruce. Sovellettu kryptografia. Protokollat, algoritmit, lähdetekstit C-kielellä. M.: Triumph, 2002
2. Babash A.V. Nykyaikaisen tietoturvan kryptografiset ja automaatioteoreettiset näkökohdat. Osa 1 M.: Kustantaja. EAOI Center, 2009. 414 s.
3. E.S. Selmer. Monografia: "Lineaarinen rekursio äärellisessä kentässä." Bergenin yliopisto, Norja, 1966.
4. N. Zierler ja J. Brillhart. "On primitive trinomials modulo 2", Journal of Information and Control, Vol. 13 No. 6 December 1968, s. 541-544.
5. K.H. Meyer ja W. L. Tuchman. "Pseudosatunnaiset koodit voidaan rikkoa", Electronic Design -lehti, nro. 23. marraskuuta 1972.
6. J. L. Massey. "Siirtorekisterien yleistäminen ja Bose-Chowdhury-Hocquenghem-koodin dekoodaus", IEEE Transactions on Information Theory, v. IT-15, n . 1, tammikuu 1969, s. 122-127.
7. S.U. Golomb. Shift Register Sequences, San Francisco, Golden Day, 1967 (uudelleenpainos Aigean Park Press, 1982).

Liite A

Joidenkin primitiivisten polynomien taulukko modulo 2

(1, 0)

(2, 1, 0)

(3, 1, 0)

(4, 1, 0)

(5, 2, 0)

(6, 1, 0)

(7, 1, 0)

(7, 3, 0)

(8, 4, 3, 2, 0)

(9, 4, 0)

(10, 3, 0)

(11, 2, 0)

(12, 6, 4, 1, 0)

(13, 4, 3, 1, 0)

(14, 5, 3, 1, 0)

(15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0)

(17, 5, 0)

(17, 6, 0)

(18, 7, 0)

(18, 5, 2, 1, 0)

(19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0)

(22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)
(25, 3, 0)

(26, 6, 2, 1, 0)

(27, 5, 2, 1, 0)

(28, 3, 0)

(29, 2, 0)

(30, 6, 4, 1.0)

(31, 3, 0)

(31, 6, 0)

(31, 7, 0)

(31, 13, 0)

(32, 7, 6, 2, 0)

(32, 7, 5, 3, 2, 1, 0)

(33, 13, 0)

(33, 16, 4, 1, 0)

(34, 8, 4, 3, 0)

(34, 7, 6, 5, 2, 1, 0)

(35, 2, 0)

(135, 11, 0)

(135, 16, 0)

(135, 22, 0)

(136, 8, 3, 2, 0)

(137, 21, 0)

(138, 8, 7, 1, 0)

(139, 8, 5, 3, 0)

(140, 29, 0)

(141, 13, 6, 1, 0)

(142, 21, 0)

(143, 5, 3, 2, 0)

(144, 7, 4, 2, 0)

(145, 52, 0)

(145, 69, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0)

(148, 27, 0)

(149, 10, 9, 7, 0)

(150, 53, 0)

(151, 3, 0)

(151, 9, 0)

(151, 15, 0)

(151, 31, 0)

(151, 39, 0)

(151, 43, 0)

(151, 46, 0)

(151, 51, 0)

(151, 63, 0)

(151, 66, 0)

(151, 67, 0)

(151, 70, 0)

(36, 11, 0)

(36, 6, 5, 4, 2, 1, 0)

(37, 6, 4, 1, 0)

(37, 5, 4, 3, 2, 1, 0)

(38, 6, 5, 1, 0)

(39, 4, 0)

(40, 5, 4, 3, 0)

(41, 3, 0)

(42, 7, 4, 3, 0)

(42, 5, 4, 3, 2, 1, 0)

(43, 6, 4, 3, 0)

(44, 6, 5, 2, 0)

(45, 4, 3, 1, 0)

(46, 8, 7, 6, 0)

(46, 8, 5, 3, 2, 1, 0)

(47, 5, 0)

(48, 9, 7, 4, 0)

(48, 7, 5, 4, 2, 1, 0)

(49, 9, 0)

(49, 6, 5, 4, 0)

(50, 4, 3, 2, 0)

(51, 6, 3, 1, 0)

(52, 3, 0)

(53, 6, 2, 1, 0)

(54, 8, 6, 3, 0)

(54, 6, 5, 4, 3, 2, 0)

(55, 24, 0)

(55, 6, 2, 1, 0)

(56, 7, 4, 2, 0)

(57, 7, 0)

(57, 5, 3, 2, 0)

(58, 19.0)

(58, 6, 5, 1, 0)

(59, 7, 4, 2, 0)

(59, 6, 5, 4, 3, 1, 0)

(60, 1, 0)

(61, 5, 2, 1, 0)

(62, 6, 5, 3, 0)

(63, 1, 0)

(64, 4, 3, 1, 0)

(65, 18, 0)

(65, 4, 3, 1, 0)

(66, 9, 8, 6, 0)

(66, 8, 6, 5, 3, 2, 0)

(67, 5, 2, 1, 0)

(152, 6, 3, 2, 0)

(153, 1, 0)

(153, 8, 0)

(154, 9, 5, 1, 0)

(155, 7, 5, 4, 0)

(156, 9, 5, 3, 0)

(157, 6, 5, 2, 0)

(158, 8, 6, 5, 0)

(159, 31, 0)

(159, 34, 0)

(159, 40, 0)

(160, 5, 3, 2, 0)

(161, 18, 0)

(161, 39, 0)

(161, 60, 0)

(162, 8, 7, 4, 0)

(163, 7, 6, 3, 0)

(164, 12, 6, 5, 0)

(165, 9, 8, 3, 0)

(166, 10, 3, 2, 0)

(167, 6, 0)

(170, 23, 0)

(172, 2, 0)

(174, 13, 0)

(175, 6, 0)

(175, 16, 0)

(175, 18, 0)

(175, 57, 0)

(177, 8, 0)

(177, 22, 0)

(1 77, 88, 0)

(68, 9, 0)

(68, 7, 5, 1, 0)

(69, 6, 5, 2, 0)

(70, 5, 3, 1, 0)

(71, 6, 0)

(71, 5, 3, 1, 0)

(72, 10, 9, 3, 0)

(72, 6, 4, 3, 2, 1, 0)

(73, 25, 0)

(73, 4, 3, 2, 0)

(74, 7, 4, 3, 0)

(75, 6, 3, 1, 0)

(76, 5, 4, 2, 0)

(77, 6, 5, 2, 0)

(78, 7, 2, 1, 0)

(79, 9, 0)

(79, 4, 3, 2, 0)

(80, 9, 4, 2, 0)

(80, 7, 5, 3, 2, 1, 0)

(81, 4, 0)

(82, 9, 6, 4, 0)

(82, 8, 7, 6, 1, 0)

(83, 7, 4, 2, 0)

(84, 13, 0)

(84, 8, 7, 5, 3, 1, 0)

(85, 8, 2, 1, 0)

(86, 6, 5, 2, 0)

(87, 13, 0)

(87, 7, 5, 1, 0)

(88, 11, 9, 8, 0)

(88, 8, 5, 4, 3, 1, 0)

(89, 38, 0)

(89, 51, 0)

(89, 6, 5, 3, 0)

(90, 5, 3, 2, 0)

(91, 8, 5, 1, 0)

(91, 7, 6, 5, 3, 2, 0)

(92, 6, 5, 2, 0)

(93, 2, 0)

(94, 21, 0)

(94, 6, 5, 1, 0)

(95, 11, 0)

(95, 6, 5, 4, 2, 1, 0)

(96, 10, 9, 6, 0)

(96, 7, 6, 4, 3, 2, 0)

(178, 87, 0)

(183, 56, 0)

(194, 87, 0)

(198, 65, 0)

(201, 14, 0)

(201, 17, 0)

(201, 59, 0)

(201, 79, 0)

(202, 55, 0)

(207, 43, 0)

(212, 105, 0)

(218, 11, 0)

(218, 15, 0)

(218, 71, 0)

(218.83, 0)

(225, 32, 0)

(225, 74, 0)

(225, 88, 0)

(225, 97, 0)

(225, 109, 0)

(231, 26, 0)

(231, 34, 0)

(234, 31, 0)

(234, 103, 0)

(236, 5, 0)

(250, 103, 0)

(255, 52, 0)

(255, 56, 0)

(255, 82, 0)

(258, 83, 0)

(266, 47, 0)

(97, 6, 0)

(98, 11, 0)

(98, 7, 4, 3, 1, 0)

(99, 7, 5, 4, 0)

(100, 37, 0)

(100, 8, 7, 2, 0)

(101, 7, 6, 1, 0)

(102, 6, 5, 3, 0)

(103, 9, 9)

(104, 11, 10, 1, 0)

(105, 16, 0)

(106, 15, 0)

(107, 9, 7, 4, 0)

(108, 31, 0)

(109, 5, 4, 2.0)

(110, 6, 4, 1, 0)

(111, 10, 0)

(111, 49, 0)

(113, 9, 0)

(113, 15, 0)

(113, 30, 0)

(114, 11, 2, 1, 0)

(115, 8, 7, 5, 0)

(116, 6, 5, 2, 0)

(117, 5, 2, 1, 0)

(118, 33, 0)

(119, 8, 0)

(119, 45, 0)

(120, 9, 6, 2, 0)

(121, 18, 0)

(122, 6, 2, 1, 0)

(123, 2, 0)

(124, 37, 0)

(125, 7, 6, 5, 0)

(126, 7, 4, 2, 0)

(127, 1, 0)

(127, 7, 0)

(127, 63, 0)

(128, 7, 2, 1, 0)

(129, 5, 0)

(130, 3, 0)

(131, 8, 3, 2, 0)

(132, 29, 0)

(133, 9, 8, 2, 0)

(134, 57, 0)

(270, 133, 0)

(282, 35, 0)

(282, 43, 0)
(286, 69, 0)

(286, 73, 0)

(294, 61, 0)

(322, 67, 0)

(333, 2, 0)

(350, 53, 0)

(366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0)

(462, 73, 0)

(521, 32, 0)

(521, 48, 0)

(521, 158, 0)

(521, 168, 0)

(607, 105, 0)

(607, 147, 0)

(607, 273, 0)

(1279, 216, 0)

(1279, 418, 0)

(2281, 715, 0)

(2281, 915, 0)

(2281, 1029, 0)

(3217, 67, 0)

(3217, 576, 0)

(4423, 271, 0)

(9689, 84, 0)

Aloitustilaan siirtyminen (IS)

syötteiden oikeellisuuden tarkistaminen

Anna virheilmoitus

Napautusjärjestyksen asettaminen

IC:n tallentaminen tilataulukkoon

Levy i rekisterin tila ja ulostulobitti tilataulukkoon

IS==Nykyinen tila

Tulosten tallentaminen

Näennäissatunnainen sekvenssilähtö

Poistu

Tuoda markkinoille

Joo

Joo

Ei

Linear Feedback Shift Register (LFSR) on mekanismi, jolla luodaan näennäissatunnainen binääribittien sekvenssi. Rekisteri (kuva 1) koostuu useista soluista, jotka on muodostettu alustusvektorin (useimmiten salaisen avaimen) avulla. Rekisterin toiminta määräytyy kunkin bitin ja palautteen välisen tiedonsiirron läsnäolon tai puuttumisen perusteella. Palauterekisterin tapit eivät ole kiinteitä, vaan ovat osa avainta. Seuraavassa vaiheessa rekisterisolujen sisältö siirretään yhden aseman oikealle ja yksi XOR-operaation seurauksena vapaaksi jäänyt bitti sijoitetaan vasemmanpuoleisimpaan soluun.

Riisi. 1. Lineaarinen takaisinkytkentäsiirtorekisteri

Saavuttaaksesi suurimman salauksen gammajakson, bittien lukumäärä m siirtorekisteri valitaan yhtä suureksi kuin jokin Mersennen alkuluvuista (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203...), ja rekisterin sisäiset yhteydet tulee valita korkeimman asteen redusoitumattomien primitiivisten polynomien mukaan m. Tässä tapauksessa salauksen gammajakso voi saavuttaa (2 m-1).

LFSR on nopea ja helppo toteuttaa sekä ohjelmistossa että laitteistossa. Oikealla takaisinkytkentäbittien valinnalla generoiduilla sarjoilla on hyvät tilastolliset ominaisuudet. LFSR:ää käytetään peruselementtinä erittäin turvallisten järjestelmien rakentamisessa.

Rekisterikaskadi on joukko LFSR:itä, jotka on kytketty siten, että yhden LFSR:n käyttäytyminen riippuu edellisen LFSR:n käyttäytymisestä kaskadissa. Tämä "riippuvainen" käyttäytyminen on tyypillisesti suunniteltu ohjaamaan seuraavan LFSR:n siirtolaskuria ensimmäisellä LFSR:llä.

Esimerkiksi rekisteriä siirretään yhden askeleen verran, jos edellisen rekisterin arvo on 1, ja jos arvo on 0, niin rekisteriä siirretään kaksi askelta tai jollain muulla tavalla. Suuri määrä tällaisia ​​yhdistelmiä mahdollistaa erittäin korkean turvallisuuden.

Turvallisimmat sekvenssit tuotetaan kutistuvalla generaattorilla, joka perustuu kahden LFSR-rekisterin tulosten yksinkertaiseen vuorovaikutukseen. Yhden tuloksen bitit määräävät, käytetäänkö toisen tuloksen vastaavia bittejä osana täydellistä "virtaavainta". Kompressiogeneraattori on yksinkertainen, skaalautuva ja sillä on hyvät suojaominaisuudet. Sen haittapuoli on, että "stream-avaimen" generointinopeus ei ole vakio, ellei joitain varotoimia ryhdytä.

Fibonacci-menetelmä viiveillä Yksi laajalti käytetyistä Fibonacci-generaattoreista perustuu seuraavaan iteratiiviseen kaavaan:

Missä Y k- todelliset luvut alueelta

Riisi. 2. Round-robin-salaus

DES-lähtötakaisinkytkentätilaa voidaan käyttää näennäissatunnaisten lukujen luomiseen, samalla tavalla kuin sitä käytetään virran salaukseen. Jokaisen salausvaiheen ulostulona on 64-bittinen arvo, josta vain merkittävin j-bittiä syötetään takaisin salaukseen. 64-bittiset lähdöt ovat pseudosatunnaislukujen sarja, jolla on hyvät tilastolliset ominaisuudet.

ANSI X9.17 -standardissa kuvattu pseudosatunnaislukugeneraattori on yksi salausturvallisimmistasta. Tätä tekniikkaa käyttävät sovellukset sisältävät taloudellista turvallisuutta ja PGP-sovelluksia.

ANSI X9.17 -generaattori koostuu seuraavista osista (kuva 3):

1. Tulo: Generaattoria ohjataan kahdella näennäissatunnaisella sisääntulolla. Ensimmäinen tulo on 64-bittinen esitys nykyisestä päivämäärästä ja kellonajasta ( DT i), jotka muuttuvat aina, kun numero luodaan. Toinen tulo on 64-bittinen siemen, joka alustetaan johonkin mielivaltaiseen arvoon ja jota muutetaan pseudosatunnaislukujonon luomisen aikana ( V i).

2. Näppäimet: Generaattori käyttää kolmea kolminkertaista DES-moduulia kahdella näppäimellä K1, K2. Kaikki kolme käyttävät samaa 56-bittistä avainparia, joka on pidettävä salassa ja käyttää vain näennäissatunnaisen luvun luomiseen.

Riisi. 3. ANSI X9.17 pseudosatunnaislukugeneraattori

Siirtorekistereissä olevia sekvenssejä käytetään usein virtasalausten rakentamiseen. Takaisinkytkentäsiirtorekisteri koostuu kahdesta osasta: siirtorekisteristä ja takaisinkytkentäfunktiosta, kuten kuvassa 1 on esitetty. 87. Itse siirtorekisteri on sarja bittejä, joiden lukumäärä määrää rekisterin pituuden. Joten jos rekisteri sisältää n bittiä, sen sanotaan olevan n-bittinen siirtorekisteri. Joka kerta kun bitti noudetaan, kaikki siirtorekisterin bitit siirtyvät oikealle yhden kohdan verran, yleensä vähiten merkitseviä bittejä kohti. Siirtorekisterijakso on tuloksena olevan sekvenssin pituus ennen sen toiston alkamista.

Riisi. 87.

Mikä tahansa matemaattinen funktio, joka suorittaa toiminnon biteille, voi toimia palautteena. Yksinkertaisin palautesiirtorekisterityyppi on lineaarinen takaisinkytkentäsiirtorekisteri (LFSR). RFLS:ssä takaisinkytkentä on yksinkertaisesti modulo-2-lisäysoperaatio (XOR) joillekin rekisteribiteille; näiden bittien luetteloa kutsutaan väliottopisteiden sekvenssiksi, kuten kuvassa 1 on esitetty. 88. Joskus tätä mallia kutsutaan Fibonacci-konfiguraatioksi. Takaisinkytkentäsekvenssin yksinkertaisuuden vuoksi LFSR:n analysointiin voidaan käyttää melko edistynyttä matemaattista teoriaa. Joka tapauksessa luodun PSP:n laatu arvioidaan käyttämällä erityistä testisarjaa.

Riisi. 88.

SFLO:t kirjoitetaan polynomien muodossa. Tässä tapauksessa polynomin ensimmäisen elementin potenssi ilmaisee bittien lukumäärän siirtorekisterissä ja polynomin muiden jäsenten tehoeksponentit osoittavat, mitä näytteenottopisteitä käytetään. Joten esimerkiksi merkintä x 4 + x + 1 tarkoittaa, että käytetään neljän elementin rekisteriä, joille bitit bi ja b 0 osallistuvat takaisinkytkennän muodostukseen (kuva 89).

Riisi. 89.4

Tarkastellaan kuvan 1 mukaisen rekisterin toimintaa. 89. Alustamme sen esimerkiksi arvolla 0101 (alkualustus voidaan suorittaa millä tahansa bittisekvenssillä, paitsi vain nollien sekvenssillä, koska tässä tapauksessa palaute muodostaa aina arvon nolla ja rekisteri eivät tuota odotettua kaistanleveyttä). Rekisteri siirtyy siis yhden paikan verran oikealle. Vähiten merkitsevä bitti, yhtä suuri kuin 1, pakotetaan pois rekisteristä ja muodostaa muistin kaistanleveyden ensimmäisen bitin. Ne bitit, jotka olivat paikoissa b ja b 0, lisätään modulo 2 ennen siirtoa ja muodostavat uuden

rekisterin merkittävin osa. Selkeä esimerkki tarkasteltavan LFSR:n toiminnasta on esitetty kuvassa. 90.

Riisi. 90.

Kuten kuvasta voidaan nähdä. 90, rekisterin täyttö kulkee 15:n painon läpi 16 mahdollisesta tilasta (aiemmin päätimme, että kuudestoista tilaa, kun LFSR on 0000, ei voida ottaa huomioon). Tämän jälkeen rekisterin täyttö on jälleen yhtä suuri kuin alkuarvo 0101 ja bittisekvenssin generointi alkaa toistua. Rekisterin lähtösekvenssi on vähiten merkitsevien bittien merkkijono (kuvan 90 vaakaviivaan asti): 101011110001001. Bittisekvenssin kokoa ennen sen toistamista kutsutaan jaksoksi. Tietyn LFSR:n maksimijakson varmistamiseksi (eli rekisterin läpäisemiseksi mahdollisten sisäisten tilojen painon kautta), rekisterin toiminnan määräävän polynomin on oltava primitiivinen modulo 2. Kuten suurilla alkuluvuilla, ei ole olemassa tapa luoda tällaisia ​​polynomeja. Voit vain ottaa polynomin ja tarkistaa, onko se redusoitumaton modulo 2 vai ei. Yleisessä tapauksessa n-asteinen primitiivinen polynomi on redusoitumaton polynomi, joka on x 2 "+1" jakaja, mutta ei ole x d +1:n jakaja kaikille d:lle, jotka ovat luvun 2" -1 jakajia. B. Schneierin taulukossa on annettu taulukko joistakin polynomeista, jotka ovat redusoitumattomia modulo 2.

Yhteenvetona saadusta tiedosta, kun tarkastellaan esimerkkiä LFSR:n toiminnasta (kuva 90), voidaan sanoa, että n-bittinen LFSR voi olla jossakin 2”-1 sisätiloista. Teoreettisesti tällainen rekisteri voi generoida näennäissatunnaisen sekvenssin, jonka jakso on 2 n-1 bittiä. Tällaisia ​​rekistereitä kutsutaan LFSR-rekistereiksi, joilla on maksimijakso. Tuloksena olevaa tulosta kutsutaan t-sekvenssiksi.

Riisi. 7.21.

Suoratoistosalaukset ovat nopeampia kuin lohkosalaukset. Virtasalauksen laitteistototeutus on myös yksinkertaisempaa. Kun meidän on salattava binäärivirrat ja lähetettävä ne vakionopeudella, paras valinta on käyttää stream-salausta. Stream-salauksilla on parempi suoja bittivaurioilta lähetyksen aikana.

Nykyaikaisessa stream-salauksessa jokainen r -bittinen sana pelkässä tekstivirrassa salataan käyttämällä r -bittinen sana avainvirrassa vastaavan luomiseksi r -bittinen sana salatekstivirrassa.

Kertakäyttöinen tyyny on täydellinen salaus. Hän on täydellinen. Ei ole olemassa menetelmää, jonka avulla vastustaja tunnistaisi salatekstin ja selkeän tekstin avaimen tai tilastot. Alkuperäisen ja salatekstin välillä ei ole suhdetta. Toisin sanoen salateksti on todellinen satunnainen bittivirta, vaikka alkuperäisestä tekstistä saadaankin joitakin näytteitä. Eve ei voi murtaa salausta, ellei hän kokeile kaikkia mahdollisia satunnaisia ​​avainvirtoja, jotka olisivat 2n, jos pelkkätekstin koko olisi n-bittiä. Tässä on kuitenkin ongelma. Jotta lähetin ja vastaanotin voivat jakaa kertaluontoisen näppäinlevyn, niiden on muodostettava yhteys aina, kun he haluavat vaihtaa tietoja. Heidän täytyy jotenkin sopia satunnaisesta avaimesta. Joten tämä täydellinen ja ihanteellinen salaus on erittäin vaikea toteuttaa.

Esimerkki 7.17

Mikä on salatekstin muoto käytettäessä kertalukusalausta seuraavissa tapauksissa?

A. Lähdeteksti koostuu n nollasta.

b. Lähdeteksti koostuu n yksiköstä.

V. Lähdeteksti koostuu vuorotellen nollista ja ykkösistä.

d. Lähdeteksti on satunnainen bittijono.

Ratkaisu

a. Koska , niin salatekstivirta vastaa avainvirtaa. Jos avain on satunnainen, myös salateksti on satunnainen. Alkuperäisen tekstin osia ei tallenneta salatekstiin.

b. Koska , jossa on salatekstivirran komplementti on avainvirran komplementti. Jos avainvirta on satunnainen, myös salateksti on satunnainen; osia alkuperäisestä tekstistä ei tallenneta salatekstiin.

c. Tässä tapauksessa jokainen salatekstivirran bitti on joko sama kuin avainvirrassa tai sen komplementti. Siksi tulos on myös satunnainen, jos avainvirta on satunnainen.

d. Tässä tapauksessa salateksti on selvästi satunnainen, koska XOR-operaation suorittaminen kahdelle satunnaiselle bitille johtaa satunnaiseen bittivirtaan.

Palautevuororekisteri

Yksi parannus kertakäyttöiseen näppäimistöön on (FSR - Feedback Shift Register). FSR voidaan toteuttaa joko ohjelmistolla tai laitteistolla, mutta yksinkertaisuuden vuoksi harkitsemme laitteistototeutusta. Palautevuororekisteri sisältää vaihtorekisteri ja palautetoiminnot, kuten kuvassa näkyy. 7.23.

Siirtorekisteri on m solun sekvenssi b 0 - b m-1, jossa jokainen solu on suunniteltu tallentamaan yksi bitti. Soluja käsitellään n-bittisenä sanana, jota kutsutaan alussa "siemenarvoksi" tai lähde. Aina kun bitti on tulostettava (esimerkiksi signaalista tiettynä aikana), jokaista bittiä siirretään yhden solun verran oikealle. Tämä tarkoittaa, että kunkin solun arvo on määritetty oikeanpuoleiselle viereiselle solulle ja se ottaa vasemman solun arvon. Oikeanpuoleista solua b 0 pidetään ulostulona ja se antaa lähtöarvon (k i ). Vasemmanpuoleisin solu, b m-1, saa arvonsa palautefunktiotietojen arvon mukaan. Merkitään funktion lähtö palautetiedolla b m . Palautetietofunktio määrittää, mitä arvoja soluilla on laskea b m . Palauteinformaation siirtorekisteri voi olla lineaarinen tai epälineaarinen.

Linear Feedback Shift Register (LFSR). Oletetaan, että b m on lineaarinen funktio b 0, b 1,…..., b m-1, jolle

Lineaarinen takaisinkytkentäsiirtorekisteri toimii binäärinumeroilla, joten kerto- ja yhteenlasku ovat GF(2)-kentässä, joten C i:n arvo on joko 1 tai 0, mutta C 0:n on oltava 1, jotta ulostuloon saadaan palauteinformaatiota. Lisäystoiminto on EXCLUSIVE TAI -toiminto. Toisin sanoen,

Esimerkki 7.18

Rakennetaan lineaarinen takaisinkytkentäsiirtorekisteri, jossa on 5 solua, jossa .

Ratkaisu

Jos C i = 0, b i ei näytä roolia b m:n laskennassa, tämä tarkoittaa, että b i ei liity palautetietofunktioon. Jos c i = 1, b i sisällytetään b m:n laskelmaan. Tässä esimerkissä c 1 ja c 3 ovat nollia, mikä tarkoittaa, että meillä on vain kolme yhteyttä. Kuva 7.24 esittää lineaarisen takaisinkytkennän siirtorekisterin piiriä.

Esimerkki 7.19

Rakennetaan lineaarinen takaisinkytkentäsiirtorekisteri, jossa on 4 solua, jossa . Näytä rekisteriarvo 20:n jälkeen toiminnot (vuorot), jos alkuperäinen arvo on (0001) 2 .

Ratkaisu

Kuva 7.25 esittää lineaarisen suljetun silmukan siirtorekisterin suunnittelua ja käyttöä salaukseen.

Taulukko 7.6. näyttää avainvirran arvon. Jokaiselle siirtymälle lasketaan b 4:n ensimmäinen arvo ja sitten kutakin bittiä siirretään yhden solun verran oikealle.

Huomaa, että avainvirta on 1000100110101111 1001……. Se näyttää ensi silmäyksellä satunnaiselta sekvenssiltä, ​​mutta jos tarkastelemme suurta määrää tapahtumia (siirtymiä), voimme nähdä, että sekvenssit ovat jaksollisia. Tämä 15 bitin toisto on esitetty alla.

Virta-avain luodaan käyttämällä lineaarista takaisinkytkentäsiirtorekisteriä näennäissatunnainen sekvenssi, jossa N pituiset sekvenssit toistuvat. Virtaus on säännöllistä. Se riippuu generaattoripiiristä ja lähtötiedoista ja voi olla enintään 2 m – 1. Jokainen piiri tuottaa m-bittisiä sekvenssejä, jotka vaihtelevat niistä, jotka sisältävät kaikki nollat, niihin, jotka sisältävät kaikki ykköset. Kuitenkin, jos alkuperäinen sekvenssi on kaikki nollia, tulos on hyödytön - alkuperäinen teksti olisi kaikkien nollien virta. Siksi tällainen alkusekvenssi on suljettu pois.