Exemplu de registru cu deplasare liniară. Schimbă registrele cu feedback. Exemple de generatoare pentru rslos

- „Tetromino tenis”). A creat și rezolvat nenumărate puzzle-uri și jocuri de cuvinte matematice. Acum aproximativ 20 de ani am aflat că el a fost foarte aproape de a descoperi regula mea preferată de 30 pentru automatele celulare, în 1959, când tocmai m-am născut.

Cum l-am cunoscut pe Saul Golomb

Am ajuns să cunosc aproape toți oamenii de știință și matematicienii pe care îi cunosc prin relațiile mele profesionale. Dar nu Sola Golomba. Era 1981, iar eu, un fizician de 21 de ani (care devenisem un pic celebru în mass-media pentru că eram cel mai tânăr laureat al Premiului MacArthur la ceremonia inaugurală de premiere), făceam cercetări la . S-a auzit o bătaie la ușa biroului meu și în curând o tânără a trecut pragul. Acest lucru era deja neobișnuit, pentru că în acele vremuri, în care se studia fizica teoretică a energiilor înalte, erau fără speranță puține femei. Deși locuisem în California de câțiva ani, nu părăsisem niciodată campusul și eram prost pregătit pentru explozia de energie din California de Sud care a izbucnit în biroul meu. Femeia s-a prezentat ca fiind Astrid și a spus că a fost la Oxford și că știa pe cineva cu care am fost grădiniţă. Ea a explicat că a fost însărcinată cu strângerea de informații despre oameni interesanți din zona Pasadena. Cred că ea mă considera un caz dificil, dar totuși a insistat să vorbesc. Și într-o zi, când încercam să spun ceva despre ceea ce fac, ea a spus: „ Trebuie să-l cunoști pe tatăl meu. El este deja om batran dar mintea îi este încă ascuțită „Și s-a întâmplat că Astrid Golomb, fiica cea mare a lui Sol Golomb, mi-a făcut cunoștință cu el.

Familia Golomb locuia într-o casă situată în munți, lângă Pasadena. Au avut două fiice: Astrid - puțin mai mare decât mine, o fată ambițioasă de la Hollywood și Beatrice - cam de vârsta și mintea mea științifică. Surorile Golomb organizau adesea petreceri, de obicei la ei acasă. Temele au fost diferite: o petrecere în grădină și crochet cu flamingo și arici (" Câștigătorul va fi cel al cărui costum se potrivește cel mai bine cu tema menționată"), sau o petrecere în stil Stonehenge, cu instrucțiuni scrise în rune. La aceste petreceri s-au încrucișat tineri și nu atât de tineri, inclusiv diverse luminate locale. Și la ei, puțin în lateral, era mereu un omuleț cu o barbă mare, un pic ca un spiriduș și purtând mereu o haină întunecată – Solomon Golomb însuși.

Treptat am aflat ceva despre el. În ce a fost implicat" teoria informaţiei„. Că a lucrat la Universitatea din California de Sud. Că a avut diverse legături vagi, dar aparent de nivel înalt guvernamentali și alte conexiuni. Am auzit despre registrele de schimb, dar nu știam practic nimic despre ele.

Iată ce se întâmplă după un timp:

După cum puteți vedea, registrul de deplasare deplasează întotdeauna biții la stânga, iar alți biți sunt adăugați la dreapta conform unei reguli simple. Secvența de biți pare să fie aleatorie, deși, așa cum se arată în figură, se repetă în cele din urmă. Sol Golomb a găsit o modalitate matematică elegantă de a analiza astfel de secvențe și modul în care se repetă.

Dacă registrul de deplasare are dimensiune n, atunci are 2 n stări posibile (corespunzătoare tuturor secvențelor posibile de 0 și 1 cu o lungime n). Deoarece regulile pentru un registru de deplasare sunt deterministe, orice poziție dată trebuie să convergă întotdeauna către o altă poziție similară. Aceasta înseamnă că numărul maxim posibil de pași prin care poate parcurge registrul de deplasare înainte ca pașii să înceapă să se repete este 2 n(de fapt 2 n- 1, deoarece o poziție cu toate 0-urile nu poate evolua în nimic altceva).

În exemplul de mai sus, registrul de deplasare este de dimensiunea 7 și se va repeta în exact 2 7 - 1 = 127 de pași. Dar care registre de deplasare - cu care aranjamente de tap - vor produce secvențele lungime maxima? Solomon Golomb a început să exploreze această întrebare în vara anului 1954. Iar răspunsul lui a fost simplu și elegant.

Registrul de deplasare de mai sus are ramuri la pozițiile 7, 6 și 1. Saul a reprezentat acest lucru algebric folosind un polinom X 7 + X 6 + 1. Apoi a arătat că secvența generată va fi de lungime maximă dacă acest polinom " ireductibil modulo 2„; prin urmare, nu poate fi factorizat, ceea ce îl face analogul numărului prim al polinoamelor; iar prezența altor proprietăți îl face un „polinom primitiv”. Astăzi, acest lucru este ușor de verificat folosind Mathematica și Wolfram Language:

Pe atunci, în 1954, Saul trebuia să facă totul manual; el a compilat un tabel destul de lung de polinoame primitive corespunzătoare registrelor de deplasare care au produs secvențe de lungime maximă:

Istoricul registrelor de deplasare

Ideea de a menține memorie cu acces aleator prin " linii de întârziere", care transmit impulsuri digitale, datează de la începutul erei computerelor. Până la sfârșitul anilor 1940, astfel de linii de întârziere au fost aplicate digital folosind o serie de tuburi cu vid și au fost numite " registre de deplasare„Nu este încă clar când au fost create primele registre de schimbare cu părere. Este posibil să fi fost la sfârșitul anilor 1940. Cu toate acestea, acest eveniment este încă învăluit în mister, deoarece au fost folosite pentru prima dată în criptografia militară.

Ideea de bază a criptografiei este de a schimba mesajele semnificative, astfel încât să nu poată fi recunoscute; totuși, dacă cunoașteți cheia, puteți recrea mesajul criptat. Așa-numitele cifruri în flux funcționează pe principiul creării de secvențe lungi de elemente aparent aleatorii și sunt decodificate folosind un receptor care generează în mod independent aceeași secvență de elemente.

Registrele cu deplasare cu feedback liniar au fost apreciate în criptografie datorită perioadelor lungi de repetare. Cu toate acestea, analiza matematică folosită de Saul pentru a găsi aceste perioade arată clar că astfel de registre de deplasare nu sunt potrivite pentru criptografie sigură. Cu toate acestea, la început păreau destul de bune (mai ales în comparație cu pozițiile secvențiale ale rotorului din Enigma); au existat zvonuri persistente că criptosistemele militare sovietice au fost construite pe această bază.

În 2001, când lucram la note istorice pentru cartea mea Un nou tip de știință, Saul și cu mine am avut o lungă conversație la telefon despre schimbarea cazurilor. Saul mi-a spus că, atunci când a început, nu știa nimic despre munca criptografică a registrului de schimb. El a spus că oamenii de la Bell Labs, Lincoln Labs și Jet Propulsion Laboratory au început să lucreze la registrele de schimbare cam în același timp cu el; a reușit totuși să meargă puțin mai departe, ceea ce a notat în raportul său din 1955.

