Kryptographie - Algebraischer Hintergrund

Prof . Dr. F.-O. Schreyer

Übungsblatt 4: Elliptische Kurven Kryptogrphie

Abgabetermin 28.5.2002

Voraussetzungen: Vorlesungskapitel Public-Key-Kryptographie, Elliptische Kurven.

1. Das ElGamal-Kryptosystem funktioniert wie folgt:

   Bob wählt eine Primzahl p und ein g $\in$ $\mathbb {F}$_p ^* mit $\mathbb {F}$_p ^* = $\left\langle\vphantom{ g}\right.$g$\left.\vphantom{ g}\right\rangle$ : = $\left\{\vphantom{ g^{k}\mid k=0,...,p-1}\right.$g^k | k = 0,..., p - 1$\left.\vphantom{ g^{k}\mid k=0,...,p-1}\right\}$.

   Dann wählt er ein zufälliges d $\in$ $\left\{\vphantom{ 1,...p-2}\right.$1,...p - 2$\left.\vphantom{ 1,...p-2}\right\}$, welches er geheim hält.

   Der öffentliche Schlüssel ist g^d $\in$ $\mathbb {F}$_p ^* zusammen mit g und p.

   Alice kann nun eine für Bob bestimmte Nachricht T $\in$ $\mathbb {F}$_p ^* wie folgt verschlüsseln:

   Alice wählt ein zufälliges k $\in$ $\left\{\vphantom{ 1,...p-2}\right.$1,...p - 2$\left.\vphantom{ 1,...p-2}\right\}$ und berechnet

   $$\left(\vphantom{ g^{k},T\cdot\left( g^{d}\right) ^{k}}\right.$$g^k, T ^. $$\left(\vphantom{ g^{d}}\right.$$g^d$$\left.\vphantom{ g^{d}}\right)^{{k}}_{}$$$$\left.\vphantom{ g^{k},T\cdot\left( g^{d}\right) ^{k}}\right)$$
   Alice schickt dies an Bob und dieser berechnet
   $$\left(\vphantom{ g^{k}}\right.$$g^k$$\left.\vphantom{ g^{k}}\right)^{{d}}_{}$$ = $$\left(\vphantom{ g^{d}}\right.$$g^d$$\left.\vphantom{ g^{d}}\right)^{{k}%% }_{}$$
   und bekommt damit wieder den Klartext
   T = $$\left(\vphantom{ T\cdot\left( g^{d}\right) ^{k}}\right.$$T ^. $$\left(\vphantom{ g^{d}}\right.$$g^d$$\left.\vphantom{ g^{d}}\right)^{{k}}_{}$$$$\left.\vphantom{ T\cdot\left( g^{d}\right) ^{k}}\right)$$ ^. $$\left(\vphantom{ \left( g^{d}\right) ^{k}}\right.$$$$\left(\vphantom{ g^{d}}\right.$$g^d$$\left.\vphantom{ g^{d}}\right)^{{k}}_{}$$$$\left.\vphantom{ \left( g^{d}\right) ^{k}}\right)^{{-1}%% }_{}$$

   Kann man d = log_g$\left(\vphantom{ g^{d}}\right.$g^d$\left.\vphantom{ g^{d}}\right)$ berechnen, dann hat man das System geknackt.

   1. Schreiben Sie eine Maple-Prozedur mit dem Alice eine Nachricht für Bob mit dem ElGamal-Kryptosystem verschlüsseln kann.

   2. Schreiben Sie eine Maple-Prozedur mit der Bob diese Nachricht wieder entschlüsseln kann.

   3. Schreiben Sie eine Maple-Prozedur, die das ElGamal-Kryptosystem knackt, indem sie aus dem öffentlichen Schlüssel den geheimen Schlüssel berechnet.

   4. Probieren Sie Ihre Skripte mit einem frei gewählten Beispiel aus.

   Bem: Das Kodieren und Dekodieren der Nachricht als Zahl soll wie im RSA Skript durchgeführt werden.

