Rechenoperationen für sehr lange Binärzahlen

[kdot]

Hallo

Seit einiger Zeit interessiert mich die Frage, wie es möglich ist, besonders lange, ganze Zahlen(mit bis zu 400 Stellen) miteinander zu addieren, subtrahieren, multiplizieren und dividieren. weiterhin wäre es schön zu erfahren, wie man diese bitketten dann als dezimalzahlen wieder ausgeben lassen kann. Das ganze soll dazu dienen, eine RSA-verschlüsselung in einen eigenen Texteditor zu integrieren.

Ich bedanke mich schonmal für eure Mitarbeit.

bis bald
kdot

[bischi]

Geht auf jeden Fall:

1) Selber Proggen - die Grösse der Zahl wird einzig durch vorhandenen Arbeitsspeicher begrenzt

2) Die meisten Spachen haben Bibliotheken dafür - jetzt müsste man noch die Sprache, die du benutzt, kennen...

MfG Bischi

PS: Addieren, subtrahieren und multiplizieren sind kein Problem - die Division vor riesigen Zahlen dauert allerdings SEHR lange; Dies ist genau das, was RSA ausnutzt...

[kdot]

danke erstmal für die antwort. ich will C mit gcc/linux benutzen.

habe gerade eben mit meinem info-prof geredet und er meint, ich solle doch einen Vektor aus 32bit-zahlen erstelln, in den dann meine zahl hineinpassen könnte. dann mittels dem assemblerbefehl "adc" den vektor elementweise mit übertrag zu addieren. außer adc gibts auch noch befehle, die division etc mit carryflag machen.
eine fertige bibliothek wäre zwar ganz nett, aber ich will doch was lernen...


PS.: RSA nutzt meines erachtens nicht die tatsache, dass divisionen SEHR lange dauern(sooolage ist das nämlich gar nich) sondern eher die tatsache, dass es SEHR SEHR lange dauert, eine naja sagen wir mal 200-stellige zahl in ihre Primfaktoren zu zerlegen. der Zeitraum über den wir hier sprechen liegt bei ungefähr der Hälfte der in unserem universum bisher verstrichenen zeit...

[anda_skoa]

http://www.swox.com/gmp/

Ciao,
_

[peschmae]

der mit der Hälfte und dem Universum ist aber sehr relativ :D

Ich finde so Vergleiche übrigens blöd. Genau so wie all die Vergleiche von Grössen im Mikro- und Nanometerbereich mit menschlichen Haaren(*)... ;)

MfG Peschmä

(*) ich weiss nämlich nicht wie dick ein "menschliches Haar" (in Normgrösse ;)) ist...

[bischi]

PS.: RSA nutzt meines erachtens nicht die tatsache, dass divisionen SEHR lange dauern(sooolage ist das nämlich gar nich) sondern eher die tatsache, dass es SEHR SEHR lange dauert, eine naja sagen wir mal 200-stellige zahl in ihre Primfaktoren zu zerlegen. der Zeitraum über den wir hier sprechen liegt bei ungefähr der Hälfte der in unserem universum bisher verstrichenen zeit...

Naja - um die Zahl in Primfaktoren zu zerlegen, musst du dividieren... Geht für eine einzelne (lange) Zahl mit einem herkömmlichen Computer wohl noch in annehmbarer Zeit (<1Tag, je nach Grösse), dauert aber SEHR lange, wenn dus mehrmals machen willst...

Und noch eins dieser schönen Universumsbeispiele: Problem von Hanoi - 64 Scheiben, eine Scheibe pro Minute bewegen: Dauert etwa 15 mal vom Urknall bis heute...

MfG Bischi

[peschmae]

Na gut, mit einer Scheibe pro Minute hast du dir wohl nen Philosophen angestellt, der sich zwischen dem Scheiben rumschubsen immer ein paar Integrale ausrechnet ;)

MfG Peschmä

[bischi]

Na gut, mit einer Scheibe pro Minute hast du dir wohl nen Philosophen angestellt, der sich zwischen dem Scheiben rumschubsen immer ein paar Integrale ausrechnet ;)

