Kasiski-Test mithilfe von R

Wie rufe ich R-Funktionen auf, wie selektiere ich Daten, ich weiß nicht genau ....

Moderatoren: EDi, jogo

Kev1807
Beiträge: 15
Registriert: Mo Mai 21, 2018 1:47 pm

Kasiski-Test mithilfe von R

Beitrag von Kev1807 »

Halli Hallo,

Vorab: Ich bin leider gerade nur mit dem Tablet unterwegs (auf dem R noch nicht eingerichtet ist, was aber nachgeholt wird)
Der Kasiski-Test (https://de.wikipedia.org/wiki/Kasiski-Test) wird zur Entcshlüsselung der Vigenere-Chiffre genutzt. (https://de.wikipedia.org/wiki/Vigen%C3%A8re-Chiffre)

Meine Fragen dazu finden sich immer zwischen den Schritten. Sollte es unübersichtlich sein, ändere ich das !

Zur Entschlüsselung sind mehrere Schritte notwendig, nachfolgend kurz aufgelistet

1) Man muss Doppler finden und zwar in Form von zweizeichigen, dreizeichigen,..., n-zeichigen "Päärchen" (n= Schlüssellänge)
Wenn der verschlüsselte Text die Variable c_text ist, der sich wiederholende Elemente enthält, kann ich einfach

Code: Alles auswählen

c_text <- duplicated(c_text)
in irgendeiner Form anpassen, um die doppelten Elemente zu erfassen.
Wie bekomme ich sie angezeigt?
2) Man muss den Abstand zwischen den einzelnen Päärchen errechnen
Das ist ja eigentlich nur ein Zählen der Zeichen dazwischen und Ablegen derselben in Variablen?

3) Primfaktorzerlegung der Abstände ermöglicht "Schätzungen" der möglichen Schlüssellängen

4) Nun mit den "geschätzten" Längen den Text in die Einheiten einteilen, die wahrscheinlich mit demselben Element des Schlüssels verschlüsselt wurden.


Die Schritte 3) und 4) stellen mich noch mehr vor Probleme als 1) und 2)
Schritt 1 erledige ich gerade händisch, damit ich nicht untätig bin :-D

Ich hoffe, jemand ist trotz des mängelbehafteten Posts (kein Beispiel - bisher null ausführbaren Code ...) bereit, mir einige Hinweise zu geben :-)

