Primjer linearnog posmačnog registra. Pomačni registri s povratnom spregom. Primjeri generatora za rslos

- “Tetromino tenis”). Osmislio je i riješio bezbrojne matematičke zagonetke i igre riječi. Prije otprilike 20 godina saznao sam da je bio vrlo blizu otkrivanju mog omiljenog pravila od 30 za stanične automate 1959., kad sam se tek rodio.

Kako sam upoznao Saula Golomba

Gotovo sve znanstvenike i matematičare koje poznajem upoznao sam kroz svoje profesionalne veze. Ali ne Sola Golomba. Bila je 1981., a ja, 21-godišnji fizičar (koji je postao malo poznat u medijima po tome što je bio najmlađi dobitnik nagrade MacArthur na inauguralnoj ceremoniji dodjele nagrada), bavio sam se istraživanjem u . Netko je pokucao na vrata mog ureda, a ubrzo je prag prešla mlada žena. To je već bilo neobično, jer je u ono doba, gdje se proučavala teorijska fizika visokih energija, bilo beznadno malo žena. Iako sam nekoliko godina živio u Kaliforniji, nikada nisam napustio kampus i bio sam loše pripremljen za navalu energije Južne Kalifornije koja je prodrla u moj ured. Žena se predstavila kao Astrid i rekla da je pohađala Oxford i da poznaje nekoga s kim sam bio Dječji vrtić. Objasnila je da je dobila zadatak prikupiti informacije o zanimljivim ljudima u području Pasadene. Mislim da me smatrala teškim slučajem, ali je ipak inzistirala na razgovoru. I jednog dana kada sam pokušavao ispričati nešto o tome čime se bavim, rekla je: " Morate upoznati mog oca. On je već starac ali njegov je um još uvijek oštar kao britva „I dogodilo se da me Astrid Golomb, najstarija kći Sola Golomba, upoznala s njim.

Obitelj Golomb živjela je u kući smještenoj u planinama u blizini Pasadene. Imali su dvije kćeri: Astrid - nešto stariju od mene, ambicioznu holivudsku djevojku, i Beatrice - otprilike mojih godina i znanstvenog uma. Sestre Golomb često su priređivale zabave, najčešće u svom domu. Teme su bile različite: zabava u vrtu i kroket s flamingosima i ježevima (" Pobjednik će biti onaj čiji kostim najbolje odgovara navedenoj temi"), ili zabava u stilu Stonehengea s uputama ispisanim runama. Na tim zabavama križali su se mladi i manje mladi ljudi, uključujući i razna domaća velikana. A na njima, malo po strani, uvijek je bio mali čovjek s velika brada, pomalo poput vilenjaka i uvijek nosi tamni kaput - sam Solomon Golomb.

Postupno sam naučio nešto o njemu. U što je bio uključen" teorija informacija". Da je radio na Sveučilištu Južne Kalifornije. Da je imao razne nejasne, ali očito visoke vladine i druge veze. Čuo sam za registre smjena, ali o njima nisam znao gotovo ništa.

Evo što se događa nakon nekog vremena:

Kao što vidite, registar posmaka uvijek pomiče bitove ulijevo, a ostali bitovi se dodaju udesno prema jednostavnom pravilu. Čini se da je niz bitova nasumičan, iako se, kao što je prikazano na slici, na kraju ponavlja. Sol Golomb pronašao je elegantan matematički način za analizu takvih nizova i načina na koji se ponavljaju.

Ako posmični registar ima veličinu n, onda ima 2 n moguća stanja (koja odgovaraju svim mogućim nizovima od 0 i 1 s duljinom n). Budući da su pravila za registar posmaka deterministička, svaka dana pozicija mora uvijek konvergirati drugoj sličnoj poziciji. To znači da je najveći mogući broj koraka kroz koje registar posmaka može proći prije nego što se koraci počnu ponavljati 2 n(zapravo 2 n- 1, budući da pozicija sa svim nulama ne može evoluirati ni u što drugo).

U gornjem primjeru, registar posmaka je veličine 7 i ponavljat će se u točno 2 7 - 1 = 127 koraka. Ali koji će registri pomaka - s kojim rasporedom slavina - proizvesti sekvence maksimalna duljina? Solomon Golomb počeo je istraživati ovo pitanje u ljeto 1954. A njegov je odgovor bio jednostavan i elegantan.

Gornji registar pomaka ima grane na pozicijama 7, 6 i 1. Saul je to algebarski predstavio koristeći polinom x 7 + x 6 + 1. Zatim je pokazao da će generirani niz biti maksimalne duljine ako je ovaj polinom " nesvodljiv modulo 2"; stoga se ne može faktorizirati, što ga čini analognim prostim brojevima polinoma; a prisutnost nekih drugih svojstava čini ga "primitivnim polinomom". Danas je to lako provjeriti pomoću Mathematice i Wolfram jezika:

Tada, 1954., Saul je sve to morao raditi ručno; sastavio je prilično dugačku tablicu primitivnih polinoma koji odgovaraju registrima posmaka koji proizvode nizove maksimalne duljine:

Povijest registara pomaka

Ideja o održavanju RAM memorija kroz " linije kašnjenja", koji odašilje digitalne impulse, datira s početka računalne ere. Do kasnih 1940-ih, takve linije kašnjenja primijenjene su digitalno pomoću niza vakuumskih cijevi i nazvane su " registri pomaka„Još nije jasno kada su stvoreni prvi registri pomaka Povratne informacije. To je moglo biti kasnih 1940-ih. Međutim, taj je događaj još uvijek obavijen velom tajne jer su prvi put korišteni u vojnoj kriptografiji.

Osnovna ideja kriptografije je promijeniti smislene poruke tako da se ne mogu prepoznati; međutim, ako znate ključ, možete ponovno stvoriti šifriranu poruku. Takozvane stream šifre rade na principu stvaranja dugih nizova naizgled nasumičnih elemenata, a dekodiraju se pomoću prijemnika koji neovisno generira isti niz elemenata.

Linearni registri pomaka s povratnom spregom bili su cijenjeni u kriptografiji zbog svojih dugih perioda ponavljanja. Međutim, matematička analiza koju je Saul koristio da pronađe ta razdoblja jasno pokazuje da takvi registri pomaka nisu prikladni za sigurnu kriptografiju. No, na početku su se činile sasvim dobre (posebno u usporedbi sa sekvencijalnim položajima rotora u Enigmi); postojale su uporne glasine da su sovjetski vojni kriptosustavi izgrađeni na ovoj osnovi.

Davne 2001. godine, kada sam radio povijesne bilješke za svoju knjigu Nova vrsta znanosti, Saul i ja smo dugo razgovarali telefonom o promjenama predmeta. Saul mi je rekao da, kad je počeo, nije znao ništa o kriptografskom radu pomačnog registra. Rekao je da su ljudi u Bell Labsu, Lincoln Labsu i Laboratoriju za mlazni pogon počeli raditi na registrima pomaka otprilike u isto vrijeme kad i on; ipak je uspio otići malo dalje, što je zabilježio u svom izvješću iz 1955. godine.

