Modulare Addition, Subtraktion, Multiplikation, Exponentiation und Inverse. Lernen Sie die modularen Operationen kennen, die bei der RSA-Verschlüsselung verwendet werden.
Die Modulo-Operation (a mod m) ist der Rest der Division von a durch m. Beispiel: 17 mod 5 = 2. Wird täglich bei Uhrzeitberechnungen (24-Stunden-System) und bei der Berechnung des Wochentags verwendet. In der Programmierung essenziell für das zyklische Umlaufen von Array-Indizes und für Hashfunktionen.
Modulare Addition: (a + b) mod m. Modulare Multiplikation: (a × b) mod m. Um bei der Berechnung großer Zahlen einen Überlauf zu vermeiden, wird bei jedem Schritt der Modulo genommen. Beispiel: (12 + 8) mod 5 = 20 mod 5 = 0.
Bei der Berechnung von a^b mod m werden die Zahlen bei direkter Potenzierung zu groß. Der Schnellpotenzierungs-Algorithmus nach dem Prinzip „Teile und herrsche“ ermöglicht eine Berechnung in O(log b) Zeit. Dies ist die zentrale Operation der RSA-Verschlüsselung.
Die modulare Inverse ist x, sodass (a × x) mod m = 1 gilt. Sie existiert nur, wenn a und m teilerfremd sind. Sie wird mit dem erweiterten euklidischen Algorithmus in O(log m) Zeit berechnet. Wird bei der Entschlüsselung und bei Bruchrechnungen verwendet.
RSA ist ein Public-Key-Kryptosystem, das auf modularer Exponentiation und Inverse basiert. Verschlüsselung: c = m^e mod n, Entschlüsselung: m = c^d mod n. Es beruht auf der Schwierigkeit, n, das Produkt zweier großer Primzahlen, zu faktorisieren.