Blum-Blum-Shub-Generator

Der Blum-Blum-Shub-Generator (BBS-Generator) i​st ein Pseudozufallszahlengenerator, entwickelt 1986 v​on Lenore Blum, Manuel Blum u​nd Michael Shub. Anwendung findet d​as System u. a. i​n der Kryptologie i​m Entwurf komplexitätstheoretisch sicherer Kryptosysteme.

Definition

Der BBS-Generator ist definiert als Folge ${\displaystyle (s_{i})}$ durch die Iterationsvorschrift

${\displaystyle {\begin{aligned}&s_{0}&=s^{2}\;{\bmod {\;}}n\\&s_{i+1}&=s_{i}^{2}\;{\bmod {\;}}n\end{aligned}}}$

Dabei bezeichnet d​en Divisionsrest (siehe Modulo).

Der Modul ${\displaystyle n=p\cdot q}$ ist das Produkt zweier verschiedener Primzahlen ${\displaystyle p}$ und ${\displaystyle q}$, die von der Form ${\displaystyle 4k+3}$ sind, d. h. ${\displaystyle p\equiv q\equiv 3\;({\bmod {\;}}4)}$. Eine Zahl ${\displaystyle n}$ mit diesen Eigenschaften wird auch Blum-Zahl genannt. Der Startwert ${\displaystyle s}$ ist zu ${\displaystyle n}$ teilerfremd: ${\displaystyle \operatorname {ggT} (s,n)=1}$.

Der Parameter ${\displaystyle n}$ sollte außerdem folgenden Bedingungen genügen, damit ${\displaystyle n}$ möglichst schwer zu faktorisieren ist und der Generator garantiert hochwertige Zufallszahlen erzeugt:

• ${\displaystyle n}$ sollte hinreichend groß sein, für kryptografische Anwendung mindestens 200 Dezimalstellen.
• ${\displaystyle p}$ und ${\displaystyle q}$ sollten etwa gleichdimensioniert sein, aber nicht zu nah beieinander liegen, etwa ${\displaystyle 2<p/q<1000}$.
• ${\displaystyle p-1}$ und ${\displaystyle p+1}$ sowie ${\displaystyle q-1}$ und ${\displaystyle q+1}$ sollten jeweils einen großen Primfaktor haben, größer als ca. ${\displaystyle {\sqrt[{4}]{n}}}$.

Manchmal ist es praktisch, ${\displaystyle k}$ Iterationsschritte des Generators auf einmal zu berechnen. Dies geht mit der Formel

${\displaystyle s_{i+k}=s_{i}^{2^{k}\,{\bmod {\,}}\lambda (n)}\;{\bmod {\;}}n}$wobei hier ${\displaystyle \lambda (n)=\operatorname {kgV} (p-1,q-1)}$, siehe kgV.

Periodenlänge

Sei ${\displaystyle Z}$ die Menge der zu ${\displaystyle n}$ teilerfremden Zahlen in ${\displaystyle \{1,\dots ,n-1\}}$.

Der BBS-Generator arbeitet auf der Menge ${\displaystyle Q\subset Z}$ der Quadratreste modulo ${\displaystyle n}$. Die ${\displaystyle s_{i}}$ sind trivialerweise in ${\displaystyle Q}$, da sie als Rest des Quadrats einer zu ${\displaystyle n}$ teilerfremden Zahl berechnet werden. ${\displaystyle Q}$ enthält genau ein Viertel der Zahlen in ${\displaystyle Z}$. Jedes ${\displaystyle x\in Q}$ hat genau eine Wurzel in ${\displaystyle Q}$: ${\displaystyle W_{x}=\{w\in Z\;|\;w^{2}\;{\bmod {\;}}n=x\}\;;\;|W_{x}\cap Q|=1}$. Die Iterationsvorschrift des Generators bildet also ${\displaystyle Q}$ bijektiv auf ${\displaystyle Q}$ ab. Somit zerfällt ${\displaystyle Q}$ in mehrere Teilmengen ${\displaystyle Q_{j}}$, die jeweils eine Periode des Generators bilden. Die Periodenlänge ${\displaystyle \left|Q_{j}\right|}$ ist immer ein Teiler von ${\displaystyle \lambda (\lambda (n))}$, wobei ${\displaystyle \lambda }$ die Carmichael-Funktion ist.

