[QUIZ#11] Codeknacker


#1
Quiz #11
Codeknacker

Regeln
Die Regeln und der Ablauf der Quizrunde können in der entsprechenden Ankündigung eingesehen werden. Bitte lest sie euch aufmerksam durch, da sie alle wichtigen Informationen enthält. Lösungsansätze können und dürfen auch schon vorab untereinander ausgetauscht und diskutiert werden, allerdings nicht öffentlich im Forum. Verwendet stattdessen bitte private Nachrichten oder schaut im Chat vorbei.

Abgabe
Die Abgabe erfolgt wie immer im Abgabeforum. Abgabefrist ist voraussichtlich Samstag, der 24. Oktober 2009 um ca. 23 Uhr.

Das Problem
Dagobert Duck hat in seinem Geldspeicher ein neues Sicherheitssystem installieren lassen. Der Tresorraum kann jetzt nur noch betreten werden, wenn man am Eingang die richtige Passphrase aufsagt. Da Dagobert nicht mehr der jüngste ist und befürchtet, er könnte die Passphrase vergessen, hat er sie sich auf einem Zettel notiert. Diese Schwachstelle hat die berüchtigte Panzerknacker-Bande erkannt und der reichsten Ente der Welt auch prompt den Zettel abgeluchst. Sie staunten allerdings nicht schlecht, als sie das Stück Papier in ihren Händen hielten:
passphrase.png
Das ist doch nur irgendwelcher Kauderwelsch, aber bestimmt keine Passphrase! Hatte der alte Duck sie wieder mal auf den Leim gehen lassen?

Aber wer ein echer Panzerknacker ist, gibt so schnell nicht auf.

Stufe 1
Als Polizeibeamter verkleidet befragt einer der Panzerknacker Daniel Düsentrieb nach der Bedeutung des Buchstabensalats. Der gutgläubige Erfinder äußert die Vermutung, dass die Passphrase mit der Verschiebechiffre kodiert wurde.

Deine Aufgabe ist es nun, den verwendeten Schlüsselbuchstaben bzw. die unverschlüsselte Passphrase zu ermitteln. Zu diesem Zweck soll natürlich ein Programm geschrieben werden. Es erhält als Eingabe einen mit der Verschiebechiffre verschlüsselten Text, von dem bekannt ist, dass der zugehörige Klartext in deutscher Sprache verfasst ist. Das Programm soll daraus den (vermuteten) Klartext ermitteln und diesen ausgeben.

Beispiel
Eingabe:
Code:
xfcu leu jzcsvi czvs zty jvyi,
bree'j rlty nfyc xvsirltyve,
yrvkk zty ufty vze xreqvj dvvi,
dzty urivze ql krltyve.
Ausgabe: ist streng geheim! ;)


Stufe 2
Als die Panzerknacker den Code endlich geknackt und die Passphrase vor sich haben, hat Dagobert den Diebstahl seines Zettels längst bemerkt. Er hat die Passphrase sofort ändern lassen und die Anstrengungen der Panzerknacker somit wertlos gemacht. Trotzdem schreibt sich Dagobert einen Zettel mit der neuen Passphrase. Diesmal fotografiert er ihn allerdings mit seiner Digitalkamera, verbrennt das Papier anschließend und legt die Bilddatei verschlüsselt auf seinem Rechner ab.

Aber auch die Panzerknacker sind mit ihren Methoden mit der Zeit gegangen. Über einen Phishing-Angriff besorgen sie sich die verschlüsselte Datei. Zunächst können sie mit ihr allerdings nichts anfangen, da sie keine Ahnung haben, mit welchem Verfahren die Datei verschlüsselt wurde. Sie ziehen daher Gundel Gaukeley zu Rate, der sie den Glückszehner versprechen, wenn sie ihnen helfen kann. Ein Blick in ihre Kristallkugel verrät, dass die Datei mit einer affinen Chiffre verschlüsselt wurde. Die Datei wurde dazu als lückenlose Folge von 32-Bit vorzeichenlosen Ganzzahlen interpretiert. Diese Ganzzahlen wurden der Reihe nach abgearbeitet. Dabei wurde jede gemäß der Vorschrift der affinen Chiffre mit einem geheimen Schlüssel (a, b) und dem Modul m = 2^32 kodiert und das Ergebnis in die verschlüsselte Datei geschrieben. (Dies entspricht dem ECB-Modus.) Den Schlüssel konnte Gundel allerdings in ihrer Kristallkugel nicht erkennen, da grade in dem Moment der Akku leer wurde und sie ihr Ladekabel am Vesuv vergessen hatte.

