HÜ A1

[awl.marco]

Hallo,

ich hab den RSA soweit fertig, allerdings ist mir aufgefallen, dass zB die Nachricht "0" nicht funktionieren würde.
Ich hätte auch eine Idee woran es liegt, aber ich wollte erstmal nachfragen, ob es für die volle Punktzahl ausreicht, wenn die bereits gegebene Nachricht funktioniert.

[Dennis Albrecht]

Also ich weiß jetzt zwar nicht, wie du deinen RSA kongret implementiert hast, aber theoretisch muss auch "0" funktionieren 0^e=0; 0^d=0 ergo: 0^e^d=0 qed.

Gruß Dennis

[awl.marco]

Ja das habe ich auch, also als Chiffrat 0. Weiss aber nicht ob das so richtig sein soll, weil im Prinzip wird die Nachricht ja dann Klartext übertragen.

[Dennis Albrecht]

Eine RSA-Codierung hat mit den Messages "0" und "1" zwar mathematisch gesehen kein Problem, aber diese beiden Zahlen (und abhängig von den Schlüsselpaaren vielleicht auch noch einige wenige mehr) werden halt nicht verändert. Aber bei einem Wortraum von 2^512 sollte es uns nicht jucken, dass man die Messages "0" und "1" vermeiden sollte; der Wortraum wird dadurch nur marginal kleiner.

Gruß

[awl.marco]

Stimmt auch wieder, danke.

[Steven]

Textbook RSA ist generell eine ziemlich schlechte Idee. In der Praxis verwendet man Paddings wie OAEP, um diverse Angriffe auszuschließen. Insbesondere möchte man keine deterministische Verschlüsselung (d.h. Abbildung gleicher Klartexte auf gleiche Chiffretexte) udn man möchte zudem kryptanalytische Angriffe auf Teile des Chiffretexts ausschließen (all-or-nothing-Prinzip).

[Woyzeck]

Ich habe an dieser Stelle auch noch eine Frage zu der RSA-Aufgabenstellung.

Und zwar ist gefordert, dass "der Klartextraum (und damit der Modulus n) groß genug gewählt wird, um die obige Nachricht darstellen zu können".

Mit anderen Worten bedeutet das ja, dass n > m gelten muss. Soll nun einfach ein n >910111212.... gewählt werden oder soll das für jede erdenkliche Nachricht mit <=512 bits gelten?

Gruß Woyzeck

[Dennis Albrecht]

Ich denke, dass da einfach mehrere Versionen der Aufgabenstellung zusammenkopiert wurden.
Wir sollen ein n im Bereich von 512 bits generieren. Dadurch ist der Wortraum 512 bits (zumindest aber 511 bits, je nachdem, wie groß n dann genau wird) groß.
Damit liegt m auf jeden Fall in diesem Wortraum (m ist irgendwo so bei 150 bits ganz grob überschlagen).
Also erfüll einfach das 512-bit-Kriterium und ignorier den Rest (zumindest alles in Hinblick auf die Wortraumgröße).

Gruß

[Woyzeck]

Das war auch mein erster Gedanke, allerdings ist ja auch z.B. 00100100 8 bits lang und damit kann meines Erachtens auch der Modulus aus [0; 2^512 - 1] gewaählt werden

Eine Möglichkeit wäre natürlich auch beim Verschlüsseln der Nachricht zu überprüfen, ob m > n, und falls das aufkommt einen neuen Key anfordern (in der Praxis wohl kaum üblich) oder die Nachricht in Blöcke aufteilen und verschlüsseln.

Eine Stellungnahme eines Tutors zu dieser Problematik wäre wünschenswert

Viele Grüße

Woyzeck

[kbraden]

AFAIK wird bei dem Generieren von zufaelligen Primzahlen haeufig manuell das hoechste und niedrigste Bit der Zufallszahl gesetzt und dann erst auf Primeigenschaft getestet - dann hast du garantiert eine ungerade n-bit Zahl.

Also generierst du zwei 256-bit Primzahlen, wenn du die multiplizierst hast du garantiert ein 511- oder 512-bit Modulus. Meine Tutorin meinte dass das in Ordnung sei, man kann aber auch eine Behandlung des 511-Bit-Fall einfuehren (nochmal probieren, abbrechen,...)

[Woyzeck]

Ich habe meinen Primzahlgenerator selbst geschrieben und da auch die Möglichkeit gegebeben eine Range anzugeben. Es ist also an sich kein Problem das so zu machen.

Für mich stellt sich eigentlich nur noch die Frage, wie die Aufgabe gedacht war.

[VMann]

Gibt es eine Bedingung, in welchem Größenbereich e zufällig gewählt werden muss? Also, ausser dass es in Z*(phi(n)) sein muss?

[Dennis Albrecht]

es gibt keine Einschränkung, aber generell gilt: je größer desto ausgeglichener (egal wie groß e ist, d wird 511/512-bit groß, daher hab ich e auch sehr groß gewählt, damit die Exponenten ähnlich groß sind und nicht eine 4-bit und die andere 511-bit ist)

[Steven]

es gibt keine Einschränkung, aber generell gilt: je größer desto ausgeglichener

In der Praxis wird e oftmals möglichst klein gewählt, um den Rechenaufwand zu senken. Man kann sich überlegen, welcher e-Wert minimal funktionieren kann.

Für eure Hausübung ist es egal, welchen (funktionierenden!) e-Wert ihr nehmt.

[Erich]

Frage:

Wie genau soll ich ein geeignetes e finden?

Oder besser, wie gehe ich sicher, dass eine zufällige Zahl e in Z*(phi(n)) liegt ?

Und was ist mit d?

Soll ich einfach ein vielfaches von e finden, dass mod (phi(n)) = 1 ist, und durch e teilen? (vgl. TS-4 S.5 )
Wie soll ich das möglichst effizient und leserlich gestallten ( in Java )?

Irgendwie sehe ich nicht wie effiziente Exponentiation oder Erw.Euklid bei obigen Problemen weiterhelfen sollen ( zumal e ja ein Input zu letzterem, aber eben unbekannt ist ).