Vor einigen Tagen laß ich in meinem Mathebuch im Kapitel Kryptographie etwas über das RSA-Verfahren. Ich wollte daraufhin versuchen, diesen nachzustellen.
Die Formeln bzw. eine grobe Anleitung war dort gegeben.
Was ist RSA
RSA ist ein, nach den Entwicklern Rivest, Shamir und Adleman benannter kryptographischer Algorithmus, welcher mit öffentlichen (public) und privaten (private) Schlüsseln arbeitet. Das ganze System asymmetrisch aufgebaut, d.h. man nutzt den öffentlichen Schlüssel zum Verschlüsseln einer Nachricht, welche nur mit dem geheimen privaten Schlüssel entschlüsselt werden kann. Die Stärke basiert darauf, dass man den privaten Schlüssel nur mit sehr hohem technischen Aufwand zurückrechnen kann.
Wie funktioniert RSA?
Zunächst müssen alle Kommunikationspartner ein Schlüsselpaar bestehend aus öffentlichem und privatem Schlüssel erstellen.
Der private Schlüssel muss geheim gehalten werden, denn damit ist die Entschlüsselung möglich. Die öffentlichen Schlüssel können problemlos unter den Kommunikationsteilnehmern ausgetauscht werden.
Möchte nun Alice eine Nachricht an Bob schicken, so muss Sie Bobs öffentlichen Schlüssel kennen.
Sie verschlüsselt die Nachricht mit Bobs öffentlichen Schlüssel.
Die Nachricht kann dann über einen ungesicherten Kanal an Bob übertragen werden.
Bob entschlüsselt die Nachricht mit seinem privaten Schlüssel.
Christopher, welcher die verschlüsselte Nachricht abfangen konnte, kann damit nichts anfangen, denn er besitzt nicht Bobs privaten Schlüssel. Dieser lässt sich auch nur schwer zurückrechnen.
Mathematik hinter RSA
Zu Anfang benötigt man zwei große Primzahlen mit mehreren Hundert stellen, wobei gelten muss, dass p != q.
Primzahl p
Primzahl q
Daraufhin kann man das RSA-Modul N und Phi(N) berechnen:
N = p*q
Phi(N) = (p-1)*(q-1)
Es folgt die Bestimmung einer Zahl e, welche zu Phi(N) teilerfremd ist. Dies geschieht mithilfe des ggT, und dabei gilt 1 < e < Phi(N):
- ggT(e, Phi(N)) = 1
e und N bilden den öffentlichen Schlüssel.
Zuletzt fehlt noch der private Schlüssel d, welches ein multiplikatives Inverses zu e ist:
- ed + kPhi(N) = 1 = ggT(e, Phi(N))
Damit hat man alle Voraussetzungen für eine Ver-/Entschlüsselung geschaffen.
Eine Nachricht T verschlüsselt man mit dem öffentlichen Schlüssel folgendermaßen:
- C = Te % N
Das Chiffrat C lässt sich mit dem privaten Schlüssel wieder entschlüsseln:
- T = Cd % N
Das war dann auch schon der RSA-Algorithmus.
Meine Implementierung in Python
Im Großen und Ganzen besteht der RSA-Algorithmus aus größten gemeinsamen Teilern (ggTs), Potenzen, und Modulos.
Ich gebe zu, dass der Code nicht der schönste ist, da man einiges optimieren kann, z.B. ggT per Rekursion (was komischweise immer nur 0 brachte, da es einen Durchlaufen zu viel tat); die Funktion zur Berechnung des privaten Schlüssels,…
Es soll jedoch nur zum Lernzweck und Nachvollzug des RSA-Algorithmus dienen.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
|
Überarbeitung durch Ghost 21.10.2012
Den Code findet ihr auf GitHub.
Sollte jemand Optimierungen an dem Code durchführen, würde ich mich über eine Benachrichtigung freuen.
Gruß
gehaxelt