MOV

Menez und Vanstone schlugen ein auf ElGamal basierendes Kryptosystem für Nachrichten $M=\left( x,y\right) \in \mathbb{F}_{q}\times \mathbb{F}_{q}$ vor, bei dem auch das Problem der Kodierung einer Nachricht als Element von $E\left( \mathbb{F}_{q}\right) \protect$ nicht auftritt.

Algorithmus 6.7 (MOV - Menezes, Okamoto, Vanstone)  

1. Schlüsselpaar-Erzeugung

   A führt die folgenden Schritte durch:

   • wähle eine elliptische Kurve $E$ über $\mathbb{F}_{q}$ der Ordnung $n$ und ein Element $h\in E\left( \mathbb{F}_{q}\right)$ mit Primordnung $r$;
   • wähle eine Zufallszahl $a$ mit $1<a<r$;
   • berechne $\alpha \leftarrow a\cdot h$
   As öffentlicher Schlüssel ist $\left( E\left( \mathbb{F}_{q}\right) ,h,\alpha \right)$, As geheimer Schlüssel ist $a$.

2. Verschlüsselung

   B führt die folgenden Schritte durch:

   • besorge As authentischen öffentlichen Schlüssel;
   • wähle eine Zufallszahl $k$ mit $1<k<r$;
   • berechne $\rho \leftarrow k\cdot h$;
   • berechne $c_{1}\leftarrow x\left( k\cdot \alpha \right) _{1}$ und $c_{2}\leftarrow y\left( k\cdot \alpha \right) _{2}$, wobei $\gamma _{i}$ die $i$-te Koordinate von $\gamma \in E\left( \mathbb{F}_{q}\right)$ sein soll $\left( i=1,2\right)$;
   $C=\left( \rho ,c_{1},c_{2}\right)$ ist die Verschlüsselung von $M$.

3. Entschlüsselung

   A führt die folgenden Schritte durch:

   • berechne $\beta \leftarrow a\cdot \rho$
   • berechne $x\leftarrow c_{1}\frac{1}{\beta _{1}}=x\left( k\cdot \alpha \right) _{1}\frac{... ...a\cdot h\right) _{1}\frac{1}{\left( ka\cdot h\right) _{1}}=x\in \mathbb{F}_{q}$
   • berechne $y\leftarrow c_{2}\frac{1}{\beta _{2}}=y\left( k\cdot \alpha \right) _{2}\frac{... ...a\cdot h\right) _{2}\frac{1}{\left( ka\cdot h\right) _{2}}=y\in \mathbb{F}_{q}$

Wenn ein Angreifer $x$ (oder $y$) kennt, ist es ihm einfach möglich, $y$ (oder $x$) zu berechnen. Um die Sicherheit zu erhöhen, kann man auch nur $\left( \rho ,c_{1}\right) \in E\left( \mathbb{F}_{q}\right) \times \mathbb{F}_{q}\subseteq \mathbb{F}_{q}^{3}$ als eine Verschlüsselung von $x$ senden. Damit wäre der Kryptotext dann aber dreimal so lang wie der Klartext.

Wir können die ,,Cyphertext-Expansion'' verringern, indem wir die $y$-Koordinate von $\rho \in E\left( \mathbb{F}_{q}\right)$ mit nur einem Bit kodieren, da es zu einer festen $x$-Koordinate von $\rho$ ja nur maximal zwei $y$-Koordinaten geben kann, für die $\rho \in E\left( \mathbb{F}_{q}\right)$ gilt.

Damit vergrößern sich die Nachrichten nur noch um den Faktor $\approx \frac{3}{2}$.

Angenommen, das DLP ist für $q\sim 2^{160}$ nicht mehr effizient lösbar, dann erhalten wir bei gleicher ,,Sicherheit'' von RSA, ElGamal über $\mathbb{F}_{q}^{*}$ und MOV durch Komprimierung der $y$-Koordinate von $\rho$ und durch Senden von nur $\left( \rho ,c_{1}\right)$:

System	Kryptotextgröße in Bits
RSA	1024
ElGamal	2048
MOV	321

Vergleich der Kryptotextgrößen einer 100 Bit großen Nachricht