Lineaarinen palautevaihtorekisteri

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 5. lokakuuta 2016 tarkistetusta versiosta . tarkastukset vaativat 44 muokkausta .

Lineaarinen palautesiirtorekisteri ( LFSR ) on bittisanojen siirtorekisteri , jossa syötetyn liukuvan) bitin arvo on yhtä suuri kuin lineaarinen Boolen funktio rekisterin jäljellä olevien bittien arvoista ennen siirtoa . Se voidaan järjestää sekä ohjelmiston että laitteiston mukaan. Sitä käytetään pseudosatunnaisten bittisekvenssien luomiseen , jota käytetään erityisesti kryptografiassa [1] . Siirtorekisteri, jossa on siirtopalaute , toimii samalla periaatteella. yleinen palautemuutosrekisteri .

Kuvaus

Lineaarisen takaisinkytkennän siirtorekisterissä ( RSLOS ) on kaksi osaa (moduulia):

todellinen siirtorekisteri;
takaisinkytkentäpiiri (tai aliohjelma), joka laskee lisätyn bitin arvon.

Rekisteri koostuu toiminnallisista muistisoluista (yhden tai useamman konesanan bitit), joista jokainen tallentaa yhden bitin nykyisen tilan (arvon). Solujen lukumäärää kutsutaan rekisterin pituudeksi. Bitit (solut) numeroidaan yleensä numeroilla , solun sisältö on merkitty . Uuden bitin arvo määritetään ennen bittisiirtoa rekisterissä ja vasta sen jälkeen, kun siirto on kirjoitettu soluun , ja seuraava generoitu bitti erotetaan solusta. $L$ $i = 0,\;1,\;\pisteet,\;L-1$ $i$ $S_{(L-1)-i}$ $S_L$ $0$ $L-1$

LFSR:n palautefunktio on lineaarinen Boolen funktio rekisterin kaikkien tai joidenkin bittien arvojen arvoista. Funktio kertoo rekisteribitit kertoimilla , missä . Kertoimien määrä on sama kuin rekisteribittien määrä . Kertoimet ottavat arvot , ja viimeinen kerroin on yhtä suuri kuin , koska LFSR annetaan ominaispolynomilla asteella . Modulo 2 -lisäys ("XOR"-operaatio, jota kaavoissa merkitään symbolilla " ") tai sen looginen käännös " XNOR " ovat lineaarisia Boolen funktioita ja niitä käytetään useimmiten tällaisissa rekistereissä [2] . Tässä tapauksessa takaisinkytkentäfunktion muuttujina olevia bittejä kutsutaan tapeiksi ja itse rekisteriä Fibonacci - konfiguraatioksi [3] . $c_{i}$ $i = 1, \; 2,\; \pisteet,\; L$ $L$ $c_{i}$ $\{ 0, \; yksi \}$ $c_L$ $c_L = 1$ $L$ $\oplus$

Rekisterin ohjaus laitteistototeutuksissa suoritetaan käyttämällä siirtopulssia (muuten kutsutaan kelloksi tai kellopulssiksi ) kaikkiin soluihin. Rekisterinhallinta ohjelmistototeutuksissa suoritetaan silmukalla . Silmukan jokaisessa iteraatiossa palautefunktio lasketaan ja sanassa suoritetaan bittisiirto .

Kuinka se toimii

Jokaisen kellojakson aikana lineaarinen takaisinkytkentäsiirtorekisteri suorittaa seuraavat toiminnot:

solussa oleva bitti luetaan ; tämä bitti on tulossekvenssin seuraava bitti; $L-1$
palautefunktio laskee solulle uuden arvon käyttämällä solujen nykyisiä arvoja; $0$
kunkin solun sisältö siirretään seuraavaan soluun , jossa ; $i$ $i+1$ $i = 0,\;1,\;\pisteet,\;L-2$
solu kirjoitetaan takaisinkytkentäfunktion aiemmin laskemaan bittiin. $0$

Jos takaisinkytkentätoiminto suorittaa loogisen toiminnon " XOR " (poissulkeva OR), bittien (solujen) arvot voidaan laskea seuraavilla kaavoilla [4] :

$S_L=(c_1*S_{L-1})\oplus(c_2*S_{L-2})\oplus\dots\oplus(c_L*S_{0})$

$S_{L+1}=(c_1*S_{L})\oplus(c_2*S_{L-1})\oplus\dots\oplus(c_L*S_{1})$ $...$ $S_{L+j-1}=(c_1*S_{L+j-2})\oplus(c_2*S_{L+j-3})\oplus\dots\oplus(c_L*S_{j-1} )$

Ominaisuudet

Jaksoisuus

