Ein RSA-Äquivalent für elliptischen Kurven über $\mathbb{Z}_{n}\protect$

Algorithmus 6.1 (KMOV)  

1. Schlüsselpaar-Erzeugung:

   A führt die folgenden Schritte durch:

   • wähle zwei Primzahlen $p$ und $q$ mit $p\equiv 2\, \mod 3$ und $q\equiv 2\, \mod 3$
   • berechne $n\leftarrow pq$
   • wähle eine zufällige Zahl $e$, so daß $\textrm{ggT}\left( e,\left( p+1\right) \left( q+1\right) \right) =1$
   • berechne ein $d$, so daß $ed\equiv 1\mod \left( p+1\right) \left( q+1\right)$.
   As öffentlicher Schlüssel ist $\left( n,e\right)$. As geheimer Schlüssel ist $d$.

2. Verschlüsselung:

   B führt die folgenden Schritte durch, um eine Nachricht $M=\left( x,y\right) \in \mathbb{Z}_{n}\times \mathbb{Z}_{n}$ an A zu übertragen:

   • besorge As authentischen, öffentlichen Schlüssel $\left( n,e\right)$
   • berechne $\left( c_{1},c_{2}\right) \leftarrow e\cdot \left( x,y\right)$ in der Gruppe $\tilde{E}_{0,b}\left( \mathbb{Z}_{n}\right) =E_{0,b}\left( \mathbb{F}_{p}\right) \times E_{0,b}\left( \mathbb{F}_{q}\right)$, wobei $b=y^{2}-x^{3}\mod n$.
   $C=\left( c_{1},c_{2}\right)$ ist die Verschlüsselung von $M$.

3. Entschlüsselung:

   A führt den folgenden Schritt durch:

   • berechne $M=\left( x,y\right) \leftarrow d\cdot \left( c_{1},c_{2}\right)$.

Beachte hierbei, daß B im 2. Schritt die Faktoren $p$ und $q$ nicht kennt, aber trotzdem in $\tilde{E}_{0,b}\left( \mathbb{Z}_{n}\right)$ rechnen kann, indem er die Pseudo-Addition in $E_{0,b}\left( \mathbb{Z}_{n}\right)$ anwendet (vgl. Kapitel 3). Die Wahrscheinlichkeit, daß das Rechnen in $E_{0,b}\left( \mathbb{Z}_{n}\right)$ fehlschlägt ist sehr gering.

Um die Korrektheit des Verfahrens zu verifizieren, stellen wir zuerst fest:

Theorem 6.2   Es sei $q$ eine Potenz einer ungeraden Primzahl, so daß $q\equiv 2\mod 3$ gilt, und sei weiter $b\in \mathbb{F}_{q},b\neq 0$. Betrachte die elliptische Kurve $E:y^{2}=x^{3}+b$ über $\mathbb{F}_{q}$. Dann gilt

$$\char93 E\left( \mathbb{F}_{q}\right) =q+1.$$

Als Folgerung des Satzes erhalten wir

$$\char93 E_{0,b}\left( \mathbb{F}_{p}\right) =p+1 \char93 E_{0,b}\left( \mathbb{F}_{q}\right) =q+1$$

und damit

$$\char93 \tilde{E}_{0,b}\left( \mathbb{Z}_{n}\right) =\left( p+1\right) \left( q+1\right)$$

Wegen $de\equiv 1\, \mod \char93 \tilde{E}_{0,b}\left( \mathbb{Z}_{n}\right)$ erhalten wir

$$d\cdot \left( c_{1},c_{2}\right) =de\cdot \left( x,y\right) \equiv \left( x,y\right) \, \mod \char93 \tilde{E}_{0,b}\left( \mathbb{Z}_{n}\right) .$$

Dieses Verfahren hat die Eigenschaft, daß die Kurve, mit der wir rechnen, von der zu verschlüsselnden Nachricht abhängt. Dieses Kryptosystem ist allerdings nicht so effizient wie das RSA-Verfahren, dafür soll es resistenter gegen bestimmte bekannte RSA-Attacken sein.

Es sind aber auch folgende Attacke bekannt:

Theorem 6.3 (Angriff bei teilweise bekanntem Klartext)  

Sei $\left( n,e\right)$ ein öffentlicher Schlüssel für KMOV und $C=\left( c_{1},c_{2}\right)$ die verschlüsselte Nachricht $M=\left( x,y\right)$. Ist nun $n,e,C$ und $x$ oder $y$ gegeben, so kann der Klartext $M$ effizient berechnet werden.

Der Beweis dieses Satzes benutzt die Redundanz, die durch $b\equiv c_{2}^{2}-c_{1}^{3}\, \mod n$ gegeben ist.

Wenn dieselbe Nachricht mehrmals mit verschiedenen Public-Keys verschlüsselt wird, ist folgender Satz anwendbar:

Theorem 6.4   Sei $t\geq 1$ und seien $\left( e_{1},n_{1}\right) ,\, \left( e_{2},n_{2}\right) ,\, \left( e_{3},n_{3}\right)$ verschiedene öffentliche Schlüssel. Sei $M=\left( x,y\right) \in \left\{ 0,\min _{i}\left\{ n_{i}\right\} -1\right\} ^{2}$ eine unbekannte Nachricht. Wenn 3 Cryptotexte existieren, die mit den 3 Schlüsseln verschlüsselt wurden, dann kann $M$ in Zeit $O\left( t^{2}\log \left( n\right) ^{3}\right)$ mit Wahrscheinlichkeit $1-\frac{1}{t}$ gefunden werden, wobei $n=\max _{i}\left\{ n_{i}\right\}$.