În anii următori, Saul a aflat treptat despre diferiți predecesori ai lucrării sale din literatura de matematică pură. Încă din 1202, Fibonacci vorbea despre ceea ce se numesc acum numere Fibonacci, care sunt generate de o relație de recurență (care poate fi considerată analogă cu un registru de deplasare cu feedback liniar, care funcționează pe numere întregi arbitrare, mai degrabă decât pe unu și zero). Există, de asemenea, lucrări mici de la începutul anilor 1900 cu privire la ciclicitatea lui 0 și 1, dar primul studiu la scară largă a fost lucrarea lui Oystein Åre de la Universitatea din Oslo. Ore a avut un student pe nume Marshall Hall care l-a consiliat pe predecesorul Agenției Naționale de Securitate la sfârșitul anilor 1940. - probabil pe tema registrelor de deplasare. Totuși, tot ceea ce a făcut a fost clasificat și, așadar, a aranjat ca Saul să publice istoria registrelor de deplasare cu feedback linear; Saul și-a dedicat cartea lui Marshall Hall.

Pentru ce sunt secvențele generate de registrele de deplasare?

Am observat de multe ori că sistemele definite prin reguli simple sfârșesc cu multe aplicații posibile; De asemenea, registrele de deplasare urmează acest model. Atât hardware-ul modern, cât și software-ul sunt pline de registre de deplasare: un telefon mobil tipic are probabil o duzină sau două dintre ele, de obicei implementate în hardware și, uneori, în software(atunci când scriu „registru de schimbare” aici, mă refer la registru de deplasare cu feedback liniar - LFSR).

În cele mai multe cazuri, acele registre de deplasare care produc secvențe de lungime maximă (cunoscute și sub denumirea de „ secvențe M"). Motivele pentru care sunt folosite în general au de-a face cu unele dintre proprietățile lor pe care le-a descoperit Saul. Ele conțin întotdeauna același număr de 0 și 1 (deși, de fapt, există întotdeauna exact un 1 în plus). Saul a arătat ulterior că ei de asemenea, este obișnuit să aibă același număr de secvențe 00, 01, 10 și 11 - și pentru blocuri mari. Această proprietate " echilibru„Acest lucru în sine este deja foarte util - de exemplu, dacă testați toate combinațiile posibile de biți ca intrare.

Cu toate acestea, Saul a descoperit o altă proprietate, și mai importantă. Înlocuiți fiecare 0 din secvență cu un 1, apoi înmulțiți fiecare element din versiunea deplasată a secvenței cu elementul corespunzător din original. Saul a arătat că atunci când sunt adăugate, aceste elemente vor fi întotdeauna egale cu zero (cu excepția cazurilor în care nu există nicio schimbare). Adică, secvența nu are nicio corelație cu versiunile deplasate ale ei însăși.

Aceste proprietăți vor fi adevărate pentru orice secvență aleatoare suficient de lungă de 0 și 1. În mod surprinzător, pentru secvențe de lungime maximă, aceste proprietăți sunt întotdeauna adevărate. Secvențele au unele trăsături haotice, dar de fapt nu sunt haotice deloc: au o structură bine definită, organizată.

Această structură inerentă registrelor de deplasare cu feedback liniar le face nepotrivite pentru criptografia serioasă. Dar sunt grozave pentru „permutarea elementului” de bază și criptografia cu costuri reduse și sunt utilizate pe scară largă în aceste scopuri. Adesea sarcina este pur și simplu să „albiți” semnalul (ca în „zgomotul alb”). Uneori trebuie să transmiteți date cu secvențe lungi de 0. Dar în acest caz, electronica poate deveni confuză dacă „tăcerea” este prea lungă. Puteți evita această problemă prin amestecarea datelor originale combinându-le cu secvența generată de registrul de deplasare. Este exact ceea ce s-a făcut cu Wi-Fi, Bluetooth, USB, TV digital, internet etc.

Un efect secundar al amestecării registrelor de schimbare este decodarea mai complexă, care este uneori folosită pentru a îmbunătăți securitatea (tehnologia DVD utilizează o combinație de registre de deplasare pe 16 și 24 de biți pentru a codifica datele; multe telefoane GSM folosesc o combinație de trei registre de deplasare pentru codifică toate semnalele).

Saul a creat baza matematică pentru toate acestea și a introdus, de asemenea, o serie de figuri cheie unul altuia. Încă din 1959, l-a cunoscut pe Irwin Jacobs, care și-a primit recent doctoratul de la MIT. Îl cunoștea și pe Andy Viterbi, care lucra la Jet Propulsion Laboratory. Saul le-a prezentat și în 1968 au înființat o companie numită Linkabit, care lucrează la sisteme de codare (în special în scopuri militare).

În 1985, Jacobs și Viterbi au fondat o altă companie numită Qualcomm. La început nu se descurcau foarte bine, dar la începutul anilor 1990, când au început să producă componente pentru a implementa CDMA în celulare, compania a început să crească rapid.

Deci unde sunt aceste registre?

Este surprinzător că majoritatea oamenilor nu au auzit niciodată de registrele de deplasare și totuși interacționează cu ele de fiecare dată când le folosesc sisteme moderne comunicații, tehnologie informatică etc. Aici este ușor să se confunde, având în vedere că în spatele unor nume și abrevieri diferite se află aceleași secvențe de registre de deplasare cu feedback liniar (PN, pseudozgomot, secvențe M-, FSR, LFSR, MLS, SRS). , PRBS etc.).

Când vine vorba de telefoane mobile, utilizarea lor a secvențelor generate de registrul de schimbare a variat de-a lungul anilor, crescând și descrezând. rețelele se bazează pe TDMA, deci nu folosesc secvențe generate de registrele de deplasare pentru a-și codifica datele, dar încă folosesc adesea CRC (cod de redundanță ciclică) pentru a verifica blocurile de date. rețelele sunt cei mai mari utilizatori de CDMA, astfel încât secvențele generate de registrele de deplasare sunt implicate în transmiterea fiecărui bit. rețelele folosesc de obicei o combinație de intervale de timp și frecvență care nu includ secvențe de registru de deplasare, deși CRC-urile sunt încă folosite: de exemplu, pentru a interacționa cu date integrale atunci când ferestrele de frecvență se suprapun. are o structură mai complexă - cu antene multiple care se adaptează dinamic pentru a utiliza timpul și frecvența optime a sloturilor. Cu toate acestea, jumătate din canalele lor sunt de obicei alocate „semnalelor pilot” care sunt utilizate pentru a deduce mediul radio local; se bazează şi pe secvenţe generate de registrele de deplasare.

În producția de electronice, de obicei încercăm să obținem cel mai mult de mare viteză transmisie de date cu un consum minim de energie, permițând biților să depășească pragul de zgomot. Și, de regulă, această cale duce la automatizarea detectării erorilor - și, prin urmare, la utilizarea CRC (cod de redundanță ciclică) și, prin urmare, la secvențe generate de registrul de deplasare. Acest lucru se aplică aproape tuturor tipurilor de magistrale din interiorul unui computer (PCIe, SATA etc.): asigurarea interacțiunii între părțile procesorului central sau primirea datelor de la dispozitive sau conectarea la un afișaj cu HDMI. În cazul discurilor sau al memoriei, CRC și alte coduri bazate pe secvențe generate de registrele de deplasare sunt, de asemenea, folosite aproape universal pentru a funcționa la viteză maximă.

