Ten konkurs się zakończył.
Ze względu na charakter wyzwań dla gliniarzy i rabusiów wyzwanie dla gliniarzy staje się znacznie łatwiejsze, gdy zainteresowanie związanym z nim wyzwaniem spadnie. Dlatego, mimo że nadal możesz publikować funkcje skrótu, twoja odpowiedź nie zostanie zaakceptowana ani nie będzie częścią tabeli wyników.
To wyzwanie jest poszukiwanie najkrótszej realizacji funkcji skrótu , która jest odporna na zderzenia , czyli powinno być niemożliwe do znalezienia dwóch różnych wiadomości z tego samego skrótu.
Jako policjant próbujesz wymyślić i wdrożyć funkcję skrótu, znajdując najlepszy kompromis między rozmiarem kodu a odpornością na kolizje. Użyj zbyt wielu bajtów, a inny policjant cię obezwładni!
Jako złodziej próbujesz udaremnić próby gliniarzy, łamiąc ich funkcje, udowadniając, że nie są one odpowiednie. Zmusi ich to do użycia większej liczby bajtów w celu wzmocnienia algorytmów!
Wyzwanie gliniarzy
Zadanie
Zaimplementuj kryptograficzną funkcję skrótu H: I -> O twojego wyboru, gdzie I jest zbiorem wszystkich nieujemnych liczb całkowitych poniżej 2 2 30, a O jest zbiorem wszystkich nieujemnych liczb całkowitych poniżej 2 128 .
Możesz albo wdrożyć H. jako rzeczywistą funkcję, która przyjmuje i zwraca pojedynczą liczbę całkowitą, ciąg znaków reprezentujący liczbę całkowitą lub tablicę liczb całkowitych lub pełny program, który odczytuje STDIN i drukuje do STDOUT w bazie 10 lub 16.
Punktacja
H , że musi oprzeć się wyzwaniu złodziei zdefiniowanemu poniżej.
Jeśli złodziej pokona twoje zgłoszenie w ciągu pierwszych 168 godzin po opublikowaniu, uznaje się je za pęknięte .
Implementacja H powinna być jak najkrótsza. Najkrótsze niezłapane zgłoszenie będzie zwycięzcą wyzwania gliniarzy.
Dodatkowe zasady
Jeśli implementujesz H jako funkcję, podaj opakowanie, aby wykonać funkcję z poziomu programu, który zachowuje się jak wyjaśniono powyżej.
Podaj co najmniej trzy wektory testowe dla swojego programu lub opakowania (przykładowe dane wejściowe i odpowiadające im dane wyjściowe).
H. może być twoim nowym projektem (preferowanym) lub znanym algorytmem, o ile sam go zaimplementujesz. Zabrania się korzystania z jakichkolwiek wbudowanych funkcji skrótu, funkcji kompresji, szyfru, PRNG itp.
Wszelkie wbudowane powszechnie używane do implementacji funkcji skrótu (np. Konwersja bazy) to uczciwa gra.
Wynik działania programu lub funkcji musi być deterministyczny.
Powinien istnieć darmowy (jak w przypadku piwa) kompilator / interpreter, który można uruchomić na platformie x86 lub x64 lub z poziomu przeglądarki internetowej.
Twój program lub funkcja powinna być dość wydajna i musi mieszać każdą wiadomość w I poniżej 2 2 19 w mniej niż sekundę.
W przypadkach krawędziowych decydujący będzie czas (ścienny) na moim komputerze (Intel Core i7-3770, 16 GiB pamięci RAM).
Biorąc pod uwagę naturę tego wyzwania, zabronione jest zmienianie kodu odpowiedzi w jakikolwiek sposób, niezależnie od tego, czy zmienia on wynik, czy nie.
Jeśli Twoje zgłoszenie zostało złamane (lub nawet jeśli nie zostało), możesz opublikować dodatkową odpowiedź.
Jeśli twoja odpowiedź jest nieprawidłowa (np. Nie jest zgodna ze specyfikacją I / O), usuń ją.
Przykład
Python 2.7, 22 bajty
def H(M): return M%17
Obwoluta
print H(int(input()))
Wyzwanie rabusiów
Zadanie
Złam dowolne oświadczenie gliniarzy, zamieszczając w wątku rabusiów : dwie wiadomości M i N w I takie, że H (M) = H (N) i M ≠ N .
Punktacja
Złamanie każdego zgłoszenia gliny daje ci jeden punkt. Złodziej z największą liczbą punktów wygrywa.
W przypadku remisu wygrywa ten związany bandyta, który złamał najdłuższe poddanie.
Dodatkowe zasady
Każde zgłoszenie policjanta może zostać złamane tylko raz.
Jeśli przesłanie policjanta opiera się na zachowaniu zdefiniowanym lub niezdefiniowanym, musisz jedynie znaleźć pęknięcie, które działa (weryfikowalnie) na twoim komputerze.
Każde pęknięcie należy do osobnej odpowiedzi w wątku złodziei.
Opublikowanie nieważnej próby złamania uniemożliwi zablokowanie tego konkretnego zgłoszenia przez 30 minut.
Nie możesz złamać własnego zgłoszenia.
Przykład
Python 2.7, 22 bajty według użytkownika8675309
1
i
18
Tabela liderów
Bezpieczne zgłoszenia
Nieprzetworzone zgłoszenia
Możesz użyć tego fragmentu stosu, aby uzyskać listę jeszcze nie spękanych odpowiedzi.
function g(p){$.getJSON('//api.stackexchange.com/2.2/questions/51068/answers?page='+p+'&pagesize=100&order=desc&sort=creation&site=codegolf&filter=!.Fjs-H6J36w0DtV5A_ZMzR7bRqt1e',function(s){s.items.map(function(a){var h=$('<div/>').html(a.body).children().first().text();if(!/cracked/i.test(h)&&(typeof a.comments=='undefined'||a.comments.filter(function(b){var c=$('<div/>').html(b.body);return /^cracked/i.test(c.text())||c.find('a').filter(function(){return /cracked/i.test($(this).text())}).length>0}).length==0)){var m=/^\s*((?:[^,(\s]|\s+[^-,(\s])+)\s*(?:[,(]|\s-).*?([0-9]+)/.exec(h);$('<tr/>').append($('<td/>').append($('<a/>').text(m?m[1]:h).attr('href',a.link)),$('<td class="score"/>').text(m?m[2]:'?'),$('<td/>').append($('<a/>').text(a.owner.display_name).attr('href',a.owner.link))).appendTo('#listcontent');}});if(s.length==100)g(p+1);});}g(1);
table th, table td {padding: 5px} th {text-align: left} .score {text-align: right} table a {display:block}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><table><tr><th>Language</th><th class="score">Length</th><th>User</th></tr><tbody id="listcontent"></tbody></table>
Odpowiedzi:
CJam, 21 bajtów
Pobiera ciąg bajtów jako dane wejściowe.
W pseudokodzie:
Przykładowe skróty:
„” (pusty ciąg) -> 1
„Test” -> 2607833638733409808360080023081587841
„test” -> 363640467424586895504738713637444713
Może to być trochę proste, zakres wyjściowy jest tylko nieco większy niż 122 bity, potrójne wzmocnienie iteracji jest już nieco zepsute, ponieważ robi dokładnie to samo za każdym razem, więc wprowadź hash do 1 w pierwszym iteracja będzie pełną przerwą. Ale jest krótki i nie jest fajnie być zbyt bezpiecznym.
źródło
Pyton, 109 bajty [ krakingu , i ponownie ]
Próbowałem wdrożyć Jenkinsa pojedynczo funkcję jaka jest, z tą różnicą, że była to liczba początkowa i liczba bitów.
Ciekawostka: najwyraźniej Perl w pewnym momencie użył skrótu Jenkinsa .
Obwoluta
Przykłady
źródło
C ++, 148 bajtów
__uint128_t jest rozszerzeniem GCC i działa zgodnie z oczekiwaniami. Hash opiera się na iteracji hash FNV (chociaż pożyczyłem ich prime
a
liczbę pierwszą są to pierwsze cyfry Pi w heksie) z rotacją podobną do sha1 na początku każdej iteracji. Kompilowanie z-O3
haszowaniem pliku 10 MB zajmuje mniej niż 2 sekundy, więc wciąż jest margines na zwiększenie iteracji w wewnętrznej pętli - ale dzisiaj czuję się hojny.Odblokowane (zmienione nazwy zmiennych, dodane komentarze, białe znaki i para nawiasów klamrowych) dla Twojej przyjemności z łamania:
Sugestie dotyczące gry w golfa są mile widziane (nawet jeśli nie uda mi się poprawić kodu na ich podstawie).
edytuj: poprawiono literówki w nieblakowanym kodzie (wersja w golfa pozostaje niezmieniona).
źródło
o
wydaje się niezainicjowany. Gdzieoutput
jest zadeklarowany? A możeo
jestoutput
?n
. Czy rzeczywiście sprawdziłeś kod „nienablowany”, aby go uruchomić?U i=81;i-=3
mogłoby być jeszcze bardziej podłe, bez znacznych kosztów w czasie wykonywania.CJam, 44 bajty [ pęknięty ]
Dane wejściowe są w bazie 10.
CJam jest wolny. Mam nadzieję, że uruchomi się w ciągu 1 sekundy na jakimś komputerze ...
Objaśnienia
Cóż, dwuwymiarowe rzeczy wydawały się słabością ... Miał na celu przyspieszenie niektórych powolnych obliczeń na początku. Ale nie może uruchomić się w sekundę bez względu na to, co robię, więc w końcu usunąłem wolny kod.
Powinno być również lepiej, jeśli użyłem bitów binarnych i wyższych zasad.
Wersja C.
źródło
C ++, 182 znaków (+ około 51 znaków na płycie grzewczej)
Płyta grzewcza:
Program uruchamiany z funkcją gry w golfa
źródło
__uint128_t
dopiero po wdrożeniu tego.Pyth, 8 Cracked
Wypróbuj online
Trochę głupia odpowiedź, wyjaśnię, jak to działa, ponieważ większość ludzi nie umie czytać w Pyth. Pobiera logarytm naturalny z jednego plus danych wejściowych, a następnie konwertuje go na ciąg. Ten ciąg znaków jest odwracany, a następnie analizowany, a następnie konwertowany na liczbę całkowitą.
Tłumaczenie python wyglądałoby następująco:
źródło
Python 3, 216 bajtów [ pęknięty ]
Ze względu na niezgodność ze specyfikacją mogę wymyślić przynajmniej jedną drobną lukę, ale poza tym uważam, że jest to dowód przynajmniej na brutalną siłę. Sprawdziłem między innymi pierwsze 10 milionów skrótów.
Pod względem golfa byłoby to krótsze w Pythonie 2, ale poświęciłem kilka bajtów na wydajność (ponieważ prawdopodobnie i tak nie wygra).
Edycja: To była moja próba zaimplementowania Very Smooth Hash , ale niestety 128 bitów było zdecydowanie za małe.
Obwoluta
Przykłady
Wyjaśnienie kodu
Przykład wypełnienia dla
f(6)
:źródło
C, 87 bajtów [ pęknięty ]
To jest kompletny program; nie wymaga opakowania. Akceptuje dane binarne przez stdin i wysyła szesnastkowy skrót do standardowego wejścia.
Oblicza to tylko 64-bitowy skrót, więc biorę tutaj trochę ryzyka.
Jeśli ktoś się zastanawia, dwie stałe
'foo+'
i'bar/'
są liczbami pierwszymi 1718578987 i 1650553391.Przykłady:
Ignoruje wiodące zera:
Dane wejściowe jednobajtowe:
Dane wejściowe wielobajtowe:
źródło
foo|
(d5c9bef71d4f5d1b) ifoo\
(d5c9bef71d4f5d1b) wytwarzają BARDZO podobne skróty.\x00
i\x00\x00
!J - 39 bajtów - pęknięty
Funkcja przyjmuje ciąg znaków jako dane wejściowe i zwraca liczbę całkowitą <2 128 . Zakładam, że musimy nazwać naszą funkcję, aby była poprawna, więc usuń kolejne 3 znaki z liczby, jeśli możemy przesłać anonimowe funkcje.
Dla tych z was, którzy nie czytają hieroglifów, oto podsumowanie tego, co robię.
a=.(2^128x)&|@^/@
Jest to podprogram *, który pobiera tablicę liczb, a następnie traktuje go jako wieżę mocy, w której potęguje się mod 2 128 . Przez „wieżę mocy” mam na myśli, że jeśli podasz dane wejściowe3 4 5 6
, to się obliczy3 ^ (4 ^ (5 ^ 6))
.(".p:@+5,9:)a
Ta funkcja pobiera ciąg znaków, konwertuje go na liczbę N , a następnie oblicza ( n +5) -te i ( n +9) -te liczby pierwsze, a następnie wyrzucaa
na nią przed nim. To znaczy, znajdujemyp(n+5) ^ p(n+9)
mod 2 128, gdziep(k)
jestk
-ta liczba pierwsza.H=:_8...\(a...)]
Wykonaj powyższą funkcję na 8-znakowych podblokach wejścia, a następniea
wszystkie wyniki razem i wywołaj wynikową funkcję skrótuH
. Używam 8 znaków, ponieważk
funkcja „ -ta liczba pierwsza” J kończy się niepowodzeniem, gdyp(k)
> 2 31 , tj.k=105097564
Jest największym sejfemk
.Mam kilka przykładowych wyników. Możesz spróbować tego samemu online na tryj.tk , ale naprawdę polecam robienie tego w domu, pobierając interpreter z Jsoftware .
* Technicznie rzecz biorąc, nie jest to funkcja sama w sobie, przywiązuje się do innych funkcji i działa na ich wynik. Jest to jednak kwestia semantyczna J, a nie różnica konceptualna: przebieg programu jest taki, jak to opisałem powyżej.
źródło
Python 3, 118 bajtów [ pęknięty ]
Wcięcie to pojedyncza karta. Prosty skrót, jeszcze nie przetestowałem go dokładnie.
Zadzwoń w następujący sposób:
wynik:
73117705077050518159191803746489514685
źródło
ord(c)
tak naprawdę, każdy ciąg znaków zrobi :) (oprócz rzeczy takich jak nul chars, myślę, że dzięki temu kolizje skrótów są naprawdę łatwe. Więc trzymaj się łańcucha 0-9.)C ++, 239 bajtów
Mój pierwszy golf golfowy! [ Proszę, bądź delikatny ]
Wersja bez golfa:
Nie najlepszy skrót, a na pewno nie najkrótszy istniejący kod. Akceptowanie wskazówek golfowych i liczenie na poprawę!
Obwoluta
Prawdopodobnie nie najlepszy na świecie, ale mimo wszystko
źródło
printf '33333333\x40\xF3\x32\xD6\x56\x91\xCA\x66' | ./hash7_
->a4baea17243177fd
;printf '33333333\x77\x39\xF3\x82\x93\xDE\xA7\x2F' | ./hash7_
->a4baea17243177fd
. Bruteforcer znajduje tutaj kolizje znacznie szybciej niż w innym 64-bitowym haszu tutaj.Java,
299291282 bajtów, pęknięty.Wykonuje niektóre operacje na BigIntegers, a następnie przyjmuje wynik modulo 2 128 .
źródło
public
yourself, saving 7 chars?C, 128 bytes [cracked]
This is more or less the same algorithm as my last effort (cracked by Vi.), but now has enough hamster wheels to generate proper 128-bit hashes.
The four prime constants in the code are as follows:
As before, this is a complete program with no need for a wrapper. The integer I is input via stdin as raw binary data (big-endian), and the hash O is printed in hex to stdout. Leading zeroes in I are ignored.
Examples:
źródło
C, 122 bytes [cracked]
Nested loops, half-assed LCGs, and variable swapping. What's not to love?
Here's a ungolf'd version to play around with:
This is a fully self-contains program that reads from STDIN and prints to STDOUT.
Example:
In some simple benchmarks, it hashes around 3MB/s of text data. The hash speed depends on the input data itself, so that should probably be taken into consideration.
źródło
PHP 4.1, 66 bytes [cracked]
I'm just warming up.
I hope you find this insteresting.
I've tried it numbers as large as 999999999999999999999999999.
The output seemed to be within the 2128 range.
PHP 4.1 is required because of the
register_globals
directive.It works by automatically creating local variables from the session, POST, GET, REQUEST and cookies.
It uses the key
a
. (E.G.: access overhttp://localhost/file.php?a=<number>
).If you want to test it with PHP 4.2 and newer, try this:
This version only works with POST and GET.
Example output:
(I assure you that there are numbers that produce the same hash).
źródło
C, 134 bytes, Cracked
This is complete C program.
What it does: The idea is to take input as byte array and append pseudo random (but deterministic) bytes at the end to make the length equal to about 2230 (a bit more). The implementation reads input byte by byte and starts using pseudo random data when it finds the first character that isn't a digit.
As builtin PRNG isn't allowed I implemented it myself.
There is undefined/implementation defined behavior that makes the code shorter (the final value should be unsigned, and I should use different types for different values). And I couldn't use 128 bit values in C. Less obfuscated version:
źródło
Python 2.X - 139 bytes [[Cracked]]
This is quite similar to all the other (LOOP,XOR,SHIFT,ADD) hashes out here. Come get your points robbers ;) I'll make a harder one after this one is solved.
Wrapper (expects one argument in base-16 also known as hexadecimal):
źródło
H(2**(2**10))
took around 8 or 9 seconds, whileH(2**(2**12))
took around 29 seconds andH(2**(2**14))
took over two minutes.Python 2.7 - 161 bytes [[Cracked]]
Well since I managed to change my first hash function into an useless version before posting it, I think I will post another version of a similar structure. This time I tested it against trivial collisions and I tested most of the possible input magnitudes for speed.
Wrapper (not counted in the bytecount)
Run example (input is always a hexadecimal number):
źródło
Ruby, 90 Bytes
A highly random hash algorithm I made up without looking at any real hashes...no idea if it is good. it takes a string as input.
Wrapper:
źródło
comparison of String with 255 failed (ArgumentError)
.gets.to_i
in the wrapper.Mathematica, 89 bytes, cracked
Not the shortest.
źródło
PHP, 79 Bytes (cracked. With a comment):
This does alot of scary things via type-conversions in php, which makes it hard to predict ;) (or at least I hope so). It's not the shortest or most unreadable answer, however.
To run it you can use PHP4 and register globals (with ?i=123) or use the commandline:
źródło
C# - 393 bytes cracked
Ungolfed:
I have never touched cryptography or hashing in my life, so be gentle :)
It's a simple implementation of an FNV-1a hash with some array pivoting on the input. I am sure there is a better way of doing this but this is the best I could do.
It might use a bit of memory on long inputs.
źródło
Python 2, 115 bytes [Cracked already!]
OK, here's my last effort. Only 115 bytes because the final newline isn't required.
This is a complete program that inputs a decimal integer on stdin and prints a decimal hash value on stdout. Extra leading zeroes will result in different hash values, so I'll just assume that the input doesn't have any.
This works by stuffing 197-digit chunks of the input number through a modular exponentiation. Unlike some languages, the
int()
function always defaults to base 10, soint('077')
is 77, not 63.Sample outputs:
źródło