Tijekom sljedećih godina, Saul je postupno učio o raznim prethodnicima svog rada iz literature o čistoj matematici. Još 1202. Fibonacci je govorio o onome što se danas naziva Fibonaccijevim brojevima, koji su generirani relacijom ponavljanja (koja se može smatrati analognom registru pomaka s linearnom povratnom spregom, koji djeluje na proizvoljnim cijelim brojevima, a ne jedinicama i nulama). Postoji i mali rad iz ranih 1900-ih o cikličnosti 0 i 1, ali prva velika studija bio je rad Oysteina Årea sa Sveučilišta u Oslu. Ore je imao studenta po imenu Marshall Hall koji je savjetovao prethodnika Nacionalne sigurnosne agencije kasnih 1940-ih. - vjerojatno na temu posmičnih registara. Međutim, sve što je radio bilo je povjerljivo, pa je sredio da Saul objavi povijest registara pomaka s linearnom povratnom spregom; Saul je svoju knjigu posvetio Marshall Hallu.

Čemu služe nizovi generirani pomačnim registrima?

Mnogo sam puta primijetio da sustavi definirani jednostavnim pravilima završavaju s mnogo mogućih primjena; Registri pomaka također slijede ovaj obrazac. I moderni hardver i softver pretrpani su registrima pomaka: tipičan mobilni telefon vjerojatno ih ima desetak ili dva, obično ugrađenih u hardver, a ponekad i u softver(kad ovdje napišem "registar pomaka", mislim na registar pomaka s linearnom povratnom spregom - LFSR).

U većini slučajeva, oni posmačni registri koji proizvode sekvence maksimalne duljine (inače poznate kao " M-nizovi"). Razlozi zašto se koriste općenito imaju veze s nekim njihovim svojstvima koja je Saul otkrio. Uvijek sadrže isti broj 0 i 1 (iako zapravo uvijek postoji točno jedna dodatna 1). Saul je kasnije pokazao da također je uobičajeno imati isti broj nizova 00, 01, 10 i 11 - i za velike blokove također. Ovo svojstvo " ravnoteža"Ovo je već samo po sebi vrlo korisno - na primjer, ako testirate sve moguće kombinacije bitova kao ulaznih podataka.

Međutim, Saul je otkrio još jedno, još važnije svojstvo. Zamijenite svaku 0 u nizu s 1, a zatim pomnožite svaki element u pomaknutoj verziji niza s odgovarajućim elementom u izvorniku. Saul je pokazao da će ti elementi, kada se dodaju, uvijek biti jednaki nuli (osim u slučajevima kada uopće nema pomaka). To jest, niz nema korelaciju s pomaknutim verzijama samog sebe.

Ova svojstva će biti istinita za bilo koju dovoljno dugu slučajnu sekvencu od 0 i 1. Iznenađujuće, za sekvence maksimalne duljine, ova svojstva su uvijek istinita. Nizovi imaju neka kaotična obilježja, ali zapravo uopće nisu kaotični: imaju dobro definiranu, organiziranu strukturu.

Upravo ova struktura svojstvena registrima pomaka s linearnom povratnom spregom čini ih neprikladnima za ozbiljnu kriptografiju. Ali oni su izvrsni za osnovnu "permutaciju elemenata" i jeftinu kriptografiju, i naširoko se koriste u te svrhe. Često je zadatak jednostavno "izbijeliti" signal (kao u "bijelom šumu"). Ponekad trebate prenijeti podatke s dugim sekvencama od 0. Ali u ovom slučaju, elektronika se može zbuniti ako je "tišina" preduga. Ovaj problem možete izbjeći kodiranjem izvornih podataka kombiniranjem sa sekvencom koju generira registar posmaka. Upravo je to učinjeno s Wi-Fi-jem, Bluetoothom, USB-om, digitalnom televizijom, internetom itd.

Nuspojava kodiranja registra pomaka je složenije dekodiranje, koje se ponekad koristi za poboljšanje sigurnosti (DVD tehnologija koristi kombinaciju 16-bitnih i 24-bitnih registara pomaka za kodiranje podataka; mnogi GSM telefoni koriste kombinaciju tri registra pomaka za kodirati sve signale).

Saul je stvorio matematičku osnovu za sve ovo, a također je međusobno upoznao niz ključnih figura. Već 1959. upoznao je Irwina Jacobsa, koji je nedavno doktorirao na MIT-u. Poznavao je i Andyja Viterbija, koji je radio u Laboratoriju za mlazni pogon. Saul ih je predstavio i 1968. osnovali su tvrtku pod nazivom Linkabit, koja je radila na sustavima kodiranja (uglavnom za vojne svrhe).

Godine 1985. Jacobs i Viterbi osnovali su drugu tvrtku pod nazivom Qualcomm. U početku im nije išlo osobito dobro, ali do ranih 1990-ih, kada su počeli proizvoditi komponente za uvođenje CDMA u Mobiteli, tvrtka je počela ubrzano rasti.

Pa gdje su ti registri?

Iznenađujuće je da većina ljudi nikada nije čula za registre pomaka, a ipak komuniciraju s njima svaki put kada ih koriste moderni sustavi komunikacije, računalne tehnologije itd. Ovdje se lako zabuniti, s obzirom da se iza različitih naziva i kratica kriju iste sekvence posmačnih registara s linearnom povratnom spregom (PN, pseudo šum, M-, FSR, LFSR sekvence, MLS, SRS , PRBS, itd.).

Kada je riječ o mobilnim telefonima, njihova upotreba nizova generiranih registrom pomaka varirala je tijekom godina, povećavajući se i smanjujući. mreže se temelje na TDMA, tako da ne koriste sekvence koje generiraju registri posmaka za kodiranje svojih podataka, ali još uvijek često koriste CRC (ciklički redundantni kod) za provjeru blokova podataka. mreže su najveći korisnici CDMA-a, tako da su sekvence generirane registrima posmaka uključene u prijenos svakog bita. mreže obično koriste kombinaciju vremenskih i frekvencijskih odsječaka koji ne uključuju sekvence registara pomaka, iako se CRC-ovi i dalje koriste: na primjer, za interakciju s integralnim podacima kada se frekvencijski prozori preklapaju. ima složeniju strukturu - s više antena koje se dinamički prilagođavaju za korištenje optimalnog vremena i frekvencije utora. Međutim, polovica njihovih kanala obično je dodijeljena "pilot signalima" koji se koriste za zaključivanje lokalnog radijskog okruženja; također se temelje na sekvencama koje generiraju posmačni registri.

U proizvodnji elektronike obično pokušavamo postići najviše velika brzina prijenos podataka uz minimalnu potrošnju energije, omogućujući bitovima da prevladaju prag šuma. I, u pravilu, ovaj put vodi do automatizacije otkrivanja grešaka - a time i do upotrebe CRC-a (cikličkog redundantnog koda) i, prema tome, sekvenci koje generira registar pomaka. To se odnosi na gotovo sve vrste sabirnica unutar računala (PCIe, SATA, itd.): osiguravanje interakcije između dijelova središnjeg procesora, ili primanje podataka s uređaja, ili povezivanje sa zaslonom s HDMI-jem. U slučaju diskova ili memorije, CRC i drugi kodovi temeljeni na sekvencama koje generiraju registri posmaka također se gotovo univerzalno koriste za rad maksimalnom brzinom.

