Соревнование
Простая задача «шпион против шпиона».
Напишите программу со следующими характеристиками:
- Программа может быть написана на любом языке, но не должна превышать 512 символов (как представлено в блоке кода на этом сайте).
- Программа должна принимать 5 знаковых 32-битных целых в качестве входных данных. Он может принимать форму функции, которая принимает 5 аргументов, функции, которая принимает один массив из 5 элементов, или полной программы, которая считывает 5 целых чисел из любого стандартного ввода.
- Программа должна вывести одно 32-разрядное целое число со знаком.
- Программа должна возвращать 1 в том и только в том случае, если пять входов, интерпретируемых как последовательность, соответствуют определенной арифметической последовательности по выбору программиста, называемой «ключом». Функция должна возвращать 0 для всех остальных входов.
Арифметическая последовательность обладает тем свойством, что каждый последующий элемент последовательности равен своему предшественнику плюс некоторая фиксированная константа a
.
Например, 25 30 35 40 45
является арифметической последовательностью, поскольку каждый элемент последовательности равен его предшественнику плюс 5. Аналогично, 17 10 3 -4 -11
это арифметическая последовательность, поскольку каждый элемент равен его предшественнику плюс -7.
Последовательности 1 2 4 8 16
и 3 9 15 6 12
не являются арифметическими последовательностями.
Ключом может быть любая арифметическая последовательность по вашему выбору, с единственным ограничением, что последовательности с целочисленным переполнением не допускаются. То есть последовательность должна строго увеличиваться, строго уменьшаться или иметь все элементы равными.
В качестве примера предположим, что вы выбрали ключ 98021 93880 89739 85598 81457
. Ваша программа должна вернуть 1, если входы (последовательно) соответствуют этим пяти числам, и 0 в противном случае.
Обратите внимание, что средства защиты ключа должны быть вашего собственного нового дизайна. Кроме того, вероятностные решения, которые могут возвращать ложные срабатывания с любой ненулевой вероятностью, не допускаются. В частности, пожалуйста, не используйте никаких стандартных криптографических хэшей, включая библиотечные функции для стандартных криптографических хэшей.
Скоринг
Самые короткие не взломанные представления на количество персонажей будут объявлены победителями.
Если есть путаница, пожалуйста, не стесняйтесь спрашивать или комментировать.
Встречный вызов
Всем читателям, включая тех, кто представил свои собственные программы, предлагается «взломать» материалы. Отправка взламывается, когда ее ключ публикуется в соответствующем разделе комментариев. Если представление сохраняется в течение 72 часов без изменения или взлома, оно считается «безопасным» и любой последующий успех в взломе будет проигнорирован ради контеста.
См. «Отказ от ответственности» ниже для получения подробной информации об обновленной политике оценки взлома.
Взломанные материалы исключаются из спора (при условии, что они не «безопасны»). Они не должны редактироваться. Если читатель хочет представить новую программу (ы), он должен сделать это в отдельном ответе.
Взломщики с наивысшим количеством баллов будут объявлены победителями вместе с разработчиками победивших программ.
Пожалуйста, не взламывайте ваши собственные представления.
Удачи. :)
Leaderboard
Предпоследний зачет (в ожидании безопасности представления Дениса CJam 49).
Безопасные шкафчики
- CJam 49, Деннис
- CJam 62, Денис Сейф
- CJam 91, сейф Денниса
- Питон 156, Maarten Baert сейф
- Perl 256, безопасный для чилимагов
- Java 468, Geobits безопасно
Неостановимые крекеры
- Питер Тейлор [Ruby 130, Java 342, Mathematica 146 *, Mathematica 72 *, CJam 37]
- Деннис [Pyth 13, Python 86 *, Lua 105 *, GolfScript 116, C 239 *]
- Мартин Бюттнер [Javascript 125, Python 128 *, Ruby 175 *, Ruby 249 *]
- Тийло [C 459, Javascript 958 *]
- Фреддиекнец [Mathematica 67 *]
- Илмари Каронен [Python27 182 *]
- закись азота [C 212 *]
* несоответствующая подача
Отказ от ответственности (Обновлено 23:15 EST, 26 августа)
Когда проблемы с оценками наконец достигли критической массы (учитывая, что две трети взломанных представлений пока не соответствуют), я оценил лучшие взломщики с точки зрения количества взломанных отправлений (основной) и общего количества символов в совместимых взломанных отправках. (вторичные).
Как и прежде, точные данные о взломе, длительность представлений и их статус соответствия / несоответствия помечены так, чтобы читатели могли сделать вывод о своих собственных рейтингах, если они считают, что новые официальные рейтинги несправедливы.
Приношу свои извинения за внесение изменений в правила в конце игры.
Ответы:
CJam, 62 символа
Stack Exchange склонен к обработке непечатаемых символов, но копирование кода из этой вставки и вставка его в интерпретатор CJam прекрасно работает для меня.
Как это работает
После замены строки Unicode строкой ASCII выполняется следующий код:
Этот подход использует Bivium-B (см. Алгебраический анализ тривиумоподобных шифров ), ослабленную версию потокового шифра Trivium .
Программа использует последовательность целых чисел в качестве начального состояния, обновляет состояние 434 раза (354 раунда достигают полной диффузии) и генерирует 177-битный результат, который сравнивается с таковым в правильной последовательности.
Поскольку размер состояния составляет ровно 177 бит, этого должно быть достаточно для однозначной идентификации исходного состояния.
Пример запуска
источник
CJam, 91 символов
Stack Exchange склонен к обработке непечатаемых символов, но копирование кода из этой вставки и вставка его в интерпретатор CJam прекрасно работает для меня.
Как это работает
После замены строки Unicode на целые числа (с учетом цифр символов из базовых 65533 чисел) выполняется следующий код:
Поскольку 13 является взаимно простым для модуля модуля (этот термин является секретным, поэтому вам просто нужно доверять мне), разные базы будут давать разные результаты, т. Е. Решение является уникальным.
Если кто-то не может использовать небольшой показатель степени (13), самый эффективный способ сломать эту блокировку - это факторизовать модуль (см. Проблему RSA ). Я выбрал 512-битное целое число для модуля, которое должно выдерживать 72 часа попыток факторизации.
Пример запуска
источник
found 1740001 rational and 1739328 algebraic entries
; с тех пор у него было почти 100 часов на их обработку и отчетыsieving in progress b = 46583, 0 complete / 0 batched relations (need 44970493)
.Python - 128
Давайте попробуем это:
(Ожидается, что пользователь введет 5 чисел, разделенных запятыми, например
1,2,3,4,5
.)источник
32416190039,32416190047,32416190055,32416190063,32416190071
Ява: 468
Вход дан как
k(int[5])
. Залог рано, если не равномерно. В противном случае, потребуется немного выяснить, правильны ли все десять хешей. Для больших чисел «немного» может означать десять секунд или больше, поэтому это может отговорить взломщиков.источник
Ява: 342
Вот строковый шкафчик, который зависит как от количества вводимых символов, так и от конкретного ввода. Последовательность может быть основана на неясных ссылках на поп-культуру. Повеселись!
Немного разгульный
источник
-8675309
дельта5551212
.Питон, 147
Изменить: более короткая версия на основе комментария Денниса. Я также обновил последовательность, чтобы избежать утечки информации.
Исходя из проблемы дискретного логарифма, которая считается непробиваемой, однако, простое число, которое я использую, вероятно, слишком мало, чтобы быть безопасным (и у него могут быть другие проблемы, я не знаю). И вы можете, конечно, перебор, поскольку единственными неизвестными являются два 32-разрядных целых числа.
источник
c=1
, вычисляяc=(c<<32)+d
и изменяя константу соответственно.Javascript 125
Этот должен быть взломан довольно быстро. Я сделаю что-то более сильное.
источник
0, 3913, 7826, 11739, 15652
Рубин, 175
В отличие от использования криптографического хэша или
srand
, это доказуемо уникально (что является небольшой подсказкой). Принимает пять чисел через STDIN, разделенные любым нецифровым, не символом новой строки или символами. Выходы в STDOUT.источник
622238809,1397646693,2173054577,2948462461,3723870345
(моя предыдущая догадка имела ошибку, но эта проверена). Я не думаю, что это действительно так, потому что последнее число не помещается в 32-разрядное целое число со знаком.GolfScript (116 символов)
Принимает ввод как разделенные пробелом целые числа.
источник
-51469355 -37912886 -24356417 -10799948 2756521
C 459 байт
Решено Tyilo - ЧИТАТЬ РЕДАКТИРОВАТЬ НИЖЕ
Нам нужен кто-то, чтобы написать решение C, не так ли? Я никого не впечатляю длиной, я не игрок в гольф. Надеюсь, это интересный вызов!
Я не думаю, что есть очевидный способ взломать этот, и я с нетерпением жду всех попыток! Я знаю, что это решение уникально. Очень минимальное запутывание, в основном для удовлетворения требований к длине. Это можно проверить просто:
PS Существует значение для
a[0]
числа как такового, и я хотел бы, чтобы кто-то указал на это в комментариях!РЕДАКТИРОВАТЬ:
Решение:
6174, 48216, 90258, 132300, 174342
Примечание о взломе:
Хотя этот метод не используется (см. Комментарии), мне удалось взломать мой собственный шифр с помощью очень простого брутфорса. Теперь я понимаю, что очень важно сделать цифры большими. Следующий код может взломать любой шифр, для
upper_bound
которого известна верхняя границаa[0] + a[1] + a[2] + a[3] + a[4]
. Верхняя граница в приведенном выше шифре457464
, которая может быть получена из системы уравненийb[]
и некоторой проработки алгоритма. Можно показать, чтоb[4] = a[0] + a[1] + a[2] + a[3] + a[4]
.С
a[0] = 6174
этим циклом моя работа прервалась чуть меньше минуты.источник
6174, 48216, 90258, 132300, 174342
.Mathematica
8067Бег:
Вероятно, довольно легко взломать, может также иметь несколько решений.
Обновление: улучшил игру в гольф, выполнив то, что предложил Мартин Бюттнер. Функциональность функции и клавиши не изменилась.
источник
{58871,5592,-47687,-100966,-154245}
NextPrime
может вернуть отрицательные значения. Как ты это нашел?Python27,
283182Хорошо, я очень уверен в своем шкафчике, но это довольно долго, так как я добавил «трудно перевернуть» вычисления к входу, чтобы сделать его хорошо - трудно перевернуть.
Редактировать: Спасибо Colevk для дальнейшего игры в гольф. Во время редактирования я понял, что в моем алгоритме есть и ошибка, и, может быть, в следующий раз мне повезет больше.
источник
121174841 121174871 121174901 121174931 121174961
работает, но только если список[1,3,5,7]
в строке 7 заменяется на[1,3,5,7,11]
.Mathematica
142146РЕДАКТИРОВАТЬ : ключ не был уникальным, добавил 4 символа, теперь это так.
(Пробелы и символы новой строки добавлены для удобства чтения, не учитываются и не нужны).
Использование:
источник
256208
, дельта-5
.IntegerDigits
а затем учитывать, чтобы получить кандидатов на начальный срок и дельту.NextPrime
; если мы изменим его на плюс или минус один, по крайней мере один из них даст то же самое следующее простое число.Взломанный @Dennis через 2 часа
Просто, чтобы начать работу - я полностью ожидаю, что это будет быстро взломано.
Пиф , 13
Принимает разделенный запятыми ввод на STDIN.
Запустите его так (-c означает принять программу в качестве аргумента командной строки):
Исправил программу - я не понял спецификацию.
Этот язык может быть слишком эзотерическим для этого соревнования - если OP так думает, я его уберу.
источник
1,2,3,4,5
ключ?97,96,95,94,93
(Я только что убил свой потрясающий счет.)Луа 105
Я подозреваю, что это не займет много времени, прежде чем он взломан, но здесь мы идем:
(пробелы добавлены для ясности, но не являются частью подсчета)
источник
3, 7, 11, 15, 19
или6, 14, 22, 30, 38
t1==0
всякий разS
, когда увеличивается. Кроме того, оба условия являются однородными; ЕслиS
это решение, так и естьkS
.Perl - 256
Мне пришлось добавить много логики обработки ошибок, и это, безусловно, может привести к гораздо большему. Он напечатает,
1
когда вы получите правильные пять чисел. Он с надеждой напечатать0
для всего остального (может быть ошибки или ничего, я не знаю). Если кто-то хочет помочь улучшить код или играть в гольф, не стесняйтесь помочь!Звоните с:
источник
Рубин - 130
На основе регистра сдвига с линейной обратной связью. Входные данные по аргументам командной строки.
Должно быть уникальным в зависимости от природы LFSR. Подсказка: восходящая и все положительная.
Даст больше подсказок, если никто не решит это в ближайшее время.
источник
Руби, 249
Должно быть весело. Кому нужна математика?
источник
309, 77347, 154385, 231423, 308461
но я не думаю, что это уникально.103, 232041, 463979, 695917, 927855
и3, 7966741, 15933479, 23900217, 31866955
. И я почти уверен, что есть другие действительные регулярные выражения, использующие дополнительные+
s.()
или аналогичный.CJam, 49 символов
Попробуйте онлайн.
Как это работает
Результат будет равен 1 тогда и только тогда, когда второе целое число будет множителем первого, которое является произведением двух простых чисел: одно соответствует секретной последовательности, а другое не соответствует какой-либо действительной последовательности. Поэтому решение является уникальным.
Факторизуя 512 битное целое число не что трудно, но я надеюсь , что никто не сможет в течение 72 часов. Моя предыдущая версия, использующая 320-битное целое число , была сломана .
Пример запуска
источник
Javascript 958
Преобразует входные данные в несколько типов данных и выполняет некоторые манипуляции, относящиеся к каждому типу данных. Должен быть довольно легко изменен для любого, кто берет время.
источник
320689, 444121, 567553, 690985, 814417
С, 239 (взломано Деннисом)
Пойди сюда для моего обновленного представления.
Возможно, будет играть в гольф немного более тщательно. По общему признанию, я не потратил время, чтобы доказать, что ключ уникален (вероятно, это не так), но он определенно имеет порядок коллизий хешей. Если взломали, поделитесь, пожалуйста, своим методом :)
источник
0 0 0 0 0
?C, 212 от Orby - треснувший
/codegolf//a/36810/31064 от Orby имеет как минимум два ключа:
Орби попросил метод, который я использовал, чтобы взломать его. Функция p проверяет, является ли x простым, проверяя
x%i==0
все i между 2 и x (хотя и используя(x/i)*i==x
вместоx%i==0
), и возвращает true, если x является простым числом. Функция f проверяет, что все a, b, c, d и e простые. Он также проверяет, является ли число m, конкатенация десятичных представлений e, d, c, b и a (в этом порядке), простым. Ключ таков, что a, b, c, d, e и m все простые.Грин и Тао (2004) показывают, что существует бесконечно много арифметических последовательностей простых чисел для любой длины k, поэтому нам просто нужно искать эти последовательности, которые также удовлетворяют m, являющемуся простым числом. Учитывая, что long ограничен значениями -9.223372037e + 18 и 9.223372037e + 18, мы знаем, что для объединенной строки, чтобы соответствовать long long, числа имеют верхнюю границу 9999. Таким образом, с помощью сценария python для генерации всех арифметические последовательности во всех простых числах <10000, а затем проверяя, является ли их обратная конкатенация простым числом, мы можем найти много возможных решений.
По какой-то причине у меня возникли ложные срабатывания, но два приведенных выше действительны в соответствии с программой. Кроме того, могут быть решения, где e отрицательно, а остальные положительны (p использует модуль x), но я не искал их.
Все ключи, которые я дал, являются арифметическими последовательностями, но сценарий Орби, по-видимому, не требует, чтобы входные данные были арифметической последовательностью, поэтому могут быть и недействительные ключи.
источник
MATLAB: очевидно недействительный
Очень просто, вам просто нужно сгенерировать правильное случайное число.
Это все еще может привести к ошибке, но это не должно быть проблемой.
источник
MATLAB (с набором символов), 173 символа
Это не официальная запись и не засчитывается как чей-то потрясающий результат, но это лишит вас безумных прав на хвастовство. ;)
Символический набор инструментов требуется только для обработки вычитания больших целых чисел.
Грубое принуждение должно быть собакой, но если вы знакомы с сериалом, который он включает, решение тривиально.
источник
Python 2 (91)Изменить: Это не допускается, потому что аргумент в пользу уникальности является вероятностным. Я сдаюсь.
Принимает списки целых чисел в качестве ввода, как
[1,2,3,4,5]
.Цикл предназначен для работы на входах раздражающим способом, оставляя множество сумм и показателей. Идея похожа на дискретное бревно, но с математической простотой вместо математической простоты. Может быть, сложность модуля является уязвимостью, и в этом случае я мог бы сделать что-то вроде
7**58+8
.Я действительно не знаю, как я могу доказать, что мой ключ - единственный, но диапазон выходов по крайней мере в 10 раз больше, чем диапазон входов, так что, вероятно? Хотя, возможно, достижима лишь небольшая часть потенциальных результатов. Я всегда мог бы увеличить количество цифр за счет символов. Я оставлю это на ваше усмотрение, чтобы решить, что справедливо.
Счастливого взлома!
источник
Mathematica - 72
Версия 2 моего скрипта, с тем же ключом, который предназначен для моей версии 1.
Это в основном удаляет отрицательные простые числа для
NextPrime
.Бег:
источник
9244115
, delta25
.1073743739, 1073886396, 1074029053, 1074171710, 1074314367
Python, 86 символов
Введите цифры, как
1,2,3,4,5
.источник
1,0,1,63021563418517255630720,0
.19960211, 31167202, 42374193, 53581184, 64788175
63021563418517255630720
это не 32-битное число.Python, 78
(Взломано Тейло за 14 минут)
Весело!
Хорошо, здесь не отображается должным образом :(
Ожидается список из пяти чисел, например. [1,2,3,4,5]
источник
[-481890276, -594823292, -728999970, -887503650, -1073741792]
CJam, 37 символов (не работает)
Попробуйте онлайн.
Как это работает
Смотрите мой новый ответ.
Пример запуска
источник
737262825 208413108 3974530688 3445680972 2916831257
работает, но не арифметическая прогрессия. Факторинг за 3 часа 20 минут. 512-битные числа, по-видимому, выполнились за 72 часа за 75 долларов на EC2 два года назад, поэтому я думаю, что это было бы безопасно.737262825 208413109 -320436607 -849286323 -1378136039
С 212 (треснувший)
Это та же идея , как мое предыдущее представление , golfed более тщательно, с ошибкой исправлена Проходящими 0,0,0,0,0 (спасибо Денниса за указание на ошибке). Компилировать с -std = c99.
источник
-7 -37 -67 -97 -127
,-157 -127 -97 -67 -37