quadratische Restgenerator

15.07.2005, 17:17	amsel	Auf diesen Beitrag antworten »
quadratische Restgenerator hallo habe gleich noch eine frage. zum s^2 mod n generator hier eine beschreibung Blum, Blum und Shub Bei diesem PRNG (auch BBS abgekürzt und gelegentlich als "quadratische Restgenerator" bezeichnet) handelt es sich um einen recht einfachen, auf großen Zahlen basierenden Zufallsgenerator. Dabei sucht man zunächst zwei große Primzahlen p und q, welche kongruent 3 modulo 4 sind, d. h.: p mod 4 = 3 (selbiges gilt für q) Dann bildet man das Produkt n: n = pq (n ist übrigens eine sog. Blumsche Zahl.) Nun benötigen wir noch eine Zahl x, die zu n relativ prim ist; d. h., x hat keine gemeinsamen Teiler außer 1 mit n (Beispiel: 21 [3 · 7] ist relativ prim zu 10 [2 · 5]). Um den Generator zu starten, wird der Startwert x0 berechnet: $\begin{eqnarray} x0 = x^ 2 mod n \end{eqnarray}$ Jetzt kann's losgehen. Das i-te Zufallsbit wird erzeugt, indem zunächst $\begin{eqnarray} x_i = x_(i-1) ^2 mod n \end{eqnarray}$ berechnet wird; von diesem Wert wird nur das niederwertigste Bit verwendet (das ist äquivalent zu einer Modulo-2-Operation; das niederwertigste Bit von 7 ist 1, da 7 mod 2 = 1). Der Vorteil dieses Generators ist, dass man das i-te Bit direkt berechnen kann, ohne die vorherigen i 1 Bits zu kennen: $\begin{eqnarray} x_i = x_0^{(2i) mod ((p - 1)(q - 1))} \end{eqnarray}$ Aus diesem Grund eignet sich der BBS-Generator gut für Dateien mit wahlfreiem Zugriff. Warum ist dieses Verfahren sicher? Der BBS-Generator setzt auf die Schwierigkeit der Faktorisierung von n. Dieser Wert selbst kann öffentlich bekannt sein, ohne Kenntnis der Faktoren p und q jedoch ist es nicht möglich, die Ausgabe des Generators vorherzusagen. Dank dieser Eigenschaft kann ein Kryptoanalytiker weder das vorhergehende noch das nächste Bit der Folge berechnen. wenn man das ganze an dem bespiel n = 3 * 11 = 33, x = 2 dann kommt man auf $\begin{eqnarray} \begin{matrix} x_i & 4 &16&25&31&4&\cdot\cdot\cdot \\ b_i & 0 & 0 &1&1&0&\cdot\cdot\cdot \end{matrix} \end{eqnarray}$ bi ... letzte bit einer zahl damit komm wiederholt sich doch das ganze nun immer wieder. --> damit wäre es ja dann doch vorrauszusagen liegt einzig daran das die zahlen zu klein sind oder ???? danke für eure hilfe
15.07.2005, 18:06	AD	Auf diesen Beitrag antworten »
Nach spätestens n Bits läuft auch dieser Generator in eine Periode. Der Beweis dafür ist äußerst simpel. (Das heißt jetzt nicht notwendig, dass die Periode sofort vom Start weg beginnt.)
15.07.2005, 18:12	amsel	Auf diesen Beitrag antworten »
also liegt es bei meinem beispiel nur an den sehr klein gehaltenen werten. gut dankeschön :-)
15.07.2005, 18:22	AD	Auf diesen Beitrag antworten »
Brauchbar ist der Generator also erst, wenn das n deutlich größer ist, als die Anzahl der Bits, die er generieren soll. Spricht also nicht gerade für den Generator, falls man sehr viele Bits brauchen sollte...
15.07.2005, 19:04	amsel	Auf diesen Beitrag antworten »
ja nur sicher ist er.
15.07.2005, 19:46	AD	Auf diesen Beitrag antworten »
Was man halt unter Sicherheit versteht. Ich kenne jedenfalls keinen einzigen Pseudozufallsgenerator (um einen solchen handelt es sich hier), der mathematisch beweisbar "zufällige" Zahlen (oder Bits) erzeugt.
Anzeige

15.07.2005, 20:14	amsel	Auf diesen Beitrag antworten »
ja mit dem beweisen ist das so ne sache das nich so ganz einfach ist. aber da du dich ja glücklicher weise damit auskennst kannst mir vielleicht auch bei meiner nächsten frage helfen. wenn ich den PBG $\begin{eqnarray} s^2 mod n \end{eqnarray}$ als asymetrisches Konzelationssystem verwende kann man das ganze brechen indem man die Schlüsseltextfolge welche mit einem Klartext : $\begin{eqnarray} x = x_0,x_1,x_2,\cdot\cdot\cdot, x_k \end{eqnarray}$ und einer Pseudozufallsbitfolge von : $\begin{eqnarray} b = b_0,b_1,b_2,\cdot\cdot\cdot, b_k \end{eqnarray}$ man zu dem orginal Schlusseltext kommt: $\begin{eqnarray} x_0\oplus b_0,x_1\oplus b_1,x_2\oplus b_2,\cdot\cdot\cdot, x_k\oplus b_k, s_{k+1} \end{eqnarray}$ wobei $\begin{eqnarray} s_{k+1} \end{eqnarray}$ mitgesendet wird damit der empfänger wurzeln ziehen kann und damit die verwendete b folge sich erzeugen kann. wenn man den schlüsseltext nun verändert indem man $\begin{eqnarray} x_0\oplus b_0,x_1\oplus b_1,x_2\oplus b_2,\cdot\cdot\cdot, x_k\oplus b_k, \end{eqnarray}$ duch $\begin{eqnarray} k+1 \end{eqnarray}$ zufällige bit ersetzt. soll der angreifer aus der antwort des opfers die Pseudozufallsbitfolge errechnen können und damit den ursprünglichen Schlüsseltext entschlüsseln können. nur mir fehlt im moment die idee wie man aus der antwort (wie die aussieht weis ich auch nciht genau sollte doch eigentlich die entschlüsselung der veränderten bitfolge des angreifers sein. oder?) dann die pseudozufallsbitfolge errechnet. kannst du mir da auch weiter helfen?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »