Når du logger på en hjemmeside, hvor du har en brugerkonto, opretter din browser en »sikret forbindelse«, men hvordan fungerer sådan egentligt? (Foto: Colourbox)

Dette sker f.eks., når du køber noget online, eller når du logger på en hjemmeside, hvor du har en brugerkonto. I mange browsere kan du genkende en sikret forbindelse ved en lille hængelås, der vises i browserens bund. Når forbindelsen er sikret, så bliver al data krypteret. Dette betyder, at de er kodet, således at kun du og din kommunikationspartner (typisk webserveren) kan læse de beskeder, der sendes frem og tilbage. Krypteringen er kun mulig, hvis du deler en hemmelighed med din partner, som ingen andre kender til. I kryptologien - videnskaben, som beskæftiger sig med hemmelige koder - kaldes en sådan hemmelighed en nøgle. Men hvordan kan det være, at du (eller din browser) deler en fælles hemmelighed med en webserver, som du aldrig før har været i kontakt med? Ens browser kunne måske have en nøgle til alle webservere? Det har den ikke, og det vil heller ikke være en god idé - hvis browserproducenten bygger nøglerne ind, så vil den jo dermed kende dem, og de vil derfor ikke længere være hemmelige. Her har vi åbenbart et problem: For at være i stand til at sende hinanden hemmelige beskeder skal man først udveksle en hemmelig nøgle, dvs. sende hinanden en hemmelig besked. Dette paradoks virker uløseligt, men i denne artikel skal vi se på, hvordan problemet med nøgleudveksling løses. Løsningsidéen Kryptologi er næsten lige så gammel som håndskriften, og i årtusinder har man løst problemet med at kunne dele en fælles hemmelighed ved at skrive nøglen på et stykke papir (eller en papyrus eller en tavle) og aflevere koden personligt eller med et bud. Med internettet er det tydeligt, at nedskrevne nøgler ikke fungerer som løsning for vores problem - du modtager jo ikke et sådant stykke papir med din computer, og du har heller ikke tastet nøglen ind i din computer. Selvfølgelig kan computeren heller ikke få nøglen direkte fra nettet, fordi så kunne andre (som eksempelvis dit telefonselskab) jo også se nøglen. Så hvordan er nøglen kommet ind i din computer? For mere end 30 år siden, da internettet ikke engang var opfundet endnu, stillede de to amerikanske kryptografer Whitfield Diffie og Martin Hellman sig det samme spørgsmål. De vidste, hvor store problemer regeringer, militær og virksomheder havde med nøgleudvekslingen, og de forudså endda en tid, hvor også privatpersoner ville få brug for kryptering. Løsningen, som Diffie og Hellman fandt på, bygger på den iagttagelse, at det ikke er muligt at basere nøgleudvekslingen på kun en enkelt besked. Hvis senderen (som vi fremover kalder Alice) sender en nøglebesked til modtageren (som vi kalder Bob), og denne besked indeholder nogle nøgleinformationer, så kan indholdet kun være selve nøglen, og dermed vil en potentiel angriber (som vi kalder Eva) også kende den. Der skal altså mindst to beskeder til for at udveksle en nøgle på en sikker måde. Eksempel på en nøgleudveksling Alice og Bob bliver enige om et offentligt heltal, som de kalder g. Eva må godt kende g, dvs., at de kan sende det åbent over nettet. Alice vælger et hemmeligt heltal, som hun kalder a. Hun beregner va = g ・ a og sender resultatet til Bob. Bob vælger også et hemmeligt heltal, som han kalder b. Han beregner vb = g ・ b og sender resultatet til Alice. Nu kan Alice beregne den fælles nøgle som va ・ b, og Bob kan beregne den som vb ・ a. Som det viser sig, er resultatet det samme, og Alice og Bob har dermed samme nøgle. Metoden er uden tvivl lidt forvirrende for Eva, men det er ikke det samme som at være sikker. Hvis Eva kender g, så kan hun beregne a = va / g. Hun kender også vb, fordi Bob har sendt det over nettet, og kan dermed bestemme nøglen på samme måde som Bob, dvs. som vb · a. Med andre ord: Vores første idé var god, men ikke god nok. Modulo-regning Vi forsøger nu at finde en bedre metode og bibeholder strukturen fra vores første eksempel. Formålet er dog at finde en bedre funktion end multiplikation - en funktion, som knytter to tal sammen på en sådan måde, at Eva ikke kan skille dem ad igen. For at forstå løsningen, som Diffie og Hellman brugte, skal vi først forstå den såkaldte modulo-funktion. Hvis x og y er hele tal (y ≠ 0), og vi skriver x mod y, så er resultatet divisionsresten, når x deles med y. For eksempel er 47 mod 15 = 2, fordi 47 = 3 ・ 15 + 2. Et kendt eksempel for modulo-regning i hverdagen er uret. Vores ure har kun tolv timer. Hvis klokken er 9 nu, og der går yderligere 6 timer, så viser uret klokken (9+6) mod 12, altså klokken 3. En lignende regel kan bruges, når man regner i måneder. Hvis det er den 20. januar i dag, og vi skal mødes om 3 uger, så er det jo egentlig den 41. januar. Men siden januar kun har 31 dage, regner vi 41 mod 31 for at finde ud af, at det svarer til den 10. februar. Når først man har vænnet sig til det, er modulo-regning ikke vanskelig at bruge. En vigtig regneregel er, at man ved brug af addition, subtraktion og multiplikation altid må reducere resultatet undervejs. Eksempel: Selvfølgelig kan man beregne (27 · 74) mod 7 ved først at danne 27 · 74 = 1998 og derefter reducere mod 7. Det kræver dog en lommeregner eller i det mindste gode regnefærdigheder. I stedet kan man nøjes med først at beregne 27 mod 7 = 6 og 74 mod 7 = 4, og derefter beregne (6 · 4) mod 7 = 24 mod 7 = 3. Modulær eksponentiering Nu er vi parat til at udvikle den funktion, som Diffie og Hellman brugte til at løse nøgleudvekslingsproblemet. Den ligner en ganske almindelig eksponentiering, som vi kender den fra matematisk analyse, hvor vi skriver gx, når g skal ganges x gange med sig selv. Men her bruger vi en modulo-operation til sidst, dvs. gx mod n. Denne operation kalder vi modulær eksponentiering. Denne funktion har den sære egenskab, at den for visse valg af g og n »springer« gennem samtlige tal i området 1,...,n-1. Hvis vi f.eks. tager g = 3 og n = 7, så får vi følgende tabel: Læg mærke til, at f.eks. 34 mod 7 kan beregnes som 33 · 3 mod 7 = 6 · 3 mod 7 = 4; det er ikke nødvendigt først at regne hele 34 ud. Bemærk også, at følgen starter forfra igen efter 35, dvs. 36 = 30 = 1, 37 = 31 = 3 osv. Hvis funktionen gx mod n gennemløber samtlige værdier mellem 1 og n-1, så hedder g en generator for {1,..,n-1}. I talteorien (en af de mest teoretiske matematiske discipliner) findes der en del teori om, hvordan man finder en sådan generator, men det behøver vi ikke at interessere os for her. Vi kan nøjes med at vide, at hvis n er et primtal, så findes der altid mindst en generator for {1,..,n-1}. Diffie-Hellman nøgleudveksling Hvorfor er det nu vigtigt? Vi har lært, at hvis n er et primtal, og g er en generator for {1,..,n-1}, så gennemløber funktionen gx mod n samtlige værdier i {1,..,n-1}. Derudover kan vi se i tabellen fra opgave 8, at funktionen »springer« på en meget uforudsigelig måde fra en værdi til den næste. Uden tabellen ville du ikke umiddelbart være i stand til at finde ud af, hvilket x du skal vælge for at få 3x mod 7 = 6. Vi siger derfor, at funktionen er vanskelig at invertere. Og dette er nøjagtigt, hvad vi har brug for. Vi ændrer nu vores protokoludkast, således at det bruger modulær eksponentiering i stedet for multiplikation: Alice og Bob bliver enige om et offentligt primtal n og en tilsvarende generator g. Angriberen må godt kende n og g, dvs. at de kan sende dem åbent over nettet. Alice vælger et hemmeligt heltal a. Hun beregner va = ga mod n og sender resultatet til Bob. Bob vælger også et hemmeligt heltal b. Han beregner vb = gb mod n og sender resultatet til Alice. Nu kan Bob beregne den fælles nøgle som (va)b mod n, og Alice kan beregne den som (vb)a mod n. Det viser sig, at resultatet er det samme, og Alice og Bob deler dermed en nøgle. I modsætning til vores første udkast kan Eva ikke beregne a ud fra va, og hun kan heller ikke beregne b ud fra vb. Hvis tallene er store nok, så kender man ingen effektiv metode til at skille va eller vb ad igen - og dette på trods af mere end 30 års intensiv forskning! Ulempen ved metoden er dog, at tallene skal være temmelig store for at gøre løsningen sikker i praksis. Primtallet n (og dermed også nøglen) skal i dag have mindst 1024 bit (helst 2048), hvilket svarer til mellem 307 og 614 cifre! Opfindelsens betydning Hvordan kan vi nu bruge denne matematiske metode i praksis? Husk at Alice kan være en hvilken som helst afsender, og Bob kan være en hvilken som helst modtager. At vi har givet dem navne betyder ikke, at de behøver være mennesker. Hvis vi husker vores eksempel fra artiklens begyndelse, så kan Alice i virkeligheden være en webserver (f.eks. for en bank), og Bob kan vare en internetbrugers computer (f.eks. din). Så når du kontakter en sikret hjemmeside - som kendes ved forkortelsen »https« i adressen - bruger webserveren og din computer ovenstående løsning for at udveksle en nøgle. Derefter kan kommunikationen foregå uforstyrret. Faktisk forudså Whitfield Diffie allerede i 1970'erne det, som senere blev kendt som »Internet«. Hans motivation for at opfinde ovenstående løsning var at give almindelige mennesker adgang til beskyttet kommunikation, som hidtil kun var tilgængeligt for militær og efterretningstjenester. Denne idé blev taget imod med stor begejstring, og snart var der flere og flere forskere, som begyndte at interessere sig for emnet. Politiske ledere og myndighederne i mange lande var dog mindre begejstrede for udspredelsen af denne teknologi, som selvfølgelig også kan anvendes til at sløre ulovlige aktiviteter. Men udviklingen lod sig ikke bremse, og i dag er kryptologi et meget aktivt forskningsområde, der fortsat bidrager til at sikre kommunikation i hverdagen. Hver gang du bruger din mobiltelefon, betaler med dankort, logger på en sikret hjemmeside eller åbner en bildør med fjernstyring, er kryptologi i spil. Diffies og Hellmans opfindelse havde også indvirkning på matematikken selv. Som nævnt stammer deres metode fra talteorien, et matematisk område som inden da blev anset for at være helt uden nogen form for praktisk nytte. Talteoretikerne var faktisk stolte af, at deres fag besad den rene teoris basale skønhed, der ikke kunne misbruges til verdslige formål. Nu viste det sig pludseligt, at dette ikke længere var tilfældet. Talteoretikernes videnskab blev anvendt i den virkelige verden, og det sidste fæstningsværk af den rene, ubesmittede matematik var nu faldet. Lavet i samarbejde med DTU Matematik

