Zahlentheoretische Algorithmen der Kryptografie

Blum-Blum-Shub Zufallsbits

 aufwärts

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.

Grundlagen

Definition:  Eine Primzahl p mit p kongruent 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 kongruent 1 (mod 2). Damit gilt 2q kongruent 2 (mod 4) und 2q+1 kongruent 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.

Algorithmus

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

Es wird nun ein Startwert x0 mit ggt(x0, n) = 1 gewählt. Ausgehend vom Startwert x0 wird eine Folge von xi für i Element natürliche Zahlen nach folgender Iterationsformel berechnet:

xi  =  xi-12 mod n

 

Von der erzeugten Zahl xi 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 xi 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.

Implementierung

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

Literatur

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

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 22.06.2011   Updated: 08.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik