Messungen

Erzeuge z.B. mit Hilfe des krypto0.py-Systems oder der unten 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. Cryptool oder ein CA-System wie Maxima können bei der Ermittlung der Primzahlen helfen, da sie über effiziente Implementierungen von nextprime verfügen. Mittlerweile verfügt auch krypto0.py über ein effizientes nextprime. Die Faktorisierung der Zahlen n kann dann z.B. mit Python oder unter angeführtem Programm oder mit Maxima oder mit ... durchgeführt werden. Immer wäre eine Möglichkeit, die Rechenzeit zu bestimmen, nützlich. Die Messtabelle soll etwas folgende Form haben:

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

Für 'Tipp-Faule' ist in krypto.py eine Funktion f eingebaut.

>>> f(12007001)
([3001, 4001], 0.0016918182373046875)

Hilfsprogramme für 'Nicht-Pythonistas'

Die folgenden Programme wurden basierend auf der Langzahlarithmetik GInt von Walied Othman in Delphi geschrieben. Sie sind auch unter wine in Linux lauffähig. 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

Auswertung

Ermittle mit Hilfe der Tabelle und einer Tabellenkalkulation einen Schätzwert, wie lange die Faktorisierung einer 512-Bit-Zahl dauern könnte. Wieviele Stellen hat eine solche Zahl in dezimaler Darstellung?

Backdoor-Angriff

Wie kann man sich gegen einen Backdoor-Angriff schützen?

Enthält unser Kryptosystem krypto0.py ein Backdoor? Kannst du das beurteilen? Kann das ein Fremder beurteilen?

Welcher Art könnte ein Backdoor in einem Betriebssystem sein? Kann man bei einem Betriebssystem sicher sein, dass kein Backdoor enthalten ist? Kann ein Betriebssystem die nationale Sicherheit oder das Überleben einer Firma gefährden?

Links

• RSA-129RSA-129
• Die Sicherheit des RSA-Verfahrens - Klaus Pommerening, Uni Mainz
• 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.