Siirtorekisterin jakso on tuloksena olevan sekvenssin minimipituus ennen kuin se alkaa toistua. Pituudella LFSR on alkutilat, jotka määrittelevät solujen bittien arvot. Näistä tilat ovat nollasta poikkeavat, joten generoidun sekvenssin jakso on . Generoidun sekvenssin jakso on maksimi ja yhtä suuri kuin , jos takaisinkytkentäpolynomi (tai ominaispolynomi) kentän yli on primitiivinen . Tätä varten on välttämätöntä (mutta ei riittävää) täyttää seuraavat 2 ehtoa: $L$ $2^{{L}}$ $2^{L}-1$ $T\leq2^{L}-1$ $2^{L}-1$ $C(x)=c_{L}x^{L}+c_{L-1}x^{L-1}+\dots +c_{1}x+1$ ${\mathrm {GF}}(2)$

parillinen määrä hanat;
napautusnumerot, kaikki yhdessä, ei pareittain, ovat koprime .

Kaikkien mahdollisten primitiivisten polynomien lukumäärä on , missä on Euler-funktio [5] . Tällaisen polynomin antamaa rekisteriä kutsutaan maksimijakson siirtorekisteriksi (tai näennäissatunnaisten sekvenssien generaattoriksi ), ja generoituja sekvenssejä kutsutaan maksimijaksojonoiksi (tai M-sekvenssiksi ) [4] [6] . $\tfrac{\phi(2^L-1)}{L}$ $\phi$

Lineaarinen monimutkaisuus

Äärettömän binäärisekvenssin lineaarinen monimutkaisuus on luku, joka määritellään seuraavasti: $S=(S_0,\;S_1,\;S_2,\;\pisteet)$ $L(S)$

jos on nolla sekvenssi, niin ; $S=(0,\;0,\;0,\;\pisteet)$ $L(S) = 0$
jos ei ole LFSR, joka tuottaa , niin ; $S$ $L(S) = \infty$
muuten yhtä suuri kuin lyhimmän LFSR:n pituus, joka tuottaa . $L(S)$ $S$

Äärillisen binäärisekvenssin lineaarinen monimutkaisuus on luku , joka on yhtä suuri kuin tämän sekvenssin muodostavan lyhimmän LFSR:n pituus. $S_n=(S_0,\;S_1,\;\pisteet,\;S_n)$ $L(S_n)$

Lineaarisen takaisinkytkennän siirtorekisterin lineaarinen monimutkaisuus osoittaa, kuinka lähellä generoitu sekvenssi on satunnaista . Tehokas algoritmi äärellisen binäärijonon lineaarisen monimutkaisuuden määrittämiseen on Berlekamp-Massey-algoritmi .

Korrelaatioriippumattomuus

Yrittäessään saada generoidusta sekvenssistä suuri lineaarinen monimutkaisuus kryptografit yhdistävät epälineaarisesti useiden siirtorekisterien lähdöt. Tässä tapauksessa yksi tai useampi lähtösekvenssi (tai jopa yksittäisten LFSR:ien ulostulot) voidaan yhdistää yhteisellä virralla ja avata kryptanalyytikon toimesta . Tällaiseen haavoittuvuuteen perustuvaa hakkerointia kutsutaan korrelaatiohyökkäykseksi . Tällaisen hakkeroinnin pääideana on löytää korrelaatio generaattorin lähdön ja sen komponenttien ulostulojen välillä. Sitten ulostulosekvenssiä tarkkailemalla voidaan saada tietoa näistä välituloista ja siten hakkeroida generaattori. Thomas Siegenthaler on osoittanut, että korrelaatioriippumattomuus on mahdollista määritellä tarkasti ja että korrelaatioriippumattomuuden ja lineaarisen kompleksisuuden välillä on kompromissi [7] .

Ohjelmiston toteutus

RSLOS:n ohjelmistototeutukset ovat melko hitaita ja toimivat nopeammin, jos ne on kirjoitettu assemblerillä . Yksi ratkaisuista on 16 RSLOS: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 jokainen sanan bitti viittaa omaan LFSR:ään. Koska käytetään samaa määrää väliottosarjoja, tämä voi parantaa generaattorin suorituskykyä huomattavasti [3] .

Fibonacci-kokoonpano

Harkitse 32-bittistä siirtorekisteriä. Sitä varten on pakosarja . 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 . Tällaisen rekisterin koodi C:ssä on seuraava: $\left(32,\;31,\;30,\;28,\;26,\;1\oikea)$ $2^{ 32 }-1$

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

Kuten Fibonacci-konfiguraatiossa, takaisinkytkentäpiiri on joukko väliottobittien XOR-operaatioita generaattorin lähdön kanssa, mutta bittien järjestys rekisterissä on käänteinen: -th bitti on tulo ja -th bitti . on lähtö . Lisäyksen tulos kirjoitetaan seuraavaan soluun ja uusi lähtöbitti -th. Eli jos generoitu bitti on yhtä suuri kuin nolla, niin kaikki solujen bitit siirretään oikealle ilman muutoksia, jos generoitu bitti on yhtä suuri, tapbitit muuttavat arvonsa päinvastaiseksi ja kaikki bitit siirtyvät oikealle. Sekä Fibonacci-konfiguraatio että samanpituinen Galois -konfiguraatio generoivat samat sekvenssit, mutta ajallisesti siirtyneet toisistaan (tässä tapauksessa rekisterien sisäiset tilat voivat vaihdella) [8] . $L-1$ $0$ $L-1$

