Weiterentwicklung gitterbasierter Nullstellenverfahren mit Anwendungen für RSA, Faktorisierung und in der Codierungstheorie, Konstruktion beweisbar sicherer kryptographischer Primitiven unter gitterbasierten Annahmen
Zusammenfassung der Projektergebnisse
Das Lösen von Gleichungssystemen ist ein integraler Bestandteil der modernen Kryptographie und Kryptanalyse. Insbesondere haben sich gitterbasierte Methoden zum effzienten Finden betragsmäßig kleiner Nullstellen als wertvolles Werkzeug herausgestellt. In diesem Projekt wurden zum einen solche gitterbasierten Verfahren benutzt, um neue bzw. verbesserte Angriffe auf bekannte Public Key Kryptosysteme zu entwickeln, und zum anderen wurden algorithmische Weiterentwicklungen der Methoden zur Nullstellenbestimmung untersucht. Die behandelten Angriffe beinhalten beispielsweise ein RSA-Broadcast Szenario, bei denen eine Nachricht an viele Empfänger gleichzeitig verschlüsselt wird, oder eine Verallgemeinerung eines berühmten Resultats zur Faktorisierung mit bekannten Bits. Ein algorithmischer Fortschritt konnte durch eine Technik names unravelled linearization erzielt werden. Diese Methode erlaubt es, Beziehungen zwischen verschiedenen vorkommenden Variablen der zu lösenden Gleichung besser auszunutzen. Mittels dieses Ansatzes konnten neue Ergebnisse zur Sicherheit von Zufallszahlengeneratoren,wie z.B. dem Blum-Blum-Shub Generator, sowie einer RSA Variante (RSA-CRT) erzielt werden. Mit der Methode der unravelled linearization konnte ebenfalls ein äußerst wichtiges Resultat der Kryptanalyse von RSA mit einfachen Mitteln bewiesen werden. Im Laufes des Projekts wurden weiterhin neue Modelle untersucht, wie zum Beispiel die Implizite Faktorisierung. Üblicherweise werden zur Untersuchung der Komplexität des Faktorisierungsproblems zunächst Relaxierungen untersucht, die eine effziente Lösung des Problems zulassen. Ein Beispiel einer Relaxierung ist die Bekanntgabe von einigen Bits eines Primfaktors. In diesem Projekt wurde eine schwächere Relaxierung vorgeschlagen, die keine explizite, sondern nur implizite Information über einen Primfaktor liefert. Diese implizite Information ist in Form von weiteren RSA-Moduln gegeben, bei denen Primfaktoren gemeinsame Bits aufweisen. Es konnte gezeigt werden, wann mit dieser Relaxierung eine effziente Faktorisierung möglich ist. In einem weiteren untersuchten Modell bekommt ein Angreifer weder explizite noch implizite, sondern eine fehlerbehaftete Information. Im Projekt wurde das RSA Kryptosystem in diesem Modell untersucht, wobei ein Angreifer eine fehlerhafte Kopie des privaten Schlüssels zur Verfügung hat. Es konnte gezeigt werden, dass sich die Redundanz im geheimen Schlüssel verwenden lässt, um die fehlerhafte Information zu korrigieren.
Projektbezogene Publikationen (Auswahl)
- Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits (Asiacrypt 2008)
Mathias Herrmann, Alexander May
- Solving Systems of Modular Equations in One Variable: How Many RSA-Encrypted Messages Does Eve Need to Know? (PKC 2008)
Alexander May, Maike Ritzenhofen
- Attacking Power Generators Using Unravelled Linearization: When Do We Output Too Much? (Asiacrypt 2009)
Mathias Herrmann, Alexander May
- Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint (PKC 2009)
Alexander May, Maike Ritzenhofen
- Correcting Errors in RSA Private Keys (Crypto 2010)
Wilko Henecka, Alexander May, Alexander Meurer
- Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA (PKC 2010)
Mathias Herrmann, Alexander May