Registrele de deplasare sunt atât de omniprezente încât este aproape imposibil de estimat câți biți generează. Există aproximativ 10 miliarde de computere, puțin mai puține telefoane și un număr mare de dispozitive în IoT încorporat („Internet of Things”). Aproape fiecare mașină din lume (și există mai mult de un miliard dintre ele!) are aproximativ 10 microprocesoare încorporate.

La ce frecvență funcționează registrele de deplasare? Sistemele de comunicații au o frecvență purtătoare de bază în intervalul de herți, precum și o „rată de cip” care arată cât de repede se realizează accesul multiplu (vorbim despre CDMA) în intervalul MHz. Pe de altă parte, în autobuzele din interiorul computerelor, toate datele sunt transferate folosind registre de deplasare - cu cea mai buna viteza transmisii în intervalul hertzi.

Există cel puțin 10 miliarde de linii de comunicație care rulează timp de cel puțin 1/10 miliarde de secunde (aproximativ 3 ani) care folosesc cel puțin 1 miliard de biți din registrele de deplasare în fiecare secundă, ceea ce înseamnă că până în prezent algoritmul lui Saul a fost folosit de cel puțin un octilion de ori. .

Este acesta cel mai des folosit algoritm? Cred ca da. Bănuiesc că numai operațiile aritmetice pot concura. În zilele noastre, procesoarele sunt capabile să efectueze un trilion de operații aritmetice pe secundă și astfel de operațiuni sunt necesare pentru aproape fiecare bit generat de un computer. Dar cum se face aritmetica? La un anumit nivel, aceasta este pur și simplu implementarea electronicii digitale.

Cu toate acestea, există „idei algoritmice” care rămân neclare pentru toată lumea, cu excepția designerilor de microprocesoare. Când Babbage și-a făcut diferența motorul (a se vedea articolul despre Habré „Dezvăluirea poveștii lui Ada Lovelace (primul programator din istorie)”), transporturile au devenit o piedică majoră în efectuarea operațiilor aritmetice (de fapt, un registru de deplasare cu feedback liniar poate fi considerat ca un sistem care face ceva de genul calculelor aritmetice, dar nu se reportează). Există „arbori de propagare a semnalului de transfer” care optimizează transferul. Există, de asemenea, mici trucuri (cum ar fi „Algoritmul Booth”, „Arborii Wallace”, etc.) care reduc numărul de operații pe biți necesare pentru a crea „internele” aritmeticii. Dar, spre deosebire de registrele de deplasare cu feedback liniar, pur și simplu nu există o idee algoritmică unică care să poată fi folosită aproape oriunde; deci cred că cele mai lungi secvențe generate de registrele de deplasare cu feedback liniar câștigă în continuare printre cele mai utilizate secvențe.

Automate celulare și registre de deplasare cu feedback neliniar

Deși poate să nu pară evident la prima vedere, se pare că există o legătură strânsă între registrele de schimbare a feedback-ului și automatele celulare pe care le-am studiat de mulți ani. Organizarea de bază pentru un registru de schimbare a feedback-ului este de a evalua câte un bit. Într-un automat celular, există o linie de celule și, la fiecare pas, toate celulele sunt actualizate în paralel, pe baza unei reguli care depinde, de exemplu, de valorile celor mai apropiați vecini.

Pentru a vedea cum sunt legate, trebuie să rulați un registru de schimbare a feedback-ului de dimensiune n, și, în același timp, afișează starea sa numai fiecare n trepte; cu alte cuvinte, lăsați toți biții să fie rescrise înainte de a apărea din nou. Dacă fiecare pas al unui registru de deplasare cu feedback liniar este mapat (aici cu două atingeri), atunci la fiecare pas totul se va deplasa spre stânga - asta este. Dar dacă faci o imagine comprimată, arătând numai fiecare n pași, un model va deveni vizibil.

Acesta este un model imbricat; iar această imagine este foarte asemănătoare cu cea care poate fi obținută dacă un automat celular ia o celulă și vecinul ei și le adaugă modulo 2 (XOR). Iată ce se întâmplă cu un automat celular dacă își aranjează celulele astfel încât acestea să fie într-un cerc de aceeași dimensiune ca registrul de deplasare de mai sus:

La început, automatele celulare și tiparele registrului de schimbare se dovedesc a fi exact aceleași. Dacă te uiți la aceste imagini, devine mai puțin surprinzător că matematica registrelor de deplasare ar trebui să aibă ceva de-a face cu automatele celulare. Și având în vedere repetabilitatea modelelor imbricate, este clar de ce trebuie să existe o teorie matematică elegantă pentru registrele de deplasare.

Registrele de deplasare tipice utilizate în practică nu au astfel de modele care se repetă în mod clar. Iată câteva exemple de registre de deplasare care generează secvențe de lungime maximă. Faptul este că ramurile sunt îndepărtate, ceea ce face dificilă găsirea de urme vizuale de cuibărit.

Cât de largă este corespondența dintre registrele de deplasare și automatele celulare? Pentru automatele celulare, regulile pentru generarea de noi valori de celule pot fi orice. În registrele de deplasare cu feedback liniar, acestea ar trebui să se bazeze întotdeauna pe adăugarea modulo 2 (sau XOR). Aceasta este ceea ce înseamnă partea „liniară” a unui „registru de deplasare cu feedback liniar”. De asemenea, este posibil să utilizați orice regulă pentru a combina valorile pentru registrele de deplasare cu feedback neliniar (NFSR).

Într-adevăr, când Saul și-a dezvoltat teoria pentru registrele de deplasare cu feedback liniar, a început cu cazul neliniar. Când a ajuns la JPL în 1956, a primit un laborator complet cu rafturi pentru module electronice mici. Saul a spus că modulele (fiecare cam de dimensiunea unui pachet de țigări) au fost construite pentru un proiect Bell Labs pentru a efectua o anumită operație logică (ȘI, SAU, NU, ...). Modulele pot fi folosite împreună pentru a implementa orice registre de deplasare a feedback-ului neliniar dorit, oferind aproximativ un milion de biți pe secundă (Saul mi-a spus că cineva a încercat să facă același lucru folosind un computer mainframe, iar asta a durat 1 secundă când a folosit module hardware, a fost necesar. 6 săptămâni de lucru pe un computer universal).

Când Saul a început să studieze registrele de schimbare a feedback-ului linear, prima sa descoperire majoră au fost perioadele lor de repetiție. Și în cazul celor neliniare, el și-a dedicat majoritatea eforturilor încercării de a înțelege același lucru. A adunat tot felul de date experimentale. Mi-a spus că a testat chiar și secvențe lungi de 2 45, care au durat un an. A făcut un rezumat ca în imaginea de mai jos (observați vizualizarea secvențelor afișate pe linia formei de undă). Dar nu a reușit niciodată să vină cu vreunul teorie generală, pe care o avea pentru registrele de deplasare cu feedback liniar.

