Einbettung von Text

Bei Verschlüsselungen und auch bei Signaturen mit Message-Recovery müssem wir den Text $M$ bei den bisher gezeigten Verfahren als Gruppenelement $\mu \in G$ darstellen; dies wird als Einbettung von $M$ in $G$ bezeichnet. Die Einbettung soll effizient sein, und außerdem wollen wir $M$ aus $\mu$ eindeutig (und ebenfalls effizient) wiederherstellen können. Um $M$ in $G$ einbetten zu können, muß $M$ i.a. zunächst in Blöcke ,,passender'' Größe unterteilt werden, denn bei festem $G$ können höchstens $\left\vert G\right\vert$ unterschiedliche Texte $M$ eingebettet werden. Wir gehen im weiteren davon aus, daß $M$ binärcodiert auf offensichtliche Weise als natürliche Zahl interpretiert werden kann, und daß $M$ bereits eine ,,passende'' Größe hat. Wenn z.B. $G=\mathbb{Z}_{p}^{*}$ ist, dann ergibt sich eine natürliche Möglichkeit, $M$ auf $\mu$ abzubilden, denn hier ist $\mu$ identisch mit $M$ aufgefaßt als positive ganze Zahl.

Bei anderen Gruppen kann die Einbettung komplizierter werden. Wenn wir einen Text als Punkt einer elliptischen Kurve $E$ über $\mathbb{F}_{q}$ kodieren wollen, dann müssen wir eine Repräsentation von $M$ als Paar $\left( x,y\right)$ finden. Auf den ersten Blick hat man keine andere Wahl, als $M$ z.B. auf die $x$-Koordinate eines Punktes abzubilden, weil die $x$- und die $y$-Koordinaten eines Punktes nicht unabhängig voneinander sind. Gibt man nämlich die $x$-Koordinate vor, so kann man maximal nur noch das Vorzeichen der $y$-Koordinate auswählen.

An dieser Stelle wird aber noch eine ganz andere Schwierigkeit offenkundig, denn nicht zu jeder $x$-Koordinate existiert ein Punkt auf der Kurve. In diesem Fall müßten wir die Möglichkeit haben, $M$ ersatzweise auf eine andere $x$-Koordinate abzubilden, und zwar so, daß $M$ aus $x$ eindeutig rekonstruiert werden kann. Wenn $M$ als Element von $\mathbb{F}_{q}$ interpretiert wird, z.B. durch $M=\sum _{i=0}^{m-1}a_{i}p^{i}$ mit $a_{i}\in \mathbb{F}_{p}$ und $q=p^{m}$, dann kann für die Einbettung das folgende Schema angewendet werden:

$$M\mapsto mk+i$$

für das kleinste $i,0\leq i\leq k$, so daß $mk+i$ die $x$-Koordinate eines Punktes aus $E\left( \mathbb{F}_{q}\right) \setminus \left\{ \O\right\}$ ist. Da $x\in \mathbb{F}_{q}$ ist und die Abbildung in gewisser Weise eindeutig sein soll, muß $M<\frac{q}{k}$ sein, und daher können höchstens etwas $\log _{2}\left( \frac{q}{k}\right) =\log _{2}q-\log _{2}k$ Bits auf diese Weise eingebettet werden. Mit anderen Worten, es müssen für jede Einbettung $\log k$ Bits aufgewendet werden, um die Wahrscheinlichkeit eines Fehlschlags entsprechend zu verkleinern, d.h. mit dieser Methode kann immer noch nicht garantiert werden, daß es für $M$ eine Darstellung als Punkt der Kurve gibt.

In Abschnitt 2.2 hatten wir dazu bereits festgestellt, daß man bei zufälliger Wahl einer $x$-Koordinate mit einer Wahrscheinlichkeit von etwa $\frac{1}{2}$ einen Punkt auf der Kurve erhält, d.h. man erhält mit einer Wahrscheinlichkeit von etwas $\frac{1}{2}$ keinen Punkt. Wenn wir für ein $M$ also $k$ Versuche für die Einbettung haben, dann kann $M$ mit einer Wahrscheinlichkeit von $2^{-k}$ nicht auf die $x$-Koordinate eines Punktes aus $E\left( \mathbb{F}_{q}\right) \setminus \left\{ \O\right\}$ abgebildet werden. Dies geht natürlich mit einem Verlust einher, denn je größer $K$ ist, desto weniger Bits können für $M$ selber verwendet werden, d.h. die Einbettung wird ineffizienter. Wenn wir z.B. $k=256$ wählen, dann müssen wir dafür 8 Bits (für jedes $M$) aufwenden, allerdings ist die Wahrscheinlichkeit eines Fehlschlages mit $2^{-256}$ verschwindend gering.

Bei anderen Gruppen kann das Einbettungs-Problem weitaus komplizierter sein. Um dieses Problem bei der Verschlüsselung zu vermeiden, kann man die folgende Variante der ElGamal-Verschlüsselung anwenden:

Algorithmus 6.6    

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 $\beta \leftarrow k\cdot \alpha$;
   • für eine Hash-Funktion $i:E\left( \mathbb{F}_{q}\right) \rightarrow \mathbb{F}_{q}$ berechne $c\leftarrow i\left( \beta \right) \oplus M$
   $C=\left( \rho ,c\right)$ ist die Verschlüsselung von $M$.

3. Entschlüsselung

   A führt die folgenden Schritte durch:

   • berechne $\beta \leftarrow a\cdot \rho$
   • berechne $M\leftarrow i\left( \beta \right) \oplus c$

Der Trick ist, daß die Multiplikation von $\beta$ mit einer Einbettung von $M$ in $E\left( \mathbb{F}_{q}\right) \protect$ durch ein simples bitweises XOR von $i\left( \beta \right)$ und $M$ ersetzt wird.

Die Vorteile liegen auf der Hand: $M$ wird direkt und deterministisch in die Verschlüsselung eingebracht, ohne die u. U. probabilistische, mühselige Suche nach einem Gruppenelement, in welches $M$ ansonsten eingebettet werden muß.