Der Legende nach ist es ein Mönchsorden, der das versuchen soll. Die Scheiben sind ziemlich gross (so Wagenradgrösse) und aus Massivgold (nein - ich sag jetzt nicht, wo man die klauen kann...) - für die grösseren dürftest du wohl mehrere Leute brauchen. Weiter sind die beiden Stapel nicht direkt nebeneinander. Eine Minute ist also eher noch zu wenig - es könnte ja auch mal Glatteis haben,... Und irgendwann müssen sogar Mönche auch mal etwas anderes machen, als Gold schleppen. Langer Rede, kurzer Sinn: Der Legende nach soll die Welt untergehen, wenn die Mönche das Ziel erreicht haben und das geht ja noch (bei richtiger Umschichtstrategie) immerhin 14.5 mal so lange, wie das Universum bis heute existierte...

Die Welt wird untergehen! (Aber noch nicht so bald!)

MfG Bischi

[peschmae]

Cool. Damit verbringt ihr also eure Zeit :D

Kann man da irgendwo zugucken. Ab und zu wärs schon jemanden zu sehen der etwas noch sinnloseres macht... :D

Jetzt noch schnell mal den Wert ausrechnen, schliesslich bin ich ka Kapitalist.

MfG Peschmä

[bischi]

Cool. Damit verbringt ihr also eure Zeit :D
War ein Beispiel für die Komplexität eines Algorithmuses.



Kann man da irgendwo zugucken. Ab und zu wärs schon jemanden zu sehen der etwas noch sinnloseres macht... :D

Gibt leider keine Webcam...

MfG Bischi

[peschmae]

Das ist Thread-Hijacking in Reinform was wir hier machen :)

MfG Peschmä

[Joghurt]

Und noch eins dieser schönen Universumsbeispiele: Problem von Hanoi - 64 Scheiben, eine Scheibe pro Minute bewegen: Dauert etwa 15 mal vom Urknall bis heute...Ein Zug pro Sekunde! Dann sinds fast 43 mal vom Urknall bis heute...

[peschmae]

Scheint bischi hat den besseren Algo ;)

MfG Peschmä

[BlauerBlitz]

Hallo!

Ich hab mir diese Library zwar nicht angesehen, vielleicht hilft sie dir aber weiter:

"GMP", zu finden auf http://www.swox.com/gmp

Hier heißt es:
"GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on."

Klingt doch nicht übel! Den Sourcecode müsste man sich halt anschauen ...

Ciao
Werner

[Joghurt]

@kdot: Für RSA gibt es fertige Bibliotheken.

Außerdem ist RSA nicht geeignet, ganze Texte zu Verschlüsseln, da RSA dafür einfach viel zu langsam ist (sehr lange Schlüssel sind notwendig)

Was man allgemein macht, ist, eine Zufallszahl zu erzeugen, und den Text dann mit dieser Zahl als Schlüssel mit einem normalen symmetrischen Algorithmus, zum Beispiel AES, zu verschlüsseln. Nur Der Schlüssel/die Zufallszahl wird nun mit RSA verschlüsselt.

[kdot]

ich bedanke mich für die amüsanten hinweise. die gmp-library ist ne geniale sache und dazu gibts ne tolle doku unter:
http://www.swox.com/gmp/gmp-man-4.1.4.pdf

beschäftige mich jetz erst seit heute vormittag und bin absolut begeistert von der lauffreudigkeit der bibliothek. die arbeiten ungefähr so: man zerlget die große zahl in lauter prozessorwörter, also in einen großen vektor aus lauter 32/64-bit-zahlen und rechnen immer nur mit einzelnen vektorfeldern. geile sache, muss ich sagen.

danke auch zu der(mir leider zu kurz geratenen) Erläuterung zu RSA. ich würde vorschlagen, man eröffnet mal ein neues Thema, in dem auf RSA im speziellen eingegangen wird. es ist nämlich(wie mein prof sagen würde:) nicht trivial, rsa zu implementieren. noch viel weniger trivial ist es, öffentliche Schlüssel wieder in ihre primfaktoren zu zerlegen(rechnerisch/mit bruteforce) ich hab da auch noch einen drittenansatz, aber den verrat ich euch erst, wenn ichs geschafft hab, aber dann werdet ihr sowieso von mir in der zeitung lesen ;-))

