-- title:  Diffie-Hellman in 200 Zeilen C
-- author: pesco
-- date:   2009-07-24 21:30
-- update: 2009-08-07 23:38
-- lang:   de

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[http://kbfr.livejournal.com/] of farbrausch[http://www.farb-rausch.de/]
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[http://de.wikipedia.org/wiki/Diffie-Hellman]
ist natuerlich wirklich ganz einfach. Fuenf Zeilen.
Man braucht nur Exponentiation. Kein Problem. Dafuer gibts ja
Square-and-Multiply[http://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation].
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[http://en.wikipedia.org/wiki/Montgomery_reduction].
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[/log/2009/jul/dh].
Der ganze Spass passiert dort in 'monty.c'[/log/2009/jul/dh/monty.c].
Ein Beispiel-Programm zum Ausprobieren per cut&paste ist
'dh.c'[/log/2009/jul/dh/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? :-)

<</img/2009/telegraphus.jpg>>
Kein Blogpost ohne Bild.
Aufgenommen im {Deutschen Technikmuseum}[http://www.sdtb.de/] 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.