Beispiel

Sei ${\displaystyle n=3\cdot 7=21}$. Dann ist ${\displaystyle Z\!\,=\{1,2,4,5,8,10,11,13,16,17,19,20\}}$ und die Quadratreste sind ${\displaystyle Q\!\,=\{1,4,16\}}$. Die Wurzeln der Quadratreste sind

${\displaystyle W_{1}=\{1,8,13,20\}}$ mit ${\displaystyle 1\in Q}$,

${\displaystyle W_{4}=\{2,5,16,19\}}$ wobei ${\displaystyle 16\in Q}$ und

${\displaystyle W_{16}=\{4,10,11,17\}}$ wobei ${\displaystyle 4\in Q}$.

Weil ${\displaystyle 1\in W_{1}}$, aber ${\displaystyle 16\in W_{4}}$ und ${\displaystyle 4\in W_{16}}$, zerfällt ${\displaystyle Q}$ in die beiden Perioden ${\displaystyle Q_{1}\!\,=\{1\}}$ und ${\displaystyle Q_{2}\!\,=\{4,16\}}$.

Nachweis der Periodenlänge

Es ist schwierig, die Parameter ${\displaystyle s}$ und ${\displaystyle n}$ so zu bestimmen, dass eine ausreichende Periodenlänge garantiert ist. Bei der Verwendung des BBS-Generators in der Kryptographie wird dieses Problem oft vernachlässigt, denn die Wahrscheinlichkeit einer zu kurzen Periode ist sehr klein. Absolute Sicherheit kann ohnehin nicht erreicht werden, da ein Angreifer den Modul ${\displaystyle n}$ mit Glück faktorisieren könnte, etwa indem er einige Millionen zufällig erzeugte Probeteiler ausprobiert.

Wenn ${\displaystyle n}$ und ${\displaystyle s}$ so gewählt werden, dass gilt:

${\displaystyle \operatorname {ord} _{\lambda (n)/2}(2)=\lambda (\lambda (n))}$, und

${\displaystyle \operatorname {ord} _{n}(s_{0})=\lambda (n)/2}$,

dann beträgt die Periodenlänge ${\displaystyle \lambda (\lambda (n))}$.

${\displaystyle \operatorname {ord} _{b}(a)}$ bezeichnet dabei die Ordnung des Elements ${\displaystyle a}$ der primen Restklassengruppe ${\displaystyle (\mathbb {Z} /b\mathbb {Z} )^{\times }}$:

${\displaystyle \operatorname {ord} _{b}(a)=\min\{m\in \mathbb {N} ^{+}\;|\;a^{m}\equiv 1\;({\bmod {\;}}b)\}}$.

Zur effizienten Berechnung k​ann ausgenutzt werden, d​ass die Elementordnung l​aut dem Satz v​on Lagrange e​in Teiler d​er Gruppenordnung s​ein muss:

${\displaystyle \operatorname {ord} _{b}(a)\;|\;\phi (b)}$.

Dafür muss die Faktorisierung der Gruppenordnung ${\displaystyle \phi (b)}$ bekannt sein (siehe Eulersche φ-Funktion).

Man muss ${\displaystyle n}$ also so konstruieren, dass die Faktorisierungen von ${\displaystyle p-1}$ und ${\displaystyle q-1}$ bekannt sind oder mit vertretbarem Aufwand berechnet werden können, und ebenso die Faktorisierungen der um ${\displaystyle 1}$ verminderten Primfaktoren von ${\displaystyle p-1}$ und ${\displaystyle q-1}$. Damit können die benötigten Größen und die Faktoren der Gruppenordnungen effizient bestimmt werden. Mit der binären Exponentiation kann man anschließend jeweils ${\displaystyle a^{m}\;({\bmod {\;}}b)}$ für alle Teiler ${\displaystyle m}$ von ${\displaystyle \phi (b)}$ effizient berechnen.

Anwendung

Erzeugung von Zufallsbits

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

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

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

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

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

Eine weitere Möglichkeit ist die Bestimmung des Positionsbits, das von der Position von ${\displaystyle s_{i}}$ im Intervall ${\displaystyle [1,n-1]}$ abhängt:

