Unknackbare Verschlüsselung

@El_Gato

El_Gato schrieb:Ich habe mir überlegt, wie man das Vigènere-Verfahren sicherer und auch leichter zu handhaben machen könnte. Statt einer normalen Substitutionsmatrix, deren oberste Reihe mit A, B, C, D, E und so weiter beginnt, benutzt man einfach eine, deren Reihen zufällig angeordnet sind.

Das bringt aber nichts: Jeder Buchstabe im Schlüssel sagt aus, um wieviel der entsprechende Buchstabe im zu verschlüsselnden Text verschoben werden soll.

Das heißt aus dem Schlüssel wird zunächst eine Verschiebe-Liste generiert. Beispiel:

Schlüssel: ACE
Verschiebungen: 0, 2, 4

Der erste Buchstabe des Textes wird um 0 verschoben, der zweite um 2, der dritte um 4, der vierte um 0 usw.

Die relevanten Zeilen der Matrix lauten dementsprechend (links der Schlüsselbuchstabe, Mitte Verschiebung, rechts die Klartextkodierung):

A 0 ABCDE...Z
C 2 CDEFG...B
E 4 EFGHI...D

Jetzt kommt deine Idee ins Spiel. Vertauschen wir also mal die erste und zweite Zeile:

A 2 CDEFG...B
C 0 ABCDE...Z
E 4 EFGHI...D

Jetzt kann man sehen, daß die Zeile ABCDE...Z nicht mehr über den Schlüsselbuchstaben A, sondern über C angesprochen wird. Und umgekehrt, Zeile CDEFG...B wird nun über A erreicht.

Das gleiche Resultat erreicht man, indem man im Schlüssel A durch C und umgekehrt ersetzt und die herkömliche (sortierte) Matrix verwendet. Statt dem Schlüssel ACE nimmt man also CAE.

Dein Verfahren läuft also darauf hinaus, daß man den Schlüssel vor der Verwendung selbst erst einmal verschlüsselt und dann mit der herkömlichen Matrix weiterarbeitet.

Allerdings ist das ganze Verfahren mit einem verschlüsselten Schlüssel nicht sicherer als mit einem unverschlüsselten. Und du müßtest außerdem mit dem Empfänger nicht nur den eigentlichen Schlüssel austauschen, sondern auch noch den Schlüssel, mit dem der Schlüssel kodiert wird...

Zäld

@zaeld

Ähm, nein. So meinte ich das nicht. Die erste Reihe der Matrix würde mit zB Z, J, D, P, Q beginnen und so weiter halt, völlig willkürlich. Die zweite Reihe fängt dann mit W, L, O, S, X an und so verfährt man mit allen Reihen. Keine soll der anderen gleichen oder irgendeine Gesetzmäßigkeit aufweisen.

zaeld schrieb:Dein Verfahren läuft also darauf hinaus, daß man den Schlüssel vor der Verwendung selbst erst einmal verschlüsselt und dann mit der herkömlichen Matrix weiterarbeitet.

Nein. Der Schlüssel wird nicht verschlüsselt und eine herkömmliche Matrix kommt bei meiner Variante der Vigènere-Verschlüsselung auch nicht zur Anwendung.

El_Gato schrieb:Ähm, nein. So meinte ich das nicht. Die erste Reihe der Matrix würde mit zB Z, J, D, P, Q beginnen

Ich bezog mich auf deinen ersten Vorschlag, die Reihen der Matrix in eine andere Reihenfolge zu bringen.

Zu deinem zweiten Vorschlag fällt mir auch noch was ein, aber erst heute abend irgendwann.

El_Gato schrieb:Der Schlüssel wird nicht verschlüsselt und eine herkömmliche Matrix kommt bei meiner Variante der Vigènere-Verschlüsselung auch nicht zur Anwendung.

Ich meinte damit: Dein erstes Verfahren mit den umsortierten Reihen hat exakt das gleiche Resultat als würde man den Schlüssel verschlüsseln und mit einer herkömlichen Matrix mit geordneten Reihen arbeiten. Und letzteres bringt keinen Sicherheitszuwachs.

Edit: Nach kurzem Blick auf die zweite, komplexere Variante, stellt sich heraus, daß auch das keinen Sicherheitsgewinn bietet. Aber dazu dann später mehr!

Z.

@zaeld

Na da bin ich ja mal gespannt. :vv:

@El_Gato

So, ich habe auf dem Nachhauseweg nochmal drüber nachdenken können.

Zur ersten Variante nochmal, die vertauschten Reihen in der Matrix:

