Im letzten Jahr wurde im Unterricht schon ein kleiner Einstieg in die Kryptographie gewagt. Nun wird diese Reihe fortgesetzt und um aktuelle Verfahren wie den Diffie-Hellman-Schlüsselaustausch und das RSA-Verfahren erweitert.

Damals wurden Caesar und Vigenère implementiert - zwei einfache Verfahren, die auf Verschiebung der Daten um einen festgelegten Schlüssel basieren.

Caesar verschiebt jeden Buchstaben um die gleiche, festgelegte Zahl. Der Klartext “Anna” wird mit 33 als Schlüssel zum Chiffre “Dqqd”, aus dem durch das Rückverschieben um 33 wieder “Anna” entsteht.

Vigenère erweitert dies um einen variierenden Schlüssel. “abc” als Schlüssel bedeutet: Verschiebe den ersten Buchstaben um 11, den zweiten um 22, den dritten um 33 und den vierten wieder um 11 (und so weiter…).

Man könnte nun denken: “Na also, dann kann ich ja jetzt beruhigt meine Online-Überweisung tätigen - Vigenère verschlüsselt das ja sicher.” Dieser Gedanke wäre fatal, denn sowohl Cäsar als auch Vigenère sind angreifbar:

Caesar ist einfach über Brute-Force anzugreifen, schließlich gibt es nur 26 Möglichkeiten der Verschiebung. Vigenère kann über eine Häufigkeitsanalsye angegreifen werden - das funktioniert aber nur, wenn der Schlüssel zu kurz ist - diese Eigenschaft wird später noch wichtig.

Diffie-Hellman-Schlüsselaustausch

Nehmen wir an, zwei Personen möchten miteinander kommunizieren. Diese einigen sich darauf, Vigenère mit ausreichend langem Schlüssel zu verwenden. Nun müssen sie diesen Schlüssel irgendwie aushandeln - am besten, ohne sich dabei zu treffen. Der Diffie-Hellman-Schlüsselaustausch ermöglicht dies.

Zum besseren Verständnis möchte ich drei Figuren einführen: Alice, Bob und Eve (“Eavesdropper”). Alice möchte Bob eine Nachricht senden, ohne dass Eve diese mitlesen kann. Der Haken ist: Alice und Bob können ausschließlich über Eve kommunizieren. Eve kann das, was sie in den Händen hält, mitlesen und sogar manipulieren.

Ein Kryptographisches Verfahren muss also leisten, dass Alice und Bob kommunizieren können, ohne dass Eve diese Kommunikation mitlesen kann.

Zur Aushandlung des Schlüssels wird zuerst ein öffentlicher Schlüssel (p,g)(p, g) bestimmt. Dieser wird nach folgenden Bestimmungen gewählt:

  • pp ist eine Primzahl.
  • g<p;g∈Rg < p ; g \in \mathbb{R}

Dieses Schlüsselpaar wird nun veröffentlicht - Alice, Bob und Eve kennen es.

Nun wählen Alice und Bob im Geheimen einen eigenen, privaten Schlüssel:

a<pbzw.b<p\displaystyle a < p \quad \textrm{bzw.} \quad b < p

Damit bestimmen sie ihre öffentlichen Austausch-Werte:

A=ga mod p\displaystyle A = g^a \bmod p
B=gb mod p\displaystyle B = g^b \bmod p

Diese werden dann wieder veröffentlicht, Alice erhält also BB und Bob erhält AA.

Aus diesen Werten kann nun einfach ein gemeinsamer Schlüssel bestimmt werden:

KA=Ba mod p\displaystyle K_A = B^a \bmod p
KB=Ab mod p\displaystyle K_B = A^b \bmod p

Dass KAK_A mit KBK_B identisch ist, lässt sich mathematisch beweisen. Mehr Informationen dazu finden sich in der zugehörigen Veröffentlichung .

Eve hat zwar während des Schlüsselaustauschs alle Informationen übertragen, kennt aber nur pp, gg, AA und BB. Daraus kann Eve nicht auf K schließen, denn ihr fehlt einer der geheimen Schlüssel aa und bb. Trotzdem verfügen Alice und Bob nach diesem Schlüsselaustausch über einen gemeinsamen Schlüssel, mit dem sie nun ihre Daten verschlüsseln können. Jetzt könnte zum Beispiel Vigènere oder One-Time-Pad1 eingesetzt werden - bei hohen Schlüssellängen sind diese Verfahren nämlich sicher2.

Dort liegt eine Krux des Verfahrens: Um einen großen Schlüssel zu erzeugen, müssen große Eingabewerte gewählt werden - deshalb sind große Primzahlen für die Kryptographie so wichtig.

DH kann angegriffen werden, wenn zu kleine Werte verwendet werden, oder rr unklug gesetzt wird. rr sollte ein Generator sein, sonst könnte Eve AA und BB auf aa oder bb schließen.

Eine Beispiel-Implementierung für Diffie-Hellman findet sich in meinem GitHub-Repository.

Asymmetrische Verschlüsselungsverfahren