Nu e de mirare că nu a putut să o facă. Încă din anii 1950, au existat rezultate teoretice (în mare parte bazate pe ideile lui Turing despre calculul universal) despre programele care ar putea, în principiu, să facă acest lucru. Nu cred că Saul sau oricine altcineva s-au gândit vreodată că registrele de deplasare cu feedback neliniar ar folosi funcții foarte simple (neliniare).

Și abia mai târziu a devenit clar cât de complex este comportamentul chiar și foarte programe simple. Exemplul meu preferat este Regula 30 pentru un automat celular, în care valorile celulelor învecinate sunt combinate folosind o funcție care poate fi reprezentată ca R + q + r + q*r mod 2(sau R XOR ( q SAU r)). Incredibil, Saul se gândea la registre neliniare de schimbare a feedback-ului bazate pe funcții similare: R + G + s + q*r + q*s + r*s mod 2. Iată mai jos ilustrații ale funcției lui Saul (care poate fi considerată „regula 29070”), regula 30 și alte câteva reguli similare într-un registru de schimbare:

Și aici ele, nelimitate de un registru de dimensiune fixă, arată ca niște automate celulare:

Desigur, Saul nu a făcut niciodată astfel de imagini (și era aproape imposibil de făcut în anii 1950). În schimb, s-a concentrat pe perioada de repetiție ca pe un fel de caracteristică agregată.

Saul se întreba dacă registrele de deplasare cu feedback neliniar ar putea fi surse de haos. Din ceea ce se știe în prezent despre automatele celulare, este clar că pot. De exemplu, pentru a crea haos pentru Mathematica, am folosit regula celor 30 de automate celulare timp de 25 de ani (deși recent am abandonat-o în favoarea unui regula eficienta, pe care l-am găsit după ce am explorat trilioane de posibilități).

Saul nu a vorbit prea mult despre criptare; deși cred că a lucrat pentru guvern doar pentru o perioadă scurtă de timp. Mi-a spus că, deși în 1959 a descoperit " atacuri de corelație multidimensională asupra secvențelor neliniare„în același timp el” a evitat cu grijă afirmațiile că programul era pentru criptoanaliza„Ideea este că regula 30 pentru automatele celulare (și poate și registrele neliniare cu deplasare cu feedback) pot fi criptosisteme bune - deși datorită faptului că sunt aparent echivalente cu registrele cu deplasare cu feedback liniar (ceea ce nu este așa), nu au fost niciodată folosite. cat mai mult posibil.

Ca un entuziast, în ultimele decenii am încercat să studiez toți predecesorii lucrării mele despre automatele celulare unidimensionale. Automatele celulare bidimensionale au fost puțin studiate, dar în cazul automatelor celulare unidimensionale s-a găsit o singură lucrare pur teoretică. Mă gândesc la toate lucrurile pe care le-am văzut, registrele neliniare de schimbare a feedback-ului lui Solomon Golomb au fost cele mai apropiate de ceea ce am ajuns să fac un sfert de secol mai târziu.

Polyomino

Auzind numele " Golomb „, mulți își vor aminti registrele de deplasare. Cu toate acestea, majoritatea își vor aminti poliomino. Saul nu a inventat poliominoe, deși a venit cu numele. El a făcut sistematic ceea ce apărea anterior doar în puzzle-uri individuale.

Principala întrebare la care Saul era interesat să răspundă a fost cum ar putea fi organizate seturi de poliomino pentru a acoperi o anumită zonă. Uneori este destul de evident, iar uneori destul de dificil. Saul a publicat prima lucrare despre poliomino în 1954, dar Martin Gardner a fost cel care a făcut cu adevărat poliominoele populare în 1957 (a scris o rubrică despre jocurile matematice în revistă științific american). După cum a explicat Saul în prefața cărții sale din 1964, rezultatul a fost „ un flux constant de corespondenți din întreaga lume și din toate categoriile sociale: președinți ai consiliilor de administrație ale universităților de top, rezidenți ai mănăstirilor necunoscute, prizonieri din închisori celebre...".

Companiile de jocuri au luat în seamă noile puzzle-uri și în câteva luni au apărut titluri precum „ noi puzzle-uri senzaționale", urmată de zeci de ani de alte puzzle-uri și jocuri pe bază de poliomino (nu, tipul chel înfiorător nu seamănă cu Saul):

Saul a continuat să publice articole despre poliomino încă 50 de ani de la prima publicare. În 1961, el a introdus „rep-tile” care ar putea fi folosite pentru a crea modele fractale („Infin-tile”). Dar aproape tot ce a făcut Saul cu poliominoi implica rezolvarea unor probleme specifice.

Mă interesează puțin specificul poliominoelor; Sunt interesat de fenomenele mai generale asociate acestora. Se pare că se poate decide cu câteva forme simple Este ușor să „pavezi” întregul avion. Dar cu poliominoe (și toate jocurile și puzzle-urile bazate pe ele), este clar că lucrurile nu sunt atât de simple. Și într-adevăr, în anii 1960 s-a dovedit că această problemă este teoretic de nerezolvat.

Dacă ne interesează doar o zonă limitată, atunci, în principiu, putem enumera pur și simplu toate aranjamentele imaginabile ale figurilor și apoi să vedem dacă sunt aranjate așa cum ar trebui. Cu toate acestea, dacă suntem interesați de infinit, atunci acest lucru nu trebuie făcut. Poate cineva va găsi o modalitate de a plasa cu succes un milion de cifre, dar nu există nicio garanție că acest rezultat poate fi extins și mai mult.

Se pare că ar putea arăta ca o mașină Turing funcțională - sau un automat celular. Începi cu o linie de plăci. Atunci întrebarea dacă este posibilă placarea infinită este echivalentă cu întrebarea dacă este posibil să se instaleze o mașină Turing care să îi permită să nu se oprească. Ideea este că, dacă o mașină Turing este universală (adică poate fi programată pentru a efectua orice calcul posibil), atunci problema de oprire a acesteia poate fi indecidabilă, ceea ce înseamnă că și problema de tiling va fi indecidabilă.

Desigur, acest lucru depinde de setul original de formulare. Întrebarea este cât de complexe trebuie să fie formele pentru a codifica calculele universale și pentru a duce la o problemă de țiglare de nerezolvat. Solomon Golomb cunoștea literatura pe această temă, dar nu era deosebit de interesat de ea.

Se știe că seturi complexe și atent proiectate de poliominoe suportă de fapt calculul universal. Dar ce zici de un set simplu? Este într-adevăr suficient de simplu pentru a fi dat din întâmplare? Dacă te uiți la toate sistemele pe care le-am studiat, cel mai simplu set se dovedește cu adevărat simplu. Cu toate acestea, este greu de găsit.

O problemă mult mai simplă este să găsești poliomino care să umple cu succes avioanele, deși doar neperiodic. Roger Penrose a găsit un exemplu potrivit în 1994. În cartea mea Un nou tip de știință Am dat un exemplu puțin mai simplu cu 3 poliominoe:

Restul poveștii

Saul avea treizeci de ani când a obținut un succes notabil în domeniul registrelor de deplasare și al poliominoelor... Era o persoană foarte activă. A scris câteva sute de lucrări, dintre care unele au extins lucrările sale anterioare, dintre care unele erau răspunsuri la întrebările care i se adresase, iar unele au fost scrise, se pare, doar pentru distracție - pentru a afla lucruri interesante despre numere, secvențe. , criptosisteme etc. d.

