vorherigerMenunächster

RSA

Funktionsweise und Beispiel

Das RSA-Verschlüsselungssystem ist das erste entwickelte asymmetrische Verschlüsselungsverfahren. Die klassischen (und allermeisten in GCC zu findende) Verschlüsselungen sind so genannte symmetrische Verschlüsselungen. Das heißt, dass zur Verschlüsselung und zur Entschlüsselung jeweils das gleiche Schlüsselwort/der gleiche Schlüssel verwendet wird. Das verursacht sicherheitstechnische Probleme. So kann beim Schlüsselaustausch zwischen den beiden kommunizierenden Parteien beispielsweise eine dritte, unbefugte Partei mitlauschen und den Schlüssel abfangen und damit die Nachricht lesen.
Erst in den späten 1970er Jahren gab es erste Bestrebungen, ein Verfahren dagegen zu entwickeln. Drei Mathematiker vom MIT (Massachusetts Institute of Technology), Ronald L. Rivest, Adi Shamir und Leonard Adleman, versuchten zu dieser vergeblich ein neuartiges Verfahren für einen sicheren Schlüsselaustausch zu widerlegen, das Public-Key-Verfahren von Whitfield Diffie und Martin Hellman, welches auch heute noch große Bedeutung hat. Dabei stießen sie zufällig auf eine neue Art der Verschlüsselung: der asymmetrischen. Im Jahr 1977 wurde RSA veröffentlicht. Der Name leitet sich schlicht aus den ersten Buchstaben der Nachnamen der drei Mathematiker ab.

RSA beruht auf einem System, welches mit zwei Schlüsseln funktioniert, dem öffentlichen ("public key") und dem privaten ("private key"). Jeder Teilnehmer an einer verschlüsselten Kommunikation kann sich ein Schlüsselpaar generieren (lassen). Den öffentlichen Schlüssel macht er, wie der Name vermuten lässt, öffentlich. Jeder kann ihn sehen und jeder weiß von wem welcher Schlüssel ist. Den privaten Schlüssel behält der Teilnehmer jedoch für sich. Eine Übertragung funktioniert nun so, dass ein Sender sich den öffentlichen Schlüssel seines Empfängers nimmt. Mit einem bestimmten mathematischen Verfahren kann nun die Nachricht mit diesem Schlüssel verschlüsselt werden. Der Clou an der Sache ist nun aber, dass man die Nachricht mit diesem Schlüssel nicht mehr entschlüsseln und lesen kann. Das kann nur mit dem zugehörigen privaten Schlüssel erfolgen. Hinter dieser "Magie" stecken komplizierte mathematische Verfahren, die genau zu erklären leider den Rahmen sprengen würden. Für mathematisch Interessierte gibt es nach dem Text eine grobe Darstellung des mathematischen Verfahrens
Generell lässt sich sagen, dass diesem Verfahren mehrere Dinge zugrunde liegen, allen voran so genannte Einwegfunktionen. Das sind mathematische Operationen, genauer Funktionen, deren Hinweg sehr leicht berechenbar sind (in der Informationstheorie spricht man von "polynomiell berechenbar"), deren Rückweg allerdings nur mit sehr hohen Aufwänden gelingen kann ("exponentiell berechenbar"). Bei RSA kommt dafür die Modulo-Arithmetik zum Einsatz, grob gesagt also das Rechnen mit Divisions-Resten. Weiterhin spielen Primzahlen eine große Rollen, da sie teilerfremd zu allen anderen Zahlen (außer sich selbst und der 1 natürlich) sind und damit immer bei Divisionen einen Rest hinterlassen. RSA basiert komplett auf Zahlen. Das heißt, möchte man einen Text verschlüsseln, braucht man vorher eine geeignete Form der Darstellung. Bei Computern eignet sich dafür natürlich der ASCII-Code.

Einfach und (hoffentlich) anschaulich gesagt: N = 14 sei das Produkt der beiden Primzahlen P = 2 und Q = 7. Als Verschlüsselungs-Exponent ist E = 11 geeignet. Wenn wir den Buchstaben "B" (Nummer "2" im Alphabet) verschlüsseln, rechnen wir 2 hoch 11 = 2048 und bestimmen den Rest beim Teilen durch N = 14:
2048 = 146 * 14 + 4.
Damit ist "4" das Ergebnis unserer Verschlüsselung. Unser öffentlicher Schlüssel ist das Zahlenpaar (E, N) = (11, 14).
Für den Weg zurück benötigt man zunächst einmal den sogenannten Nebenmodul φ (griech. "phi"; aus den beiden Primzahlen 2 und 7): (2 - 1) * (7 - 1) = 1 * 6 = 6.
E = 11 war eben "geeignet", weil 11 und 6 keinen gemeinsamen Teiler besitzen. Deshalb findet man unter den Vielfachen von 11 eine Zahl D * 11, die beim Teilen durch 6 den Rest 1 hat. 5 * 11 = 55 = 54 + 1 = 9 * 6 + 1. Damit ist D = 5 der gesuchte Exponent. Damit ist unser privater Schlüssel das Zahlenpaar (D, N) = (5, 14).
Entschlüsselung von "4": 4 hoch 5 = 1024, und 1024 geteilt durch N = 14 ergibt als Rest die Zahl "2" und damit den Buchstaben "B". (1024 = 73 * 14 + 2)

