Blum-Blum-Shub-Generator

Der Blum-Blum-Shub-Generator (BBS-Generator) (auch „s² mod n - Generator“) ist ein Pseudozufallszahlengenerator, entwickelt 1986 von Lenore Blum, Manuel Blum und Michael Shub. Anwendung findet das System u. a. in der Kryptologie im Entwurf komplexitätstheoretisch sicherer Kryptosysteme.

Definition

Der BBS-Generator ist definiert als Folge

$s_{0}\!\,=s^{2}\;{\bmod {\;}}n$

$s_{i+1}\!\,=s_{i}^{2}\;{\bmod {\;}}n$

Der Modul $n=pq$ ist das Produkt zweier ungleicher Primzahlen $p$ und $q$, die von der Form $4k+3$ sind, d. h. $p\equiv q\equiv 3{\pmod {4}}$. Eine Zahl $n$ mit diesen Eigenschaften wird auch Blum-Zahl genannt.

Der Startwert $s\in \{2,3,\ldots ,n-2\}$ ist zu $n$ teilerfremd ($\operatorname {ggT} (s,n)=1$).

Der Parameter $n$ sollte außerdem folgenden Bedingungen genügen, damit $n$ möglichst schwer zu faktorisieren ist und der Generator garantiert hochwertige Zufalszahlen erzeugt (siehe Kapitel „Sicherheit“):

• n sollte hinreichend groß sein; für kryptografische Anwendung mindestens etwa 200 Dezimalstellen.
• $p$ und $q$ sollten etwa gleichdimensioniert sein, aber nicht zu nah beieinander liegen, etwa $5<p/q<1000$.
• $p-1$ und $p+1$ sollten jeweils einen großen Primfaktor haben, der etwa im Bereich ${\sqrt {p}}\;\;{\text{bis}}\;\;p^{3/4}$ liegt. Das entsprechende sollte auch für $q$ gelten.

Periodenlänge

Es ist schwierig, die Parameter $s$ und $n$ so zu bestimmen, dass eine ausreichende Periodenlänge garantiert ist. Folgende Regeln erhöhen die Wahrscheinlichkeit für eine lange Periode:

• $p_{0}=(p-1)/2$ und $q_{0}=(q-1)/2$ sowie $(p_{0}-1)/2$ und $(q_{0}-1)/2$ sollten prim sein.
• $\operatorname {ggT} (\phi (p-1),\phi (q-1))$ sollte möglichst klein sein. (siehe Eulersche φ-Funktion)
• Für den Startwert $s$ sollte ${\sqrt {n}}<s<n-{\sqrt {n}}$ gelten.

Anwendung

Aus jedem der so berechneten $s_{i}$ werden ein oder mehrere Zufallsbits gewonnen. Im einfachsten Fall nimmt man das niederwertigste Bit, also

$b_{i}=s_{i}\;{\bmod {\;}}2$,

oder man berechnet das Paritätsbit zu $s_{i}$:

$b_{i}=\operatorname {bitnum} (s_{i})\;{\bmod {\;}}2$.

Die Funktion $\operatorname {bitnum} (x)$ liefert die Zahl der Bits mit dem Wert 1 in der Binärdarstellung von $x$.

Besser ist es jedoch, wenn das Paritätsbit von einigen fest gewählten Bits aus $s_{i}$ bestimmt wird. Dazu wählt man vorab eine zufällige Konstante z, die etwa so groß wie n ist, und berechnet

$b_{i}=\operatorname {bitnum} (s_{i}\wedge z)\;{\bmod {\;}}2$.

Dabei bezeichnet $\wedge$ die bitweise UND-Verknüpfung.

Man kann zeigen, dass der BBS-Generator kryptografisch auch dann noch sicher ist, wenn nicht nur ein, sondern bis zu $a=\log _{2}\log _{2}n$ Bits aus jedem $s_{i}$ extrahiert werden. Meist werden einfach die $a$ niederwertigsten Bits genommen:

$b_{ai+j}=\lfloor s_{i}\,/\,2^{j}\rfloor \;{\bmod {\;}}2\quad {\text{mit}}\;j=0,1,\ldots ,a-1$,

oder etwas elaborierter:

$b_{ai+j}=\operatorname {bitnum} (s_{i}\wedge z_{j})\;{\bmod {\;}}2\quad {\text{mit}}\;j=0,1,\ldots ,a-1\;;\quad j\neq k\Rightarrow z_{j}\wedge z_{k}=0$.

Symmetrisches Kryptosystem

Zunächst wird der BBS-Generator zur Umsetzung eines symmetrischen Kryptosystems verwendet. Als geheimer Schlüssel zwischen Sender und Empfänger dienen n und der Startwert s des Generators.

Z. B. generiert der Sender aus n=7$\cdot$11=77 und s=64 nach der oben angegebenen Vorschrift die Folge der s_i. Die zugehörige Pseudozufallszahl b_i ergibt sich beispielsweise aus dem letzten Bit des jeweiligen Wertes von s_i, d. h. b_i=s_i mod 2. Um den Schlüsseltext zu bestimmen, wird der Klartext (im Beispiel: 0011) XOR mit der Pseudozufallszahlenfolge verknüpft.

 Generierte Folge         15 71 36 64 …
 Pseudozufallszahlenfolge  1  1  0  0 …
 Klartext                  0  0  1  1
 Schlüsseltext             1  1  1  1

Der Empfänger bestimmt seinerseits aus den geheimen Werten n und s die Folgen s_i und b_i. Mit Hilfe des übersendeten Schlüsseltextes wird wiederum mittels XOR der Klartext berechnet.

 Generierte Folge         15 71 36 64 …
 Pseudozufallszahlenfolge  1  1  0  0 …
 Schlüsseltext             1  1  1  1
 Klartext                  0  0  1  1

