RSA-Verschlüsselung

Die RSA-Verschlüsselung ist ein kryptografisches Verfahren. Die Mathematik dahinter ist schnell erklärt, aber dennoch nicht einfach; aber um die an vielen Stellen erklärte Mathematik geht es hier gar nicht, sondern darum, in welcher Form die Schlüssel gespeichert werden. Dafür gibt es nämlich verschiedene Formate.

Was man zum Verschlüsseln braucht

Eine Nachricht
n (Produkt zweiter Primzahlen)
e (public key exponent, indirekt aus n erzeugt)

Jeder kann verschlüsseln, da der public key öffentlich ist!

Was man zum Entschlüsseln braucht

Eine verschlüsselte Nachricht
n (Produkt zweier Primzahlen)
d (private key exponent, indirekt aus n und e erzeugt)

Nur wer den private key hat, kann entschlüsseln!

Die Zahlen n, d und e müssen natürlich die gleichen sein, und der Witz ist, dass man, auch wenn man n und e kennt, nicht so einfach d ausrechnen kann.

(Tatsächlich wird meist nicht die ganze Nachricht mit RSA verschlüsselt, sondern nur der symmetrische Schlüssel, der dann geteilt wird.)

Formate

In welcher Form speichert man den öffentlichen und den privaten Schlüssel? Zuerst n, dann e, oder umgekehrt, mit welchem Trennzeichen dazwischen? Speichert man die Zahlen als Bitfolge (lauter 0en und 1en) oder als Hexadezimalfolge (0 bis 9, dazu A bis F), oder in einem ganz anderen Format? Soll man einen Namen mit speichern, damit man später noch weiß, welcher privater Schlüssel zu welchem öffentlichen gehört, oder zu welchem Zweck der Schlüssel überhaupt angelegt wurde? Will man das Erstelldatum speichern, soll man ein Ablaufdatum eingeben? Soll der gespeicherte Schlüssel selber verschlüsselt werden, damit ihn niemand unbefugt verwenden kann? All diese Informationen kann man eventuell in der Schlüsseldatei zusätzlich speichern.

Im Lauf der Zeit haben sich verschiedene Format-Standards zur Schlüssel-Speicherung entwickelt:

PKCS8	Java private key
X.509	Java public key
PEM
RFC 4716
OpenSSH	ssh-keygen
PPK	PuTTY

Verschiedene Programme benutzen verschiedene Formate. Das macht den Austausch nicht ganz einfach. Dazu kommt noch, dass es neben RSA auch noch weitere Verschlüsselungsverfahren gibt.

Format: OpenSSH mit RSA

Erzeugen eines Schlüsselpaars

Unter Linux (oder MacOS?) tippt man auf der Kommandozeile:

ssh-keygen -b 1024 -t rsa -C "rau" -f rau1024

-b 1024: Der Schlüssel soll 1024 Bits lang sein. Das ist in der Praxis zu kurz, da sind 4096 besser!
-t rsa: Es soll das RSA-Verfahren verwendet werden.
-C "rau": Das ist ein kurzer Kommentar, der in die Datei geschrieben wird. Das könnte auch eine E-Mail-Adresse sein.
-f rau1024: Speichere die zwei Schlüssel in Dateien namens „rau1024“

Außerdem kann man die Schlüsseldatei noch durch ein Kennwort (passphrase) sichern, das habe ich hier nicht getan.

Der öffentliche Schlüssel in OpenSSH mit RSA

Wenn man so macht wie oben angegeben, dann sieht ein öffentlicher Schlüssel etwa so aus (Zeilenumbrüche ergänzt):

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAAAgQDWWlYiaGqPz0t
WeFgGjfRyH1Tt2Og0JLcTten2jttbwSO+FRAuO3CK4+1KLI4g6z
UKVbEAN6HM3g4YkstnWLEGphAgeix9dBKSoEokPWKZw1Rcz7XPz
4hMAqZsPAc/8o9FDDoORirWQmU2ovL5jx9931whbFtS/KVhOAay
B4K7AQ== rau

Alles bis zum ersten Leerzeichen und alles ab dem zweiten Leerzeichen gehört nicht dazu, das ist nur für den Menschen gedacht. Mehr Leerzeichen wird es nicht geben. Der Rest besteht eigentlich aus einer Reihe von Bits oder Bytes, aber damit man sie in einem Textprogramm gut anschauen kann, ist sie mit einem Verfahren, das Base64 heißt, in druckbare Zeichen, also Buchstaben, Satzzeichen und Ziffern, umgewandelt worden.

Mit dem Befehl base64 -d rau1024.pub.cut > rau1024.pub.cut.hex erzeugt man aus der Datei mit den Base64-kodierten Bits wieder die ursprünglichen Bits oder Bytes. Weil das jetzt nicht mehr Base64-kodiert ist, kann man sich diese Bytes nicht mehr in einem Texteditor anschauen, sondern muss einen Hexeditor benutzen:

Oder mit hexdump -C rau1024.pub.cut.hex > rau1024.pub.cut.hex.dump:

