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

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 s$^2$-mod-n-Generators
### Einleitung

Der s$^2$-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{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$^2$-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 $\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$^2$-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 $\epsilon$-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\!\,'$, der zu gegebenem $s_{1}$ das letzte Bit von $s_{0}$, also $b_{0}$ vorhersagt.
Prädiktor $P\!\,'$:
Dieser verwendet $P$ und rät damit ebenfalls mit $\epsilon$-Vorteil richtig.
Unser Ziel ist es nun, aus $P\!\,'$ einen Algorithmus $R$ zu entwickeln, der mit $\epsilon$-Vorteil rät, ob ein beliebiges $s\!\,'\in \mathbb {Z} /n^{\times }$ mit Jacobi-Symbol $\left({\frac {s\!\,'}{n}}\right)=1$ quadratischer Rest ist.
Wenn $s\!\,'=s_{0}$ gilt, dann ist $s\!\,'$ quadratischer Rest, da $s_{0}$ als erste Wurzel von $s_{1}$ 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 $b_{0}$ 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{\text{ ungerade}}$
    $\Rightarrow \quad b\!\,'\neq b_{0}$
Damit ist der oben genannte Algorithmus $R$ korrekt und sagt mit $\epsilon$-Vorteil voraus, ob $s\!\,'\in QR_{n}$. Dies ist ein Widerspruch zur Quadratischen-Reste-Annahme. Folglich gilt die obige Annahme nicht.

### Beweis mit Faktorisierungsannahme

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

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