RSA

RSA ist der derzeit wohl populärste Public Key Kryptographiealgorithmus.

Funktionsweise

Beim RSA Algorithmus wird aus einem geheimen Schlüssel, der aus zwei (sehr großen) Primzahlen erstellt wird, ein öffentlicher Schlüssel errechnet. Mit diesem Schlüsselpaar kann eine beliebige Zahl (d.h. jede Art von codierten Daten) nach einem vorgegebenem Algorithmus ver- und entschlüsselt werden. Das Verfahren ist kommutativ, d.h. es ist egal, wie oft eine Datei verschlüsselt worden ist, sie kann in jeder beliebigen Reihenfolge entschlüsselt werden. Eine gute Analogie bietet das abschließen einer Kiste mit Vorhängeschlössern: Man kann zwei verschiedene Schlösser nacheinander verwenden, um die Kiste zu verschließen, trotzdem kann jedes Schloss jederzeit wieder entfernt werden, solange man den (geheimen) Schlüssel besitzt. Dies bedeutet ausserdem, dass eine Verschlüsselung sowohl mit dem öffentlichen als auch dem geheimen Schlüssel geschehen kann. Die Entschlüsselung funktioniert dann eben mit dem jeweils anderen Schlüssel. Da es allerdings sehr leicht ist, aus einem geheimen Schlüssel einen gültigen öffentlichen Schlüssel zu berechnen, sollte man sich genau überlegen, für welche Anwendung man welche Reihenfolge wählt.

Mathematischer Hintergrund

Dieses Kapitel bleibt leer bis zur <Math> Einführung ;)

Anwendungen

Umsetzung unter Linux mit openssl

Um mit openssl einen geheimen RSA Schlüssel zu erstellen, kann man folgendes Kommando verwenden:

openssl genrsa

Damit wird ein Schlüssel erzeugt und im PEM Format auf die Standardausgabe geschrieben. Dies kann man bereits benutzen, um einfache Verschlüsselungen selbst zu implementieren.

Angenommen, die Datei text.txt soll verschlüsselt werden.

[choeger@choeger4 ~]$ cat test.txt
openssl kann viel mehr

Unter public.pem liegt ein Öffentlicher Schlüssel:

[choeger@choeger4 ~]$ cat public.pem
-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBALI8b4vxq8TX7ormU+0M2K0T2yJnj2ym
EjIGZIVVY28/5w0Rvrc8Z4kHcD2U9fPVET3fzmvYZ7XrE96GOi/hfKsCAwEAAQ==
-----END PUBLIC KEY-----

Die Verschlüsselung erfolgt dann so:

[choeger@choeger4 ~]$ cat test.txt | openssl rsautl -encrypt -pubin -inkey public.pem  -out out.data

Anmerkung: openssl rsaut kann nur kurze Daten mit dem RSA Algorithmus verschlüsseln. Für die Verschlüsselung längerer Dateien muss man die Datei in kleine Häppchen aufspalten und Stück für Stück verschüsseln.

Die verschlüsselte Datei sieht nun in binärer Form so aus:

[choeger@choeger4 ~]$ hexdump out.data
0000000 c35c 7be0 5d61 330f 0989 b2d0 8fc2 a67e
0000010 f02e 7a91 75c5 f911 1cf9 4878 13e9 8508
0000020 2e08 6d6a 519c 2de7 ec03 7165 9f5f 6397
0000030 23e7 3384 2a68 7a82 a566 0d57 ef91 60e9
0000040

Um sie wieder zu entschlüsseln:

[choeger@choeger4 ~]$ cat out.data | openssl rsautl -decrypt -inkey private.pem 
openssl kann viel mehr

Signaturen

RSA wird zB von GnuPG verwendet, um emails zu signieren. Dazu geht man wie folgt vor: Eine Datei wird mittels eines geeigneten Hashingverfahrens (z.B. SHA-1) auf eine festgelegte Datenmenge (zB 1024 Byte) 'geschrumpft'. Dieser Hashwert wird dann mittels des geheimen Schlüssels verschlüsselt. Jeder, der einen öffentlichen Schlüssel zu diesem geheimen Schlüssel besitzt, kann nun den Hash entschlüsseln und ihn mit einem selbsterstellten Hash der übermittelten Datei vergleichen. Sind beide identisch, ist die Wahrscheinlichkeit, dass die übermittelte Datei so vom Absender kam, genauso groß wie die Wahrscheinlichkeit, dass nur der Absender den geheimen Schlüssel besitzt und die Hash Funktion kollisionsfrei für 'sinnvolle' Daten ist.