HÜ A1

awl.marco
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 21. Mai 2010 15:29

HÜ A1

Beitrag von 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
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 222
Registriert: 4. Okt 2010 18:15

Re: HÜ A1

Beitrag von 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
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 21. Mai 2010 15:29

Re: HÜ A1

Beitrag von 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
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 222
Registriert: 4. Okt 2010 18:15

Re: HÜ A1

Beitrag von 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
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 21. Mai 2010 15:29

Re: HÜ A1

Beitrag von awl.marco »

Stimmt auch wieder, danke. :)

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: HÜ A1

Beitrag von 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
Erstie
Erstie
Beiträge: 18
Registriert: 13. Mär 2011 15:30

Re: HÜ A1

Beitrag von 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
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 222
Registriert: 4. Okt 2010 18:15

Re: HÜ A1

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

Gruß

Woyzeck
Erstie
Erstie
Beiträge: 18
Registriert: 13. Mär 2011 15:30

Re: HÜ A1

Beitrag von 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
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 15. Okt 2010 20:35

Re: HÜ A1

Beitrag von 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
Erstie
Erstie
Beiträge: 18
Registriert: 13. Mär 2011 15:30

Re: HÜ A1

Beitrag von 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
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 16. Apr 2009 11:51

Re: HÜ A1

Beitrag von 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?
Computer tun nicht das, was du von ihnen willst, sie tun das, was du ihnen sagst.

Dennis Albrecht
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 222
Registriert: 4. Okt 2010 18:15

Re: HÜ A1

Beitrag von 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) :D :D :D

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: HÜ A1

Beitrag von Steven »

Dennis Albrecht hat geschrieben: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
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 17. Okt 2010 13:29

Re: HÜ A1

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

Antworten

Zurück zu „Archiv“