Diffie-Hellman Algo beschleunigen?

Wutz

Ohne den Quelltext der Bibliothek anzufassen, könntest du ja mal nachschauen, mit welchem Stringformat (hex,dez,bin) sie am besten klarkommt und dieses dann verwenden, da sparst du schon man bei der Input/Output-Konvertierung. malloc/free verwendest du hoffentlich auch nur 1x und nicht etwa innerhalb einer Schleife.

knivil schrieb:

Wie berechnest du a^b mod p? Der naive Ansatz ist ja, erst den Wert tmp fuer a^b auszurechnen und danach tmp mod p zu rechnen. Das geht auch anders, weiss aber gerade nicht wie es heisst.

Das ist eine Funktion der Library, sie dokumentiert es so:

Compute c = (a ** b) mod m.  Uses a standard square-and-multiply
  method with modular reductions at each step.

Wutz schrieb:

Ohne den Quelltext der Bibliothek anzufassen, könntest du ja mal nachschauen, mit welchem Stringformat (hex,dez,bin) sie am besten klarkommt und dieses dann verwenden, da sparst du schon man bei der Input/Output-Konvertierung. malloc/free verwendest du hoffentlich auch nur 1x und nicht etwa innerhalb einer Schleife.

Die Bibliothek arbeitet mit Binärdaten. Jeder Integer ist eine Folge von Bits im Speicher. So wie auch native Integer, nur eben länger

Ich habe gerade mitzählen lassen.
malloc/free ist vermutlich das Problem. Die Library ruft für die eine Berechnung a^b mod c 9095(!!!) mal malloc auf. So ein Mist!

Danke Jungs, welch Library empfiehlt ihr mir?

Wutz

Ich hatte mal Quellen zusammengetragen, inwieweit diese performant sind, musst du wohl selbst erforschen:

http://www.c-plusplus.net/forum/viewtopic-var-t-is-272479-and-postdays-is-0-and-postorder-is-asc-and-start-is-0.html

Ich meine auch nicht, wieviel malloc/free die Bibliothek intern aufruft, sondern wieoft DU in deinem aufrufenden Kontext malloc/free aufrufst.
Ich weiß auch, was Integer sind und wie man damit rechnet, ich meine dass DU deinen aufrufenden Kontext für die Bibliothekfunktionen optimal anpassen solltest, also z.B. kann es Vorteile bringen, je nachdem, wie man die Funktionen verwendet:

/* deine Schleife */
for(i=0;i<1000000;++i)
  lib_funktion_exp( "65535", "65535", 10, outputString );
for(i=0;i<1000000;++i)
  lib_funktion_exp( "FFFF", "FFFF", 16, outputString );
for(i=0;i<1000000;++i)
  lib_funktion_exp( "1111111111111111", "1111111111111111", 2, outputString );

Wutz schrieb:

http://www.c-plusplus.net/forum/viewtopic-var-t-is-272479-and-postdays-is-0-and-postorder-is-asc-and-start-is-0.html

Dankeschön!

Wutz schrieb:

Ich meine auch nicht, wieviel malloc/free die Bibliothek intern aufruft, sondern wieoft DU in deinem aufrufenden Kontext malloc/free aufrufst.
Ich weiß auch, was Integer sind und wie man damit rechnet, ich meine dass DU deinen aufrufenden Kontext für die Bibliothekfunktionen optimal anpassen solltest, also z.B. kann es Vorteile bringen, je nachdem, wie man die Funktionen verwendet:

Die Library hat eine eigene "modpow"-Funktion, die extrem oft malloc/free aufruft. Ich habe keinen Einfluß darauf. Ich selbst benutze malloc/free in dem Kontext überhaupt nicht.

Nun bin ich gerade dabei "GMP" auf mein System anzupassen. Ich will hoffen, daß ich damit unter 3 Sekunden komme, ansonsten muß ich einen schnelleren Controller nehmen.

C kann schon manchmal richtig kacke sein.

O-lli schrieb:

C kann schon manchmal richtig kacke sein.

Ich programmiere sonst am liebsten in Java, aber auf Mikrokontrollern gestaltet sich dies recht prekär. Ich könnte Assembler benutzen; das wäre aber noch schwieriger.

Hiermit beschäftige ich mich: http://en.wikipedia.org/wiki/Wi-Fi_Protected_Setup
Und dafür brauche ich das Diffie-Hellman-Protokoll.

rage_quit

Cryptor schrieb:

O-lli schrieb:

C kann schon manchmal richtig kacke sein.

Ich programmiere sonst am liebsten in Java, aber auf Mikrokontrollern gestaltet sich dies recht prekär. Ich könnte Assembler benutzen; das wäre aber noch schwieriger.

Hiermit beschäftige ich mich: http://en.wikipedia.org/wiki/Wi-Fi_Protected_Setup
Und dafür brauche ich das Diffie-Hellman-Protokoll.

du könntest es auch einfach bleiben lassen, wenn du es nicht gebacken bekommst!

rage_quit schrieb:

du könntest es auch einfach bleiben lassen, wenn du es nicht gebacken bekommst!

Wieso kommst Du darauf, dß ich es nicht hinkriegen würde?

falls du noch eine lib brauchst: --> http://philzimmermann.com/EN/bnlib/index.html

der code schafft 'expmod' mit der 1536-bit primzahl aus RFC3526, auf einem arm7, mit 72mhz cpu-clock, in ~3 sekunden und braucht dabei etwa 6kb RAM. (funktion: lbnExpMod_32)

/*
* Perform modular exponentiation, as fast as possible! This uses
* Montgomery reduction, optimized squaring, and windowed exponentiation.

schneller ist IMHO nur die speicherintensive 'montgomery ladder'.