24.7.2009 21:30, pesco
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.