Kryptographie liefert die Basistechnologie für die Welt der digitalen Kommunikation. Ohne kryptographische Public-Key Verfahren wären sichere E-Commerce Anwendungen, automatische Software-Updates oder sicherer E-Mail-Verkehr undenkbar. In der kommerziellen Praxis wird hauptsächlich das RSA Public-Key Kryptosystem eingesetzt, dessen Sicherheit auf dem Faktorisierungsproblem beruht. Daher ist es von entscheidender Bedeutung, sowohl die Sicherheit von RSA zu evaluieren als auch praktikable Alternativen zum RSA System vorzuschlagen. Das Projekt befasst sich mit Methoden zur Sicherheitsanalyse von RSA und dem zugrundeliegenden Faktorisierungsproblem. Die Ziele des Projektes lassen sich in zwei Bereiche aufteilen:
Sicherheitsanalyse: Um ein Public-Key Kryptosysteme wie RSA anzugreifen, wird dieses in Form von Polynomgleichungen modelliert. Eine Nullstellenbestimmung der Polynome liefert dann die geheimen Parameter des Systems. Zur effizienten Ermittlung der Nullstellen sollen gitterbasierte Lösungsverfahren zum Einsatz kommen. Anwendungsbeispiele sind insbesondere Relaxierungen des Faktorisierungsproblems und RSA-Varianten. Das Projekt erforscht aber auch weitere Anwendungsmöglichkeiten in verwandten Bereichen, wie z.B. der Codierungstheorie.
Algorithmische Weiterentwicklung von Nullstellenverfahren: Gitterbasierte Verfahren zum Lösen von Polynomgleichungen sind dazu geeignet, betragsmäßig kleine Nullstellen effizient zu bestimmen. Ziel des Projektes ist es, optimale Schranken für die Größe der Nullstellen zu erreichen und die Optimalität unter geeigneten Annahmen zu beweisen.
Unter Verwendung der entwickelten Schrankenanalyse werden beweisbar sichere kryptographische Verfahren entwickelt, deren Sicherheit auf der Schwierigkeit des Lösens von polynomiellen Gleichungssystemen jenseits der erreichbaren Schranken beruht.
Publikationen
- Mathias Herrmann, Alexander May
„Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA“In Practice and Theory in Public Key Cryptography (PKC 2010), Lecture
Notes in Computer Science, Springer-Verlag, 2010. - Mathias Herrmann, Alexander May
„Attacking Power Generators Using Unravelled Linearization: When Do We Output Too Much?“ In Advances in Cryptology (Asiacrypt 2009), Lecture Notes in Computer Science, Springer-Verlag, 2009. - Alexander May, Maike Ritzenhofen
„Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint“ In Practice and Theory in Public Key Cryptography (PKC 2009), Lecture Notes in Computer Science, Springer-Verlag, 2009. - Mathias Herrmann, Alexander May
„Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits“ In Advances in Cryptology (Asiacrypt 2008), Lecture Notes in Computer Science, Springer-Verlag, 2008. - Alexander May, Maike Ritzenhofen
„Solving Systems of Modular Equations in One Variable: How Many RSA-Encrypted Messages Does Eve Need to Know?“
In Practice and Theory in Public Key Cryptography (PKC 2008), Lecture Notes in Computer Science Volume 4939, pages 37-46, Springer-Verlag, 2008. - Ellen Jochemz, Alexander May
„A Polynomial Time Attack on RSA with Private CRT-Exponents Smaller Than N^0.073“ In Advances in Cryptology (Crypto 2007), Lecture Notes in Computer Science, Springer-Verlag, 2007.