Berechnungsverfahren

Blum-Blum-Shub Zufallsbits

Kryptografisch sichere Zufallsbits haben die Eigenschaft, dass ein Angreifer auch in Kenntnis von beliebig vielen vorherigen Bits das nächste Bit nicht effizient vorhersagen kann.

Definition: Eine Primzahl p mit p ≡ 3 (mod 4) wird als Blum-Primzahl bezeichnet.

Beispiel: Die Primzahlen 3, 7, 11, 19, 23, 31, ... sind Blum-Primzahlen; die Primzahlen 5, 13, 17, 29, ... sind keine Blum-Primzahlen.

Satz: Jede starke Primzahl p mit p > 5 ist eine Blum-Primzahl.

Beweis: Eine starke Primzahl hat die Form p = 2q+1 mit q Primzahl. Da p > 5 gilt q > 2; damit ist q ungerade, d.h. q ≡ 1 (mod 2). Damit gilt 2q ≡ 2 (mod 4) und 2q+1 ≡ 3 (mod 4). Also ist p Blum-Primzahl.

Andererseits ist nicht jede Blum-Primzahl p mit p > 5 eine starke Primzahl. Die Primzahl 19 beispielsweise ist Blum-Primzahl, aber keine starke Primzahl, denn es gilt 19 = 2·9+1, und 9 ist keine Primzahl.

Es sei n = p·q, wobei p und q zwei verschiedene Blum-Primzahlen sind.

Es wird nun ein Startwert x₀ mit ggt(x₀, n) = 1 gewählt. Ausgehend vom Startwert x₀ wird eine Folge von x_i für i ∈ ℕ nach folgender Iterationsformel berechnet:

x_i = x_i-1² mod n

Von der erzeugten Zahl x_i wird nur ein Bit verwendet. Hierfür gibt es unterschiedliche Möglichkeiten. Es kann ein bestimmtes Bit der Zahl verwendet werden (z.B. das letzte oder das drittletzte) oder es kann das Exklusiv-Oder von mehreren bestimmten Bits genommen werden oder es kann die Position von x_i im Intervall [1, n-1] herangezogen werden (Position in der unteren Hälfte: 0, in der oberen Hälfte: 1). Die letztere Möglichkeit wird in der folgenden Implementierung gewählt.

Die Erzeugung von Zufallsbits ist als Generatorfunktion in der Programmiersprache Python implementiert.

In der Generatorfunktion randomBits werden zunächst zwei Blum-Primzahlen p und q zufällig gewählt und daraus das Produkt n = p·q gebildet, wobei n die Länge von k Bits hat. Mit der Funktion randint wird ein Startwert für x solange zufällig aus der Menge {2, ..., n-2} gewählt, bis ggt(x, n) = 1 gilt. Daraufhin wird x iteriert; die Yield-Anweisung liefert eine 1, wenn x > n/2 ist, sonst eine 0.

def randomBits(k):
    p=randomBlumPrime(k//2-1)
    q=randomBlumPrime(k-k//2+1)
    n=p*q
    x=randint(2, n-2)
    while ggt(x, n)!=1:
        x=randint(2, n-2)
    while True:
        x=x*x%n
        yield int(2*x > n)

Mit dem folgenden Programmstück werden 20 Zufallsbits auf Basis einer 50 Bit langen Zahl n erzeugt und auf dem Bildschirm ausgegeben.

# Test
if __name__ == "__main__":
    r=randomBits(50)
    for i in range(20):
        print r.next(),
    print

[BBS 86] L. Blum, M. Blum, M. Shub: A Simple Unpredictable Pseudo-Random Number Generator. SIAM Journal on Computing 15, 2, 364-383 (1986)

[Lan 18] H.W. Lang: Kryptografie für Dummies. Wiley (2018)

[Weitere Informationen]

Weiter mit: [up]

H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 22.06.2011 Updated: 17.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden

Berechnungsverfahren

Blum-Blum-Shub Zufallsbits

Grundlagen

Algorithmus

Implementierung

Literatur