zufällige Doku

Mathematik – Kryptographie


Die Sicherheit der faktorisierungsbasierten Public-Key-Kryptographie liegt in der Verwendung eines Produkts aus großen Primzahlen, welches als öffentlicher Schlüssel dient. Der private Schlüssel besteht aus den dazugehörenden Primfaktoren bzw. davon abgeleiteten Werten. Die Zerlegung eines hinreichend großen öffentlichen Schlüssels gilt aufgrund der mathematisch sehr aufwendigen Faktorisierung als nicht praktikabel. Anschaulich gesprochen ist es schwierig (rechenaufwändig) die Teiler z. B. der Zahl 1073 zu finden: dies geht mehr oder weniger nur durch systematisches Ausprobieren von 3,5,7, und so weiter (siehe z. B. Sieb des Eratosthenes), was bei großen Zahlen einen beträchtlichen Aufwand bedeutet. Kennt man hingegen die Teiler (29 und 37), ist es leicht, die Zahl 1073 durch eine einfache Multiplikation zu erzeugen. Multiplikation und Faktorisierung sind also unterschiedlich rechenaufwändig, was bei genügend großen Zahlen dazu führt, dass die Faktorisierung auch auf einem Supercomputer tausende Jahre dauern würde. Diese Asymmetrie macht man sich in der Public-Key Architektur zu Nutze. Kryptographisch sichere Verfahren sind dann solche, für die es keine bessere Methode als das Ausprobieren von derartig vielen Möglichkeiten gibt, dass es bei heutigem oder zukünftig zu erwartender Rechenleistung im Mittel viele tausend Jahre dauert, einen privaten Schlüssel zu errechnen, bzw. eine Nachricht zu dekodieren. Das heißt, dass de facto der private nicht aus dem öffentlichen Schlüssel errechnet werden kann und daher eine Nachricht zwar ver-, aber nicht entschlüsselt werden kann, sofern man nur den öffentlichen Schlüssel besitzt. Die derzeit wichtigsten Public-Key-Verfahren (RSA, Verfahren, die auf dem Diskreten Logarithmus in endlichen Körpern beruhen (z. B. DSA oder Diffie-Hellman)), und Elliptic Curve Cryptography könnten theoretisch durch so genannte Quantencomputer in Polynomialzeit gebrochen werden und somit ihre Sicherheit verlieren. Eine weitere theoretische Methode für Angriffe auf kryptographische Verfahren wäre die Verwendung von DNA-Computern. Diese könnten wegen der extrem großen Anzahl der darin parallel arbeitenden „Recheneinheiten“ (DNA-Fragmente) bestimmte symmetrische Verfahren effektiver als herkömmliche Computer brechen.

#Mathematik #Harald Lesch