Kryptologie | Qualitäten einschätzen
In der Kryptologie verwendet man unter anderem zur sicheren Datenübermittlung Formeln und Algorithmen, die quasi „zufällige“ Folgen von Nullen und Einsen erzeugen sollen. Diese werden dann etwa einem Datenstrom überlagert, um deren Inhalt zu verschleiern. Eines von vielen Kriterien dafür, was „zufällige“ bedeuten soll, ist, dass die Beziehung zwischen den Folgengliedern nicht zu offensichtlich sein soll, etwa das letzte linear von wenigen vorhergehenden abhängen soll.
Zum Beispiel gilt für die Folge der ungeraden Zahlen a1 = 1, a2 = 3, a3 = 5, . . ., dass 3 = 1 + 2, 5 = 3 + 2, . . . , ai = ai−1 + 2. Der Teil „+2“ stört dabei noch, weil er nicht von den ai abhängt. Da aber für alle i > 1 gilt ai − ai−1 = 2, können wir auch ai = ai−1 + (ai−1 − ai−2) = 2ai−1 − ai−2 schreiben. (Auch ai = ai−1 + ai−2 − ai−3 wäre möglich, aber da wir dazu bis ai−3 zurückgehen müssten, ist die vorherige Version besser.)
Allgemein wird es etwas technischer wie folgt beschrieben: Sei eine Folge von Zahlen a1, a2, a3, . . . gegeben, dann hat die Folge eine „lineare Komplexität“ N, wenn es N Zahlen c1, . . . , cN gibt, sodass für jedes i > N gilt
$$a_{i}=c_{1}\cdot a_{i-1}+c_{2}\cdot a_{i-2}+...+c_{N}a_{i-N}$$
(Und es soll das kleinste derartige N genommen werden.)
Die ungeraden Zahlen haben also die lineare Komplexität 2.
Sieh dir nun die Beispielfolgen an und bestimme ihre lineare Komplexität: a1, a2, a3, . . . =
In der Praxis muss man aus technischen Gründen immer sich nach einer Zahl von Schritten (nennen wir diese Zahl T) wiederholende Folgen benutzen. Wie die Beispiele zeigen, sehen weder Folgen mit sehr niedriger noch mit sehr hoher linearer Komplexität besonders zufällig aus. Man kann zeigen, dass eine Folge mit einem Wert für die lineare Komplexität nahe bei T /2 einer „echt“ zufälligen Folge am ähnlichsten ist und daher für kryptographische Zwecke in Betracht kommt.
