Diffie-Hellman in 200 Zeilen C

Das hat man dann davon. Und dabei hatte alles so harmlos angefangen. Ich stand auf dieser Einweihungsparty herum und trank Bier. Nebenbei betrieb ich die wundervollste Sache neben Sex: Nerdtalk. Krypto-Nerdtalk, mind you. kb of farbrausch fame wollte Datenpakete authentisieren. Hauptsache billig (zu coden). Spieleindustrie shrug. Nach kurzer Eroerterung sagte ich irgendwann:

Da kannst Du doch (wait for it…) einfach Diffie-Hellman machen.

Ah, die Dummheit des Theoretikers. Diffie-Hellman ist natuerlich wirklich ganz einfach. Fuenf Zeilen. Man braucht nur Exponentiation. Kein Problem. Dafuer gibts ja Square-and-Multiply. Easy peasy, solange man multiplizieren kann. …Modulo grosser Primzahlen.

Ach… aeh. Tja, zu diesem Zeitpunkt war schon eine Nacht vergangen. The damage had been done. Erstens kann man sowas nicht auf sich sitzen lassen. Zweitens, und das ist noch gravierender, brennt einem unerbittlich die Frage unter den Naegeln, ob es nicht tatsaechlich ganz einfach ist, wenn man nur weiss, wie's geht. Die gute Nachricht vorweg: Isses. :)

Der Haken ist offensichtlich: Herauszufinden wie es geht, ist nicht so leicht. Einfach normal multiplizieren und danach durch den Modulus dividieren ist in der Groessenordnung von ein paar tausend Bits naemlich schon schmerzhaft. Immerhin besteht die Exponentiation ihrerseits aus ein paar tausend Multiplikationen. Ausserdem ist Division grosser Zahlen nicht mehr huebsch, sondern ein ziemlicher Schandfleck im bis dahin sehr uebersichtlichen, wenn auch noch hypothetischen, angeblich einfachen Code.

Die elegante Antwort lautet Montgomery-Multiplikation. Ein wundervoller mathematischer Trick, mithilfe dessen man sich um die ganzen Divisionen druecken kann. Leider kann mein Blogmarkup noch keine Formeln, deswegen verzichte ich vorerst auf die sexy Details und poste nur den Code. Der ganze Spass passiert dort in monty.c. Ein Beispiel-Programm zum Ausprobieren per cut&paste ist dh.c. Dort findet sich auch der Diffie-Hellman-Fuenfzeiler:

/* diffie-hellman: */
mrand(n, N, a);                   /* generate random number modulo N */
monty_exp(n, N, R, gaR, gR, a);   /* compute g^a */
send(n, gaR);                     /* send g^a to bob */
recv(n, gbR);                     /* receive g^b from bob */
monty_exp(n, N, R, gabR, gbR, a); /* compute (g^a)^b = g^(ab) */

Easy peasy. Right? :-)

Kein Blogpost ohne Bild. Aufgenommen im Deutschen Technikmuseum in Berlin. Er hat einen Telegraphenmasten in der Hand und der Adler haelt Blitze in den Krallen.

PS. Der Code laeuft unter BSD. Linux-Fanbois und Verwandte muessen selber wissen, wo sie ihre Zufallszahlen herkriegen. ;)

Update. Da ich irgendwo ja auch noch eins habe, ist der Code jetzt doch Linux-kompatibel.