PS:
Ein berühmtes Beispiel ist die Zimmermann-Depesche (https://de.wikipedia.org/wiki/Zimmermann-Depesche) grober Inhalt: D sichert Mexiko Unterstützung zu, wenn Mexiko den USA den Krieg erklärt um so den Kriegseintritt der USA auf Seiten der entente-Mächte zu verhindern (1917 ist das Jahr)
consuli
Beiträge: 479
Registriert: Mo Okt 10, 2016 8:18 pm

Re: Kasiski-Test mithilfe von R

Beitrag von consuli »

Hallo!

R wird für gewöhnlich nicht für Kryptografie verwendet. Deshalb findet die Google-Suche "[R] Kryptographie" auch fast nichts.

Der Gründe liegen vermutlich darin, dass
- die Dienste eine Open-Source Software schlechter kontrollieren können als eine proprietäre Software
- R für Brute-Force-Angriffe zu langsam ist

Consuli
Irmgard.
bigben
Beiträge: 2771
Registriert: Mi Okt 12, 2016 9:09 am

Re: Kasiski-Test mithilfe von R

Beitrag von bigben »

Hi,

und doch findet sich eine Vigenere-Verschlüsselung in einem Package für Deskriptive Statistiken: https://www.rdocumentation.org/packages ... s/Vigenere

Für den beschriebenen Algorithmus zum Knacken finde ich, dass R nicht die schlechteste Programmiersprache ist, um das umzusetzen. Es wäre halt hilfreich zu wissen, an welcher Stelle es bei Dir hängt.

Hier mal Beispielhaft alle 4-Buchstaben langen Teile eines Textes:

Code: Alles auswählen

bsp <- "geheimer text ist text von dem man nicht möchte, dass andere den text lesen können. nicht, dass mich das etwas anginge."

anfaenge <- sapply(as.list(1:(nchar(bsp)-3)),
                   function(start) substring(bsp, start, start+3))
head(anfaenge, 15)
Das ging doch in R schon ganz flott. Wird natürlich noch etwas komplizierter. Hier beispielsweise Treffer von Wiederholungen:

Code: Alles auswählen

for(anfang in anfaenge){ 
    treffer <- unlist(gregexpr(pattern = anfang, text = bsp, fixed=TRUE))
    if(length(treffer) > 1){
        cat(paste0(anfang, "  -  "))
        print(treffer)
        cat("\n")
    }
}
Die letzte Zeile im Output lautet

Code: Alles auswählen

s an  -  [1]  53 110
Das bedeutet, dass die Buchstabenfolge "s an" an Stelle 53 und an Stelle 110 vorkommt.

Ich glaube nicht, dass hier jemand Lust hat, den ganzen Algorithmus für Dich umzusetzen. Was kannst Du denn selbst, und was nicht?

LG,
Bernhard
---
Programmiere stets so, dass die Maxime Deines Programmierstils Grundlage allgemeiner Gesetzgebung sein könnte
consuli
Beiträge: 479
Registriert: Mo Okt 10, 2016 8:18 pm

Re: Kasiski-Test mithilfe von R

Beitrag von consuli »

Die R Pakete crypto und Sodium gibt's noch. Sie scheinen eher Bildungscharakter zu haben als sich professionell mit der Thematik zu beschäftigen. Keine Ahnung, ob das das ist, was Du suchst.

Consuli
Irmgard.
Kev1807
Beiträge: 15
Registriert: Mo Mai 21, 2018 1:47 pm

Re: Kasiski-Test mithilfe von R

Beitrag von Kev1807 »

bigben hat geschrieben: Mo Jun 04, 2018 3:34 pm

Ich glaube nicht, dass hier jemand Lust hat, den ganzen Algorithmus für Dich umzusetzen. Was kannst Du denn selbst, und was nicht?

LG,
Bernhard
Da sehe ich momentan das Problem: Ich bin, wie du vielleicht aus dem anderen Thread erkannt hast, noch ziemlich neu mit R. Ich habe mir die Vigenere-Sachen mal in Python angeschaut und da ebenfalls kapituliert :-D Also zum Kenntniss-Stand: Es wird eine steile Lernkurve :-D
consuli hat geschrieben: Mo Jun 04, 2018 8:56 pm Die R Pakete crypto und Sodium gibt's noch. Sie scheinen eher Bildungscharakter zu haben als sich professionell mit der Thematik zu beschäftigen. Keine Ahnung, ob das das ist, was Du suchst.

Consuli
Es geht um "nur" drei bis fünf Briefe, mit je 400 (+-100) Zeichen.

Allgemein:
Gerade der Kasiski-Test, das Auffinden von wiederkehrenden Elementen, ist doch eine rein statistische Auswertung, ebenso das Erfassen der Häufigkeiten und der Abstände dazwischen ...


Again: Danke für die zahlreichen hilfreichen Antworten, obschon ich wohl recht unfähig bin (was mir jeden Tag mehr und mehr vor Augen geführt wird - aber immerhin zweifle ich noch nicht an meinen Fähigkeiten auf dem Gebiet der Geschichtswissenschaft! )
consuli
Beiträge: 479
Registriert: Mo Okt 10, 2016 8:18 pm

Re: Kasiski-Test mithilfe von R

Beitrag von consuli »

https://de.wikipedia.org/wiki/Vigen%C3%A8re-Chiffre#Kryptanalyse hat geschrieben: Idealerweise sollte der Vigenere-Schlüssel möglichst lang sein und aus einer möglichst „zufälligen“ Buchstabenfolge bestehen. Erreicht die Länge des Schlüssels die des Klartextes und wird der Schlüssel nicht mehrfach verwendet, dann erhält man ein tatsächlich „unknackbares“ Verfahren,
Na, dann wünsch ich Dir mal, dass der Verfasser keinen sehr langen und zufälligen Schlüssel verwendet hat. ;)

Meine Simon Mercury Puzzle Fähigkeiten sind jedenfalls stark begrenzt. :D

