Blog post

asymmetrische Algorithmen: Faktorisierungsproblem von ganzen Zahlen

Anna Lena Fehlhaber

In dem folgenden Abschnitt sollen Algorithmen und Funktionen, die auf dem Faktorisierungsproblem ganzer Zahlen aufbauen, vorgestellt werden.

Nach heutigem wissenschaftlichen Stand ist es nicht möglich, Aussagen darüber zu treffen, ob es einen Algorithmus gibt, der aus einer zusammengesetzten Zahl einen echten Teiler in polynomialer Laufzeit zu ermitteln vermag. Sollte ein solcher Algorithmus entdeckt werden, wären viele asymmetrische Verfahren, die in der angewandten Kryptografie eingesetzt werden, unsicher. Das zugrunde liegende Problem wird der Komplexitätsklasse NP zugeordnet. Eine Garantie für Sicherheit lässt sich daraus nicht ableiten, weil die Existenz eines solchen Algorithmus das zahlentheoretische Berechnungsproblem lösen und die Kryptosysteme, die auf ihnen aufbauen, brechen würde.

Bekannte Algorithmen, die auch in der angewandten asymmetrischen Kryptografie eingesetzt werden, und auf dem Faktorisierungsproblem beruhen, sind der euklidische Algorithmus, die eulersche Phi-Funktion, der kleine fermatsche Satz und die Verallgemeinerung des letztgenannten zum Satz von Euler.

Der euklidische Algorithmus berechnet aus zwei positiven ganzen Zahlen den größten gemeinsamen Teiler. Die Bestimmung erfolgt in mehreren Iterationen, die Anzahl ihrer entspricht in etwa der Anzahl der Ziffern der Eingabewerte. Werden zusätzlich die Linearkombination der beiden Zahlen dargestellt, wird das Verfahren als erweiterter euklidischer Algorithmus bezeichnet, welches Anwendung in der Kryptologie findet. Entsprechend werden in jeder Iteration zwei zu initalisierende natürliche Zahlen auf jeweils die erste, respektive die zweite ganze Zahl multipliziert, und die Produkte zusammenaddiert, wodurch ganzzahlige lineare Gleichungssysteme gelöst werden können. Angewandte Umsetzung findet der Algorithmus als binärer erweiterter euklidischer Algorithmus, der den größten gemeinsamen Teiler durch Subtraktion und Division durch Zweierpotenzen (entspricht der shift Operation) berechnet. Durch die Verlagerung auf Bitoperation und -verschiebung wird der Algorithmus in der Anwendung auf Geräten beschleunigt.

Die eulersche Phi-Funktion betrachtet einen Ring ganzer Zahlen und kann die Anzahl teilerfremder Zahlen zur letztbetrachteten bestimmen. Wenn die Faktorisierung genannter letztbetrachteter Zahl bekannt ist, kann phi durch eine einfache Formel berechnet werden, andernfalls ist die Bestimmung des größten gemeinsamen Teilers derart rechenleistungsintensiv, dass sie für große Zahlen unter heutigen technischen Voraussetzungen als nahezu unmöglich erachtet wird.

Der kleine fermatsche Satz, der ein Sonderfall des verallgemeinerten Satz von Eulers ist, beschreibt eine allgemeingültige Kongruenz von ap zu a(mod p) unter der Bedingung, dass a und p Primzahlen sind. Die Berechnung der Inversen kann durch a-1 , welches sich kongruent, also gleichbedeutend zu ap-2 (mod p) verhält, erfolgen.

Die vorgestellten Algorithmen und das zugrunde liegende Konzept, das Faktorisierungsproblem ganzer Zahlen, werden bei vielen asymmetrischen Verfahren angewendet. Ein bekanntes Beispiel ist das RSA-Kryptosystem. Bis entsprechende Algorithmen gefunden werden, die das Problem in polynomialer Laufzeit zu lösen vermögen, sofern ein solcher Algorithmus überhaupt existiert, sind die Verfahren zum gegenwärtigen Zeitpunkt (Oktober 2017) als sicher einzustufen.

 

Verwendete Literatur:

  • Buchmann (2015): Einführung in die Kryptographie, 6. überarb. Aufl..
  • Paar und Pelzl (2016): Kryptografie verständlich.
  • Ram et al. (2015): Application of Data Structure in the field of Cryptography.
  • Stallings (2013): Cryptography and Network Security: Principles and Practice, 6. überarb. Aufl..

 

 

Comments (2)

Leave a comment

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Prev Post Next Post