RSA-Verschlüsselungs Paradoxon

[Aphton]

Hallo liebe Leute,
Mir bereitet RSA Kopfzerbrechen.

Code:

Legende:
C = Chiffre
T = Text
N = RSA Modul
E & D = Enc. & Decryption exponents

Verschlüsselung:
C = T^e mod N

Entschlüsselung
T = C^d mod N

Das Problem liegt hier: das RSA-Modul (N) muss größer sein als der Text (T), den man verschlüsseln will.
Warum? Nun, da, wenn N < T, man nicht zum richtigen Ergebnis kommt.

Nimmt man beispielsweise für T = "123" (entspricht 0x313233; 3 Bytes; wobei es verkehrt rum im Speicher liegt -> 0x333231)
und N 0x333230 (N hat die Größe 2^24 -> ebenfalls 3 Bytes),
dann käme niemals wieder der ursprüngliche Text (T) nach dem Verschlüsseln & Entschlüsseln raus.
Das sollte noch verständlich sein.

Ich finde leider keine passende/elegante Lösung zu diesem Problem. Nimmt man für N eine größere Zahl (z.B: 4 Bytes (2^32)), so geht man die
Gefahr ein, nach dem Modulo bei der Verschlüsselung eine größere Zahl (> 3 Bytes) als Ergebnis zu bekommen, da eben N = 4 Bytes ist.

Das einzige, was machbar wäre, wäre, für C (je 3 Bytes) einen größeren Speicherbereich (4 Bytes) zu reservieren :( und anschließend bei der Entschlüsselung 4 Bytes aufeinmal entschlüsselt.

:wall:

Übrigens, bitte schreibt nur, wenn ihr euch mit RSA auskennt und mir Tipps geben könnt.

Edit:

Ich bin nun nach langem Überlegen davon überzeugt, dass es anders gar nicht geht.
Ich verschlüssle 3 Bytes Datenblöcke und speichere sie in 4 Bytes. Nach dem Entschlüsseln weise ich sie in 3 Byte Datenblöcken wieder zusammen.
Falls trotzdem jeman eine bessere Idee hat, dann nur her damit :)

MfG

[slemke76]

Hallo,

es ist zwar schon eine Weile her, aber ich habe schonmal was mit RSA gemacht :-)
Bei mir war es so, dass ich eine Delphi und eine PHP-Anwendung "kompatibel" machen musste, was RSA angeht.

Um die beschriebenen Probleme zu "umgehen", gibt es die Block-Definition "bt00", "bt01" und "bt02" - dann wird der Text in Blöcke zerlegt, bzw. aufgefüllt (und wie ist halt in den "bt00", etc. definiert) und der Block ver/entschlüsselt.

Schau mal hier:
http://svn2.assembla.com/svn/wimpCry...Box2/LbRSA.pas

Es gibt für Delphi im übrigen ein paar Packages, die das können:
http://www.cityinthesky.co.uk/cryptography.html
http://sourceforge.net/projects/tplockbox/

Ich hoffe, geholfen zu haben :-)

lg
Sebastian

[gammatester]

Zitat:

Zitat von Aphton

Übrigens, bitte schreibt nur, wenn ihr euch mit RSA auskennt und mir Tipps geben könnt.

Edit:

Ich bin nun nach langem Überlegen davon überzeugt, dass es anders gar nicht geht.
Ich verschlüssle 3 Bytes Datenblöcke und speichere sie in 4 Bytes. Nach dem Entschlüsseln weise ich sie in 3 Byte Datenblöcken wieder zusammen.
Falls trotzdem jeman eine bessere Idee hat, dann nur her damit :)

Das ist mit Verlaub ziemlicher Unsinn (es sei denn das soll Lernzwecken dienen)! Die Faktorisierung von 32-Bit-Integer ist doch wohl völlig trivial. Und selbstverständlich geht es anders, wie kannst Du der Meinung sein, "dass es anders gar nicht geht"????

Lies Dir mal die RFC2313 und RFC3447 durch. Dort werden Standardcodierungen und Algorithmen beschrieben. Wenn Du eine relativ vollständige EME-PKCS1-v1_5-Implementation in Pascal/Delphi brauchst, kannst Du meine Opensource mp_rsa-Unit aus MPArith benutzen, im SuppTest-Archiv sind einige RSA-Beispiele, und hier ist die Liste der RSA-Funktionen

[Aphton]

@Gammatester: Kann durchaus möglich sein, dass du mein Problem nicht verstanden hast.
Ist auch nicht verweunderlich, habs so schlecht beschrieben.

Schau dir mal das Beispiel hier an:

Code:

P      4099
Q      4111
N      16850989
Phi(N) 16842780
E      16831
D      6935851

Message = "AAAA" = 0x41414141
Enkodieren: 0x41414141 ^E mod N = 0x6FA2FC
Dekodieren: 0x6FA2FC   ^D mod N = 0xF93601
Fazit: 0x41414141 <> 0xF93601
Weil Message > N

Wobei wäre Message < N -> "AAA" = 0x414141
dann sähe das so aus:

Enkodieren: 0x414141^E mod N = 0x6E9094
Dekodieren: 0x6E9094^D mod N = 0x414141
Fazit: 0x414141 = 0x414141

Ich habs so gelöst:
Wertebreich von N berechnen ( bsp: 4 Bytes ) und diesen Wert (nennen wirs M)-1 als Anzahl der Bytes, die man verschlüsseln will, nehmen ( also 3 Bytes ).
Diese M-1 Bytes pack ich in M Bytes Speicher, da der Chiffre Text im Wertebereich 0..N-1 liegt.

Hoffe, dass nicht allzu viel Blödsinn und Halbwissen mit eingeflossen sind.
Ansonsten verzeiht mir, es ist schon so spät =]

MfG und gute Nacht

[gammatester]

So hört sich das etwas besser, und ist eigentlich schon eine praktikable Rohform: Teile den Klartext in Blöcke ein, deren Zahlenwerte < N sind und verschlüssele die Blöcke.

Wie gesagt, zum Lernen/Verstehen ist das OK, aber für eine richtige Anwendung ist Dein Beispiel-N mit 25 Bit viel zu klein, Richtwert ist heute 1024 ... 2048 Bit.

Was bleibt jetzt eigentlich als Frage?

[Aphton]

Das Problem war eben, dass ich die Message M mit der gleichen Größe (Anz. der Bytes) von N nicht sicher kodieren kann, da es passieren kann, dass N < M ist ODER/UND wenn N > M - der Chiffre Text anschließend größer sein kann.

MfG