Zahlentheoretische Algorithmen der Kryptografie

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

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 Iterationsformel berechnet:

xi  =  gxi-1 mod p

 

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, 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 Generatorfunktion in der Programmiersprache Python implementiert.

In der Generatorfunktion 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 Programmstü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   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