Dette sker f.eks., når du køber noget online, eller når du logger på en hjemmeside, hvor du har en brugerkonto. I mange browsere kan du genkende en sikret forbindelse ved en lille hængelås, der vises i browserens bund. Når forbindelsen er sikret, så bliver al data krypteret. Dette betyder, at de er kodet, således at kun du og din kommunikationspartner (typisk webserveren) kan læse de beskeder, der sendes frem og tilbage. Krypteringen er kun mulig, hvis du deler en hemmelighed med din partner, som ingen andre kender til. I kryptologien - videnskaben, som beskæftiger sig med hemmelige koder - kaldes en sådan hemmelighed en nøgle. Men hvordan kan det være, at du (eller din browser) deler en fælles hemmelighed med en webserver, som du aldrig før har været i kontakt med? Ens browser kunne måske have en nøgle til alle webservere? Det har den ikke, og det vil heller ikke være en god idé - hvis browserproducenten bygger nøglerne ind, så vil den jo dermed kende dem, og de vil derfor ikke længere være hemmelige. Her har vi åbenbart et problem: For at være i stand til at sende hinanden hemmelige beskeder skal man først udveksle en hemmelig nøgle, dvs. sende hinanden en hemmelig besked. Dette paradoks virker uløseligt, men i denne artikel skal vi se på, hvordan problemet med nøgleudveksling løses. Løsningsidéen Kryptologi er næsten lige så gammel som håndskriften, og i årtusinder har man løst problemet med at kunne dele en fælles hemmelighed ved at skrive nøglen på et stykke papir (eller en papyrus eller en tavle) og aflevere koden personligt eller med et bud. Med internettet er det tydeligt, at nedskrevne nøgler ikke fungerer som løsning for vores problem - du modtager jo ikke et sådant stykke papir med din computer, og du har heller ikke tastet nøglen ind i din computer. Selvfølgelig kan computeren heller ikke få nøglen direkte fra nettet, fordi så kunne andre (som eksempelvis dit telefonselskab) jo også se nøglen. Så hvordan er nøglen kommet ind i din computer? For mere end 30 år siden, da internettet ikke engang var opfundet endnu, stillede de to amerikanske kryptografer Whitfield Diffie og Martin Hellman sig det samme spørgsmål. De vidste, hvor store problemer regeringer, militær og virksomheder havde med nøgleudvekslingen, og de forudså endda en tid, hvor også privatpersoner ville få brug for kryptering. Løsningen, som Diffie og Hellman fandt på, bygger på den iagttagelse, at det ikke er muligt at basere nøgleudvekslingen på kun en enkelt besked. Hvis senderen (som vi fremover kalder Alice) sender en nøglebesked til modtageren (som vi kalder Bob), og denne besked indeholder nogle nøgleinformationer, så kan indholdet kun være selve nøglen, og dermed vil en potentiel angriber (som vi kalder Eva) også kende den. Der skal altså mindst to beskeder til for at udveksle en nøgle på en sikker måde. Eksempel på en nøgleudveksling Alice og Bob bliver enige om et offentligt heltal, som de kalder g. Eva må godt kende g, dvs., at de kan sende det åbent over nettet. Alice vælger et hemmeligt heltal, som hun kalder a. Hun beregner va = g ・ a og sender resultatet til Bob. Bob vælger også et hemmeligt heltal, som han kalder b. Han beregner vb = g ・ b og sender resultatet til Alice. Nu kan Alice beregne den fælles nøgle som va ・ b, og Bob kan beregne den som vb ・ a. Som det viser sig, er resultatet det samme, og Alice og Bob har dermed samme nøgle. Metoden er uden tvivl lidt forvirrende for Eva, men det er ikke det samme som at være sikker. Hvis Eva kender g, så kan hun beregne a = va / g. Hun kender også vb, fordi Bob har sendt det over nettet, og kan dermed bestemme nøglen på samme måde som Bob, dvs. som vb · a. Med andre ord: Vores første idé var god, men ikke god nok. Modulo-regning Vi forsøger nu at finde en bedre metode og bibeholder strukturen fra vores første eksempel. Formålet er dog at finde en bedre funktion end multiplikation - en funktion, som knytter to tal sammen på en sådan måde, at Eva ikke kan skille dem ad igen. For at forstå løsningen, som Diffie og Hellman brugte, skal vi først forstå den såkaldte modulo-funktion. Hvis x og y er hele tal (y ≠ 0), og vi skriver x mod y, så er resultatet divisionsresten, når x deles med y. For eksempel er 47 mod 15 = 2, fordi 47 = 3 ・ 15 + 2. Et kendt eksempel for modulo-regning i hverdagen er uret. Vores ure har kun tolv timer. Hvis klokken er 9 nu, og der går yderligere 6 timer, så viser uret klokken (9+6) mod 12, altså klokken 3. En lignende regel kan bruges, når man regner i måneder. Hvis det er den 20. januar i dag, og vi skal mødes om 3 uger, så er det jo egentlig den 41. januar. Men siden januar kun har 31 dage, regner vi 41 mod 31 for at finde ud af, at det svarer til den 10. februar. Når først man har vænnet sig til det, er modulo-regning ikke vanskelig at bruge. En vigtig regneregel er, at man ved brug af addition, subtraktion og multiplikation altid må reducere resultatet undervejs. Eksempel: Selvfølgelig kan man beregne (27 · 74) mod 7 ved først at danne 27 · 74 = 1998 og derefter reducere mod 7. Det kræver dog en lommeregner eller i det mindste gode regnefærdigheder. I stedet kan man nøjes med først at beregne 27 mod 7 = 6 og 74 mod 7 = 4, og derefter beregne (6 · 4) mod 7 = 24 mod 7 = 3. Modulær eksponentiering Nu er vi parat til at udvikle den funktion, som Diffie og Hellman brugte til at løse nøgleudvekslingsproblemet. Den ligner en ganske almindelig eksponentiering, som vi kender den fra matematisk analyse, hvor vi skriver gx, når g skal ganges x gange med sig selv. Men her bruger vi en modulo-operation til sidst, dvs. gx mod n. Denne operation kalder vi modulær eksponentiering. Denne funktion har den sære egenskab, at den for visse valg af g og n »springer« gennem samtlige tal i området 1,...,n-1. Hvis vi f.eks. tager g = 3 og n = 7, så får vi følgende tabel: Læg mærke til, at f.eks. 34 mod 7 kan beregnes som 33 · 3 mod 7 = 6 · 3 mod 7 = 4; det er ikke nødvendigt først at regne hele 34 ud. Bemærk også, at følgen starter forfra igen efter 35, dvs. 36 = 30 = 1, 37 = 31 = 3 osv. Hvis funktionen gx mod n gennemløber samtlige værdier mellem 1 og n-1, så hedder g en generator for {1,..,n-1}. I talteorien (en af de mest teoretiske matematiske discipliner) findes der en del teori om, hvordan man finder en sådan generator, men det behøver vi ikke at interessere os for her. Vi kan nøjes med at vide, at hvis n er et primtal, så findes der altid mindst en generator for {1,..,n-1}. Diffie-Hellman nøgleudveksling Hvorfor er det nu vigtigt? Vi har lært, at hvis n er et primtal, og g er en generator for {1,..,n-1}, så gennemløber funktionen gx mod n samtlige værdier i {1,..,n-1}. Derudover kan vi se i tabellen fra opgave 8, at funktionen »springer« på en meget uforudsigelig måde fra en værdi til den næste. Uden tabellen ville du ikke umiddelbart være i stand til at finde ud af, hvilket x du skal vælge for at få 3x mod 7 = 6. Vi siger derfor, at funktionen er vanskelig at invertere. Og dette er nøjagtigt, hvad vi har brug for. Vi ændrer nu vores protokoludkast, således at det bruger modulær eksponentiering i stedet for multiplikation: Alice og Bob bliver enige om et offentligt primtal n og en tilsvarende generator g. Angriberen må godt kende n og g, dvs. at de kan sende dem åbent over nettet. Alice vælger et hemmeligt heltal a. Hun beregner va = ga mod n og sender resultatet til Bob. Bob vælger også et hemmeligt heltal b. Han beregner vb = gb mod n og sender resultatet til Alice. Nu kan Bob beregne den fælles nøgle som (va)b mod n, og Alice kan beregne den som (vb)a mod n. Det viser sig, at resultatet er det samme, og Alice og Bob deler dermed en nøgle. I modsætning til vores første udkast kan Eva ikke beregne a ud fra va, og hun kan heller ikke beregne b ud fra vb. Hvis tallene er store nok, så kender man ingen effektiv metode til at skille va eller vb ad igen - og dette på trods af mere end 30 års intensiv forskning! Ulempen ved metoden er dog, at tallene skal være temmelig store for at gøre løsningen sikker i praksis. Primtallet n (og dermed også nøglen) skal i dag have mindst 1024 bit (helst 2048), hvilket svarer til mellem 307 og 614 cifre! Opfindelsens betydning Hvordan kan vi nu bruge denne matematiske metode i praksis? Husk at Alice kan være en hvilken som helst afsender, og Bob kan være en hvilken som helst modtager. At vi har givet dem navne betyder ikke, at de behøver være mennesker. Hvis vi husker vores eksempel fra artiklens begyndelse, så kan Alice i virkeligheden være en webserver (f.eks. for en bank), og Bob kan vare en internetbrugers computer (f.eks. din). Så når du kontakter en sikret hjemmeside - som kendes ved forkortelsen »https« i adressen - bruger webserveren og din computer ovenstående løsning for at udveksle en nøgle. Derefter kan kommunikationen foregå uforstyrret. Faktisk forudså Whitfield Diffie allerede i 1970'erne det, som senere blev kendt som »Internet«. Hans motivation for at opfinde ovenstående løsning var at give almindelige mennesker adgang til beskyttet kommunikation, som hidtil kun var tilgængeligt for militær og efterretningstjenester. Denne idé blev taget imod med stor begejstring, og snart var der flere og flere forskere, som begyndte at interessere sig for emnet. Politiske ledere og myndighederne i mange lande var dog mindre begejstrede for udspredelsen af denne teknologi, som selvfølgelig også kan anvendes til at sløre ulovlige aktiviteter. Men udviklingen lod sig ikke bremse, og i dag er kryptologi et meget aktivt forskningsområde, der fortsat bidrager til at sikre kommunikation i hverdagen. Hver gang du bruger din mobiltelefon, betaler med dankort, logger på en sikret hjemmeside eller åbner en bildør med fjernstyring, er kryptologi i spil. Diffies og Hellmans opfindelse havde også indvirkning på matematikken selv. Som nævnt stammer deres metode fra talteorien, et matematisk område som inden da blev anset for at være helt uden nogen form for praktisk nytte. Talteoretikerne var faktisk stolte af, at deres fag besad den rene teoris basale skønhed, der ikke kunne misbruges til verdslige formål. Nu viste det sig pludseligt, at dette ikke længere var tilfældet. Talteoretikernes videnskab blev anvendt i den virkelige verden, og det sidste fæstningsværk af den rene, ubesmittede matematik var nu faldet. Lavet i samarbejde med DTU Matematik

