Zahlentheoretische Algorithmen der Kryptografie

Blum-Micali 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.

Algorithmus

Es sei p eine starke Primzahl und g ein erzeugendes Element der Gruppe ganze Zahlenp*.

Es wird nun ein Startwert x0 Element {2, ..., p-2} gewählt. Ausgehend vom Startwert x0 wird eine Folge von xi für i Element natürliche Zahlen nach folgender Iterations­formel berechnet:

xi  =  gxi-1 mod p

 

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, p-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 wird zunächst eine Primzahl p der Länge k Bits und ein erzeugendes Element g zufällig gewählt. Mit der Funktion randint wird ein Startwert für x gewählt. Anschließend wird x iteriert; die Yield-Anweisung liefert eine 1, wenn x > p/2 ist, sonst eine 0.

def randomBits(k):
    p=randomStrongPrime(k)
    g=generatingElement(p)
    x=randint(2, p-2)
    while True:
        x=modexp(g, x, p)
        yield int(2*x > p)

Mit dem folgenden Programm­stück werden 20 Zufallsbits auf Basis einer 50 Bit langen Primzahl p erzeugt und auf dem Bildschirm ausgegeben.

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

Literatur

[BM 84]M. Blum, S. Micali: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits. SIAM Journal on Computing 13, 4, 850-864 (1984)

 

Weiter mit:   [Blum-Blum-Shub-Zufallsbits]   oder   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