Consuli
Irmgard.
bigben
Beiträge: 2771
Registriert: Mi Okt 12, 2016 9:09 am

Re: Kasiski-Test mithilfe von R

Beitrag von bigben »

Kev1807 hat geschrieben: Di Jun 05, 2018 8:47 pmDa sehe ich momentan das Problem: Ich bin, wie du vielleicht aus dem anderen Thread erkannt hast, noch ziemlich neu mit R.
Kannst Du denn mit dem Code den ich gepostet habe, irgendwas anfangen? Es macht doch mehr Sinn, den zu verwenden als die 5x400 Zeichen manuell auf Wiederholungen abzusuchen! Den Rest kannst Du ja ggf per Handarbeit machen, wenn es sein muss.

LG,
Bernhard
---
Programmiere stets so, dass die Maxime Deines Programmierstils Grundlage allgemeiner Gesetzgebung sein könnte
consuli
Beiträge: 479
Registriert: Mo Okt 10, 2016 8:18 pm

Re: Kasiski-Test mithilfe von R

Beitrag von consuli »

Ich würde das ganze mit Zahlen aufbauen, damit Du später die Entschlüsselung mit Primfaktorzerlegung machen kannst.

Beispielsweise so:

Code: Alles auswählen

text=toupper("HorstvonAdlerDasKuckuckseiistgeschluepftAdlervonHorstVerstanden")
text

inttext= utf8ToInt(text) - utf8ToInt("A")
inttext
length(inttext)

schluessel="PANTAU"
intschluessel= utf8ToInt(schluessel)
intschluesselmulti= rep(intschluessel, 1000)

intciphertext= (inttext + intschluesselmulti[1:length(inttext)]) %% 26  # Modulo 26
intciphertext

ciphertext= intToUtf8(intciphertext + utf8ToInt("A"))
ciphertext
bigben hat geschrieben: Mi Jun 06, 2018 10:44 am Es macht doch mehr Sinn, den zu verwenden als die 5x400 Zeichen manuell auf Wiederholungen abzusuchen! Den Rest kannst Du ja ggf per Handarbeit machen, wenn es sein muss.
Meines Ermessens macht es bei Vigenère-Chiffre ohnehin keinen Sinn nach Wiederholungen zu suchen.

Aus dem Klartext
"HORSTVONADLERDASKUCKUCKSEIISTGESCHLUEPFTADLERVONHORSTVERSTANDEN"
wird die Vigenère-Chiffre
"JBRYGCQAAJYLTQAYXBEXUIXZGVIYGNGFCNYBGCFZNKNRRBBUJBRYGCGESZNUFRN"

Die verräterische Wiederholung "JBRYG" kommt nur dadurch zu Stande, dass der Positionsbeginn von "HORST" und der Positionsbeginn der Wiederholung von "PANTAU" zufällig auf die gleiche Postion fallen. Das ist aber reine Glückssache und kommt nur bei sehr kurzen Schlüsseln vor. Man kann daraus nicht einen generellen Dechiffrieralgotithmus ableiten.
https://de.wikipedia.org/wiki/Vigen%C3%A8re-Chiffre#Kryptanalyse hat geschrieben: Vorteile einer polyalphabetischen Methode wie der Vigenère-Chiffre gegenüber den in den damaligen Jahrhunderten üblichen einfachen monoalphabetischen Methoden – dazu gehören auch die damals sehr beliebten Nomenklatoren – ist das durch die Verwendung von vielen unterschiedlichen Alphabeten bewirkte Abschleifen des bei den monoalphabetischen Verfahren so verräterischen Häufigkeitsgebirges.
Weshalb man statistische Methoden auf eine solche Chiffre nicht anwenden kann (mathematisch eine ganz andere Baustelle).

Jetzt hast Du eine ungefähre Vorstellung davon bekommen, dass das kryptologische Entschlüsseln einer Vigenère-Chiffre mathematisch eine ganz andere Liga ist, als selbst eine herzustellen (oder authorisiert mit dem Schlüssel zu dekodieren).

Consuli
Irmgard.
Kev1807
Beiträge: 15
Registriert: Mo Mai 21, 2018 1:47 pm