Registri pomaka toliko su sveprisutni da je gotovo nemoguće procijeniti koliko bitova generiraju. Postoji otprilike 10 milijardi računala, nešto manje telefona i ogroman broj uređaja u ugrađenom IoT-u ("Internet of Things"). Gotovo svaki automobil na svijetu (a ima ih više od milijardu!) ima oko 10 ugrađenih mikroprocesora.

Na kojoj frekvenciji rade registri posmaka? Komunikacijski sustavi imaju osnovnu nosivu frekvenciju u hertznom rasponu, kao i "chip rate" koji govori koliko se brzo višestruki pristup (govorimo o CDMA) izvodi u MHz raspon. S druge strane, u sabirnicama unutar računala svi podaci se prenose pomoću registara pomaka - sa najbolja brzina prijenose u hertznom području.

Postoji najmanje 10 milijardi komunikacijskih linija koje rade najmanje 1/10 milijarde sekundi (oko 3 godine) koje koriste najmanje 1 milijardu bitova iz registara pomaka svake sekunde, što znači da je do danas Saulov algoritam korišten najmanje oktilion puta .

Je li ovo najčešće korišteni algoritam? Ja mislim da. Pretpostavljam da se samo aritmetičke operacije mogu natjecati. Danas su procesori sposobni izvesti trilijun aritmetičkih operacija u sekundi, a takve su operacije potrebne za gotovo svaki bit koji generira računalo. Ali kako se radi aritmetika? Na nekoj razini, ovo je jednostavno implementacija digitalne elektronike.

Međutim, postoje "algoritamske ideje" koje ostaju nejasne svima osim dizajnerima mikroprocesora. Kad je Babbage napravio svoj diferencijski stroj (pogledajte članak na Habréu "Razotkrivanje priče o Adi Lovelace (prvoj programerki u povijesti)"), prijenosi su postali velika prepreka u izvođenju aritmetičkih operacija (zapravo, linearni registar pomaka s povratnom spregom može se smatrati kao sustav koji radi nešto poput aritmetičkih izračuna ali ne prenosi). Postoje "stabla prijenosa propagacije" koja optimiziraju prijenos. Postoje i mali trikovi (kao što su "Boothov algoritam", "Wallaceova stabla" itd.) koji smanjuju broj bitnih operacija potrebnih za stvaranje "unutarnjih" aritmetičkih podataka. Ali za razliku od registara pomaka s linearnom povratnom spregom, jednostavno ne postoji jedna algoritamska ideja koja se može koristiti gotovo bilo gdje; pa mislim da najdulje sekvence generirane registrima pomaka s linearnom povratnom spregom još uvijek pobjeđuju među najčešće korištenim sekvencama.

Stanični automati i posmačni registri s nelinearnom povratnom spregom

Iako se na prvi pogled možda ne čini očiglednim, pokazalo se da postoji bliska veza između registara pomaka s povratnom spregom i staničnih automata koje sam proučavao mnogo godina. Osnovna organizacija registra pomaka s povratnom spregom je procjena jednog po bita. U staničnom automatu postoji jedna linija ćelija, a na svakom koraku sve ćelije se ažuriraju paralelno, na temelju pravila koje ovisi, na primjer, o vrijednostima njihovih najbližih susjeda.

Da biste vidjeli kako su povezani, morate pokrenuti registar pomaka s povratnom veličinom n, au isto vrijeme prikazuje svoje stanje samo svakih n koraci; drugim riječima, neka se svi bitovi prepišu prije nego što se ponovno pojave. Ako se mapira svaki korak registra pomaka s linearnom povratnom spregom (ovdje s dva dodira), tada će se u svakom koraku sve pomaknuti ulijevo - to je to. Ali ako napravite komprimiranu sliku, prikazujući samo svaki n koraka, uzorak će postati vidljiv.

Ovo je ugniježđeni uzorak; a ta je slika vrlo slična onoj koja se može dobiti ako stanični automat uzme ćeliju i njezinog susjeda i zbroji ih po modulu 2 (XOR). Ovo se događa staničnom automatu ako svoje ćelije rasporedi tako da su u krugu iste veličine kao gornji registar pomaka:

Isprva se ispostavi da su obrasci staničnih automata i registra pomaka potpuno isti. Ako pogledate ove slike, postaje manje iznenađujuće da matematika registara pomaka ima veze sa staničnim automatima. A s obzirom na ponovljivost ugniježđenih uzoraka, jasno je zašto mora postojati elegantna matematička teorija za registre pomaka.

Tipični registri posmaka koji se koriste u praksi nemaju tako jasno ponavljajuće obrasce. Evo nekoliko primjera registara posmaka koji generiraju nizove maksimalne duljine. Činjenica je da su grane udaljene jedna od druge, što otežava pronalaženje vizualnih tragova gniježđenja.

Koliko je široka korespondencija između registara pomaka i staničnih automata? Za stanične automate, pravila za generiranje novih vrijednosti ćelija mogu biti bilo što. U registrima pomaka s linearnom povratnom spregom oni bi se uvijek trebali temeljiti na zbrajanju po modulu 2 (ili XOR). To je ono što znači "linearni" dio "registra pomaka s linearnom povratnom spregom". Također je moguće koristiti bilo koje pravilo za kombiniranje vrijednosti za registre pomaka s nelinearnom povratnom spregom (NFSR).

Doista, kada je Saul razvio svoju teoriju za linearne registre pomaka s povratnom spregom, započeo je s nelinearnim slučajem. Kad je 1956. stigao u JPL, dobio je laboratorij zajedno s policama za male elektroničke module. Saul je rekao da su moduli (svaki otprilike veličine kutije cigareta) izgrađeni za projekt Bell Labsa za izvođenje određene logičke operacije (I, ILI, NE, ...). Moduli se mogu koristiti zajedno za implementaciju bilo kojih željenih registara pomaka s nelinearnom povratnom spregom, pružajući oko milijun bitova u sekundi (Saul mi je rekao da je netko pokušao učiniti istu stvar koristeći glavno računalo, a to je trajalo 1 sekundu kada su se koristili potrebni hardverski moduli 6 tjedana rada na univerzalnom računalu).

Kad je Saul počeo proučavati registre posmaka s linearnom povratnom spregom, njegovo prvo veliko otkriće bila su njihova razdoblja ponavljanja. A u slučaju nelinearnih, većinu je svojih napora posvetio pokušaju da shvati istu stvar. Prikupio je sve vrste eksperimentalnih podataka. Rekao mi je da je čak testirao nizove duge 2 45, što je trajalo godinu dana. Napravio je sažetak kao na slici ispod (obratite pažnju na vizualizaciju sekvenci prikazanih na liniji valnog oblika). Ali nikada nije uspio smisliti nijedan opća teorija, koje je imao za posmačne registre s linearnom povratnom spregom.

Nije ni čudo da to nije mogao. Već 1950-ih, postojali su teorijski rezultati (uglavnom temeljeni na Turingovim idejama o univerzalnom računalstvu) o tome koji programi to u načelu mogu učiniti. Mislim da Saul ili bilo tko drugi nikada nije pomislio da bi registri pomaka s nelinearnom povratnom spregom koristili vrlo jednostavne (nelinearne) funkcije.

