Home | english | Impressum | Sitemap | Intranet | KIT
Institut für Angewandte und Numerische Mathematik 4: Numerische Simulation, Optimierung und Hochleistungsrechnen

Sekretariat
Kollegiengebäude Mathematik (20.30)
Zimmer 3.039

Adresse
Karlsruher Institut für Technologie (KIT)
Institut für Angewandte und Numerische Mathematik
Englerstrasse 2
76131 Karlsruhe

Öffnungszeiten:

Tel.: +49 721 608 - 42062

Fax.: +49 721 608 - 44178

Der Modellansatz: Modell070 - RSA-Faktorisierung

modellansatz.de/rsa-faktorisierung

Bei genauem Hinsehen finden wir die Naturwissenschaft und besonders Mathematik überall in unserem Leben, vom Wasserhahn über die automatischen Temporegelungen an Autobahnen, in der Medizintechnik bis hin zum Mobiltelefon. Woran die Forscher, Absolventen und Lehrenden in Karlsruhe gerade tüfteln, erfahren wir im Modellansatz Podcast aus erster Hand.

Der Modellansatz: RSA-Faktorisierung. Illustration und Komposition: Sebastian Ritterbusch. Rot sind Primzahlen, blau Produkte zweier unterschiedlicher Primzahlen.

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



Diese Podcast-Episode zitieren