Rabin-Verfahren ohne(!!) p = q = 3 mod 4

01.07.2013, 00:40

martin57

Rabin-Verfahren ohne(!!) p = q = 3 mod 4

Hallo, ich habe eine Frage zum Rabin-Verfahren. Ich habe jetzt ca. 1 Stunde "gegoogelt" und in jeder Quelle steht "man wählt $\begin{eqnarray*} p \equiv q \equiv 3 \mbox{ mod } 4 \end{eqnarray*}$ , aber nur der Einfachheit halber etc usw, man kann ja auch beliebige Primzahlen nehmen". Da wollte ich mich natürlich anhand eines Beispiels selbst überzeugen und was passiert - es klappt natürlich nicht ...

Meine Frage ist jetzt, ob mir jemand einen Link angeben kann, wo das Rabin-Verfahren in allgemeiner Form erklärt wird bzw. mir sagen kann, was am folgenden Beispiel falsch läuft?

Beispiel:
Ich wähle $\begin{eqnarray*} p = 11 \end{eqnarray*}$ und $\begin{eqnarray*} q = 23 \end{eqnarray*}$ . Dann ist $\begin{eqnarray*} m = p \cdot q = 253 \end{eqnarray*}$ . Die Nachricht $\begin{eqnarray*} z = 158 \end{eqnarray*}$ möchte ich damit verschlüsseln, also

$\begin{eqnarray*} c \equiv 158^2 \equiv 170 \mbox{ mod } m \end{eqnarray*}$ .

Nun möchte ich das ganze wieder entschlüsseln:

$\begin{eqnarray*} z_p \equiv 170^{12} \equiv 170^{2^3} \cdot 170^{2^2} \equiv 4 \cdot 9 \equiv 3 \mbox{ mod } p = 11 \end{eqnarray*}$

und

$\begin{eqnarray*} z_q \equiv 170^{24} \equiv 170^{2^4} \cdot 170^{2^3} \equiv 8 \cdot 13 \equiv 12 \mbox{ mod } q = 23 \end{eqnarray*}$ .

Außerdem bestimme ich $\begin{eqnarray*} k_p = -2 \end{eqnarray*}$ und $\begin{eqnarray*} k_q = 1 \end{eqnarray*}$ (Bézout-Koeffizienten).

Dann gilt

$\begin{eqnarray*} r \equiv k_p \cdot p \cdot z_q + k_q \cdot q \cdot z_p \equiv -2 \cdot 11 \cdot 12 + 1 \cdot 23 \cdot 3 \equiv - 264 + 69 \equiv 58 \mbox{ mod } m = 253 \end{eqnarray*}$

und hier stimmt was nicht, denn 58 ist keine Quadratwurzel von 170 mod 253. Was hab ich falsch gemacht?

01.07.2013, 19:49

watcher

Auf diesen Beitrag antworten »

Hallo martin,

leider ist deine Rechnung sehr schwer nachvollziehbar da du etliche Bezeichnungen einführst aber nicht erklärst was diese bedeuten (z.B $\begin{eqnarray*} z_p , k_p \end{eqnarray*}$ ) und auch nicht erklärst was du berechnest und wie.

Ferner rechnest du sehr umständlich:

Zitat:

$\begin{eqnarray*} z_p \equiv 170^{12} \equiv 170^{2^3} \cdot 170^{2^2} \equiv 4 \cdot 9 \equiv 3 \mbox{ mod } p = 11 \end{eqnarray*}$

Nach dem kleiner Fermat ist $\begin{eqnarray*} a^{p-1}\equiv 1 \mod p \end{eqnarray*}$ für alle a mit $\begin{eqnarray*} p \nmid a \end{eqnarray*}$ .
und $\begin{eqnarray*} 170 \equiv 5 \mod 11 \end{eqnarray*}$ , also
$\begin{eqnarray*} 170^{12}\equiv 5^2 \equiv 25 \equiv 3 \mod 11 \end{eqnarray*}$
Allerdings ist $\begin{eqnarray*} 3^2\equiv 9 \not\equiv 5 \equiv 170 \mod 11 \end{eqnarray*}$ was vermutlich gelten soll.

Allerdings dürfte $\begin{eqnarray*} z_p= c^{\frac{p+1}{4}} \end{eqnarray*}$
also $\begin{eqnarray*} 170 ^6 \end{eqnarray*}$ sein. $\begin{eqnarray*} z_p \end{eqnarray*}$ ist doch die Wurzel aus c modulo p?

Anmerkung zu dem "ohne":
Das ändert nur den Schritt "Wurzel aus Geheimtext modulo p ziehen".
Wurzelziehen für Primzahlen mit $\begin{eqnarray*} p\equiv 1 \mod 4 \end{eqnarray*}$ ist prinzipiell möglich, allerdings nicht annähernd so schnell wie für die anderen.
Wikipedia schlägt den Berlekamp-Algorithmus vor.

Neue Frage »

Antworten »

Rabin-Verfahren ohne(!!) p = q = 3 mod 4

Verwandte Themen