Re: Kasiski-Test mithilfe von R

Beitrag von Kev1807 »

bigben hat geschrieben: Mi Jun 06, 2018 10:44 am
Kev1807 hat geschrieben: Di Jun 05, 2018 8:47 pmDa sehe ich momentan das Problem: Ich bin, wie du vielleicht aus dem anderen Thread erkannt hast, noch ziemlich neu mit R.
Kannst Du denn mit dem Code den ich gepostet habe, irgendwas anfangen? Es macht doch mehr Sinn, den zu verwenden als die 5x400 Zeichen manuell auf Wiederholungen abzusuchen! Den Rest kannst Du ja ggf per Handarbeit machen, wenn es sein muss.

LG,
Bernhard
Erstaunlicherweise ja, auch wenn ich das alleine so noch nicht hätte schreiben können!
Durch die Einteilung in Tripletten habe ich, für meinen Text, eine vermutete Schlüssellänge von entweder einem Vielfachen von 3 oder einem Vielfachen von einer der Primzahlen im Bereich 10-20 (also 11,13,17,19) Da der Versuchstext ja nur 305 Zeichen hatte erscheint mir ein Vielfaches von 3 (im Bereich 3,6,9,12) für wahrscheinlicher. Der Verfasser des Briefes galt als sehr versiert in der Kryptographie des 18. Jahrhunderts, was die Sache nicht vereinfacht.

consuli hat geschrieben: Mi Jun 06, 2018 12:06 pm Ich würde das ganze mit Zahlen aufbauen, damit Du später die Entschlüsselung mit Primfaktorzerlegung machen kannst.
Meinst du so wie auf dem Bild der Zimmermann-Depesche zu sehen? Falls du es nicht angeschaut hast: Es sind mehrere Zahlekombinationen hintereinander. Optisch unterscheiden sich "meine" Briefe nicht davon. Ich habe lediglich Leerzeichen entfernt, sodass ich eine Zahlenkette habe, die 305 Zeichen lang ist.

consuli hat geschrieben: Di Jun 05, 2018 9:42 pm
https://de.wikipedia.org/wiki/Vigen%C3%A8re-Chiffre#Kryptanalyse hat geschrieben: Idealerweise sollte der Vigenere-Schlüssel möglichst lang sein und aus einer möglichst „zufälligen“ Buchstabenfolge bestehen. Erreicht die Länge des Schlüssels die des Klartextes und wird der Schlüssel nicht mehrfach verwendet, dann erhält man ein tatsächlich „unknackbares“ Verfahren,
Na, dann wünsch ich Dir mal, dass der Verfasser keinen sehr langen und zufälligen Schlüssel verwendet hat. ;)

Meine Simon Mercury Puzzle Fähigkeiten sind jedenfalls stark begrenzt. :D