I tek kasnije je postalo jasno koliko je složeno ponašanje čak i vrlo jednostavni programi. Moj omiljeni primjer je pravilo 30 za stanični automat, u kojem se vrijednosti susjednih ćelija kombiniraju pomoću funkcije koja se može predstaviti kao R + q + r + q*r modifikacija 2(ili R XOR ( q ILI r)). Nevjerojatno, Saul je razmatrao registre posmaka s nelinearnom povratnom spregom na temelju sličnih funkcija: R + G + s + q*r + q*s + r*s modifikacija 2. Ovdje ispod su ilustracije kako Saulova funkcija (koja se može smatrati "pravilom 29070"), pravilo 30 i nekoliko drugih sličnih pravila izgledaju u registru pomaka:

I ovdje oni, nisu ograničeni registrom fiksne veličine, izgledaju poput staničnih automata:

Naravno, Saul nikada nije napravio ovakve slike (a to je bilo gotovo nemoguće u 1950-ima). Umjesto toga, usredotočio se na period ponavljanja kao neku vrstu agregatne karakteristike.

Saul se pitao mogu li registri pomaka s nelinearnom povratnom spregom biti izvori slučajnosti. Iz onoga što se trenutno zna o staničnim automatima, jasno je da mogu. Na primjer, da bismo stvorili kaos za Mathematicu, koristili smo pravilo 30 staničnih automata 25 godina (iako smo ga nedavno napustili u korist više učinkovito pravilo, što smo pronašli nakon istraživanja trilijuna mogućnosti).

Saul nije mnogo govorio o enkripciji; iako mislim da je samo kratko vrijeme radio za vladu. Rekao mi je da iako je 1959. otkrio " višedimenzionalni korelacijski napadi na nelinearne nizove"u isto vrijeme on" pažljivo izbjegavao tvrdnje da je program bio za kriptoanalizu"Stvar je u tome da pravilo 30 za stanične automate (a možda i nelinearne povratne sprege pomačnih registara) mogu biti dobri kriptosustavi - iako zbog činjenice da su naizgled ekvivalentni linearnim pomačnim registrima povratne sprege (što nije tako), nikada nisu korišteni koliko je god moguće.

Kao entuzijast, tijekom proteklih nekoliko desetljeća pokušao sam proučiti sve prethodnike svog rada na jednodimenzionalnim staničnim automatima. Dvodimenzionalni stanični automati malo su proučavani, ali u slučaju jednodimenzionalnih staničnih automata pronađen je samo jedan čisto teorijski rad. Mislim da su od svih stvari koje sam vidio nelinearni registri pomaka s povratnom spregom Solomona Golomba bili najbliži onome što sam na kraju napravio četvrt stoljeća kasnije.

Polyomino

Čuti ime " Golomb ", mnogi će se sjetiti registara posmaka. No, većina će se sjetiti poliomino. Saul nije izmislio poliomine, iako je smislio ime. Učinio je sustavnim ono što se prije pojavljivalo samo u pojedinačnim zagonetkama.

Glavno pitanje na koje je Saul želio odgovoriti bilo je kako se skupovi poliomina mogu organizirati da pokriju neko područje. Ponekad je to sasvim očito, a ponekad je prilično teško. Saul je objavio svoj prvi rad o poliominu 1954., ali Martin Gardner je bio taj koji je učinio poliominu popularnom 1957. (napisao je kolumnu o matematičkim igrama u časopisu Scientific American). Kao što je Saul objasnio u predgovoru svojoj knjizi iz 1964., rezultat je bio " stalna struja dopisnika iz cijelog svijeta i iz svih društvenih slojeva: predsjednici upravnih odbora vodećih sveučilišta, štićenici nepoznatih samostana, zatvorenici iz poznatih zatvora...".

Tvrtke koje se bave igrama također su primijetile nove zagonetke, a za nekoliko mjeseci pojavili su se naslovi poput " nove senzacionalne zagonetke", nakon čega slijede desetljeća drugih zagonetki i igara temeljenih na poliominu (ne, jezivi ćelavi tip ne izgleda kao Saul):

Saul je nastavio objavljivati članke o poliominu još 50 godina nakon prve objave. Godine 1961. predstavio je "rep-pločice" koje se mogu koristiti za stvaranje fraktalnih ("Infin-tile") uzoraka. Ali gotovo sve što je Saul radio s poliominom uključivalo je rješavanje specifičnih problema.

Malo me zanimaju specifičnosti poliomina; Zanimaju me općenitiji fenomeni povezani s njima. Čini se da se može odlučiti s nekolicinom jednostavnih oblika Lako je "popločati" cijelu ravninu. Ali s poliominima (i svim igrama i zagonetkama temeljenim na njima), jasno je da stvari nisu tako jednostavne. I doista, šezdesetih godina prošlog stoljeća dokazano je da je taj problem teorijski nerješiv.

Ako nas zanima samo ograničeno područje, onda, u načelu, možemo jednostavno nabrojati sve zamislive rasporede figura, a zatim vidjeti jesu li raspoređeni kako treba. Međutim, ako nas zanima beskonačnost, onda to ne treba činiti. Možda će netko pronaći način da uspješno postavi milijunske figure, ali nema jamstva da se ovaj rezultat može dalje proširivati.

Ispostavilo se da bi mogao izgledati kao Turingov stroj koji radi - ili stanični automat. Počinjete s linijom pločica. Tada je pitanje je li moguće beskonačno popločavanje ekvivalentno pitanju je li moguće postaviti Turingov stroj koji će mu omogućiti da ne stane. Poanta je da ako je Turingov stroj univerzalan (to jest, može se programirati za izvođenje bilo kojeg mogućeg računanja), tada problem zaustavljanja za njega može biti neodlučan, što znači da će problem popločavanja također biti neodlučan.

Naravno, to ovisi o izvornom skupu obrazaca. Pitanje je koliko obrasci moraju biti složeni da kodiraju univerzalna izračunavanja i dovedu do nerješivog problema s popločavanjem. Solomon Golomb je bio svjestan literature o ovoj temi, ali nije bio posebno zainteresiran za nju.

Poznato je da složeni i pažljivo dizajnirani skupovi poliomina zapravo podržavaju univerzalno računanje. Ali što je s jednostavnim setom? Je li doista dovoljno jednostavno da naletite slučajno? Ako pogledate sve sustave koje sam proučavao, najjednostavniji skup stvarno se pokazao jednostavnim. Međutim, teško ga je pronaći.

Puno jednostavniji problem je pronaći poliomine koji uspješno ispunjavaju ravnine, iako samo neperiodički. Roger Penrose pronašao je odgovarajući primjer 1994. godine. U mojoj knjizi Nova vrsta znanosti Dao sam malo jednostavniji primjer s 3 poliomina:

Ostatak priče

Saul je bio u svojim ranim tridesetima kada je postigao zapažene uspjehe na polju pomačnih registara i poliomina... Bio je vrlo aktivna osoba. Napisao je nekoliko stotina radova, od kojih su neki proširivali njegov raniji rad, neki su bili odgovori na pitanja koja su mu postavljana, a neki su napisani, čini se, samo iz zabave - da saznaju zanimljivosti o brojevima, nizovima. , kriptosustavi, itd. d.

