Kryptographie - Algebraischer Hintergrund

Prof . Dr. F.-O. Schreyer

Übungsblatt 5: Endliche Körper und Quadratische Reziprozität

Abgabetermin 18.6.2002

Voraussetzungen: Vorlesungskapitel Endliche Körper, Quadratische Reziprodizität.

1. Schreiben Sie ein Maple-Skript, das die Anzahl der irreduziblen Polynome vom Grad r in $\mathbb {F}$_p$\left[\vphantom{ x}\right.$x$\left.\vphantom{ x}\right]$ bestimmt.

2. Schreiben Sie ein Maple-Skript, das für q = p^r den Körper $\mathbb {F}$_q $\simeq$ $\mathbb {F}$_p$\left[\vphantom{ x}\right.$x$\left.\vphantom{ x}\right]$/$\left(\vphantom{ f}\right.$f$\left.\vphantom{ f}\right)$ mit einem irreduziblen Polynom f $\in$ $\mathbb {F}$_p$\left[\vphantom{ x}\right.$x$\left.\vphantom{ x}\right]$ vom Grad r konstruiert, d.h. Multiplikation, Addition und Bildung des Inversen realisiert auf Repräsentanten vom Grad < r der Elemente von $\mathbb {F}$_q.

3. Wir ersetzen im RSA-Kryptosystem $\mathbb {Z}$ durch $\mathbb {F}$_p$\left[\vphantom{ x}\right.$x$\left.\vphantom{ x}\right]$, d.h. statt n = p ^. q das Produkt zweier Primzahlen, schreiben wir f = g ^. h das Produkt zweier irreduzibler Polynome aus $\mathbb {F}$_p$\left[\vphantom{ x}\right.$x$\left.\vphantom{ x}\right]$.

   Bob wählt also 2 irreduzible Polynome g und h aus $\mathbb {F}$_p$\left[\vphantom{ x}\right.$x$\left.\vphantom{ x}\right]$, berechnet f = g ^. h und

   $$\varphi \left(\vphantom{ f}\right. \left.\vphantom{ f}\right) \left(\vphantom{ \left( \mathbb{F}_{p}\left[ x\right] /\left( g\right) \right) ^{\ast}}\right. \left(\vphantom{ \mathbb{F}_{p}\left[ x\right] /\left( g\right) }\right. \mathbb {F} \left[\vphantom{ x}\right. \left.\vphantom{ x}\right] \left(\vphantom{ g}\right. \left.\vphantom{ g}\right) \left.\vphantom{ \mathbb{F}_{p}\left[ x\right] /\left( g\right) }\right)^{{\ast}}_{} \left.\vphantom{ \left( \mathbb{F}_{p}\left[ x\right] /\left( g\right) \right) ^{\ast}}\right) \left(\vphantom{ \left( \mathbb{F}_{p}\left[ x\right] /\left( h\right) \right) ^{\ast}}\right. \left(\vphantom{ \mathbb{F}_{p}\left[ x\right] /\left( h\right) }\right. \mathbb {F} \left[\vphantom{ x}\right. \left.\vphantom{ x}\right] \left(\vphantom{ h}\right. \left.\vphantom{ h}\right) \left.\vphantom{ \mathbb{F}_{p}\left[ x\right] /\left( h\right) }\right)^{{\ast}}_{} \left.\vphantom{ \left( \mathbb{F}_{p}\left[ x\right] /\left( h\right) \right) ^{\ast}}\right)$$

   $$\left(\vphantom{ p^{\deg g}-1}\right. \left.\vphantom{ p^{\deg g}-1}\right) \left(\vphantom{ p^{\deg h}-1}\right. \left.\vphantom{ p^{\deg h}-1}\right)$$

   
   

   Dann wählt Bob ein zufälliges e mit ggT$\left(\vphantom{ e,\varphi\left( f\right) }\right.$e,$\varphi$$\left(\vphantom{ f}\right.$f$\left.\vphantom{ f}\right)$$\left.\vphantom{ e,\varphi\left( f\right) }\right)$ = 1 und bestimmt d mit

   e ^. d $$\equiv$$ 1mod$$\varphi$$$$\left(\vphantom{ f}\right.$$f$$\left.\vphantom{ f}\right)$$
   Bobs öffentlicher Schlüssel ist dann $\left(\vphantom{ f,e}\right.$f, e$\left.\vphantom{ f,e}\right)$, sein geheimer Schlüssel ist d.

   Alice kann nun eine für Bob bestimmte Nachricht m $\in$ $\mathbb {F}$_p$\left[\vphantom{ x}\right.$x$\left.\vphantom{ x}\right]$/$\left(\vphantom{ f}\right.$f$\left.\vphantom{ f}\right)$ verschlüsseln (wobei m teilerfremd mit f sei) mittels

   c : = m^emodf
   Bob bekommt wieder den Klartext durch:
   c^d = m^{d . e} = m^{$^{{%% \begin{array}[c]{c}%% {\tiny 1+k\cdot\varphi}\left( f\right) \end{array}}}$} = mmodf
   1. Warum kann man dieses Kryptosystem leicht knacken ?

   2. Überprüfen Sie, daß dieses Kryptosystem auch deshalb zu schwach ist, weil sich z.B. Polynome vom Grad $\approx$ 300 über $\mathbb {F}$₁₁ faktorisieren lassen.