Die Aufgabe sollte jetzt klar sein: schreibe ein Programm, das den geheimen Schlüssel ermittelt und die Datei (im Anhang) dekodiert. Dazu ist etwas lineare Algebra (modulare Arithmetik) und Kombinationsgabe erforderlich. Ich versichere aber, dass die Aufgabe tatsächlich lösbar ist. Wenn wirklich keiner eine Idee für die Lösung hat, kann ich auch noch ein paar Tipps geben.


Und jetzt ran an die Tasten und viel Spaß beim Programmieren!

P.S.: Die beiden Stufen können natürlich unabhängig voneinander gelöst werden.
 

Anhänge

Zuletzt bearbeitet:

OnlyFoo

Erfahrenes Mitglied
#2
Haha! Ersten Code genackt :)
Super Aufgabe!

Ich hab noch ein paar Beispiele zusammengestellt...

Code:
pbkxj tkqd sw uywzvodd fobgkrbvycdox
dkhs aeob nebmr lkiobx
Code:
ebfgvt jveq qrf tyrvfrf fpuvrar 
jraa xrva jntra qehrore ynrhsg
sebfgvt jveq qrf znaarf zvrar
jraa re no haq mh avpug fähsg.
Code:
mna txyo cdc fnq, 
mrn odnbbn bcrwtnw
qxnlqbcn inrc 
nrw krna id carwtnw...
Code:
bijzyh ohx guft, 
uv ch xyh bufm.
Code:
hoz xy bogjyh
hyc xu tcheu,
gilau goy'gu qummyl nlcheyh!
oyvylgilayh gimn,
xlog jlimn.
Code:
'ulu tlaly cvy
'ulu tlaly g'ybljr
'ulu tlaly vip
'ulu tlaly hbmp
qlaga zhbmp
 

Anhänge

Zuletzt bearbeitet:

OnlyFoo

Erfahrenes Mitglied
#6
Ich habe hier im Anhang nochmal vier Bilder (zweimal die selben, sry ^^) mit unterschiedlichen Schlüssel-Paaren angehängt. Musste nämlich feststellen, dass ich Glück beim Entschlüsseln des gegebenen Bildes hatte...
 

Anhänge

zeja

Erfahrenes Mitglied
#7
Hmm also irgendwie komm ich mit dem entschlüsseln von dem zweiten Bild noch nicht so vorran...

Es ist doch richtig, dass ich die möglichen Schlüsselpaare (a,b) ermitteln muss? Im Bereich bis m = 2^32 sind das ziemlich viele. Zumindest wenn man Wikipedia glaubt. Das was ich verstanden habe:
a ist eine Zahl im Bereich von 0 bis m-1 wobei ggT(a,m) = 1
b ist eine beliebige Zahl im Bereich von 0 bis m-1

Wie wird nun das Inverse Element zu a berechnet? Ist die Eingabe für den Algorithmus in http://de.wikipedia.org/wiki/Erweiterter_Euklidischer_Algorithmus#Rekursive_Variante_2 nun a,b oder a,m? Und welches von den 3 Ergebnissen ist dann das inverse zu a?
 

OnlyFoo

Erfahrenes Mitglied
#8
Hmm also irgendwie komm ich mit dem entschlüsseln von dem zweiten Bild noch nicht so vorran...

Es ist doch richtig, dass ich die möglichen Schlüsselpaare (a,b) ermitteln muss? Im Bereich bis m = 2^32 sind das ziemlich viele. Zumindest wenn man Wikipedia glaubt. Das was ich verstanden habe:
a ist eine Zahl im Bereich von 0 bis m-1 wobei ggT(a,m) = 1
b ist eine beliebige Zahl im Bereich von 0 bis m-1

Wie wird nun das Inverse Element zu a berechnet? Ist die Eingabe für den Algorithmus in http://de.wikipedia.org/wiki/Erweiterter_Euklidischer_Algorithmus#Rekursive_Variante_2 nun a,b oder a,m? Und welches von den 3 Ergebnissen ist dann das inverse zu a?
Ja wiki ist da recht unverständlich.
euclid( a, m ) und davon das mittlere Ergebnis ist das Inverse zu a.

