Nu este clar care este exact „un anumit cod de timp”, dar îl voi considera ca însemnând o secvență de lungime finită $s_0, s_1, \ldots, s_{N-1}$ de $N$ biți. Secvența în sine poate sau nu să fi fost generată de un LFSR -- nu știm -- dar am dori să găsim un LFSR (Fibonacci) care generează secvența.
Să pregătim un pic scena. Un LFSR Fibonacci de lungime $n$
este o serie de $n$ biți cu valoarea inițială
$$(s_0, \quad s_1,\quad \ldots, \quad s_{n-2}, \quad s_{n-1})$$ și valori succesive
$$(s_0, \quad s_1, \quad \ldots, \quad s_{n-2}, \quad s_{n-1})\
\sageata in jos\
(s_1, \quad s_2, \quad \ldots, \quad s_{n-1}, \quad s_n)\
\sageata in jos\
(s_2, \quad s_3, \quad \ldots, \quad s_n, \quad \quad s_{n+1})\
\sageata in jos\
\cdots \quad \cdots$$
unde conținutul matricei se deplasează spre stânga la fiecare pas (ciclu de ceas)
astfel încât bucățile să cadă
de la capătul din stânga (LFSR ieșire) sunt succesiunea dată, în timp ce
biții afișați ca intrând în LFSR pe dreapta
sunt fiind calculată ca combinație liniară (a.k.a. Exclusive-OR suma) de niste a LFSR
conținut la pasul anterior. În special, pentru $i \geq 0$,
cel tranziție de stat poate fi exprimat ca
$$\biggr(s_i, \quad s_{i+1}, \ldots, \quad s_{i+n-2}, \quad s_{i+n-1}\biggr)\
\sageata in jos\
\biggr(s_{i+1}, \quad s_{i+2}, \ldots, \quad s_{i+n-1}, \quad {\Large{\oplus}}_{j=0}^ {n-1}c_{n-j} s_{i+j}\biggr),$$
unde $c_i$au valoare $0$ sau $1$, astfel încât liniar combinaţie
$c_ns_i\oplus c_{n-1}s_{i+1} \oplus \cdots \oplus c_1s_{i+n-1}$ ale anterioare
Conținutul LFSR este în curs alimentat înapoi în capătul drept al LFSR
la fel de $s_{n+i}$ este de fapt suma SAU Exclusivă a câtorva biți selectați din conținutul anterior (cei pentru care $c_i$ au valoare $1$).
De aici denumirea de registru de deplasare cu feedback liniar care este inițializat în LFSR.
Având în vedere descrierea de mai sus, un răspuns la întrebarea unui LFSR este trivial într-un sens: an $N$ etapă LFSR cu coeficienți de feedback $(c_N,c_{N-1}, \cdots, c_1) = (1,0,0,\cdots, 0)$ și încărcarea inițială $\big(s_0, s_1, \ldots, s_{N-1}\big)$ va produce repetiții nesfârșite
$$s_0, s_1, \ldots, s_{N-1},s_0, s_1, \ldots, s_{N-1}, s_0, s_1, \ldots, s_{N-1}, \cdots$$
a codului temporal dat
$s_0, s_1, \ldots, s_{N-1}$ pentru toata eternitatea. Alternativ, orice altă alegere a $(c_N,c_{N-1}, \cdots, c_1)$ va umple registrul de schimb cu altceva, dar primul $N$ bits out vor mai fi $s_0, s_1, \ldots, s_{N-1}$ iar ceea ce urmează după aceea va fi diferit. În mod evident, nu este ceea ce ne dorim și, prin urmare, căutăm un criteriu mai bun: găsiți cel mai scurt LFSR (și încărcarea sa inițială) care va genera $s_0, s_1, \ldots, s_{N-1}$și exact asta găsește algoritmul Berlekamp-Massey.
Algoritmul Berlekamp-Massey este un proces iterativ care constă în găsirea celui mai scurt LFSR care generează primul $t$ biți
$s_0, s_1, \ldots s_{t-1}$ și verificând dacă LFSR
găsește $s_t$ corect. Daca da, $s_{t+1}$ este bifat,
în timp ce dacă nu, $c_i$sunt actualizate astfel încât
LFSR revizuit generează $s_t$. Adesea, dar nu întotdeauna, lungimea LFSR crește. Procesul iterativ continuă până la ultimul bit disponibil $s_{N-1}$ a fost procesat, astfel încât atunci când algoritmul Berlekamp-Massey se termină, LFSR sintetizat produce întreaga secvență $s_0, s_1, \ldots, s_{N-1}$ la iesirea sa. Dacă LFSR sintetizat are $n\leq N$ etape, atunci încărcarea sa inițială este
$\big(s_0, s_1, \ldots, s_{n-1}\big)$ (care sunt primele $n$ biți de ieșire) și LFSR calculează corect $s_n, s_{n+1}, \cdots, s_{N-1}$ (adică restul secvenței date). Lungimea LFSR sintetizată de algoritmul Berlekamp-Massey este garantată a fi minim: Nu LFSR care generează $s_0, s_1, \ldots, s_{N-1}$ poate avea mai scurt lungime. In orice caz, există Nu pretinde ca $n$ este garantat a fi mai mic decât $N$; s-ar putea foarte bine să se întâmple ca soluțiile banale descrise mai sus să fie soluții minime. Într-adevăr, susțin că acesta este într-adevăr cazul cel mai secvențe; LFSR este de lungime $N$. Teoria complexității Kolmogorov spune că cel mai scurt program pentru tipărirea celor mai multe șiruri de lungime $N$ este de lungime $N+c$, sau în mod colocvial, pentru cele mai multe șiruri, se poate face puțin mai bine decât să păstreze șirul și să-l imprime; "$c$" este doar lungimea comenzii "Tipărește următorul șir". În contextul registrelor de deplasare, pentru majoritatea secvențelor de lungime $N$, cel mai scurt registru cu deplasare a cărui ieșire este o secvență dată de lungime $N$ este doar registrul de deplasare al lungimii $N$ inițializat la secvența dată. Care este feedback-ul (dacă există vreun feedback) este irelevant.
- Dacă secvența a fost într-adevăr creată de a
$n$-etapa LFSR așa cum este descris mai sus, unde $n \leq \frac N2$, apoi Berlekamp-Massey
algoritmul le găsește pe toate $n$ coeficienți $c_i$ după
examinând $s_0, s_1, \ldots, s_{2n-1}$. Încărcarea inițială a LFSR sintetizat este, desigur, justă $\big(s_0, s_1, \ldots, s_{n-1}\big)$. Din această
mai departe, algoritmul Berlekamp-Massey poate
continuați să verificați restul secvenței (dacă da
dorit), dar nu trebuie să actualizeze $c_i$lui
deoarece fiecare verificare a simbolului următor pur și simplu raportează
înapoi că totul este OK; LFSR-ul curent generează și următorul bit. in orice caz, în general, criptoanalistul are Nu ideea dacă codul de timp a fost generat de un LFSR; este doar o succesiune de $N$ biți de origine necunoscută și, așadar, pentru scopurile criptoanalistului, toate $N$ biții trebuie examinați pentru a găsi cel mai scurt LFSR care poate fi generat $s_0, s_1, \ldots, s_{N-1}$. Dacă biți suplimentari $s_N, s_{N+1}, \ldots$ sunt disponibile, atunci nu există nicio garanție că LFSR-ul a fost găsit după examinare $N$ biții vor genera și acești biți suplimentari. De fapt, întreaga idee din spatele algoritmului Berlekamp-Massey este că, dacă testul „Generează LFSR actual și $s_n$?" eșuează, algoritmul sintetizează un LFSR modificat din LFSR curent, astfel încât LFSR modificat generează $s_0, s_1, \ldots, s_{n-1},s_n$. În acest proces, lungime a LFSR ar putea (sau nu) să crească.
- Dacă secvența a fost într-adevăr creată de a
$n$-etapa LFSR așa cum este descris mai sus, unde $\frac N2 < n \leq N$, apoi algoritmul Berlekamp-Massey găsește cel mai scurt LFSR care generează $s_0, s_1, \ldots, s_{N-1}$. S-ar putea să genereze sau nu aceleași valori pentru $s_N, s_{N+1}, \cdots, s_{2n-1}$ așa cum face LFSR propriu-zis.
Având în vedere diatriba lungă de mai sus, haideți să răspundem întrebărilor OP. În titlu, OP întreabă
Ce instrumente sunt disponibile pentru a face inginerie inversă a unui LFSR în afară de BMA?
Ei bine, algoritm euclidian extins pentru polinomii cei mai mari divizori comuni pot fi utilizați, dar într-un sens, este echivalent cu algoritmul Berlekamp-Massey; poate fi văzută ca procesând secvența în ordine inversă $s_{N-1}, s_{N-2}, \cdots, s_1, s_0$ in comparatie cu comanda $s_0, s_1, \cdots, s_{N-2}, s_{N-1}$ folosit de algoritmul Berlekamp-Massey.
În corpul întrebării, OP se plânge
acest cod pare să aibă o complexitate liniară de 110, ceea ce nu este practic în niciun fel.De asemenea, nu poate fi reconstruit cu polinomul ireductibil de 110 biți pe care îl găsește BMA. Doar primii câțiva biți sunt așa cum era de așteptat și apoi biții par să se răstoarne.
Este probabil ca această problemă să fie o problemă de greșeli în implementarea BMA. „Nu este practic în niciun fel” sugerează că poate a fost alocată memorie insuficientă pentru stocarea diferitelor polinoame utilizate intern în BMA sau că bufferele s-au debordat etc. După cum subliniază @kodlu, dacă codul de timp este de lungime $220$ biți, apoi examinând toate $220$ biți ar putea avea ca rezultat un LFSR de lungime $110$. Altfel, așa cum sa discutat mai sus, dacă codul de timp este de lungime $110$ sau mai multe (poate $128$ biți $= 16$ octeți?), BMA ar putea sintetiza un LFSR de lungime $110$. În cele din urmă, nu am altă explicație decât eroarea programatorului pentru observația OP-ului că în ieșirea LFSR sintetizată, „primii câțiva biți” sunt corecti, dar restul sunt inversați.
are cineva idee în ce condiții BMA detectează un polinom atât de lung?
Vedeți materialul de deasupra liniei întrerupte din acest răspuns.