Registrele de deplasare și poliominoele sunt subiecte extinse (sunt chiar clasificate în categorii separate în clasificarea AMS). În ultimele decenii, amândoi au primit o nouă rundă de dezvoltare când au început să fie efectuate experimente pe calculator pe baza lor; Sol a participat activ la ele. Cu toate acestea, multe întrebări rămân fără răspuns. Și dacă pot fi găsite matrici mari Hadamard pentru registrele de deplasare cu feedback liniar, atunci chiar și acum se știe puțin despre registrele de deplasare cu feedback neliniar, ca să nu mai vorbim de toate poliominoele neperiodice și alte exotice.

Saul a fost întotdeauna interesat de puzzle-uri, atât puzzle-uri matematice, cât și cu cuvinte. De ceva vreme a scris o coloană puzzle pentru Los Angeles Timesși timp de 32 de ani a scris „ Gambiturile lui Golomb" în revista pentru absolvenți de la Johns Hopkins. A luat parte la testarea MegaIQ și a câștigat o excursie la Casa Albă când el și șeful său s-au clasat printre primele cinci din țară.

A investit un efort enorm în munca sa la universitate: nu numai că a predat studenți și a supervizat studenți absolvenți și a urcat pe scara administrativă (președinte al consiliului universitar, prorector pentru cercetare etc.), dar și-a exprimat și opiniile cu privire la managementul universitatea în ansamblu (de exemplu, a scris un articol intitulat „Consultanța facultății: îndepărtați sau părăsiți?”; Răspuns: nu, este bine pentru universitate!). La Universitatea din California de Sud, a fost un vânător de capete, iar în timpul petrecut acolo, a ajutat universitatea să se ridice din obscuritate în fruntea clasamentului programelor educaționale.

Și apoi a fost consultanță. Saul a fost meticulos și nu a dezvăluit ce a făcut pentru organizațiile guvernamentale. La sfârșitul anilor 1960, frustrat că toată lumea, în afară de el, vindeau jocuri poliomino, Saul a fondat o companie pe care a numit-o Recreational Technology, Inc. Lucrurile nu mergeau prea bine, dar Saul l-a cunoscut pe Alvin Berlekamp, un profesor din Berkeley care era interesat de teorii de codificare și puzzle-uri. Ulterior au fondat compania Cyclotomics (în cinstea polinoamelor ciclotomice de forma X n– 1), care a fost vândut în cele din urmă către Kodak pentru o sumă ordonată (Berlekamp a creat și un sistem de tranzacționare algoritmică, pe care l-a vândut apoi lui Jim Simons și care a devenit punctul de plecare pentru Renaissance Technologies, unul dintre cele mai mari fonduri speculative de astăzi).

Peste 10.000 de brevete sunt legate într-un fel sau altul de opera lui Saul, dar Saul însuși a primit doar un singur brevet pe criptosisteme bazate pe cvasi-grup - și cred că a făcut puțin pentru a-și comercializa munca.

Timp de mulți ani, Saul a lucrat cu Technion, un institut israelian de tehnologie. El a vorbit despre el ca „ evreu ortodox nereligios„, dar, în același timp, a predat uneori seminarii despre Cartea Genezei pentru începători și a lucrat și la descifrarea părților din Manuscrisele de la Marea Moartă (manuscrisele Qumran).

Saul și soția sa au călătorit mult, dar „centrul lumii” al lui Saul a fost cu siguranță biroul lui din Los Angeles, la Universitatea din California de Sud, și casa în care el și soția sa au locuit timp de aproape 60 de ani. A fost mereu înconjurat de prieteni și studenți. Și avea o familie. Fiica sa Astrid a jucat rolul unui student într-o piesă despre Richard Feynman (ea a pozat pentru el) și în romanul unui prieten ca unul dintre personaje. Beatrice și-a dedicat cariera aplicării unui nivel matematic de precizie diferitelor tipuri de afecțiuni și diagnostice medicale (boli legate de Războiul din Golf, efectele statinelor, sughiț etc.). Am adus chiar și o mică contribuție la viața Beatricei, prezentându-i bărbatului care mai târziu i-a devenit soț - Terry Sejnowski, unul dintre fondatorii neuroștiinței computaționale moderne.

Saul părea implicat în multe lucruri, chiar dacă nu vorbea prea mult despre detalii. Din când în când am vrut să vorbesc cu el despre știință și matematică, dar el era mai interesat să spună povești (deseori foarte incitante) atât despre indivizi cât și despre organizații (" Îți vine să crezi că [în 1985], după ani de absență de la conferințe, Claude Shannon a apărut pur și simplu neanunțat la bar la conferința anuală de teoria informației?"; "știi cât au trebuit să plătească șefului de la Caltech pentru a-l face să plece în Arabia Saudită?", etc.).

Privind în urmă, îmi dau seama că mi-ar fi plăcut să-l interesez pe Saul să rezolve unele dintre întrebările matematice ridicate în munca mea. Nu cred că mi-am dat seama vreodată în ce măsură îi plăcea să rezolve problemele propuse de alți oameni. În ciuda contribuțiilor sale semnificative la infrastructura lumii computerelor, Saul însuși nu a folosit niciodată în mod serios computerele. Era foarte mândru de faptul că putea face cu ușurință calcule în capul lui. Până la 70 de ani, nu a folosit e-mailul și nu a folosit niciodată un computer acasă, totuși telefon mobil el a avut (obișnuit E-mail aproape nimic nu venea de la el. Am menționat odată că în urmă cu aproximativ un an studiam povestea Adei Lovelace; el a raspuns: " Povestea Adei Lovelace ca programatoare a lui Babbage este atât de răspândită încât toată lumea pare să o accepte ca pe un fapt, dar nu am văzut niciodată surse pe acest subiect.").

Fiicele lui Saul au organizat o petrecere de 80 de ani în urmă cu câțiva ani și au creat aceste invitații interesante:

Sol a avut unele probleme de sănătate, deși acest lucru nu părea să-i afecteze foarte mult ritmul de viață. Starea de sănătate a soției sale se înrăutățise, destul de brusc în ultimele săptămâni. Vineri, Saul s-a dus la birou ca de obicei, iar sâmbătă seara a murit în somn. Soția lui Bo i-a supraviețuit cu doar două săptămâni și a murit cu doar două zile înainte de a 60-a aniversare a nunții.

Deși Saul a dispărut, munca lui continuă să trăiască în octlioane de biți în lumea digitală.

La revedere Sol. Și de la noi toți - mulțumesc.

Într-un registru de deplasare cu feedback liniar, există două părți (module): registrul de deplasare în sine și circuitele (sau subprogramele) care calculează valoarea bitului împins. Un registru constă din celule funcționale (sau biți ai unui cuvânt mașină sau mai multe cuvinte), fiecare dintre ele stochează starea curentă a unui bit. Numărul de celule se numește lungimea registrului. Biții (celulele) sunt de obicei numerotați cu numere, fiecare dintre acestea fiind capabil să stocheze un bit, iar bitul calculat este împins în celulă, iar următorul bit generat este eliminat din celulă. Calculul bitului care trebuie împins se face de obicei înainte ca registrul să fie deplasat și numai după deplasare este plasată în celulă valoarea bitului calculat.

