RSA-Faktorisierung

Im Rahmen eines Bogy-Praktikums hat Finn Schmidt sich mit dem
RSA-Verfahren befasst, einem Vertreter der Asymmetrischen
Verschlüsselungsverfahren und eine elementare Basis für private
Kommunikation- besonders angesichts der globalen Überwachung, die
2013 nochmal besonders in die öffentliche Aufmerksamkeit rückte.
Elementare Rechte, wie das im Grundgesetz gesicherte Recht auf
das Postgeheimnis bei einem verschlossenen Briefumschlag, kann
man in elektronischen Medien nur durch Kryptoverfahren erreichen.


Aus mathematischer Sicht sind Primzahlen grundlegende Bausteine,
aus denen RSA-Schlüsselpaare, bestehend aus einem privaten und
einem öffentlichen Schlüssel, bestimmt werden. Dazu werden zwei
große Primzahlen multipliziert- und das Produkt im öffentlichen
Schlüssel preisgegeben. Dies schützt die einzelnen Faktoren, da
die Rückrechnung in Form einer Faktorisierung viel aufwendiger
als die Multiplikation ist. Zur Betrachtung der Sicherheit des
Verfahrens, muss man genau diese Verfahren untersuchen.


Ein effizientes Faktorisierungsverfahren ist das Quadratische
Sieb, das auf der dritten binomischen Formel basiert. Dazu sucht
man zwei Quadratzahlen, deren Differenz die zu faktorisierende
Zahl ergibt, da man so eine Faktorisierung erhält. Ein noch
besseres Verfahren verspricht der Shor-Algorithmus, jedoch
benötigt dieser zur effizienten Ausführung einen Quantencomputer.


Das RSA-Verfahren ist bei Betrachtung von Faktorisierungsmethoden
auf gängigen Digitalrechnern in dem Sinne sicher, dass die
Faktorisierung um Größenordnungen aufwendiger als die
Schlüsselerzeugung ist. So kann jedes gewünschte
Sicherheitsniveau erreicht werden. Dies ändert sich jedoch sobald
Quantencomputer in beliebiger Größe realisiert werden können, da
die Faktorisierung mit dem Shor-Algorithmus unmittelbar erfolgen
kann. Außerdem werden heute sicher verschlüsselte Texte eventuell
mit den leistungsfähigeren Computern der Zukunft in einigen
Jahren relativ leicht zu entschlüsseln sein.
Literatur und Zusatzinformationen

Koziol et al: RSA – Primzahlen zur Verschlüsselung von
Nachrichten, Skript und Arbeitsblätter, Fraunhofer Institut
Algorithmen und Wissenschaftliches Rechnen SCAI und
Mathematisches Institut der Universität zu Köln.

A. Beutelspacher, J. Schwenk, K.-D. Wolfenstetter: Moderne
Verfahren der Kryptographie, Vieweg, 2006.

Bogy-Praktikum G. Thäter: Wasserraketen. Gespräch mit G.
Thäter im Modellansatz Podcast, Folge 49, Fakultät für
Mathematik, Karlsruher Institut für Technologie (KIT), 2015.


S. Ritterbusch: Digitale Währungen. Gespräch mit G. Thäter im
Modellansatz Podcast, Folge 32, Fakultät für Mathematik,
Karlsruher Institut für Technologie (KIT), 2014.