Also in der normalen Matrix steht in Zeile A die Kodierung "ABCD...Z", in Zeile B "BCDE...A" usw.

Du willst jetzt die einzelnen Zeilen untereinander vertauschen, daß z.B. in Zeile A "BCDE...A" steht und in Zeile B "ABCD...Z", also die ersten beiden Zeilen vertauscht.

Beim Verschlüsseln passiert jetzt folgendes (angenommen, der Schlüssel beginnt mit "A"):

- Das A wird genommen

- In Zeile A steht jetzt das, was in der Standardmatrix in Zeile B steht

- Der Klartextbuchstabe wird mittels der Zeile A aus deiner Matrix ("BCDE...A") mit der umsortierten Reihenfolge kodiert.

Das ganze kann man auch anders erledigen, indem man die Matrix nicht umsortiert, sondern indem man eine Umsortierungstabelle benutzt. Dort steht dann drin, welche Zeile man bei einem gegebenen Schlüsselwortbuchstaben nehmen soll.

In diesem Beispiel würde also A auf B verweisen und B auf A. Soll heißen: Bei Schlüsselbuchstabe A nimm tatsächlich Zeile B aus der Standardmatrix. Das kommt aufs gleiche hinaus, als würde man Zeile A aus der Standardmatrix auf Zeile B schieben:

- Das A wird genommen

- In der Umsortierungstabelle steht an Eintrag A, daß Zeile B genommen werden soll.

- Der Klartextbuchstabe wird mittels der Zeile B aus der Standardmatrix kodiert.

Da nun aber jedes A aus dem Schlüssel auf Zeile B zeigt (und ein Schlüssel-B verweist immer auf A), kann man die Umsortierungstabelle gleich auf den ganzen Schlüssel anwenden. Aus jedem A macht man ein B, und aus jedem B macht man ein A, so spart man sich anschließend die Umsortierungstabelle und macht das nur einmal vorher.

Das bedeutet, man verschlüsselt den Schlüssel. Da der Schlüssel aber sowieso geheim ist, bringt eine weitere Verschlüsselung nichts. Und damit bringt eben eine Vertauschung der Zeilen in der Matrix gar nichts.


Nun zu der komplexeren Variante mit den vertauschten Buchstaben in der Zeile. Hier nehme ich erst einmal die Auffassung von vorhin zurück, daß das keinen Sicherheitsgewinn bietet. Gewisse Probleme bleiben aber trotzdem bestehen.

Bei diesem Verfahren bleibt es dabei, daß wenn ein bestimmter Schlüsselbuchstabe und ein bestimmter Klartextbuchstabe aufeinandertreffen, immer derselbe verschlüsselte Buchstabe entsteht. Ein Schlüssel-"A" und ein Klartext-"e" führen z.B. immer zu "m", und "A" + "x" ergibt immer "u".

Jeder Buchstabe im Schlüssel trifft häufiger auf einen oft vorkommenden Buchstaben als auf einen seltenen. Das bedeutet, ein "A" im Schlüssel erzeugt durch die häufigen "e"s häufiger ein "m" als ein "u" durch das "x". Und genau da liegt die Schwäche des gesamten Algorithmus. Man kann sozusagen zählen, wie häufig ein Buchstabe vorkommt. Und wenn "m" am häufigsten vorkommt, dann ist das im Klartext wahrscheinlich ein "e". Die Differenz zwischen dem "m" und dem "e" ist dann wohl der Paßwortbuchstabe, und den kann man dann für die Dekodierung der anderen Zeichen verwenden. Der Algorithmus macht das schon deutlich schwieriger, weil mit einem anderen Schlüsselbuchstaben und einem anderen Klartextbuchstaben ebenfalls ein "m" erzeugt wird, aber es geht trotzdem. Wie das genau geht, erzähle ich jetzt aber nicht.

So, das mit der Rekonstruktion des Passwortbuchstabens wie eben angedeutet funktioniert aber nur mit der Standardmatrix, nicht mit deiner durcheinandergwürfelten Zeile. Das macht den Angriff schwieriger, vielleicht auch deutlich schwieriger, aber die statistischen Auffälligkeiten bleiben eben bestehen.

Das also dazu, daß es doch einen Sicherheitsgewinn bietet.

Aber es besteht noch ein anderes Problem: Wie bekommst du die Matrix vom Sender zum Empfänger? Als Bestandteil vom Schlüssel? Der wird dann so groß, daß man im Prinzip gleich ein One-Time-Pad verwenden kann. Das ist ja dann schon fast ein One-Time-Pad - mit dem Nachteil, daß der verschlüsselte Text statistisch ungleich verteilt ist.

