Anotácia

Slovenská technická univerzita v Bratislave
Fakulta elektrotechniky a informatiky
Študijný odbor: INFORMATIKA
Autor: Bc. Peter Vadovič
Diplomová práca: Kryptoanalýza paritného generátora založeného na LFSR a FCSR
Vedenie diplomovej práce: Ing. Milan Vojvoda
December 2001

Táto práca sa zaoberá implementáciou a analýzou generátora prúdových šifier založeného na paritnej funkcii registrov typu LFSR a FCSR.

V práci sú rozobrané najdôležitejšie teoretické poznatky o registroch typu LFSR a FCSR, ako aj o postupnostiach, ktoré generujú. Je implementovaný paritný generátor založený na LFSR a FCSR, Berlekampov-Masseyov algoritmus na analýzu lineárnej zložitosti, 2RA algoritmus pre analýzu 2-adickej zložitosti a balík testov podľa publikácie NIST SP 800-22.

Aplikovaním Berlekampov-Masseyovho algoritmu bola zavedená hypotéza o lineárnej zložitosti FCSR, rovnajúca sa približne 1/2 jeho čísla prepojenia. Taktiež lineárna zložitosť generátora sa rovná súčtu lineárnych zložitostí registrov, z ktorých sa skladá. Analýzou pomocou 2RA algoritmu boli zistené výsledky, ktoré viedli k vzniku pozoruhodných hypotéz o 2-adickej zložitosti postupností generovaných registrami LFSR a paritným generátorom.

Výsledky štatistických testov neukázali žiadnu zásadnú odchýlku od náhodnosti, a preto je vhodné uvažovať o ďalšej analýze generátora.