also, danke erstmal und viel spaß noch

[Joghurt]

Falls der Drittanzahl die Berechnung des diskreten Logarithmus ist: vergiss es, oder besser: versuch es. Dann hast du auch gleich Diffe-Hellman (IIRC) geknackt.

[bischi]

Ein Zug pro Sekunde! Dann sinds fast 43 mal vom Urknall bis heute...
Naja - wie lange existiert das Universum schon? Je nach Forscher so zwischen 1 Mia und 15 Mia Jahren - wir sind also relativ genau beisammen - oder wie Physiker sagen würden: Die Grössenordnung stimmt.



Scheint bischi hat den besseren Algo
Immer doch! Naja - ich hab den bestmöglichen. Du machst damit keinen überflüssigen Zug.



Was man allgemein macht, ist, eine Zufallszahl zu erzeugen, und den Text dann mit dieser Zahl als Schlüssel mit einem normalen symmetrischen Algorithmus, zum Beispiel AES, zu verschlüsseln. Nur Der Schlüssel/die Zufallszahl wird nun mit RSA verschlüsselt.



danke auch zu der(mir leider zu kurz geratenen) Erläuterung zu RSA. ich würde vorschlagen, man eröffnet mal ein neues Thema, in dem auf RSA im speziellen eingegangen wird. es ist nämlich(wie mein prof sagen würde nicht trivial, rsa zu implementieren. noch viel weniger trivial ist es, öffentliche Schlüssel wieder in ihre primfaktoren zu zerlegen(rechnerisch/mit bruteforce) ich hab da auch noch einen drittenansatz, aber den verrat ich euch erst, wenn ichs geschafft hab, aber dann werdet ihr sowieso von mir in der zeitung lesen ;-))


@Joghurt: Wie genau funktionieren symmetrische Algos?
@kdot und Rest: hier gehts weiter: http://www.mrunix.de/forums/showthread.php?p=194180#post194180

MfG Bischi

[Joghurt]

Naja - wie lange existiert das Universum schon? Je nach Forscher so zwischen 1 Mia und 15 Mia Jahren - wir sind also relativ genau beisammen - oder wie Physiker sagen würden: Die Grössenordnung stimmt.Du hast nur pro Minute geschrieben. Pro Sekunde reicht schon, und wirkt für einen Menschen beeindruckender, wenngleich es auch nur der Faktor 60 ist.


@Joghurt: Wie genau funktionieren symmetrische Algos?
Code = Encipher(Nachricht, Schlüssel)
Nachricht = Decipher(Code, Schlüssel)

Du brauchst nur einen Schlüssel, der Algorithmus muss nicht zwangsweise identisch sein für Ver- und Entschlüsselung, ist es jedoch meistens.

Einfachstes Beispiel: Encipher = Addition, Decipher = Subtraktion.


Vielleicht ganz hilfreich: die Enigma:
http://en.wikipedia.org/wiki/Enigma_machine
(Zum Glück waren die Deutschen zu Arrogant und bescheuert, um sie richtig zu benutzen, weswegen die Engländer den Code knacken konnten. Ohne hätte der Krieg evtl. noch ein paar Jährchen länger gedauert.)

AES ist z.B. hier beschrieben:
http://en.wikipedia.org/wiki/Advanced_Encryption_Standard

[kdot]

Falls der Drittanzahl die Berechnung des diskreten Logarithmus ist: vergiss es, oder besser: versuch es. Dann hast du auch gleich Diffe-Hellman (IIRC) geknackt.

Nein, der dritte ansatz ist nicht vergelichbar mit bekannten mathematischen versuche, primfaktoren zu ermitteln. man kann ihn eher mit einer intelligenten bruteforce-attacke vergleichen

Finde es gut, dass mein Gedanke aufgegriffen wurde und ein thread zur kryptographie eröffnet wurde.