Aber lass dich davon bloß nicht entmutigen, dich mit dem Thema zu beschäftigen. Falls du programmierst, ist alleine die Erkenntnis, daß selbstgebaute Kryptographie nichts taugt, und daß man lieber standardisierte, geprüfte Verfahren verwenden sollte, das alles wert..

Zäld

zaeld schrieb:Jeder Buchstabe im Schlüssel trifft häufiger auf einen oft vorkommenden Buchstaben als auf einen seltenen. Das bedeutet, ein "A" im Schlüssel erzeugt durch die häufigen "e"s häufiger ein "m" als ein "u" durch das "x". Und genau da liegt die Schwäche des gesamten Algorithmus. Man kann sozusagen zählen, wie häufig ein Buchstabe vorkommt. Und wenn "m" am häufigsten vorkommt, dann ist das im Klartext wahrscheinlich ein "e". Die Differenz zwischen dem "m" und dem "e" ist dann wohl der Paßwortbuchstabe, und den kann man dann für die Dekodierung der anderen Zeichen verwenden. Der Algorithmus macht das schon deutlich schwieriger, weil mit einem anderen Schlüsselbuchstaben und einem anderen Klartextbuchstaben ebenfalls ein "m" erzeugt wird, aber es geht trotzdem. Wie das genau geht, erzähle ich jetzt aber nicht.

Das ist eine Häufigkeitsanalyse. Die funktioniert nur bei monoalphabetischen Substitutionen.
Bei Vigènere kannst du das vergessen. Bei polyalphapetischen Verschlüsselungen gibt es andere Angriffsmöglichkeiten; die sind aber bei weitem nicht so einfach wie die Häufigkeitsanalyse.

Meine Intention hinter der willkürlich zusammengestellten Matrix ist, daß man diese seltener auswechseln muss und relativ kurze Schlüsselwörter nehmen kann.
Ich schrieb schon, daß wenn man das Standardalphabet nimmt, die Umlaute und das Eszett sowie die zehn Ziffern, hat man vierzig Zeichen. Vierzig mal vierzig ergibt 1600.
1600! ergibt eine Zahl mit fast 4500 Stellen, wie ich schon auf der letzten Seite schrieb.

@El_Gato

El_Gato schrieb:Das ist eine Häufigkeitsanalyse. Die funktioniert nur bei monoalphabetischen Substitutionen.
Bei Vigènere kannst du das vergessen.

Nö, da funktioniert das auch. Es ist nur nicht so einfach. Erst ermittelt man die Länge des Passworts, und dann die einzelnen Buchstaben des Passworts. Geht alles über die Häufigkeit.

El_Gato schrieb:Meine Intention hinter der willkürlich zusammengestellten Matrix ist, daß man diese seltener auswechseln muss und relativ kurze Schlüsselwörter nehmen kann.

Naja, meine Kenntnisse reichen nicht so weit, daß ich die Qualität dieses Verfahrens stichhaltig beurteilen könnte. Ich kann nur feststellen, daß die statistischen Auffälligkeiten auf jeden Fall bestehen bleiben.

Und wenn man schon mit einem 1600 Zeichen großen Schlüssel hantiert, was bei ca. 6 Bit pro Zeichen also 9600 Bit entspricht, warum dann nicht einen von den etablierten Algorithmen verwenden, die viel kleinere Schlüssel brauchen und trotzdem sicher sind?

El_Gato schrieb:Ich schrieb schon, daß wenn man das Standardalphabet nimmt, die Umlaute und das Eszett sowie die zehn Ziffern, hat man vierzig Zeichen. Vierzig mal vierzig ergibt 1600.
1600! ergibt eine Zahl mit fast 4500 Stellen, wie ich schon auf der letzten Seite schrieb.

Ich glaube, die Berechnung stimmt nicht. Es gibt ja nicht 1600 unterschiedliche Symbole, die in der Matrix irgendwie untergebracht werden müssen.

In jeder Zeile muß jeder Buchstabe einmal vorkommen. Macht pro Zeile 40! Möglichkeiten. Dann kann man diese Zeilen anschließend kombinieren, ergibt insgesamt 40! ^ 40 Möglichkeiten.

Aber was bringt diese Zahl? Der Angriff erfolgt ja nicht über Brute-Force, sondern über andere Wege. Brute-Force würde im übrigen wie der One-Time-Pad nicht den Klartext liefern, da alle möglichen Texte dekodiert würden.

