Kryptographie - Algebraischer Hintergrund

Prof . Dr. F.-O. Schreyer

Übungsblatt 2: Faktorisierung und RSA

Abgabetermin 14.5.2002

Voraussetzungen: Vorlesungskapitel RSA und Wiederholung, Faktorisierung.

1. Zeichnen Sie folgende Funktionen:
   1. g₁ : $\left[\vphantom{ 1,11}\right.$1, 11$\left.\vphantom{ 1,11}\right]$ $\rightarrow$ $\mathbb {R}$

      g₁$\left(\vphantom{ k}\right.$k$\left.\vphantom{ k}\right)$ = L_2^k$\left[\vphantom{ \frac{1}{2},1}\right.$${\frac{{1}}{{2}}}$, 1$\left.\vphantom{ \frac{1}{2},1}\right]$

   2. g₂ : $\left[\vphantom{ 1,11}\right.$1, 11$\left.\vphantom{ 1,11}\right]$ $\rightarrow$ $\mathbb {R}$

      g₂$\left(\vphantom{ k}\right.$k$\left.\vphantom{ k}\right)$ = L_2^k$\left[\vphantom{ 0,4}\right.$0, 4$\left.\vphantom{ 0,4}\right]$

   3. g₃ : $\left[\vphantom{ 1,11}\right.$1, 11$\left.\vphantom{ 1,11}\right]$ $\rightarrow$ $\mathbb {R}$

      g₃$\left(\vphantom{ k}\right.$k$\left.\vphantom{ k}\right)$ = L_2^k$\left[\vphantom{ 1,\frac{1}{2}}\right.$1,${\frac{{1}}{{2}}}$$\left.\vphantom{ 1,\frac{1}{2}}\right]$

2. Faktorisieren Sie die Zahlen
   1. 510511

   2. 5302555407858282827768779093

   3. 713623837172067545560252416065537

   4. 42144985531257745681402189153111135

   5. 12098743833798169067520000007523445343024140716896711111

   6. 64898518442585961302416669382254503060920596574980..
      ..25293841379902123372605065112731390344140051162106..
      ..64274752968417922051839654930184534182840779371249..
      ..77201178904854777462019451974017116414724852487815..
      ..1680000000000000001

   7. 2468001160766705452066353134549702698515108744549..

      ..4665685615343871770215418328461561352271369287472..

      ..2894942800453480535296312038337227963302750841644..

      ..8080849156722646366456990845503383352913528008289..

      ..3217698465676926977153625636105890357806909711920..

      ..3632383280760251916550382742710343646274895445668..

      ..7336461016448159044677999713509355259225543554112..

      ..189128101829876543546780098765000111111111200611

   mit Probedivision, Pollards $\left(\vphantom{ p-1}\right.$p - 1$\left.\vphantom{ p-1}\right)$-Methode und mit dem Quadratischen Sieb (soweit jeweils anwendbar).

3. Entschlüsseln Sie die mit RSA verschlüsselte Nachricht:

   28940876200588807614880444715257804099176669707381..

   ..18342040725536981792071169315573271203611095429446..

   ..91101712755066527975565713841027366846493109170684

   Der öffentliche Schlüssel ist:

   n =3345252661316380710817006205344075166515200000000100..

           0000000000000000000000000000000000000000000000893182..

           4605714736497881406568268680694595584000000267

   e =65537

   Die Nachricht wurde im Alphabet $\left\{\vphantom{ A..Z}\right.$A..Z$\left.\vphantom{ A..Z}\right\}$ $\simeq$ $\mathbb {Z}$/26 kodiert durch

   $$\mapsto$$ A

   $$\mapsto$$ B

   $$\vdots$$

   $$\mapsto$$ Y

   $$\mapsto$$ Z

   
   
   und die dann erhaltene Zahl mit RSA verschlüsselt.

Die zu faktorisierenden Zahlen, die RSA-Nachricht und der öffentliche Schlüssel können separat als Textdatei heruntergeladen werden von

www.math.uni-sb.de/~ag-schreyer/krypto/blatt2.txt