Verschlüsselungsverfahren, wie wir sie bisher kennen gelernt haben, verwenden zum Verschlüsseln den selben Schlüssel wie zum Entschlüsseln. In Kontrast zu diesen symmetrischen Verfahren stehen solche, die zum Verschlüsseln und Entschlüsseln zwei separate Schlüssel verwenden. Solche Verfahren nett man asymmetrische, ein Beispiel ist das als sicher geltende RSA.

RSA

RSA wurde 1977 von den drei Wissenschaftlern Ron Rivest, Adi Shamir und Leonard Adleman vorgestellt.

Um RSA verwenden zu können, muss erst ein Schlüsselpaar, also ein öffentlicher und ein privater Schlüssel, erzeugt werden.

Dafür werden zu Beginn zwei beliebige Primzahlen pp und qq gewählt.

p∈P\displaystyle p \in \mathbb{P}
q∈P\displaystyle q \in \mathbb{P}

Aus diesen kann dann NN und rr ermittelt werden:

N=p∗q\displaystyle N = p * q
r=ϕ(p,q)=(p−1)∗(q−1)\displaystyle r = \phi(p, q) = (p - 1) * (q - 1)

Nun wird eine weitere, beliebige Zahl ee gewählt, die mit rr Teilerfremd ist.

e∈N\displaystyle e \in \mathbb{N}
ggt(e,r)=1\displaystyle ggt(e, r) = 1

Als letzte Berechnung muss nun noch dd, das modulare Inverse von ee und rr gefunden werden.

e∗d mod r=1\displaystyle e * d \bmod r = 1

Nun sind alle Teile des Schlüsselpaars vorhanden: Der öffentliche Schlüssel (N,e)(N, e) und der private Schlüssel (N,d)(N, d). Die anderen berechneten Werte sollten zerstört werden, um die Rekonstruktion des privaten Schlüssels zu verhindern.

Möchte man nun eine Nachricht mm verschlüsseln, so verwendet man den öffentlichen Schlüssel:

c=me mod N\displaystyle c = m^e \bmod N

Um dieses Chiffre cc nun wieder zu entschlüsseln, kommt der private Schlüssel zum Einsatz:

m=cd mod N\displaystyle m = c^d \bmod N

Um das Erzeugen eines Schlüssels einmal selbst auszuprobieren, kann ich die Website der Drexel University sehr empfehlen.

Kryptographie in Java

Kryptographische Verfahren basieren oft auf der Verwendung großer Zahlen, die gerne die Größe von 32 Bit (Java’s int-Typ) übersteigen.

Um diese Begrenzung zu umgehen, stellt das JDK die BigInteger-Klasse zur Verfügung. Sie hält beliebig große Zahlen, ihre einzige Grenze ist die Größe des Arbeitsspeichers.

Sie verfügt außerdem schon über alle Rechenarten, die wir für die meisten Verschlüsselungsverfahren benötigen!

Als Beispiel möchte ich die Implementation von RSA anführen.

Das Ver- und Ent-schlüsseln verwendet die a.modPow(e, m)-Methode des BigInteger, die dem Term ae mod ma^e \bmod m entspricht.

BigInteger encrypt(BigInteger m, BigInteger e, BigInteger N) {
  return m.modPow(e, N);
}

BigInteger decrypt(BigInteger c, BigInteger d, BigInteger N) {
  return c.modPow(d, N);
}

Das Erzeugen eines Schlüsselpaars ist ähnlich simpel:

Random random = new SecureRandom();
BigInteger p = BigInteger.probablePrime(1024, random);
BigInteger g = BigInteger.probablePrime(1024, random);

BigInteger N = p.multiply(g);
BigInteger r = p.subtract(BigInteger.ONE)
                .multiply(
                  g.subtract(BigInteger.ONE)
                );

BigInteger e = computeE(r);

BigInteger d = e.modInverse(r);

computeE(r) ist eine Methode, die so lange eine zufällige Zahl ee erzeugt, bis sie alle drei Bedingungen erfüllt:

  1. e>=1e >= 1
  2. e<=re <= r
  3. gcd⁡e,r=1\gcd{e, r} = 1
static BigInteger computeE(BigInteger r) {
  BigInteger e;

  do e = new BigInteger(r.bitLength(), random);
  while (e.compareTo(BigInteger.ONE) <= 0 // 1
          || e.compareTo(r) >= 0 // 2
          || !e.gcd(r).equals(BigInteger.ONE)); // 3

  return e;
}

TL;DR

Diffie-Hellman ermöglicht es, sich auf einen gemeinsamen Schlüssel zu eignen, ohne dass ein Dritter diesen erfährt. Dabei werden große Primzahlen und eine geschickte Wahl des Generators gg benötigt.

Asymmetrische Verschlüsselungsverfahren haben einen öffentlichen Schlüssel, mit dem Daten verschlüsselt werden, sowie einen privaten Schlüssel, mit den diese wieder entschlüsselt werden können. Ein Beispiel eines solchen Verfahrens ist RSA.

Möchte man eines dieser Verfahren in Java implementieren, so muss man oft noch nicht einmal komplizierte Algorithmen umsetzen - die Klasse BigInteger kann die meisten Rechenarten von Haus aus.

  1. One-Time-Pad: Bitweise XOR-Verknüpfung von Daten und Schlüssel ↩

  2. “sicher” bedeutet, dass sie nur durch eine Brute-Force-Attacke geknackt werden können. ↩