Deine Bedingungen für a und b stimmen. Durchprobieren ist nicht soo klug, Unten im Wikiartikel steht wo die Schwachstelleim Algorithmus ist.
 
#9
Die englische Wikipedia ist da (wie so oft) ausführlicher: http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Eine Erklärung zum inversen Element: Sei a ein invertierbares Element des Restklassenrings modulo m. Da a invertierbar ist, wissen wir, dass ggT(a, m) = 1 gilt. Folglich existieren ganze Zahlen c, d mit ca + dm = 1 (berechenbar über den euklidischen Algorithmus). Reduktion modulo m ergibt:
Code:
ca ? 1  mod m
Also ist c das Inverse von a.

Das Durchprobieren aller möglichen Schlüssel würde ich nicht empfehlen, da es davon ?(2^32) * 2^32 = 2^31 * 2^32 = 2^63 = 9.223.372.036.854.775.808 Stück gibt. Selbst wenn man mit einem 3-GHz-Prozessor arbeitet, der pro Taktzyklus einen Schlüssel testen kann, müsste man im schlimmsten Fall immer noch rund ein Jahrhundert auf das Ergebnis warten :eek:

Grüße, Matthias
 

Erik

Erfahrenes Mitglied
#10
Eine Erklärung zum inversen Element: Sei a ein invertierbares Element des Restklassenrings modulo m. Da a invertierbar ist, wissen wir, dass ggT(a, m) = 1 gilt. Folglich existieren ganze Zahlen c, d mit ca + dm = 1 (berechenbar über den euklidischen Algorithmus). Reduktion modulo m ergibt:
Code:
ca ? 1  mod m
Also ist c das Inverse von a.
:confused:
Ich glaub da reicht 9. Klasse Mathe nicht mehr aus.
Ich werd nur das erste einreichen. :(

Gruß
x y z
 

Chumper

Erfahrenes Mitglied
#12
Besteht die erste Aufgabe darin, das zu entschlüsseln und mit dem Programm alle Lösungen anzubieten, oder soll das Programm die richtige Lösung automatisch finden?

Wenn es nur das erstere wäre, wäre das zu einfach, ich habe die zweite Variante genommen und eigentlich funktioniert das ganz gut.
 
Zuletzt bearbeitet:
#15
Jetzt müßte ich nur noch wissen wie man ein Gleichungssystem löst, in dem Modulo vorkommt.
„Im Prinzip“ so wie man auch eines ohne Modulo lösen würde: eine Gleichung nach einer Variable auflösen, den so gewonnenen Ausdruck für die Variable in die nächste Gleichung einsetzen etc. Mal ein völlig aus der Luft gegriffenes ;) Beispiel:
Code:
a * x1 + b = y1  mod m  (I)
a * x2 + b = y2  mod m  (II)

(I) nach b auflösen:
b = y1 - a * x1  mod m  (*)

(*) in (II) einsetzen:
a * x2 + y1 - a * x1 = y2  mod m  (**)

(**) versuchen nach a aufzulösen:
a * (x2 - x1) = y2 - y1  mod m  (***)
Hier stößt man möglicherweise auf ein Problem: man möchte jetzt gern das Inverse von (x2 - x1) von rechts an die Gleichung multiplizieren. Es kann allerdings vorkommen, dass (x2 - x1) überhaupt nicht invertierbar ist. Dann muss man noch etwas mehr Energie reinstecken, um auf das Ergebnis zu kommen. Das kann man sich aber sparen, wenn man x1 und x2 im Rahmen der Möglichkeiten so wählt, dass die Differenz invertierbar ist. Hoffe das hilft etwas weiter, ohne zu viel zu verraten.

Grüße, Matthias
 

zeja

Erfahrenes Mitglied
#19
Danke Matthias. Gedacht hab ich also richtig. Die Formel war im Prinzip auch richtig nur die eine Variable und meine UnsignedInt<-->Byte Array Konvertierungen nicht so recht. Aber nun klappts. Tolle Sache.... ich kann ja auch nicht davon lassen bis es geht :)
 

Neue Beiträge