RSA-Verschlüsselung wie den Wert abspeichern

[Marcel (Gast)]

guten morgen,
ich gucke mir gerade die rsa-verschlüsselung an. An für sich ist es ja 
nicht kompliziert. Was es für mich aber schwierig macht, sind die 
Zahlen, die dabei rauskommen. Ich hatte eigentlcih vor das ganze in C 
mal umzusetzen.
Wenn ich mir jetzt aber z.B. das Beispiel von Wiki angucke
c=m^e(mod N)
mit den werten
m=7, e=23, N=143
und ich jetzt aber 7^23 rechne, komme ich mit meinem Taschenrechner auf
2.736874734x10^19
In was für einem Datentyp soll man das denn abspeichern?
Wenn ich mir denke, dass dies wirklich noch ein minimales Beispiel ist. 
Normalerweise wird für e ja ein  1024 bit wert genommen und m ist ja 
auch eigentlich größer.

Wie wird so etwas berechnet?
einfach m^e fällt ja schonmal aus. Auch muss man dann ja aus der 
riesen-Zahl ja noch den Modolus berechnen

[Oliver S. (oliverso)]

Marcel schrieb:
> In was für einem Datentyp soll man das denn abspeichern?

bigInt

Oliver

[Jim M. (turboj)]

Gibt es einen Grund warum Du das selber machen willst anstatt eine 
Library wie OpenSSL zu benutzen?

Bei dem ganzen Crypto Zeuchs gibt es etliche Fallstricke, die möchte man 
nicht alle selbst finden...

[Marcel (Gast)]

Jim M. schrieb:
> Gibt es einen Grund warum Du das selber machen willst anstatt eine
> Library wie OpenSSL zu benutzen?

Der einzige Grund ist es, dass ich es selber mal machen wollte.
Theorie ist klar wie es funktioniert, für kleine werte (uint8) geht es 
auch (da ich hier direkt die mathematischen funktionen (exponential und 
modolus) nutzen kann). Jetzt wollte ich es einfach mal selbst probieren 
und bin schon an die Probleme gestoßen.

[sid (Gast)]

zunächst brauchst Du ne powmod funktion, damit die werte am Ende nicht 
explodieren (also den modulus nach jeder quadratur als neuen startwert)
Am einfachsten schaust Du dir das BigINT library an
(kannst auch in den php quellcode gucken da ist das ach recht 
verständlich lesbar)
idealerweise (besonders zur Ausgabe) speicherst Du die fiesen Biester 
als Hex,
das lässt sich nämlich nichtnur schön ausgeben, sondern auch ebensoschön 
wieder in (BIG) integer wandeln.

Ohne ein bigint lib wird das aber nix, fang also damit an ;)

'sid

[Joe Don (Gast)]

Wenn Du einfach mal RSA nachbasteln möchtest, dann kannst Du das auch in 
Python machen, das kann von Haus aus mit beliebig großen Integers 
umgehen.

Wenn Du wissen möchtest, wie man sowas in C macht, dann bist Du jetzt 
auf die erste Herausforderung gestoßen. Du musst dir dafür eine eigene 
Datenstruktur anlegen. Zum Beispiel kann man einen 1024bit unsigned 
integer in einem uint8 Array mit 128 Elementen speichern. Natürlich 
funktionieren dann die ganzen Operatoren +, -, *, / nicht mehr direkt. 
Musst Du dir also auch etwas selber bauen. Das ist alles machbar und 
wenn Du es nicht produktiv einsetzen willst, eine sehr lohnenswerte 
Sache, man kann dabei viel lernen.

Nachdem Du all diese Grundlagen entwickelt hast, kannst Du dir auch 
Gedanken machen, wie man bei großen Potenzen ein paar Multiplikationen 
einspart, z.B https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation.

Oder Du nimmst dafür bereits existierende Bibliotheken, wurde ja bereits 
vorgeschlagen.

[Sven B. (scummos)]

Nimm Python, außer du willst 2 Dinge gleichzeitig lernen: wie man große 
Integer implementiert und wie RSA funktioniert. ;)

Dass das Ergebnis dieser Aktion nirgends eingesetzt werden darf, 
versteht sich von selbst. RSA gilt als notorisch schwierig korrekt zu 
implementieren. So sehr, dass es inzwischen zugunsten von EC ziemlich an 
Boden verloren hat.