Der Diffie-Hellman Key Exchange ist ein kryptographisches Protokoll, das die sichere Kommunikation über unsichere Kanäle ermöglicht. Es ist eines der grundlegenden Verfahren im Bereich der asynchronen [[kryptographie|Verschlüsselung]] (Public-Key-Encryption). Der Diffie-Hellman Key Exchange bildet die Basis für viele moderne Verschlüsselungsprotokolle, wie zum Beispiel das Secure Sockets Layer ([[ssl|SSL]]) und das Internet Protocol Security ([[ipsec|IPsec]]).

<box green>Es ermöglicht zwei Parteien, einen geheimen Schlüssel über eine unsichere Leitung zu vereinbaren.</box>.

=====Beispiel=====

<code>
Step 1: Alice and Bob both share public numbers (P = 23, G = 9) where G is a primitive root of P.

Step 2: Alice selected a private key a = 4 and Bob selected a private key b = 3

Step 3: Alice and Bob compute public values
        Alice:   x =(9^4 mod 23) = (6561 mod 23) = 6
        Bob:    y = (9^3 mod 23) = (729 mod 23)  = 16

Step 4: Alice and Bob exchange public numbers

Step 5: Alice receives public key y =16 and Bob receives public key x = 6

Step 6: Alice and Bob compute symmetric keys
        Alice:  ka = y^a mod p = 65536 mod 23 = 9
        Bob:    kb = x^b mod p = 216 mod 23 = 9

Step 7: 9 is the shared secret.
</code>

=====Pseudo Code=====

<code>
function power(a, b, P) {
    if(b == 1)
        return a;    
    return Integer.parse(Math.pow(a, b)) % P;
}

var P, G, apub, a, bpub, b, ka, kb;

P = 23; // A prime number P is taken
G = 9; // A primitve root for P, G is taken

a = 17; // a 4 is the chosen private key
apub = power(G, a, P); // gets the generated key
     
b = 33; // b 3 is the chosen private key
bpub = power(G, b, P); // gets the generated key
 
ka = power(bpub, a, P); // Secret key for Alice
kb = power(apub, b, P); // Secret key for Bob

print("Secret key for the Alice is : " + ka + ", Secret Key for the Bob is : " + kb);
</code>

<code c>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Diffie-Hellman-Parameter
#define P 10847      // Prime number 23
#define G 5       // Primitive root of P 5

// Funktion zur Berechnung des Modulo-Exponentiation
int moduloExpo(int base, int exponent, int modulus) {
    long long result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exponent /= 2;
    }
    return (int) result;
}

int main() {
    
    int privateA, privateB;  // Private Schlüssel für A und B
    int publicA, publicB;    // Öffentliche Schlüssel für A und B
    int sharedSecretA, sharedSecretB;  // Gemeinsames Geheimnis für A und B

    // Schritt 1: Schlüsselpaare generieren
    privateA = rand() % 10 + 1; // Zufälliger privater Schlüssel für A
    privateB = rand() % 10 + 1; // Zufälliger privater Schlüssel für B

    // Berechnung der öffentlichen Schlüssel für A und B
    publicA = moduloExpo(G, privateA, P);
    publicB = moduloExpo(G, privateB, P);
    
    printf("publicA: %d, publicB: %d\n", publicA, publicB);

    // Schritt 2: Gemeinsames Geheimnis berechnen
    sharedSecretA = moduloExpo(publicB, privateA, P);
    sharedSecretB = moduloExpo(publicA, privateB, P);

    // Überprüfen, ob die berechneten gemeinsamen Geheimnisse übereinstimmen
    if (sharedSecretA == sharedSecretB) {
        printf("Gemeinsames Geheimnis: %d\n", sharedSecretA);
    } else {
        printf("Fehler beim Berechnen des gemeinsamen Geheimnisses.\n");
        return 1;
    }

    // Schritt 3: Verschlüsselung und Entschlüsselung eines Strings
    char plaintext[] = "Hallo, Welt, wie geht es dir? Alles in der Ordnung? Hallo, Welt, wie geht es dir? Alles in der Ordnung? Hallo, Welt, wie geht es dir? Alles in der Ordnung? Hallo, Welt, wie geht es dir? Alles in der Ordnung? Hallo, Welt, wie geht es dir? Alles in der Ordnung? Hallo, Welt, wie geht es dir? Alles in der Ordnung? Hallo, Welt, wie geht es dir? Alles in der Ordnung? Hallo, Welt, wie geht es dir? Alles in der Ordnung? Hallo, Welt, wie geht es dir? Alles in der Ordnung?";
    int len = strlen(plaintext);

    // Verschlüsselung
    for (int i = 0; i < len; i++) {
        plaintext[i] = plaintext[i] ^ sharedSecretA;
    }
    
    printf("Verschlüsselter Text: %s\n", plaintext);

    // Entschlüsselung
    for (int i = 0; i < len; i++) {
        plaintext[i] = plaintext[i] ^ sharedSecretA;
    }

    printf("Entschlüsselter Text: %s\n", plaintext);

    return 0;
}
</code>

Find primitive root

<code c>
#include <stdio.h>
#include <stdbool.h>

// Funktion zur Berechnung des Modulo-Exponentiation
int moduloExpo(int base, int exponent, int modulus) {
    long long result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exponent /= 2;
    }
    return (int) result;
}

// Funktion zur Überprüfung, ob eine Zahl eine Primzahl ist
bool isPrime(int number) {
    if (number <= 1) {
        return false;
    }
    for (int i = 2; i * i <= number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

// Funktion zur Berechnung der primitive Wurzel einer Primzahl
int calculatePrimitiveRoot(int prime) {
    for (int root = 2; root < prime; root++) {
        bool isPrimitiveRoot = true;
        for (int i = 1; i < prime - 1; i++) {
            if (moduloExpo(root, i, prime) == 1) {
                isPrimitiveRoot = false;
                break;
            }
        }
        if (isPrimitiveRoot) {
            return root;
        }
    }
    return -1;  // Keine primitive Wurzel gefunden
}

int main() {
    int prime;

    printf("Geben Sie eine Primzahl ein: ");
    scanf("%d", &prime);

    if (!isPrime(prime)) {
        printf("%d ist keine Primzahl.\n", prime);
        return 1;
    }

    int primitiveRoot = calculatePrimitiveRoot(prime);
    if (primitiveRoot == -1) {
        printf("Keine primitive Wurzel gefunden für die Primzahl %d.\n", prime);
    } else {
        printf("Die primitive Wurzel von %d ist %d.\n", prime, primitiveRoot);
    }

    return 0;
}
</code>