Quelle: RSA-Verschlüsselung



Achtung, es folgt der Stoff für die ganz Harten und die, die es ganz genau wissen wollen!:)

Einschub: Modulo-Operation

A mod B = C heißt, dass A bei der Division durch B den Rest C lässt.
Im Beispiel heißt das: 13 mod 5 = 3, da 13/5 = 2 Rest 3; also umgekehrt 5 * 2 + 3 = 13.

Der Knackpunkt an der Sache ist, dass es unendlich viele Möglichkeiten gibt, die Gleichung
A mod 5 = 3
umzukehren, da zum Beispiel 8 mod 5 = 3 (8/5 = 1 Rest 3), genauso wie 13 mod 5 = 3 (13/5 = 2 Rest 3) und 18 mod 5 = 3 (18/5 = 3 Rest 3), usw. Alle Zahlen die man für A eintragen kann, nennt man zusammen genommen die Restklasse von 3 modulo 5. Dies ist ein wesentlicher Bestandteil des Verfahrens. Deshalb wird A stets sehr groß gewählt.

Erzeugung des Schlüsselpaares

Für mathematisch Interessierte: Der öffentliche Schlüssel ist ein Zahlenpaar (e,N) und der private Schlüssel (private key) ein Zahlenpaar (d,N), wobei N bei beiden Schlüsseln gleich ist. Man nennt N den RSA-Modul, e den Verschlüsselungsexponenten und d den Entschlüsselungsexponenten. Diese Zahlen werden durch das folgende Verfahren erzeugt:
  1. Wähle zufällig und stochastisch unabhängig zwei Primzahlen p ungleich q.
  2. Berechne den RSA-Modul: N = P * Q
  3. Berechne die Eulersche φ-Funktion von N: φ(N) = (P - 1)*(Q - 1), auch Nebenmodul genannt
  4. Wähle eine zu φ(N) teilerfremde Zahl E, für die gilt 1 < e < φ(N)
  5. Berechne den Entschlüsselungsexponenten D als "Multiplikativ Inverses" von E bezüglich des Moduls φ(N). Es gilt: E * D = 1 mod φ(N). Das heißt dass, wenn man das Produkt (E * D) durch die Zahl, die bei Schritt 3 heraus gekommen ist, teilt, erhält man den Rest 1
Man erhält also am Ende die Paare (E, N) und (D, N). Die Zahlen P, Q und φ(N) werden nicht mehr benötigt und können nach der Schlüsselerstellung gelöscht werden. Es ist jedoch relativ einfach, diese Werte aus E, D und N zu rekonstruieren. Aus Effizienzgründen wird E in dem Beispiel klein gewählt, üblich ist 2^16 + 1 = 65537. Kleinere Werte von E können zu Angriffsmöglichkeiten führen (zum Beispiel Dechiffrierung mittels "chinesischem Restsatz"). Bei Wahl eines zu kleinen D kann es mit einem auf Kettenbrüchen aufbauenden Verfahren effizient ermittelt werden.

Beispiele

Schlüsselerzeugung

  1. Wir wählen P = 11 und Q = 13 für die beiden Primzahlen. In der Realität verwendet man Primzahlen mit mehreren hundert Stellen Länge; P und Q unterscheiden sich selbst auch um viele Stellen.
  2. Der RSA-Modul ist N = P * Q = 143. Durch möglichst große Primzahlen fällt die Primzahlzerlegung, also das finden von P und Q aus N sehr schwer. Darauf beruht die Sicherheit des Verfahrens. Denn könnte man aus N, welches Bestandteil des öffentlichen Schlüssels ist, seine Primfaktoren P und Q ermitteln, ließe sich dann φ(N) berechnen und damit die Modulo-Operation nachvollziehen, das heißt im Endeffekt, den Text entschlüsseln.
  3. Die eulersche φ-Funktion nimmt damit den Wert φ(N) = φ(143) = (P - 1)*(Q - 1) = 120 an.
  4. Die Zahl E muss zu 120 teilerfremd sein. Wir wählen E = 23. Damit bilden E = 23 und N = 143 den öffentlichen Schlüssel.
  5. Berechnung der Inversen zu E:
    Es gilt: E * D + k * φ(N) = 1 = ggT(E, φ(N)); ggT(E, φ(N)) = 1 heißt, dass der größte gemeinsame Teiler von E und φ(N) gleich 1 ist, die beiden Zahlen sind also teilerfremd zueinander
    --> im konkreten Beispiel: 23 * D + k * 120 = 1 = ggT(23, 120)
    Mit dem erweiterten euklidischen Algorithmus berechnet man nun die Faktoren D = 47 und k = -9, so dass die Gleichung aus dem Beispiel wie folgt aussieht:
    23 * 47 + (-9) * 120 = 1
    D ist der geheime Exponent, während k nicht weiter benötigt wird.