Perioada registrului de deplasare este lungimea minimă a secvenței rezultate înainte de a începe să se repete. Deoarece un registru de celule de biți are doar stări diferite de zero, atunci, în principiu, perioada registrului nu poate depăși acest număr. Dacă perioada de înregistrare este egală cu acest număr, atunci un astfel de registru se numește registru de perioadă maximă.

Pentru LFSR, funcția de feedback este o funcție booleană liniară a stărilor tuturor sau a unora dintre biții de registru. De exemplu, suma modulo doi sau inversarea sa logică este o funcție booleană liniară (operație XOR, notată în formule ca ) și este folosită cel mai adesea în astfel de registre.

Mai mult, acele biți care sunt variabilele funcţiei feedback este de obicei numit curbe.

Controlul registrului în implementările hardware se realizează prin aplicarea unui impuls de deplasare (denumit altfel ceas sau puls de sincronizare) la toate celulele, în software - prin executarea unui ciclu software, inclusiv calcularea funcției de feedback și deplasarea biților într-un cuvânt.

În fiecare pas de timp sunt efectuate următoarele operații:

Registru de schimbare linear cu feedback

Astfel, operația logică XOR (SAU exclusiv) este luată ca funcție de feedback, adică:

Proprietățile polinoamelor primitive

Proprietăți

Proprietățile secvenței produse de LFSR sunt strâns legate de proprietățile polinomului asociat. Se numesc coeficienții săi diferit de zero curbe, precum și celulele de registru corespunzătoare care furnizează valorile argumentelor funcției de feedback.

Complexitate liniară

Complexitatea liniară a unei secvențe binare este una dintre cele mai multe caracteristici importante RSLOS funcționează. Să introducem următoarea notație:

Definiție

Complexitatea liniară a unei secvențe binare infinite se numește număr, care este definit după cum urmează:

Complexitatea liniară a unei secvențe binare finite se numește număr egal cu lungimea celui mai scurt LFSR care generează o secvență având ca primii termeni .

Proprietăți ale complexității liniare

Fie și fie șiruri binare. Apoi:

Independența corelației

Pentru a obține o complexitate liniară ridicată, criptografii încearcă să combine în mod neliniar rezultatele secvențelor multiple de ieșire. În acest caz, pericolul este că una sau mai multe secvențe de ieșire (adesea chiar și ieșirile LFSR-urilor individuale) pot fi conectate printr-un flux de chei comune și deschise folosind algebră liniară. Hackingul bazat pe o astfel de vulnerabilitate se numește autopsie de corelație. Thomas Siegenthaler a arătat că este posibil să se precizeze independența corelației cu precizie și că există un compromis între independența corelației și complexitatea liniară.

Ideea principală a unui astfel de hack este de a detecta o anumită corelație între ieșirea generatorului și ieșirea uneia dintre componentele sale. Apoi, prin observarea secvenței de ieșire, se pot obține informații despre această ieșire intermediară. Folosind aceste informații și alte corelații, datele pot fi colectate pe alți pini intermediari până când generatorul este compromis.

Atacurile de corelație sau variațiile, cum ar fi atacurile de corelație rapide care implică un compromis între complexitatea computațională și eficiență, au fost utilizate cu succes împotriva multor generatoare de fluxuri de chei cu registru cu deplasare cu feedback liniar.

Exemplu

Pentru SFLOS cu un polinom asociat, secvența generată are forma . Să presupunem că înainte de începerea procesului secvența este scrisă în registru, apoi perioada fluxului de biți generat va fi egală cu 7 cu următoarea secvență:

Numărul pasului	Stat	Bit generat
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

Deoarece starea internă la pasul al șaptelea a revenit la starea inițială, atunci, începând de la pasul următor, va exista o repetare. Cu alte cuvinte, perioada secvenței s-a dovedit a fi egală cu 7, ceea ce s-a produs datorită caracterului primitiv al polinomului.

Algoritmi pentru generarea de polinoame primitive

Mesele gata

Calcularea primitivității unui polinom este o problemă matematică destul de complexă. Prin urmare, există tabele gata făcute care arată numărul de secvențe de tape care oferă perioada maximă a generatorului. De exemplu, pentru un registru cu deplasare pe 32 de biți există secvența . Aceasta înseamnă că pentru a genera un nou bit, trebuie să adăugați biții 31, 30, 29, 27, 25 și 0 folosind funcția XOR. Codul pentru astfel de RLOS în limbajul C este următorul:

Int LFSR (void) ( static fără semn lung S = 1; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 )<< 31 ) | (S>> 1); întoarcere S & 1 ; )

Implementările software ale generatoarelor LFSR sunt destul de lente și funcționează mai rapid dacă sunt scrise mai degrabă în asamblator decât în limbaj C. O soluție este să utilizați 16 RSLOS în paralel (sau 32, în funcție de lungimea cuvântului din arhitectura unui anumit computer). Într-o astfel de schemă, este utilizată o matrice de cuvinte, a căror dimensiune este egală cu lungimea LFSR, iar fiecare bit al unui cuvânt din matrice se referă la propriul său LFSR. Cu condiția ca aceleași numere de secvență de atingere să fie utilizate, acest lucru poate oferi un câștig de performanță vizibil. [nevoie de un exemplu de cod] (Vezi: bitslice).

Configurația Galois

Configurația Galois a unui registru de deplasare cu feedback liniar

Circuitul de feedback poate fi de asemenea modificat. În acest caz, generatorul nu va avea o putere criptografică mai mare, dar va fi mai ușor de implementat în software. În loc să folosească bitul cel mai din stânga al secvenței de atingere pentru a genera noul bit cel mai din stânga, acesta XOR face fiecare bit al secvenței de atingere cu ieșirea generatorului și îl înlocuiește cu rezultatul acelei acțiuni, apoi ieșirea generatorului devine noul partea din stânga. În C arată așa:

Int LFSR (void) ( static lung fără semn Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; )

Avantajul este că toate XOR sunt efectuate într-o singură operație.

se poate dovedi că configurația Fibonacci dată mai întâi și configurația Galois dată aici dau aceleași secvențe (lungime 2 32 −1), dar deplasate în fază una de cealaltă
o buclă cu un număr fix de apeluri la funcția LFSR în configurația Galois rulează aproximativ de două ori mai repede decât în configurația Fibonacci (compilatorul MS VS 2010 pe Intel Core i5)
Rețineți că în configurația Galois ordinea biților din cuvântul care definește feedback-ul este inversată în comparație cu configurația Fibonacci

Exemple de generatoare

Generatoare stop-and-go

Generator alternativ stop-go

Acest oscilator folosește ieșirea unui LFSR pentru a controla frecvența de ceas a altui LFSR. Ieșirea ceasului RSLOS-2 este controlată de ieșirea RSLOS-1, astfel încât RSLOS-2 își poate schimba starea la momentul t numai dacă ieșirea RSDOS-1 la momentul t-1 a fost egală cu unu. Dar această schemă nu a putut rezista disecției corelaționale.

