On Friday 16 November 2007, Frank Gerlach wrote:
Meines wissens hat ein schlauer mathematiker bewiesen dass das verschlüsselung mit dem one -time-pad nicht zu knacken ist.
Das ist einer von zwei bekannten Algorithmen, die beweisbar sind (der zweite ist "secret sharing" via Gleichungssystem).
Man hat leider noch keine Methode gefunden im allgemeinen Fall die Sicherheit eines Algorithmus beweisen zu können. Man kann nur versuchen sie zu knacken.
Gilt damit auch dass alle anderen verfahren grundsätzlich zu knacken sind, wir lediglich die nötige mathematik noch nicht kennen ?
Zu einem großen Teil ist die Mathematik bekannt, aber oft nicht praktikabel. Oder sie muss noch weiterentwickelt werden um praktikabel zu werden.
Interessant ist natürlich nur die frage, ob man beweisen kann, dass es eine methode gibt, welche wesentlich weniger rechenaufwendig ist als den schlüsselraum zu durchsuchen.
Das ist genau das was ein Kryptanalytiker macht.
Es gibt zwei Kriterien:
a) Gibt es eine Methode, die effizienter ist als "brute force" (=alles durchsuchen)? Dann nennt man das "theoretisch geknackt".
b) Ist die effizienteste Methode, inklusive brute force, auf existenten Rechnern in akzeptabler Zeit anwendbar? Dann nennt man das "praktisch geknackt".
Das was die Kryptanalytiker interessiert ist a). Das was die Geheimdienste und andere Angreifer interessiert ist b).
Beispiel:
Brute force auf SHA-1 ist nicht praktikabel. Es gibt einen Angriff, der schneller als brute force arbeitet, also ist SHA-1 theoretisch geknackt. Inzwischen ist dieser Angriff so weit entwickelt dass er für bestimmte Szenarien eine Komplexität von 2^63 Operationen hat - das kann ein guter Rechencluster schon in ein paar Tagen durchrechnen. Für diese Szenarien ist SHA-1 also auch praktisch geknackt.
Gegenbeispiel:
DES hat eine Schlüssellänge von 56 bit. Das kann jeder Rechner innerhalb von Tagen, Spezialrechner innerhalb von Stunden durchprobieren. Bis vor ein paar Jahren gab es keine besseren Angriffe als brute force, also war DES praktisch geknackt aber theoretisch sicher. Inzwischen gibt es ein paar theoretische Angriffe, die aber immer noch nicht sehr praktikabel sind.
Oder gibt es methoden für die man beweisen kann, dass es keine schnellere methode als das durchsuchen der schlüsselraumes gibt ?
Siehe oben. Das Problem ist, dass man dafür beweisen muss, dass partielles Wissen über den Schlüssel und die Daten keine Auswirkungen auf den Rest hat:
One time pad: es gibt keinen Zusammenhang zwischen den Bits des Ciphertext, da jedes Ciphertext-Bit exakt einem Schlüsselbit zugeordnet ist. Eine Information über einen Teil der Daten sagt Dir also exakt nichts über den Rest der Daten.
Polynomiales Gleichungssystem: wenn Dir eine Gleichung fehlt ist das Ergebnis vollständig undeterminiert (alle möglichen Ergebnisse sind immernoch möglich).
Alle anderen Algorithmen: es gibt bekannte mathematische Zusammenhänge zwischen den Bits von Schlüssel, Klartext und Ciphertext. Die Sicherheit dieser Algorithmen beruht darauf dass die Gleichung nicht mit bekannten Methoden zu lösen ist, auch wenn man Teilinformationen hat.
Wenn das so wäre, wäre wohl das ende der kryptanalyse gekommen.. Hat vielleicht was mit np-problemen zu tun...
So schnell wird das Ende nicht kommen: Menschen sind sehr gut darin sich Probleme auszudenken, die sie nicht selbst lösen können - die Frage ist immer nur, ob es jemand anderes lösen kann.
Konrad