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

Sicherheit des s²-mod-n-Generators[Bearbeiten]

Einleitung[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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.