Z.

zaeld schrieb:Nö, da funktioniert das auch. Es ist nur nicht so einfach. Erst ermittelt man die Länge des Passworts, und dann die einzelnen Buchstaben des Passworts. Geht alles über die Häufigkeit.

Da brauchts aber ein wenig mehr als die Häufigkeitsanalyse und einfach ist das ganz sicher nicht.

zaeld schrieb:Naja, meine Kenntnisse reichen nicht so weit, daß ich die Qualität dieses Verfahrens stichhaltig beurteilen könnte. Ich kann nur feststellen, daß die statistischen Auffälligkeiten auf jeden Fall bestehen bleiben.

Das mag sein, aber da kann man ohne die richtige Matrix nichts machen. Und ich denke auch, daß wenn man die Matrix zB so anordnet, daß in einer Reihe derselbe Buchstabe mehrmals vorkommt und wieder andere dafür gar nicht, dann ändert das die Struktur und irgendwelche statistischen Häufigkeiten ganz erheblich.

zaeld schrieb:Ich glaube, die Berechnung stimmt nicht. Es gibt ja nicht 1600 unterschiedliche Symbole, die in der Matrix irgendwie untergebracht werden müssen.

Schon richtig, aber dennoch gibt es 1600! Möglichkeiten, diese anzuordnen. Auch wenn nur 40 verschiedene Zeichen verwendet werden.

@zaeld

Und selbst wenn die Matrix "nur" 40!^40 Kombinationen haben sollte, so wäre die Anzahl immer noch unvorstellbar groß:

Spoiler29 22824 41357 62483 32356 56341 69980 67436 44029 32624 62321 52617 20185 02348 52660 38167 65721 24176 20394 85559 88205 48380 61367 52534 61185 45881 52590 09402 13762 13938 64813 26723 17796 22899 35798 06996 29428 53351 25010 07429 39599 57698 39273 64661 89355 89512 80848 57757 99002 49166 89129 43068 31671 26905 43325 95195 94737 82547 13877 08942 10162 97227 07519 84714 55466 07972 97104 63724 33704 10315 93680 70035 74530 61732 76040 36015 87970 56292 25361 09626 17362 82943 12770 13624 08679 75617 99868 74951 68396 48756 06215 02331 67876 08763 04949 18042 02149 58403 50955 14455 69628 12257 95841 68113 52881 72289 17072 96306 46900 51024 38423 48423 34375 77550 33243 44801 21632 44198 80587 38637 62125 09702 22520 30385 80691 57740 32696 33407 03579 71496 57791 56603 93955 55167 36379 81642 83656 93579 51925 70122 35801 72731 59361 00548 46741 95138 04995 88383 90584 13850 46008 89673 19921 90323 39926 53192 50086 72240 79150 58042 05498 77386 89718 88059 22425 86360 89410 71349 18341 30112 95229 83164 19426 57695 20823 36004 30133 00819 07105 26765 27948 77399 06676 97277 59158 13634 01747 61279 58381 90705 04749 47391 79764 11490 18158 59940 77571 14050 21479 22460 57457 39170 19613 03610 59111 97642 27256 85009 49998 19211 95293 05632 93055 08045 69344 42478 28234 63451 23751 83421 76712 17407 38480 78866 23961 03963 65237 78345 29657 21156 88968 42167 25436 28472 67061 23247 75083 57191 27194 79031 44587 13533 87601 73290 33503 91266 51232 22635 52174 25870 32156 49466 70977 14143 57349 29686 71609 02177 85496 63204 40399 16174 51567 15712 55535 82990 64542 41562 29214 24940 43408 78404 50764 74904 39801 93648 84569 04387 47931 29874 23880 03799 98721 67980 14000 71049 17961 49455 51308 26430 96932 29579 98162 59620 59670 34829 04597 88250 60021 76390 33690 77775 92655 25799 05155 38334 20572 38661 53573 93248 92195 06176 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000

1917 Stellen. Eine Zahl jenseits aller Vorstellungskraft.

@El_Gato

El_Gato schrieb:Da brauchts aber ein wenig mehr als die Häufigkeitsanalyse und einfach ist das ganz sicher nicht.

Super einfach ist es nicht, aber machbar. Grundzüge sind ja bereits im Wikipedia-Artikel dargestellt:

Wikipedia: Vigenère-Verschlüsselung#Kryptoanalyse

