Theoretischer Hintergrund
Inhalt:
Primzahlen
Der RSA-Algorithmus basiert auf der Schwierigkeit, eine große Zahl in ihre Primfaktoren zu zerlegen. Bob überlegt - Primfaktoren / Primzahlen - das hat er doch schon gehört. Aber dann kommen im doch Zweifel, ob seine Kenntnisse auch reichen?
Aufgaben:
Erarbeite Dir mit Hilfe des Theorieteils zu Primzahlen die folgenden Aufgabenstellungen.
- Dokumentiere die Antworten auf die drei folgenden Fragestellungen:
- Gibt es unendlich viele Primzahlen?
- Wieviele von 100 Zahlen sind durchschnittlich Primzahlen bei Zahlen im Bereich von 1 Million?
- Gibt es eine "Erzeugungsformel" für Primzahlen?
- Dokumentiere die Antworten auf die drei folgenden Fragestellungen:
Optional: Übprüfe mit Hilfe des Siebes von Eratosthenes, ob es sich bei 373 um eine Primzahl handelt.
Optional: Wie lautet die 42te Mersennesche Primzahl? Informiere Dich über den geschichtlichen Hintergrund dieser besonderen Zahlen.
Optional: Erkläre mit Hilfe einer Präsentation die Bedeutung von Primzahltests. Wo liegen die Stärken des Miller-Rabin-Tests gegenüber dem Fermat-Test? Welche Zahlen erfüllen manche dieser Tests, sind aber trotzdem keine Primzahlen?
- Überprüfe mit Hilfe der DERIVE-Funktionen zu Primzahlen, ob
- 1105 eine Primzahl ist!
- Bestimme die nächsthöhere Primzahl.
- die Mersennesche Zahl m = 2^17-1 eine Primzahl ist!
- Bestimme die nächstgelegene Primzahl kleiner als m.
- Überprüfe mit Hilfe der DERIVE-Funktionen zu Primzahlen, ob
Optional: Was besagt, der Satz von Wilson? Arbeite die angegebene Übung dazu durch.
Rechnen mit Restklassen
Der zweite Begriff, der in den Unterlagen immer wieder auftaucht, ist jener der Modulo-Rechnung / Rechnung mit Restklassen.
Aufgaben:
Optional: Arbeite den Theorieteil zur Restklassenrechnung durch und dokumentiere die wichtigsten Inhalte und alle Übungen.
- Löse mit Hilfe des Square-and-Multiply-Algorithmus (die Anleitung dazu findest Du im Theorieteil zu modularem Potenzieren) die folgenden Beispiele:
- 54^16 mod 55 =
- 2^269 mod 19 =
- 3^333 mod 15 =
- Löse mit Hilfe des Square-and-Multiply-Algorithmus (die Anleitung dazu findest Du im Theorieteil zu modularem Potenzieren) die folgenden Beispiele:
Satz von Euler-Fermat
Die Grundlage für den von den Kryptologen Rabin, Shamir und Adelman gefundenen Algorithmus (nach ihren Anfangsbuchstaben RSA genannt) ist der Satz von Euler-Fermat. Verwende für die Erarbeitung dieses Themas den Theorieteil zum Satz von Euler.
Aufgaben:
- Wodurch unterscheiden sich der kleine Satz von Fermat und der Satz von Euler?
- überprüfe und dokumentiere den Satz von Euler mit Hilfe der beiden Primfaktoren n = 5 und m = 7.
Zeige, dass φ(n.m) = (n-1)(m-1) und für zwei Werte (a = 3 und a = 11), dassa(n-1)(m-1) mod n.m = 1
Erweiterter euklidischer Algorithmus
Für die Berechnung des privaten Schlüssels (private Key) bei der asymmetrischen Verschlüsselung nach dem RSA-Verfahren benötigt man die sogenannte modulare Inverse. Die Berechnung derselben kann mit Hilfe des erweiterten euklidischen Algorithmus durchgeführt werden (die einfache Form - der euklidischen Algorithmus - ist den meisten von der Berechnung des ggT (größten gemeinsamen Teilers) bekannt.
Aufgaben:
- Erarbeite mit Hilfe des Theoriemoduls "Erweiterter euklidischer Algorithmus" das Verfahren und löse die im Modul enthaltenen Übungen.
Nachdem Bob sich jetzt in der Theorie sicher fühlt, probiert er seine Kenntnisse mit Hilfe einer
© letzte Änderung am 11. November