Wyzwanie
Proste wyzwanie „szpieg kontra szpieg”.
Napisz program o następujących specyfikacjach:
- Program może być napisany w dowolnym języku, ale nie może przekraczać 512 znaków (przedstawionych w bloku kodu na tej stronie).
- Program musi zaakceptować 5 podpisanych 32-bitowych liczb całkowitych jako dane wejściowe. Może mieć postać funkcji, która akceptuje 5 argumentów, funkcji, która akceptuje pojedynczą tablicę 5-elementową lub kompletnego programu, który odczytuje 5 liczb całkowitych z dowolnego standardowego wejścia.
- Program musi wypisać jedną 32-bitową liczbę całkowitą ze znakiem.
- Program musi zwrócić 1 wtedy i tylko wtedy, gdy pięć wejść, interpretowanych jako sekwencja, odpowiada określonej sekwencji arytmetycznej wybranej przez programistę, zwanej „kluczem”. Funkcja musi zwrócić 0 dla wszystkich innych wejść.
Sekwencja arytmetyczna ma właściwość polegającą na tym, że każdy kolejny element sekwencji jest równy swojemu poprzednikowi plus pewna stała stała a
.
Na przykład 25 30 35 40 45
jest sekwencją arytmetyczną, ponieważ każdy element sekwencji jest równy swojemu poprzednikowi plus 5. Podobnie 17 10 3 -4 -11
jest sekwencją arytmetyczną, ponieważ każdy element jest równy jego poprzednikowi plus -7.
Sekwencje 1 2 4 8 16
i 3 9 15 6 12
nie są sekwencjami arytmetycznymi.
Kluczem może być dowolna wybrana przez ciebie sekwencja arytmetyczna, z jedynym ograniczeniem, że sekwencje obejmujące przepełnienie liczb całkowitych są niedozwolone. Oznacza to, że sekwencja musi być ściśle rosnąca, ściśle malejąca lub mieć wszystkie elementy równe.
Jako przykład załóżmy, że wybierasz klucz 98021 93880 89739 85598 81457
. Twój program musi zwrócić 1, jeśli dane wejściowe (w sekwencji) są zgodne z tymi pięcioma liczbami, a 0 w przeciwnym razie.
Należy pamiętać, że środki ochrony klucza powinny być opracowane według własnego projektu. Również rozwiązania probabilistyczne, które mogą zwracać wyniki fałszywie dodatnie z dowolnym niezerowym prawdopodobieństwem, są niedozwolone. W szczególności nie używaj żadnych standardowych skrótów kryptograficznych, w tym funkcji bibliotecznych dla standardowych skrótów kryptograficznych.
Punktacja
Najkrótsze niezłamywane materiały na liczbę znaków zostaną ogłoszone zwycięzcami.
W przypadku jakichkolwiek nieporozumień prosimy pytać lub komentować.
Kontr-wyzwanie
Wszystkich czytelników, w tym tych, którzy przesłali własne programy, zachęca się do „łamania” zgłoszeń. Zgłoszenie jest łamane, gdy jego klucz jest publikowany w powiązanej sekcji komentarzy. Jeśli przesłanie trwa 72 godziny bez modyfikacji lub krakowania, jest uważane za „bezpieczne”, a wszelkie kolejne sukcesy w krakowaniu będą ignorowane ze względu na konkurs.
Zobacz „Zrzeczenie się odpowiedzialności” poniżej, aby uzyskać szczegółowe informacje na temat zaktualizowanych zasad oceny wyników crackingu.
Zgłoszone zgłoszenia są eliminowane ze sporów (pod warunkiem, że nie są „bezpieczne”). Nie należy ich edytować. Jeśli czytelnik chce złożyć nowy program, powinien to zrobić w osobnej odpowiedzi.
Krakersy o najwyższym wyniku zostaną ogłoszone zwycięzcami wraz z twórcami zwycięskich programów.
Proszę nie łamać własnego zgłoszenia.
Powodzenia. :)
Tabela liderów
Klasyfikacja przedostatnia (w oczekiwaniu na bezpieczeństwo zgłoszenia Dennisa CJam 49).
Bezpieczne szafki
- CJam 49, Dennis
- CJam 62, Dennis bezpieczny
- CJam 91, Dennis bezpieczny
- Python 156, Maarten Baert bezpieczny
- Perl 256, bezpieczny dla dzieci
- Java 468, Bezpieczne geobity
Niepowstrzymani krakersy
- Peter Taylor [Ruby 130, Java 342, Mathematica 146 *, Mathematica 72 *, CJam 37]
- Dennis [Pyth 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 *]
- azotawy [C 212 *]
* przesłanie niezgodne
Oświadczenie (zaktualizowane 23.15 EST, 26 sierpnia)
Ponieważ problemy z punktowaniem w końcu osiągnęły masę krytyczną (biorąc pod uwagę, że dwie trzecie zgłoszonych do tej pory zgłoszeń są niezgodne), umieściłem w rankingu najlepszych crackerów pod względem liczby zgłoszonych zgłoszeń (pierwotne) i całkowitej liczby znaków w zgłoszeniach zgłoszonych do złamania (wtórny).
Tak jak poprzednio, dokładnie zgłoszone pęknięcia, długość zgłoszeń oraz ich status zgodności / niezgodności są oznaczone, aby czytelnicy mogli wyciągać własne rankingi, jeśli uważają, że nowe oficjalne rankingi są niesprawiedliwe.
Przepraszam za zmianę zasad w późnej fazie gry.
Odpowiedzi:
CJam, 62 znaki
Wymiana stosów jest podatna na fałszowanie niedrukowalnych znaków, ale kopiowanie kodu z tej pasty i wklejanie go do interpretera CJam działa dla mnie dobrze.
Jak to działa
Po zamianie ciągu Unicode na ciąg ASCII wykonywany jest następujący kod:
Podejście to wykorzystuje Bivium-B (patrz analiza algebraiczna szyfrów typu trivium ), osłabioną wersję szyfru strumieniowego trivium .
Program wykorzystuje sekwencję liczb całkowitych jako stan początkowy, aktualizuje stan 434 razy (354 rundy osiągają pełną dyfuzję) i generuje 177 bitów wyjścia, które porównuje z tymi o prawidłowej sekwencji.
Ponieważ rozmiar stanu wynosi dokładnie 177 bitów, powinno to wystarczyć do jednoznacznej identyfikacji stanu początkowego.
Przykładowy przebieg
źródło
CJam, 91 znaków
Wymiana stosów jest podatna na fałszowanie niedrukowalnych znaków, ale kopiowanie kodu z tej pasty i wklejanie go do interpretera CJam działa dla mnie dobrze.
Jak to działa
Po zamianie ciągu Unicode na liczby całkowite (biorąc pod uwagę cyfry znaków liczb podstawowych 65533), wykonywany jest następujący kod:
Ponieważ 13 jest coprime do sumy modułu (totient jest tajny, więc musisz mi tylko zaufać), różne zasady wygenerują różne wyniki, tj. Rozwiązanie jest unikalne.
Chyba że ktoś może wykorzystać mały wykładnik (13), najbardziej skutecznym sposobem na złamanie tego zamka jest rozkładanie modułu na moduł (patrz problem RSA ). Wybrałem 512-bitową liczbę całkowitą dla modułu, która powinna wytrzymać 72 godziny prób faktoryzacji.
Przykładowy przebieg
źródło
found 1740001 rational and 1739328 algebraic entries
; od tego czasu mieli prawie 100 godzin na ich przetworzenie i raportysieving in progress b = 46583, 0 complete / 0 batched relations (need 44970493)
.Python - 128
Spróbujmy tego:
(Oczekuje, że użytkownik wprowadzi 5 liczb oddzielonych przecinkami, np
1,2,3,4,5
.)źródło
32416190039,32416190047,32416190055,32416190063,32416190071
Java: 468
Dane wejściowe są podane jako
k(int[5])
. Kaucje wcześnie, jeśli nie są równo rozmieszczone. W przeciwnym razie trzeba nieco dowiedzieć się, czy wszystkie dziesięć skrótów jest poprawne. W przypadku dużych liczb „trochę” może oznaczać dziesięć lub więcej sekund, więc może zniechęcić crackerów.źródło
Java: 342
Oto blokada łańcuchowa, która zależy zarówno od liczby znaków wejściowych, jak i od konkretnych danych wejściowych. Sekwencja może być oparta na niejasnych odniesieniach do popkultury. Baw się dobrze!
Nieco golfista:
źródło
-8675309
, delta to5551212
.Python, 147
Edycja: krótsza wersja na podstawie komentarza Dennisa. Zaktualizowałem też sekwencję, aby uniknąć wycieku jakichkolwiek informacji.
Oparty na problemie logarytmu dyskretnego, który uważa się za niemożliwy do rozwiązania, jednak liczba podstawowa, której używam, jest prawdopodobnie zbyt mała, aby była bezpieczna (i może mieć inne problemy, nie wiem). Możesz oczywiście użyć siły, ponieważ jedynymi niewiadomymi są dwie 32-bitowe liczby całkowite.
źródło
c=1
, obliczającc=(c<<32)+d
i zmieniając stałą.JavaScript 125
Ten powinien zostać złamany dość szybko. Zajmę się czymś silniejszym.
źródło
0, 3913, 7826, 11739, 15652
Ruby, 175
W przeciwieństwie do korzystania z kryptograficznego skrótu lub
srand
, jest to możliwe do udowodnienia, że jest to wyjątkowa wskazówka. Pobiera pięć cyfr przez STDIN, oddzielonych dowolnymi nie cyfrowymi, nieliniowymi znakami lub znakami. Wyjścia do STDOUT.źródło
622238809,1397646693,2173054577,2948462461,3723870345
(moje poprzednie przypuszczenie było błędem, ale ten został przetestowany). Nie sądzę, aby było to poprawne, ponieważ ostatnia liczba nie pasuje do 32-bitowej liczby całkowitej ze znakiem.GolfScript (116 znaków)
Pobiera dane wejściowe jako liczby całkowite rozdzielone spacjami.
źródło
-51469355 -37912886 -24356417 -10799948 2756521
C 459 bajtów
ROZWIĄZANE PRZEZ TYILO - CZYTAJ PONIŻEJ EDYCJI
Potrzebujemy kogoś, kto napisze rozwiązanie C, prawda? Nie robię na nikim wrażenia długością, nie jestem golfistą. Mam nadzieję, że to ciekawe wyzwanie!
Nie sądzę, że istnieje oczywisty sposób na złamanie tego i z niecierpliwością czekam na wszystkie próby! Wiem, że to rozwiązanie jest wyjątkowe. Bardzo minimalne zaciemnienie, głównie w celu spełnienia wymagań dotyczących długości. Można to przetestować po prostu:
PS Jest to
a[0]
samo w sobie ważne i chciałbym, aby ktoś zauważył to w komentarzach!EDYTOWAĆ:
Rozwiązanie:
6174, 48216, 90258, 132300, 174342
Uwaga na temat łamania:
Chociaż nie jest to stosowana metoda (patrz komentarze), zdarzyło mi się złamać własny szyfr bardzo łatwą siłą. Rozumiem teraz, że niezwykle ważne jest, aby liczby były duże. Poniższy kod może złamać dowolny szyfr, dla którego
upper_bound
jest znana górna granicaa[0] + a[1] + a[2] + a[3] + a[4]
. Górną granicą powyższego szyfru jest457464
, która może być wyprowadzona z układu równańb[]
i pewnego sposobu działania algorytmu. Można to pokazaćb[4] = a[0] + a[1] + a[2] + a[3] + a[4]
.Z
a[0] = 6174
ta pętla złamał moją pracę w nieco krótszym niż minuta.źródło
6174, 48216, 90258, 132300, 174342
.Mathematica
8067Bieganie:
Prawdopodobnie dość łatwe do złamania, może również mieć wiele rozwiązań.
Aktualizacja: Ulepszono grę w golfa dzięki temu, co sugerował Martin Büttner. Funkcjonalność funkcji i klawisza nie uległa zmianie.
źródło
{58871,5592,-47687,-100966,-154245}
NextPrime
może zwrócić wartości ujemne. Jak to znalazłeś?Python27,
283182W porządku, jestem bardzo pewny swojej szafki, jednak jest ona dość długa, ponieważ do danych wejściowych dodałem obliczenia „trudne do odwrócenia”, aby było dobrze - trudno ją odwrócić.
edycja: Podziękowania dla colevk za dalszą grę w golfa. Podczas edycji zdałem sobie sprawę, że w moim algorytmie był błąd, a także wada, może następnym razem będę miał więcej szczęścia.
źródło
121174841 121174871 121174901 121174931 121174961
działa, ale tylko wtedy, gdy lista[1,3,5,7]
w linii 7 zostanie zastąpiona[1,3,5,7,11]
.Mathematica
142146EDYCJA : klucz nie był unikalny, dodano 4 znaki, teraz jest.
(Dodano spacje i znaki nowej linii dla czytelności, nie są liczone i nie są potrzebne).
Stosowanie:
źródło
256208
, delta-5
.IntegerDigits
a następnie na uwzględnieniu kandydatów w początkowej kadencji i delcie.NextPrime
; jeśli zmienimy go o plus lub minus jeden, przynajmniej jeden z nich da tę samą kolejną liczbę pierwszą.Pęknięty przez @Dennis w 2 godziny
Po prostu prosty sposób na rozpoczęcie - w pełni oczekuję, że zostanie to szybko złamane.
Pyth , 13 lat
Pobiera wejście oddzielone przecinkami na STDIN.
Uruchom go w ten sposób (-c oznacza, że weź program jako argument wiersza poleceń):
Naprawiono program - nie zrozumiałem specyfikacji.
Ten język może być zbyt ezoteryczny dla tego konkursu - jeśli OP tak uważa, usunę go.
źródło
1,2,3,4,5
jest klucz?97,96,95,94,93
(Właśnie zabiłem swój wynik cracking.)Lua 105
Podejrzewam, że nie potrwa długo, zanim się pęknie, ale proszę bardzo:
(spacje dodane dla przejrzystości, ale nie są częścią liczenia)
źródło
3, 7, 11, 15, 19
lub6, 14, 22, 30, 38
t1==0
kiedykolwiekS
rośnie. Ponadto oba warunki są jednorodne; jeśliS
jest rozwiązaniem, tak też jestkS
.Perl - 256
Musiałem wprowadzić wiele logiki obsługi błędów, a to zdecydowanie można pograć w golfa jeszcze bardziej. Wydrukuje a,
1
gdy otrzymasz odpowiednie pięć liczb. Mam nadzieję , że wydrukuje0
wszystko inne (mogą to być błędy lub nic, nie wiem). Jeśli ktoś chce poprawić kod lub pograć w golfa, nie wahaj się pomóc!Zadzwoń z:
źródło
Rubin - 130
Na podstawie rejestru przesunięcia liniowego sprzężenia zwrotnego. Dane wejściowe według argumentów wiersza poleceń.
Powinien być unikalny w oparciu o charakter LFSR. Wskazówka: rosnąco i wszystkie pozytywne.
Daje więcej wskazówek, jeśli nikt nie rozwiąże go wkrótce.
źródło
Ruby, 249
Powinno być zabawnie. Kto potrzebuje matematyki?
źródło
309, 77347, 154385, 231423, 308461
ale nie sądzę, żeby to było wyjątkowe.103, 232041, 463979, 695917, 927855
i3, 7966741, 15933479, 23900217, 31866955
. I jestem prawie pewien, że istnieją inne poprawne wyrażenia regularne przy użyciu dodatkowych+
s.()
lub w podobny sposób.CJam, 49 znaków
Wypróbuj online.
Jak to działa
Wynik będzie wynosił 1 wtedy i tylko wtedy, gdy druga liczba całkowita jest czynnikiem pierwszego, który jest iloczynem dwóch liczb pierwszych: jednej odpowiadającej tajnej sekwencji i drugiej, która nie odpowiada żadnej prawidłowej sekwencji. Dlatego rozwiązanie jest wyjątkowe.
Factorizing 512 bitową liczbę całkowitą nie jest to trudne, ale mam nadzieję, że nikt nie będzie w stanie w ciągu 72 godzin. Moja poprzednia wersja z 320-bitową liczbą całkowitą została zepsuta .
Przykładowy przebieg
źródło
JavaScript 958
Konwertuje dane wejściowe na wiele typów danych i wykonuje pewne manipulacje odpowiednie dla każdego typu danych po drodze. Powinien być dość łatwo odwrócony dla każdego, kto potrzebuje czasu.
źródło
320689, 444121, 567553, 690985, 814417
C, 239 (Cracked by Dennis)
Przejdź tutaj, aby uzyskać zaktualizowane zgłoszenie.
Prawdopodobnie można by grać w golfa nieco dokładniej. Trzeba przyznać, że nie poświęciłem czasu, aby udowodnić, że klucz jest unikalny (prawdopodobnie nie jest), ale zdecydowanie jest to zgodne z kolizją skrótu. Jeśli go złamiesz, udostępnij swoją metodę :)
źródło
0 0 0 0 0
?C, 212 autorstwa Orby - Cracked
https://codegolf.stackexchange.com/a/36810/31064 firmy Orby ma co najmniej dwa klucze:
Orby poprosił o metodę, której użyłem do jej złamania. Funkcja p sprawdza, czy x jest liczbą pierwszą, sprawdzając
x%i==0
wszystkie i między 2 a x (chociaż używa(x/i)*i==x
zamiastx%i==0
) i zwraca true, jeśli x jest liczbą pierwszą. Funkcja f sprawdza, czy wszystkie a, b, c, d i e są liczbą pierwszą. Sprawdza również, czy liczba m, konkatenacja dziesiętnych reprezentacji e, d, c, b oraz a (w tej kolejności), jest liczbą pierwszą. Klucz jest taki, że a, b, c, d, e im są wszystkie pierwsze.Green i Tao (2004) pokazują, że istnieje nieskończenie wiele ciągów arytmetycznych liczb pierwszych dla dowolnej długości k, więc musimy po prostu szukać tych sekwencji, które również spełniają m, że są pierwsze. Biorąc pod uwagę długi czas, ponieważ jest on ograniczony przez -9,223372037e + 18 i 9.223372037e + 18, wiemy, że aby skonkatenowany łańcuch pasował do długiej długości, liczby mają górną granicę 9999. Tak więc używając skryptu pythonowego do wygenerowania wszystkich sekwencje arytmetyczne we wszystkich liczbach pierwszych <10000, a następnie sprawdzając, czy ich odwrotna konkatenacja jest liczbą pierwszą, możemy znaleźć wiele możliwych rozwiązań.
Z jakiegoś powodu wymyśliłem fałszywe wyniki pozytywne, ale dwa powyższe są zgodne z programem. Ponadto mogą istnieć rozwiązania, w których e jest ujemne, a reszta jest dodatnia (p używa modułu x), ale ich nie szukałem.
Wszystkie klucze, które podałem, są ciągami arytmetycznymi, ale skrypt Orby'ego nie wymaga, aby dane wejściowe były ciągami arytmetycznymi, więc mogą być też nieprawidłowe klucze.
źródło
MATLAB: Najwyraźniej nieważny
Bardzo proste, wystarczy wygenerować odpowiednią liczbę losową.
Nadal może występować błąd, ale nie powinno to stanowić problemu.
źródło
MATLAB (z Symbolicznym zestawem narzędzi), 173 znaków
To nie jest oficjalny wpis i nie będzie się liczył do nikogo, ale zdobędziesz szalone prawa do przechwalania się. ;)
Symboliczny zestaw narzędzi jest wymagany tylko do obsługi odejmowania dużych liczb całkowitych.
Brutalne zmuszanie do tego powinno być psem, ale jeśli znasz tę serię, rozwiązanie jest trywialne.
źródło
Python 2 (91)Edycja: jest to niedozwolone, ponieważ argument za wyjątkowością jest probabilistyczny. Poddaję się.
Pobiera na wejściu listy liczb całkowitych, np
[1,2,3,4,5]
.Pętla ma działać w sposób denerwujący na wejściach, pozostawiając wieżę sum i wykładników. Pomysł jest jak dyskretny log, ale z nieporządną komplikacją zamiast matematycznej prostoty. Być może złożoność modułu jest podatna na atak, w którym to przypadku mogłabym to zrobić
7**58+8
.Naprawdę nie wiem, jak udowodnię, że mój klucz jest jedyny, ale zakres wyjść jest co najmniej 10 razy większy niż zakres wejść, więc prawdopodobnie? Chociaż może tylko niewielka część potencjalnych wyników jest osiągalna. Zawsze mogłem zwiększyć liczbę cyfr kosztem znaków. Sam zdecyduję, co jest sprawiedliwe.
Miłego łamania!
źródło
Mathematica - 72
Wersja 2 mojego skryptu, z takim samym kluczem jak ten przeznaczony dla mojej wersji 1.
To w zasadzie usuwa ujemne liczby pierwsze dla
NextPrime
.Bieganie:
źródło
9244115
, delta25
.1073743739, 1073886396, 1074029053, 1074171710, 1074314367
Python, 86 znaków
Wpisz liczby jak
1,2,3,4,5
.źródło
1,0,1,63021563418517255630720,0
.19960211, 31167202, 42374193, 53581184, 64788175
63021563418517255630720
nie jest liczbą 32-bitową.Python, 78
(Pęknięty przez Tyilo w 14 minut)
Zabawa!
Okej, tutaj nie wyświetla się poprawnie :(
Oczekuje listy pięciu liczb, np. [1,2,3,4,5]
źródło
[-481890276, -594823292, -728999970, -887503650, -1073741792]
CJam, 37 znaków (zepsuty)
Wypróbuj online.
Jak to działa
Zobacz moją nową odpowiedź.
Przykładowy przebieg
źródło
737262825 208413108 3974530688 3445680972 2916831257
działa, ale nie jest postępem arytmetycznym. Zrealizowane w 3 godziny 20 minut. Liczby 512-bitowe były najwyraźniej wykonalne w ciągu 72 godzin za 75 USD na EC2 dwa lata temu, więc myślę, że byłoby to bezpieczne.737262825 208413109 -320436607 -849286323 -1378136039
C, 212 (pęknięty)
Jest to ten sam pomysł, co moje poprzednie zgłoszenie , bardziej szczegółowo grał w golfa, z poprawionym błędem, który przeszedł 0,0,0,0,0 (Podziękowania dla Dennisa za wskazanie błędu). Skompiluj z -std = c99.
źródło
-7 -37 -67 -97 -127
,-157 -127 -97 -67 -37