Tällä generaattorilla ei ole suurempaa salausvoimakkuutta , mutta se antaa suorituskyvyn lisäyksen: kaikki rinnakkaisuuden kautta suoritettavat XOR-operaatiot voidaan suorittaa yhdessä operaatiossa, eikä peräkkäin peräkkäin, kuten Fibonacci-konfiguraatiossa. Tämä järjestelmä parantaa myös laitteiston toteutusta.

C:n 32-bittisen siirtorekisterin koodi on seuraava:

int LFSR_Galois ( mitätön ) { // polynomille 0x80000057, käänteinen 0xea000001 staattinen etumerkitön pitkä S = 0x00000001 ; if ( S & 0x00000001 ) { S = (( S ^ 0x80000057 ) >> 1 ) | 0x80000000 ; paluu 1 ;} else { S >>= 1 ; palauta 0 ;} }

On syytä huomata, että kiinteän määrän funktiokutsuja sisältävä silmukka LFSR_GaloisGalois-kokoonpanossa on noin 2 kertaa nopeampi kuin LFSR_FibonacciFibonacci-kokoonpanon funktio ( MS VS 2010 -kääntäjä Intel Core i5 :ssä ).

Esimerkki luodusta sarjasta

Fibonacci-kokoonpano

Olkoon LFSR annettu ominaispolynomilla . Tämä tarkoittaa, että tapbitit ovat 2. ja 0., ja polynomikaavan yksikkö tarkoittaa, että 0. bitti on syöte. Palautetoiminnolla on muoto . Oletetaan, että siirtorekisterin alkutila oli sekvenssi . Rekisterin muut tilat näkyvät alla olevassa taulukossa: $x^{3}+x+1$ $S_j=S_{j-1}\oplus S_{j-3}$ $\vasen[0,\;0,\;1\oikea]$

Vaiheen numero	Osavaltio	Bitti luotu
0	$\vasen[0,\;0,\;1\oikea]$	yksi
yksi	$\vasen[1,\;0,\;0\oikea]$	0
2	$\vasen[1,\;1,\;0\oikea]$	0
3	$\vasen[1,\;1,\;1\oikea]$	yksi
neljä	$\vasen[0,\;1,\;1\oikea]$	yksi
5	$\vasen[1,\;0,\;1\oikea]$	yksi
6	$\vasen[0,\;1,\;0\oikea]$	0
7	$\vasen[0,\;0,\;1\oikea]$	yksi

Koska sisäinen tila seitsemännessä vaiheessa palasi alkuperäiseen tilaan, niin seuraavasta vaiheesta alkaen bitit toistetaan. Toisin sanoen generoitu sekvenssi on seuraava: (bittien järjestys sekvenssissä vastaa järjestystä, jossa LFSR generoi ne). Näin ollen sekvenssin jakso on 7, eli suurin mahdollinen arvo, joka tapahtui annetun polynomin primitiivisyydestä johtuen. $\left[1,\;0,\;0,\;1,\;1,\;1,\;0,\;1\;...\right]$

Galois-kokoonpano

Otetaan sama ominaispolynomi, eli , . Vain 1. bitti lisätään lähtöbittiin. Alkutila on sama. Muut rekisterin tilat: $c_3=c_1=1$ $c_2=0$

Vaiheen numero	Osavaltio	Bitti luotu
0	$\vasen[0,\;0,\;1\oikea]$	yksi
yksi	$\vasen[1,\;0,\;1\oikea]$	yksi
2	$\vasen[1,\;1,\;1\oikea]$	yksi
3	$\vasen[1,\;1,\;0\oikea]$	0
neljä	$\vasen[0,\;1,\;1\oikea]$	yksi
5	$\vasen[1,\;0,\;0\oikea]$	0
6	$\vasen[0,\;1,\;0\oikea]$	0
7	$\vasen[0,\;0,\;1\oikea]$	yksi

Rekisterin sisäinen tila seitsemännessä vaiheessa palasi alkuperäiseen tilaansa, joten sen jakso on myös yhtä suuri kuin 7. Toisin kuin Fibonacci-konfiguraatiossa, rekisterin sisäiset tilat osoittautuivat erilaisiksi, mutta generoitu sekvenssi on sama , siirretty vain 4 jaksolla : (sekvenssin bittien järjestys vastaa niiden LFSR:n luomisjärjestystä). $\left[1,\;1,\;1,\;0,\;1,\;0,\;0,\;1,\;...\right]$

LFSR:n matriisiesitys

englanninkielisen artikkelin osio

Alkuperäisten polynomien luominen

Primitiivisen polynomin laskeminen kentän yli on melko monimutkainen matemaattinen ongelma: primitiivisen astepolynomin muodostamiseksi sinun on tiedettävä luvun tekijät . On helpompi valita satunnaisesti polynomi ja testata sen primitiivisyyttä [3] . Toinen tapa on käyttää valmiita taulukoita, joissa luetellaan väliottosekvenssien lukumäärät, jotka tarjoavat generaattorin maksimijakson. Alla on taulukko primitiivisistä polynomeista kentän yli siirtorekistereille, joiden enimmäisjakso on 19 bittiä [5] . On syytä ottaa huomioon, että minkä tahansa pituisella generaattorilla voi olla enemmän kuin yksi primitiivipolynomi niiden ominaisuuksien mukaan . Täydellinen luettelo 4-32 bitin pituisista rekistereistä löytyy täältä . ${\mathrm {GF}}(2)$ $k$ $2^{k}-1$ ${\mathrm {GF}}(2)$

palasia, $n$	Primitiivinen polynomi	kausi, $2^{n}-1$	Primitiivisten polynomien lukumäärä
2	$x^{2}+x+1$	3	yksi
3	$x^3+x^2+1$	7	2
neljä	$x^4+x^3+1$	viisitoista	2
5	$x^{5}+x^{3}+1$	31	6
6	$x^{6}+x^{5}+1$	63	6
7	$x^{ 7 }+x^{ 6 }+1$	127	kahdeksantoista
kahdeksan	$x^{8}+x^{6}+x^{5}+x^{4}+1$	255	16
9	$x^{9}+x^{5}+1$	511	48
kymmenen	$x^{10}+x^{7}+1$	1023	60
yksitoista	$x^{11}+x^{9}+1$	2047	176
12	$x^{12}+x^{11}+x^{10}+x^{4}+1$	4095	144
13	$x^{13}+x^{12}+x^{11}+x^{8}+1$	8191	630
neljätoista	$x^{14}+x^{13}+x^{12}+x^{2}+1$	16383	756
viisitoista	$x^{15}+x^{14}+1$	32767	1800
16	$x^{16}+x^{14}+x^{13}+x^{11}+1$	65535	2048
17	$x^{17}+x^{14}+1$	131071	7710
kahdeksantoista	$x^{18}+x^{11}+1$	262143	7776
19	$x^{19}+x^{18}+x^{17}+x^{14}+1$	524287	27594
20-168	[yksi]
2-786, 1024, 2048, 4096	[2]

Edut ja haitat

Edut

LFSR:n perusteella luotujen salausalgoritmien korkea suorituskyky (esimerkiksi virtasalaukset );
vain yksinkertaisimpien yhteen- ja kertolaskuoperaatioiden käyttö , jotka on toteutettu laitteistossa lähes kaikissa tietokonelaitteissa;
hyvät kryptografiset ominaisuudet (LFSR:t voivat tuottaa pitkän ajanjakson sekvenssejä hyvillä tilastollisilla ominaisuuksilla);
rakenteensa ansiosta LFSR:t on helppo analysoida algebrallisilla menetelmillä.

Haitat

Yksi LFSR:n suurimmista ongelmista on, että niiden ohjelmistototeutus on erittäin tehoton: harvat palautepolynomit on vältettävä, koska ne johtavat helpompaan hakkerointiin korrelaatiohyökkäyksellä ja tiheät polynomit ovat erittäin hitaita laskea. Siksi tällaisen generaattorin ohjelmistototeutus ei ole nopeampi kuin DES -toteutus .
Rekisterin lähdön sekvenssin lineaarisuus mahdollistaa takaisinkytkentäpolynomin yksiselitteisen määrittämisen sarjabittien yli käyttämällä Berlekamp-Massey- algoritmia tai Euclid-algoritmia [3] [4] . $C(x)$ $2L$
Algebrallisten menetelmien analyysin suhteellinen helppous ei ainoastaan helpota kehitystä, vaan lisää myös mahdollisuuksia rikkoa LFSR-pohjainen generaattori.

Tapoja parantaa luotujen sekvenssien kryptografista vahvuutta

Generaattorit useilla vuororekistereillä

Tämän tyyppinen generaattori koostuu useista lineaarisista takaisinkytkentäsiirtorekistereistä, jotka generoivat vastaavasti bittejä. Seuraavaksi generoidut bitit muunnetaan jollain Boolen funktiolla . On huomattava, että tämän tyyppisillä generaattoreilla rekisteripituudet , , ovat suhteellisen tärkeimmät toisiinsa nähden. $x_{1,i},\;x_{2,i},\;\dots,\;x_{M,i}$ $f(x_{1,i},\;x_{2,i},\;\pisteet,\;x_{M,i})$ $L_i$ $i=1,\;2,\;\pisteet,\;M$

Tämän generaattorin jakso on , jossa on solujen kokonaismäärä. Siksi usean LFSR:n käyttö lisää generoidun sekvenssin jaksoa yhteen rekisteriin verrattuna, mikä lisää generaattorin kryptografista vahvuutta . Se lisää myös lineaarista monimutkaisuutta tai lyhimmän rekisterin pituutta, joka vastaa tiettyä generaattoria. 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 [4] . $T=(2^{L_1}-1)\cdot(2^{L_2}-1)\cdots(2^{L_M}-1)\lesssim2^L$ $L=\sum\limits_{i=1}^M L_i$

Generaattorit epälineaarisilla muunnoksilla

Tällaisen generaattorin lohkokaavio ei eroa edellisen generaattorin kaaviosta. Suurin ero on, että muunnoslaite annetaan epälineaarisella Boolen funktiolla . Sellaisena funktiona otetaan esimerkiksi Zhegalkin-polynomi ( Zhegalkin- lauseen mukaan mikä tahansa Boolen funktio voidaan yksilöllisesti esittää Zhegalkin-polynomilla). $f(x_1, x_2, \pisteet, x_M)$

Epälineaarinen generaattori voidaan toteuttaa myös siirtorekisteriin, jossa on epälineaarinen takaisinkytkentä . Se voi antaa muunnelmia maksimijakson sekvensseistä , mikä on enemmän kuin LFSR:n [5] . $2^{2^{L-1}-L}$

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 tunneta algoritmia, joka palauttaisi alkuperäiset tilat.

Tätä menetelmää käytetään esimerkiksi Geff-generaattorissa ja yleistetyssä Geff-generaattorissa, mutta tällaiset generaattorit voidaan hakkeroida korrelaatioanalyysillä [7] .

Oskillaattorit eri siirtorekisteri-ajoituksilla

Stop-and-go generaattori

Stop-and-Go- generaattori ( eng. Stop-and-Go , Both-Piper ) käyttää LFSR-1:n lähtöä ohjaamaan LFSR-2:n kellotaajuutta , jotta LFSR-2 muuttaa tilaansa jossain vaiheessa vain, jos LFSR-1:n lähtö tuolloin oli yhtä suuri kuin yksi. Tämä kaavio ei vastustanut korrelaation avautumista [3] . $t_{i}$ $t_{i-1}$

Salauksen vahvuuden lisäämiseksi ehdotettiin lomitettua stop-go-generaattoria . Se käyttää kolmea eripituista siirtorekisteriä. Tässä LFOS-1 ohjaa 2. ja 3. rekisterin kellotaajuutta, eli LFSR-2 muuttaa tilaansa, kun LFSR-1-lähtö on yhtä suuri kuin yksi, ja LFSR-3 - kun LFSR-1-lähtö on yhtä suuri kuin nolla. Generaattorin lähtö on RLOS-2:n ja RLLS-3 :n lähdöistä kahden modulo -toiminto. Tällä generaattorilla on suuri jakso ja suuri lineaarinen monimutkaisuus. On olemassa menetelmä RLOS-1:n korrelaatioiden avaamiseksi, mutta tämä ei heikennä suuresti generaattorin kryptografisia ominaisuuksia.

Monimutkaisempaa kellojärjestelmää käytetään kaksisuuntaisessa stop-and-go-generaattorissa , joka käyttää kahta samanpituista siirtorekisteriä. Jos LFSR-1:n lähtö tietyllä ajanhetkellä on yhtä suuri kuin nolla ja ajanhetkellä yksi, niin LFSR-2:ta ei kellotata tällä hetkellä . Jos LFSR-2:n lähtö ajanhetkellä on nolla ja ajanhetkellä yksi ja jos tämä rekisteri on kellotettu ajanhetkellä , niin LFSR-1 on samalla hetkellä ei kellotettu. Tämän piirin lineaarinen monimutkaisuus on suunnilleen yhtä suuri kuin generoidun sekvenssin jakso. $t_{i-1}$ $t_{i-2}$ $t_{i}$ $t_{i-1}$ $t_{i-2}$ $t_{i}$

Itsedesimoiva generaattori

Itsedesimaalit oskillaattorit ohjaavat omaa taajuuttaan . Tällaisia generaattoreita on kahdenlaisia. Ensimmäisen ehdotti Rainer Rüppel . Se koostuu siirtorekisteristä ja lineaarisesta takaisinkytkentäpiiristä, joka kellottaa rekisterin siirtorekisterin ulostulon perusteella. Jos LFSR-lähtö on yhtä suuri kuin yksi, rekisteriä kellotetaan yhdellä taajuudella ja jos lähtö on nolla, niin toisella. Toista tyyppiä ehdottivat Bill Chambers ja Dieter Kollman . Takaisinkytkentäpiiri ei vastaanota itse lähtösignaalia, vaan tiettyjen LFSR-bittien XOR-toiminnan tulosta.

On myös kutistuvia ja itsekutistuvia generaattoreita . _ _ _ _ Ne ovat melko uusia, eikä kaikkia niiden ominaisuuksia ole tutkittu hyvin. Ensimmäinen käyttää kahta LFSR:ää. Jos generaattoriin syötetään kellopulssi ja RLOS-1:n lähtö on yksi, generaattorin ulostulo on RLLS-2:n lähtö. Muussa tapauksessa, kun kellopulssia käytetään, molemmat bitit nollataan ja kello alkaa alusta. Toisessa generaattorissa kahden rekisterin ulostulojen tarkistamisen sijaan 0 tai 1 tarkistetaan yhden rekisterin 2 bittiä.

Desimoitu generaattori voidaan hakkeroida, jos palautepolynomit desimoidaan. Lisäksi sen tuotantonopeus ei ole vakio. Itsedesimoiva generaattori tarvitsee noin 2 kertaa vähemmän muistia kuin ensimmäinen, mutta se toimii 2 kertaa hitaammin [7] .

Moninopeusoskillaattori sisätuotteella

Tämä generaattori käyttää kahta siirtorekisteriä RSLOS-1 ja RSLOS-2. RSLOS-2:n kellotaajuus on useita kertoja suurempi kuin RSLOS-1:n. Tietyt näiden rekisterien bitit kerrotaan keskenään JA -operaatiolla . Kertolaskujen tulokset lasketaan yhteen XOR-operaatiolla ja saadaan tulossekvenssi. Tällä generaattorilla on korkea lineaarinen monimutkaisuus ja hyvät tilastolliset ominaisuudet. Sen tila voidaan kuitenkin määrittää pituus , jossa ja ovat LFSR-1:n ja LFSR-2:n pituudet, ja on niiden kellotaajuuksien suhde. $d$ $L_1 + L_2 + \log_2{d}$ $L_{1}$ $L_{2}$ $d$

Gollmann Cascade

Tämä piiri on parannettu versio stop-go-generaattorista. Se koostuu sarjasta LFSR:itä, joiden kunkin ajoitusta ohjaa edellinen LFSR. Jos LFSR-1:n lähtö hetkellä on 1, niin LFSR-2 kellotetaan. Jos LFSR-2:n lähtö hetkellä on 1, niin LFSR-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 kuin , niin LFSR-järjestelmän jakso on , ja lineaarinen monimutkaisuus on [7] . $t_{i}$ $t_{i}$ $L$ $M$ $(2^L - 1)^M$ $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 ne ovat alttiita hyökkäykselle nimeltä lock - in , kun kryptanalyytikko palauttaa ensin kaskadin viimeisen rekisterin syöttösekvenssin, katkaisee koko kaskadin rekisteri kerrallaan. Rekistereiden määrän kasvaessa luotu sekvenssi lähestyy satunnaista , joten on parempi käyttää enemmän pienipituisia LFSR:itä kuin vähemmän pitkiä LFSR:itä. $M$

Enemmistögeneraattorit

Enemmistö- (tai kynnys )generaattori koostuu suuresta määrästä siirtorekistereitä, joiden lähdöt menevät majorisointifunktion määrittelemään laitteeseen, esimerkiksi enemmistöelementti . Tämän generaattorin erikoisuus on, että jokaisella siirtorekisterillä on oma kellobittinsä , , jotka ovat enemmistöfunktion muuttujia. Esimerkiksi kolmelle rekisterille tällaisen funktion muoto on . Vain niitä rekistereitä siirretään, joiden kellobitit ovat yhtä suuret kuin arvo , eli rekisterien siirtyminen tapahtuu suurimmalla osalla tällaisten bittien arvoista: 0 tai 1. $a_{i}$ $i=1,\;2,\;\pisteet,\;M$ $b(t)=(a_{1}\land a_{2})\oplus (a_{1}\land a_{3})\oplus (a_{2}\land a_{3})$ $b(t)$

Siten saamme generaattorin, jossa on vaihteleva määrä LFSR:itä. Sen lineaarinen kompleksisuus on , missä on -: nnen rekisterin pituus [7] . Tällaisen generaattorin haittoja ovat suoran numeroinnin ja korrelaation avaamisen mahdollisuus (jokainen lähtöbitti antaa jonkin verran tietoa siirtorekisterin tilasta, tarkalleen ottaen - 0,189 bittiä). $L(S) = \sum\limits_{i,j=1}^M L_iL_j$ $L_i$ $i$

Samanlaisia generaattoreita käytetään A5 - salausalgoritmeissa (A5/1, A5/2).

Sovellus

Lineaariset takaisinkytkentäsiirtorekisterit voidaan toteuttaa laitteistossa, jolloin niitä voidaan käyttää nopeaan näennäissatunnaisten sekvenssien generointiin , kuten suorasekvenssihajaspektrin tai kohinasignaalien generointiin [9] .

Käytä kryptografiassa

Lineaarisia takaisinkytkentäisiä siirtorekistereitä on pitkään käytetty näennäissatunnaisten sekvenssigeneraattoreina stream -salauksille (erityisesti sotilaallisessa kryptografiassa ). LFSR on kuitenkin lineaarinen järjestelmä, ja joissain tapauksissa se voidaan helposti hakkeroida. Kryptanalyytikko voi esimerkiksi siepata osan salatekstistä ja käyttää sitä edellä mainittua Berlekamp-Massey-algoritmia käyttäen rekonstruoidakseen vähimmäiskoon LFSR:n, joka jäljittelee alkuperäistä LFSR:ää. Sitten siepattu teksti voidaan syöttää vastaanotettuun rekisteriin ja purkaa sen salaus. Menetelmät LFSR:ään perustuvien virtasalausten kryptografisen vahvuuden lisäämiseksi on esitetty edellä .

Lineaarinen takaisinkytkentäsiirtorekisteri on pohjana GSM -standardissa käytetyille virtasalauksille, kuten A5/1 ja A5/2 , sekä Bluetoothissa käytettävälle E0 -salaukselle . A5/2-salaus on rikki, ja A5/1- ja E0-salaukset ovat vakavasti viallisia [10] [11] .

Lineaarinen takaisinkytkentäsiirtorekisteri liittyy läheisesti lineaariseen kongruenssigeneraattoriin [12] .

Käytä laskureina

Luodun LFSR-sekvenssin taajuudella voit käyttää sitä kellojakajana tai laskurina [13] . Tällaiseen oskillaattoriin perustuvalla laskurilla on yksinkertaistettu takaisinkytkentäpiiri, toisin kuin perinteiset binääri- tai harmaakoodilaskurit , ja siksi se voi toimia suurilla kellotaajuuksilla. Sinun on kuitenkin varmistettava, että tällainen laskuri ei koskaan mene nollatilaan.

Digitaalisten laitteiden testaus

Toisin kuin perinteinen laskuri, LFSR ei siirry tilasta toiseen binäärilaskennan järjestyksessä, mikä mahdollistaa sen käytön testisignaalin muodostamiseen, kun logiikkapiireissä havaitaan virheitä [6] .

Lineaarisia takaisinkytkennän siirtorekistereitä käytetään myös sisäänrakennetussa itsetestissä ( sisäänrakennettu itsetesti , BIST ) logiikkapiireissä signeeraukseen ( bittivirheiden havaitsemiseen). Tällaisia järjestelmiä käytetään mikropiirilähtöjen rajallisen määrän vuoksi (kaikkia välibittiarvoja ei voida soveltaa lähtöön). BIST-järjestelmä koostuu kolmesta lohkosta: testisekvenssigeneraattorista ja allekirjoitusanalysaattorista, jotka on rakennettu LFSR:n pohjalta, sekä testiohjaimesta. Analysaattorin siirtorekisteri "pakkaa" testisekvenssin piirin tuloksen allekirjoitukseksi ja jatkaa toimintaansa, kunnes kaikki sen bitit, lukuun ottamatta nollaa, ovat yhtä suuret kuin nolla, eli tilaan . LFSR:n ohella on binäärilaskuri, joka laskee jaksojen lukumäärän testireaktion pakkauksen päättymisen jälkeen. Jos rekisterin alkutila vastasi referenssiallekirjoitusta (virheettömän piirin allekirjoitus), niin laskurin lukema vastaa virheellisen bitin numeroa [14] [15] . $\left[1,\;0,\;0,\;...,\;0\oikea]$

Koska LFSR suorittaa häviöllisen pakkaamisen, on todennäköistä, että virheellisissä järjestelyissä tuloksena oleva allekirjoitus on sama kuin viite. Tämä voidaan välttää käyttämällä allekirjoitusanalysaattoria, jossa on useita tuloja.

Scrambling

Lineaarisia takaisinkytkentäisiä siirtorekistereitä käytetään sekoitusprosessissa digitaalisen virran tuottamiseksi satunnaissekvenssiominaisuuksilla . Maksimipituinen näennäissatunnainen LFSR-sekvenssi lisätään modulo 2 lähetettyyn bittivirtaan, ja sekvenssi generoidaan samalla nopeudella kuin tiedonsiirto. Jotkut sekoitusta käyttävät järjestelmät ja tekniikat ovat:

ATSC [16] ;
DAB ;
DVB-T ;
NICAM ;
CDMA ;
100BASE-T2 Fast Ethernet ;
1000BASE-T Gigabit Ethernet ;
PCI Express 3.0 ;
SATA ;
Serial Attached SCSI ;
USB 3.0 ;
IEEE 802.11a ;
Bluetooth L.E.

Katso myös

Muistiinpanot

↑ B. Sklyar, 2007 .
↑ Lineaariset palautesiirtorekisterit Virtex-laitteissa . Haettu 19. marraskuuta 2014. Arkistoitu alkuperäisestä 2. marraskuuta 2013. (määrätön)
↑ 1 2 3 4 5 B. Schneier, 2013 .
↑ 1 2 3 4 Gabidulin, Kshevetsky, Kolybelnikov, 2011 .
↑ 1 2 3 Yu.B. Kobzarev, 2013 .
↑ 1 2 Larin, 2008 .
↑ 1 2 3 4 5 Fomichev, 2003 .
↑ Beker, Piper, 1982 .
↑ A. Sizonenko, 2012 .
↑ E. Barklan, E. Biham, N. Keller, 2008 .
↑ Y. Lu, W. Meier, S. Vaudenay, 2005 .
↑ D. Eastlake, J. Schiller, S. Crocker, 2005 .
↑ Tehokkaat siirtorekisterit, LFSR-laskurit ja pitkät näennäissatunnaiset sekvenssigeneraattorit . Haettu 18. marraskuuta 2014. Arkistoitu alkuperäisestä 25. tammikuuta 2021. (määrätön)
↑ B. Harrington, 2008 .
↑ O. Djatšenko .
↑ V. Vargauzin, 1999 .

Kirjallisuus

Schneier B. Sovellettu kryptografia. Protokollat, algoritmit, lähdetekstit C-kielellä. - Triumph, 2013. - 816 s. - ISBN 978-5-89392-527-2 .
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Tietoturva : oppikirja - M .: MIPT , 2011. - 225 s. — ISBN 978-5-7417-0377-9
Larin A. L. Digitaalisen elektroniikan perusteet - M .: MIPT , 2008. - 314 s. — ISBN 978-5-7417-0228-4
Sklyar B. Digitaalinen viestintä. Teoreettiset perusteet ja käytännön sovellus. - Williams, 2007. - 1104 s. - ISBN 978-5-8459-0497-3 .
Kobzarev Yu. B. Nykyaikainen tutka. - Ripol Classic, 2013. - 708 s. — ISBN 978-5-4584-7357-6 .
Fomichev V. M. Diskreetti matematiikka ja kryptologia : Luentokurssi / toim. N. D. Podufalov - M. : Dialog-MEPhI , 2013. - 397 s. — ISBN 978-5-86404-185-7
Beker H. , Piper F. Salausjärjestelmät: tietoliikenteen suojaus (englanti) - London : Northwood Books , 1982. - 427 s. — ISBN 978-0-7198-2611-5
Sizonenko AB Monikanavainen digitaalinen kohinalähde perustuu toistuvaan siirtorekisteriin . - Special Equipment and Communications Magazine nro 3, 2012. Arkistokopiopäivätty 29. marraskuuta 2014Wayback Machinessa
Barklan E. , Biham E. , Keller N. Välitön salakirjoitus vain GSM-salatun viestinnän kryptausanalyysi . - Journal of cryptology nro 21-3, 2008.
Lu Y. , Meier W. , Vaudenay S. Vain välitön salakirjoitus GSM-salatun viestinnän salausanalyysi . - Salausnumero 3621, 2005. (linkki ei ole käytettävissä)
Eastlake D. , Schiller J. , Crocker S. Turvallisuuden satunnaisuusvaatimukset . – 2005.
Harrington B. Hanki tehosi BIST:ltä . — 2008. (linkki ei käytettävissä)
Dyachenko O. N. Kompakti analyysi kentällä GF(3).
Vargauzin V. ATSC-standardin digitaalisen television periaatteet. - Tele-Sputnik-lehti nro 9 (47), 1999.

Linkit

LFSR- viittaus . LFSR-teoria ja toteutus, enimmäispituussekvenssit ja täydelliset napautussekvenssitaulukot pituuksille 7–16 miljoonaa (3–24 bittiä) ja osittaiset taulukot pituuksille 4 miljardiin (25–32 bittiä) asti (linkki ei käytettävissä) Arkistoitu 1. lokakuuta 2018 .
Kansainvälisen teleliiton suositus O.151 . elokuuta 1992
Näennäissatunnaislukujen luontirutiini Arkistoitu 25. joulukuuta 2008 Wayback Machinessa
[3 ]
Yksinkertainen selitys LFSR : istä insinööreille
Palautteen ehdot
Toteutus kryptografisesti turvallisesta kutistuvasta näennäissatunnaislukugeneraattorista
Salaustietojen suojauksen menetelmät ja tehtävät (pääsemätön linkki)