Blum-Blum-Shub

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.

Inhaltsverzeichnis

Definition

Der BBS-Generator ist definiert als Folge (si) durch die Iterationsvorschrift

 s_0 \!\, = s^2 \; \bmod \; n,
 s_{i+1} \!\, = s_i^2 \; \bmod \; n (dabei bezeichnet  \mod den Divisionsrest; siehe Modulo).

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

Der Parameter n sollte außerdem folgenden Bedingungen genügen, damit n möglichst schwer zu faktorisieren ist und der Generator garantiert hochwertige Zufallszahlen 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 2 < p / q < 1000.
  • p − 1 und p + 1 sowie q − 1 und q + 1 sollten jeweils einen großen Primfaktor haben, größer als ca.  \sqrt[4]{n} .

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

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

Periodenlänge

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

Die Periodenlänge des BBS-Generators ist immer ein Teiler von λ(λ(n)), wobei λ die Carmichael-Funktion ist. Wenn n und s so gewählt werden, dass gilt:

 \operatorname{ord}_{\lambda(n)/2}(2) = \lambda(\lambda(n)) , und
 \operatorname{ord}_n(s_0) = \lambda(n)/2 ,

dann beträgt die Periodenlänge λ(λ(n)).  \operatorname{ord}_b(a) bezeichnet dabei die Ordnung des Elements a der primen Restklassengruppe (\Z / b \Z)^\times:

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

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

 \operatorname{ord}_b(a) \; | \; \phi(b) .

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

Mann muss n also so konstruieren, dass die Faktorisierungen von p − 1 und q − 1 bekannt sind oder mit vertretbarem Aufwand berechnet werden können, und ebenso die Faktorisierungen der um 1 verminderten Primfaktoren von p − 1 und 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  a^m \; (\bmod \; b) für alle Teiler m von φ(b) effizient berechnen.


Anwendung

Erzeugung von Zufallsbits

Aus jedem si 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 si:

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.

Eine weitere Möglichkeit ist die Bestimmung des Positionsbits, das von der Position von si im Intervall [1,n − 1] abhängt:

 b_i = \begin{cases}
 1, &amp;amp; \text{wenn } s_i &amp;gt; \lfloor n/2 \rfloor\\
 0, &amp;amp; \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 si bestimmt wird. Dazu wählt man vorab eine Konstante z als Maske, die etwa so groß wie n ist und eine unregelmäßige, „zufällige“ Binärdarstellung aufweist, und berechnet

b_i = \operatorname{bitnum}(s_i \wedge z) \; \bmod \; 2.

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

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

 b_{2i} = s_i \; \bmod \; 2, \quad b_{2i+1} = \begin{cases}
 1, &amp;amp; \text{wenn } s_i &amp;gt; \lfloor n/2 \rfloor\\
 0, &amp;amp; \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  a = \lfloor \log_2 \log_2 n \rfloor Bits aus jedem si 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, mit „disjunkten“ Masken zj:

 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\cdot11=77 und s=64 nach der oben angegebenen Vorschrift die Folge der si. Die zugehörige Pseudozufallszahl bi ergibt sich beispielsweise aus dem letzten Bit des jeweiligen Wertes von si, d. h. bi=si 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 si und bi. 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 si+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 si+1 bis zum Startwert s zurück. Für das Beispiel bedeutet das, der Empfänger erhält 1111 sowie s4=15.

si-1 = (up\cdotsi(q+1)/4 mod q + vq\cdotsi(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\cdot11-3\cdot7=1 im Beispiel. Damit ergibt sich die folgende Abarbeitung.

s3 = (22\cdot152 mod 7 - 21\cdot153 mod 11) mod 77
s3 = (22\cdot1 - 21\cdot9) mod 77 = 64
s2 = (22\cdot642 mod 7 - 21\cdot643 mod 11) mod 77
s2 = (22\cdot1 - 21\cdot3) mod 77 = 36
s1 = (22\cdot362 mod 7 - 21\cdot363 mod 11) mod 77
s1 = (22\cdot1 - 21\cdot5) mod 77 = 71
s0 = (22\cdot712 mod 7 - 21\cdot713 mod 11) mod 77
s0 = (22\cdot1 - 21\cdot4) mod 77 = 15
s = (22\cdot152 mod 7 - 21\cdot153 mod 11) mod 77
s = (22\cdot1 - 21\cdot5) 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.


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   Deutsch Wikipedia

  • Blum Blum Shub — Saltar a navegación, búsqueda Blum Blum Shub (BBS) es un generador pseudoaleatorio de números propuesto por Lenore Blum, Manuel Blum y Michael Shub en 1986. El algoritmo BBS es: xn+1 = (xn)2 mod M donde M=pq es el producto de dos números primos… …   Wikipedia Español

  • Blum Blum Shub — (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al, 1986).Blum Blum Shub takes the form:: x n +1 = ( xn )2 mod M where M=pq is the product of two large primes p and q . At each… …   Wikipedia

  • Blum Blum Shub — Pour les articles homonymes, voir BBS. Blum Blum Shub (BBS) est un algorithme capable de produire des nombres pseudo aléatoires. Il fut proposé en 1986 par Lenore Blum, Manuel Blum et Michael Shub, d où son nom. On calcule la sortie de BBS en… …   Wikipédia en Français

  • Blum-Goldwasser-Kryptosystem — 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… …   Deutsch Wikipedia

  • Shub — ist der Familienname von Esfir Schub (1894–1953), sowjetische Regisseurin und Drehbuchautorin Michael Shub, Entwickler des Blum Blum Shub Generator Peter Shub (* 1957), US amerikanischer Clowndarsteller Diese Seite ist eine Be …   Deutsch Wikipedia

  • Blum-Shub-Smale machine — In computation theory, the Blum Shub Smale machine, or BSS machine, is a model of computation introduced by Lenore Blum, Michael Shub and Stephen Smale, intended to describe computations over the real numbers. Essentially, a BSS machine is a… …   Wikipedia

  • Blum-Goldwasser cryptosystem — The Blum Goldwasser (BG) cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum Goldwasser is a probabilistic, semantically secure cryptosystem with a constant size ciphertext expansion.… …   Wikipedia

  • Blum — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.  Pour les articles homophones, voir Bloom et Blume. Patronyme Blum est un nom de famille notamment porté par : Alain Blum (1958 ), historien et… …   Wikipédia en Français

  • Machine de Blum-Shub-Smale — Une machine de Blum Shub Smale (ou machine BSS) est une machine de Turing calculant sur les nombres réels (autrement dit, son alphabet de bande est ). Elle manipule les réels comme des entités atomiques (c est à dire sans s intéresser à leur… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”