4.5 – Blum-Blum-Shub-Generator

 

Wir haben drei Arten von Sicherheit besprochen. Der Schlüsselstromgenerator, den wir hier nun besprechen, ist beweisbar sicher.

4.5.1 Definitionen

Quadratischer Rest:

Sei n \in \mathbb{N} eine natürliche Zahl. Eine Zahl a \in \mathbb{Z} heißt quadratischer Rest Modulo n, wenn es eine Zahl b \in \mathbb{Z} gibt, so dass gilt: a \equiv {b^2}\bmod n. Alle anderen Zahlen heißen quadratischer Nichtrest.

Legendre-Symbol:

Das Legendre-Symbol ist eine Kurzschreibweise, die in der Zahlentheorie verwendet wird. Es ist nach dem französischen Mathematiker Adrien-Marie Legendre benannt und wird wie folgt notiert:

\left( {\frac{a}{n}} \right) = \left\{ {\begin{array}{*{20}{c}} 1 & {a\:\:ist\:\:qdr.\:Rst\:\:\bmod \:\:n,\quad a\bmod n \ne 0} \\ { - 1} & {a\:\:ist\:\:qdr.\:NichtRst\:\:\bmod \:\:n} \\ 0 & {a\bmod n = 0} \\ \end{array} } \right.

Das Jacobi-Symbol, benannt nach Carl Gustav Jacob Jacobi, ist eine Verallgemeinerung des Legendre-Symbols. Das Jacobi-Symbol kann wiederum vom Kronecker-Symbol verallgemeinert werden. Die Notation ist die gleiche wie die des Legendre-Symbols. Im Gegensatz zum Legendre-Symbol muss beim Jacobi-Symbol n keine Primzahl sein.

Quadratisches Restproblem:

Sei n > 2 eine zusammengesetzte Zahl, sei a \in \mathbb{Z} mit Jacobi-Symbol \left( {\frac{a}{n}} \right) = 1. Das quadratische Restproblem mit den Parametern a und n ist es, zu entscheiden, ob a\bmod n ein quadratischer Rest ist oder nicht.

Durch das Jacobi-Symbol wird das Problem auf eine Primfaktorzerlegung zurückgeführt:

\left( {\frac{a}{n}} \right) = {\left( {\frac{a}{{{p_1}}}} \right)^{{\nu _1}}} \cdot {\left( {\frac{a}{{{p_2}}}} \right)^{{\nu _2}}} \cdot \ldots \cdot {\left( {\frac{a}{{{p_k}}}} \right)^{{\nu _k}}}

Blum-Blum-Shub-Generator:

Seien p,q \in \mathbb{Z} zwei große Primzahlen mit p\bmod 4 = 3, q\bmod 4 = 3 und p \ne q. Eine Pseudozufallsbitfolge {b_1},{b_2}, \ldots ,{b_l} wird (in Python) wie folgt erzeugt: 

def bbs(n, s, l):
	out = []
	xi = s
	for i in range(l)
		xi = xi ** 2 % n
		out.append(xi % 2)
	return out

Frage: Warum denken wir über statistische Tests nach, warum gibt es überhaupt Verfahren wie RC4, wenn es einen beweisbar sicheren Stromchiffrengenerator wie diesen gibt?

Antwort: Der Schritt {x_i} \leftarrow \left( {x_i^2\bmod n} \right) ist sehr aufwändig, daher kann auch die Verschlüsselung und Entschlüsselung nicht effizient durchgeführt werden.