Pomačni registri i poliomini opsežne su teme (čak su klasificirani u zasebne kategorije u AMS klasifikaciji). Posljednjih desetljeća oba su dobila novi krug razvoja kada su se na njihovoj osnovi počeli provoditi računalni eksperimenti; U njima je aktivno sudjelovao i Sol. Međutim, mnoga pitanja ostaju bez odgovora. I ako se velike Hadamardove matrice mogu naći za registre posmaka s linearnom povratnom spregom, onda se čak i sada malo zna o registrima posmaka s nelinearnom povratnom spregom, da ne spominjemo sve neperiodične i druge egzotične poliomine.

Saula su oduvijek zanimale zagonetke, kako matematičke tako i zagonetke s riječima. Neko je vrijeme pisao kolumnu zagonetki za Los Angeles Times, i 32 godine pisao " Golombovi gambiti" u časopisu Johns Hopkins alumni. Sudjelovao je u MegaIQ testiranju i osvojio put u Bijelu kuću kada su on i njegov šef bili rangirani među pet najboljih u zemlji.

Ulagao je golem trud u svoj rad na sveučilištu: ne samo da je predavao dodiplomcima i nadzirao diplomske studente te se penjao na administrativnoj ljestvici (predsjednik sveučilišnog vijeća, prorektor za znanstvena istraživanja i dr.), nego je izražavao i svoje mišljenje o upravljanju fakultetom. sveučilište u cjelini (npr. napisao članak pod naslovom „Savjetovanje fakulteta: ukloniti ili ostaviti?“; Odgovor: ne, to je dobro za sveučilište!). Na Sveučilištu Južne Kalifornije bio je lovac na glave, a tijekom svog boravka tamo pomogao je sveučilištu da se iz mraka izdigne na vrh ljestvice obrazovnih programa.

A onda je uslijedilo savjetovanje. Saul je bio pedantan i nije otkrio što je radio za vladine organizacije. U kasnim 1960-ima, frustriran što svi osim njega prodaju poliomino igre, Saul je osnovao tvrtku koju je nazvao Recreational Technology, Inc. Stvari nisu išle najbolje, ali Saul je upoznao Alvina Berlekampa, profesora s Berkeleyja koji je bio zainteresiran za teorije kodiranja i zagonetke. Kasnije su osnovali tvrtku Cyclotomics (u čast ciklotomskih polinoma oblika x n– 1), koji je na kraju prodan Kodaku za solidnu svotu (Berlekamp je stvorio i algoritamski sustav trgovanja, koji je zatim prodao Jimu Simonsu i koji je postao polazište Renaissance Technologies, jednog od najvećih hedge fondova današnjice).

Više od 10 000 patenata je na ovaj ili onaj način povezano sa Saulovim radom, ali sam Saul dobio je samo jedan patent na kvazi-grupnim kriptosustavima - i mislim da je učinio malo da komercijalizira svoj rad.

Dugi niz godina Saul je radio za Technion, izraelski tehnološki institut. O sebi je govorio kao o " nereligiozni ortodoksni Židov“, ali je u isto vrijeme ponekad držao seminare o Knjizi postanka za početnike, a također je radio na dešifriranju dijelova svitaka s Mrtvog mora (kumranski rukopisi).

Saul i njegova žena mnogo su putovali, ali Saulov "centar svijeta" definitivno je bio njegov ured u Los Angelesu na Sveučilištu Južne Kalifornije i dom u kojem su on i njegova supruga živjeli gotovo 60 godina. Uvijek je bio okružen prijateljima i studentima. I imao je obitelj. Njegova kći Astrid glumila je studenticu u predstavi o Richardu Feynmanu (pozirala mu), au prijateljskom romanu kao jedan od likova. Beatrice je svoju karijeru posvetila primjeni matematičke razine preciznosti na različite vrste medicinskih stanja i dijagnoza (bolesti povezane sa Zaljevskim ratom, učinci statina, štucanje itd.). Čak sam dao mali doprinos Beatriceinom životu upoznavši je s čovjekom koji joj je kasnije postao suprug – Terryjem Sejnowskim, jednim od utemeljitelja moderne računalne neuroznanosti.

Činilo se da je Saul upleten u mnoge stvari, iako nije previše govorio o detaljima. S vremena na vrijeme želio sam s njim razgovarati o znanosti i matematici, ali njega su više zanimale priče (često vrlo uzbudljive) o pojedincima i organizacijama (" Možete li vjerovati da se [1985.], nakon godina izbivanja s konferencija, Claude Shannon jednostavno nenajavljen pojavio u baru na godišnjoj konferenciji o teoriji informacija?"; "znaš li koliko su morali platiti šefu Caltecha da bi otišao u Saudijsku Arabiju?", itd.).

Gledajući unatrag, shvaćam da bih volio zainteresirati Saula za rješavanje nekih matematičkih pitanja postavljenih u mom radu. Mislim da nikad nisam shvatio do koje je mjere volio rješavati probleme koje su predložili drugi ljudi. Unatoč njegovom značajnom doprinosu infrastrukturi svijeta računala, sam Saul nikada nije ozbiljno koristio računala. Bio je vrlo ponosan na činjenicu da je lako mogao računati u glavi. Do svoje 70. godine života nije koristio e-mail i nikada nije koristio računalo kod kuće, iako mobitel imao je (redovno E-mail od njega nije dolazilo gotovo ništa. Jednom sam spomenuo da sam prije otprilike godinu dana proučavao priču o Adi Lovelace; on je odgovorio: " Priča o Adi Lovelace kao Babbageovoj programerki toliko je raširena da se čini da je svi prihvaćaju kao činjenicu, ali nikad nisam vidio izvore o toj temi.").

Saulove kćeri su prije nekoliko godina priredile zabavu za njegov 80. rođendan i osmislile ove zanimljive pozivnice:

Sol je imao zdravstvenih problema, iako se činilo da to nije previše utjecalo na njegov ritam života. Zdravlje njegove supruge se pogoršavalo, prilično naglo u posljednjih nekoliko tjedana. U petak je Saul otišao u svoj ured kao i obično, au subotu navečer je umro u snu. Njegova supruga Bo nadživjela ga je samo dva tjedna i umrla je samo dva dana prije 60. godišnjice braka.

Iako Saula više nema, njegovo djelo živi u oktilionima bitova u digitalnom svijetu.

Zbogom Sol. I od svih nas - hvala.

U registru posmaka s linearnom povratnom spregom postoje dva dijela (modula): sam registar pomaka i sklopovi (ili potprogrami) koji izračunavaju vrijednost gurnutog bita. Registar se sastoji od funkcijskih ćelija (ili bitova strojne riječi ili više riječi), od kojih svaka pohranjuje trenutno stanje jednog bita. Broj ćelija naziva se duljina registra. Bitovi (ćelije) obično su numerirani brojevima, od kojih je svaki sposoban pohraniti bit, te se izračunati bit gura u ćeliju, a sljedeći generirani bit se uklanja iz ćelije. Izračun bita koji se gura obično se radi prije pomaka registra, a tek nakon pomaka se vrijednost izračunatog bita stavlja u ćeliju.

Period registra pomaka je minimalna duljina rezultirajuće sekvence prije nego što se počne ponavljati. Budući da registar bitnih ćelija ima samo različita stanja različita od nule, tada, u načelu, period registra ne može premašiti ovaj broj. Ako je razdoblje registra jednako ovom broju, onda se takav registar naziva registar maksimalnog perioda.

