RSA | MathePrisma

Entschlüsseln

Zum Entschlüsseln benötigt man den geheimen Schlüssel $d$ .

Entschlüsselt wird damit durch $M = C^d \bmod N$ .

Angenommen, dein öffentlicher Schlüssel ist (187, 7), also $N = 187$ , $e = 7$ . Du erhältst die damit verschlüsselte Nachricht $C = 142$ . Um diese zu entschlüsseln, benötigst du deinen private key. Der ist in diesem Fall $d = 23$ . Wie $d$ berechnet wird, kommt später.

N = 187, e = 7, d = 23

M < N !!!

Das funktioniert allerdings nur, wenn die Nachricht $M$ (als Zahl) kleiner ist als $N$ .

Probier es mit dem Taschenrechner aus obiger Aufgabe aus. Verschlüssele verschiedene Zahlen und entschlüssele sie direkt wieder. Versuche Zahlen, die kleiner sind als $N = 187$ und Zahlen, die größer sind!

Das ist allerdings keine Einschränkung. Will man eine Nachricht verschlüsseln, deren Zahlenwert zu groß ist, so teilt man sie in kleinere Blöcke und verschlüsselt jeden Block einzeln.

blockweise

Um es einfach zu halten, codieren wir: Leerzeichen = 00, A = 01, B = 02, ..., Z = 26.
Mit dem Schlüssel (N, e) = (2773, 17) wird die Nachricht:

$05 \; 18 \; 18 \; 01 \; 18 \; 05 \; 00 \; 08 \; 21 \; 13 \; 01 \; 14 \; 21 \; 13 \; 00 \; 05 \; 19 \; 20$

in 3er-Blöcke geteilt (die sind sicher kleiner als N):

$051 \; 818 \; 011 \; 805 \; 000 \; 821 \; 130 \; 114 \; 211 \; 300 \; 051 \; 920$

und verschlüsselt zu (mit führenden Nullen auf vier Stellen aufgefüllt):

$2236 \; 2000 \; 1725 \; 0542 \; 0000 \; 0436 \; 1988 \; 1684 \; 1064 \; 0567 \; 2236 \; 0948$

Aber wie berechnet man denn nun den private key $d$ ?