RSA und die Häufigkeitsanalyse

Wegen scheinbar regem Interesse: Ja, RSA ist anfällig für Häufigkeitsanalyse; in der Praxis ist das jedoch vollkommen egal.

Das in meiner Facharbeit beschriebene Verfahren ist im Endeffekt eine vom privaten und öffentlichen Schlüssel abhängige monoalphabetische Verschlüsselung. Würde man zeichenweise einen längeren deutschen Text damit verschlüsseln, könnte man vermutlich recht zügig die Ursprungsnachricht ableiten. Das Gute: Bis auf Mathematiklehrer tut niemand so einen Blödsinn. Verschlüsselt man Daten mit zufälliger Zeichenverteilung hilft eine Häufigkeitsanalyse nichts. Und da RSA in der Regel hybrid, d.h. in Kombination mit einem symmetrischen Verschlüsselungsverfahren, verwendet wird, ist das Thema unkritisch; unter der Annahme, dass das mit RSA verschlüsselte Kennwort für das symmetrische Verfahren keine auffällige Zeichenverteilung aufweist.

Jetzt könnte jemand korrekterweise anmerken, dass selbst wenn ich keinen Anhaltspunkt habe, für was «abba» steht, ich immerhin weiß, dass die beiden Zeichen in der Mitte und das Zeichen am Anfang und Ende gleich sind. Und das wäre für das Knacken von Kennwörtern schon ein extrem hilreicher Hinweis, schließlich würde sich die Komplexität zum Brechen per Bruteforce von (bei angenommenem Alphabet von 26 Zeichen) 4^26 auf 2^26 verringern (676-fache Vereinfachung).

In der Praxis ist das ungleich komplexer: Man nehme an, das Alphabet wäre nicht 26 Zeichen groß, sondern 2000 chinesische Schriftzeichen. Da ist die Häufigkeitsanalyse fast nutzlos. Man stelle sich also vor, wir würden nicht Zahlen von 0 bis 255 (die ein ASCII-Zeichen repräsentieren) mit RSA verschlüsseln, sondern deutlich größere.

In meiner Facharbeit nicht groß ausgeführt ist, ist dass mehrere Zeichen üblicherweise zu Daten-Chunks zusammengefasst werden. Ist ja reine Definitionssache, was ein Zeichen ist. Angenommen wir hätten jetzt z.B. nicht 4 Zahlen zwischen 0 und 255, sondern eine einzige zwischen 0 und 4228250625 (die die gleiche Menge an Information enthält, und auf vier 256-Bit-Zeichen abgebildet werden kann), dann könnte unser «abba» oben also z.B. durch die Zahl 34555578 dargestellt werden. Was können wir dann mit Häufigkeitsanalyse noch ableiten? Genau: Nichts.

© 2009 Julian von Mendel (http://derjulian.net) | Datum: 16.12.2018