Za LFSR, funkcija povratne veze je linearna Booleova funkcija stanja svih ili nekih bitova registra. Na primjer, zbroj modula dva ili njegova logička inverzija je linearna Booleova funkcija (XOR operacija, označena u formulama kao ) i najčešće se koristi u takvim registrima.

Štoviše, oni bitovi koji su funkcijske varijable obično se zove povratna informacija zavoja.

Kontrola registra u hardverskim implementacijama izvodi se primjenom impulsa pomaka (drugačije se naziva sat ili impuls sinkronizacije) u sve ćelije, u softveru - izvršavanjem softverskog ciklusa, uključujući izračunavanje povratne funkcije i pomicanje bitova u riječi.

Tijekom svakog vremenskog koraka izvode se sljedeće operacije:

Registar pomaka s linearnom povratnom spregom

Stoga se logička operacija XOR (isključivo ILI) uzima kao funkcija povratne sprege, to jest:

Svojstva primitivnih polinoma

Svojstva

Svojstva niza koje proizvodi LFSR usko su povezana sa svojstvima pridruženog polinoma. Njegovi koeficijenti različiti od nule nazivaju se zavoja, kao i odgovarajuće ćelije registra koje daju vrijednosti argumenata funkcije povratne sprege.

Linearna složenost

Linearna složenost binarnog niza jedna je od najvećih važne karakteristike RSLOS rad. Uvedimo sljedeću oznaku:

Definicija

Linearna složenost beskonačnog binarnog niza naziva se broj koji je definiran na sljedeći način:

Linearna složenost konačnog binarnog niza naziva se broj koji je jednak duljini najkraćeg LFSR-a koji generira niz koji ima kao prve članove .

Svojstva linearne složenosti

Neka i budu binarni nizovi. Zatim:

Korelacijska neovisnost

Kako bi postigli visoku linearnu složenost, kriptografi pokušavaju nelinearno kombinirati rezultate višestrukih izlaznih nizova. U ovom slučaju, opasnost je da se jedna ili više izlaznih sekvenci (često čak i izlazi pojedinačnih LFSR-ova) mogu povezati zajedničkim protokom ključa i otvoriti pomoću linearne algebre. Hakiranje temeljeno na takvoj ranjivosti naziva se korelacija autopsija. Thomas Siegenthaler pokazao je da je moguće precizno odrediti korelacijsku neovisnost i da postoji kompromis između korelacijske neovisnosti i linearne složenosti.

Glavna ideja takvog hakiranja je otkriti neku korelaciju između izlaza generatora i izlaza jedne od njegovih komponenti. Zatim, promatranjem izlazne sekvence, mogu se dobiti informacije o ovom međuizlazu. Koristeći ove informacije i druge korelacije, podaci se mogu prikupljati na drugim međupinovima sve dok generator ne bude ugrožen.

Korelacijski napadi ili varijacije kao što su brzi korelacijski napadi koji uključuju kompromis između računske složenosti i učinkovitosti uspješno su korišteni protiv mnogih generatora toka ključeva s linearnom povratnom spregom registra pomaka.

Primjer

Za SFLOS s pridruženim polinomom, generirani niz ima oblik . Recimo da je prije početka procesa niz zapisan u registar, tada će period generiranog toka bitova biti jednak 7 sa sljedećim nizom:

Broj koraka	država	Generirani bit
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

Budući da se unutarnje stanje u sedmom koraku vratilo u prvobitno stanje, tada će, počevši od sljedećeg koraka, doći do ponavljanja. Drugim riječima, pokazalo se da je period niza jednak 7, što se dogodilo zbog primitivnosti polinoma.

Algoritmi za generiranje primitivnih polinoma

Gotovi stolovi

Izračunavanje primitivnosti polinoma prilično je složen matematički problem. Stoga postoje gotove tablice koje prikazuju brojeve sekvenci slavina koje osiguravaju maksimalno razdoblje generatora. Na primjer, za 32-bitni registar posmaka postoji niz . To znači da za generiranje novog bita morate dodati 31., 30., 29., 27., 25. i 0. bit pomoću funkcije XOR. Kod za takav RLOS u jeziku C je sljedeći:

Int LFSR (praznina) ( statički nepredznačeni dugi S = 1; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25) ^ S) & 1)<< 31 ) | (S>> 1); povratak S & 1 ; )

Softverske implementacije LFSR generatora prilično su spore i rade brže ako su napisane u asembleru umjesto u C jeziku. Jedno od rješenja je paralelno korištenje 16 RSLOS (ili 32, ovisno o duljini riječi u arhitekturi pojedinog računala). U takvoj shemi koristi se niz riječi čija je veličina jednaka duljini LFSR-a, a svaki bit riječi u nizu odnosi se na vlastiti LFSR. Pod uvjetom da se koriste isti sekvencijski brojevi dodira, to može pružiti primjetan dobitak performansi. [trebam primjer koda] (Vidi: bitslice).

Galois konfiguracija

Galoisova konfiguracija posmačnog registra s linearnom povratnom spregom

Povratni krug se također može modificirati. U tom slučaju generator neće imati veću kriptografsku snagu, ali će ga biti lakše programski implementirati. Umjesto da koristi krajnji lijevi bit niza dodira za generiranje novog krajnjeg lijevog bita, on izvodi XOR svaki bit niza dodira s izlazom generatora i zamjenjuje ga rezultatom te radnje, tada izlaz generatora postaje novi krajnji lijevi bit. U C-u to izgleda ovako:

Int LFSR (void) ( static unsigned long Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; )

Prednost je u tome što se svi XOR-ovi izvode u jednoj operaciji.

može se dokazati da prva Fibonaccijeva konfiguracija i ovdje dana Galoisova konfiguracija daju iste sekvence (dužine 2 32 −1), ali pomaknute u fazi jedna od druge
petlja fiksnog broja poziva funkciji LFSR u Galois konfiguraciji radi približno dvostruko brže nego u Fibonaccijevoj konfiguraciji (MS VS 2010 kompajler na Intel Core i5)
imajte na umu da je u Galoisovoj konfiguraciji redoslijed bitova u riječi koja definira povratnu spregu obrnut u usporedbi s Fibonaccijevom konfiguracijom

Primjeri generatora

Stop-and-go generatori

Izmjenični generator stani-kreni

Ovaj oscilator koristi izlaz jednog LFSR-a za kontrolu taktne frekvencije drugog LFSR-a. Izlaz sata RSLOS-2 kontrolira izlaz RSLOS-1, tako da RSLOS-2 može promijeniti svoje stanje u trenutku t samo ako je izlaz RSDOS-1 u trenutku t-1 bio jednak jedinici. Ali ova shema nije mogla odoljeti korelacijskom seciranju.

Stoga je predložen poboljšani generator temeljen na istoj ideji. Naziva se izmjeničnim stop-go generatorom. Koristi tri LFSR-a različitih duljina. RSLOS-2 se taktira kada je izlaz RSLOS-1 jednak jedinici, a RSLOS-3 se taktira kada je izlaz RSLOS-1 jednak nuli. Izlaz generatora je modulo 2 zbroj RSLOS-2 i RSLOS-3. Ovaj generator ima dug period i visoku linearnu složenost. Njegovi autori također su pokazali metodu za korelativno otvaranje RSLOS-1, ali to ne oslabljuje generator u velikoj mjeri.

