Blog post

asymmetrische Algorithmen: Diskretes Logarithmusproblem

Anna Lena Fehlhaber

Einige asymmetrische Verfahren nutzen ein mathematisches Phänomen, das als diskretes Logarithmusproblem bekannt ist. Für dieses wird vermutet, dass keine effizienten Algorithmen, d.h. Logarithmen, die das Problem in polynominaler Zeit lösen können, existieren.

Als solches kann das diskrete Logarithmusproblem bis zu dem Zeitpunkt, zu dem effiziente Algorithmen für dessen Lösung gefunden sind, als Einwegfunktion bezeichnet werden. Die Exponentialfunktion exp a mod n ist für die Basen a die mathematische Funktion, auf der die beschriebenen kryptografisch asymmetrischen Verfahren basieren.

Die diskrete Exponentialfunktion kann relativ einfach durch Potenzierung und modular Reduktion generiert werden, das Brechen dieser hingegen gestaltet sich unter bestimmten Bedingungen komplex. Zur Realisierung dieses Unterfangens müssen, unter Berücksichtigung gegenwärtiger Algorithmen, fast alle Werte der diskreten Exponentialfunktion manuell berechnet und geprüft werden, um den diskreten Logairthmus einer Restklasse zu bestimmen.

Bei kleinen Zahlen ist das durchaus zu bewerkstelligen, bei größeren Zahlen hingegen steigt die Laufzeit mindestens exponentiell, etwa unter Verwendung des Baby-Step-Giant-Step Verfahrens, welches auch als Tonelli-Shanks Algorithmus bekannt ist. Wenn bestimmte Komponenten bekannt sind, etwa die Primfaktorzerlegung der Gruppenordnung, gibt es hingegen effiziente Algorithmen, die das diskrete Logarithmusproblem unter dieser Bedingung zu lösen vermögen.

Verwendete Literatur:
  •  Pommerening (2000): Der diskrete Logarithmus.
  • Shoup (2007): A Computational Introduction to Number Theory and Algebra.
  • Ziegenbalg et al. (2016): Algorithmen von Hammurapi bis Gödel. 4. überarb. Aufl..

Comments (1)

Leave a comment

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

Prev Post Next Post