Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten mit Zugriffsrechten für diese Ausgabe frei zugänglich.

Komplexität: Auf der Jagd nach unknackbaren Funktionen

Ob es überhaupt möglich ist, Daten völlig sicher zu verschlüsseln, hängt von einer der bedeutendsten Fragen der theoretischen Informatik ab: Wie effizient lässt sich beurteilen, ob eine Zeichenfolge zufällig entstanden ist?
Kryptografie-Kauderwelsch

Das Kinderbuch »Alice im Wunderland« steckt voller verschlüsselter Anspielungen auf anspruchsvolle politische Inhalte. Und tatsächlich beschäftigte sich der Autor, Lewis Carroll, der eigentlich Charles Dodgson hieß, auch in seiner Forscherkarriere mit Verschlüsselungen. Wahrscheinlich würde er sich freuen, dass »Alice« inzwischen in der Informationstheorie als Synonym für einen Sender oder einen Empfänger genutzt wird.

Im Jahr 1868 war Dodgson überzeugt, den heiligen Gral der Kryptografie ausgemacht zu haben: Er erklärte die seit dem 16. Jahrhundert verwendete Vigenère-Chiffre (siehe »Vigenère-Chiffre«) als unknackbar. Er konnte das zwar nicht beweisen, aber er hatte gute Gründe für die Aussage. Denn nach mehr als 300 Jahren war seines Wissens noch immer keine effiziente Methode bekannt, um die Chiffre zu brechen.

Es gab nur ein kleines Problem: Fünf Jahre vor Dodgsons wagemutiger Behauptung hatte der preußische Infanteriemajor Friedrich Kasiski die Vigenère-Chiffre in seinem damals kaum beachteten Buch »Die Geheimschriften und die Dechiffrier-Kunst« geknackt.

Kryptografen spielen dieses Katz- und Mausspiel – das Erfinden und Knacken von Codes – schon so lange, wie Menschen geheime Informationen teilen. »Seit Tausenden von Jahren versuchen wir herauszufinden, ob man den Kreislauf durchbrechen kann«, so der Computerwissenschaftler Rafael Pass von der Cornell Tech und der Cornell University …

Kennen Sie schon …

Spektrum - Die Woche – Drohen im Winter Stromausfälle?

Deutschlands Stromnetz scheint am Limit – doch die Netzbetreiber halten die Gefahr von Stromausfällen derzeit für gering. Die Herausforderungen werden nach dem Winter jedoch nur noch größer. Außerdem in dieser Ausgabe: Sind blaue Räume besser als grüne? Und wie erschafft man unknackbare Funktionen?

Spektrum der Wissenschaft – Schutz vor Quantenhackern

»Spektrum der Wissenschaft« berichtet in »Schutz vor Quantenhackern«, wie die Datensicherheit mit neuartigen kryptografische Verfahren gewährleistet werden soll. Außerdem im Heft: Proteine: Strukturbestimmung durch KI; Evolution des Vogelhirns; Wasser in Mondkratern.

Spektrum - Die Woche – Schutz vor Quantenhackern

In dieser Ausgabe von »Spektrum – Die Woche« geht es um einen Wettlauf gegen die Zeit: Programmierer entwickeln Post-Quanten-Algorithmen, um Computer vor den Hackern der Zukunft zu schützen. Ebenso spannend: der Blick zurück in die Geschichte des erfolgreichsten Piraten aller Zeiten: »Black Bart«.

Schreiben Sie uns!

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

  • Quellen

Diffie, W., Hellman, M. E.: New Directions in Cryptography. IEEE Transactions on Information Theory 22, 1976

Impagliazzo, R.: A personal view of average-case complexity. Proceedings of Structure in Complexity Theory. 10th Annual IEEE Conference, 1995

Levin, L. A.: One-way functions and pseudorandom generators. Proceedings of the 17th annual ACM symposium on Theory of computing, 1985

Liu, Y., Pass, R.: On One-way Functions and Kolmogorov Complexity. ArXiv: 2009.11514, 2020