Gollmannova kaskada

Gollmannova kaskada je pojačana verzija stop-go generatora. Sastoji se od niza LFSR-ova, od kojih je vremenski raspored svakog kontroliran prethodnim LFSR-om. Ako je izlaz RSLOS-1 u trenutku t 1, tada se RSLOS-2 taktira. Ako je izlaz RSLOS-2 u trenutku t 1, tada se RSLOS-3 taktira, i tako dalje. Izlaz posljednjeg LFSR je izlaz generatora. Ako je duljina svih LFSR-ova ista i jednaka n, tada je linearna složenost sustava od k LFSR-ova jednaka .

Ova ideja je jednostavna i može se koristiti za generiranje nizova s velikim periodima, velikom linearnom složenošću i dobrim statističkim svojstvima. Ali, nažalost, osjetljivi su na otvaranje, što se naziva "zaključavanje". Za veću izdržljivost preporučuje se korištenje k od najmanje 15. Štoviše, bolje je koristiti više kratkih SFSR nego manje dugih SFSR.

Generator praga

Ovaj generator pokušava zaobići sigurnosne probleme pronađene u prethodnim generatorima varijabilni broj registri pomaka. U teoriji, korištenjem većeg broja posmačnih registara povećava se složenost šifre, što je i učinjeno u ovom generatoru.

Ovaj generator se sastoji od velikog broja registara posmaka, čiji se izlazi šalju funkciji majorizacije. Ako je broj jedinica na izlazima registara veći od polovice, tada generator ispisuje jedinicu. Ako je broj nula na izlazima veći od polovice, tada generator daje nulu. Da bi usporedba broja nula i jedinica bila moguća, broj posmačnih registara mora biti neparan. Duljine svih registara moraju biti relativno proste, a povratni polinomi moraju biti primitivni, tako da period generiranog niza bude maksimalan.

U slučaju tri registra pomaka, generator se može predstaviti kao:

Ovaj generator je sličan Geffovom generatoru osim što generator praga ima veću linearnu složenost. Njegova linearna složenost je:

gdje su , , duljine prvog, drugog i trećeg registra posmaka.

Njegov nedostatak je što svaki izlazni bit daje neke informacije o stanju registra posmaka. Ili bolje rečeno, 0,189 bita. Stoga se ovaj generator možda neće moći oduprijeti korelacijskom napadu.

Ostale vrste

Samorazrjeđivanje

Samodecimajući generatori su oni koji kontroliraju vlastitu frekvenciju. Predložena su dva tipa takvih generatora. Prvi se sastoji od linearnog povratnog registra posmaka i nekih strujnih krugova koji taktiraju registar ovisno o tome koje su izlazne vrijednosti registra posmaka. Ako je izlaz SFSR-a jednak jedan, tada se registar taktira d puta. Ako je izlaz nula, tada se registar taktira k puta. Drugi ima gotovo isti dizajn, ali malo modificiran: u krugu sata, ulaz, kao provjera za 0 ili 1, nije sam izlazni signal, već XOR određenih bitova registra posmaka s linearnom povratnom spregom. Nažalost, ova vrsta generatora nije sigurna.

Višebrzinski oscilator s unutarnjim produktom

Ovaj oscilator koristi dva registra posmaka s linearnom povratnom spregom s različitim taktnim frekvencijama: RSLOS-1 i RSLOS-2. Frekvencija sata RSLOS-2 je d puta veća od RSLOS-1. Pojedinačni bitovi ovih registara kombiniraju se pomoću operacije AND. Izlazi operacije AND zatim se slažu XOR. Izlazni niz je preuzet iz ovog XOR bloka. Opet, ovaj generator nije besprijekoran (nije izdržao otkriće linearne konzistencije. Ako je - duljina SFOS-1, - duljina SFOS-2, a d je omjer taktne frekvencije, tada se unutarnje stanje generatora može dobiti iz izlazne sekvence duljine ), ali ima visoku linearnu složenost i izvrsne statističke karakteristike.

U ovom slučaju obično se pozivaju oni bitovi koji su varijable funkcije povratne sprege zavoja.

Tijekom svakog vremenskog koraka izvode se sljedeće operacije:

Registar pomaka s linearnom povratnom spregom

Stoga se logička operacija XOR (isključivo ILI) uzima kao funkcija povratne sprege, to jest:

Svojstva primitivnih polinoma

Svojstva

Linearna složenost

Linearna složenost binarnog niza jedna je od najvažnijih karakteristika rada LFSR-a. Uvedimo sljedeću oznaku:

Definicija

Linearna složenost beskonačnog binarnog niza naziva se broj koji je definiran na sljedeći način:

Linearna složenost konačnog binarnog niza naziva se broj koji je jednak duljini najkraćeg LFSR-a koji generira niz koji ima kao prve članove .

Svojstva linearne složenosti

Neka i budu binarni nizovi. Zatim:

Korelacijska neovisnost

Primjer

Za SFLOS s pridruženim polinomom, generirani niz ima oblik . Recimo da je prije početka procesa niz zapisan u registar, tada će period generiranog toka bitova biti jednak 7 sa sljedećim nizom:

Broj koraka	država	Generirani bit
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

Algoritmi za generiranje primitivnih polinoma

Gotovi stolovi

Int LFSR (praznina) ( statički nepredznačeni dugi S = 1; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25) ^ S) & 1)<< 31 ) | (S>> 1); povratak S & 1 ; )

Galois konfiguracija

Galoisova konfiguracija posmačnog registra s linearnom povratnom spregom

Int LFSR (void) ( static unsigned long Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; )

Prednost je u tome što se svi XOR-ovi izvode u jednoj operaciji.

može se dokazati da prva Fibonaccijeva konfiguracija i ovdje dana Galoisova konfiguracija daju iste sekvence (dužine 2 32 −1), ali pomaknute u fazi jedna od druge
petlja fiksnog broja poziva funkciji LFSR u Galois konfiguraciji radi približno dvostruko brže nego u Fibonaccijevoj konfiguraciji (MS VS 2010 kompajler na Intel Core i5)
imajte na umu da je u Galoisovoj konfiguraciji redoslijed bitova u riječi koja definira povratnu spregu obrnut u usporedbi s Fibonaccijevom konfiguracijom

Primjeri generatora

Stop-and-go generatori

Izmjenični generator stani-kreni

Gollmannova kaskada

Generator praga

Ovaj generator pokušava zaobići sigurnosne probleme svojstvene prethodnim generatorima korištenjem varijabilnog broja registara posmaka. U teoriji, korištenjem većeg broja posmačnih registara povećava se složenost šifre, što je i učinjeno u ovom generatoru.

U slučaju tri registra pomaka, generator se može predstaviti kao:

Ovaj generator je sličan Geffovom generatoru osim što generator praga ima veću linearnu složenost. Njegova linearna složenost je:

gdje su , , duljine prvog, drugog i trećeg registra posmaka.