4. 1. Berechnen Sie per Hand:
      $$\left(\vphantom{ \frac{3}{97}}\right.$$$${\frac{{3}}{{97}}}$$$$\left.\vphantom{ \frac{3}{97}}\right)$$, $$\left(\vphantom{ \frac{5}{389}}\right.$$$${\frac{{5}}{{389}}}$$$$\left.\vphantom{ \frac{5}{389}}\right)$$, $$\left(\vphantom{ \frac{2003}{11}}\right.$$$${\frac{{2003}}{{11}}}$$$$\left.\vphantom{ \frac{2003}{11}}\right)$$, $$\left(\vphantom{ \frac{5!}{7}}\right.$$$${\frac{{5!}}{{7}}}$$$$\left.\vphantom{ \frac{5!}{7}}\right)$$

   2. Zeigen Sie
      $$\left(\vphantom{ \frac{3}{p}}\right.$$$${\frac{{3}}{{p}}}$$$$\left.\vphantom{ \frac{3}{p}}\right)$$ = $$\left\{\vphantom{ \begin{array}[c]{ll}%% 1 & \text{falls }p\equiv... ...2\text{ und}\\ -1 & \text{falls }p\equiv5,7\text{ mod }12 \end{array}}\right.$$$$\begin{array}[c]{ll}%% 1 & \text{falls }p\equiv1,11\text{ mod }12\text{ und}\\ -1 & \text{falls }p\equiv5,7\text{ mod }12 \end{array}$$$$\left.\vphantom{ \begin{array}[c]{ll}%% 1 & \text{falls }p\equiv1... ...\text{ und}\\ -1 & \text{falls }p\equiv5,7\text{ mod }12 \end{array}}\right\}$$

   3. Zeigen Sie direkt, daß
      $$\left(\vphantom{ \frac{-3}{p}}\right.$$$${\frac{{-3}}{{p}}}$$$$\left.\vphantom{ \frac{-3}{p}}\right)$$ = 1 falls    p $$\equiv$$ 1mod3
      (Tip: Sei g eine primitive Wurzel von $\left(\vphantom{ \mathbb{Z}/p\mathbb{Z}%% }\right.$$\mathbb {Z}$/p$\mathbb {Z}$$\left.\vphantom{ \mathbb{Z}/p\mathbb{Z}%% }\right)^{{\ast}}_{}$. Konstruieren Sie aus g ein Element h der Ordnung 3 und zeigen Sie, daß $\left(\vphantom{ 2\cdot h+1}\right.$2 ^. h + 1$\left.\vphantom{ 2\cdot h+1}\right)^{{2}}_{}$ $\equiv$ -3modp).

5. Schreiben Sie ein Maple-Skript, das mit dem Legendresymbol die Anzahl der Punkte einer elliptischen Kurve über $\mathbb {F}$_p bestimmt.

Abgabe der Aufgaben bitte als email an

$$\begin{array}[c]{c}%% \text{boehm@btm8x5.mat.uni-bayreuth.de}\\ ... ...{\text{oder}}\\ \multicolumn{1}{l}{\text{boehm@math.uni-sb.de}}%% \end{array}$$