RSA | MathePrisma

RSA

Den Namen hat das Verfahren von Ronald Rivest (in der Mitte), Adi Shamir (links) und Leonard Adleman (rechts), den drei Männern, die es 1977 erfunden haben.

RSA ist ein asymmetrisches Verfahren, es gibt also einen public key und einen private key. Beide werden über Primzahlen gebildet. Außerdem geht in das Verfahren die Modulo-Rechnung ein. Wenn du dich damit schon auskennst, kannst du einfach weiterlesen, ansonsten wähle

eine kurze Einführung,in der du genau so viel erfährst, wie du zum Verständnis des RSA-Verfahrens benötigst oder
eine etwas längere Einführung, in der du darüber hinaus noch etwas über Kongruenz und Restklassen erfährst.

Schlüsselerzeugung

Für die Erzeugung der beiden Schlüssel wählt man zunächst zwei (große) Primzahlen $p$ und $q$ . Diese werden multipliziert und man erhält $N = p\cdot q$ . Diese Zahl $N$ sowie eine weitere (fast) beliebig wählbare Zahl $e$ (encipher = verschlüsseln) bilden den public key. Eine dritte Zahl $d$ (decipher = entschlüsseln), zu deren Berechnung wir später kommen, ist der private key.

Um mit diesem public key eine Nachricht zu verschlüsseln, muss diese als Zahl vorliegen.

Verschlüsseln

Verschlüsselt wird durch $C = M^e \bmod N$ . Die Zahlen $N$ und $e$ sind der public key. $M$ ist der Klartext (Message), $C$ der verschlüsselte Text (Cipher).

Nehmen wir an, du willst an Alice die Nachricht "L" schicken. Alice's public key sei (187, 7), also $N = 187$ und $e = 7$ .
Das L lautet in ASCII 01001100, das entspricht der Dezimalzahl 76. Die Nachricht lautet also "76".

N = 187, e = 7

Und umgekehrt?