64/128/256 - bit (oder mehr) Arithmetik gesucht

[MitjaStachowiak]

Hallo,
ich habe endlich das Datenupload per HTTP-Request (halbwegs) fertig und verwende dort als Verifizierungs-Key einen "Blum-Blum-Shub-Generator" (http://de.wikipedia.org/wiki/Blum-Blum-Shub), also (schematisch) folgenden Algorithmus:

Code: Alles auswählen

var Sequenz : QWord;
 
Sequenz := (Sequenz * Sequenz) mod (p * q);     // p und q sind Primzahlen.

Das ganze habe ich auf meinem 64-Bit-System unkompliziert mit QWord realisiert, das heißt, dass das Produkt p * q < 2^32 sein muss und sich p und q im Bereich 65536 bewegen müssen. Kein superhohes Sicherheitsniveau, aber für meine Zwecke sollte das reichen. Leider ist das Zielsystem nur 32bit und mein Algorithmus liefert dort falsche Ergebnisse. Auf 32bit müssten p und q dann im Bereich 256 sein, was dann doch zu unsicher wäre. Kennt also jemand eine fertige Arithmetik, die mit Übertrag (usw.) auch auf 32-bit-Systemen 64-bit-Operationen durchführen kann?

Wenn ich schon dabei bin, wäre 128, 256, 512 - bit (oder noch mehr) natürlich praktisch
Das ganze müsste +, -, * und mod unterstützen; darf aber auch mehr können...

Ich könnte zwar selbst Hand anlegen, aber das würde sicher Monate dauern und eigentlich sollte es das doch schon geben. Ich habe schon gründlich gesucht, aber nichts gefunden (jedenfalls nichts in Pascal)
Bin für jeden Tipp dankbar.

[Socke]

Das ganze habe ich auf meinem 64-Bit-System unkompliziert mit QWord realisiert, das heißt, dass das Produkt p * q < 2^32 sein muss und sich p und q im Bereich 65536 bewegen müssen. Kein superhohes Sicherheitsniveau, aber für meine Zwecke sollte das reichen. Leider ist das Zielsystem nur 32bit und mein Algorithmus liefert dort falsche Ergebnisse. Auf 32bit müssten p und q dann im Bereich 256 sein, was dann doch zu unsicher wäre. Kennt also jemand eine fertige Arithmetik, die mit Übertrag (usw.) auch auf 32-bit-Systemen 64-bit-Operationen durchführen kann?

Wenn ich schon dabei bin, wäre 128, 256, 512 - bit (oder noch mehr) natürlich praktisch
Das ganze müsste +, -, * und mod unterstützen; darf aber auch mehr können...

Ich verstehe zwar nicht ganz, was du da tust (ich hab mehr mit Datenbanken zu tun), aber mit GNURZ kannst du das wohl realisieren.

[mse]

Das ganze habe ich auf meinem 64-Bit-System unkompliziert mit QWord realisiert, das heißt, dass das Produkt p * q < 2^32 sein muss und sich p und q im Bereich 65536 bewegen müssen. Kein superhohes Sicherheitsniveau, aber für meine Zwecke sollte das reichen. Leider ist das Zielsystem nur 32bit und mein Algorithmus liefert dort falsche Ergebnisse.

32 oder 64 Bit System sollte keinen Unterschied machen, QWord ist QWord. Entweder hast du einen bug in deinem Code oder du hast einen Compilerfehler gefunden der unbedingt gemeldet und repariert werden muss. Bitte mache weitere Untersuchungen.

[MitjaStachowiak]

Danke

Das sieht zwar nicht sooo schnell aus, ist für meine Zwecke aber genau richtig.
Weitere Vorschläge sind natürlich trotzdem willkommen.

Wofür ich das brauche? Also: Das Upload-Projekt, an dem ich gerade arbeite lädt in kurzen Zeitabständen kleinere Datenpakete (Messdaten) per HTTP auf einen Server hoch. Ich habe sozusagen ein eigenes Protokoll auf Basis von HTTP erstellt, das alle nötigen Funktionen anbietet. Dass ich das auch über HTTPS hätte laufen lassen können, ist mir erst eingefallen, nachdem ich das schon soweit fertig hatte. Der Vorteil jetzt besteht zumindest darin, dass ich HTTPS nur zum Verbindungsaufbau brauche (dabei werden unterschiedliche Schlüssel übergeben) und später arbeite ich nur mit Prüfsummen (Was etwas Rechenzeit sparen dürfte). Das Upload muss nicht verschlüsselt sein. Also gebe ich jedem Request eine Zufallszahl mit, deren Sequenz auf Server und Client gleich ist. Ein potentieller Angreifer sollte aufgrund des Zufalls-Algorithmus nicht in der Lage sein, die nächste Zufallszahl zu berechnen. Er könnte höchstens das gesendete Request auf dem Weg verändern. Deswegen gibt es da noch eine Prüfsumme, bei welcher die gesendeten Zeichen in die Zufallszahl mit einfließen (Schema:

Code: Alles auswählen

var s : AnsiString = 'Das Request';
 Sequenz = Startwert;
 for i := 1 to length(s) do Sequenz = ((Sequenz + Byte(s[i]) * (Sequenz + Byte(s[i])) mod (p * q);

) Ich hoffe mal, dass das so sicher ist...
Sollte ein Angreifer die Daten auf dem Weg manipulieren, so hat die Manipulation nur Bestand, solange die Verbindung unterbrochen ist, danach würden diese Daten überschrieben werden...

Jetzt muss ich den Verbindungsaufbau noch mit HTTPS abwickeln. Ich hoffe mal, ich finde dafür Beispielcode; sonst muss ich am Ende RSA noch selber einbauen

[MitjaStachowiak]

32 oder 64 Bit System sollte keinen Unterschied machen, QWord ist QWord. Entweder hast du einen bug in deinem Code oder du hast einen Compilerfehler gefunden der unbedingt gemeldet und repariert werden muss. Bitte mache weitere Untersuchungen.

Oh... Dann macht der Compiler das mit dem Übertrag schon automatisch... Wie gesagt: Die gleiche Exe arbeitet auf meinem System korrekt und auf dem Zielsystem funktioniert vielleicht jedes 70ste Request. Jetzt habe ich nochmal genauer nachgesehen: Es ist nur die Checksummen-Funktion, die unterschiedliche Ergebnisse verursacht. Also könnte es doch ein Fehler meinerseits sein. Werde ich mal untersuchen...

[MitjaStachowiak]

Aha, es gab da Zeichen (Zum Beispiel Leerzeichen) die im Request verschluckt wurden. Das war also der Fehler...
Dafür werde ich noch eine Umformung schreiben.

Aber eigentlich hätte das Upload dann gar nicht klappen dürfen. Mein Checksummen-Algorithmus ist wohl noch nicht das gelbe vom Ei. Ich hab leider noch kein konkretes Beispiel für MD5, oder so, gefunden. Aber wenn die Zahlengröße jetzt keine Einschränkung mehr darstellt, schaffe ich das ja vielleicht noch

[corpsman]

Also wenn ich mit Richtig großen Zahlen Rechnen will, nutze ich das hier : http://home.netsurf.de/wolfgang.ehrhard ... ml#mparith" onclick="window.open(this.href);return false;

[carli]

Hallo,
ich habe endlich das Datenupload per HTTP-Request (halbwegs) fertig und verwende dort als Verifizierungs-Key einen "Blum-Blum-Shub-Generator" (http://de.wikipedia.org/wiki/Blum-Blum-Shub), also (schematisch) folgenden Algorithmus:

Code: Alles auswählen

var Sequenz : QWord;
 
Sequenz := (Sequenz * Sequenz) mod (p * q);     // p und q sind Primzahlen.

Das ganze habe ich auf meinem 64-Bit-System unkompliziert mit QWord realisiert, das heißt, dass das Produkt p * q < 2^32 sein muss und sich p und q im Bereich 65536 bewegen müssen. Kein superhohes Sicherheitsniveau, aber für meine Zwecke sollte das reichen. Leider ist das Zielsystem nur 32bit und mein Algorithmus liefert dort falsche Ergebnisse. Auf 32bit müssten p und q dann im Bereich 256 sein, was dann doch zu unsicher wäre. Kennt also jemand eine fertige Arithmetik, die mit Übertrag (usw.) auch auf 32-bit-Systemen 64-bit-Operationen durchführen kann?

Wenn ich schon dabei bin, wäre 128, 256, 512 - bit (oder noch mehr) natürlich praktisch
Das ganze müsste +, -, * und mod unterstützen; darf aber auch mehr können...

Ich könnte zwar selbst Hand anlegen, aber das würde sicher Monate dauern und eigentlich sollte es das doch schon geben. Ich habe schon gründlich gesucht, aber nichts gefunden (jedenfalls nichts in Pascal)
Bin für jeden Tipp dankbar.

Du brauchst die GNU GMP.
einfach "uses gmp", Rechtsklick auf gmp, Deklaration suchen und die Funktionen anschauen.
Für Tutorials kannst du die C-Beispiele aus dem Internet 1:1 übernehmen.