Dette sker f.eks., når du køber noget online, eller når du logger på en hjemmeside, hvor du har en brugerkonto. I mange browsere kan du genkende en sikret forbindelse ved en lille hængelås, der vises i browserens bund. Når forbindelsen er sikret, så bliver al data krypteret. Dette betyder, at de er kodet, således at kun du og din kommunikationspartner (typisk webserveren) kan læse de beskeder, der sendes frem og tilbage. Krypteringen er kun mulig, hvis du deler en hemmelighed med din partner, som ingen andre kender til. I kryptologien - videnskaben, som beskæftiger sig med hemmelige koder - kaldes en sådan hemmelighed en nøgle. Men hvordan kan det være, at du (eller din browser) deler en fælles hemmelighed med en webserver, som du aldrig før har været i kontakt med? Ens browser kunne måske have en nøgle til alle webservere? Det har den ikke, og det vil heller ikke være en god idé - hvis browserproducenten bygger nøglerne ind, så vil den jo dermed kende dem, og de vil derfor ikke længere være hemmelige. Her har vi åbenbart et problem: For at være i stand til at sende hinanden hemmelige beskeder skal man først udveksle en hemmelig nøgle, dvs. sende hinanden en hemmelig besked. Dette paradoks virker uløseligt, men i denne artikel skal vi se på, hvordan problemet med nøgleudveksling løses. Løsningsidéen Kryptologi er næsten lige så gammel som håndskriften, og i årtusinder har man løst problemet med at kunne dele en fælles hemmelighed ved at skrive nøglen på et stykke papir (eller en papyrus eller en tavle) og aflevere koden personligt eller med et bud. Med internettet er det tydeligt, at nedskrevne nøgler ikke fungerer som løsning for vores problem - du modtager jo ikke et sådant stykke papir med din computer, og du har heller ikke tastet nøglen ind i din computer. Selvfølgelig kan computeren heller ikke få nøglen direkte fra nettet, fordi så kunne andre (som eksempelvis dit telefonselskab) jo også se nøglen. Så hvordan er nøglen kommet ind i din computer? For mere end 30 år siden, da internettet ikke engang var opfundet endnu, stillede de to amerikanske kryptografer Whitfield Diffie og Martin Hellman sig det samme spørgsmål. De vidste, hvor store problemer regeringer, militær og virksomheder havde med nøgleudvekslingen, og de forudså endda en tid, hvor også privatpersoner ville få brug for kryptering. Løsningen, som Diffie og Hellman fandt på, bygger på den iagttagelse, at det ikke er muligt at basere nøgleudvekslingen på kun en enkelt besked. Hvis senderen (som vi fremover kalder Alice) sender en nøglebesked til modtageren (som vi kalder Bob), og denne besked indeholder nogle nøgleinformationer, så kan indholdet kun være selve nøglen, og dermed vil en potentiel angriber (som vi kalder Eva) også kende den. Der skal altså mindst to beskeder til for at udveksle en nøgle på en sikker måde. Eksempel på en nøgleudveksling Alice og Bob bliver enige om et offentligt heltal, som de kalder g. Eva må godt kende g, dvs., at de kan sende det åbent over nettet. Alice vælger et hemmeligt heltal, som hun kalder a. Hun beregner va = g ・ a og sender resultatet til Bob. Bob vælger også et hemmeligt heltal, som han kalder b. Han beregner vb = g ・ b og sender resultatet til Alice. Nu kan Alice beregne den fælles nøgle som va ・ b, og Bob kan beregne den som vb ・ a. Som det viser sig, er resultatet det samme, og Alice og Bob har dermed samme nøgle. Metoden er uden tvivl lidt forvirrende for Eva, men det er ikke det samme som at være sikker. Hvis Eva kender g, så kan hun beregne a = va / g. Hun kender også vb, fordi Bob har sendt det over nettet, og kan dermed bestemme nøglen på samme måde som Bob, dvs. som vb · a. Med andre ord: Vores første idé var god, men ikke god nok. Modulo-regning Vi forsøger nu at finde en bedre metode og bibeholder strukturen fra vores første eksempel. Formålet er dog at finde en bedre funktion end multiplikation - en funktion, som knytter to tal sammen på en sådan måde, at Eva ikke kan skille dem ad igen. For at forstå løsningen, som Diffie og Hellman brugte, skal vi først forstå den såkaldte modulo-funktion. Hvis x og y er hele tal (y ≠ 0), og vi skriver x mod y, så er resultatet divisionsresten, når x deles med y. For eksempel er 47 mod 15 = 2, fordi 47 = 3 ・ 15 + 2. Et kendt eksempel for modulo-regning i hverdagen er uret. Vores ure har kun tolv timer. Hvis klokken er 9 nu, og der går yderligere 6 timer, så viser uret klokken (9+6) mod 12, altså klokken 3. En lignende regel kan bruges, når man regner i måneder. Hvis det er den 20. januar i dag, og vi skal mødes om 3 uger, så er det jo egentlig den 41. januar. Men siden januar kun har 31 dage, regner vi 41 mod 31 for at finde ud af, at det svarer til den 10. februar. Når først man har vænnet sig til det, er modulo-regning ikke vanskelig at bruge. En vigtig regneregel er, at man ved brug af addition, subtraktion og multiplikation altid må reducere resultatet undervejs. Eksempel: Selvfølgelig kan man beregne (27 · 74) mod 7 ved først at danne 27 · 74 = 1998 og derefter reducere mod 7. Det kræver dog en lommeregner eller i det mindste gode regnefærdigheder. I stedet kan man nøjes med først at beregne 27 mod 7 = 6 og 74 mod 7 = 4, og derefter beregne (6 · 4) mod 7 = 24 mod 7 = 3. Modulær eksponentiering Nu er vi parat til at udvikle den funktion, som Diffie og Hellman brugte til at løse nøgleudvekslingsproblemet. Den ligner en ganske almindelig eksponentiering, som vi kender den fra matematisk analyse, hvor vi skriver gx, når g skal ganges x gange med sig selv. Men her bruger vi en modulo-operation til sidst, dvs. gx mod n. Denne operation kalder vi modulær eksponentiering. Denne funktion har den sære egenskab, at den for visse valg af g og n »springer« gennem samtlige tal i området 1,...,n-1. Hvis vi f.eks. tager g = 3 og n = 7, så får vi følgende tabel: Læg mærke til, at f.eks. 34 mod 7 kan beregnes som 33 · 3 mod 7 = 6 · 3 mod 7 = 4; det er ikke nødvendigt først at regne hele 34 ud. Bemærk også, at følgen starter forfra igen efter 35, dvs. 36 = 30 = 1, 37 = 31 = 3 osv. Hvis funktionen gx mod n gennemløber samtlige værdier mellem 1 og n-1, så hedder g en generator for {1,..,n-1}. I talteorien (en af de mest teoretiske matematiske discipliner) findes der en del teori om, hvordan man finder en sådan generator, men det behøver vi ikke at interessere os for her. Vi kan nøjes med at vide, at hvis n er et primtal, så findes der altid mindst en generator for {1,..,n-1}. Diffie-Hellman nøgleudveksling Hvorfor er det nu vigtigt? Vi har lært, at hvis n er et primtal, og g er en generator for {1,..,n-1}, så gennemløber funktionen gx mod n samtlige værdier i {1,..,n-1}. Derudover kan vi se i tabellen fra opgave 8, at funktionen »springer« på en meget uforudsigelig måde fra en værdi til den næste. Uden tabellen ville du ikke umiddelbart være i stand til at finde ud af, hvilket x du skal vælge for at få 3x mod 7 = 6. Vi siger derfor, at funktionen er vanskelig at invertere. Og dette er nøjagtigt, hvad vi har brug for. Vi ændrer nu vores protokoludkast, således at det bruger modulær eksponentiering i stedet for multiplikation: Alice og Bob bliver enige om et offentligt primtal n og en tilsvarende generator g. Angriberen må godt kende n og g, dvs. at de kan sende dem åbent over nettet. Alice vælger et hemmeligt heltal a. Hun beregner va = ga mod n og sender resultatet til Bob. Bob vælger også et hemmeligt heltal b. Han beregner vb = gb mod n og sender resultatet til Alice. Nu kan Bob beregne den fælles nøgle som (va)b mod n, og Alice kan beregne den som (vb)a mod n. Det viser sig, at resultatet er det samme, og Alice og Bob deler dermed en nøgle. I modsætning til vores første udkast kan Eva ikke beregne a ud fra va, og hun kan heller ikke beregne b ud fra vb. Hvis tallene er store nok, så kender man ingen effektiv metode til at skille va eller vb ad igen - og dette på trods af mere end 30 års intensiv forskning! Ulempen ved metoden er dog, at tallene skal være temmelig store for at gøre løsningen sikker i praksis. Primtallet n (og dermed også nøglen) skal i dag have mindst 1024 bit (helst 2048), hvilket svarer til mellem 307 og 614 cifre! Opfindelsens betydning Hvordan kan vi nu bruge denne matematiske metode i praksis? Husk at Alice kan være en hvilken som helst afsender, og Bob kan være en hvilken som helst modtager. At vi har givet dem navne betyder ikke, at de behøver være mennesker. Hvis vi husker vores eksempel fra artiklens begyndelse, så kan Alice i virkeligheden være en webserver (f.eks. for en bank), og Bob kan vare en internetbrugers computer (f.eks. din). Så når du kontakter en sikret hjemmeside - som kendes ved forkortelsen »https« i adressen - bruger webserveren og din computer ovenstående løsning for at udveksle en nøgle. Derefter kan kommunikationen foregå uforstyrret. Faktisk forudså Whitfield Diffie allerede i 1970'erne det, som senere blev kendt som »Internet«. Hans motivation for at opfinde ovenstående løsning var at give almindelige mennesker adgang til beskyttet kommunikation, som hidtil kun var tilgængeligt for militær og efterretningstjenester. Denne idé blev taget imod med stor begejstring, og snart var der flere og flere forskere, som begyndte at interessere sig for emnet. Politiske ledere og myndighederne i mange lande var dog mindre begejstrede for udspredelsen af denne teknologi, som selvfølgelig også kan anvendes til at sløre ulovlige aktiviteter. Men udviklingen lod sig ikke bremse, og i dag er kryptologi et meget aktivt forskningsområde, der fortsat bidrager til at sikre kommunikation i hverdagen. Hver gang du bruger din mobiltelefon, betaler med dankort, logger på en sikret hjemmeside eller åbner en bildør med fjernstyring, er kryptologi i spil. Diffies og Hellmans opfindelse havde også indvirkning på matematikken selv. Som nævnt stammer deres metode fra talteorien, et matematisk område som inden da blev anset for at være helt uden nogen form for praktisk nytte. Talteoretikerne var faktisk stolte af, at deres fag besad den rene teoris basale skønhed, der ikke kunne misbruges til verdslige formål. Nu viste det sig pludseligt, at dette ikke længere var tilfældet. Talteoretikernes videnskab blev anvendt i den virkelige verden, og det sidste fæstningsværk af den rene, ubesmittede matematik var nu faldet. Lavet i samarbejde med DTU Matematik

