mit sehr großen Zahlen arbeiten

[Tryndamere]

Hallo Community,

Mir stellt sich seit einiger Zeit die Frage,
Wie arbeiten kryptographische Algorithmen. Ich schaue einmal Richtung RSA. hier sollen 2 möglichst große Primzahlen multipliziert werden, damit es ein n ergibt.

Wie handhabt man denn so etwas programmiertechnisch?

Also wo wird getrickst um das Modulo n auszurechnen, wenn es in keinen bekannten Datentyp passt. Ich hab da meine Vermutungen aber die wäre alle so ineffizient das es aus ist.

 

[drfuture]

Warum zu lange für bekannte Datentypen
- in Double passt immerhin eine 12-stellige Zahl - was nun nicht gaaaanz so wenig ist...
- darüber hinaus wäre long double mit 18 Stellen

 

[Larius]

Vor allem könnte man auch mit Unsigned arbeiten womit man einen großen positiven Bereich abdecken kann.

 

[Kugelfisch]

Für kryptografische Anwendungen sind allerdings sowohl Gleitkomma-Datentypen (keine garantierte Präzision, selbst long double ist mit 80 oder 128 Bit Länge bei weitem zu kurz, um die üblichen Schlüssellängen mit voller Präzision aufzunehmen) als auch die unsigned-Varianten üblicher Datentypen inklusive long long (64 Bit unsigned - zu kurz) ungeeignet.

Um die üblichen Schlüssellängen von > 1024 Bit bei RSA handhaben zu können, muss man Big-Integer-Arithmetik entweder selbst implementieren oder eine entsprechende Bibliothek nutzen. Einen kurzen Überblick bietet etwa https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic, wo auch auf verbreitete Algorithmen z.B. zur Multiplikation (z.B. Karatsuba) von beliebig grossen Zahlen hingewiesen wird. Problematischer als die Multiplikation in Bezug auf die Länge ist bei RSA übrigens die Exponentialfunktion modulo N (P=C^K mod N). Siehe dazu auch https://en.wikipedia.org/wiki/Modular_exponentiation.

 

[KaPiTN]

.Net bietet die structure BigInteger.

Für die Sprache Deiner Wahl suche nach Langzahlarithemik !

 

[Tryndamere]

ja genau das was Kugelfisch und KaPiTN geschrieben ahben, ahbe ich gesucht :-)

Also gibt es spezielle Datentypen dafür

Danke für eure Antworten

 

[Larius]

Hm stimmt, die Exponentialkomponente hab ich komplett außer Acht gelassen. Damit sind dann bei großen Zahlen die bisher bestehenden Datentypen unzureichend (und ungenau).

 

[Mr_J]

Da eine Modulofunktion aber auch dazu kommt wird die Zahl wieder deutlich kleiner.

MfG
Mr. J

 

[Kugelfisch]

Korrekt, allerdings nur bei effizienter ModExp-Implementierung (die zwingend notwendig ist, um RSA mit sinnvollen Schlüssellängen überhaupt nutzen zu können); ausserdem wird das Ergebnis im Allgemeinen nach wie vor in der Grössenordnung des Modulus liegen, der in der Praxis mindestens 2048 Bit lang sein sollte. Würde man die Standard-64-Bit-Datentypen (z.B. unsigned long long int) nutzen, würde man einen Modulus mit maximal 64 Bit erhalten, der sich in Sekundenbruchteilen trivial faktorisieren lässt.

 

[wolfsjunge]

Hier, vielleicht nicht direkt bezogen aufs Thema, eine ziemlich gute, detaillierte und fundierte Erklärung von Public-Key Kryptographie, RSA und im besonderen der Modexp Algorithmus.

 

[Mr_J]

Wenn man mal dazu etwas tiefer einsteigen will kann ich immer noch die Einführung in die Kryptographie von Johannes Buchmann empfehlen. Ich fand es sehr gut und verständlich erklärt und es war zu meiner Studienzeit eine gute Ergänzung zur Vorlesung.

MfG
Mr. J