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

Aus Wikibooks

Wechseln zu: Navigation, Suche

Beweisarchiv: Kryptografie

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


Inhaltsverzeichnis

[Bearbeiten] Sicherheit des s2-mod-n-Generators

[Bearbeiten] Einleitung

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

Dazu werden zwei große Primzahlen p \equiv 3 \pmod 4 und q \equiv 3 \pmod 4 zufällig gewählt. Der im Folgenden verwendete Modulus n = p \cdot q kann für ein Kryptosystem als öffentlicher Schlüssel verwendet werden. Die Bitfolge wird aus dem Startwert s \in \mathbb{Z}/n^{\times} wie folgt rekursiv berechnet:

\begin{align} s_0 & := s^2 \pmod n & \qquad b_0 & := s_0 \pmod 2 \\ s_i & := s_{i-1}^2 \pmod n & \qquad b_i & := s_i \pmod 2 \end{align}

[Bearbeiten] Behauptung

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

\forall P   (polynomialer Vorhersagealgorithmus / Prädiktor)
\forall \delta,\ 0 < \delta < 1   (Frequenz der unsicheren n)
\forall t \in \mathbb{N}   (Grad der Polynome)

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

W(P(n, b_1, b_2, \dots , b_k) = b_0 | s \in \mathbb{Z}/n^{\times} \text{random}) < \frac{1}{2} + \frac{1}{l^t}

Zur Erklärung:

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

W(P(n, b_1, b_2, \dots , b_k) = b_0 | s \in \mathbb{Z}/n^{\times} \text{random}) ist die Wahrscheinlichkeit, dass der Prädiktor mit Kenntnis eines Teils der Bitkette b_1\, b_2\, \dots \, b_k und des Modulus n das vorangegangene Zufallsbit b0 richtig vorhersagt, obwohl der Startwert s zufällig gewählt wurde.

[Bearbeiten] Beweis mit Quadratische-Reste-Annahme

Annahme: Wir nehmen an, es gebe solch einen Prädiktor, der b0 zu b_1\, b_2\, \dots \, b_k,\ n mit ε-Vorteil (also Wahrscheinlichkeit größer \frac12) richtig rät.

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

Widerspruchsbeweis:

Wir konstruieren aus P einen Prädiktor P\!\,', der zu gegebenem s1 das letzte Bit von s0, also b0 vorhersagt.

Prädiktor P\!\,':

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 P und rät damit ebenfalls mit ε-Vorteil richtig.

Unser Ziel ist es nun, aus P\!\,' einen Algorithmus R zu entwickeln, der mit ε-Vorteil rät, ob ein beliebiges s\!\,' \in \mathbb{Z}/n^{\times} mit Jacobi-Symbol \left( \frac{s\!\,'}{n} \right) = 1 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 s\!\,' = s_0 gilt, dann ist s\!\,' quadratischer Rest, da s0 als erste Wurzel von s1 quadratischer Rest ist. Andernfalls kann s\!\,' 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 s\!\,' mit b0 zu vergleichen.

1.Fall: s\!\,' = s_0 \quad \Rightarrow \quad b\!\,' = b_0

2.Fall: s\!\,' \neq s_0 und \left( \frac{s\!\,'}{n} \right) = \left( \frac{s_0}{n} \right) = 1

\Rightarrow \quad s\!\,' \equiv -s_0 \pmod n
\Rightarrow \quad s\!\,' = n - s_0 und n ungerade
\Rightarrow \quad b\!\,' \neq b_0

Damit ist der oben genannte Algorithmus R korrekt und sagt mit ε-Vorteil voraus, ob s\!\,' \in QR_n. Dies ist ein Widerspruch zur Quadratischen-Reste-Annahme. Folglich gilt die obige Annahme nicht.

[Bearbeiten] Beweis mit Faktorisierungsannahme

Good art ru.svg 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.

[Bearbeiten] Wikipedia-Verweise

Wikipedia-logo.png Blum-Blum-Shub-Generator
Wikipedia-logo.png Kryptosystem
Wikipedia-logo.png Polynomialzeit
Wikipedia-logo.png Quadratischer Rest
Wikipedia-logo.png 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
Von „http://de.wikibooks.org/wiki/Beweisarchiv:_Kryptografie:_Pseudozufall:_Sicherheit_des_s2-mod-n-Generators“
Persönliche Werkzeuge