Consuli
Ich mir auch :-(
305 Zeichen kann ich mir nicht vorstellen - er musste das ja adhoc schreiben an Bord eines Schiffes in der Nähe feindlicher Schiffe, sodass er eventuell nicht sein ganzes Können aufwenden konnte :-D Weiterhin musste der Empfänger dazu in der Lage sein das zu lesen und die Schlüssellänge 305 wäre dan ja nicht festlegbar für ihn, da der Brief ja spontan geschrieben wurde und eben nicht klar war, dass es 305 Zeichen sind ...
Zumal wir bei Vigenere Ohne-Code-Wort und mit Zeichenkette der Länge des Textes dann beim one-Time-Pad sind, was erst später Anwendung fand (was ihr bis zu diesem Post nicht wissen konntet - Sorry dafür :-D )

consuli hat geschrieben: Mi Jun 06, 2018 12:06 pm
consuli hat geschrieben: Mi Jun 06, 2018 12:06 pm Jetzt hast Du eine ungefähre Vorstellung davon bekommen, dass das kryptologische Entschlüsseln einer Vigenère-Chiffre mathematisch eine ganz andere Liga ist, als selbst eine herzustellen (oder authorisiert mit dem Schlüssel zu dekodieren).

Consuli
Dass das Knacken der V-Chiffre schwer(mir unmöglich?!) ist, ist mir durchaus bekannt :-D Ich habe den Betreuern der Arbeit auch gesagt, dass ich als Historiker eventuell nicht in der Lage dazu bin, das umzusetzen.(Ich fertige eine Quellenedition und diese drei Briefe können auch nur Randnotiz sein, aber es wäre recht schön, da etwas zu finden)
consuli hat geschrieben: Mi Jun 06, 2018 12:06 pmMeines Ermessens macht es bei Vigenère-Chiffre ohnehin keinen Sinn nach Wiederholungen zu suchen.
Die Suche nach Dopplern ist doch nichts anderes als die Suche nach sich wiederholenden Sequenzen? Ist dann der Kasiski-Test in deinen Augen nicht zielführend? (versteh das bitte nicht als Angriff, auch wenn es eventuell so gelesen werden kann!)
Ich muss doch zunächst nach Dopplern suchen und die Abstände zwischen ihnen zählen und dann per Primfaktorzerlegung auf wahrscheinliche Schlüssellänge schließen?
Erst über die wiederholenden Elemente im verschlüsselten Text kann ich doch die Schlüssellänge ermitteln? (Also Doppler finden, Abstände zählen, Primfaktorzerlegung --> häufigster Abstand vermutete Schlüssellänge)

Mich irritiert dass es sehr wenige relevante Abstände gibt - das spricht für einen langen Schlüssel ODER eine Mehrfachverschlüsselung:
Lediglich 2 Kombinationen kommen öfter als 3 mal vor (die eine 6 mal die andere 4 mal), wobei eine lediglich in Abständen von Primzahlen(oder einem Vielfachen einer Primzahl vorkommt) (79,17,79,2*41). Bei Betrachtung der Abstandsberechnungen, old-school auf Papier gemacht!, auf, sieht man:
Oft lässt sich die Zerlegung gar nicht anders darstellen als 1*Primzahl (Alternativ kommt noch ab und an 2*Primzahl)

Ich glaube ich muss damit meine Ausführungen (der untere Teil) halbwegs sinnvoll erscheinen etwas mit euch teilen ...
Kev1807
Beiträge: 15
Registriert: Mo Mai 21, 2018 1:47 pm

Re: Kasiski-Test mithilfe von R

Beitrag von Kev1807 »

bigben hat geschrieben: Mi Jun 06, 2018 10:44 am
Kev1807 hat geschrieben: Di Jun 05, 2018 8:47 pmDa sehe ich momentan das Problem: Ich bin, wie du vielleicht aus dem anderen Thread erkannt hast, noch ziemlich neu mit R.
Kannst Du denn mit dem Code den ich gepostet habe, irgendwas anfangen? Es macht doch mehr Sinn, den zu verwenden als die 5x400 Zeichen manuell auf Wiederholungen abzusuchen! Den Rest kannst Du ja ggf per Handarbeit machen, wenn es sein muss.

LG,
Bernhard
Erstaunlicherweise ja, auch wenn ich das alleine so noch nicht hätte schreiben können!
Durch die Einteilung in Tripletten habe ich, für meinen Text, eine vermutete Schlüssellänge von entweder einem Vielfachen von 3 oder einem Vielfachen von einer der Primzahlen im Bereich 10-20 (also 11,13,17,19) Da der Versuchstext ja nur 305 Zeichen hatte erscheint mir ein Vielfaches von 3 (im Bereich 3,6,9,12) für wahrscheinlicher. Der Verfasser des Briefes galt als sehr versiert in der Kryptographie des 18. Jahrhunderts, was die Sache nicht vereinfacht.

consuli hat geschrieben: Mi Jun 06, 2018 12:06 pm Ich würde das ganze mit Zahlen aufbauen, damit Du später die Entschlüsselung mit Primfaktorzerlegung machen kannst.
Meinst du so wie auf dem Bild der Zimmermann-Depesche zu sehen? Falls du es nicht angeschaut hast: Es sind mehrere Zahlekombinationen hintereinander. Optisch unterscheiden sich "meine" Briefe nicht davon. Ich habe lediglich Leerzeichen entfernt, sodass ich eine Zahlenkette habe, die 305 Zeichen lang ist.

consuli hat geschrieben: Di Jun 05, 2018 9:42 pm
https://de.wikipedia.org/wiki/Vigen%C3%A8re-Chiffre#Kryptanalyse hat geschrieben: Idealerweise sollte der Vigenere-Schlüssel möglichst lang sein und aus einer möglichst „zufälligen“ Buchstabenfolge bestehen. Erreicht die Länge des Schlüssels die des Klartextes und wird der Schlüssel nicht mehrfach verwendet, dann erhält man ein tatsächlich „unknackbares“ Verfahren,
Na, dann wünsch ich Dir mal, dass der Verfasser keinen sehr langen und zufälligen Schlüssel verwendet hat. ;)

