Verschlüsselungen und das Problem mit gezinkten Primzahlen

Verschlüsselung

Viele heute gebräuchlichen Verschlüsselungssysteme bauen auf möglichst komplexe mathematische Berechnungen auf, deren Lösung zu lange dauert, wenn man die zahlreichen Möglichkeiten durchprobieren muss. Zwei solche Verfahren, die auf die Berechnung von diskreten Logarithmen beruhen, wären die Diffie-Hellman-Methode (verwendet etwa beim Aufbau von HTTPS Verbindungen) oder der DSA Algorithmus (etwa für digitale Signaturen). Diese beiden Methoden nutzen, dass bei gegebener Grundzahl g und Primzahl p der Ausdruck g^a mod p leicht zu berechnen ist, aber der umgekehrte Weg von g^a auf a zu schließen extrem aufwändig ist. Er ist umso mühsamer je größer die gewählte Primzahl ist, wobei diese Primzahl immer bekannt ist.

Primzahlen

Aber die Größe der Primzahl p ist nicht das einzige Kriterium für die Komplexität der Verschlüsselung. Denn auch wenn das Auffinden von a bei gegebenem Ausdruck g^a sehr aufwändig ist, so gibt es doch auch Methoden bzw. Algorithmen, wie man diese wieder herausfiltern kann.

NFS und SNFS

Zwei solche Algorithmen wären der NFS (Number Field Sive) und der SNFS (Special Number Field Sieve)  Algorithmus. Von diesen beiden ist der SNFS Algorithmus bei weitem schneller, nutzt aber zur Erzeugung der Primzahl zwei "geheime" irreduzible Polynome, die mit der Primzahl auf eine bestimmte Art und Weise in Verbindung stehen, was den Algorithmus anfälliger macht. Bei der Benutzung dieses Algorithmus muss man also nur die geheimen Zutaten konstruieren und im Anschluss daran eine dazu passende Primzahl finden. Mit den so gefundenen Primzahlen lassen sich dann viel schneller diskrete Logarithmen berechnen als mit dem NFS Algorithmus unter der Voraussetzung, dass man die geheimen Zutaten kennt. Und genau da liegt das Problem. Von einer beliebigen Primzahl p zu den geheimen Zutaten zu gelangen ist zwar nur in den seltensten Fällen möglich, aber was wäre, wenn man Primzahlen in Umlauf bringt, deren geheime Zutaten der Erzeugung man bereits weiß?

Das Problem mit den Primzahlen

Um sicherzustellen, dass verschlüsselte Daten nicht rasch mittels SNFS Algorithmus entschlüsselt werden können, ist es somit wichtig, dass es sich bei den verwendeten Primzahlen um solche handelt, bei denen nicht andere die geheimen Zutaten besitzen. Oder anders gesagt: Wenn es jemandem gelingen würde, Primzahlen in Umlauf zu bringen, die vorher mittels der beschriebenen geheimen Zutaten erzeugt wurden, so hätte dieser jemand leichtes Spiel Daten unter Verwendung des SNFS Algorithmus schnell zu entschlüsseln. Dieser jemand wäre dann quasi im Besitz einer Hintertür. Man muss also sicherstellen, dass es sich bei den verwendeten Primzahlen um saubere und nicht gezinkte Primzahlen handelt.

Saubere Primzahlen

Aber wie kann man sicherstellen, dass Primzahlen, die man für die Verschlüsselung verwenden möchte, nicht gezinkt sondern sauber sind? Am Leichtesten geht dies, wenn man offenlegt, wie man zu einer Primzahl gekommen ist. Dies passiert in der Regel durch Verwendung von sogenannten pseudo-zufälligen Verfahren. Dabei wird nach Eingabe eines Startwerts mit Hilfe eines dokumentierten und nachvollziehbaren Algorithmus eine Primzahl erzeugt. Der Startwert wird zufällig gewählt und veröffentlicht und im Anschluss daran kann jede_r nachprüfen, wie die Primzahl zustande gekommen ist. Eine andere Variante wäre die nachvollziehbare Herleitung einer Primzahl aus einer Zahl, die über jeden Zweifel erhaben ist von Menschen erfunden worden zu sein, wie etwa die Zahlen pi und e. Solcherart gewonnene Primzahlen findet man zum Beispiel in der Oakley Groups, einer Sammlung von Primzahlen, die sich aus den Nachkommadarstellungen der Zahl pi ableiten lassen.

2048 statt 1024

Am Leichtesten ließe sich das Problem jedoch lösen, wenn man nicht mehr Primzahlen mit 1024 Bit sondern welche mit mindestens 2048 Bit verwenden würde. Dann wäre es auch egal, wenn man gezinkte Primzahlen verwendet, da selbst der SNFS Algorithmus für deren Entschlüsselung mit den heutigen technischen Mitteln mehrere Jahrhunderte benötigen würde. Und wenn sich die Technik wieder weiterentwickelt, dass diese Zeitspanne auch wieder deutlich geringer wird? Was macht man dann? Richtig! Man verwendet Primzahlen, die noch größer sind.

Links:

• heise.de: Zahlen, bitte! Von unbescholtenen und teuflischen Primzahlen
• heise.de: Gezinkte Primzahlen ermöglichen Hintertüren in Verschlüsselung
• heise.de: Verflixte Primzahlen: Eine subtile Hintertür im Diffie-Hellman-Schlüsselaustausch
• derstandard.at: Manipulierte Primzahlen als Gefahr für Verschlüsselung
• eprint.iacr.org: Link zum Paper "A kilobit hidden SNFS discrete logarithm computation"
• tools.ietf.org: The OAKLEY Key Determination Protocol