Zum Inhalt springen

Beweisarchiv: Kryptografie: Pseudozufall: Sicherheit des s2-mod-n-Generators

Aus Wikibooks

Beweisarchiv: Kryptografie

Sicherheitsdefinitionen: Äquivalente Definitionen informationstheoretischer Sicherheit
Kryptosysteme: Korrektheit des RSA-Kryptosystems · Sicherheit des GMR-Signatursystems
Pseudozufall: Sicherheit des s²-mod-n-Generators


Sicherheit des s2-mod-n-Generators

[Bearbeiten]

Einleitung

[Bearbeiten]

Der s2-mod-n-Generator (auch: Blum-Blum-Shub-Generator) erzeugt mittels eines zufälligen Schlüssels und eines Startwertes (engl. seed) durch Quadrieren eine zufällige Bitfolge .

Dazu werden zwei große Primzahlen und zufällig gewählt. Der im Folgenden verwendete Modulus kann für ein Kryptosystem als öffentlicher Schlüssel verwendet werden. Die Bitfolge wird aus dem Startwert wie folgt rekursiv berechnet:

Behauptung

[Bearbeiten]

Der s2-mod-n-Generator ist genau dann kryptografisch sicher (auch: komplexitätstheoretisch sicher), wenn die folgende Behauptung bewiesen werden kann:

  (polynomialer Vorhersagealgorithmus / Prädiktor)
  (Frequenz der unsicheren )
  (Grad der Polynome)

und wenn genügend groß ist, gilt für alle Schlüssel , ausgenommen den -Anteil:

Zur Erklärung:

Mit der „Frequenz der unsicheren ” ist gemeint, für wie viele der Schlüssel der s2-mod-n-Generator keine „guten” Zufallsbitfolgen generiert.

ist die Wahrscheinlichkeit, dass der Prädiktor mit Kenntnis eines Teils der Bitkette und des Modulus das vorangegangene Zufallsbit richtig vorhersagt, obwohl der Startwert zufällig gewählt wurde.

Beweis mit Quadratische-Reste-Annahme

[Bearbeiten]

Annahme: Wir nehmen an, es gebe solch einen Prädiktor, der zu mit -Vorteil (also Wahrscheinlichkeit größer ) richtig rät.

Es ist zu zeigen, dass die Annahme im Widerspruch zur Quadratischen-Reste-Annahme steht.

Widerspruchsbeweis:

Wir konstruieren aus einen Prädiktor , der zu gegebenem das letzte Bit von , also vorhersagt.

Prädiktor :

P'(s[1], n){
  b[1] := s[1] (mod 2)
  for(1 < i <= k){
    s[i] := s[i-1] * s[i-1] (mod n)
    b[i] := s[i] (mod 2)
  }
  b[0] := P(b[·], n)
  return b[0]
}

Dieser verwendet und rät damit ebenfalls mit -Vorteil richtig.

Unser Ziel ist es nun, aus einen Algorithmus zu entwickeln, der mit -Vorteil rät, ob ein beliebiges mit Jacobi-Symbol quadratischer Rest ist.

R(s', n){
  s[1] := s' * s' (mod n)
  b[0] := P'(s[1], n)
  b' := letztesBit(s')   
  if(b[0] = b')
    return "s' ist quadratischer Rest"
  else
    return "s' ist nicht quadratischer Rest"
}

Wenn gilt, dann ist quadratischer Rest, da als erste Wurzel von quadratischer Rest ist. Andernfalls kann nicht quadratischer Rest sein, da nur eine der vier Wurzeln quadratischer Rest ist.

Nun müssen wir noch zeigen, dass es reicht, das letzte Bit von mit zu vergleichen.

1.Fall:

2.Fall: und

und

Damit ist der oben genannte Algorithmus korrekt und sagt mit -Vorteil voraus, ob . Dies ist ein Widerspruch zur Quadratischen-Reste-Annahme. Folglich gilt die obige Annahme nicht.

Beweis mit Faktorisierungsannahme

[Bearbeiten]

Dieses Buch wird durch intensive Zusammenarbeit sicher schnell besser. Der Hauptautor freut sich über jeden, der mitmacht. Kaputtmachen kannst du nicht viel – also sei mutig. Wenn etwas nicht passt, rührt sich der Hauptautor bestimmt. Danke.

Anmerkung: Es wäre schön, wenn noch jemand ergänzen könnte, wie man die Sicherheit des Generators auf Faktorisierung zurückführt.

Wikipedia-Verweise

[Bearbeiten]

 Blum-Blum-Shub-Generator
 Kryptosystem
 Polynomialzeit
 Quadratischer Rest
 Jacobi-Symbol


Beweisarchiv: Kryptografie

Sicherheitsdefinitionen: Äquivalente Definitionen informationstheoretischer Sicherheit
Kryptosysteme: Korrektheit des RSA-Kryptosystems · Sicherheit des GMR-Signatursystems
Pseudozufall: Sicherheit des s²-mod-n-Generators