RSA Implementierung

[seceng]

Liebe Studenten,
in der Hausübung sollen Sie in der ersten Aufgabe das RSA-Verfahren implementieren. Bitte beachten Sie dabei, dass Sie den erweiterten Euklidischen Algorithmus implementieren müssen.

Ein schönes Weihnachtsfest und einen guten Rutsch wünsche ich Ihnen ,

Beste Grüße,
Heike Busch

[bruse]

Die von Java angebotene Bibliotheksfunktion für inverse modulo m geht also nicht in Ordnung? Das geht aber nicht wirklich klar aus der Aufgabenstellung hervor...

[Jan Schejbal]

Ich dachte in der Übungsbesprechung sei sogar explizit gesagt worden dass wir für den erweiterten Euklid ne Library nutzen dürfen. Freut mich jetzt natürlich richtig, weil ich schon ne implementierung hatte, sie aber gelöscht und durch ne lib ersetzt hab weil ich mir bei meinem code nicht 100% sicher war ob er immer macht was er soll.

[m_hof]

Hallo zusammen/Frau Busch,

sehe ich es auch richtig das ich die "Primzahlsuche" implementieren muss; und kein Bibliothek nutzen darf, die mir eine Pseudoprimzahl(/mögliche Primzahl) liefert?!

Danke für Antworten schon mal im voraus.

[Jan Schejbal]

sehe ich es auch richtig das ich die "Primzahlsuche" implementieren muss; und kein Bibliothek nutzen darf, die mir eine Pseudoprimzahl(/mögliche Primzahl) liefert?!

Also zumindest für "prüfe ob (wahrscheinlich) prim" bin ich mir recht sicher dass wir libraries benutzen dürfen, da wir die Algorithmen dafür nicht hatten und TS ja eigentlich nicht das Ausrechnen von Primzahlen als Lehrinhalt hat.

[Osterlaus]

Vor allem für große Primzahlen sind ja auch etwas geschicktere Algorithmen nötig als eine einfache for-Schleife mit Modulo-Berechnung Und im Gegensatz zum EEA ist eine gute Primzahlprüfung ja kein Vorlesungsbestandteil. Also, um Heike zu zitieren: Nicht überall das Rad neu erfinden

[treo]

Ich hoffe doch auch das wir zum erstellen der Primzahlen Libraries verwenden dürfen, ich hab zwar den Miller Rabin mal implementiert, aber schon bei 40bit dauert es eigentlich zu lange um da gescheit etwas zu machen.

Wäre gut wenn wir da offiziell noch eine Antwort bekommen könnten.

[Christoph-D]

Ich hoffe doch auch das wir zum erstellen der Primzahlen Libraries verwenden dürfen, ich hab zwar den Miller Rabin mal implementiert, aber schon bei 40bit dauert es eigentlich zu lange um da gescheit etwas zu machen.

Miller-Rabin und ähnliche komplizierte Primzahltests sollten doch auch Zahlen bis zu einigen tausend Bits in Sekundenbruchteilen analysieren können?

[Nephilim]

Ich würde auch einfach mal behaupten, wenn wir schon Librarys benutzen können, dann wirklich alle. Die Java.math.biginteger für BigInteger ist gerade für RSA/Krypto gemacht. Alternativ auch sun.security.habvergesserwasgenau

Sowohl das Moduloinverse, der GCD, als auch eine Funktion für schnelle Exponentation modPow(e, n) ist vorimplementiert.

In der Übung hieß es noch

[...] das Rad nicht neu erfinden [...]

Warum sollen wir jetzt plötzlich Euklid und erweiterten Euklid selbst implementieren (von den Vorlesungsfolien abschreiben?) Sowas würde ich in GDI II einordnen... wenn wir das für die Klausur üben sollen, sagt bescheid.

Schöne Weihnachten

[FeG]