${\displaystyle b_{i}={\begin{cases}1,&{\text{wenn }}s_{i}>\lfloor n/2\rfloor \\0,&{\text{wenn }}s_{i}\leq \lfloor n/2\rfloor \end{cases}}}$.

Am besten ist es jedoch, wenn das Paritätsbit von einigen fest gewählten Bits aus ${\displaystyle s_{i}}$ bestimmt wird. Dazu wählt man vorab eine Konstante ${\displaystyle z}$ als Maske, die etwa so groß wie ${\displaystyle n}$ ist und eine unregelmäßige, „zufällige“ Binärdarstellung aufweist, und berechnet

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

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

Aus einem ${\displaystyle s_{i}}$ kann man mehrere Zufallsbits erhalten. Die Erfinder Blum, Blum und Shub haben schon früh vorgeschlagen, das niederwertigste Bit und das Positionsbit zugleich zu nutzen:

${\displaystyle b_{2\cdot i}=s_{i}\;{\bmod {\;}}2,\quad b_{2i+1}={\begin{cases}1,&{\text{wenn }}s_{i}>\lfloor n/2\rfloor \\0,&{\text{wenn }}s_{i}\leq \lfloor n/2\rfloor \end{cases}}}$.

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

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

oder etwas elaborierter, mit „disjunkten“ Masken ${\displaystyle z_{j}}$:

${\displaystyle b_{a\cdot i+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 einer Stromchiffre verwendet. Als geheimer Schlüssel zwischen Sender und Empfänger dienen ${\displaystyle n}$ und der Startwert ${\displaystyle s}$ des Generators.

Z. B. generiert der Sender aus ${\displaystyle n=7\cdot 11=77}$ und ${\displaystyle s=64}$ nach der oben angegebenen Vorschrift die Folge der ${\displaystyle s_{i}}$. Die zugehörige Pseudozufallszahl ${\displaystyle b_{i}}$ ergibt sich beispielsweise aus dem letzten Bit des jeweiligen Wertes von ${\displaystyle s_{i}}$, d. h. ${\displaystyle b_{i}=s_{i}\;{\bmod {\;}}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 ${\displaystyle n}$ und ${\displaystyle s}$ die Folgen ${\displaystyle s_{i}}$ und ${\displaystyle 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 ${\displaystyle p}$ und ${\displaystyle q}$.

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

${\displaystyle s_{i-1}=\left(u\cdot p\cdot s_{i}^{\left(q+1\right)/4}{\bmod {q}}+v\cdot q\cdot s_{i}^{\left(p+1\right)/4}{\bmod {p}}\right){\bmod {n}}}$ mit ${\displaystyle n=p\cdot q}$

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

s₃ = (22·15² mod 7 - 21·15³ mod 11) mod 77

s₃ = (22·1 - 21·9) mod 77 = 64

s₂ = (22·64² mod 7 - 21·64³ mod 11) mod 77

s₂ = (22·1 - 21·3) mod 77 = 36

s₁ = (22·36² mod 7 - 21·36³ mod 11) mod 77

s₁ = (22·1 - 21·5) mod 77 = 71

s₀ = (22·71² mod 7 - 21·71³ mod 11) mod 77

s₀ = (22·1 - 21·4) mod 77 = 15

s = (22·15² mod 7 - 21·15³ mod 11) mod 77

s = (22·1 - 21·5) mod 77 = 64

Empfängerseitig w​ird nun analog z​um symmetrischen Fall a​us der e​ben rückwärts berechneten BBS-Generatorfolge d​ie Folge d​er Pseudozufallszahlen bestimmt u​nd letztlich d​urch XOR-Verknüpfung m​it dem Schlüsseltext d​er Klartext generiert.

Ein s​o konstruiertes asymmetrisches Kryptosystem i​st jedoch n​icht sicher g​egen aktive Angreifer, z. B. d​urch einen Angriff m​it frei wählbarem Geheimtext (englisch: chosen-ciphertext attack).

Sicherheit

Die Sicherheit d​es BBS-Generators basiert a​uf der Faktorisierungsannahme (FA).[1] Jeder, d​er BBS brechen kann, k​ann auch faktorisieren, w​as aber a​ls praktisch unmöglich gilt. Folglich i​st BBS sicher.

Faktorisierungsannahme (FA): Die Wahrscheinlichkeit, dass ein schnelles Faktorisierungsverfahren eine ganze Zahl ${\displaystyle n=p\cdot q}$ mit Erfolg faktorisiert, sinkt rapide mit zunehmender Länge der Faktoren ${\displaystyle p}$ und ${\displaystyle q}$.

Zurzeit 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 ${\displaystyle n}$ die Primfaktorzerlegung in ${\displaystyle p}$ und ${\displaystyle 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⁻⁵⁰ Prozent aller ${\displaystyle n}$ in einem Jahr faktorisiert.

Wer faktorisieren kann, k​ann auch BBS brechen. Faktorisieren ermöglicht d​as Brechen d​er Quadratischen-Reste-Annahme, w​as es erlaubt, d​ie Pseudozufallsfolge vorherzusagen.

Quadratische-Reste-Annahme (QRA) (englisch: quadratic residuosity assumption): Es ist schwierig (im Sinne von aufwändig), von einer gegebenen Zahl ${\displaystyle a}$ zu entscheiden, ob sie ein Quadratischer Rest in einem Restklassenring ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ist, d. h. ob es eine Zahl ${\displaystyle b}$ gibt, so dass ${\displaystyle a\equiv b^{2}{\pmod {n}}}$ ist. 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 ${\displaystyle \mathbb {Z} /4\mathbb {Z} }$ die Zahlen 1 und 3 die gleichen Quadrate: ${\displaystyle 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 g​ilt daher: Die Sicherheit d​es BBS-Generators i​st äquivalent z​ur Faktorisierungsannahme.

Programmierung

Der folgende Quelltext i​n der Programmiersprache C++ z​eigt die Implementierung e​ines BBS-Generators. Das Programm berechnet z​wei Zufallszahlen u​nd gibt s​ie auf d​er Konsole aus.[2]

#include <iostream>
#include <stdint.h>
using std::cout;
using std::endl;

// Diese Funktionen berechnen je Aufruf ein Zufallsbit mit dem Blum-Blum-Shub-Generator
unsigned blumBlumShub(uint64_t &s, uint64_t n)
{
    s = s*s % n; // Iterationsschritt
    return s & 1;
}
unsigned blumBlumShubMB(uint64_t &s, uint64_t n, uint64_t z)
{
    s = s*s % n; // Iterationsschritt
    uint64_t h = s & z; // extrahiere durch z bezeichnete Bits
    for (int b=32 ; b ; b >>= 1) // bestimme die Parität von h
        h ^= h >> b;
    return h & 1;
}

void main()
{
    uint64_t p =  39983;  // Primzahlen kongruent 3 (mod 4)
    uint64_t q = 101963;
    uint64_t n = p * q;      // Berechnet die Blum-Zahl (Modul)
    uint64_t z = 1665823915; // Zustandsbits, die ausgewertet werden sollen
    uint64_t s = 2367859;    // Startwert

    uint64_t e = 0;
    for (int i = 0; i < 64; i++) // Diese for-Schleifen berechnen je 64 Zufallsbits und geben sie auf der Konsole aus
    {
        e <<= 1;
        e |= blumBlumShub(s, n);
    }
    cout << e << endl;
 
    e = 0;
    for (int i = 0; i < 64; i++)
    {
        e <<= 1;
        e |= blumBlumShubMB(s, n, z);
    }
    cout << e << endl;
}

Siehe auch

• Erweiterter euklidischer Algorithmus
• Asymmetrisches Kryptosystems

Literatur

• Lenore Blum, Manuel Blum, und Michael Shub: A Simple Unpredictable Pseudo-Random Number Generator, SIAM Journal on Computing, Band 15, Nr. 2, Seiten 364–383, Mai 1986.
• Lenore Blum, Manuel Blum, und Michael Shub: Comparison of two pseudo-random number generators, Advances in Cryptology: Proceedings of Crypto ’82.
• Martin Geisler, Mikkel Krøigård, und Andreas Danielsen: About Random Bits, Dezember 2004. Als PDF und Gzipped Postscript.

Einzelnachweise

1. Andrey Sidorenko und Berry Schoenmakers: Concrete Security of the Blum-Blum-Shub Pseudorandom Generator. In: Cryptography and Coding 2005. 2005, S. 355–375 (tue.nl [PDF]).
2. Stack Exchange Inc.: Pseudo random number generator using the Blum Blum Shub algorithm