Этот конкурс окончен.
Из-за характера проблем полицейских и грабителей, задача полицейских становится намного легче, когда интерес к связанной проблеме грабителей уменьшился. Поэтому, хотя вы все еще можете публиковать хэш-функции, ваш ответ не будет принят или станет частью списка лидеров.
Эта задача заключается в поиске самой короткой реализации хеш-функции, которая устойчива к коллизиям , т. Е. Должно быть невозможно найти два разных сообщения с одинаковым хеш-кодом.
Как полицейский, вы пытаетесь изобрести и реализовать хеш-функцию, находя лучший компромисс между размером кода и устойчивостью к коллизиям. Используйте слишком много байтов, и другой полицейский обгонит вас!
Как грабитель, вы пытаетесь помешать попыткам полицейских, взломав их функции, доказав, что они непригодны. Это заставит их использовать больше байтов для усиления своих алгоритмов!
Вызов копов
задача
Реализуйте криптографическую хеш-функцию H: I -> O по вашему выбору, где I - множество всех неотрицательных целых чисел ниже 2 2 30, а O - множество всех неотрицательных целых чисел ниже 2 128 .
Вы можете реализовать H как фактическую функцию, которая принимает и возвращает одно целое число, строковое представление целого числа или массив целых чисел или полную программу, которая читает из STDIN и печатает в STDOUT в основаниях 10 или 16.
счет
H что он должен противостоять вызову грабителей, определенному ниже.
Если грабитель побеждает ваше представление в первые 168 часов после публикации, оно считается взломанным .
Реализация H должна быть максимально короткой. Самая короткая непроверенная подача будет победителем соревнования полицейских.
Дополнительные правила
Если вы реализуете H как функцию, пожалуйста, предоставьте оболочку для выполнения функции из программы, которая ведет себя так, как описано выше.
Пожалуйста, предоставьте не менее трех тестовых векторов для вашей программы или оболочки (например, входные данные и их соответствующие выходные данные).
H может быть вашим новым дизайном (предпочтительным) или известным алгоритмом, если вы реализуете его самостоятельно. Запрещается использовать любые встроенные хэш-функции, функции сжатия, шифрования, PRNG и т. Д.
Любая встроенная функция, обычно используемая для реализации функций хеширования (например, базовое преобразование), является честной игрой.
Вывод вашей программы или функции должен быть детерминированным.
Должен быть бесплатный (как в пиве) компилятор / интерпретатор, который можно запустить на платформе x86 или x64 или из веб-браузера.
Ваша программа или функция должна быть достаточно эффективной и должна хэшировать любое сообщение в I ниже 2 2 19 менее чем за секунду.
Для крайних случаев решающее значение будет иметь (настенное) время, необходимое на моем компьютере (Intel Core i7-3770, 16 ГБ ОЗУ).
Учитывая природу этой проблемы, запрещено каким-либо образом изменять код вашего ответа, независимо от того, изменяет ли он вывод или нет.
Если ваша заявка была взломана (или даже нет), вы можете опубликовать дополнительный ответ.
Если ваш ответ неверен (например, он не соответствует спецификации ввода / вывода), удалите его.
пример
Python 2.7, 22 байта
def H(M): return M%17
обертка
print H(int(input()))
Вызов грабителей
задача
Трещина любой из полицейских Доводы, разместив следующее в грабителей нити : два сообщения M и N в I таким образом, что H (M) = H (N) и M ≠ N .
счет
Взлом каждого подчиненного полицейского приносит вам одно очко. Грабитель с наибольшим количеством очков побеждает.
В случае ничьей побеждает грабитель, взломавший самую длинную отправку.
Дополнительные правила
Каждое подчинение полицейского может быть взломано только один раз.
Если представление полицейского основано на поведении, определяемом реализацией или неопределенном, вам нужно только найти трещину, которая работает (достоверно) на вашем компьютере.
Каждая трещина принадлежит отдельному ответу в ветке грабителей.
Публикация недопустимой попытки взлома запрещает взломать эту конкретную отправку в течение 30 минут.
Вы не можете взломать ваше собственное представление.
пример
Python 2.7, 22 байта пользователем8675309
1
а также
18
Leaderboard
Безопасные представления
Не взломанные представления
Вы можете использовать этот фрагмент стека, чтобы получить список еще не взломанных ответов.
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>
Ответы:
CJam, 21 байт
Принимает строку байтов в качестве входных данных.
В псевдокоде:
Пример хэшей:
"" (пустая строка) -> 1
"Тест" -> 2607833638733409808360080023081587841
"Тест" -> 363640467424586895504738713637444713
Это может быть немного проще, выходной диапазон составляет всего чуть более 122 бит, усиление тройной итерации уже немного нарушено, так как каждый раз он делает одно и то же, так что ввод в первом хэше 1 итерация будет полным перерывом. Но это коротко, и не слишком весело быть слишком безопасным.
источник
Python, 109 байт [ треснул , и снова ]
Я попытался реализовать единовременную функцию Дженкинса как есть, с единственной разницей, состоящей из начального числа и количества битов.
Забавный факт: очевидно, Perl в какой-то момент использовал хеш Дженкинса .
обертка
Примеры
источник
C ++, 148 байт
__uint128_t является расширением GCC и работает как положено. Хеш основан на итерации хеша FNV (я позаимствовал их простое число, хотя
a
это первые цифры числа Pi в шестнадцатеричном формате) с поворотом, подобным sha1, в начале каждой итерации. Компиляция с использованием-O3
хэширования файла размером 10 МБ занимает менее 2 секунд, поэтому все еще есть запас для увеличения числа итераций во внутреннем цикле, но сегодня я чувствую себя щедрым.Отключите (изменили имена переменных, добавили комментарии, пробелы и пару скобок) для вашего удовольствия от взлома:
Предложения по игре в гольф приветствуются (даже если я не смогу улучшить код на их основе).
редактировать: исправлены опечатки в деуглифицированном коде (версия для гольфа остается неизменной).
источник
o
кажется неинициализированным. Гдеoutput
заявлено? Или , может быть ,o
этоoutput
?n
. Вы действительно проверили «деуглифицированный» код для запуска?U i=81;i-=3
мог бы быть еще более мерзким, без значительных затрат времени выполнения.CJam, 44 байт [ трещина ]
Вход в базу 10.
CJam медленный. Я надеюсь, что это работает в 1 секунду на каком-то компьютере ...
Пояснения
Что ж, двумерные вещи казались слабостью ... Вначале предполагалось ускорить некоторые медленные вычисления. Но он не может работать за секунду, независимо от того, что я делаю, поэтому я наконец удалил медленный код.
Также должно быть лучше, если бы я использовал двоичные биты и старшие основания.
C версия
источник
C ++, 182 символа (+ около 51 символа стандартного образца)
Шаблонный:
Запускаемая программа с функцией гольфа
источник
__uint128_t
только после реализации этого.Pyth, 8 трещины
Попробуйте онлайн
Немного глупый ответ, я объясню, как это работает, потому что большинство людей не умеют читать Pyth. Это берет натуральный логарифм одного плюс вход, и затем преобразовывает это в строку. Эта строка переворачивается, а затем оценивается и затем преобразуется в целое число.
Перевод Python будет выглядеть так:
источник
Python 3, 216 байт [ взломан ]
Из-за несовместимости со спецификацией я могу вспомнить хотя бы одну небольшую уязвимость, но кроме этого я думаю, что это как минимум доказательство грубой силы. Я проверил первые 10 миллионов хэшей, между прочим.
С точки зрения гольфа это было бы короче в Python 2, но я пожертвовал некоторыми байтами ради эффективности (так как в любом случае это, вероятно, не победит).
Редактировать: это была моя попытка реализовать Very Smooth Hash , но, к сожалению, 128-бит был слишком мал.
обертка
Примеры
Объяснение кода
Пример заполнения для
f(6)
:источник
C, 87 байт [ взломано ]
Это полная программа; Обертка не требуется. Принимает двоичный ввод через стандартный ввод и выводит шестнадцатеричный хеш в стандартный вывод.
Это только вычисляет 64-битный хеш, поэтому я немного рискну здесь.
В случае, если кому-то интересно, две константы
'foo+'
и'bar/'
являются простыми числами 1718578987 и 1650553391.Примеры:
Игнорирует ведущие нули:
Однобайтовые входы:
Многобайтовые входы:
источник
foo|
(d5c9bef71d4f5d1b) иfoo\
(d5c9bef71d4f5d1b) создают ОЧЕНЬ похожие хэши.\x00
и\x00\x00
!J - 39 байт - взломан
Функция, принимающая строку в качестве входных данных и возвращающая целое число <2 128 . Я предполагаю, что мы должны назвать нашу функцию допустимой, поэтому удалите еще 3 символа из числа, если мы можем представить анонимные функции.
Для тех из вас, кто не читает иероглифы, вот краткое изложение того, что я делаю.
a=.(2^128x)&|@^/@
Это подпрограмма *, которая принимает массив чисел, а затем обрабатывает его как энергетическую вышку, где возведение в степень берется в мод 2 128 . Под «башней власти» я имею в виду, что если вы дадите ей ввод3 4 5 6
, она рассчитает3 ^ (4 ^ (5 ^ 6))
.(".p:@+5,9:)a
Эта функция берет строку, преобразует ее в число N , а затем вычисляет ( n +5) -ое и ( n +9) -ое простое число, а затем выбрасывает вa
нее значение before. То есть мы находимp(n+5) ^ p(n+9)
мод 2 128, гдеp(k)
находитсяk
-ое простое число.H=:_8...\(a...)]
Выполните описанную выше функцию для 8-символьных субблоков ввода, а затем соберитеa
все результаты вместе и вызовите результирующую хеш-функциюH
. Я использую 8 символов, потому чтоk
функция " -th prime" J не работает, когдаp(k)
> 2 31 , т.е.k=105097564
это самый большой сейфk
.Есть некоторые примеры выходных данных. Вы можете попробовать это самостоятельно на сайте tryj.tk , но я действительно рекомендую делать это дома, загрузив переводчик с Jsoftware .
* Технически, это не функция сама по себе, она присоединяется к другим функциям и влияет на их вывод. Но это семантическая проблема J, а не концептуальное различие: поток программы такой, как я описал выше.
источник
Python 3, 118 байт [ взломан ]
Отступ - это одна вкладка. Простой хэш, еще не проверил его полностью.
Звоните следующим образом:
результат:
73117705077050518159191803746489514685
источник
ord(c)
, на самом деле, подойдет любая строка :) (кроме таких вещей, как nul chars, я думаю, что это делает коллизию хешей действительно легкой. Так что придерживайтесь строки 0-9.)C ++, 239 байт
Мой самый первый кодовый гольф! [ Пожалуйста, будьте нежны ]
Безголовая версия:
Не самый лучший хэш и определенно не самый короткий код из существующих. Принимать советы по гольфу и надеяться на улучшение!
обертка
Вероятно, не самый лучший в мире, но, тем не менее, обертка
источник
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 находит здесь коллизии гораздо быстрее, чем в других 64-битных хэшах.Java,
299291282 байта, взломан.Выполняет некоторые операции с BigIntegers, затем принимает результат по модулю 2 128 .
источник
public
самостоятельно, сохранив 7 символов?C, 128 байт [ взломано ]
Это более или менее тот же алгоритм, что и в моей последней попытке (взломанный Vi.) , Но теперь у него достаточно колес хомяка для генерации правильных 128-битных хэшей.
Четыре простых константы в коде следующие:
Как и прежде, это полная программа без необходимости в обертке. Целое число I вводится через stdin как необработанные двоичные данные (big-endian), а хэш O выводится в шестнадцатеричном виде в стандартный вывод. Ведущие нули в I игнорируются.
Примеры:
источник
C, 122 байта [ взломан ]
Вложенные циклы, недоделанные LCG и переменная замена. Что не любить?
Вот отличная версия для игры:
Это полностью автономная программа, которая читает из STDIN и печатает в STDOUT.
Пример:
В некоторых простых тестах он хэширует около 3 МБ / с текстовых данных. Скорость хеширования зависит от самих входных данных, так что это, вероятно, следует учитывать.
источник
PHP 4.1, 66 байт [ взломано ]
Я просто разогреваюсь.
Я надеюсь, вы найдете это интересным.
Я пробовал номера размером до 999999999999999999999999999.
Выходные данные оказались в диапазоне 2 128 .
PHP 4.1 требуется из-за
register_globals
директивы.Он работает путем автоматического создания локальных переменных из сеанса, POST, GET, REQUEST и файлов cookie.
Он использует ключ
a
. (Например, доступ болееhttp://localhost/file.php?a=<number>
).Если вы хотите протестировать его с PHP 4.2 и новее, попробуйте это:
Эта версия работает только с POST и GET.
Пример вывода:
(Уверяю вас, что есть числа, которые производят одинаковый хэш).
источник
C, 134 байта, треснувший
Это полная C программа.
Что он делает: Идея состоит в том, чтобы взять входные данные в виде массива байтов и добавить псевдослучайные (но детерминированные) байты в конце, чтобы сделать длину равной примерно 2 2 30 (немного больше). Реализация считывает входной байт за байтом и начинает использовать псевдослучайные данные, когда находит первый символ, который не является цифрой.
Поскольку встроенный PRNG не разрешен, я реализовал его сам.
Существует неопределенное / определяемое реализацией поведение, которое делает код короче (конечное значение должно быть без знака, и я должен использовать разные типы для разных значений). И я не мог использовать 128-битные значения в C. Менее запутанная версия:
источник
Python 2.X - 139 байт [[ Cracked ]]
Это очень похоже на все другие хеши (LOOP, XOR, SHIFT, ADD) здесь. Приди и получи свои очки грабителей;) Я сделаю сложнее, когда этот будет решен.
Оболочка (ожидает один аргумент в base-16, также известный как шестнадцатеричный):
источник
H(2**(2**10))
заняло около 8 или 9 секунд, в то время какH(2**(2**12))
заняло около 29 секунд иH(2**(2**14))
заняло более двух минут.Python 2,7 - 161 байт [[ Cracked ]]
Ну, так как мне удалось изменить свою первую хэш-функцию в бесполезную версию перед публикацией, я думаю, что я опубликую другую версию аналогичной структуры. На этот раз я проверил его на предмет тривиальных столкновений и проверил большинство возможных входных величин для скорости.
Оболочка (не учитывается в байтсчете)
Пример запуска (ввод всегда шестнадцатеричное число):
источник
Рубин, 90 байт
Весьма случайный алгоритм хеширования, который я составил, не глядя ни на какие настоящие хэши ... не знаю, хорош ли он. он принимает строку в качестве ввода.
Упаковочный:
источник
comparison of String with 255 failed (ArgumentError)
.gets.to_i
в обертке.Mathematica, 89 байт, трещины
Не самый короткий.
источник
PHP, 79 байт (взломано. С комментарием):
Это делает много страшных вещей посредством преобразования типов в php, что затрудняет предсказание;) (или, по крайней мере, я на это надеюсь). Однако это не самый короткий или нечитаемый ответ.
Для его запуска вы можете использовать PHP4 и зарегистрировать глобальные переменные (с? I = 123) или использовать командную строку:
источник
C # - 393 байта взломаны
Ungolfed:
Я никогда не касался криптографии или хэширования в своей жизни, так что будьте осторожны :)
Это простая реализация хеша FNV-1a с поворотом массива на входе. Я уверен, что есть лучший способ сделать это, но это лучшее, что я мог сделать.
Это может использовать немного памяти на длинных входах.
источник
Python 2, 115 байт [ уже взломано! ]
ОК, вот мои последние усилия. Всего 115 байтов, потому что последний перевод строки не требуется.
Это полная программа, которая вводит десятичное целое число в стандартный вывод и печатает десятичное значение хеша в стандартный вывод. Дополнительные начальные нули приведут к различным значениям хеш-функции, поэтому я просто предполагаю, что входные данные не имеют никаких.
Это работает путем заполнения 197-значных кусков входного числа посредством модульного возведения в степень. В отличие от некоторых языков, по
int()
умолчанию функция всегда имеет базовое значение 10,int('077')
равно как и 77, а не 63.Пример выходов:
источник