2. Im ElGamal-Kryptosystem kann man $\mathbb {F}$_p ^* auch durch eine elliptische Kurve über einem endlichen Körper ersetzen:

   Bob wählt eine Primzahl p und eine elliptische Kurve E$\left(\vphantom{ \mathbb{F}_{p}}\right.$$\mathbb {F}$_p$\left.\vphantom{ \mathbb{F}_{p}}\right)$ über $\mathbb {F}$_p und einen Punkt g $\in$ E$\left(\vphantom{ \mathbb{F}_{p}}\right.$$\mathbb {F}$_p$\left.\vphantom{ \mathbb{F}_{p}}\right)$.

   Sei H : = $\left\langle\vphantom{ g}\right.$g$\left.\vphantom{ g}\right\rangle$ die von g erzeugte zyklische Untergruppe von E$\left(\vphantom{ \mathbb{F}_{p}}\right.$$\mathbb {F}$_p$\left.\vphantom{ \mathbb{F}_{p}}\right)$.

   Dann wählt er ein zufälliges d $\in$ $\left\{\vphantom{ 1,...\left\vert H\right\vert -1}\right.$1,...$\left\vert\vphantom{ H}\right.$H$\left.\vphantom{ H}\right\vert$ - 1$\left.\vphantom{ 1,...\left\vert H\right\vert -1}\right\}$, welches er geheim hält.

   Der öffentliche Schlüssel ist d ^. g zusammen mit g und E$\left(\vphantom{ \mathbb{F}_{p}}\right.$$\mathbb {F}$_p$\left.\vphantom{ \mathbb{F}_{p}}\right)$.

   Alice kann nun eine für Bob bestimmte Nachricht T $\in$ E$\left(\vphantom{ \mathbb{F}_{p}}\right.$$\mathbb {F}$_p$\left.\vphantom{ \mathbb{F}_{p}}\right)$ wie folgt verschlüsseln:

   Alice wählt ein zufälliges k $\in$ $\left\{\vphantom{ 1,...\left\vert H\right\vert -1}\right.$1,...$\left\vert\vphantom{ H}\right.$H$\left.\vphantom{ H}\right\vert$ - 1$\left.\vphantom{ 1,...\left\vert H\right\vert -1}\right\}$ und berechnet

   $$\left(\vphantom{ k\cdot g,T+k\cdot\left( d\cdot g\right) }\right.$$k ^. g, T + k ^. $$\left(\vphantom{ d\cdot g}\right.$$d ^. g$$\left.\vphantom{ d\cdot g}\right)$$$$\left.\vphantom{ k\cdot g,T+k\cdot\left( d\cdot g\right) }\right)$$
   Alice schickt dies an Bob und dieser berechnet
   d ^. $$\left(\vphantom{ k\cdot g}\right.$$k ^. g$$\left.\vphantom{ k\cdot g}\right)$$ = k ^. $$\left(\vphantom{ d\cdot g}\right.$$d ^. g$$\left.\vphantom{ d\cdot g}\right)$$
   und bekommt damit wieder den Klartext
   T = $$\left(\vphantom{ T+k\cdot\left( d\cdot g\right) }\right.$$T + k ^. $$\left(\vphantom{ d\cdot g}\right.$$d ^. g$$\left.\vphantom{ d\cdot g}\right)$$$$\left.\vphantom{ T+k\cdot\left( d\cdot g\right) }\right)$$ - k ^. $$\left(\vphantom{ d\cdot g}\right.$$d ^. g$$\left.\vphantom{ d\cdot g}\right)$$
   1. Schreiben Sie eine Maple-Prozedur, mit der Alice eine Nachricht für Bob mit dem elliptischen Kurven ElGamal Kryptosystem verschlüsseln kann.

   2. Schreiben Sie eine Maple-Prozedur, mit der Bob diese Nachricht wieder entschlüsseln kann.

   3. Probieren Sie Ihr Skript mit der elliptischen Kurve E : y² = x³ + x + 1 über $\mathbb {Z}$/5$\mathbb {Z}$ mit einem beliebigen Punkt g und einem Punkt der Kurve als Nachricht aus.

   4. Haben Sie eine Idee, wie man auf elliptischen Kurven den log berechnen und damit ElGamal knacken kann.

Abgabe der Aufgaben bitte als email an

boehm@btm8x5.mat.uni-bayreuth.de oder boehm@math.uni-sb.de