Njegov nedostatak je što svaki izlazni bit daje neke informacije o stanju registra posmaka. Ili bolje rečeno, 0,189 bita. Stoga se ovaj generator možda neće moći oduprijeti korelacijskom napadu.

Ostale vrste

Samorazrjeđivanje

Višebrzinski oscilator s unutarnjim produktom

Ovaj oscilator koristi dva registra posmaka s linearnom povratnom spregom s različitim taktnim frekvencijama: RSLOS-1 i RSLOS-2. Frekvencija sata RSLOS-2 je d puta veća od RSLOS-1. Pojedinačni bitovi ovih registara kombiniraju se pomoću operacije AND. Izlazi operacije AND zatim se slažu XOR. Izlazni niz je preuzet iz ovog XOR bloka. Opet, ovaj generator nije besprijekoran (nije izdržao otkriće linearne konzistencije. Ako je - duljina SFLO-1, - duljina SFLO-2, a d je omjer taktnih frekvencija, tada je unutarnje stanje generator se može dobiti iz izlazne sekvence duljine ), ali ima visoku linearnu složenost i izvrsnu statističku izvedbu.

Registar pomaka povratne veze sastoji se od dva dijela: posmačnog registra i povratne funkcije.

Slika 19. Registar posmaka povratne veze.

Općenito, registar posmaka je niz nekih elemenata prstena ili polja. Najčešće se koristi malo registri pomaka. Duljina takvog registra izražava se brojem bitova. Svaki put kad se dohvati bit, svi bitovi u registru se pomiču udesno za jednu poziciju. Novi najznačajniji bit izračunava se kao funkcija svih ostalih bitova registra. Izlaz je obično bit najmanjeg značaja. Period registra pomaka je duljina izlazne sekvence prije nego što se počne ponavljati.

Najjednostavniji tip pomačnog registra je pomačni registar s linearnom povratnom spregom (LFSR ili LRS). Povratne informacije - jednostavan rad XOR nad nekim bitovima registra. Popis ovih bitova je određen karakteristični polinom i zove se slijed dodira. Ponekad se ova shema zove Fibonaccijeva konfiguracija.

Sl.20. RSLOS Fibonaccijeva konfiguracija.

Na implementacija softvera SFLO-ovi koriste modificiranu shemu: za generiranje novog značajnog bita, umjesto korištenja bitova odvodne sekvence, XOR operacija se izvodi na svakom od njegovih bitova s izlazom generatora, zamjenjujući stari bit odvodne sekvence. Ova se modifikacija ponekad naziva Galois konfiguracija.

Sl.21. RSLOS konfiguracije Galois.

n-bitni LFSR može biti u jednom od 2 n– 1 unutarnja stanja. To znači da teoretski takav registar može generirati pseudoslučajni niz s periodom 2 n– 1 bita (ispunjavanje nulama potpuno je beskorisno). Prolaz svih 2 n– 1 unutarnja stanja moguća su samo sa određene sekvence zavoja Takvi se registri nazivaju LFSR s maksimalnim razdobljem. Da bi se osigurao maksimalni period SFSR-a, potrebno je da njegov karakteristični polinom bude primitivna modulo 2. Stupanj polinoma je duljina registra posmaka. Polinom primitivnog stupnja n- tako je nesvodljiv polinom koji je djelitelj, ali nije djelitelj x d+ 1 za sve d, koji su djelitelji broja 2 n– 1. (Kad se govori o polinomima, termin glavni broj zamjenjuje se pojmom nesvodljivi polinom). Karakteristični polinom LFSR prikazan na slikama:

x 32 + x 7 + x 5 + x 3 + x 2 + x + 1

primitivan je modulo 2. Razdoblje takvog registra bit će maksimalno, ciklički prolazi kroz svih 2 32 – 1 vrijednosti prije nego što se ponove. Najčešće se koriste istanjeni polinomi, tj. koji imaju samo neke koeficijente. najpopularniji su trinomi.

Važan parametar generator temeljen na RSLOS-u, is linearna složenost. Definira se kao duljina n najkraći HFSR koji može simulirati izlaz generatora. Linearna složenost je važna jer korištenje jednostavnog Berlenkamp-Massey algoritam možete ponovno stvoriti takav LFSR označavanjem samo 2 n gama bitovi. Nakon što se odredi potrebni RFSL, šifra toka je zapravo probijena.

Registar pomaka povratne veze sastoji se od dva dijela: posmačnog registra i povratne funkcije.

Slika 19. Registar posmaka povratne veze.

Najjednostavniji tip pomačnog registra je pomačni registar s linearnom povratnom spregom (LFSR ili LRS). Povratna veza je jednostavna XOR operacija na nekim bitovima registra. Popis ovih bitova je određen karakteristični polinom i zove se slijed dodira. Ponekad se ova shema zove Fibonaccijeva konfiguracija.

Sl.20. RSLOS Fibonaccijeva konfiguracija.

Prilikom implementacije LFSR-a u softver, koristi se modificirana shema: za generiranje novog značajnog bita, umjesto korištenja bitova sekvence odvajanja, XOR operacija se izvodi na svakom od njegovih bitova s izlazom generatora, zamjenjujući stari bit niza dodira. Ova se modifikacija ponekad naziva Galois konfiguracija.

Sl.21. RSLOS konfiguracije Galois.

n-bitni LFSR može biti u jednom od 2 n– 1 unutarnja stanja. To znači da teoretski takav registar može generirati pseudoslučajni niz s periodom 2 n– 1 bita (ispunjavanje nulama potpuno je beskorisno). Prolaz svih 2 n– 1 unutarnja stanja moguća su samo s određenim sekvencama dodira. Takvi se registri nazivaju LFSR s maksimalnim razdobljem. Da bi se osigurao maksimalni period SFSR-a, potrebno je da njegov karakteristični polinom bude primitivna modulo 2. Stupanj polinoma je duljina registra posmaka. Polinom primitivnog stupnja n- tako je nesvodljiv polinom koji je djelitelj, ali nije djelitelj x d+ 1 za sve d, koji su djelitelji broja 2 n– 1. (Kad se govori o polinomima, termin glavni broj zamjenjuje se pojmom nesvodljivi polinom). Karakteristični polinom LFSR prikazan na slikama:

x 32 + x 7 + x 5 + x 3 + x 2 + x + 1

Važan parametar generatora temeljenog na RSLOS-u je linearna složenost. Definira se kao duljina n najkraći HFSR koji može simulirati izlaz generatora. Linearna složenost je važna jer korištenje jednostavnog Berlenkamp-Massey algoritam možete ponovno stvoriti takav LFSR označavanjem samo 2 n gama bitovi. Nakon što se odredi potrebni RFSL, šifra toka je zapravo probijena.

Osim LFSR-a koriste se i posmačni registri s nelinearnom povratnom spregom, prijenosnom povratnom spregom itd.

Brojni generatori razvijeni su na temelju teorijskog pristupa brojevima (Blum-Micali generatori, RSA, BBS, kompresija, aditivni generatori itd.).

Matematička podrška za sintezu tokovnih kriptografskih algoritama razvijena je potpunije i detaljnije u usporedbi s blokovskim kriptografskim algoritmima. Međutim, blok kriptografski algoritmi u OFB ili CFB modovima često se koriste za stvaranje tokovnih šifri.