En hemlig nyckel

I det här avsnittet kommer vi gå igenom den första nedskrivna metoden för ett öppet nyckelutbyte, Diffie-Hellmans nyckelutbyte.

Diffie-Hellman

Många krypteringssystem idag använder sig av kongruensräkning. Detta är även fallet med Diffie-Hellman. Idén med metoden är att Alice och Bob, två vanligt förekommande karaktärer inom kryptering, vill skicka ett meddelande till varandra.

De vet att Eve (från engelskans eavesdropper) kommer lyssna på allt som Alice och Bob skriver till varandra. Alltså vill de skicka hemliga meddelanden till varandra. Detta kan de göra med hjälp av Diffie-Hellmans nyckelutbyte.

Metoden

Till en början kommer Alice och Bob överens om ett primtal p. För att göra metoden enklare att följa väljer vi p=17. Även Eve vet om det här talet.

Efter detta väljer de en primitiv rot modulo 17. En primitiv rot är ett heltal g som är större än 1 och mindre än p (i det här fallet mindre än 17), med egenskapen att alla heltal modulo 17 kan uttryckas som potenser av g. I det här fallet kan alltså talen 1, 2, 3,...,16 uttryckas med hjälp av g. Således är mängden \(\{1,2,\dots,16\}=\{g^1,g^2,\dots,g^{16}\}\).

Detta kan låta lite komplicerat, men så är inte fallet. Till exempel är g=3 en primitiv rot modulo 17 (g kallas även för generator). Vi kan visa att g är en generator genom följande beräkningar:

$$\begin{align}3^1&\equiv 3 \mod{17}\\3^2&\equiv 9 \mod{17}\\3^3&\equiv 10 \mod{17}\\3^4&\equiv 13 \mod{17}\\3^5&\equiv 5 \mod{17}\\3^6&\equiv 15 \mod{17}\end{align}$$

och så vidare. Alice och Bob väljer talet g=3 som deras generator, även Eve får reda på talet.

Nu väljer Alice ett heltal a och Bob ett heltal b. Dessa är de enda två talen Eve inte får reda på. Talen a och b kallas för Alice och Bobs privata nycklar. 

Alice väljer a=6 och Bob b=14. Alice skickar nu

$$g^a=3^6\equiv 15\mod{17}$$

till Bob och Bob skickar

$$g^b=3^{14}\equiv 2\mod{17}$$

till Alice. Alice skickar alltså talet 15 till Bob, inte hela uträkningen, och vice versa. Båda dessa tal ser Eve.

Både Alice och Bob kommer nu beräkna talet de fick, upphöjt till sin privata nyckel:

$$\begin{align}\text{Alice:}\ \ \ \ 2^6 \equiv 13\mod{17}\\ \text{Bob:}\ 15^{14}\equiv 13\mod{17}\end{align}$$

Talet 13 är Alice och Bobs hemliga nyckel!

Trots att Eve vet om primtalet 17, generatorn 3 och talen 15 och 2, kan Eve inte få reda på deras hemliga nyckel 13.

Formellt kommer nyckeln vara:

$$g^{ab}\equiv K\mod{p}$$

Skicka meddelanden

Det går även att skicka meddelanden med den här metoden. Först måste meddelandet översättas till ett tal M som är mindre än primtalet p. Sedan skickas det krypterade meddelandet genom:

$$K M\equiv M'\mod{p}$$

M' är alltså det krypterade meddelandet. För att dekryptera meddelandet beräknar mottagaren inversen till nyckeln, det vill säga de beräknar \(K^{-1}=g^{-ab}\). När mottagaren gjort det beräknas:

$$\begin{align}K^{-1} M'&\equiv K^{-1}KM \\&\equiv g^{-ab}g^{ab}M\\&\equiv g^{-ab+ab}M\\&\equiv M\mod p\end{align}$$

Eftersom både Alice och Bob använder sig av samma nyckel är detta ett exempel på symmetrisk kryptering.

Eve, som vet \(g,\ g^a,\ g^{b}\) och \(p\), kan inte beräkna \(g^{ab}\) och då inte heller \(g^{-ab}\). Detta eftersom metoden bygger på att det diskreta logaritmproblemet inte kan lösas inom rimlig tid.

Metoden används sällan för att skicka meddelanden. Om meddelanden skulle skickas med den här metoden krävs det stora primtal för att anses säkert, däremot går det bra att byta nycklar på det här viset. Nycklarna används för att låsa upp en annan krypteringsalgoritm.

Den här metoden är den första metoden för ett öppet nyckelutbyte. Dagens datorer använder liknande algoritmer för att göra nyckelutbyten.