jul 2009

Night of Work. Das ElGamal-Kryptosystem

Heute war night of work beim CCCHH. Aus der Beschreibung:

Im wesentlichen sagt der Name es: Die Idee ist, eine Nacht lang gemeinsam fokussierte Arbyte zu betreiben. Natuerlich soll der Austausch nicht zu kurz kommen, sonst wuerde man es nicht gemeinsam machen. Am Ende haben idealerweise alle selbst was geschafft und von anderen noch was neues mitgenommen.

Wir haben das zum ersten Mal gemacht und ich muss sagen, es hat sehr schoen geklappt. Eine angenehme Runde von Leuten hat sich eingefunden, um die Nacht durch diverse persoenliche Projekte voranzutreiben. Diensteschreiben fuer das CTF auf der HAR, Software-updates der Club-Webseiten, Compilerbau, P2P-Netzwerktechnik, etc.

Nach der Vorarbeit aus dem vorangegangenen Eintrag gab es fuer mich einen naheliegenden naechsten Schritt: Diffie-Hellman zu ElGamal-Verschluesselung umstricken. Das Beispielprogramm ist sehr einfach, an den Ecken rau und hat seinen Zweck perfekt erfuellt.

Es war erstaunlich cool, die Zahlen per cut&paste hin- und herzuschieben, zu wissen, was sie bedeuten und am Ende den gewuenschten Klartext zu sehen. :)

Das ganze ist im Vergleich zu richtigen Implementationen insofern vereinfacht, als dass Modulus und Erzeuger festgeschrieben sind. Diese werden im allgemeinen als Teil des public keys erzeugt. Sofern mein Wissen mich nicht truegt, haengt die unmittelbare Sicherheit des Systems davon aber nicht ab.

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.