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 bei der Division von a durch m. Beispiel: 17 mod 5 = 2. Wird täglich bei Uhrzeitberechnungen (24-Stunden-Format) und der Berechnung von Wochentagen verwendet. In der Programmierung unverzichtbar für das zyklische Umlaufen von Array-Indizes und Hashfunktionen.
Modulare Addition: (a + b) mod m. Modulare Multiplikation: (a × b) mod m. Um einen Überlauf bei der Berechnung großer Zahlen zu vermeiden, wird bei jedem Schritt das Modulo angewendet. Beispiel: (12 + 8) mod 5 = 20 mod 5 = 0.
Bei der Berechnung von a^b mod m werden die Zahlen bei direkter Exponentiation zu groß. Der Algorithmus der schnellen Exponentiation nach dem Teile-und-herrsche-Prinzip ermöglicht eine Berechnung in O(log b) Zeit. Dies ist die zentrale Operation der RSA-Verschlüsselung.
Die modulare Inverse ist das x, für das gilt: (a × x) mod m = 1. Sie existiert nur, wenn a und m teilerfremd sind. Sie wird mithilfe des 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 modularer 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.