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

Sicherheit des s²-mod-n-Generators

Einleitung

Der s²-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(\mathrm{mod}4)$ und $q\equiv 3(\mathrm{mod}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{array}{cccc}{s}_0& :=s^2(\mathrm{mod}n)& b_0& :=s_0(\mathrm{mod}2)\\ s_i& :=s_{i-1}^2(\mathrm{mod}n)& b_i& :=s_i(\mathrm{mod}2)\end{array}$

Behauptung

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

$\mathrm{\forall }P$   (polynomialer Vorhersagealgorithmus / Prädiktor)

$\mathrm{\forall }\delta ,0<\delta <1$   (Frequenz der unsicheren $n$)

$\mathrm{\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 $\delta$-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 s²-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 $b_0$ richtig vorhersagt, obwohl der Startwert $s$ zufällig gewählt wurde.

Beweis mit Quadratische-Reste-Annahme

Annahme: Wir nehmen an, es gebe solch einen Prädiktor, der $b_0$ zu $b_1{b}_2\dots b_k,n$ mit $ϵ$-Vorteil (also Wahrscheinlichkeit größer $\frac{1}{2}$) 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{}^{\prime }$, der zu gegebenem $s_1$ das letzte Bit von $s_0$, also $b_0$ vorhersagt.

Prädiktor $P{}^{\prime }$:

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{}^{\prime }$ einen Algorithmus $R$ zu entwickeln, der mit $ϵ$-Vorteil rät, ob ein beliebiges $s{}^{\prime }\in \mathbb{Z}/n^{\times }$ mit Jacobi-Symbol $\left(\frac{s{}^{\prime }}{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{}^{\prime }=s_0$ gilt, dann ist $s{}^{\prime }$ quadratischer Rest, da $s_0$ als erste Wurzel von $s_1$ quadratischer Rest ist. Andernfalls kann $s{}^{\prime }$ 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{}^{\prime }$ mit $b_0$ zu vergleichen.

1.Fall: $s{}^{\prime }=s_0\Rightarrow b{}^{\prime }=b_0$

2.Fall: $s{}^{\prime }\ne s_0$ und $\left(\frac{s{}^{\prime }}{n}\right)=\left(\frac{s_0}{n}\right)=1$

$\Rightarrow s{}^{\prime }\equiv -s_0(\mathrm{mod}n)$

$\Rightarrow s{}^{\prime }=n-s_0$ und $n\text{ ungerade}$

$\Rightarrow b{}^{\prime }\ne b_0$

Damit ist der oben genannte Algorithmus $R$ korrekt und sagt mit $ϵ$-Vorteil voraus, ob $s{}^{\prime }\in Q{R}_n$. Dies ist ein Widerspruch zur Quadratischen-Reste-Annahme. Folglich gilt die obige Annahme nicht.

Beweis mit Faktorisierungsannahme

Vorlage:Hauptautor wünscht Mitarbeit 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

Vorlage:W
Vorlage:W
Vorlage:W
Vorlage:W
Vorlage:W

---