Die Herausforderung
Eine einfache Herausforderung "Spion gegen Spion".
Schreiben Sie ein Programm mit folgenden Spezifikationen:
- Das Programm kann in einer beliebigen Sprache geschrieben sein, darf jedoch nicht länger als 512 Zeichen sein (wie in einem Codeblock auf dieser Site dargestellt).
- Das Programm muss 5 vorzeichenbehaftete 32-Bit-Ganzzahlen als Eingaben akzeptieren. Es kann die Form einer Funktion annehmen, die 5 Argumente akzeptiert, einer Funktion, die ein einzelnes Array mit 5 Elementen akzeptiert, oder eines vollständigen Programms, das 5 Ganzzahlen aus einer beliebigen Standardeingabe liest.
- Das Programm muss eine vorzeichenbehaftete 32-Bit-Ganzzahl ausgeben.
- Das Programm muss genau dann 1 zurückgeben, wenn die fünf als Folge interpretierten Eingaben mit einer bestimmten arithmetischen Folge der Wahl des Programmierers übereinstimmen, die als "Schlüssel" bezeichnet wird. Die Funktion muss für alle anderen Eingänge 0 zurückgeben.
Eine arithmetische Folge hat die Eigenschaft, dass jedes aufeinanderfolgende Element der Folge dem Vorgänger plus einer festen Konstante entspricht a
.
Dies ist beispielsweise 25 30 35 40 45
eine arithmetische Folge, da jedes Element der Folge dem Vorgänger plus 5 entspricht.17 10 3 -4 -11
entspricht. Dies ist auch eine arithmetische Folge, da jedes Element dem Vorgänger plus -7 entspricht.
Die Folgen 1 2 4 8 16
und 3 9 15 6 12
sind keine arithmetischen Folgen.
Ein Schlüssel kann eine beliebige arithmetische Folge Ihrer Wahl sein, mit der einzigen Einschränkung, dass Folgen mit Ganzzahlüberlauf nicht zulässig sind. Das heißt, die Reihenfolge muss streng zunehmen, streng abnehmen oder alle Elemente müssen gleich sein.
Angenommen, Sie wählen den Schlüssel aus 98021 93880 89739 85598 81457
. Ihr Programm muss 1 zurückgeben, wenn die Eingaben (nacheinander) mit diesen fünf Zahlen übereinstimmen, andernfalls 0.
Bitte beachten Sie, dass das Mittel zum Schutz des Schlüssels von Ihrem eigenen neuartigen Design sein sollte. Probabilistische Lösungen, die mit einer Wahrscheinlichkeit ungleich Null falsch positive Ergebnisse liefern können, sind ebenfalls nicht zulässig. Verwenden Sie insbesondere keine standardmäßigen kryptografischen Hashes, einschließlich Bibliotheksfunktionen für standardmäßige kryptografische Hashes.
Die Wertung
Die kürzeste (n) nicht geknackte (n) Einsendung (en) pro Zeichenanzahl wird (werden) zum Gewinner erklärt.
Bei Unklarheiten können Sie gerne nachfragen oder Kommentare abgeben.
Die Gegen-Herausforderung
Alle Leser, einschließlich derer, die ihre eigenen Programme eingereicht haben, werden aufgefordert, Einsendungen zu "knacken". Ein Beitrag wird geknackt, wenn sein Schlüssel im zugehörigen Kommentarbereich veröffentlicht wird. Wenn eine Einreichung 72 Stunden lang ohne Änderung oder Crack andauert, wird sie als "sicher" eingestuft und jeder nachfolgende Erfolg beim Cracken wird für den Wettbewerb ignoriert.
Unter "Haftungsausschluss" finden Sie Einzelheiten zur aktualisierten Richtlinie für Cracking-Scores.
Gebrochene Einsendungen werden von der Konkurrenz ausgeschlossen (sofern sie nicht "sicher" sind). Sie sollten nicht bearbeitet werden. Wenn ein Leser ein neues Programm einreichen möchte, sollte er dies in einer separaten Antwort tun.
Der / die Cracker mit der (den) höchsten Punktzahl (en) wird (werden) zusammen mit den Entwicklern der Gewinnerprogramme zum Gewinner erklärt.
Bitte knacken Sie nicht Ihren eigenen Beitrag.
Viel Glück. :)
Bestenliste
Vorletzte Platzierung (in Erwartung der Sicherheit von Dennis 'Einreichung von CJam 49).
Sichere Schließfächer
- CJam 49, Dennis
- CJam 62, Dennis sicher
- CJam 91, Dennis sicher
- Python 156, Maarten Baert sicher
- Perl 256, chilemagic safe
- Java 468, Geobits sicher
Unaufhaltsame Cracker
- Peter Taylor [Ruby 130, Java 342, Mathematica 146 *, Mathematica 72 *, CJam 37]
- Dennis [Python 13, Python 86 *, Lua 105 *, GolfScript 116, C 239 *]
- Martin Büttner [Javascript 125, Python 128 *, Ruby 175 *, Ruby 249 *]
- Tyilo [C 459, Javascript 958 *]
- freddieknets [Mathematica 67 *]
- Ilmari Karonen [Python27 182 *]
- salpetrig [C 212 *]
* nicht konforme Einreichung
Haftungsausschluss (Aktualisiert 23.15 Uhr EST, 26. August)
Da die Bewertungsprobleme endlich die kritische Masse erreichen (vorausgesetzt, zwei Drittel der geknackten Einreichungen sind bislang nicht konform), habe ich die besten Cracker in Bezug auf die Anzahl der geknackten Einreichungen (primär) und die Gesamtzahl der Zeichen in konformen geknackten Einreichungen eingestuft (sekundär).
Wie zuvor sind die genauen Einsendungen geknackt, die Länge der Einsendungen und ihr Konformitäts- / Nicht-Konformitätsstatus markiert, sodass die Leser ihre eigenen Rankings ableiten können, wenn sie glauben, dass die neuen offiziellen Rankings unfair sind.
Ich entschuldige mich dafür, dass ich die Regeln so spät im Spiel geändert habe.
Antworten:
CJam, 62 Zeichen
Stack Exchange ist anfällig dafür, nicht druckbare Zeichen zu verfälschen, aber das Kopieren des Codes aus dieser Paste und das Einfügen in den CJam-Interpreter funktioniert für mich einwandfrei .
Wie es funktioniert
Nach dem Ersetzen der Unicode-Zeichenfolge durch eine ASCII-Zeichenfolge wird der folgende Code ausgeführt:
Dieser Ansatz verwendet Bivium-B (siehe Algebraische Analyse von Trivium-ähnlichen Chiffren ), eine abgeschwächte Version der Stream-Chiffre Trivium .
Das Programm verwendet die Folge von ganzen Zahlen als Anfangszustand, aktualisiert den Zustand 434-mal (354 Runden erreichen die volle Diffusion) und erzeugt 177 Bit der Ausgabe, die es mit denen der richtigen Folge vergleicht.
Da die Größe des Zustands genau 177 Bit beträgt, sollte dies ausreichen, um den Anfangszustand eindeutig zu identifizieren.
Beispiellauf
quelle
CJam, 91 Zeichen
Stack Exchange ist anfällig dafür, nicht druckbare Zeichen zu verfälschen, aber das Kopieren des Codes aus dieser Paste und das Einfügen in den CJam-Interpreter funktioniert für mich einwandfrei .
Wie es funktioniert
Nach dem Ersetzen der Unicode-Zeichenfolge durch Ganzzahlen (unter Berücksichtigung der Ziffern der Basis-65533-Zahlen) wird der folgende Code ausgeführt:
Da 13 gleich dem Totienten des Moduls ist (der Totient ist geheim, Sie müssen mir also nur vertrauen), führen unterschiedliche Basen zu unterschiedlichen Ergebnissen, dh die Lösung ist einzigartig.
Wenn jemand den kleinen Exponenten (13) nicht ausnutzen kann, ist die effizienteste Möglichkeit, diese Sperre aufzuheben, die Faktorisierung des Moduls (siehe RSA-Problem ). Ich habe eine 512-Bit-Ganzzahl als Modul gewählt, die 72 Stunden Faktorisierungsversuchen standhalten sollte.
Beispiellauf
quelle
found 1740001 rational and 1739328 algebraic entries
; Es hat seitdem fast 100 Stunden gedauert, um sie zu verarbeiten und zu berichtensieving in progress b = 46583, 0 complete / 0 batched relations (need 44970493)
.Python - 128
Lass es uns versuchen:
(Erwartet, dass der Benutzer 5 durch Kommas getrennte Zahlen eingibt, z
1,2,3,4,5
. B. )quelle
32416190039,32416190047,32416190055,32416190063,32416190071
Java: 468
Die Eingabe erfolgt als
k(int[5])
. Kaution früh, wenn nicht gleichmäßig verteilt. Andernfalls muss ein bisschen herausgefunden werden, ob alle zehn Hashes korrekt sind. Bei großen Zahlen kann "ein bisschen" zehn Sekunden oder länger bedeuten, sodass Cracker möglicherweise davon abgehalten werden.quelle
Java: 342
Hier ist ein auf Zeichenfolgen basierendes Schließfach, das sowohl von der Anzahl der eingegebenen Zeichen als auch von der spezifischen Eingabe abhängt. Die Sequenz könnte auf obskuren Popkulturreferenzen basieren. Habe Spaß!
Ein bisschen ungolfed:
quelle
-8675309
, Delta ist5551212
.Python, 147
Edit: kürzere Version basierend auf Dennis 'Kommentar. Ich habe auch die Sequenz aktualisiert, um zu verhindern, dass Informationen verloren gehen.
Basierend auf dem diskreten Logarithmusproblem, von dem angenommen wird, dass es nicht zu knacken ist, jedoch ist die von mir verwendete Primzahl wahrscheinlich zu klein, um sicher zu sein (und es kann auch andere Probleme geben, die ich nicht kenne). Und Sie können es natürlich brachial erzwingen, da die einzigen Unbekannten zwei 32-Bit-Ganzzahlen sind.
quelle
c=1
, berechnenc=(c<<32)+d
und entsprechend ändern.Javascript 125
Dieser sollte ziemlich schnell geknackt werden. Ich werde etwas Stärkeres nachholen.
quelle
0, 3913, 7826, 11739, 15652
Rubin, 175
Im Gegensatz zur Verwendung eines kryptografischen Hashs oder
srand
ist dies nachweislich einzigartig (was ein kleiner Hinweis ist). Nimmt fünf Zahlen über STDIN entgegen, die durch ein oder mehrere nicht ziffern- oder neuzeilige Zeichen begrenzt sind. Ausgänge zu STDOUT.quelle
622238809,1397646693,2173054577,2948462461,3723870345
(Meine vorherige Vermutung hatte einen Fehler, aber dieser ist getestet). Ich denke nicht, dass dies gültig ist, da die letzte Zahl nicht in eine vorzeichenbehaftete 32-Bit-Ganzzahl passt.GolfScript (116 Zeichen)
Übernimmt Eingaben als durch Leerzeichen getrennte Ganzzahlen.
quelle
-51469355 -37912886 -24356417 -10799948 2756521
C 459 Bytes
Gelöst von Tyilo - LESEN SIE DIE BEARBEITUNG UNTEN
Wir brauchen jemanden, der eine C-Lösung schreibt, nicht wahr? Ich beeindrucke niemanden mit Länge, ich bin kein Golfspieler. Ich hoffe es ist eine interessante Herausforderung!
Ich glaube nicht, dass es einen offensichtlichen Weg gibt, diesen zu knacken, und ich warte gespannt auf alle Versuche! Ich kenne diese Lösung als einzigartig. Sehr minimale Verschleierung, hauptsächlich, um die Längenanforderungen zu erfüllen. Dies kann einfach getestet werden:
PS: Es gibt eine Bedeutung für sich
a[0]
selbst, und ich würde gerne sehen, dass jemand in den Kommentaren darauf hinweist!BEARBEITEN:
Lösung:
6174, 48216, 90258, 132300, 174342
Ein Hinweis zum Knacken:
Dies ist zwar nicht die verwendete Methode (siehe die Kommentare), aber ich habe meine eigene Chiffre mit einer sehr einfachen Bruteforce geknackt. Ich verstehe jetzt, dass es äußerst wichtig ist, die Zahlen groß zu machen. Der folgende Code kann jede Chiffre knacken, für
upper_bound
die eine Obergrenze bekannt ista[0] + a[1] + a[2] + a[3] + a[4]
. Die obere Schranke in der obigen Ziffer ist457464
, die aus dem Gleichungssystem desb[]
Algorithmus und einem gewissen Durcharbeiten desselben abgeleitet werden kann. Es kann gezeigt werden, dassb[4] = a[0] + a[1] + a[2] + a[3] + a[4]
.Damit
a[0] = 6174
hat diese Schleife meine Arbeit in weniger als einer Minute unterbrochen.quelle
6174, 48216, 90258, 132300, 174342
.Mathematica
8067Laufen:
Wahrscheinlich ziemlich leicht zu knacken, könnte auch mehrere Lösungen haben.
Update: Verbessertes Golfen mit Martin Büttner. Die Funktionalität der Funktion und des Schlüssels hat sich nicht geändert.
quelle
{58871,5592,-47687,-100966,-154245}
NextPrime
das negative Werte zurückgeben könnte. Wie hast du das gefunden?Python27,
283182Okay, ich bin sehr zuversichtlich in mein Schließfach, aber es ist ziemlich lang, da ich Berechnungen, die schwierig umzukehren sind, zur Eingabe hinzugefügt habe, um es gut zu machen - schwierig umzukehren.
edit: Danke an colevk für das weitere Golfen. Während der Bearbeitung wurde mir klar, dass mein Algorithmus sowohl einen Fehler als auch einen Fehler aufweist. Vielleicht habe ich beim nächsten Mal mehr Glück.
quelle
121174841 121174871 121174901 121174931 121174961
funktioniert, aber nur, wenn die Liste[1,3,5,7]
in Zeile 7 durch ersetzt wird[1,3,5,7,11]
.Mathematica
142146BEARBEITEN : Schlüssel war nicht eindeutig, hinzugefügt 4 Zeichen, jetzt ist es.
(Leerzeichen und Zeilenumbrüche zur besseren Lesbarkeit hinzugefügt, nicht gezählt und nicht benötigt).
Verwendung:
quelle
256208
Delta-5
.IntegerDigits
und dann Kandidaten für die Anfangslaufzeit und das Delta zu ermitteln.NextPrime
. Wenn wir es um plus oder minus eins variieren, gibt mindestens einer davon die gleiche nächste Primzahl.Von @Dennis in 2 Stunden geknackt
Nur eine einfache Möglichkeit, die Dinge in Gang zu bringen - ich gehe davon aus, dass dies schnell geknackt wird.
Pyth , 13
Übernimmt die kommagetrennte Eingabe für STDIN.
Führen Sie es folgendermaßen aus (-c bedeutet, dass Sie das Programm als Befehlszeilenargument verwenden):
Das Programm wurde behoben - ich hatte die Spezifikation nicht verstanden.
Diese Sprache könnte für diesen Wettbewerb zu esoterisch sein - Wenn OP das meint, werde ich sie entfernen.
quelle
1,2,3,4,5
is the key?97,96,95,94,93
(I just killed my cracking score.)Lua 105
I suspect it won't be long before it's cracked, but here we go:
(spaces added for clarity, but are not part of count)
quelle
3, 7, 11, 15, 19
or6, 14, 22, 30, 38
t1==0
whenverS
is increasing. Also, both conditions are homogeneous; ifS
is a solution, so iskS
.Perl - 256
I had to put in a lot of error handling logic and this can definitely be golfed down a lot more. It will print a
1
when you get the right five numbers. It will hopefully print a0
for everything else (might be errors or nothing, I don't know). If anyone wants to help improve the code or golf it more, feel free to help out!Call with:
quelle
Ruby - 130
Based on Linear Feedback Shift Register. Inputs by command line arguments.
Should be unique based on the nature of LFSRs. Clue: ascending and all positive.
Will give more clues if no one solves it soon.
quelle
Ruby, 249
Should be fun. Who needs math?
quelle
309, 77347, 154385, 231423, 308461
but I don't think it's unique.103, 232041, 463979, 695917, 927855
and3, 7966741, 15933479, 23900217, 31866955
. And I'm pretty sure there are other valid regexes by using additional+
s.()
or similar.CJam, 49 characters
Try it online.
How it works
The result will be 1 if and only if the second integer is a factor of the first, which is a product of two primes: the one corresponding to the secret sequence and another that doesn't correspond to any valid sequence. Therefore, the solution is unique.
Factorizing a 512 bit integer isn't that difficult, but I hope nobody will be able to in 72 hours. My previous version using a 320 bit integer has been broken.
Example run
quelle
Javascript 958
Converts the inputs to a number of data types and performs some manipulations relevant to each data type along the way. Should be fairly easily reversed for anyone that takes the time.
quelle
320689, 444121, 567553, 690985, 814417
C, 239 (Cracked by Dennis)
Go here for my updated submission.
Could probably be golfed a little more thoroughly. Admittedly, I haven't taken the time to prove the key is unique (it probably isn't) but its definitely on the order of a hash collision. If you crack it, please share your method :)
quelle
0 0 0 0 0
?C, 212 by Orby -- Cracked
https://codegolf.stackexchange.com/a/36810/31064 by Orby has at least two keys:
Orby asked for the method I used to crack it. Function p checks whether x is prime by checking
x%i==0
for all i between 2 and x (though using(x/i)*i==x
instead ofx%i==0
), and returns true if x is a prime number. Function f checks that all of a, b, c, d and e are prime. It also checks whether the number m, a concatenation of the decimal representations of e, d, c, b and a (in that order), is prime. The key is such that a,b,c,d,e and m are all prime.Green and Tao (2004) show that there exist infinitely many arithmetic sequences of primes for any length k, so we just need to look for these sequences that also satisfy m being prime. By taking long long as being bounded by -9.223372037e+18 and 9.223372037e+18, we know that for the concatenated string to fit into long long, the numbers have an upper bound of 9999. So by using a python script to generate all arithmetic sequences within all primes < 10000 and then checking whether their reverse concatenation is a prime, we can find many possible solutions.
For some reason I came up with false positives, but the two above are valid according to the program. In addition there may be solutions where e is negative and the rest are positive (p uses the modulus of x), but I didn't look for those.
The keys I gave are all arithmetic sequences but Orby's script doesn't appear to actually require the inputs to be an arithmetic sequence, so there may be invalid keys too.
quelle
MATLAB: Apparently invalid
Very simple, you just have to generate the right random number.
It can still error out, but that shouldn't be a problem.
quelle
MATLAB (with Symbolic Toolbox), 173 characters
This isn't an official entry and won't count towards anyone's cracking score, but it will net you mad bragging rights. ;)
The symbolic toolbox is only required to handle subtraction of big integers.
Brute forcing it should be a dog, but if you're familiar with the series it involves, the solution is trivial.
quelle
Python 2 (91)Edit: This isn't allowed because the argument for uniqueness is probabilistic. I give up.
Takes lists of integers as input, like
[1,2,3,4,5]
.The loop is meant to operate on the inputs in an annoying way, leaving a tower of sums and exponents. The idea is like discrete log, but with messy complication instead of mathematical simplicity. Maybe the compositeness of the of the modulus is a vulnerability, in which case I could make it something like
7**58+8
.I don't really know how I'd prove that my key is the only one, but the range of outputs is at least 10 times bigger than the range of inputs, so probably? Though maybe only a small fraction of potential outputs are achievable. I could always increase the number of digits at the cost of characters. I'll leave it up to you to decide what's fair.
Happy cracking!
quelle
Mathematica - 72
Version 2 of my script, with the same key as the one intended for my version 1.
This basically removes negative prime numbers for
NextPrime
.Running:
quelle
9244115
, delta25
.1073743739, 1073886396, 1074029053, 1074171710, 1074314367
Python, 86 characters
Enter the numbers like
1,2,3,4,5
.quelle
1,0,1,63021563418517255630720,0
.19960211, 31167202, 42374193, 53581184, 64788175
63021563418517255630720
isn't a 32-bit number.Python, 78
(Cracked by Tyilo in 14 mins)
Fun!
Okay, it doesn't display properly here :(
Expects a list of five numbers, eg. [1,2,3,4,5]
quelle
[-481890276, -594823292, -728999970, -887503650, -1073741792]
CJam, 37 characters (broken)
Try it online.
How it works
See my new answer.
Example run
quelle
737262825 208413108 3974530688 3445680972 2916831257
works but isn't an arithmetic progression. Factored in 3 hours 20 minutes. 512-bit numbers were apparently doable in 72 hours for $75 on EC2 two years ago, so I think that would have been safe.737262825 208413109 -320436607 -849286323 -1378136039
C, 212 (Cracked)
This is the same idea as my previous submission, golfed more thoroughly, with a bug corrected that passed 0,0,0,0,0 (Thanks to Dennis for pointing out the bug). Compile with -std=c99.
quelle
-7 -37 -67 -97 -127
,-157 -127 -97 -67 -37