Prin urmare, a fost propus un generator îmbunătățit bazat pe aceeași idee. Se numește generator alternativ stop-go. Utilizează trei LFSR-uri de lungimi diferite. RSLOS-2 este tactat atunci când ieșirea RSLOS-1 este egală cu unu, iar RSLOS-3 este tactat atunci când ieșirea RSLOS-1 este egală cu zero. Ieșirea generatorului este suma modulo 2 a RSLOS-2 și RSLOS-3. Acest generator are o perioadă lungă și o complexitate liniară mare. Autorii săi au arătat, de asemenea, o metodă de deschidere corelativă a RSLOS-1, dar aceasta nu slăbește foarte mult generatorul.

cascada Gollmann

Cascada Gollmann este o versiune îmbunătățită a generatorului stop-go. Este alcătuit dintr-o secvență de LFSR-uri, a căror sincronizare este controlată de LFSR-ul anterior. Dacă ieșirea RSLOS-1 la momentul t este 1, atunci RSLOS-2 este tactat. Dacă ieșirea lui RSLOS-2 la momentul t este 1, atunci RSLOS-3 este tactat și așa mai departe. Ieșirea ultimului LFSR este ieșirea generatorului. Dacă lungimea tuturor LFSR-urilor este aceeași și egală cu n, atunci complexitatea liniară a unui sistem de k LFSR-uri este egală cu .

Această idee este simplă și poate fi folosită pentru a genera secvențe cu perioade uriașe, complexități liniare mari și proprietăți statistice bune. Dar, din păcate, sunt sensibile la deschidere, numită „blocare”. Pentru o durabilitate mai mare, se recomandă utilizarea k de cel puțin 15. Mai mult, este mai bine să folosiți mai multe SFSR scurte decât mai puține SFSR lungi.

Generator de prag

Acest generator încearcă să ocolească problemele de securitate găsite în generatoarele anterioare de către număr variabil registre de deplasare. În teorie, atunci când se utilizează un număr mai mare de registre de deplasare, complexitatea cifrului crește, ceea ce s-a făcut în acest generator.

Acest generator este format dintr-un număr mare de registre de deplasare, ale căror ieșiri sunt alimentate la funcția de majorare. Dacă numărul de unități la ieșirile registrelor este mai mare de jumătate, atunci generatorul scoate unul. Dacă numărul de zerouri la ieșiri este mai mare de jumătate, atunci generatorul emite zero. Pentru ca compararea numărului de zerouri și unități să fie posibilă, numărul de registre de deplasare trebuie să fie impar. Lungimile tuturor registrelor trebuie să fie relativ prime, iar polinoamele de feedback trebuie să fie primitive, astfel încât perioada secvenței generate să fie maximă.

Pentru cazul a trei registre de deplasare, generatorul poate fi reprezentat astfel:

Acest generator este similar cu generatorul Geff, cu excepția faptului că generatorul de prag are o complexitate mai liniară. Complexitatea sa liniară este:

unde , , sunt lungimile primului, al doilea și al treilea registre de deplasare.

Dezavantajul său este că fiecare bit de ieșire oferă unele informații despre starea registrului de deplasare. Sau mai degrabă, 0,189 biți. Prin urmare, este posibil ca acest generator să nu poată rezista unui atac de corelație.

Alte tipuri

Auto-subțierea

Generatoarele autodecimante sunt cele care își controlează propria frecvență. Au fost propuse două tipuri de astfel de generatoare. Primul constă dintr-un registru de deplasare cu feedback liniar și unele circuite care tac registrul în funcție de valorile de ieșire ale registrului de deplasare. Dacă ieșirea SFSR este egală cu unu, atunci registrul este tactat de de ori. Dacă ieșirea este zero, atunci registrul este tactat de k ori. Al doilea are aproape același design, dar ușor modificat: în circuitul de ceas, intrarea, ca verificare pentru 0 sau 1, nu este semnalul de ieșire în sine, ci XOR al anumitor biți ai registrului de deplasare cu feedback liniar. Din păcate, acest tip de generator nu este sigur.

Oscilator cu mai multe viteze cu produs interior

Acest oscilator folosește două registre de deplasare cu feedback linear cu frecvențe de ceas diferite: RSLOS-1 și RSLOS-2. Frecvența de ceas a RSLOS-2 este de de ori mai mare decât RSLOS-1. Biții individuali ai acestor registre sunt combinați folosind operația AND. Ieșirile operației AND sunt apoi redate XOR. Secvența de ieșire este preluată din acest bloc XOR. Din nou, acest generator nu este impecabil (Nu a rezistat descoperirii consistenței liniare. Dacă - lungimea SFOS-1, - lungimea SFOS-2 și d este raportul frecvențele de ceas, atunci starea internă a generatorului poate fi obținută dintr-o secvență de ieșire de lungime ), dar are o complexitate liniară mare și caracteristici statistice excelente.

În acest caz, acei biți care sunt variabile ale funcției de feedback sunt de obicei numiți curbe.

În fiecare pas de timp sunt efectuate următoarele operații:

Registru de schimbare linear cu feedback

Astfel, operația logică XOR (SAU exclusiv) este luată ca funcție de feedback, adică:

Proprietățile polinoamelor primitive

Proprietăți

Complexitate liniară

Complexitatea liniară a unei secvențe binare este una dintre cele mai importante caracteristici ale funcționării LFSR. Să introducem următoarea notație:

Definiție

Complexitatea liniară a unei secvențe binare infinite se numește număr, care este definit după cum urmează:

Complexitatea liniară a unei secvențe binare finite se numește număr egal cu lungimea celui mai scurt LFSR care generează o secvență având ca primii termeni .

Proprietăți ale complexității liniare

Fie și fie șiruri binare. Apoi:

Independența corelației

Exemplu

Numărul pasului	Stat	Bit generat
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

Algoritmi pentru generarea de polinoame primitive

Mesele gata

Int LFSR (void) ( static fără semn lung S = 1; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 )<< 31 ) | (S>> 1); întoarcere S & 1 ; )

Configurația Galois

Configurația Galois a unui registru de deplasare cu feedback liniar

Int LFSR (void) ( static lung fără semn Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; )

Avantajul este că toate XOR sunt efectuate într-o singură operație.

se poate dovedi că configurația Fibonacci dată mai întâi și configurația Galois dată aici dau aceleași secvențe (lungime 2 32 −1), dar deplasate în fază una de cealaltă
o buclă cu un număr fix de apeluri la funcția LFSR în configurația Galois rulează aproximativ de două ori mai repede decât în configurația Fibonacci (compilatorul MS VS 2010 pe Intel Core i5)
Rețineți că în configurația Galois ordinea biților din cuvântul care definește feedback-ul este inversată în comparație cu configurația Fibonacci

Exemple de generatoare

Generatoare stop-and-go

Generator alternativ stop-go

cascada Gollmann

Generator de prag

Acest generator încearcă să ocolească problemele de securitate inerente generatoarelor anterioare prin utilizarea unui număr variabil de registre de deplasare. În teorie, atunci când se utilizează un număr mai mare de registre de deplasare, complexitatea cifrului crește, ceea ce s-a făcut în acest generator.

Pentru cazul a trei registre de deplasare, generatorul poate fi reprezentat astfel:

Acest generator este similar cu generatorul Geff, cu excepția faptului că generatorul de prag are o complexitate mai liniară. Complexitatea sa liniară este:

