Das Lösen von Systemen multivariater Polynomgleichungen über endlichen Körpern ist ein klassisches und fundamentales Problem. Dieses Problem hat wichtige Anwendungen in verschiedenen Gebieten. In der Kryptographie beruht die Sicherheit multivariater Public-Key-Kryptosysteme auf der Schwierigkeit, Systeme multivariater quadratischer Polynomgleichungen über endlichen Körpern zu lösen.

In der Vergangenheit wurden mehrere Algorithmen zum Auffinden von Lösungen multivariater Polynomgleichungen über endlichen Körpern vorgeschlagen. Im Jahr 2000 wurde der XL Algorithmus als Werkzeug für das Lösen solcher Systeme eingeführt. Die Effizienz von XL hängt hauptsächlich von dem Grad ab, bei dem eine Lösung gefunden werden kann. In der Praxis sind Laufzeit und Speicherverbrauch des XL-Algorithmus größer als für den F4-Algorithmus, den besten bekannten Algorithmus für das Lösen von Systemen polynomialer Gleichungen. Der Hauptzweck dieser Arbeit ist es, den XL-Algorithmus zu verbessern und die vorgeschlagenen Verbesserungen an Anwendungen aus der algebraischen Kryptanalyse zu testen.

Eine Möglichkeit, den XL-Algorithmus zu verbessern, besteht darin, neue Polynome niedrigen Grades zu generieren, die im von den ursprünglichen Polynomen erzeugten Ideal liegen. Man hofft, dass diese neuen Polynome von den bestehenden linear unabhängig sind, so dass der Grad, bei dem XL das System lösen kann, minimiert werden kann. Diese Polynome kleinen Grades wurden von Jintai Ding entdeckt und als mutants bezeichnet. Im Prinzip ist die Verwendung dieser mutants die erste Verbesserung des XL Algorithmus, die in dieser Arbeit vorgeschlagen wird. Dies wird im MutantXL Algorithmus und seiner Implementierung erreicht. Eine weitere Verbesserung des MutantXL-Algorithmus namens MXL2 wird ebenfalls in dieser Arbeit beschrieben. MXL2 verwendet zwei wesentliche Verbesserungen über GF(2), die das Lösen von Systemen mit deutlich kleineren Matrizen erlauben als XL und MutantXL. MXL2 wird in dieser Arbeit im Rahmen der algebraischen Kryptanalyse benutzt, um zwei multivariate public-key Kryptosysteme zu brechen, nämlich Little Dragon Two und Poly Dragon.

Die zweite Verbesserung hängt mit der Struktur der von XL generierten Matrizen zusammen. Ab einem gewissen Grad tendieren diese Matrizen dazu, schwach besetzt zu sein. Deshalb ist es bezüglich Speicher und Zeit sehr kostspielig, diese Matrizen mit Gauss-Elimination auf Zeilenstufenform zu bringen. Die Verwendung des Wiedemann-Algorithmus anstatt der Gauss Elimination über GF(256) mit einer skalaren Version des Wiedemann-Algorithmus wurde von Bo-Ying Yang et al. eingeführt. In dieser Arbeit beschreiben wir den Gebrauch des blockweisen Wiedemann-Algorithmus über GF(2) und seine Kombination mit dem XL-Algorithmus, die wir als WXL bezeichnen. Eine Möglichkeit, den WXL Algorithmus zu verbessern, besteht darin, mehr als einen Prozessor zu verwenden. Man nutzt dabei die Tatsache aus, dass der Wiedemann-Algorithmus parallelisiert werden kann. Indem man PWXL, eine parallelisierte Version von WXL, benutzt, können Systeme mit einer größeren Zahl von Variablen gelöst werden. Diese Systeme wurden bisher von keinem anderen algebraischen Algorithmus gelöst. PWXL kann insbesondere Instanzen des HFE Kryptosystems mit 37 quadratischen Gleichungen in 37 Variablen über GF(2) lösen. Diese besitzen den gleichen univariaten Grad wie die von HFE Challenge-2 und können bei Benutzung von 81 Prozessoren in 7.5 Tagen erfolgreich gelöst werden.

Die Kombination der beiden vorgeschlagenen Verbesserungen, der mutant Strategie und des parallelisierten Wiedemann-Algorithmus, ist die dritte Verbesserung. Der erste Teil dieser Verbesserung ist das Erzeugen der mutants durch Benutzung des Kerns einer Matrix, der ebenfalls mit Hilfe des Wiedemann-Algorithmus erzeugt werden kann. Der zweite Teil besteht darin, die durch den Wiedemann-Algorithmus erzeugten mutants für das Lösen des Systems zu verwenden. Das Erzeugen von mutants durch Wiedemann und das Lösen mit MutantXL ist das erste Szenario für den Gebrauch solcher mutants. Das zweite Szenario ist die Verwendung des WMXL Algorithmus, der eine Kombination aus XL-Algorithmus, Wiedemann-Algorithmus und dem Konzept der mutants darstellt, um für strukturierte Systeme eine Lösung auf effektive Weise zu erhalten.

Es werden effiziente und wirksame Verbesserungen des XL-Algorithmus vorgestellt. Diese Verbesserungen basieren einerseits auf dem Konzept der mutants und andererseits auf dem parallelisierten Wiedemann-Algorithmus. Die Bedeutung dieser Verbesserungen wird anhand der Lösung von Systemen multivariater Polynomgleichungen, die ihren Ursprung in der Kryptographie haben, aufgezeigt. Deshalb sollten Designer neuer Kryptosysteme diesen neu vorgeschlagenen Algorithmen Beachtung schenken.