Additive Random Number Generator - Aditívny generátor náhodných čísel
RNG založený na LFSR typicky používa viacbitové prvky a celočíselný sčítací (namiesto XOR) kombinačný obvod.
S výhod treba spomenúť :
- Dlhá, matematicky dokázaná dĺžka cyklu.
- Výnimočne efektívne softvérové implementácie.
- Takmer ľubovoľná inicializácia (niektorý prvok musí mať nastavený svoj najmenej významný bit, angl. least significant bit - lsb).
- Jednoduchý návrh, ktorý sa dá ľahko a správne dosiahnuť.
A naviac, obrovská multiplicita nezávislých cyklov má potenciál zmiasťaj "kvantový počítač," preto by sa mala takáto vec stať uskutočniteľnou.
Pre n-stupňový aditívny GNČ a bitovú šírku w
| Celkový počet stavov |
2nw |
| Nepočiatočné stavy: |
2n(w-1) |
| Počet cyklov: |
2(n-1)(w-1) |
| Dĺžka každého cyklu: |
(2n-1)2(w-1)
|
| Perióda LSB: |
2n-1 |
Binárne sčítanie dvoch bitov bez žiadneho prenosu vstupu je práve XOR, teda lsb aditívneho GNČ má zvyčajne maximálnu dĺžku periódy.
Napr. 127-stupňový aditívny GNČ využívajúci 127 prvkov, každý s dĺžkou 32 bitov, má 24064 jedinečných stavov. Z nich 23937 sú nedovolené podľa inicializácie ( lsb bity sú všetky "0") ale toto je iba jeden nevyužiteľný stav z 2127. Stále tu existuje 23906 cyklov, ktorých každý má takmer 2158 krokov. (Prúdová šifra Cloak2 používa aditívny GNČ s 9689 prvkami, každý dĺžky 32 bitov, a teda má 2310048 jedinečných stavov. Tieto sú väčšinou rozdelené medzi 2300328 odlišných cyklov, z ktorých každý pozastáva z takmer 29720 krokov.)
Všimnite si, že akýkoľvek LFSR vrátane aditívneho RNG, je veľmi slabý ak sa použije samotný. Ale ak sa pripravili kroky na skrytie postupnosti výsledok môže maťznačnú silu.
zdroj: http://friedo.szm.sk/krypto/lexikon.html