I tirsdags annoncerede ACM, at Turingprisen for 2015 går til Whitfield Diffie og Martin E. Hellman. De får prisen for noget, vi idag betragter som ganske selvfølgeligt, nemlig “public key kryptering”, kryptering med offentlig nøgle. Kryptering har været kendt i mange former igennem historien, læs for eksempel Simon Singhs Kodebogen.

Men indtil Diffie og Hellman skrev artiklen New directions in Cryptography i 1976, kunne man kun sende hemmelige beskeder til hinanden, hvis man først var blevet enige om en nøgle, altså, hvordan man ville kryptere og dekryptere. Og nøglen skulle være hemmelig. Så man skulle altså først have en form for hemmelig kommunikation, før man kunne udveksle mere hemmelig information. (Ralph Merkle tabte kapløbet om at komme først, men han havde mange af de samme ideer. Desuden har man senere fundet ud af, at det britiske GCHQ havde tilsvarende ideer, men holdt dem hemmelige. Det kan de jo sagtens sige… Historien om kryptering var og er fuld af skæg og blå briller, hemmeligheder, trusler,… og kamp mellem privatliv og mulighed for at kigge “the bad guys” i kortene, Hellman beretter om sit liv i kryptering her.). Både Diffie og Hellman har været meget aktive i kampen for privatliv og også nedrustning. Her er Hellmans blogindlæg, fra i går. Han vil bruge pengene på et nedrustningsinitiativ.

Tilbage til det, de fik Turingprisen for:

Diffie og Hellman forudså i artiklen ovenfor, at man i fremtiden ville have et meget stort behov for hemmelig kommunikation: “The development of computer controlled communication networks promises effortless and inexpensive contact between people or computers on opposite sides of the world, replacing most mail and many excursions with telecommunications. For many applications these contacts must be made secure against both eavesdropping and the injection of illegitimate messages. At present, however, the solution of security problems lags well behind other areas
of communications technology. Contemporary cryptography is unable to meet the requirements, in that its use would impose such severe inconveniences on the system users, as to eliminate many of the benefits of teleprocessing.”

Og det havde de jo ret i. De forudså både behovet for kryptering med henblik på at undgå, andre læser med, og behovet for en digital signatur, så man er sikker på, beskeden kommer fra den, man tror, den er fra. Det ville ikke være smart, hvis vi skulle cykle et sted hen og hente en hemmelig nøgle, før vi kunne handle på nettet. I artiklen foreslår de den løsning, vi bruger idag, nemlig en kryptering, som er asymmetrisk: Man kan ikke udfra den nøgle, der bruges til at kryptere, gætte den, der skal bruges til at dekryptere. Eller rettere: Det skal være meget svært at gætte/regne det ud. De skriver. “In a public key cryptosystem enciphering and deciphering are governed by distinct keys, E and D, such that computing D from E is computationally infeasible (e.g., requiring  instructions). The enciphering key E can thus be publicly disclosed without compromising the deciphering key D. Each user of the network can, therefore, place his enciphering key in a public directory.”

Umiddelbart lyder det jo sært: Kryptering og dekryptering er to sider af samme sag, den ene er den inverse til den anden, så at forestille sig, at man kan kende D uden at kunne finde E på en superhurtig computer, kræver fantasi. Og matematik.

Diffie-Hellman protokol til udveksling af nøgler

I artiklen giver de en protokol  til hemmelig udveksling af nøgler over en offentlig kanal. Alice og Bob vil gerne bestemme sig til en fælles nøgle.

De vælger et (stort) primtal q (dem kan man finde ganske effektivt) og arbejder nu i det endelige legeme GF(q) med q elementer. Eksempel. q=11, som ikke er stort, men alligevel. Der er 11 elementer i GF(11) og vi kan kalde dem 0,1,2,3,…,10. Dem kan man lægge sammen og gange sammen: modulo 11. 1+3=4, som ventet, men 3+8=0 eftersom 11=1×11+0. Og 3×8=2, da 24=2×11+2 og altså giver 2, når vi dividerer med 11 og ser, hvad resten er.

Elementerne 1,2,3,4,5,6,7,8,9,10 har allesammen en multiplikativ invers, en makker man kan gange med og få 1. For eksempel er 10×10=1 modulo 11, da 100=9×11+1, så 10 er sin egen invers. Og 4×3=1, da 12=11+1. Disse 10 elementer udgør den multiplikative gruppe i GF(11)

I Diffie Hellman protokollen skal man desuden bruge et element, som frembringer den multiplikative gruppe. Altså et element, som når man ganger det med sig selv et antal gange, når rundt til alle de 10 elementer (Der er altid  q-1 elementer i den multiplikative gruppe for GF(q))

