înregistrare Logare
Puncte:0
Tom avatar Crypto

Relația dintre LCG și LFSR

drapel tf
Tom

Aici:

https://en.wikipedia.org/wiki/Linear-feedback_shift_register

ei au scris:

Registrul de deplasare cu feedback liniar are o relație puternică cu generatoarele congruențiale liniare

Despre ce este vorba în această relație? Sunt echivalente matematic într-un fel? În două cazuri, putem ajunge la perioada maximă. Poate că există LCG-uri care generează aceleași numere ca și LFSR-urile? Din câte știu, LFSR-urile au și o problemă cu biții de ordin scăzut, la fel ca și modul LCG $2^n$. Dar avem aici vreo legătură mai profundă, dincolo de asemănări?

51
0 + 0
kodlu avatar
drapel sa
kodlu
Având în vedere că majoritatea LFSR-urilor utilizate în practică funcționează peste $GF(2)$ în loc de $GF(2^n)$, mă întreb despre ce poate fi comentariul tău „problema cu biții de ordin scăzut”.
0
Răspunde
kodlu avatar
drapel sa
kodlu
sau vrei să spui doar să nu scoți primii atât de mulți biți, deoarece ai da „sămânța” (uneori folosită ca cheie)
0
Răspunde
Puncte:1
kodlu avatar Crypto
drapel sa
kodlu

Sunt amandoi liniar ceea ce este desigur o slăbiciune din punct de vedere criptografic. LCG este $$x_{t}\equiv (a x_{t-1}+c) \pmod n \qquad (1) $$ în timp ce LFSR este $$x_{t} \equiv (a_1 x_{t-1}+ a_2 x_{t-2}+\cdots+ a_L x_{t-L}) \pmod 2\qquad (2) $$

S-ar putea concepe un $L$ termenul LCG $$x_{t}\equiv (a_1 x_{t-1}+a_2 x_{t-2}+\cdots+ a_L x_{t-L}) \pmod n$$ care ar putea fi apoi redusă mod 2 (atât $x_t$s și cel $a_i$este modul redus 2) pentru a corespunde unui LFSR, dar asta este puțin artificial, deoarece trebuie să alegeți o dimensiune mare pentru $n$ și alegeți proprietățile sale (de exemplu, is $n$ prim, semiprim, este $\gcd(a,n)=1$) pentru a obține o recidivă relativ puternică. Deci ar fi exagerat, fără un câștig apreciabil de putere în comparație cu (1) și o alegere mai complicată a constantelor $a_i$ ar fi nevoie.

Și atacurile de bază asupra lor se bazează pe idei destul de diferite, de exemplu atacul de trunchiere asupra LCG-urilor de către Lagarias și colab. nu are nimic de-a face cu atacul Berlekamp Massey.

Nu sunt conștient de alte asemănări importante între ele; cel puțin nu-mi vine în minte niciunul din capul meu.

0 + 0
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.