Dette sker f.eks., når du køber noget online, eller når du logger på en hjemmeside, hvor du har en brugerkonto. I mange browsere kan du genkende en sikret forbindelse ved en lille hængelås, der vises i browserens bund. Når forbindelsen er sikret, så bliver al data krypteret. Dette betyder, at de er kodet, således at kun du og din kommunikationspartner (typisk webserveren) kan læse de beskeder, der sendes frem og tilbage. Krypteringen er kun mulig, hvis du deler en hemmelighed med din partner, som ingen andre kender til. I kryptologien - videnskaben, som beskæftiger sig med hemmelige koder - kaldes en sådan hemmelighed en nøgle. Men hvordan kan det være, at du (eller din browser) deler en fælles hemmelighed med en webserver, som du aldrig før har været i kontakt med? Ens browser kunne måske have en nøgle til alle webservere? Det har den ikke, og det vil heller ikke være en god idé - hvis browserproducenten bygger nøglerne ind, så vil den jo dermed kende dem, og de vil derfor ikke længere være hemmelige. Her har vi åbenbart et problem: For at være i stand til at sende hinanden hemmelige beskeder skal man først udveksle en hemmelig nøgle, dvs. sende hinanden en hemmelig besked. Dette paradoks virker uløseligt, men i denne artikel skal vi se på, hvordan problemet med nøgleudveksling løses. Løsningsidéen Kryptologi er næsten lige så gammel som håndskriften, og i årtusinder har man løst problemet med at kunne dele en fælles hemmelighed ved at skrive nøglen på et stykke papir (eller en papyrus eller en tavle) og aflevere koden personligt eller med et bud. Med internettet er det tydeligt, at nedskrevne nøgler ikke fungerer som løsning for vores problem - du modtager jo ikke et sådant stykke papir med din computer, og du har heller ikke tastet nøglen ind i din computer. Selvfølgelig kan computeren heller ikke få nøglen direkte fra nettet, fordi så kunne andre (som eksempelvis dit telefonselskab) jo også se nøglen. Så hvordan er nøglen kommet ind i din computer? For mere end 30 år siden, da internettet ikke engang var opfundet endnu, stillede de to amerikanske kryptografer Whitfield Diffie og Martin Hellman sig det samme spørgsmål. De vidste, hvor store problemer regeringer, militær og virksomheder havde med nøgleudvekslingen, og de forudså endda en tid, hvor også privatpersoner ville få brug for kryptering. Løsningen, som Diffie og Hellman fandt på, bygger på den iagttagelse, at det ikke er muligt at basere nøgleudvekslingen på kun en enkelt besked. Hvis senderen (som vi fremover kalder Alice) sender en nøglebesked til modtageren (som vi kalder Bob), og denne besked indeholder nogle nøgleinformationer, så kan indholdet kun være selve nøglen, og dermed vil en potentiel angriber (som vi kalder Eva) også kende den. Der skal altså mindst to beskeder til for at udveksle en nøgle på en sikker måde. Eksempel på en nøgleudveksling Alice og Bob bliver enige om et offentligt heltal, som de kalder g. Eva må godt kende g, dvs., at de kan sende det åbent over nettet. Alice vælger et hemmeligt heltal, som hun kalder a. Hun beregner va = g ・ a og sender resultatet til Bob. Bob vælger også et hemmeligt heltal, som han kalder b. Han beregner vb = g ・ b og sender resultatet til Alice. Nu kan Alice beregne den fælles nøgle som va ・ b, og Bob kan beregne den som vb ・ a. Som det viser sig, er resultatet det samme, og Alice og Bob har dermed samme nøgle. Metoden er uden tvivl lidt forvirrende for Eva, men det er ikke det samme som at være sikker. Hvis Eva kender g, så kan hun beregne a = va / g. Hun kender også vb, fordi Bob har sendt det over nettet, og kan dermed bestemme nøglen på samme måde som Bob, dvs. som vb · a. Med andre ord: Vores første idé var god, men ikke god nok. Modulo-regning Vi forsøger nu at finde en bedre metode og bibeholder strukturen fra vores første eksempel. Formålet er dog at finde en bedre funktion end multiplikation - en funktion, som knytter to tal sammen på en sådan måde, at Eva ikke kan skille dem ad igen. For at forstå løsningen, som Diffie og Hellman brugte, skal vi først forstå den såkaldte modulo-funktion. Hvis x og y er hele tal (y ≠ 0), og vi skriver x mod y, så er resultatet divisionsresten, når x deles med y. For eksempel er 47 mod 15 = 2, fordi 47 = 3 ・ 15 + 2. Et kendt eksempel for modulo-regning i hverdagen er uret. Vores ure har kun tolv timer. Hvis klokken er 9 nu, og der går yderligere 6 timer, så viser uret klokken (9+6) mod 12, altså klokken 3. En lignende regel kan bruges, når man regner i måneder. Hvis det er den 20. januar i dag, og vi skal mødes om 3 uger, så er det jo egentlig den 41. januar. Men siden januar kun har 31 dage, regner vi 41 mod 31 for at finde ud af, at det svarer til den 10. februar. Når først man har vænnet sig til det, er modulo-regning ikke vanskelig at bruge. En vigtig regneregel er, at man ved brug af addition, subtraktion og multiplikation altid må reducere resultatet undervejs. Eksempel: Selvfølgelig kan man beregne (27 · 74) mod 7 ved først at danne 27 · 74 = 1998 og derefter reducere mod 7. Det kræver dog en lommeregner eller i det mindste gode regnefærdigheder. I stedet kan man nøjes med først at beregne 27 mod 7 = 6 og 74 mod 7 = 4, og derefter beregne (6 · 4) mod 7 = 24 mod 7 = 3. Modulær eksponentiering Nu er vi parat til at udvikle den funktion, som Diffie og Hellman brugte til at løse nøgleudvekslingsproblemet. Den ligner en ganske almindelig eksponentiering, som vi kender den fra matematisk analyse, hvor vi skriver gx, når g skal ganges x gange med sig selv. Men her bruger vi en modulo-operation til sidst, dvs. gx mod n. Denne operation kalder vi modulær eksponentiering. Denne funktion har den sære egenskab, at den for visse valg af g og n »springer« gennem samtlige tal i området 1,...,n-1. Hvis vi f.eks. tager g = 3 og n = 7, så får vi følgende tabel: Læg mærke til, at f.eks. 34 mod 7 kan beregnes som 33 · 3 mod 7 = 6 · 3 mod 7 = 4; det er ikke nødvendigt først at regne hele 34 ud. Bemærk også, at følgen starter forfra igen efter 35, dvs. 36 = 30 = 1, 37 = 31 = 3 osv. Hvis funktionen gx mod n gennemløber samtlige værdier mellem 1 og n-1, så hedder g en generator for {1,..,n-1}. I talteorien (en af de mest teoretiske matematiske discipliner) findes der en del teori om, hvordan man finder en sådan generator, men det behøver vi ikke at interessere os for her. Vi kan nøjes med at vide, at hvis n er et primtal, så findes der altid mindst en generator for {1,..,n-1}. Diffie-Hellman nøgleudveksling Hvorfor er det nu vigtigt? Vi har lært, at hvis n er et primtal, og g er en generator for {1,..,n-1}, så gennemløber funktionen gx mod n samtlige værdier i {1,..,n-1}. Derudover kan vi se i tabellen fra opgave 8, at funktionen »springer« på en meget uforudsigelig måde fra en værdi til den næste. Uden tabellen ville du ikke umiddelbart være i stand til at finde ud af, hvilket x du skal vælge for at få 3x mod 7 = 6. Vi siger derfor, at funktionen er vanskelig at invertere. Og dette er nøjagtigt, hvad vi har brug for. Vi ændrer nu vores protokoludkast, således at det bruger modulær eksponentiering i stedet for multiplikation: Alice og Bob bliver enige om et offentligt primtal n og en tilsvarende generator g. Angriberen må godt kende n og g, dvs. at de kan sende dem åbent over nettet. Alice vælger et hemmeligt heltal a. Hun beregner va = ga mod n og sender resultatet til Bob. Bob vælger også et hemmeligt heltal b. Han beregner vb = gb mod n og sender resultatet til Alice. Nu kan Bob beregne den fælles nøgle som (va)b mod n, og Alice kan beregne den som (vb)a mod n. Det viser sig, at resultatet er det samme, og Alice og Bob deler dermed en nøgle. I modsætning til vores første udkast kan Eva ikke beregne a ud fra va, og hun kan heller ikke beregne b ud fra vb. Hvis tallene er store nok, så kender man ingen effektiv metode til at skille va eller vb ad igen - og dette på trods af mere end 30 års intensiv forskning! Ulempen ved metoden er dog, at tallene skal være temmelig store for at gøre løsningen sikker i praksis. Primtallet n (og dermed også nøglen) skal i dag have mindst 1024 bit (helst 2048), hvilket svarer til mellem 307 og 614 cifre! Opfindelsens betydning Hvordan kan vi nu bruge denne matematiske metode i praksis? Husk at Alice kan være en hvilken som helst afsender, og Bob kan være en hvilken som helst modtager. At vi har givet dem navne betyder ikke, at de behøver være mennesker. Hvis vi husker vores eksempel fra artiklens begyndelse, så kan Alice i virkeligheden være en webserver (f.eks. for en bank), og Bob kan vare en internetbrugers computer (f.eks. din). Så når du kontakter en sikret hjemmeside - som kendes ved forkortelsen »https« i adressen - bruger webserveren og din computer ovenstående løsning for at udveksle en nøgle. Derefter kan kommunikationen foregå uforstyrret. Faktisk forudså Whitfield Diffie allerede i 1970'erne det, som senere blev kendt som »Internet«. Hans motivation for at opfinde ovenstående løsning var at give almindelige mennesker adgang til beskyttet kommunikation, som hidtil kun var tilgængeligt for militær og efterretningstjenester. Denne idé blev taget imod med stor begejstring, og snart var der flere og flere forskere, som begyndte at interessere sig for emnet. Politiske ledere og myndighederne i mange lande var dog mindre begejstrede for udspredelsen af denne teknologi, som selvfølgelig også kan anvendes til at sløre ulovlige aktiviteter. Men udviklingen lod sig ikke bremse, og i dag er kryptologi et meget aktivt forskningsområde, der fortsat bidrager til at sikre kommunikation i hverdagen. Hver gang du bruger din mobiltelefon, betaler med dankort, logger på en sikret hjemmeside eller åbner en bildør med fjernstyring, er kryptologi i spil. Diffies og Hellmans opfindelse havde også indvirkning på matematikken selv. Som nævnt stammer deres metode fra talteorien, et matematisk område som inden da blev anset for at være helt uden nogen form for praktisk nytte. Talteoretikerne var faktisk stolte af, at deres fag besad den rene teoris basale skønhed, der ikke kunne misbruges til verdslige formål. Nu viste det sig pludseligt, at dette ikke længere var tilfældet. Talteoretikernes videnskab blev anvendt i den virkelige verden, og det sidste fæstningsværk af den rene, ubesmittede matematik var nu faldet. Lavet i samarbejde med DTU Matematik