unde , , sunt lungimile primului, al doilea și al treilea registre de deplasare.

Alte tipuri

Auto-subțierea

Oscilator cu mai multe viteze cu produs interior

Acest oscilator folosește două registre de deplasare cu feedback linear cu frecvențe de ceas diferite: RSLOS-1 și RSLOS-2. Frecvența de ceas a RSLOS-2 este de de ori mai mare decât RSLOS-1. Biții individuali ai acestor registre sunt combinați folosind operația AND. Ieșirile operației AND sunt apoi redate XOR. Secvența de ieșire este preluată din acest bloc XOR. Din nou, acest generator nu este impecabil (Nu a rezistat descoperirii consistenței liniare. Dacă - lungimea SFLO-1, - lungimea SFLO-2 și d este raportul frecvențelor de ceas, atunci starea internă a generatorul poate fi obținut dintr-o secvență de ieșire de lungime ), dar are o complexitate liniară mare și o performanță statistică excelentă.

Registrul de schimbare a feedback-ului este format din două părți: un registru de deplasare și funcții de feedback.

Figura 19. Registrul de deplasare a feedback-ului.

În general, un registru de deplasare este o succesiune a unor elemente de inel sau câmp. Cel mai des folosit pic registre de deplasare. Lungimea unui astfel de registru este exprimată în numărul de biți. De fiecare dată când este preluat un bit, toți biții din registru sunt deplasați la dreapta cu o poziție. Noul bit cel mai semnificativ este calculat în funcție de toți ceilalți biți de registru. Ieșirea este de obicei bitul cel mai puțin semnificativ. Perioada registrului de deplasare este lungimea secvenței de ieșire înainte de a începe să se repete.

Cel mai simplu tip de registru de deplasare este un registru de deplasare cu feedback liniar (LFSR sau LRS). Părere - operare simplă XOR peste niște biți de registru. Lista acestor biți este determinată polinom caracteristic si se numeste succesiune de atingeri. Uneori se numește această schemă Configurația Fibonacci.

Fig.20. Configurația RSLOS Fibonacci.

La implementare software SFLO-urile folosesc o schemă modificată: pentru a genera un nou bit semnificativ, în loc să folosească biți de secvență de tape, se efectuează o operație XOR pe fiecare dintre biții săi cu ieșirea generatorului, înlocuind vechiul bit de secvență de tape. Această modificare este uneori numită Configurația Galois.

Fig.21. RSLOS de configurare Galois.

n-bit LFSR poate fi în unul din 2 n– 1 stări interne. Aceasta înseamnă că teoretic un astfel de registru poate genera o secvență pseudo-aleatorie cu o perioadă de 2 n– 1 biți (umplerea cu zerouri este complet inutilă). Trecerea tuturor 2 n– 1 stări interne sunt posibile numai cu anumite secvențe curbe Astfel de registre se numesc LFSR cu o perioadă maximă. Pentru a asigura perioada maximă a SFSR, este necesar ca polinomul său caracteristic să fie primitiv modulo 2. Gradul polinomului este lungimea registrului de deplasare. Polinom de gradul primitiv n- Este așa ireductibil un polinom care este divizor, dar nu este divizor x d+ 1 pentru toată lumea d, care sunt divizori ai lui 2 n– 1. (Când discutăm despre polinoame, termenul număr prim se înlocuiește cu termenul polinom ireductibil). Polinomul caracteristic al LFSR prezentat în figuri:

X 32 + X 7 + X 5 + X 3 + X 2 + X + 1

este primitiv modulo 2. Perioada unui astfel de registru va fi maximă, trecând ciclic prin toate valorile 2 32 – 1 înainte de a fi repetate. Cele mai frecvent utilizate sunt polinoamele subțiate, adică. care au doar unii coeficienţi. cele mai populare sunt trinoamele.

Un parametru important generator bazat pe RSLOS, este complexitate liniară. Este definită ca lungime n cel mai scurt HFSR care poate simula ieșirea generatorului. Complexitatea liniară este importantă deoarece folosirea simplă Algoritmul Berlenkamp-Massey puteți recrea un astfel de LFSR bifând doar 2 n biți gamma. Odată ce RFSL-ul necesar este determinat, cifrul fluxului este de fapt spart.

Registrul de schimbare a feedback-ului este format din două părți: un registru de deplasare și funcții de feedback.

Figura 19. Registrul de deplasare a feedback-ului.

Cel mai simplu tip de registru de deplasare este un registru de deplasare cu feedback liniar (LFSR sau LRS). Feedback-ul este o operație XOR simplă pe unii biți de registru. Lista acestor biți este determinată polinom caracteristic si se numeste succesiune de atingeri. Uneori se numește această schemă Configurația Fibonacci.

Fig.20. Configurația RSLOS Fibonacci.

La implementarea LFSR în software, se folosește o schemă modificată: pentru a genera un nou bit semnificativ, în loc să se utilizeze biții secvenței tap, se efectuează o operație XOR pe fiecare dintre biții săi cu ieșirea generatorului, înlocuind vechiul bit. a secvenței de atingere. Această modificare este uneori numită Configurația Galois.

Fig.21. RSLOS de configurare Galois.

n-bit LFSR poate fi în unul din 2 n– 1 stări interne. Aceasta înseamnă că teoretic un astfel de registru poate genera o secvență pseudo-aleatorie cu o perioadă de 2 n– 1 biți (umplerea cu zerouri este complet inutilă). Trecerea tuturor 2 n– 1 stări interne sunt posibile numai cu anumite secvențe de atingere. Astfel de registre se numesc LFSR cu o perioadă maximă. Pentru a asigura perioada maximă a SFSR, este necesar ca polinomul său caracteristic să fie primitiv modulo 2. Gradul polinomului este lungimea registrului de deplasare. Polinom de gradul primitiv n- Este așa ireductibil un polinom care este divizor, dar nu este divizor x d+ 1 pentru toată lumea d, care sunt divizori ai lui 2 n– 1. (Când discutăm despre polinoame, termenul număr prim se înlocuiește cu termenul polinom ireductibil). Polinomul caracteristic al LFSR prezentat în figuri:

X 32 + X 7 + X 5 + X 3 + X 2 + X + 1

Un parametru important al unui generator bazat pe RSLOS este complexitate liniară. Este definită ca lungime n cel mai scurt HFSR care poate simula ieșirea generatorului. Complexitatea liniară este importantă deoarece folosirea simplă Algoritmul Berlenkamp-Massey puteți recrea un astfel de LFSR bifând doar 2 n biți gamma. Odată ce RFSL-ul necesar este determinat, cifrul fluxului este de fapt spart.

Pe lângă LFSR, se mai folosesc registre de deplasare cu feedback neliniar, feedback de transfer etc.

Un număr de generatoare sunt dezvoltate pe baza unei abordări teoretice a numărului (generatoare Blum-Micali, RSA, BBS, compresie, generatoare de aditivi etc.).

Suportul matematic pentru sinteza algoritmilor criptografici de flux a fost dezvoltat mai complet și mai detaliat în comparație cu algoritmii criptografici bloc. Cu toate acestea, algoritmii criptografici bloc în modurile OFB sau CFB sunt adesea folosiți pentru a crea coduri de flux.