00 00 00 07 73 73 68 2d 72 73 61 00 00 00 03 01 00 01 00 00 00 81 00 d6 5a 56 22 68 6a 8f cf 4b 56 78 58 06 8d f4 72 1f 54 ed d8 e8 34 24 b7 13 b5 e9 f6 8e db 5b c1 23 be 15 10 2e 3b 70 8a e3 ed 4a 2c 8e 20 eb 35 0a 55 b1 00 37 a1 cc de 0e 18 92 cb 67 58 b1 06 a6 10 20 7a 2c 7d 74 12 92 a0 4a 24 3d 62 99 c3 54 5c cf b5 cf cf 88 4c 02 a6 6c 3c 07 3f f2 8f 45 0c 3a 0e 46 2a d6 42 65 36 a2 f2 f9 8f 1f 7d df 5c 21 6c 5b 52 fc a5 61 38 06 b2 07 82 bb 01

Diese Daten muss man so auseinanderpfriemeln:

Zuerst kommen 4 Byte, in denen steht, aus wie viel Zeichen/Byte der folgende Name besteht. Hier bedeuten die ersten 00 00 00 07, dass die folgenden 7 Byte für den Namen reserviert sind. Dann kommen tatsächlich auch solche Byte, hier eben 7, die den Namen des Verfahrens enthalten, 73 73 68 2d 72 73 61, was man als „ssh-rsa“ lesen kann.
Dann kommen 4 Byte, in denen steht, aus wie viel Byte der folgende Exponent e besteht. Hier steht da 00 00 00 03, also dezimal 3, was heißt, dass die darauf folgenden 3 Byte das e ausmachen. In den folgenden 3 Byte stehen dann 01 00 01, also dezimal 65537. Das ist der Wert unseres e, das wir fürs Verschlüsseln brauchen. Das ist tatsächlich auch bei verschiedenen Schlüsseln oft 65537, weil sich das als praktisch erwiesen hat.
Dann kommen 4 Byte, in denen steht, aus wie viel Byte die folgende Zahl n besteht. Oben steht 00 00 00 81, das ist dezimal 129. Die folgenden 129 Byte (es sind alle restlichen in der Datei) sind also unser n: 00 d6 5a 56 22 68 6a 8f cf 4b 56 78 58 06 8d f4 72 1f 54 ed d8 e8 34 24 b7 13 b5 e9 f6 8e db 5b c1 23 be 15 10 2e 3b 70 8a e3 ed 4a 2c 8e 20 eb 35 0a 55 b1 00 37 a1 cc de 0e 18 92 cb 67 58 b1 06 a6 10 20 7a 2c 7d 74 12 92 a0 4a 24 3d 62 99 c3 54 5c cf b5 cf cf 88 4c 02 a6 6c 3c 07 3f f2 8f 45 0c 3a 0e 46 2a d6 42 65 36 a2 f2 f9 8f 1f 7d df 5c 21 6c 5b 52 fc a5 61 38 06 b2 07 82 bb 01

129 Byte, das ist 1 Byte mehr als unsere ursprünglich angegebenen 1024 Bit. Close enough. Diese 129 Byte, als eine einzelne Zahl interpretiert, entsprechen dezimal (Zeilenumbrüche ergänzt):

15052370901306396395988986398928137604234264911648771568548509
91021645103955104561998465724689490878440067992392673029168968
31518446323640562368644004952455932039091356362132097488144531
43274840211112842428025166245595869782489980086453045910472002
0717771621525939289582128731633820466542410920992300641467137

Diese lange Zahl n ist das Produkt zweier Primzahlen, und wenn man die herausfinden kann, hat man die Verschlüsselung geknackt. Das ist aber sehr aufwendig! Dennoch sollte aktuell der Schlüssel viermal so groß sein, um wirklich noch sicher zu sein.

Der private Schlüssel in OpenSSH mit RSA

Der ist leider noch komplizierter:

Die ersten 15 Bytes sind Text, ebenso die letzten, also das mit BEGIN und END darin; es kommt wieder nur auf das dazwischen an. Wir wandeln wieder Base64 in reine Bytes um und machen einen Hexdump:

Für Eilige: Die zwei blauen Blöcke unten sind p und q, die rote Schrift – sie ist zweimal vorhanden – ist das n. Das öffentliche e erscheint zweimal in dunkelgrüner Schrift (010001), das geheime d ist der blassorange Block.