Asymmetrisches Kryptosystem

Zur Umsetzung eines asymmetrischen Kryptosystems eignet sich der BBS-Generator ebenfalls. Dieses Verfahren wurde 1984 von Manuel Blum und Shafi Goldwasser vorgeschlagen und wird auch als Blum-Goldwasser-Kryptosystem bezeichnet. Der geheime Schlüssel auf Seiten des Empfängers sind die Primfaktoren p und q.

Senderseitig laufen die Berechnungen analog zum obigen symmetrischen Fall ab. Zusätzlich zum Schlüsseltext $x_{0}\oplus b_{0},\ldots ,x_{i}\oplus b_{i}$ wird aber noch s_i+1 gesendet. Da der Empfänger den Startwert nicht kennt, bildet er mit Hilfe der geheimen Primzahlen p und q die Folge der Pseudozufallszahlen ausgehend vom versendeten s_i+1 bis zum Startwert s zurück. Für das Beispiel bedeutet das, der Empfänger erhält 1111 sowie s₄=15.

s_i-1 = (up$\cdot$s_i^(q+1)/4 mod q + vq$\cdot$s_i^(p+1)/4 mod p) mod n

Der Ansatz bedient sich des Chinesischen Restealgorithmus, einem Spezialfall des chinesischen Restsatzes. Die beiden Unbekannten u und v sind von den Primfaktoren p und q abhängig und werden zu Beginn mittels des erweiterten Euklidischen Algorithmus bestimmt. Dabei gilt up+vq=1, also 2$\cdot$11-3$\cdot$7=1 im Beispiel. Damit ergibt sich die folgende Abarbeitung.

s₃ = (22$\cdot$15² mod 7 - 21$\cdot$15³ mod 11) mod 77

s₃ = (22$\cdot$1 - 21$\cdot$9) mod 77 = 64

s₂ = (22$\cdot$64² mod 7 - 21$\cdot$64³ mod 11) mod 77

s₂ = (22$\cdot$1 - 21$\cdot$3) mod 77 = 36

s₁ = (22$\cdot$36² mod 7 - 21$\cdot$36³ mod 11) mod 77

s₁ = (22$\cdot$1 - 21$\cdot$5) mod 77 = 71

s₀ = (22$\cdot$71² mod 7 - 21$\cdot$71³ mod 11) mod 77

s₀ = (22$\cdot$1 - 21$\cdot$4) mod 77 = 15

s = (22$\cdot$15² mod 7 - 21$\cdot$15³ mod 11) mod 77

s = (22$\cdot$1 - 21$\cdot$5) mod 77 = 64

Empfängerseitig wird nun analog zum symmetrischen Fall aus der eben rückwärts berechneten BBS-Generatorfolge die Folge der Pseudozufallszahlen bestimmt und letztlich durch XOR-Verknüpfung mit dem Schlüsseltext der Klartext generiert.

Ein so konstruiertes asymmetrisches Kryptosystem ist jedoch nicht sicher gegen aktive Angreifer, z. B. durch einen gewählter Schlüsseltext-Klartext-Angriff (englisch: chosen-ciphertext attack).

Sicherheit

Die Sicherheit des BBS-Generators hängt von der Faktorisierungsannahme (FA) und der Quadratische-Reste-Annahme (QRA) ab.

Faktorisierungsannahme (FA): Die Wahrscheinlichkeit, dass ein schnelles Faktorisierungsverfahren eine ganze Zahl n=pq mit Erfolg faktorisiert, sinkt rapide mit Länge der Faktoren p und q.

Zur Zeit kann keine sichere Aussage getroffen werden, wie schwer Faktorisierung ist. Mit anderen Worten, die Frage nach einem Algorithmus, der in annehmbarer Zeit bei Eingabe beliebiger n die Primfaktorzerlegung in p und q durchführt, bleibt unbeantwortet. Somit kann die Problematik lediglich mit Hilfe einer Annahme abgeschätzt werden.

Für konkrete praktische Anwendungen fordert man dann, dass bei gegebener Länge der Primfaktoren nur ein bestimmter Teil in einer bestimmten Zeit mit maximal verfügbarer Rechnerkapazität und den besten bekannten Faktorisierungsverfahren faktorisiert werden kann, also z. B. bei einer Länge von 1024 Bit werden 2^-50 % aller n in einem Jahr faktorisiert.

Quadratische-Reste-Annahme (QRA) (englisch: quadratic residuosity assumption): est ist schwierig (im Sinne von aufwändig), von einer gegebenen Zahl zu entscheiden, ob sie ein Quadratischer Rest in einem Restklassenring $\mathbb {Z} /n\mathbb {Z}$ ist. Mit anderen Worten, es ist zu entscheiden, ob es zu der gegebenen Zahl $a$ eine Zahl $b$ gibt, so dass $a\equiv b^{2}{\pmod {n}}$. Die QRA ist wie die FA nicht bewiesen.

Zwei Punkte erschweren diesen Test. Erstens gibt es in einem Restklassenring mehrere Wurzeln zu einer gegebenen Zahl. So haben z. B. im $\mathbb {Z} /4\mathbb {Z}$ die Zahlen 1 und 3 die gleichen Quadrate: $1^{2}\equiv 3^{2}\equiv 1{\pmod {4}}$. Zweitens interessiert man sich nur für solche Quadrate, die selbst Quadrate sind. Diesen Umstand kann man sich mittels der Definition der BBS-Generatorfolge verdeutlichen.

Zusammenfassend gilt daher: Der Generator ist sicher, weil die Umkehrung des Quadrierens in einem Restklassenring $\mathbb {Z} /n\mathbb {Z}$ mit zusammengesetztem Modul n genauso schwierig ist wie die Faktorisierung von n.