RSA Verschlüsselung

1. Grundlagen

Der Modulo Operator Übung1    Übung2

Zum Grundverständnis

Übersicht RSA Verschlüsselung

Vervollständige durch Recherche den Lückentext!

2. Privater Schlüssel (n,d)

a) Modulares Inverses d zu e

Methode Tabellenkalkulation >>

b) Modulares Inverses d zu e

Methode : Euklidischen Algorithmus

Beispiel 1: >>      Beispiel 2: >>     Beispiel 3:  >>     Beispiel 4:  >>

c) Vollziehe das folgende Beispiel zum Verschlüsseln und Entschlüsseln einer Geheimnachricht nach und löse die Aufgaben schriftlich im Heft!

d) Verwende für das Beispiel andere Primzahlen und eine andere gewählte Zahl e!

3. Textnachrichten übermitteln

Bob möchte an Alice eine Nachricht schicken. Hier nur der Buchstabe A.


a) Vollziehe das Beispiel schriftlich im Heft nach:
(Hinweis: Die Zahl e entspricht hier dem Buchstabe a, die Zahl d entspricht b.)

• privater Schlüssel, modulares Inverses b=173 (Ergibt sich aus dem Euklidischen Algorithmus)
  Wer sie immer noch braucht, hier die Lösung. Die Zahl darf nicht negativ sein. Finde heraus, wie das Problem gelöst wird!
  

b) Was ändert sich, wenn Bob den Buchstaben B schicken möchte? Notiere den Ablauf!

c) Alice wählt die Primzahlen 11 und 13.
    Für die Bildung des öffentlichen Schlüssels wählt sie a=23.
    Bob wird diesmal wieder den Buchstaben B (ASCII 66) übermitteln.
    Führe eine analoge Rechnung durch! Weise nach, dass das modulare Inverse a^(-1) mod m = 47 ist!

d) Alice wählt nun a=7 für den öffentlichen Schlüssel unter Beibehaltung der beiden Primzahlen 11 und 13.
    Verschlüssele und Entschlüssele nun wieder den Buchstaben B!
    (Hinweis: Bei längeren Texten wird der Text in Blöcke aufgezeilt und die Blöcke werden dann einzeln übermittelt.)

4. Weitere Übungen zum Verschlüsseln und Entschlüsseln

Gegeben sind die beiden Primzahlen p=997 und q=991
a) Weise nach, dass mit einem gewählten a=997 das modulare Inverse von a gleich 704173 ist!      Lösung: >>   

b) Verschlüssele und entschlüssele die Botschaft ABC (Ascii 656667)!

c) Bei welcher Länge stösst der Rechner an seine Grenzen?

d) Übung erweiterter Euklidischer Algorithmus  Übung1    Übung2

5. Realisierung der RSA-Verschlüsselung mit Python

    Für die RSA Verschlüsselung sind mathematische Grundlagen Voraussetzung.
    Beispiele:
a) Primzahlen bis zu einer Grenze (z.B. 100) in einer Liste ausgeben

b) Untersuchung, ob eine eingegebenen Zahl p eine Primzahl ist (bis zur Wurzel(p) Teilbarkeit überprüfen)

c) Bestimmung des größten gemeinsamen Teilers (ggT) mit dem Euklidischen Algorithmus

d) Überprüfung, ob eine Zahl e teilerfremd zu einer anderen Zahl a ist (ggT(a,e)=1)

e) Unterteilung eines längeren Textes in Blöcke   (z.B. 4-er Blöcke)

Zu den Aufgaben

6. Euklidischer Algorithmus mit einer Tabellenkalkulation

Bestimme das modulare Inverse (Verwendung von TK Lernsax, Excel oder dem kostenlosen LibreOffice) >>

Abschließende Kontrolle