Beispiel: Verschlüsselung mit RSA

rsa.md

Beispiel: Verschlüsselung mit RSA

Im Folgenden verschlüssle ich meinen Namen, die Zeichenkette jannis mittels RSA.

Funktionsweise

1. Es werden zwei verschiedene, große Primzahlen p und q zufällig gewählt, wobei die Differenz nicht zu klein sein sollte, und das Produkt der beiden berechnet: n = p * q

2. Dann wird ein zufälliger Wert e ermittelt, der teilerfremd (relativ prim) und kleiner als (p-1) * (q-1) ist. Zu diesem wird das modular Inverse d berechnet, so dass gilt: (e * d) mod ((p-1) * (q-1)) = 1

3. Als öffentlicher Schlüssel gilt dann: e, n und der private Schlüssel ist: d und n. Die Primzahlen p und q können vergessen werden, aber sie sollten niemals bekannt werden.

4. Das RSA-Verfahren verschlüsselt und entschlüsselt nur Zahlen in Zahlen, daher muss der Klartext mit einem öffentlich bekannten Alphabet in eine Zahlenfolge (numerical Encoding) übersetzt werden.

5. Zunächst wird die Nachricht in numerische Blöcke zerlegt, die kleiner als n sein müssen, orientiert an der Bitlänge bedeutet dies: Bitlänge(Block) <= Bitlänge(n) - 1.

6. Zur Verschlüsselung benutzt man die Funktion: C = M^e mod(n)

7. Die Entschlüsselung erreicht man mit: M = C^d mod(n)

Praxisbeispiel

Verschlüsseln

P = 41
Q = 11
n = 451

(p-1) * (q-1) = (41 - 1) * (11 -1) = 400

e = 3
d = 267

Mein Name in Hexadezimal lautet 6a 61 6e 6e 69 73. Wenn ich ihn verschlüssle, ergibt das 178 12c 63 63 167 67 (Hex) bzw. 376 300 99 99 359 103 (Dez).

Entschlüsseln

Wir haben den Chiffre-Text 178 12c 63 63 167 67. Fangen wir beim ersten Buchstaben an.

M = C^d mod(n)
M = 178^10b = 178 ∙d5 ∙c9 ∙106 mod 1c3 = 6a
6a entspricht 106 (dez). Das ist in der Unicore-Tabelle ein kleines `j`.

Ergebnis: j

M = C^d mod(n)
M = 12c^10b = 12c ∙fb ∙17b ∙df mod 1c3 = 61
61 entspricht 97 (dez). Das ist in der Unicore-Tabelle ein kleines `a`.

Ergebnis: ja

M = C^d mod(n)
M = 63^10b = 63 ∙14a ∙181 ∙129 mod 1c3 = 6e
6e entspricht 110 (dez). Das ist in der Unicore-Tabelle ein kleines `n`.

Ergebnis: jan

M = C^d mod(n)
M = 63^10b = 63 ∙14a ∙181 ∙129 mod 1c3 = 6e
6e entspricht 110 (dez). Das ist in der Unicore-Tabelle ein kleines `n`.

Ergebnis: jann

M = C^d mod(n)
M = 167^10b = 167 ∙15a ∙106 ∙5c mod 1c3 = 69
69 entspricht 105 (dez). Das ist in der Unicore-Tabelle ein kleines `i`.

Ergebnis: janni

M = C^d mod(n)
M = 67^10b = 67 ∙ec ∙77 ∙b4 mod 1c3 = 73
73 entspricht 115 (dez). Das ist in der Unicore-Tabelle ein kleines `s`.

Ergebnis: jannis