Einleitung

Der s²-mod-n-Generator (auch: Blum-Blum-Shub-Generator) erzeugt mittels eines zufälligen Schlüssels ${\displaystyle n}$ und eines Startwertes ${\displaystyle s}$ (engl. seed) durch Quadrieren eine zufällige Bitfolge ${\displaystyle b_{0}\,b_{1}\,\dots \,b_{k}}$.

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

${\displaystyle {\begin{aligned}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{aligned}}}$

Behauptung

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

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

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

${\displaystyle \forall t\in \mathbb {N} }$   (Grad der Polynome)

und wenn ${\displaystyle l=|n|}$ genügend groß ist, gilt für alle Schlüssel ${\displaystyle n}$, ausgenommen den ${\displaystyle \delta }$-Anteil:

${\displaystyle 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 ${\displaystyle n}$” ist gemeint, für wie viele der Schlüssel der s²-mod-n-Generator keine „guten” Zufallsbitfolgen generiert.

${\displaystyle 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 ${\displaystyle b_{1}\,b_{2}\,\dots \,b_{k}}$ und des Modulus ${\displaystyle n}$ das vorangegangene Zufallsbit ${\displaystyle b_{0}}$ richtig vorhersagt, obwohl der Startwert ${\displaystyle s}$ zufällig gewählt wurde.

Beweis mit Quadratische-Reste-Annahme

Annahme: Wir nehmen an, es gebe solch einen Prädiktor, der ${\displaystyle b_{0}}$ zu ${\displaystyle b_{1}\,b_{2}\,\dots \,b_{k},\ n}$ mit ${\displaystyle \epsilon }$-Vorteil (also Wahrscheinlichkeit größer ${\displaystyle {\frac {1}{2}}}$) richtig rät.

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

Widerspruchsbeweis:

Wir konstruieren aus ${\displaystyle P}$ einen Prädiktor ${\displaystyle P\!\,'}$, der zu gegebenem ${\displaystyle s_{1}}$ das letzte Bit von ${\displaystyle s_{0}}$, also ${\displaystyle b_{0}}$ vorhersagt.

Prädiktor ${\displaystyle 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 ${\displaystyle P}$ und rät damit ebenfalls mit ${\displaystyle \epsilon }$-Vorteil richtig.

Unser Ziel ist es nun, aus ${\displaystyle P\!\,'}$ einen Algorithmus ${\displaystyle R}$ zu entwickeln, der mit ${\displaystyle \epsilon }$-Vorteil rät, ob ein beliebiges ${\displaystyle s\!\,'\in \mathbb {Z} /n^{\times }}$ mit Jacobi-Symbol ${\displaystyle \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 ${\displaystyle s\!\,'=s_{0}}$ gilt, dann ist ${\displaystyle s\!\,'}$ quadratischer Rest, da ${\displaystyle s_{0}}$ als erste Wurzel von ${\displaystyle s_{1}}$ quadratischer Rest ist. Andernfalls kann ${\displaystyle 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 ${\displaystyle s\!\,'}$ mit ${\displaystyle b_{0}}$ zu vergleichen.

1.Fall: ${\displaystyle s\!\,'=s_{0}\quad \Rightarrow \quad b\!\,'=b_{0}}$

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

${\displaystyle \Rightarrow \quad s\!\,'\equiv -s_{0}{\pmod {n}}}$

${\displaystyle \Rightarrow \quad s\!\,'=n-s_{0}}$ und ${\displaystyle n{\text{ ungerade}}}$

${\displaystyle \Rightarrow \quad b\!\,'\neq b_{0}}$

Damit ist der oben genannte Algorithmus ${\displaystyle R}$ korrekt und sagt mit ${\displaystyle \epsilon }$-Vorteil voraus, ob ${\displaystyle s\!\,'\in QR_{n}}$. Dies ist ein Widerspruch zur Quadratischen-Reste-Annahme. Folglich gilt die obige Annahme nicht.

Beweis mit Faktorisierungsannahme

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