RSA	[modulo-Rechnen] [modulares Potenzieren] [Algorithmus von Euklid] [Euler-Funktion] [Satz von Euler] [modulares Inverses] [Primfaktorzerlegung] [Primzahlen finden] [Schlüsselpaar] [Angriff] [Sicherheit] Pfad: [Startseite] / [Fächer] / [Informatik] / [Kryptologie] / [RSA] / [Sicherheit]
Hohenstaufen-Gymnasium Kaiserslautern	Autor: mk Letzte Änderung dieser Seite: 22.12.2007 13:08:17  87 Sicherheit

Hilfsprogramme

Die folgenden Programme wurden basierend auf der Langzahlarithmetik GInt von Walied Othman geschrieben. Walied Othman bietet auf seiner Webseite freie Implementierungen gängiger kryptologischer Verfahren für Delphi an.

Programm zur Primfaktorzerlegung großer Zahlen

primfak_lang.zip

Programm zum Finden großer Primzahlen

primGen_lang.zip

Programm zum Multiplizieren großer Zahlen

FGInt.zip

Messungen

Erzeuge z.B. mit Hilfe der angeführten Programme große Zahlen der Form n = p·q. Die Primzahlen p und q sollen dabei in der Nähe von 30..0 bzw 40..0 liegen. Die Zahlen 30..0 sollen beginnend bei 30 jeweils um eine Stelle wachsen, analog 40..0 = 40, 400, 4000, .. . Die Zahlen n wachsen dann jeweils um zwei Stellen. Die Faktorisierung der Zahlen n kann dann z.B. mit obigem Programm durchgeführt werden. Die Messtabelle soll etwas folgende Form haben:

Achtung, bitte sich nicht zu viel vornehmen und die Tabelle Schritt für Schritt erstellen.

Auswertung

Ermittle mit Hilfe der Tabelle und einer Tabellenkalkulation einen Schätzwert, wie lange die Faktorisierung einer 512-Bit-Zahl dauern könnte.

Links

• Die Sicherheit des RSA-Verfahrens - Klaus Pommerening, Uni Mainz
• Die Sicherheit des RSA-Verfahrens - Julius-Leber-Schule, Hamburg
• Spezialhardware bedroht möglicherweise RSA-Sicherheit - heise newsticker, 2002

Maxima-Funktionen zur Zahlentheorie

m, m1, m2, ..., n sind natürliche Zahlen!

• mod(m, n) - m modulo n (der nichtnegative Rest von m/n
• floor(m), ceiling(m) - Rundungsmöglichkeiten
• ggT = gcd(m1, m2, ...) - größter gemeinsamer Teiler
• kgV = lcm(m1, m2, ...) - kleinstes gemeinsames Vielfaches
• floor(a/b) - (positive, a und b>0) Ganzzahldivision
• power_mod(a, n, m) - liefert a^n mod m
• inv_mod(a,m) - Die "Inverse" von a modulo m
• primep(m) - Überprüfung, ob m eine Primzahl ist
• next_prime(m), prev_prime(m) - nächstliegende Primzahlen zur Zahl m
• factor(m) - Zerlegung einer Zahl in ihre Primfaktoren

Übungen

Berechne den größten gemeinsamen Teiler von 3465 und 924 und bestimme die gemeinsamen Teiler!

Welche Uhrzeit u (in 24-Stunden-Darstellung) ist "1000 Stunden nach Mitternacht"? Wieviele Tage sind verstrichen?

Überprüfe, ob die Mersennesche Zahl m = 2^23-1 eine Primzahl ist! Bestimme die nächstliegenden Primzahlen.

lokal