Der Blum-Blum-Shub-Generator (BBS-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

Bearbeiten

Der BBS-Generator ist definiert als Folge   durch die Iterationsvorschrift

 

Dabei bezeichnet   den Divisionsrest (siehe Modulo).

Der Modul   ist das Produkt zweier verschiedener Primzahlen   und  , die von der Form   sind, d. h.  . Eine Zahl   mit diesen Eigenschaften wird auch Blum-Zahl genannt. Der Startwert   ist zu   teilerfremd:  .

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

  •   sollte hinreichend groß sein, für kryptografische Anwendung mindestens 200 Dezimalstellen.
  •   und   sollten etwa gleichdimensioniert sein, aber nicht zu nah beieinander liegen, etwa  .
  •   und   sowie   und   sollten jeweils einen großen Primfaktor haben, größer als ca.  .

Manchmal ist es praktisch,   Iterationsschritte des Generators auf einmal zu berechnen. Dies geht mit der Formel

 wobei hier  , siehe kgV.

Periodenlänge

Bearbeiten

Sei   die Menge der zu   teilerfremden Zahlen in  .

Der BBS-Generator arbeitet auf der Menge   der Quadratreste modulo  . Die   sind trivialerweise in  , da sie als Rest des Quadrats einer zu   teilerfremden Zahl berechnet werden.   enthält genau ein Viertel der Zahlen in  . Jedes   hat genau eine Wurzel in  :  . Die Iterationsvorschrift des Generators bildet also   bijektiv auf   ab. Somit zerfällt   in mehrere Teilmengen  , die jeweils eine Periode des Generators bilden. Die Periodenlänge   ist immer ein Teiler von  , wobei   die Carmichael-Funktion ist.

Beispiel

Bearbeiten

Sei  . Dann ist   und die Quadratreste sind  . Die Wurzeln der Quadratreste sind

  mit  ,
  wobei   und
  wobei  .

Weil  , aber   und  , zerfällt   in die beiden Perioden   und  .

Nachweis der Periodenlänge

Bearbeiten

Es ist schwierig, die Parameter   und   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   mit Glück faktorisieren könnte, etwa indem er einige Millionen zufällig erzeugte Probeteiler ausprobiert.

Wenn   und   so gewählt werden, dass gilt:

 , und
 ,

dann beträgt die Periodenlänge  .

  bezeichnet dabei die Ordnung des Elements   der primen Restklassengruppe  :

 .

Zur effizienten Berechnung kann ausgenutzt werden, dass die Elementordnung laut dem Satz von Lagrange ein Teiler der Gruppenordnung sein muss:

 .

Dafür muss die Faktorisierung der Gruppenordnung   bekannt sein (siehe Eulersche φ-Funktion).

Man muss   also so konstruieren, dass die Faktorisierungen von   und   bekannt sind oder mit vertretbarem Aufwand berechnet werden können, und ebenso die Faktorisierungen der um   verminderten Primfaktoren von   und  . 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   für alle Teiler   von   effizient berechnen.

Anwendung

Bearbeiten

Erzeugung von Zufallsbits

Bearbeiten

Aus jedem   werden ein oder mehrere Zufallsbits gewonnen. Im einfachsten Fall nimmt man das niederwertigste Bit, also

 ,

oder man berechnet das Paritätsbit zu  :

 .

Die Funktion   liefert die Zahl der Bits mit dem Wert 1 in der Binärdarstellung von  .

Eine weitere Möglichkeit ist die Bestimmung des Positionsbits, das von der Position von   im Intervall   abhängt:

 .

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

 .

Dabei bezeichnet   die bitweise UND-Verknüpfung.

Aus einem   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:

 .

Man kann zeigen, dass der BBS-Generator kryptografisch auch dann noch sicher ist, wenn bis zu   Bits aus jedem   extrahiert werden. Meist werden einfach die   niederwertigsten Bits genommen:

 ,

oder etwas elaborierter, mit „disjunkten“ Masken  :

 .

Symmetrisches Kryptosystem

Bearbeiten

Zunächst wird der BBS-Generator zur Umsetzung einer Stromchiffre verwendet. Als geheimer Schlüssel zwischen Sender und Empfänger dienen   und der Startwert   des Generators.

Z. B. generiert der Sender aus   und   nach der oben angegebenen Vorschrift die Folge der  . Die zugehörige Pseudozufallszahl   ergibt sich beispielsweise aus dem letzten Bit des jeweiligen Wertes von  , d. h.  . 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   und   die Folgen   und  . 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

Bearbeiten

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   und  .

Senderseitig laufen die Berechnungen analog zum obigen symmetrischen Fall ab. Zusätzlich zum Schlüsseltext   wird aber noch   gesendet. Da der Empfänger den Startwert nicht kennt, bildet er mit Hilfe der geheimen Primzahlen   und   die Folge der Pseudozufallszahlen ausgehend vom versendeten   bis zum Startwert   zurück. Für das Beispiel bedeutet das, der Empfänger erhält  ,  , sowie  .

  mit  

Der Ansatz bedient sich des Chinesischen Restealgorithmus, einem Spezialfall des chinesischen Restsatzes. Die beiden Unbekannten   und   sind von den Primfaktoren   und   abhängig und werden zu Beginn mittels des erweiterten euklidischen Algorithmus bestimmt. Dabei gilt  , also   im Beispiel. Damit ergibt sich die folgende Abarbeitung.

s3 = (22·152 mod 7 - 21·153 mod 11) mod 77
s3 = (22·1 - 21·9) mod 77 = 64
s2 = (22·642 mod 7 - 21·643 mod 11) mod 77
s2 = (22·1 - 21·3) mod 77 = 36
s1 = (22·362 mod 7 - 21·363 mod 11) mod 77
s1 = (22·1 - 21·5) mod 77 = 71
s0 = (22·712 mod 7 - 21·713 mod 11) mod 77
s0 = (22·1 - 21·4) mod 77 = 15
s = (22·152 mod 7 - 21·153 mod 11) mod 77
s = (22·1 - 21·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 Angriff mit frei wählbarem Geheimtext (englisch: chosen-ciphertext attack).

Sicherheit

Bearbeiten

Die Sicherheit des BBS-Generators basiert auf der Faktorisierungsannahme (FA).[1] Jeder, der BBS brechen kann, kann auch faktorisieren, was aber als praktisch unmöglich gilt. Folglich ist BBS sicher.

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

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   die Primfaktorzerlegung in   und   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 Prozent aller   in einem Jahr faktorisiert.

Wer faktorisieren kann, kann auch BBS brechen. Faktorisieren ermöglicht das Brechen der Quadratischen-Reste-Annahme, was es erlaubt, die Pseudozufallsfolge vorherzusagen.

Eine Einschränkung der Sicherheit besteht somit: Ein hypothetischer Quantencomputer könnte Shors Algorithmus nutzen, um den Modul   effizient zu faktorisieren. Solche Quantencomputer sind derzeit technisch nicht umsetzbar, es wird allerdings aktiv daran geforscht.

Quadratische-Reste-Annahme (QRA) (englisch: quadratic residuosity assumption): Es ist schwierig (im Sinne von aufwändig), von einer gegebenen Zahl   zu entscheiden, ob sie ein Quadratischer Rest in einem Restklassenring   ist, d. h. ob es eine Zahl   gibt, so dass   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   die Zahlen 1 und 3 die gleichen Quadrate:  . 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: Die Sicherheit des BBS-Generators ist äquivalent zur Faktorisierungsannahme.

Programmierung

Bearbeiten

Der folgende Quelltext in der Programmiersprache C++ zeigt die Implementierung eines BBS-Generators. Das Programm berechnet zwei Zufallszahlen und gibt sie auf der 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
    // todo: s*s sollte mit 128 bit Genauigkeit berechnet werden, damit n länger als 32 bit sein kann
    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 (unsigned b=32 ; b ; b >>= 1) // bestimme die Parität von h
        h ^= h >> b;
    return h & 1;
}

int 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;
    return 0;
}

Literatur

Bearbeiten
  • 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

Bearbeiten
  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