El_Gato schrieb:Und ich denke auch, daß wenn man die Matrix zB so anordnet, daß in einer Reihe derselbe Buchstabe mehrmals vorkommt und wieder andere dafür gar nicht,

... dann funktioniert die Entschlüsselung nicht mehr. Wenn du z.B. mehrmals ein "d" hast und im verschlüsselten Text kommt jetzt ein "d", welches von den mehreren nimmst du dann zur Entschlüsselung?

El_Gato schrieb:Schon richtig, aber dennoch gibt es 1600! Möglichkeiten, diese anzuordnen. Auch wenn nur 40 verschiedene Zeichen verwendet werden.

Nein. Jeder Buchstabe in der Matrix kommt 40 mal vor. Bei 40 Buchstaben ergibt das 1600 Buchstaben, die unterzubringen sind. Fängt man an, die Buchstaben in die leere Matrix unterzubringen und platziert z.B. das erste "A" in die erste Position und das zweite "A" an die zweite Position , dann ist das das gleiche Ergebnis als würde man das zweite "A" an die erste Position und das erste "A" an die zweite Position stellen. In der 1600!-Berechnung wären dies zwei unterschiedliche Konstellationen.

El_Gato schrieb:1917 Stellen. Eine Zahl jenseits aller Vorstellungskraft.

Der Angriff liegt ja wie gesagt auch nicht in einem Brute-Force-Angriff, sondern in der Ausnutzung von bestimmten Schwächen im System. Und statistische Auffälligkeiten gibt es da definitiv.

Und der Nachteil, daß Sender und Empfänger erst einmal diese riesige Tabelle mit 1600 Zeichen austauschen müssen. Man hantiert also quasi mit einem sehr langen Schlüssel, bei dem noch nicht einmal jede Stelle beliebig gewählt werden darf, sondern jeder Buchstabe muß im Schlüssel genau 40 mal vorkommen.

Als Alternative würde ich vorschlagen, eine herkömliche Verschlüsselung durchzuführen (mit der Standard-Matrix) und das Ergebnis mit einem 1600 Zeichen langen One-Time-Pad zu verschlüsseln. Das hätte den Vorteil, daß in dem One-Time-Pad jeder Buchstabe beliebig oft vorkommen kann.

Zäld

Hey leute kann des sein das der letzte codierte text von dem zodiak killer der ja noch nicht entschlüsselt wurde auch so eine art one-time-pad ist?!

zaeld schrieb:... dann funktioniert die Entschlüsselung nicht mehr. Wenn du z.B. mehrmals ein "d" hast und im verschlüsselten Text kommt jetzt ein "d", welches von den mehreren nimmst du dann zur Entschlüsselung?

Das Zusammenspiel zwischen Schlüssel und Geheimtext stellt die Eindeutigkeit sicher. Man müsste das halt mal ausprobieren, wenn man sich ganz sicher sein will.

man kann auch eigene symbole entwerfen, dann ist der text auch unknackbar...siehe voynich manuskript

Wikipedia: Voynich-Manuskript

@Leibhaftiger

Du glaubst doch nicht ernsthaft das das teil echt ist?!

ich glaube an gar nichts...

es gibt keinen eindeutigen beweis das es echt ist und keinen eindeutigen beweis das es eine fälschung ist. aber trotzdem ist es interessant.

@Leibhaftiger

Also ich glaub die tatsache das darin pflazem

Leibhaftiger schrieb:man kann auch eigene symbole entwerfen, dann ist der text auch unknackbar...siehe voynich manuskript

Nein, ist er nicht. Die statistischen Häufigkeiten bleiben dennoch erhalten. Das Voynich-Manuskript ist da wieder eine andere Geschichte. Aber nur andere Symbole zu verwenden bringt keine zusätzliche Sicherheit.

@El_Gato

El_Gato schrieb:Das Zusammenspiel zwischen Schlüssel und Geheimtext stellt die Eindeutigkeit sicher. Man müsste das halt mal ausprobieren, wenn man sich ganz sicher sein will.

Na das will ich mal sehen:

Matrix (nur die benötigte Zeile gezeigt):

__ABCDE FGHIJ KLMNO PQRST UVWXY Z
A_QWFFT ZUIOP FFDFG HJKLY XCVBN M

Schlüssel: "A"

chiffrierter Text: "TFFT"

Wie lautet der Klartext?

Z.

@zaeld

Ok, du hast recht. Ich kann mich eben auch irren. :vv:

El_Gato schrieb:Ok, du hast recht. Ich kann mich eben auch irren.

Macht ja nichts, dafür diskutieren wir ja hier :-)