Blog post

Effizienz von Algorithmen

Anna Lena Fehlhaber

Die Verwendung kryptologischer Algorithmen geht mathematisch mit dem Problem der Abschätzbarkeit einher. Die Bestimmung der Effizienz von Algorithmen beim Design dieser wird dadurch notwendig.

Bevor kryptografische oder kryptanalytische Algorithmen generiert werden, wird ihr Berechnungsaufwand und ihr Ressourcenverbrauch abgeschätzt. Diese Abschätzung wird durch die asymptotische Notation vereinfacht und kann das Verhalten von Algorithmen beschreiben.

Effizienzbestimmung

Zur Beschreibung des asymptotischen Verhaltens einer Funktion wird die Landau-Notation verwendet. Mit dieser lässt sich die Effizienz des Algorithmus analysieren. Mit ihr kann die Laufzeit, die in Abhängigkeit zur Länge der Eingabe dargestellt wird, für drei verschiedene Szenarien angegeben werden: Das Worst-Case, das Average-Case, und das Best-Case Szenario.

Entsprechend lassen Aussagen über die Landau-Notation des Worst-Case Szenarios Ableitungen über Garantien zu, nach der die Laufzeit des analysierten Algorithmus immer und in jedem Fall kleiner oder gleich der angegebenen Laufzeit des genannten Szenarios ist.

Die Diskrepanzen zwischen Worst- und Best-Case Szenarien sind zum Teil immens. Insbesondere probabilistische Algorithmen beinhalten nicht zwingend eine Garantie, dass sie überhaupt ein korrektes Ergebnis abliefern.  Wenn diese Garantie für einen probabilistischen Algorithmus gegeben werden kann, wird dieser Las-Vegas-Algorithmus, andernfalls, entsprechend wenn der Algorithmus lediglich einer Erfolgswahrscheinlichkeit unterliegt, Monte-Carlo-Algorithmus genannt. Jeder Las-Vegas-Algorithmus kann in einen Monte-Carlo-Algorithmus umgeformt werden, die entgegengesetzte Umformung ist möglich, gestaltet sich allerdings in der Umsetzung schwieriger.

Die Angabe der Szenarien kann unter Einbezug der Parameterlänge erfolgen, und bezieht das Wachstum der Laufzeit in Abhängigkeit zur Länge der Eingabe mit ein. Diese wird als Referenz zur Bestimmung der Effizienz von Algorithmen verwendet und lässt eine Vergleichbarkeit dieser zu.

Sicherheit von Algorithmen

Für die meisten Algorithmen, bedeutungslos ob symmetrisch kryptografische oder asymmetrisch kryptografische Verschlüsselungsverfahren, und auch Hash-Funktionen, gilt, dass sie lediglich berechenbarkeitstheoretisch sicher sind. Das heißt, dass die Wahrscheinlichkeit, dass diese zu brechen sind, sehr gering ist. Eine Ausnahme bildet die OTP-Verschlüsselung, die auch informationstheoretisch sicher ist.

 

Verwendete Literatur:

  • Beutelspacher et al. (2012): Kryptografie in Theorie und Praxis. Mathematische Grundlagen für elektronisches Geld, Internetsicherheit und Mobilfunk.
  • Blahut (2014): Cryptography and secure communication.
  • Buchmann (2015): Einführung in die Kryptographie, 6. überarb. Aufl..
  • 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