RSA Implementierung

seceng
Erstie
Erstie
Beiträge: 16
Registriert: 9. Dez 2008 10:48

RSA Implementierung

Beitrag von 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

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: RSA Implementierung

Beitrag von 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...
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

Benutzeravatar
Jan Schejbal
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 1. Nov 2007 00:17

Re: RSA Implementierung

Beitrag von 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.
\(a = \sum\limits_{i=0}^{\infty} a_i \cdot 10^i\) mit \(a_0 = 2 \wedge a_1 = 4 \wedge \forall n \in \mathbb N^+\setminus\{1\} ~~ a_n = 0\)

Das Schlimmste an Zensur ist ████████████████████████

m_hof
Mausschubser
Mausschubser
Beiträge: 47
Registriert: 9. Jan 2005 13:37
Wohnort: Darmstadt

Re: RSA Implementierung

Beitrag von 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.

Benutzeravatar
Jan Schejbal
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 1. Nov 2007 00:17

Re: RSA Implementierung

Beitrag von Jan Schejbal »

m_hof hat geschrieben: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.
\(a = \sum\limits_{i=0}^{\infty} a_i \cdot 10^i\) mit \(a_0 = 2 \wedge a_1 = 4 \wedge \forall n \in \mathbb N^+\setminus\{1\} ~~ a_n = 0\)

Das Schlimmste an Zensur ist ████████████████████████

Osterlaus
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Re: RSA Implementierung

Beitrag von 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
Windoof-User
Windoof-User
Beiträge: 31
Registriert: 3. Okt 2007 21:58

Re: RSA Implementierung

Beitrag von 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
Computerversteher
Computerversteher
Beiträge: 325
Registriert: 11. Dez 2005 13:14
Wohnort: Darmstadt

Re: RSA Implementierung

Beitrag von Christoph-D »

treo hat geschrieben: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?
"I believe in the fundamental interconnectedness of all things." (Dirk Gently)

Nephilim
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 31. Mai 2005 23:36
Wohnort: Griesheim

Re: RSA Implementierung

Beitrag von 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 8)

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 :mrgreen:

FeG
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 182
Registriert: 6. Dez 2007 07:01

Re: RSA Implementierung

Beitrag von FeG »

Nephilim hat geschrieben: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
Mausschubser
Mausschubser
Beiträge: 72
Registriert: 20. Jan 2007 15:51

Re: RSA Implementierung

Beitrag von 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 :D 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
Windoof-User
Windoof-User
Beiträge: 31
Registriert: 3. Okt 2007 21:58

Re: RSA Implementierung

Beitrag von 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
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Re: RSA Implementierung

Beitrag von 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
Mausschubser
Mausschubser
Beiträge: 72
Registriert: 20. Jan 2007 15:51

Re: RSA Implementierung

Beitrag von 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
Mausschubser
Mausschubser
Beiträge: 87
Registriert: 7. Nov 2007 18:09
Kontaktdaten:

Re: RSA Implementierung

Beitrag von 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 ... :roll:

Antworten

Zurück zu „Archiv“