Dette sker f.eks., når du køber noget online, eller når du logger på en hjemmeside, hvor du har en brugerkonto. I mange browsere kan du genkende en sikret forbindelse ved en lille hængelås, der vises i browserens bund. Når forbindelsen er sikret, så bliver al data krypteret. Dette betyder, at de er kodet, således at kun du og din kommunikationspartner (typisk webserveren) kan læse de beskeder, der sendes frem og tilbage. Krypteringen er kun mulig, hvis du deler en hemmelighed med din partner, som ingen andre kender til. I kryptologien - videnskaben, som beskæftiger sig med hemmelige koder - kaldes en sådan hemmelighed en nøgle. Men hvordan kan det være, at du (eller din browser) deler en fælles hemmelighed med en webserver, som du aldrig før har været i kontakt med? Ens browser kunne måske have en nøgle til alle webservere? Det har den ikke, og det vil heller ikke være en god idé - hvis browserproducenten bygger nøglerne ind, så vil den jo dermed kende dem, og de vil derfor ikke længere være hemmelige. Her har vi åbenbart et problem: For at være i stand til at sende hinanden hemmelige beskeder skal man først udveksle en hemmelig nøgle, dvs. sende hinanden en hemmelig besked. Dette paradoks virker uløseligt, men i denne artikel skal vi se på, hvordan problemet med nøgleudveksling løses. Løsningsidéen Kryptologi er næsten lige så gammel som håndskriften, og i årtusinder har man løst problemet med at kunne dele en fælles hemmelighed ved at skrive nøglen på et stykke papir (eller en papyrus eller en tavle) og aflevere koden personligt eller med et bud. Med internettet er det tydeligt, at nedskrevne nøgler ikke fungerer som løsning for vores problem - du modtager jo ikke et sådant stykke papir med din computer, og du har heller ikke tastet nøglen ind i din computer. Selvfølgelig kan computeren heller ikke få nøglen direkte fra nettet, fordi så kunne andre (som eksempelvis dit telefonselskab) jo også se nøglen. Så hvordan er nøglen kommet ind i din computer? For mere end 30 år siden, da internettet ikke engang var opfundet endnu, stillede de to amerikanske kryptografer Whitfield Diffie og Martin Hellman sig det samme spørgsmål. De vidste, hvor store problemer regeringer, militær og virksomheder havde med nøgleudvekslingen, og de forudså endda en tid, hvor også privatpersoner ville få brug for kryptering. Løsningen, som Diffie og Hellman fandt på, bygger på den iagttagelse, at det ikke er muligt at basere nøgleudvekslingen på kun en enkelt besked. Hvis senderen (som vi fremover kalder Alice) sender en nøglebesked til modtageren (som vi kalder Bob), og denne besked indeholder nogle nøgleinformationer, så kan indholdet kun være selve nøglen, og dermed vil en potentiel angriber (som vi kalder Eva) også kende den. Der skal altså mindst to beskeder til for at udveksle en nøgle på en sikker måde. Eksempel på en nøgleudveksling Alice og Bob bliver enige om et offentligt heltal, som de kalder g. Eva må godt kende g, dvs., at de kan sende det åbent over nettet. Alice vælger et hemmeligt heltal, som hun kalder a. Hun beregner va = g ・ a og sender resultatet til Bob. Bob vælger også et hemmeligt heltal, som han kalder b. Han beregner vb = g ・ b og sender resultatet til Alice. Nu kan Alice beregne den fælles nøgle som va ・ b, og Bob kan beregne den som vb ・ a. Som det viser sig, er resultatet det samme, og Alice og Bob har dermed samme nøgle. Metoden er uden tvivl lidt forvirrende for Eva, men det er ikke det samme som at være sikker. Hvis Eva kender g, så kan hun beregne a = va / g. Hun kender også vb, fordi Bob har sendt det over nettet, og kan dermed bestemme nøglen på samme måde som Bob, dvs. som vb · a. Med andre ord: Vores første idé var god, men ikke god nok. Modulo-regning Vi forsøger nu at finde en bedre metode og bibeholder strukturen fra vores første eksempel. Formålet er dog at finde en bedre funktion end multiplikation - en funktion, som knytter to tal sammen på en sådan måde, at Eva ikke kan skille dem ad igen. For at forstå løsningen, som Diffie og Hellman brugte, skal vi først forstå den såkaldte modulo-funktion. Hvis x og y er hele tal (y ≠ 0), og vi skriver x mod y, så er resultatet divisionsresten, når x deles med y. For eksempel er 47 mod 15 = 2, fordi 47 = 3 ・ 15 + 2. Et kendt eksempel for modulo-regning i hverdagen er uret. Vores ure har kun tolv timer. Hvis klokken er 9 nu, og der går yderligere 6 timer, så viser uret klokken (9+6) mod 12, altså klokken 3. En lignende regel kan bruges, når man regner i måneder. Hvis det er den 20. januar i dag, og vi skal mødes om 3 uger, så er det jo egentlig den 41. januar. Men siden januar kun har 31 dage, regner vi 41 mod 31 for at finde ud af, at det svarer til den 10. februar. Når først man har vænnet sig til det, er modulo-regning ikke vanskelig at bruge. En vigtig regneregel er, at man ved brug af addition, subtraktion og multiplikation altid må reducere resultatet undervejs. Eksempel: Selvfølgelig kan man beregne (27 · 74) mod 7 ved først at danne 27 · 74 = 1998 og derefter reducere mod 7. Det kræver dog en lommeregner eller i det mindste gode regnefærdigheder. I stedet kan man nøjes med først at beregne 27 mod 7 = 6 og 74 mod 7 = 4, og derefter beregne (6 · 4) mod 7 = 24 mod 7 = 3. Modulær eksponentiering Nu er vi parat til at udvikle den funktion, som Diffie og Hellman brugte til at løse nøgleudvekslingsproblemet. Den ligner en ganske almindelig eksponentiering, som vi kender den fra matematisk analyse, hvor vi skriver gx, når g skal ganges x gange med sig selv. Men her bruger vi en modulo-operation til sidst, dvs. gx mod n. Denne operation kalder vi modulær eksponentiering. Denne funktion har den sære egenskab, at den for visse valg af g og n »springer« gennem samtlige tal i området 1,...,n-1. Hvis vi f.eks. tager g = 3 og n = 7, så får vi følgende tabel: Læg mærke til, at f.eks. 34 mod 7 kan beregnes som 33 · 3 mod 7 = 6 · 3 mod 7 = 4; det er ikke nødvendigt først at regne hele 34 ud. Bemærk også, at følgen starter forfra igen efter 35, dvs. 36 = 30 = 1, 37 = 31 = 3 osv. Hvis funktionen gx mod n gennemløber samtlige værdier mellem 1 og n-1, så hedder g en generator for {1,..,n-1}. I talteorien (en af de mest teoretiske matematiske discipliner) findes der en del teori om, hvordan man finder en sådan generator, men det behøver vi ikke at interessere os for her. Vi kan nøjes med at vide, at hvis n er et primtal, så findes der altid mindst en generator for {1,..,n-1}. Diffie-Hellman nøgleudveksling Hvorfor er det nu vigtigt? Vi har lært, at hvis n er et primtal, og g er en generator for {1,..,n-1}, så gennemløber funktionen gx mod n samtlige værdier i {1,..,n-1}. Derudover kan vi se i tabellen fra opgave 8, at funktionen »springer« på en meget uforudsigelig måde fra en værdi til den næste. Uden tabellen ville du ikke umiddelbart være i stand til at finde ud af, hvilket x du skal vælge for at få 3x mod 7 = 6. Vi siger derfor, at funktionen er vanskelig at invertere. Og dette er nøjagtigt, hvad vi har brug for. Vi ændrer nu vores protokoludkast, således at det bruger modulær eksponentiering i stedet for multiplikation: Alice og Bob bliver enige om et offentligt primtal n og en tilsvarende generator g. Angriberen må godt kende n og g, dvs. at de kan sende dem åbent over nettet. Alice vælger et hemmeligt heltal a. Hun beregner va = ga mod n og sender resultatet til Bob. Bob vælger også et hemmeligt heltal b. Han beregner vb = gb mod n og sender resultatet til Alice. Nu kan Bob beregne den fælles nøgle som (va)b mod n, og Alice kan beregne den som (vb)a mod n. Det viser sig, at resultatet er det samme, og Alice og Bob deler dermed en nøgle. I modsætning til vores første udkast kan Eva ikke beregne a ud fra va, og hun kan heller ikke beregne b ud fra vb. Hvis tallene er store nok, så kender man ingen effektiv metode til at skille va eller vb ad igen - og dette på trods af mere end 30 års intensiv forskning! Ulempen ved metoden er dog, at tallene skal være temmelig store for at gøre løsningen sikker i praksis. Primtallet n (og dermed også nøglen) skal i dag have mindst 1024 bit (helst 2048), hvilket svarer til mellem 307 og 614 cifre! Opfindelsens betydning Hvordan kan vi nu bruge denne matematiske metode i praksis? Husk at Alice kan være en hvilken som helst afsender, og Bob kan være en hvilken som helst modtager. At vi har givet dem navne betyder ikke, at de behøver være mennesker. Hvis vi husker vores eksempel fra artiklens begyndelse, så kan Alice i virkeligheden være en webserver (f.eks. for en bank), og Bob kan vare en internetbrugers computer (f.eks. din). Så når du kontakter en sikret hjemmeside - som kendes ved forkortelsen »https« i adressen - bruger webserveren og din computer ovenstående løsning for at udveksle en nøgle. Derefter kan kommunikationen foregå uforstyrret. Faktisk forudså Whitfield Diffie allerede i 1970'erne det, som senere blev kendt som »Internet«. Hans motivation for at opfinde ovenstående løsning var at give almindelige mennesker adgang til beskyttet kommunikation, som hidtil kun var tilgængeligt for militær og efterretningstjenester. Denne idé blev taget imod med stor begejstring, og snart var der flere og flere forskere, som begyndte at interessere sig for emnet. Politiske ledere og myndighederne i mange lande var dog mindre begejstrede for udspredelsen af denne teknologi, som selvfølgelig også kan anvendes til at sløre ulovlige aktiviteter. Men udviklingen lod sig ikke bremse, og i dag er kryptologi et meget aktivt forskningsområde, der fortsat bidrager til at sikre kommunikation i hverdagen. Hver gang du bruger din mobiltelefon, betaler med dankort, logger på en sikret hjemmeside eller åbner en bildør med fjernstyring, er kryptologi i spil. Diffies og Hellmans opfindelse havde også indvirkning på matematikken selv. Som nævnt stammer deres metode fra talteorien, et matematisk område som inden da blev anset for at være helt uden nogen form for praktisk nytte. Talteoretikerne var faktisk stolte af, at deres fag besad den rene teoris basale skønhed, der ikke kunne misbruges til verdslige formål. Nu viste det sig pludseligt, at dette ikke længere var tilfældet. Talteoretikernes videnskab blev anvendt i den virkelige verden, og det sidste fæstningsværk af den rene, ubesmittede matematik var nu faldet. Lavet i samarbejde med DTU Matematik