Verschlüsselung

Um eine Nachricht K (also die Zahlendarstellung eines Textes) zu verschlüsseln, verwendet der Absender die Formel
C = K^E mod N
und erhält so aus dem Klartext K den Geheimtext C. K muss dabei kleiner sein als der RSA-Modul N.

Es soll die Zahl 7 verschlüsselt werden. Der Nachrichtenabsender benutzt den veröffentlichten Schlüssel N = 143, E = 23 und rechnet
2 = 7^23 mod 143
Der Geheimtext ist also C = 2.

Entschlüsselung

Der Geheimtext C kann durch modulare Exponentiation wieder zum Klartext K entschlüsselt werden. Der Empfänger benutzt die Formel
K = C^D mod N
mit dem nur ihm bekannten Wert D sowie N.

Für gegebenes C = 2 wird berechnet
7 = 2^47 mod 143
Der Klartext ist also K = 7.

Quelle: Wikipedia

Bedienung

Die RSA-Funktion bei GCC teilt sind in folgende Unterbereiche auf:
  1. RSA Ver-/Entschlüsselung: Ver- und Entschlüsseln mit der RSA Funktion basierend auf E bzw. D und den Primzahlen P und Q. Zu verschlüsselnder Text wird vorher in zeichenweise in ASCII-Werte umgewandelt. Diese Zahlen werden dann verschlüsselt.
  2. E Prüfer: Prüft, ob das gewählte E (Teil des öffentlichen Schlüssels) für die Verwendung bei RSA bei den Primzahlen P und Q verwendet werden kann; ist E teilerfremd zu φ = (P - 1)*(Q - 1)
  3. D Berechner: Berechnet den D als Teil des privaten Schlüssels mittels Primzahlen P und Q, sowie öffentlichem Teilschlüssel E. Achtung: Funktioniert nur bei ausreichend kleinen Primzahlen (unter 5 Stellen), kann lange dauern.
  4. N Berechner: Berechnet RSA-Modul = P * Q
  5. φ Berechner: Berechnet Nebenmodul φ(N) = (P - 1)*(Q - 1)
  6. Primzahl Prüfung: Prüft, ob P und Q wirklich Primzahlen sind


Eingabe "RSA Ver-/Entschlüsselung"
  1. Der zu ver- oder entschlüsselnde Text. Text, der entschlüsselt werden soll ("Geheimtext"), darf nur aus Zahlen bestehen, welche durch ein Leerzeichen voneinander getrennt sind. Auch zu verschlüsselnde Zahlen müssen einzeln durch Leerzeichen getrennt sein.
  2. Schlüssel-Exponent. Bei der Verschlüsselung E, bei der Entschlüsselung D
  3. Erste Primzahl P
  4. Zweite Primzahl Q
  5. Modus-Auswahl: verschlüsseln oder entschlüsseln
  6. Der "Mach den kranken Kram"-Button ;)
Ausgabe
Ver- oder entschlüsselte Werte. Zu verschlüsselnder Text wird vorher in ASCII-Werte umgewandelt.
Bei der Entschlüsselung wird geschaut, ob alle errechneten Zahlen zwischen 32 und 255 liegen. Wenn ja, wird automatisch angenommen, dass das ASCII-Werte sind und die Ausgabe wird in Text umgewandelt.


Eingabe "E Prüfer"
  1. Gewählter Verschlüsselungsexponent E
  2. Erste Primzahl P
  3. Zweite Primzahl Q
  4. Der "Mach den kranken Kram"-Button ;)
Ausgabe
Ist E eine mögliche Zahl oder nicht.


Eingabe "D Berechner"
  1. Gewählter Verschlüsselungsexponent E
  2. Erste Primzahl P
  3. Zweite Primzahl Q
  4. Der "Mach den kranken Kram"-Button ;)
Ausgabe
Berechneten Entschlüsselungsexponten D, sofern berechenbar.


Eingabe "N Berechner"
  1. Erste Primzahl P
  2. Zweite Primzahl Q
  3. Der "Mach den kranken Kram"-Button ;)
Ausgabe
Das RSA-Modul N


Eingabe "φ Berechner"
  1. Erste Primzahl P
  2. Zweite Primzahl Q
  3. Der "Mach den kranken Kram"-Button ;)
Ausgabe
Das Nebenmodul φ(N)


Eingabe "Primzahl Prüfung"
  1. Erste Primzahl P
  2. Zweite Primzahl Q
  3. Der "Mach den kranken Kram"-Button ;)
Ausgabe
Sind P und Q Primzahlen, Ja oder Nein.