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{\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²-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²-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\!\,'$ :

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 $\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.

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 $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