Bisher haben wir nur sogenannte symmetrische Verschlüsselungsverfahren behandelt. Diese haben den Nachteil, dass die beiden kommunizierenden Partner ihre Schlüssel austauschen müssen. Dieser Vorgang stellt natürlich ein erhebliches Sicherheitsrisiko da. Daher hat man sogenannte asymmetrische Verschlüsselungsverfahren entwickelt, bei denen kein Schlüsselaustausch direkt stattfinden muss, sondern die Schlüssel der Partner unterschiedlich sind.

Ein solches Verfahren ist das RSA-Verschlüsselungsverfahren. Entwickelt wurde das Verfahren von den drei Mathematikern Rivest, Shamir und Adleman, die dem Verfahren auch ihren Namen gaben. Es entstand unter dem Einfluss der Veröffentlichung des Diffie-Hellman Verfahrens und wird als erstes pulic-key Verfahren betrachtet.

Prinzip

Bei RSA gibt es praktisch zwei Schlüssel. Einen privaten, den nur der Ersteller kennt, und einen öffentlichen, den jeder einsehen kann. Aus diesem Grund spricht man auch von einem sogenannten public-key Verfahren.

Nachdem der öffentliche und private Schlüssel generiert wurde, wird der öffentliche Schlüssel veröffentlicht. Im obigen Bild beschreibt der Schlüssel den privaten Schlüssel, und die Paketbox den öffentlichen Schlüssel.

Wenn nun Alice an Bob eine verschlüsselte Nachricht schicken möchte, nutzt sie zum Verschlüsseln den öffentlichen Schlüssel von Bob. Die Nachricht kann nun nur mit dem passenden privaten Schlüssel entschlüsselt werden. Den privaten Schlüssel besitzt im besten Fall nur Bob, und der kann somit die Nachricht in Form des Diamanten entschlüsseln und aus der Box holen.

Signaturen erstellen

RSA kann auch zum Verifizieren verwendet werde. Dabei verschlüsselt der Absender seine Nachricht mit seinem privaten Schlüssel. Jede Person kann nun diese Nachricht mit dem öffentlichen Schlüssel entschlüsseln. Tatsächlich kann aber nur dann ein vernünftiges Ergebnis aus diesem Vorgang resultieren, wenn vom Absender der passende private Schlüssel verwendet wurde. Eine solche Signatur ist unter anderem bei der Man-in-the-middle Attacke wichtig, wie im vorherigen Artikel erläutert wird.

Signaturen sowie ver- und entschlüsselte Nachrichten können nur erstellt werden, weil RSA auf folgendem Prinzip basiert:

$privateKey(publicKey(message)) = message$ $publicKey(privateKey(message)) = message$

$publicKey$ und $privateKey$ sind sogenannte Umkehrfunktionen. Das heißt, sie funktionieren in beide Richtungen.

Erstellen der Schlüssel

Zuerst werden zwei Primzahlen $p$ und $q$ gewählt.

Nun wird die Zahl $N$ berechnet.

Mit $p$ und $q$ wird nun die eulersche Phifunktion $\varphi(N) = r$ gebildet.

Nun kann der öffentliche Schlüssel $e$ berechnet werden. Dabei muss $e$ so gewählt werden, dass die Zahl zu $r$ teilerfremd ist. Der größte gemeinsame Teiler wird beispielsweise mit dem euklidischen Algorithmus überprüft.

Der private Schlüssel $d$ wird mit $e$ und $r$ berechnet.

Dabei handelt es sich bei der obigen Rechnung um eine diophantische Gleichung, die mit dem erweiterten euklidischen Algorithmus gelöst werden kann.

$e$ und $r$ sind dabei bekannte Zahlen, die schon im Verlauf der Schlüsselerstellung berechnet wurden. Sollte für $d$ ein negativer Wert berechnet werden, kann man diesen so lange mit r addieren, bis der Wert im positiven Bereich liegt.

Der öffentliche Schlüssel setzt sich nun zusammen aus $e$ und $N$. Der private Schlüssel setzt sich zusammen aus $d$ und $N$.

Ver- und Entschlüsseln

Verschlüsseln: $c = m^{e} \bmod N$

Entschlüsseln: $m = c^{d} \bmod N$

Implementierung

Zuerst muss der private und öffentliche Schlüssel erzeugt werden. Dafür wird die Klasse BigInteger benutzt, da sie viele Methoden hat, die bei der Berechnung helfen.

private BigInteger generateD() {
    if (this.e == null || this.r == null) return null;

    // Wenn e und r nicht teilerfremd sind
    if (this.e.gcd(r).compareTo(BigInteger.ONE) != 0) return null;

    // e*d mod r = 1
    return this.e.modInverse(this.r);
}

private BigInteger generateE() {
    if (this.r == null) return null;
    BigInteger tempE;
    SecureRandom secureRandom = new SecureRandom();

    do{
        // zufälligen BigInteger bis teilerfremd zu r
        tempE = new BigInteger(this.bitLength, secureRandom);
    }while(this.r.gcd(tempE).compareTo(BigInteger.ONE) != 0);

    return tempE;
}

private BigInteger generateR() {
    if (this.p == null || this.q == null) return null;
    return this.p.subtract(BigInteger.ONE).multiply(this.q.subtract(BigInteger.ONE));
}

private BigInteger generateN() {
    if (this.p == null || this.q == null) return null;
    return this.p.multiply(this.q);
}

Um eine erhaltene Nachricht zu entschlüsseln, wird die Methode Decrypt aufgerufen.

public BigInteger Decrypt(BigInteger val) {
    if (this.d == null || this.n == null) return BigInteger.ZERO;

    BigInteger c = val;

    // Potenzieren mit Modulo
    return c.modPow(this.d, this.n);
}

Wenn der Benutzer eine Nachricht mit einem fremden Schlüssel verschlüsseln will, wird folgende Methode aufgerufen.

/**
    * Verschlüsselt eine Nachricht mit einem fremden öffentlichen Schlüssel
    * @param pM Die Nachricht
    * @param pN p*q
    * @param pE Mit pN der öffentliche Schlüssel
    * @return  Die verschlüsselte Nachricht wird als BigInteger zurückgegeben
*/
public BigInteger encryptWithExternalValues(int pM, int pN, int pE) {
    BigInteger localM = BigInteger.valueOf(pM);
    BigInteger localN = BigInteger.valueOf(pN);
    BigInteger localE = BigInteger.valueOf(pE);

    return localM.modPow(localE, localN);
}