Zahlentheoretische Algorithmen der Kryptografie

Blum-Blum-Shub Zufallsbits

 aufwärts

Krypto­grafisch 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 beispiels­weise 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 Iterations­formel berechnet:

xi  =  xi-12 mod n

 

Von der erzeugten Zahl xi wird nur ein Bit verwendet. Hierfür gibt es unter­schiedliche Möglich­keiten. 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 Generator­funktion in der Programmier­sprache Python implementiert.

In der Generator­funktion 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 Programm­stü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   ©   Created: 22.06.2011   Updated: 26.02.2017
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