Berechnungsverfahren

Blum-Micali Zufallsbits

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 ℤp*.

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

xi  =  gxi-1 mod p

 

Von der erzeugten Zahl xi wird nur ein Bit verwendet. Hierfür gibt es unterschiedliche 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)

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

Buch

[Weitere Informationen]

 

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