Entwickler-Ecke
Ankündigungen - Adventsgewinnspiel 2008 - Tipps/Lösung zu Gewinnspiel 4
Gausi - Di 23.12.08 12:57
Titel: Adventsgewinnspiel 2008 - Tipps/Lösung zu Gewinnspiel 4
Weil morgen schon Heiligabend ist, und das Gewinnspiel dann endet, kommt hier der Tipp für das letzte Rätsel:
- Wem das hier zu schwer ist, dem sei gesagt: Lass einfach mal das Paranüsse knacken sein und fahr nach Paris auf eine Party. Das liegt ja nichtmal ein Parsec von hier entfernt. Unterhalte dich dort im Parlament mit ein paar paranoiden Parapsychologen über Parabeln in Parallelogrammen und Parfümherstellung im Paradies. Und wer jetzt denkt "Hier sind doch ein paar Par's zu viel...", der hat ganz recht.
Also: Viel Spaß beim Knobeln, und dabei die Weihnachtseinkäufe nicht vergessen! :D
Narses - Mi 24.12.08 14:46
Weil heute Weihnachten ist - und nur deswegen - gibt es eine kleine Winkrunde mit dem Gartenzaun:
- Im ersten Tipp waren ein paar Par's zuviel. Das haben ja alle verstanden (oder auch nicht :gruebel:). Im Rätsel selbst ist aber auch eins zuviel drin :!: Lässt man das weg, kommt man der Lösung schon sehr nahe... :zwinker:
mx :wave:
Narses
Narses - Do 25.12.08 01:30
Und hier die Auflösung für das letzte Rätsel, wieder zuerst die Tipps:
Die Buchstaben auf den Kerzen sind mit dem Paar (7,15) affin chiffriert und ergeben mit dem zugehörigen Paar (15,15) dechiffriert wieder:
Auf den Kerzen steht im Klartext: |
Ruprecht ist doof |
Damit ist Antwort 1 die korrekte Lösung. ;)
mx :wave:
Narses
GTA-Place - Do 25.12.08 01:35
Alles kein Problem. Rezept für ein gelugenes Rätsel 4:
Benötigt:
- Tipp 1
- Titel
- Wikipedia
- Geistesblitz (Marke Martok)
- Delphi
- BruteForce
Durchführung:
Man lese Tipp 1 ungefähr 483.482 Mal durch und verstehe nur Bahnhof. Dazu gibt man einen Geistesblitz von Martok. Hat man nun stundenlang die Wikipedia durchgelesen um herauszufinden, was Araffine Abbildungen sind, prüfe man weitere Möglichkeiten. Zum Schluss noch ein Schuss Delphi und BruteForce dazu. Fertig ist der Affine-Chifre-Knacker à la Carte.
Geschmack: *****
Anforderung: ******
Tipp: *****
Lösungsprogramm:
Siehe unten, es gab kein Lösungsprogramm :mrgreen:
BenBE - Do 25.12.08 01:48
Fand Rätsel 4 auch mehr als gelungen. Hat auf jeden Fall Spaß gemacht ...
Benötigt:
- Tipp 1
- Titel
- Wikipedia
- Geistesblitz (Marke Martok)
- PHP
- BruteForce
Durchführung:
Man lese Tipp 1 ungefähr 4.711 Mal durch und verstehe nur Bahnhof. Dazu gibt man einen Freundlichen Hinweis von GTA. Hat man nun kurz die Wikipedia überflogen, implementiere man eine Quick&Dirty-Lösung in PHP für einen Bruteforce-Ansatz über eine Known-Plaintext-Attacke und einer Invertierungstabelle. Fertig ist der Affine-Chifre-Knacker à la Carte.
Geschmack: *****
Anforderung: ******
Tipp: *****
Lösungsprogramm:
C#-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28:
| <?php
$s = ""; $a = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; $l = strlen($a);
$t = array(); for($x = 0; $x < strlen($s); $x++) { $t[] = strpos($a, $s[$x]); }
$b = array(1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25);
foreach($b as $j) { for($i = 0; $i < $l; $i++) { echo "<br/>\n"; echo "A = $j, B = $i: "; for($x = 0; $x < $l; $x ++) { $invtab[($j * $x + $i) % $l] = $x; } for($x = 0; $x < strlen($s); $x++) { echo $a[$invtab[$t[$x]]]; } } }
?> |
Martok - Do 25.12.08 01:59
Jup, war auf jeden fall geil ;)
Benötigt:
- Tipp 1
- Titel
- Wikipedia
- Geistesblitz (Marke Eigenbau)
- Delphi
- BruteForce, wurde mir aber abgenommen weil jemand schneller war :P
Durchführung:
Man lese die Frage und verstehe nur Bahnhof. Dann lasse man das etwas ziehen und warte auf Tipp Nummer 1. Streichen von par führt über Wikipedia zum Ergebnis. Implementieren einer sauberen Lösung und basteln an einer Lösung für das Negativ-mod-Problem und mitten drin Nachricht von GTA-Place kriegen weil er schon fertig ist. Damit fällt das Bruteforcen weg, fertig ist der Affine-Chifre-Knacker à la Carte.
Geschmack: *****
Anforderung: ******
Tipp: *****
Lösungsprogramm:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27:
| function index2chr(idx: Smallint): char; begin Result:= chr(ord('A') + idx); end;
function chr2idx(cc: char): Smallint; begin Result:= ord(cc) - ord('A'); end;
function mod26(x: smallint): smallint; begin if X >= 0 then Result:= x mod 26 else Result:= x mod 26 + 26; end;
function Decode(s: string; a_index, b: smallint): string; var p: integer; begin Result:= s; for p:= 1 to length(s) do if s[p] in ['A'..'Z'] then Result[p]:= index2chr(mod26(crypt[a_index][1] * (chr2idx(s[p]) - b))); end; |
Wolle92 - Do 25.12.08 02:21
Tja, melde mich mal mit einer Nicht-Lösung:
Also, dank Yogu bin ich darauf gekommen, dass in Narses Tipp ein Hinweis drinsteht:
Normalerweise schreibt Narses "cu" unter seine Posts, diesmal hat er mx geschrieben...
Also konnte man denken:
c -> m => 2 -> 12
u -> x => 20 -> 23
Dann hat man ja die tolle Rechnung in der Chiffre:
(a * x + b) mod 26...
Okay, dann hab ich mir also nen Array mit den Werten für a gemacht und zwei for-Schleifen ineinander gepackt und a, b und die beiden für 2 und 20 errechneten Werte ausgegeben, dann nach dem Wertepaar 12, 23 gesucht...
Problem war nur: Es gab kein Wertepaar 12, 23...
Und dann war Bescherung, Essen, Lego-Käfer bauen (noch nicht fertig), Gottesdienst und dann wars halb 1 und dann war vorbei...
Marc. - Do 25.12.08 02:22
Benötigt:
- Tipp 1
- Titel
- Wikipedia
- Geistesblitz (BenBe "Les den Tipp nochmal genau durch...")
- Delphi
- BruteForce
Durchführung:
Man lese Tipp1 mehrmals und gibt Gausi bei jedem Durchlesen recht, dass hier doch ein paar Par's zu viel sind...
Diese Aussage nimmt man jedoch zunächst als Fakt hin, bevor einem der eigentliche Sinn dieses Satzes plötzlich erschließt.
Die Umsetzung lief daraufhin beinahe reibungslos.
Geschmack: ******
Anforderung: ****
Tipp: *******
Lösungsprogramm:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33:
| function Crypt(s: string; a, b: Integer): string; var i: integer; a1: integer; begin SetLength(Result, length(s)); for i := 1 to length(result) do begin result[i] := Chr(((Ord(s[i]) - 65) * a + b) mod 26 + 65); end; end;
function DeCrypt(s: string; a, b: Integer): string; const ar1: array[1..12] of Integer = (1, 9, 21, 15, 3, 19, 7, 23, 11, 5, 17, 25); ar: array[1..12] of Integer = (1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25); var i, j: integer; a1: integer; begin for j := 1 to 12 do if (ar[j] = a) then begin a1 := ar1[j]; break; end;
SetLength(Result, length(s)); for i := 1 to length(result) do begin result[i] := Chr((Ord(s[i]) - 65 - b + 26) * a1 mod 26 + 65); end; end; |
Jann1k - Do 25.12.08 02:27
Bin ich eigentlich der einzige Idiot, der ne halbe Stunde lang überlegt hat was es denn bringen soll das "par" von "paar Buchstaben-Kerzen" wegzustreichen? Egal, großes Lob an das Team die Rätsel versüssen einem die Adventszeit immer wieder aufs neue.
Nersgatt - Do 25.12.08 10:56
Diese Mod mit negativen Zahlen hat mich wahnsinnig gemacht. Dass das ein Problem ist, habe ich bisher nicht gewusst.
Wikipedia-Beispiel durchgespielt -> Zu dem Schluss gekommen, dass die da falsch gerechnet haben.
Noch eine andere Erklärung zu der Verschlüsselung gesucht -> Die rechnen ja auch falsch.... oder??
Irgendwann habe ich es dann doch zusammen bekommen und bin mit Brute Force auf die richtige Lösung gekommen. Es sind ja nur 119 Schlüssel möglich. Man hätte aber auch auf die Idee kommen können, dass der selbe Schlüssel wie in dem Wiki-Beispiel verwendet wurde. (Bei Miau war die Programmstruktur mit der vom Wiki-Beispiel ja auch sehr ähnlich).
Das ganze Zusammen ergibt folgenden grauenhaften Code (aber funktioniert):
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| type TSchluessel = Record a : Integer; b : Integer; End;
const ar : Array [0..11] of Integer = (1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25); const ar1 : Array [0..11] of Integer = (1, 9, 21, 15, 3, 19, 7, 23, 11, 5, 17, 25); [...] private arSchluessel : Array of TSchluessel; |
Alle möglichen Schlüsselpaare berechnen:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34:
| Procedure TForm1.FillSchluessel; var a, i, b, k : Integer; bGGT : Boolean; begin SetLength(arSchluessel, 0);
for i := low(ar) to high(ar) do begin a := ar[i]; for b := a + 1 to 25 do begin bGGT := False; for k := 2 to a do begin if (a mod k = 0) and (b mod k = 0) then begin bGGT := True; break; end; end;
if not bGGT then begin setLength(arSchluessel, high(arSchluessel) + 2); arSchluessel[high(arSchluessel)].a := a; arSchluessel[high(arSchluessel)].b := b; end;
end; end;
end; |
Mod-Krücke
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
| Function TForm1.Rest (wert : Integer) : Integer; begin if wert >= 0 then result := wert mod 26 else begin result := wert; while result < 0 do result := result + 26; end; end; |
Entschlüsselung:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23:
| function TForm1.Decrypt(s: TSchluessel; sText: String): String; var a1, i, y: Integer; begin
result := ''; a1 := 0; i := 0; while (a1 = 0) and (i <= high(ar)) do begin if ar[i] = s.a then a1 := ar1[i]; inc(i); end;
for i := 1 to length(sText) do begin y := ord(sText[i]) - 65; result := result + Chr(rest(a1 * (y - s.b)) + 65); end;
end; |
Mit Brute Force alles durchprobieren:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15:
| procedure TForm1.Button1Click(Sender: TObject); var i : Integer; begin mem.Lines.Clear; FillSchluessel; for i := 0 to high(arSchluessel) do begin mem.lines.Add(intToStr(arSchluessel[i].a) + ';' + intToStr(arSchluessel[i].b) + ' ' + Decrypt(arSchluessel[i], eText.Text)); end;
mem.Lines.Add(intToStr(mem.Lines.Count));
end; |
Ich wäre dankbar, wenn mir jemand noch etwas Hintergrundinfo zu diesem Mod-Problem mit negativen Zahlen geben könnte? Ist die Mod-Funktion bei Delphi einfach nur anders definiert?
Danke,
Jens
Arne K. - Do 25.12.08 13:57
Hallo,
ich habe mich mit PHP dran versucht und bin auch beim mod (allerdings nur bei der Dechiffrierung?) kleben geblieben. Ich habe 15 Minuten hin und her überlegt, weil mir mein Computer (calc.exe und php.exe) ebenso wie mein Taschenrechner für 60/26=2R8<=>60mod26=8 ergeben hat und nicht 3R18. Die Funktion hat sich hier ja quasi der 60 "von oben" (bzw. im Negativen "von unten") genähert? Ich habe mir dann einfach eine eigene Mod-Funktion geschrieben, die genau das gemacht hat und weiter ging's, aber der mathematische Zusammenhang ist mir da bisher auch unklar.
Ergo: Ich würde mich über eine kurze Erklärung auch freuen =)
Beste Grüße,
Arne
jakobwenzel - Do 25.12.08 14:05
Delphi scheint bei
mod mit negativen Zahlen einfach mit dem Betrag zu rechnen.
Hier muss mans aber anders angehen, wie es auch schon im Wiki-Artikel zur Affinen Chiffre steht:
Arne K. - Do 25.12.08 14:09
Ach, interessant!
Den Teil hatte ich gar nicht gelesen. Ich habe mich wie gesagt quasi "von oben" genähert:
Quelltext
1: 2: 3:
| 60%26 ?= 18 26*3 = 78 = 60+18 => 60%26 = 18 |
So habe ich es auch implementiert und es hat wunderbar funktioniert, obwohl es ja im Wesentlichen dasselbe ist.
(warum das mathematisch so sein soll, frage ich mich aber immernoch. Für mich ist (-60)%26 per Definition eigentlich 8 )
Edit:
Ah ja, wer sich noch dafür interessiert, siehe hier:
http://de.wikipedia.org/wiki/Modulo#Varianten_der_Modulo-Funktion
Boldar - Do 25.12.08 15:33
mmmh ich hab Benbe's Geistesblitz verpasst...
Xentar - Do 25.12.08 16:56
Ahh, verdammt..
hab zwar das richtige Lösungswort raus, aber dieses dann falsch gedeutet :autsch:
War irgendwie der Meinung, dass "Die Kerzen ergeben eine verschlüsselte, abfällige Bemerkung über Engelchen." besser passt, auch wenn Ruprecht ja eigentlich kein Engel ist (könnt ja ein anderer so heißen). :autsch:
Nagut, trotzdem schönes Rätsel.
Hatte zeurst an Caesar Verschlüsselung gedacht, aber da kam nichts sinnvolles raus.
Xong - Do 25.12.08 21:56
Arne K. hat folgendes geschrieben : |
ich habe mich mit PHP dran versucht und bin auch beim mod (allerdings nur bei der Dechiffrierung?) kleben geblieben. |
Es reicht eine hinreichende große Zahl, die durch 26 geteilt, den Rest 0 ergibt, hinzuzuaddieren. So umgeht man die fehlerhafte Implementation des Modulo-Operators in den Programmiersprachen.
Ich habe einfach 2600 dazuaddiert.
Um Modulo zu verstehen, muss man sich mit Restklassen und Zahlenkörpern auseinandersetzen. Hat man eigentlich bei jedem Informatikstudium... :D
LG,
Xong
elundril - Fr 26.12.08 04:15
Xong hat folgendes geschrieben : |
Um Modulo zu verstehen, muss man sich mit Restklassen und Zahlenkörpern auseinandersetzen. Hat man eigentlich bei jedem Informatikstudium... :D |
Darf ich ein "Leider" an deinen Satz dranhängen? Das mit den Restklassen check ich nicht und das diese algebraischen strukturen auch nicht wirklich. Ringe, Körper, Gruppen, .... bäähhh kann ich da nur sagen!
Narses - Fr 26.12.08 15:16
Moin!
Wolle92 hat folgendes geschrieben : |
Also, dank Yogu bin ich darauf gekommen, dass in Narses Tipp ein Hinweis drinsteht:
Normalerweise schreibt Narses "cu" unter seine Posts, diesmal hat er mx geschrieben... |
:oops:
Wollte nur nett sein und mal "Merry Christmas" wünschen... :P
(also wieder verwirrungsfreies) cu :wave:
Narses
jaenicke - Fr 26.12.08 15:25
Narses hat folgendes geschrieben : |
Wollte nur nett sein und mal "Merry Christmas" wünschen... :P |
:rofl: :rofl: :rofl:
Das mx war mir noch nicht einmal aufgefallen. Irgendwie überlese ich anscheinend so einiges. :(
Aber in dem Fall war das ja nicht schlecht, falls ich es auch als Hinweis gedeutet hätte. :D
Yogu - Sa 27.12.08 19:50
Narses hat folgendes geschrieben : |
Wollte nur nett sein und mal "Merry Christmas" wünschen... :P |
Oh nö, dann hab ich den einzigen "Tipp", den ich verstanden habe, auch noch falsch verstanden :(
Naja, was solls - die anderen drei hab ich ja richtig gelöst. Das war auf jeden Fall eine Steigerung im Vergleich zu letzem Mal.
jaenicke - Sa 27.12.08 19:55
Naja, mir fehlte am Ende nur noch ein bisschen Zeit. Aber die anderen 3 und eine Paranuss hab ich ja richtig gehabt, insofern ärgere ich mich da nicht weiter drüber.
Ich hätte mit den Paranüssen früher anfangen sollen :D.
Boldar - Sa 27.12.08 19:55
Welche Paranuss hattest du denn?
Boldar - Sa 27.12.08 19:59
aso... da hab ich mich auch dran versucht, Nur ich hab den Bug mit Currency gefunden :flehan: :motz:
Moderiert von Narses: Smilietis kuriert
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!