Wie geht eigentlich RSA?

RSA ist ein Verschlüsselungsverfahren, welches zum Beispiel bei PGP verwendet wird.

Die Idee hinter RSA ist, dass Eine Nachricht mit einem Schlüssel nur verschlüsselt werden kann, jedoch nicht mit dem gleichen wieder entschlüsselt. Für die Entschlüsselung wird wiederum ein anderer Schlüssel benötigt.

Um dies zu bewirken, werden Einwegfunktionenverwendet. Das sind Funktionen, bei denen die eine Richtung leicht, die andere jedoch schwer (bzw. sogar unmöglich) zu berechnen ist. Beispiele dafür sind

  • Multiplikation von zwei Primzahlen
  • Modulo Rechnungen (=Teilen mit Rest)

Diese beiden Methoden werden bei RSA verwendet um Texte zu verschlüsseln.

Der kompliziertere Teil von RSA ist nicht das Eer- oder Entschlüsseln, sondern die Erzeugung des Schlüsselpaares.

Im folgenden werde ich versuchen das möglichst einfach darzustellen (Achtung! Mathematik!):

Das Zeichen % steht für Modulo.

  1. Zwei zufällige Primzahlen p und q werden gewählt
  2. Der “RSA-Modul N” ist p*q
  3. Die Eulersche Funktion ergibt für N= (p-1)*(q-1)
  4. Nun wird zu dem Ergebnis aus 3 eine Teilerfremde Zahl e gefunden
  5. e und N bilden den öffentlichen Schlüssel
  6. Nun muss noch ein d gefunden werden, wobei gelten soll e*d+k*(Ergebnis aus 3)=1
    Da es sich nur um ganze Zahlen handelt, ist es relativ einfach eine mögliche Lösung zu finden.
  7. d und N bilden den privaten Teil des Schlüssels.

Nun zum Ver- und Entschlüsseln einer Nachricht:

Hierbei sind

  • M die Entschlüsselte Nachricht
  • C die Verschlüsselte Nachricht

C = (M^e)%N

M = (C^d)%N

Dieses einfache aber geniale Grundprinzip wird in der Informationstechnologie verwendet um Nachrichten sicherzu verschlüsseln, da der öffentliche Teil des Schlüssels an jeden weitergegeben werden kann. Ein Angreifer kann ämlich durch die Verwendung der Einwegfunktion beim Schlüsselgenerieren den privaten Schlüssel nicht aus dem Öffentlichen extrahieren.

Lukas Schulz

 

One thought on “Wie geht eigentlich RSA?”

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.