Warum sollen wir jetzt plötzlich Euklid und erweiterten Euklid selbst implementieren (von den Vorlesungsfolien abschreiben?

Ich wundere mich auch, dass wir da plötzlich doch keine Library verwenden dürfen. In der Vorlesung hatte Prof. Katzenbeisser das noch explizit erlaubt.

[Wetterfrosch]

Hallo,

ich habe mit der Implementierung ein bisschen rumgespielt.
Jetzt habe ich gemerkt, dass mein Rechner schon bei relativ "kleinen" Zahlen probleme hat.

Die Nachricht als einen Block zu verschlüsseln erscheint mir unmöglich. Also habe ich mal probiert eine Zahl mit nur drei stellen zu verschlüsseln. Mein schlüssel und das n habe ich dabei ziemlich kein gewählt.

Das höchste was mein Laptop so verarbeiten kann wäre zum Beispiel: (123^50000)mod 88888888
Mein Schluessel e hat also 5 Stellen (Dezimal) mein Block 3 Stellen(dezimal). Sobald ich einen 6 Stelligen Schlüssen nehme dauert das alles schon ein bisschen länger Ist ja auch klar wieso das eine Zeit dauert.

Mir ist es aber nun ein Rätsel wie man mir der Rechenkraft eines Laptops zum Beispiel einen 256 Stellen (binär) verschlüsseln kann.

Ein RSA Implementierung habe ich bereits. Mit großen Schlüsseln dauert es halt ein paar Jahre bis das Program eine Lösung ausspuckt.

Bis zu welcher Schlüsselgröße läuft den euer Programm?

[treo]

Wie berechnest du denn a^b mod n ?
Es gibt für genau dieses Problem nämlich einen Algorithmus mit dem man das schnell berechnen kann (Siehe z.B. in 3.12 Schnelle Exponentiation in "Einführung in die Kryptographie" vom Buchmann).
Wenn wir Libs verwenden dürfen (so werde ich das nämlich jetzt erstmal machen...) dann kann man dafür (in Java zumindest) auch die modPow Funktion von BigInteger verwenden, sie macht wenn ich das richtig sehe nämlich das gleiche.

[Osterlaus]

Mein Programm läuft mit beliebig großen Schlüsseln, vermute ich mal. Aktuell generiere ich 80 Bit lange Schlüssel, damit gehts. Was für einen Zahlentyp verwendest du und wie arbeitest du damit? Der Hinweis auf BigInteger wurde ja schon gegeben

[Wetterfrosch]

Diesen Code hier auszuführen dauert vielleicht eine halbe Sekunde

Funktioniert noch:

Code: Alles auswählen

	BigInteger mod = new BigInteger("39970752");
	BigInteger a1 = new BigInteger("213");

	System.out.println(a1.pow(50000).mod(mod));

Wenn ich diesen Code hier ausführe. Also bei dem pow noch eine Null dranhänge kann ich schon lange warten. Habe nach einer halben Minute abgebrochen.

Funktioniert nicht:

Code: Alles auswählen

	BigInteger mod = new BigInteger("39970752");
	BigInteger a1 = new BigInteger("213");

	System.out.println(a1.pow(500000).mod(mod));

Das sind fiktive Zahlen. Wenn ich die Werte aus meinen RSA Programm oder die auf dem Buch von Frau Eckert nehme funktioniert es auch nicht

EDIT: Ich habe gerade modpow ausorobiert. Das funktioniert bestens!

Code: Alles auswählen

	BigInteger mod = new BigInteger("39970752");
	BigInteger a1 = new BigInteger("213239849879879732987498327493288768976");
	BigInteger pow = new BigInteger("500000009879879879879879879870000876989869876987600000");
	System.out.println(a1.modPow(pow, mod));

[ChRiZz88]

Herzlich Willkommen an der TU-Darmstadt.
Wieso schafft es eigentlich kein Fachbereich, sich über eigen gestellte Aufgaben solange Gedanken zu machen, um die Aufgabe nicht während der Bearbeitungszeit abändern / korrigieren und / oder ergänzen zu müssen?
Im Gegenteil: "Gegebenenfalls dürfen sie Programmbibliotheken verwenden."
Das sagt eindeutig, dass BigInteger erlaubt ist und damit auch jegliche in BigInteger mögliche Funktionen. Naja, wenn ichs nicht schon gewohnt wäre, würde ich mich wohl drüber aufregen ...