Lad os prøve med 2: , hvor vi hele tiden tager udregner rest ved division med 11. Så vi nåede gennem alle 10 elementer.

Med 3 går det ikke. og så starter man forfra.

Kun 2, 6, 7 og 8 er frembringere.

Nu tager vi et hemmeligt tal X, primtallet q og frembringeren a og udregner

 modulo q. Og fortæller hele verden, hvad Y er.

Det diskrete logaritmeproblem består i at finde X, når man kender modulo q. For et stort primtal q (og det skal mindst være større end tallet X), er dette problem vanskeligt – der er mange step i en computer.

I eksemplet ovenfor kunne vi kryptere beskeden X=6 med q=11 og a=2. Da er modulo 11. Og det har vi regnet ud ovenfor. Y=9.

Man kan få et indtryk af, at det er svært at udregne eksponenten, altså at finde X udfra Y, når man ser på udregningen  – rækkefølgen 2,4,8,5,10,9,7,3,6,1 indikerer, at det ikke er helt simpelt.

Men hvad skal Alice og Bob gøre? De kan vel heller ikke løse det diskrete logaritmeproblem. Nej, men de gør som følger: De vælger hver sit hemmelige tal n og m. Alice kende n, Bob kender m, hele verden kender q og frembringeren a (her q=11 og a=2)

Alice sender sit tal n krypteret til Bob, så Bob modtager A= modulo 11. Bob sender sit hemmelige tal m krypteret som B= modulo 11.

Nu udregner Alice modulo 11 og Bob udregner modulo 11. De har nu begge tallet modulo 11 = modulo 11, som er deres fælles hemmelige nøgle. De finder altså ikke ud af, hvad den andens hemmelige tal var, men finder en ny fælles hemmelighed.

Eksempel. n=6 og m=8. Da er A=9 og B=3. Udregner man modulo 11, får man 3 og det gør man også, hvis man udregner modulo 11. Tallet 3 er nu den hemmelige nøgle. Og den har ikke kunnet opsnappes på den kanal, Alice og Bob kommunikerer over, da det ville kræve, man kendte enten n og B eller m og A. Og kun Alice hhv Bob kender n og m.

Her er et andet eksempel:

1) Alice og Bob bliver enige om p=23, g=5 (f.eks. ved, at Alice sender de tal til Bob)
2) Alice vælger et hemmeligt tal, a=6, udregner g^a=5^6 og tager rest ved division med p=23. Det giver 8. Det tal sender hun til Bob.
3) Bob vælger sit eget hemmelige tal, b=15, udregner g^b=5^15 og resten ved division med p=23. Det giver 19, og det sender han til Alice.
4) Alice udregner nu 19^a=19^6, tager rest ved division med p=23 og får 2.
5) Bob udregner 8^15, rest ved division med p=23 og får 2.

Nu er 2 deres fælles hemmelige nøgle. Andre kender ikke a og b, så de kan ikke lave trin 4 og 5, selvom de har aflyttet det tidligere.

Man kan også bruge ideen med den diskret logaritme til at lave et public key system, men det er ikke det, der bruges mest idag.

Kryptering med offentlig nøgle.

Senere kom nemlig RSA (Rivest Shamir, Adelman) kryptering, hvor kryptering, E, bruger et produkt af to store primtal, n=pq, mens dekryptering, D,  bruger de to primtal. Udfra n kan man ikke finde p og q uden at bruge rigtig meget tid på en stor computer. Det tror vi da. Vi ved ikke, om der findes en supersmart algoritme, der kan det, men det tror vi ikke. Neil Koblitz skrev i Notices of the AMS om det problematiske forhold mellem teori og praksis i kryptering. Der kan være andre angreb end at gå direkte efter at faktorisere primtal og ofte undervurderer matematikere den praktiske side – hvad nu, hvis nogen kan få fat i de hemmelige tal af en bagvej for eksempel.

Koblittz skriver også om “The Crypto Rump Sessions“, som Diffie har ledet i de første mange år. Det er en del af konferencen Crypto og kræver underholdende indlæg; der er regler for, hvad man må kaste efter foredragsholderne. Et eksempel på et abstract: Over 3 years ago, curtains were invented with provided ‘full-window protection’. No longer could people be observed sleeping in their bedrooms from the street. Now, on behalf of crime victims the world over, we are asking whether these curtains are truly worth the cost. Curtains significantly limit our capacity to investigate these crimes and severely undermines our efficiency in the fight against terrorism. Why should we permit criminal activity to thrive behind drawn curtains, unavailable to law enforcement?….