Wie wir schon im Diffie-Hellman-Protokoll gelernt haben, soll unsere Einwegfunktion in eine Richtung einfach sein, und in die andere Richtung sehr aufwendig/unmöglich sein. Eine andere Variante ist als das RSA-Verfahren bekannt. Dabei haben wir keinen gemeinsammen geheimen Schlüssel, sonderen nur noch unsere öffentlichen und privaten Schlüssel.

Schlüsselgenerierung

  1. Wähle die Primzahlen p und p
  2. Berechne N = p * q
  3. Berechne r = (p-1)*(q-1)
  4. Wähle e, sodass e und r keine gemeinsammen Teiler haben
  5. Wähle d, sodass e*d % r = 1
  6. Gib N und e weiter. d ist der geheime Schüssel

Verschlüsseln der Nachricht m

Die Nachricht m wird über c = M^e % N verschlüsselt.

Entschlüsseln des Geheimtextes c

Wie auch schon bei Diffie-Hellman entschlüsseln wir über die gleiche Operation m = c^d % N

Es ist erkennbar, dass sich RSA und Diffie-Hellman im Grunde genommen nur über die Schlüsselberechnung unterscheiden, wobei der gemeinsamme geheime Schlüssel bei Diffie-Hellman dem Klartext entspricht. Wir haben auch hier wieder unsere Potenz mit anschschließendem Modulo-Nehmen.

Implementierung in Java

Der Einfachheit halber habe ich hier nur die Implementierung, um integer zu verschlüsseln abgebildet. Jedoch kann man sich denken, dass man so auch mit wenig Mehraufwand Text verschlüsseln kann.

class KeyPair {
    private int d;
    public int N;
    public int e;
    KeyPair(int p, int q) {
        this.N = p * q:
        int r = (p-1) * (q-1);
        this.e = r;
        // Einfach ein e finden, was keinen gemeinsammen Teiler mit r hat.
        while(checkHasGGT(this.e, r, r)) this.e++;
        this.d = inv_euklid(r, this.e);
    }
    public int decrypt(int msg) {
        return Math.pow(msg, this.d) % this.N;
    }
    public static int encrypt(int otherN, int otherE, int msg) {
        return  Math.pow(msg, otherE) % otherN;
    }
    // x ist der größte gemeinsamme Teiler, den es zu prüfen gilt.
    private static bool checkHasGGT(int a, int b, int x) {
        int G = extended_euklid(a, b);
        for(int divisor = 2; divisor <= x; divisor++)
            while (G % divisor == 0) G = G / divisor;
        return G <= X;
    }
    // Rekursive Implementierung des Euklidischen Algorithmus, um den ggT zu berrechnen
    private static int extended_euklid(int a, int b) {
        if(b==0) return a;
        if(a>b) return extended_euklid(b, a % b);
    }
    private static int inv_euklid(int r, int e) {
        // Da ich mich nicht so tief im Thema CAS (Computer-Algebra-Systeme auskenne, um eine gleichung dazu komplett umzuformen, lasse ich diese Funktion einach als Blackbox, welche das X aus der Gleichung 1 = x * r + y * e zurückgibt
    }
}