Meine Simon Mercury Puzzle Fähigkeiten sind jedenfalls stark begrenzt. :D

Consuli
Ich mir auch :-(
305 Zeichen kann ich mir nicht vorstellen - er musste das ja adhoc schreiben an Bord eines Schiffes in der Nähe feindlicher Schiffe, sodass er eventuell nicht sein ganzes Können aufwenden konnte :-D Weiterhin musste der Empfänger dazu in der Lage sein das zu lesen und die Schlüssellänge 305 wäre dan ja nicht festlegbar für ihn, da der Brief ja spontan geschrieben wurde und eben nicht klar war, dass es 305 Zeichen sind ...
Zumal wir bei Vigenere Ohne-Code-Wort und mit Zeichenkette der Länge des Textes dann beim one-Time-Pad sind, was erst später Anwendung fand (was ihr bis zu diesem Post nicht wissen konntet - Sorry dafür :-D )

consuli hat geschrieben: Mi Jun 06, 2018 12:06 pm Jetzt hast Du eine ungefähre Vorstellung davon bekommen, dass das kryptologische Entschlüsseln einer Vigenère-Chiffre mathematisch eine ganz andere Liga ist, als selbst eine herzustellen (oder authorisiert mit dem Schlüssel zu dekodieren).

Consuli
Dass das Knacken der V-Chiffre schwer(mir unmöglich?!) ist, ist mir durchaus bekannt :-D Ich habe den Betreuern der Arbeit auch gesagt, dass ich als Historiker eventuell nicht in der Lage dazu bin, das umzusetzen.(Ich fertige eine Quellenedition und diese drei Briefe können auch nur Randnotiz sein, aber es wäre recht schön, da etwas zu finden)
consuli hat geschrieben: Mi Jun 06, 2018 12:06 pmMeines Ermessens macht es bei Vigenère-Chiffre ohnehin keinen Sinn nach Wiederholungen zu suchen.
Die Suche nach Dopplern ist doch nichts anderes als die Suche nach sich wiederholenden Sequenzen? Ist dann der Kasiski-Test in deinen Augen nicht zielführend? (versteh das bitte nicht als Angriff, auch wenn es eventuell so gelesen werden kann!)
Ich muss doch zunächst nach Dopplern suchen und die Abstände zwischen ihnen zählen und dann per Primfaktorzerlegung auf wahrscheinliche Schlüssellänge schließen?
Erst über die wiederholenden Elemente im verschlüsselten Text kann ich doch die Schlüssellänge ermitteln? (Also Doppler finden, Abstände zählen, Primfaktorzerlegung --> häufigster Abstand vermutete Schlüssellänge)

Mich irritiert dass es sehr wenige relevante Abstände gibt - das spricht für einen langen Schlüssel ODER eine Mehrfachverschlüsselung:
Lediglich 2 Kombinationen kommen öfter als 3 mal vor (die eine 6 mal die andere 4 mal), wobei eine lediglich in Abständen von Primzahlen(oder einem Vielfachen einer Primzahl vorkommt) (79,17,79,2*41). Bei Betrachtung der Abstandsberechnungen, old-school auf Papier gemacht!, auf, sieht man:
Oft lässt sich die Zerlegung gar nicht anders darstellen als 1*Primzahl (Alternativ kommt noch ab und an 2*Primzahl)

Ich glaube ich muss damit meine Ausführungen (der untere Teil) halbwegs sinnvoll erscheinen etwas mit euch teilen ...
Antworten