GELB: die ersten 15 Byte sind der Name, da steht „openssh-key-v1“
HELLBLAU: die nächsten 4 Byte sagen, wie viele Bytes der Name der Verschlüsselung der Schlüsseldatei hat, im Beispiel: 00 00 00 04, also vier Byte
- GELB diese 4 Byte, 6e 6f 6e 65, dekodiert „none“ – wir haben den Schlüssel ja nicht verschlüsselt
HELLBLAU: die nächsten 4 Byte sagen, wie viele Bytes der KDF-Name für die Verschlüsselung hat, was das ist, ist uns egal, weil wir ja weiterhin gar keine Verschlüsselung haben; da steht 00 00 00 04, also vier Byte
- GELB: diese 4 Byte, wieder 6e 6f 6e 65, also wieder „none“
HELLBLAU: die nächsten 4 Byte sagen, wie viele Byte wir für KDF-Optionen brauchen, nämlich 00 00 00 00, also gar keine
ORANGE: gibt die Anzahl der folgenden öffentlichen Schlüssel an, es können nämlich mehrere in einer Datei sein, es sind hier aber nur 00 00 00 01, also einer
HELLBLAU: gibt die Länge des folgenden öffentlichen Schlüssels an, hier 00 00 00 97, also die nächsten dezimal 151 Bytes
- HELLGRÜN sind genau diese 151 Bytes, und diese Bytes sind identisch mit dem oben bereits analysierten öffentlichen Schlüssel (dieser Schlüssel besteht, siehe oben, aus verschiedenen Elementen, rot ist die Zahl n)
HELLBLAU: Länge des folgenden Schlüssels, also 00 00 02 00, dezimal 512, also die nächsten 512 Byte (es sind genau die bis zum Ende der Datei)
Alles, was folgt, ist der Inhalt des privaten Schlüssels
- OLIVGRÜN: zweimal Checksummen, die identisch sein müssen
- DUNKLERES HELLGRÜN: der assoziierte öffentliche Schlüssel. Der steht zwar oben auch schon, aber als öffentlicher Schlüssel; hier steht er als Teil des privaten Schlüssels. Die Reihenfolge ist etwas anders: Länge des Namens, Name, Länge von n, n, Länge von e, e
- HELLBLAU: 00 00 00 81 (dezimal 129): Die Länge von d, also die folgenden 129 Byte
  - BLASSORANGE: der Wert von d
  - HELLBLAU: Länge des CRT-Koeffizienten, eine Hilfszahl zum Rechnen, auch inverser Koeffizient, hier 00 00 40 (dezimal 64, also die nächsten 64 Byte)
    - ZIEGELROT: Der Wert des Koeffizienten
  - HELLBLAU: Die Länge von p, also der einen Primzahl, hier 00 00 00 41, also 65 Byte
    - DUNKLERES BLAU: Der Wert von p
  - HELLBLAU: Die Länge von q, also der anderen Primzahl, hier 00 00 00 41, also 65 Byte
    - NOCH DUNKLERES BLAU: Der Wert von q
  - HELLBLAU: Länge des folgenden Kommentars, hier 3 Byte
    - GELB: Der Kommentar, hier als „rau“ zu interpretieren
  - die restlichen 7 Byte (01 02 03 04 05 06 07) sind nur Gefüllsel, damit die Länge des privaten Schlüssels ein Vielfaches von 8 ist; bei verschlüsselten Dateien würde man stattdessen eine Zahl nehmen, die mit der Länge des Schlüssels zusammenhängt

Gerechnet wird mit d und e und n, schneller geht es wohl mit dem Koeffizienten, aber Ausgangspunkt des ganzen sind p und q.

Ausprobieren

Die Probe aufs Exempel: Ergibt p * q wirklich n? Dazu habe ich die oben als Hexzahlen angegebenen p, n und q in Dezimalzahlen umgewandelt und mit Java BigInteger multipliziert:

n

00d65a5622686a8fcf4b567858068df4721f54edd8e83424b713b5e9f68edb5bc123
be15102e3b708ae3ed4a2c8e20eb350a55b10037a1ccde0e1892cb6758b106a6102
07a2c7d741292a04a243d6299c3545ccfb5cfcf884c02a66c3c073ff28f450c3a0e462
ad6426536a2f2f98f1f7ddf5c216c5b52fca5613806b20782bb01

150523709013063963959889863989281376042342649116487715685485099102
164510395510456199846572468949087844006799239267302916896831518446
323640562368644004952455932039091356362132097488144531432748402111
128424280251662455958697824899800864530459104720020717771621525939
289582128731633820466542410920992300641467137

p

00ed176883765bf0872083dfdebd4b916d056b858c66377247e20674c9a39c67d97
12180d16f6f3d173d60cbf1344bf9c82cba41837661221b08ef41c8745b7e45

124174862079667948103381782517912651595614034438078667052106893334
357563787478899866344386934594152379452711017005899750658797812050
52517633390581290597957

q

00e772af5af589002a29b0e7284012ed91e7aac8a1346097a75c845893b1879403e0
5607c04ac38a83c72171948f3b4f8e0e8f5573541ecc960c702c83617be38d

121219147331519608672851127692536618404417242093948619139172300558
785796414360810415733216309185968054165543380649989220715601973074
95867364494501549433741

Was soll ich sagen: Funktioniert.

Sicherheitshalber

Den angegebenen Schlüssel kann man natürlich nicht zur sicheren Verschlüsselung verwenden! Erstens ist er mit 1024 Bit zu kurz, zweitens ist er hier ja öffentlich gemacht.

Andere Formate

Wie gesagt, die gibt es auch noch. Und andere Verschlüsselungsverfahren.

Quellen

https://sshref.dev/#bkdn_rsa_pub

LehrerInnenZimmer

RSA-Verschlüsselung