Шкафчики против взломщиков: последовательность из пяти элементов

31

Соревнование

Простая задача «шпион против шпиона».

Напишите программу со следующими характеристиками:

  1. Программа может быть написана на любом языке, но не должна превышать 512 символов (как представлено в блоке кода на этом сайте).
  2. Программа должна принимать 5 знаковых 32-битных целых в качестве входных данных. Он может принимать форму функции, которая принимает 5 аргументов, функции, которая принимает один массив из 5 элементов, или полной программы, которая считывает 5 целых чисел из любого стандартного ввода.
  3. Программа должна вывести одно 32-разрядное целое число со знаком.
  4. Программа должна возвращать 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).

Безопасные шкафчики

  1. CJam 49, Деннис
  2. CJam 62, Денис Сейф
  3. CJam 91, сейф Денниса
  4. Питон 156, Maarten Baert сейф
  5. Perl 256, безопасный для чилимагов
  6. Java 468, Geobits безопасно

Неостановимые крекеры

  1. Питер Тейлор [Ruby 130, Java 342, Mathematica 146 *, Mathematica 72 *, CJam 37]
  2. Деннис [Pyth 13, Python 86 *, Lua 105 *, GolfScript 116, C 239 *]
  3. Мартин Бюттнер [Javascript 125, Python 128 *, Ruby 175 *, Ruby 249 *]
  4. Тийло [C 459, Javascript 958 *]
  5. Фреддиекнец [Mathematica 67 *]
  6. Илмари Каронен [Python27 182 *]
  7. закись азота [C 212 *]

* несоответствующая подача

Отказ от ответственности (Обновлено 23:15 EST, 26 августа)

Когда проблемы с оценками наконец достигли критической массы (учитывая, что две трети взломанных представлений пока не соответствуют), я оценил лучшие взломщики с точки зрения количества взломанных отправлений (основной) и общего количества символов в совместимых взломанных отправках. (вторичные).

Как и прежде, точные данные о взломе, длительность представлений и их статус соответствия / несоответствия помечены так, чтобы читатели могли сделать вывод о своих собственных рейтингах, если они считают, что новые официальные рейтинги несправедливы.

Приношу свои извинения за внесение изменений в правила в конце игры.

COTO
источник
6
Как вы собираетесь проверить, что программы соответствуют пункту 4? Вы ожидаете, что люди отредактируют свои безопасные ответы, чтобы добавить доказательство? Допустимы ли вероятностные представления, исходя из предположения, что хеш-функции идеальны и вероятность столкновения с другим элементом 48-битного (согласно вашей оценке выше) пространства незначительна?
Питер Тейлор
2
Система подсчета очков, похоже, побуждает взломщиков игнорировать самые короткие замки, потому что они выигрывают лучше, взломав два длинных замка, чем два маленьких.
Питер Тейлор
3
@COTO Я думаю, проблема в том, что вы можете получить только 2 потрясающих результата, и только самый короткий. Так почему бы не подождать и не надеться, и дольше никто не появляется? Например, у Мартина теперь нет стимула взломать мой (более длинный) замок, поскольку он уже взломал два более коротких. Любой, кто взломает мой, теперь будет бить его, даже не делая второго.
Geobits
1
Я думаю, что лучшей системой оценки может быть сумма общего времени между вопросом и крэком. Таким образом, взломать кучу простых можно победить, и настоящая награда заключается в взломе действительно сложных.
Исаак
1
Я новичок в гольф, так что, возможно, это глупый вопрос, извините за это. Почему длина кода измеряется в символах, а не в байтах? Последнее буквально является пространством памяти, которое занимает программа, поэтому для меня это кажется более логичным. Например. ответ CJam является самым коротким в символах, но, глядя на его размер (326 из-за юникода), он даже не входит в топ-5. Поэтому я задаюсь вопросом, общепринято ли в гольфе считать символы вместо байтов?
freddieknets

Ответы:

3

CJam, 62 символа

"ḡꬼ쏉壥떨ሤ뭦㪐ꍡ㡩折量ⶌ팭뭲䯬ꀫ郯⛅彨ꄇ벍起ឣ莨ຉᆞ涁呢鲒찜⋙韪鰴ꟓ䘦쥆疭ⶊ凃揭"2G#b129b:c~

Stack Exchange склонен к обработке непечатаемых символов, но копирование кода из этой вставки и вставка его в интерпретатор CJam прекрасно работает для меня.

Как это работает

После замены строки Unicode строкой ASCII выполняется следующий код:

" Push 85, read the integers from STDIN and collect everything in an array.               ";

85l~]

" Convert the array of base 4**17 digits into and array of base 2 digits.                 ";

4H#b2b

" Split into chunks of length 93 and 84.                                                  ";

93/~

" Do the following 611 times:

    * Rotate array A (93 elements) and B one element to the left.
    * B[83] ^= B[14]
    * T = B[83]
    * B[83] ^= B[0] & B[1] ^ A[23]
    * A[92] ^= A[26]
    * Rotate T ^ A[92] below the arrays.
    * A[92] ^= A[0] & A[1] ^ B[5].                                                        ";

{(X$E=^:T1$2<:&^2$24=^+\(1$26=^_T^@@1$2<:&^3$5=^+@}611*

" Discard the arrays and collects the last 177 generated bits into an array.              ";

;;]434>

" Convert the into an integer and check if the result is 922 ... 593.                     ";

2b9229084211442676863661078230267436345695618217593=

Этот подход использует Bivium-B (см. Алгебраический анализ тривиумоподобных шифров ), ослабленную версию потокового шифра Trivium .

Программа использует последовательность целых чисел в качестве начального состояния, обновляет состояние 434 раза (354 раунда достигают полной диффузии) и генерирует 177-битный результат, который сравнивается с таковым в правильной последовательности.

Поскольку размер состояния составляет ровно 177 бит, этого должно быть достаточно для однозначной идентификации исходного состояния.

Пример запуска

$ echo $LANG
en_US.UTF-8
$ base64 -d > block.cjam <<< IgThuKHqrLzsj4nlo6XrlqjhiKTrrabjqpDqjaHjoanmipjvpb7itozuoIDtjK3rrbLul7bkr6zqgKvvjafpg6/im4XlvajqhIfrso3uprrotbfvmL/hnqPojqjguonhhp7mtoHujLPuipzlkaLpspLssJzii5npn6rpsLTqn5PkmKbspYbnlq3itorlh4Pmj60iMkcjYjEyOWI6Y34=
$ wc -m block.cjam
62 block.cjam
$ cjam block.cjam < block.secret; echo
1
$ cjam block.cjam <<< "1 2 3 4 5"; echo
0
Деннис
источник
6

CJam, 91 символов

q~]KK#bD#"᫖࿼듋ޔ唱୦廽⻎킋뎢凌Ḏ끮冕옷뿹毳슟夫΢眘藸躦䪕齃噳卤"65533:Bb%"萗縤ᤞ雑燠Ꮖ㈢ꭙ㈶タ敫䙿娲훔쓭벓脿翠❶셭剮쬭玓ୂ쁬䈆﹌⫌稟"Bb=

Stack Exchange склонен к обработке непечатаемых символов, но копирование кода из этой вставки и вставка его в интерпретатор CJam прекрасно работает для меня.

Как это работает

После замены строки Unicode на целые числа (с учетом цифр символов из базовых 65533 чисел) выполняется следующий код:

" Read the integers from STDIN and collect them in an array.                               ";

q~]

" Convert it into an integer by considering its elements digits of a base 20**20 number.   ";

KK#b

" Elevate it to the 13th power modulus 252 ... 701.                                        ";

D#
25211471039348320335042771975511542429923787152099395215402073753353303876955720415705947365696970054141596580623913538507854517012317194585728620266050701%

" Check if the result is 202 ... 866.                                                      ";

20296578126505831855363602947513398780162083699878357763732452715119575942704948999334568239084302792717120612636331880722869443591786121631020625810496866=

Поскольку 13 является взаимно простым для модуля модуля (этот термин является секретным, поэтому вам просто нужно доверять мне), разные базы будут давать разные результаты, т. Е. Решение является уникальным.

Если кто-то не может использовать небольшой показатель степени (13), самый эффективный способ сломать эту блокировку - это факторизовать модуль (см. Проблему RSA ). Я выбрал 512-битное целое число для модуля, которое должно выдерживать 72 часа попыток факторизации.

Пример запуска

$ echo $LANG
en_US.UTF-8
$ base64 -d > lock.cjam <<< cX5dS0sjYkQjIgHuiJHhq5bgv7zrk4velOWUse6zjuCtpuW7veK7ju2Ci+uOouWHjOG4ju+Rh+uBruWGleyYt+u/ueavs+6boOyKn+Wkq86i55yY6Je46Lqm5KqV6b2D5Zmz75Wp5Y2kIjY1NTMzOkJiJSIB6JCX57ik4aSe74aS6ZuR54eg4Y+G44ii6q2Z44i244K/5pWr5Jm/5aiy7ZuU7JOt67KT7rO26IS/57+g4p2275+K7IWt5Ymu7Kyt546T4K2C7IGs5IiG77mM4quM56ifIkJiPQ==
$ wc -m lock.cjam
91 lock.cjam
$ cjam lock.cjam < lock.secret; echo
1
$ cjam lock.cjam <<< "1 2 3 4 5"; echo
0
Деннис
источник
Я опубликовал новую версию, так как я забыл удалить ненужного персонажа из первого. Секретная последовательность все та же, поэтому вы можете попытаться взломать любой из них.
Деннис
К вашему сведению, я отменяю попытку факторинга. msieve установил для себя ограничение в 276 часов, но это было только для построения факторной базы. В то время это found 1740001 rational and 1739328 algebraic entries; с тех пор у него было почти 100 часов на их обработку и отчеты sieving in progress b = 46583, 0 complete / 0 batched relations (need 44970493).
Питер Тейлор
@PeterTaylor: похоже, 512 бит были излишними. Вы пытались указать целое число в моем другом ответе или в этом?
Деннис
Ой, упс. Да, другой.
Питер Тейлор
4

Python - 128

Давайте попробуем это:

i=input()
k=1050809377681880902769L
print'01'[all((i>1,i[0]<i[4],k%i[0]<1,k%i[4]<1,i[4]-i[3]==i[3]-i[2]==i[2]-i[1]==i[1]-i[0]))]

(Ожидается, что пользователь введет 5 чисел, разделенных запятыми, например 1,2,3,4,5.)

Фалько
источник
3
32416190039,32416190047,32416190055,32416190063,32416190071
Мартин Эндер
Вау, это было быстро! Вы правы! И я вышел.
Фалько
3
Кстати, это на самом деле неверно, потому что ваши пять целых чисел не вписываются в 32-разрядное целое число.
Мартин Эндер
4

Ява: 468

Вход дан как k(int[5]). Залог рано, если не равномерно. В противном случае, потребуется немного выяснить, правильны ли все десять хешей. Для больших чисел «немного» может означать десять секунд или больше, поэтому это может отговорить взломщиков.

//golfed
int k(int[]q){int b=q[1]-q[0],i,x,y,j,h[]=new int[]{280256579,123883276,1771253254,1977914749,449635393,998860524,888446062,1833324980,1391496617,2075731831};for(i=0;i<4;)if(q[i+1]-q[i++]!=b||b<1)return 0;for(i=1;i<6;b=m(b,b/(i++*100),(1<<31)-1));for(i=0;i<5;i++){for(j=1,x=b,y=b/2;j<6;x=m(x,q[i]%100000000,(1<<31)-1),y=m(y,q[i]/(j++*1000),(1<<31)-1));if(x!=h[i*2]||y!=h[i*2+1])return 0;}return 1;}int m(int a,int b,int c){long d=1;for(;b-->0;d=(d*a)%c);return (int)d;}

// line breaks
int k(int[]q){
    int b=q[1]-q[0],i,x,y,j,
    h[]=new int[]{280256579,123883276,1771253254,1977914749,449635393,
                  998860524,888446062,1833324980,1391496617,2075731831};
    for(i=0;i<4;)
        if(q[i+1]-q[i++]!=b||b<1)
            return 0;
    for(i=1;i<6;b=m(b,b/(i++*100),(1<<31)-1));
    for(i=0;i<5;i++){
        for(j=1,x=b,y=b/2;j<6;x=m(x,q[i]%100000000,(1<<31)-1),y=m(y,q[i]/(j++*1000),(1<<31)-1));
        if(x!=h[i*2]||y!=h[i*2+1])
            return 0;
    }
    return 1;
}
int m(int a,int b,int c){
    long d=1;for(;b-->0;d=(d*a)%c);
    return (int)d;
}
Geobits
источник
1
Ваш код зависает, если входная арифметическая последовательность убывает. Или, по крайней мере, занимает очень много времени. Что заставляет меня думать, что секретный код возрастает ...
Кит Рэндалл
3
@KeithRandall Упс. Давайте добавим четыре байта, чтобы нисходящие последовательности заняли необычайно короткое время, еще больше укрепляя вашу веру.
Geobits
4

Ява: 342

int l(int[]a){String s=""+(a[1]-a[0]);for(int b:a)s+=b;char[]c=new char[11];for(char x:s.toCharArray())c[x<48?10:x-48]++;for(int i=0;i<11;c[i]+=48,c[i]=c[i]>57?57:c[i],i++,s="");for(int b:a)s+=new Long(new String(c))/(double)b;return s.equals("-3083.7767567702776-8563.34366442527211022.4345579010483353.1736981951231977.3560837512646")?1:0;}

Вот строковый шкафчик, который зависит как от количества вводимых символов, так и от конкретного ввода. Последовательность может быть основана на неясных ссылках на поп-культуру. Повеселись!

Немного разгульный

int lock(int[]a){
    String s=""+(a[1]-a[0]);
    for(int b:a)
        s+=b;
    char[]c=new char[11];
    for(char x:s.toCharArray())
        c[x<48?10:x-48]++;
    for(int i=0;i<11;c[i]+=48,
                     c[i]=c[i]>57?57:c[i],
                     i++,
                     s="");
    for(int b:a)
        s+=new Long(new String(c))/(double)b;
    return s.equals("-3083.7767567702776-8563.34366442527211022.4345579010483353.1736981951231977.3560837512646")?1:0;
}
Geobits
источник
2
8675309? 90210?
Малахия
1
@ Malachi Две выдающиеся ссылки, без сомнения, но я не могу ни подтвердить, ни опровергнуть их применимость к этому упражнению.
Geobits
лол, я еще не совсем понял, как этот вызов работает полностью, я могу дать ему шанс позже, когда я дома.
Малахи
1
Начальный срок - -8675309дельта 5551212.
Питер Тейлор
@PeterTaylor Отлично сделано :)
Geobits
4

Питон, 147

Изменить: более короткая версия на основе комментария Денниса. Я также обновил последовательность, чтобы избежать утечки информации.

def a(b):
    c=1
    for d in b:
        c=(c<<32)+d
    return pow(7,c,0xf494eca63dcab7b47ac21158799ffcabca8f2c6b3)==0xa3742a4abcb812e0c3664551dd3d6d2207aecb9be

Исходя из проблемы дискретного логарифма, которая считается непробиваемой, однако, простое число, которое я использую, вероятно, слишком мало, чтобы быть безопасным (и у него могут быть другие проблемы, я не знаю). И вы можете, конечно, перебор, поскольку единственными неизвестными являются два 32-разрядных целых числа.

Мартен Баерт
источник
Дискретные логарифмы намного сложнее, чем я думал. Мой взломщик был на этом в течение 26 часов. Я сдаюсь.
Деннис
Вы можете решить проблему знака, инициализируя c=1, вычисляя c=(c<<32)+dи изменяя константу соответственно.
Деннис
3

Javascript 125

Этот должен быть взломан довольно быстро. Я сделаю что-то более сильное.

function unlock(a, b, c, d, e)
{
    return (e << a == 15652) && (c >> a == 7826) && (e - b == d) && (d - c - a == b) ? 1 : 0;
}
rdans
источник
6
0, 3913, 7826, 11739, 15652
Мартин Эндер
да, ты понял :)
rdans
3

Рубин, 175

a=gets.scan(/\d+/).map(&:to_i)
a.each_cons(2).map{|x,y|x-y}.uniq[1]&&p(0)&&exit
p a[2]*(a[1]^a[2]+3)**7==0x213a81f4518a907c85e9f1b39258723bc70f07388eec6f3274293fa03e4091e1?1:0

В отличие от использования криптографического хэша или srand, это доказуемо уникально (что является небольшой подсказкой). Принимает пять чисел через STDIN, разделенные любым нецифровым, не символом новой строки или символами. Выходы в STDOUT.

histocrat
источник
Да, забыл, что они были подписаны.
гистократ
2
622238809,1397646693,2173054577,2948462461,3723870345(моя предыдущая догадка имела ошибку, но эта проверена). Я не думаю, что это действительно так, потому что последнее число не помещается в 32-разрядное целое число со знаком.
Мартин Эндер
3

GolfScript (116 символов)

Принимает ввод как разделенные пробелом целые числа.

~]{2.5??:^(&}%^base 2733?5121107535380437850547394675965451197140470531483%5207278525522834743713290685466222557399=
Питер Тейлор
источник
2
-51469355 -37912886 -24356417 -10799948 2756521
Денис
Хорошо сделано. Вы использовали маленький показатель?
Питер Тейлор
2
Нет, я факторизовал модуль. Это заняло всего 13 секунд, используя примитивное сито с полиномами Quadratic Sieve и PyPy.
Деннис
В этом случае я мог бы также отказаться от своего текущего игры в гольф, используя компактно выраженный модуль. Если результат должен быть чем-то вроде 1024 бит, чтобы быть безопасным от факторинга, то даже с использованием представления base-256 это будет слишком длинным.
Питер Тейлор
Надеюсь нет. В моем ответе используется та же идея, что и у вас, но с 512-битным модулем и еще меньшим показателем (13). Учитывая 72-часовой лимит времени, этого может быть достаточно ...
Деннис
3

C 459 байт

Решено Tyilo - ЧИТАТЬ РЕДАКТИРОВАТЬ НИЖЕ

int c (int* a){
int d[4] = {a[1] - a[0], a[2] - a[1], a[3] - a[2], a[4] - a[3]};
if (d[0] != d[1] || d[0] != d[2] || d[0] != d[3]) return 0;
int b[5] = {a[0], a[1], a[2], a[3], a[4]};
int i, j, k;
for (i = 0; i < 5; i++) { 
for (j = 0, k = 2 * i; j < 5; j++, k++) {
k %= i + 1;
b[j] += a[k];
}
}
if (b[0] == 0xC0942 - b[1] && 
b[1] == 0x9785A - b[2] && 
b[2] == 0x6E772 - b[3] && 
b[3] == 0xC0942 - b[4] && 
b[4] == 0xB6508 - b[0]) return 1;
else return 0;
}

Нам нужен кто-то, чтобы написать решение C, не так ли? Я никого не впечатляю длиной, я не игрок в гольф. Надеюсь, это интересный вызов!

Я не думаю, что есть очевидный способ взломать этот, и я с нетерпением жду всех попыток! Я знаю, что это решение уникально. Очень минимальное запутывание, в основном для удовлетворения требований к длине. Это можно проверить просто:

int main(){
    a[5] = {0, 0, 0, 0, 0} /* your guess */
    printf("%d\n", c(a));
    return 0;
}

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].

int a[5];
for (a[0] = 0; a[0] <= upper_bound / 5; a[0]++) {
    for (a[1] = a[0] + 1; 10 * (a[1] - a[0]) + a[0] <= upper_bound; a[1]++) {
        a[2] = a[1] + (a[1] - a[0]);
        a[3] = a[2] + (a[1] - a[0]);
        a[4] = a[3] + (a[1] - a[0]);
        if (c(a)) {
            printf("PASSED FOR {%d, %d, %d, %d, %d}\n", a[0], a[1], a[2], a[3], a[4]);
        }
    }
    printf("a[0] = %d Checked\n", a[0]);
}

С a[0] = 6174этим циклом моя работа прервалась чуть меньше минуты.

BrainSteel
источник
6
Решение 6174, 48216, 90258, 132300, 174342.
Tyilo
Вау, это было быстро. Хороший. Брутфорс, или ты нашел что-то умное, что я пропустил?
BrainSteel
Я использовал символическую оценку Mathematica следующим образом: ghostbin.com/paste/jkjpf screenshot: i.imgur.com/2JRo7LE.png
Tyilo
Отредактируйте: я сделал в основном то же самое, но выдумал верх в 500k. Получил ответ и увидел, что его уже опубликовал
Tyilo
@ Geobits Это удивительно точное предположение. Надо было поставить еще 0 на концах этих чисел.
BrainSteel
3

Mathematica 80 67

f=Boole[(p=NextPrime/@#)-#=={18,31,6,9,2}&&BitXor@@#~Join~p==1000]&

Бег:

f[{1,2,3,4,5}] (* => 0 *)

Вероятно, довольно легко взломать, может также иметь несколько решений.

Обновление: улучшил игру в гольф, выполнив то, что предложил Мартин Бюттнер. Функциональность функции и клавиши не изменилась.

Tyilo
источник
@ MartinBüttner Улучшение ответов, чтобы получить более высокий балл, когда вы взломаете их. Smart; P
Tyilo
Ха, оказывается, я пропустил параграф о выигрыше для контр-соревнования. Я думал, что это просто для удовольствия без какого-либо счета вообще. Хотя я не думаю, что для меня будет иметь смысл сокращать решения, которые я хочу взломать, потому что это уменьшит мой счет.
Мартин Эндер
4
{58871,5592,-47687,-100966,-154245}
freddieknets
@freddieknets Не решение, которое я использовал при его создании. Не знал, что NextPrimeможет вернуть отрицательные значения. Как ты это нашел?
Tyilo
Тогда ваш ключ не уникален: с. Я только что провел несколько тестов - на самом деле не так уж много чисел, где NextPrime [#] - # оценивается как 31, так что это простой способ взломать его.
freddieknets
2

Python27, 283 182

Хорошо, я очень уверен в своем шкафчике, но это довольно долго, так как я добавил «трудно перевернуть» вычисления к входу, чтобы сделать его хорошо - трудно перевернуть.

import sys
p=1
for m in map(int,sys.argv[1:6]):m*=3**len(str(m));p*=m<<sum([int(str(m).zfill(9)[-i])for i in[1,3,5,7]])
print'01'[p==0x4cc695e00484947a2cb7133049bfb18c21*3**45<<101]

Редактировать: Спасибо Colevk для дальнейшего игры в гольф. Во время редактирования я понял, что в моем алгоритме есть и ошибка, и, может быть, в следующий раз мне повезет больше.

stokastic
источник
5
Это инвариант при переупорядочении аргументов, поэтому это недопустимый шкафчик.
Питер Тейлор
Кроме того, я подозреваю, что опубликованный код содержит ошибки: ключ 121174841 121174871 121174901 121174931 121174961работает, но только если список [1,3,5,7]в строке 7 заменяется на [1,3,5,7,11].
Ильмари Каронен
Черт, да, я просто исправлял свою опечатку, во время которой я сделал принципиальную ошибку в своем алгоритме, оставив его очень легко взломать: |
Stokastic
На самом деле, поиск и исправление ошибки было трудной частью; учитывая ваш алгоритм, факторинг константы был своего рода очевидной вещью, которую нужно попробовать.
Ильмари Каронен
2

Mathematica 142 146

РЕДАКТИРОВАТЬ : ключ не был уникальным, добавил 4 символа, теперь это так.

n=NextPrime;
f=Boole[
    FromDigits /@ (
        PartitionsQ[n@(237/Plus@##) {1, ##} + 1] & @@@ 
            IntegerDigits@n@{Plus@##-37*Log[#3],(#1-#5)#4}
    ) == {1913001154,729783244}
]&

(Пробелы и символы новой строки добавлены для удобства чтения, не учитываются и не нужны).

Использование:

f[1,2,3,4,5]   (* => 0 *)
freddieknets
источник
1
Начальный срок 256208, дельта -5.
Питер Тейлор
Черт, тогда он все еще не уникален, так как это не мой оригинальный ключ. Вы брутфорс?
freddieknets
Проверьте это, я мог ошибиться, потому что у меня нет доступа к Mathematica для тестирования. Каждый этап использует грубую силу, но это не так много компьютерного времени. Подход заключается в том, чтобы работать в обратном направлении к выходным данным, IntegerDigitsа затем учитывать, чтобы получить кандидатов на начальный срок и дельту.
Питер Тейлор
Но в любом случае этот подход не может быть уникальным. Второй из пяти входов используется только в сумме, которая передается NextPrime; если мы изменим его на плюс или минус один, по крайней мере один из них даст то же самое следующее простое число.
Питер Тейлор
да, но для арифметической последовательности - поскольку это обязательный вход - он должен был быть уникальным.
freddieknets
1

Взломанный @Dennis через 2 часа


Просто, чтобы начать работу - я полностью ожидаю, что это будет быстро взломано.

Пиф , 13

h_^ZqU5m-CGdQ

Принимает разделенный запятыми ввод на STDIN.

Запустите его так (-c означает принять программу в качестве аргумента командной строки):

$ echo '1,2,3,4,5' | python3 pyth.py -c h_^ZqU5m-CGdQ
0

Исправил программу - я не понял спецификацию.

Этот язык может быть слишком эзотерическим для этого соревнования - если OP так думает, я его уберу.

isaacg
источник
7
Ты только что отдал 1,2,3,4,5ключ?
Питер Тейлор
1
Каждый вход, который я пробовал, возвращал 1, вы переключали 1 и 0 как выход?
Tyilo
Извините, я не понял различия между выходом и возвратом - программа должна работать. Тот же основной алгоритм.
Исаак
3
97,96,95,94,93(Я только что убил свой потрясающий счет.)
Деннис
@ Денис молодец. Нужно изменить систему подсчета очков - она ​​создает действительно странные стимулы.
Исаак
1

Луа 105

Я подозреваю, что это не займет много времени, прежде чем он взломан, но здесь мы идем:

function f(a,b,c,d,e)
   t1=a%b-(e-2*(d-b))
   t2=(a+b+c+d+e)%e
   t3=(d+e)/2
   print(t1==0 and t2==t3 and"1"or"0")
end

(пробелы добавлены для ясности, но не являются частью подсчета)

Кайл Канос
источник
3, 7, 11, 15, 19или6, 14, 22, 30, 38
Деннис
@Dennis: к сожалению, это ни один из них. Надо будет поработать над этим чуть позже, чтобы убедиться в неуникальности.
Кайл Канос
t1==0всякий раз S, когда увеличивается. Кроме того, оба условия являются однородными; Если Sэто решение, так и есть kS.
Деннис
1

Perl - 256

sub t{($z,$j,$x,$g,$h)=@_;$t="3"x$z;@n=(7,0,split(//,$g),split(//,$h),4);@r=((2)x6,1,1,(2)x9,4,2,2,2);$u=($j+1)/2;for$n(0..$#r+1){eval{substr($t,$j,1)=$n[$n]};if($@){print 0; return}$j+=$r[$n]*$u}for(1..$x){$t=pack'H*',$t;}eval$t;if($@||$t!~/\D/){print 0}}

Мне пришлось добавить много логики обработки ошибок, и это, безусловно, может привести к гораздо большему. Он напечатает, 1когда вы получите правильные пять чисел. Он с надеждой напечатать 0для всего остального (может быть ошибки или ничего, я не знаю). Если кто-то хочет помочь улучшить код или играть в гольф, не стесняйтесь помочь!


Звоните с:

t(1,2,3,4,5);
hmatt1
источник
1

Рубин - 130

На основе регистра сдвига с линейной обратной связью. Входные данные по аргументам командной строки.
Должно быть уникальным в зависимости от природы LFSR. Подсказка: восходящая и все положительная.

Даст больше подсказок, если никто не решит это в ближайшее время.

x=($*.map{|i|i.to_i+2**35}*'').to_i
(9**8).times{x=((x/4&1^x&1)<<182)+x/2}
p x.to_s(36)=="qnsjzo1qn9o83oaw0a4av9xgnutn28x17dx"?1:0
Векторизованное
источник
3
Начальное значение 781783, приращение 17982811
Питер Тейлор
@PeterTaylor Argh ... =)
Векторизовано
1

Руби, 249

a=gets.scan(/\d+/).map(&:to_i)
a.each_cons(2).map{|x,y|x-y}.uniq[1]&&p(0)&&exit
r=(a[0]*a[1]).to_s(5).tr'234','(+)'
v=a[0]<a[1]&&!r[20]&&(0..3).select{|i|/^#{r}$/=~'%b'%[0xaa74f54ea7aa753a9d534ea7,'101'*32,'010'*32,'100'*32][i]}==[0]?1:0rescue 0
p v

Должно быть весело. Кому нужна математика?

histocrat
источник
2
309, 77347, 154385, 231423, 308461но я не думаю, что это уникально.
Мартин Эндер
Да, это не так. Для того же регулярного выражения (т.е. произведение первых двух чисел) я также нахожу 103, 232041, 463979, 695917, 927855и 3, 7966741, 15933479, 23900217, 31866955. И я почти уверен, что есть другие действительные регулярные выражения, использующие дополнительные +s.
Мартин Эндер
Извините, наверное, я испортил тестовую строку. Предполагалось, что будет только одно регулярное выражение с уникальной факторизацией.
гистократ
Если вы хотите попытаться это исправить, обязательно примите во внимание собственнические квантификаторы. Я также могу создать большее, эквивалентное регулярное выражение, вставив ()или аналогичный.
Мартин Эндер
1

CJam, 49 символов

"腕옡裃䃬꯳널֚樂律ࡆᓅ㥄뇮┎䔤嬣ꑙ䘿휺ᥰ籃僾쎧諯떆Ἣ餾腎틯"2G#b[1q~]8H#b%!

Попробуйте онлайн.

Как это работает

" Push a string representing a base 65536 number and convert it to an integer.            ";

"腕옡裃䃬꯳널֚樂律ࡆᓅ㥄뇮┎䔤嬣ꑙ䘿휺ᥰ籃僾쎧諯떆Ἣ餾腎틯"2G#b

" Prepend 1 to the integers read from STDIN and collect them into an array.               ";

[1q~]

" Convert that array into an integer by considering it a base 2**51 number.               ";

8H#b

" Push the logical NOT of the modulus of both computed integers.                          ";

%!

Результат будет равен 1 тогда и только тогда, когда второе целое число будет множителем первого, которое является произведением двух простых чисел: одно соответствует секретной последовательности, а другое не соответствует какой-либо действительной последовательности. Поэтому решение является уникальным.

Факторизуя 512 битное целое число не что трудно, но я надеюсь , что никто не сможет в течение 72 часов. Моя предыдущая версия, использующая 320-битное целое число , была сломана .

Пример запуска

$ echo $LANG
en_US.UTF-8
$ base64 -d > flock512.cjam <<< IuiFleyYoeijg+SDrOqvs+uEkNaa76a/5b6L4KGG4ZOF76Gi46WE64eu4pSO5JSk5ayj6pGZ5Ji/7Zy64aWw57GD5YO+7I6n6Kuv65aG7qK04byr6aS+6IWO7rSn7YuvIjJHI2JbMXF+XThII2IlIQ==
$ wc -m flock512.cjam
49 flock512.cjam
$ cjam flock512.cjam < flock512.secret; echo
1
$ cjam flock512.cjam <<< "1 2 3 4 5"; echo
0
Деннис
источник
Я запускал msieve более 24 часов, но, поскольку он сам наложил ограничение на время в 276,51 CPU-часа, и я дал ему только один CPU, я не оптимистичен.
Питер Тейлор
0

Javascript 958

Преобразует входные данные в несколько типов данных и выполняет некоторые манипуляции, относящиеся к каждому типу данных. Должен быть довольно легко изменен для любого, кто берет время.

function encrypt(num)
{
    var dateval = new Date(num ^ (1024-1) << 10);

    dateval.setDate(dateval.getDate() + 365);

    var dateString = (dateval.toUTCString() + dateval.getUTCMilliseconds()).split('').reverse().join('');

    var result = "";

    for(var i = 0; i < dateString.length; i++)
        result += dateString.charCodeAt(i);

    return result;
}

function unlock(int1, int2, int3, int4, int5)
{
    return encrypt(int1) == "5549508477713255485850495848483249555749321109774324948324410511470" && encrypt(int2) == "5756568477713252485848495848483249555749321109774324948324410511470" && encrypt(int3) == "5149538477713248485856485848483249555749321109774324948324410511470" && encrypt(int4) == "5356498477713256535853485848483249555749321109774324948324410511470" && encrypt(int5) == "5748568477713251535851485848483249555749321109774324948324410511470" ? 1 : 0;
}
rdans
источник
5
320689, 444121, 567553, 690985, 814417
Скотина
@Tyilo Если вы остановитесь сейчас, я думаю, что ни один взломщик не сможет побить ваш счет. ;)
Мартин Эндер
2
@ MartinBüttner Если это не может быть добавлено до 512 за операцию, я не думаю, что это считается.
Geobits
0

С, 239 (взломано Деннисом)

Пойди сюда для моего обновленного представления.

Возможно, будет играть в гольф немного более тщательно. По общему признанию, я не потратил время, чтобы доказать, что ключ уникален (вероятно, это не так), но он определенно имеет порядок коллизий хешей. Если взломали, поделитесь, пожалуйста, своим методом :)

p(long long int x){long long int i;x=abs(x);
for (i=2;i<x;i++) {if ((x/i)*i==x) return 0;}return 1;}
f(a,b,c,d,e){char k[99];long long int m;sprintf(k,"%d%d%d%d%d",e,d,c,b,a);
sscanf(k,"%lld",&m);return p(a)&&p(b)&&p(c)&&p(d)&&p(e)&&p(m);}
Orby
источник
1
Так 0 0 0 0 0?
Деннис
Вздох, это была ошибка, но да, это работает.
Орби
Я обновил исправленную версию, которая должна быть немного более интересной;)
Orby
Смотрите исправленную версию здесь .
Орби
0

C, 212 от Orby - треснувший

/codegolf//a/36810/31064 от Orby имеет как минимум два ключа:

13 103 193 283 373
113 173 233 293 353

Орби попросил метод, который я использовал, чтобы взломать его. Функция 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), но я не искал их.

Все ключи, которые я дал, являются арифметическими последовательностями, но сценарий Орби, по-видимому, не требует, чтобы входные данные были арифметической последовательностью, поэтому могут быть и недействительные ключи.

азотистый
источник
0

MATLAB: очевидно недействительный

Очень просто, вам просто нужно сгенерировать правильное случайное число.

function ans=t(a,b,c,d,e)
rng(a)
r=@(x)rng(rand*x)
r(b)
r(c)
r(d)
r(e)
rand==0.435996843156676

Это все еще может привести к ошибке, но это не должно быть проблемой.

Деннис Джаэруддин
источник
1
Этот подход запрещен в комментариях. Если это не упоминается в вопросе, предложите изменить. Сожалею.
Питер Тейлор
@PeterTaylor Полагаю, я вышел, просто оставлю это здесь без очков, потому что мне любопытно, может ли кто-нибудь найти слабость.
Деннис Джаэруддин
0

MATLAB (с набором символов), 173 символа

Это не официальная запись и не засчитывается как чей-то потрясающий результат, но это лишит вас безумных прав на хвастовство. ;)

function b=L(S),c=sprintf('%d8%d',S(1),S(2)-S(1));b=numel(unique(diff(S)))==1&&numel(c)==18&&all(c([8,9])==c([18,17]))&&isequal(c,char(sym(sort(c,'descend'))-sym(sort(c))));

Символический набор инструментов требуется только для обработки вычитания больших целых чисел.

Грубое принуждение должно быть собакой, но если вы знакомы с сериалом, который он включает, решение тривиально.

COTO
источник
0

Python 2 (91)

Изменить: Это не допускается, потому что аргумент в пользу уникальности является вероятностным. Я сдаюсь.


s=3
for n in input():s+=pow(n,s,7**58)
print s==0x8b5ca8d0cea606d2b32726a79f01adf56f12aeb6e

Принимает списки целых чисел в качестве ввода, как [1,2,3,4,5].

Цикл предназначен для работы на входах раздражающим способом, оставляя множество сумм и показателей. Идея похожа на дискретное бревно, но с математической простотой вместо математической простоты. Может быть, сложность модуля является уязвимостью, и в этом случае я мог бы сделать что-то вроде 7**58+8.

Я действительно не знаю, как я могу доказать, что мой ключ - единственный, но диапазон выходов по крайней мере в 10 раз больше, чем диапазон входов, так что, вероятно? Хотя, возможно, достижима лишь небольшая часть потенциальных результатов. Я всегда мог бы увеличить количество цифр за счет символов. Я оставлю это на ваше усмотрение, чтобы решить, что справедливо.

Счастливого взлома!

XNOR
источник
0

Mathematica - 72

Версия 2 моего скрипта, с тем же ключом, который предназначен для моей версии 1.

Это в основном удаляет отрицательные простые числа для NextPrime.

f=Boole[(p=Abs[NextPrime/@#])-#=={18,31,6,9,2}&&BitXor@@#~Join~p==1000]&

Бег:

f[{1,2,3,4,5}] (* => 0 *)
Tyilo
источник
Предполагая, что я правильно понял, что делает ваш код, я получаю несколько решений, из которых наименьшим является начальный термин 9244115, delta 25.
Питер Тейлор
@PeterTaylor Я могу подтвердить, что это действительно.
Мартин Эндер
@PeterTaylor правильно, еще один ключ1073743739, 1073886396, 1074029053, 1074171710, 1074314367
Tyilo
0

Python, 86 символов

a,b,c,d,e=input()
print 1if(a*c^b*e)*d==0xd5867e26a96897a2f80 and b^d==48891746 else 0

Введите цифры, как 1,2,3,4,5.

> python 36768.py <<< "1,2,3,4,5"
0
> python 36768.py <<< "[REDACTED]"
1
Легкая закуска
источник
Это неверное представление; он принимает входные данные 1,0,1,63021563418517255630720,0.
Деннис
@ Денис Исправлено. Я надеюсь, что это действительно сейчас.
Закуска
1
19960211, 31167202, 42374193, 53581184, 64788175
Деннис
@ Денис Правильно и круто. Я думаю, что я очень плохо разбираюсь в математике.
Закуска
2
@ Денис, 63021563418517255630720это не 32-битное число.
Питер Тейлор
0

Python, 78

(Взломано Тейло за 14 минут)

Весело!

def L(a): return 1 if a==[(i-i**6) for i in bytearray(' ','utf-8')] else 0

Хорошо, здесь не отображается должным образом :(

Ожидается список из пяти чисел, например. [1,2,3,4,5]

ElectricWarr
источник
1
Довольно просто:[-481890276, -594823292, -728999970, -887503650, -1073741792]
Tyilo
Думал так, молодец :)
ElectricWarr
0

CJam, 37 символов (не работает)

"煷➻捬渓类ⶥ땙ዶ꾫㞟姲̷ᐂ㵈禙鰳쥛忩蔃"2G#b[1q~]4G#b%!

Попробуйте онлайн.

Как это работает

Смотрите мой новый ответ.

Пример запуска

$ echo $LANG
en_US.UTF-8
$ base64 -d > flock.cjam <<< IueFt+Keu+aNrOa4k+exu+K2peuVmeGLtuq+q+Oen+Wnsu6AhMy34ZCC47WI56aZ6bCz7KWb5b+p6JSDIjJHI2JbMXF+XTRHI2IlIQ==
$ wc -m flock.cjam
37 flock.cjam
$ cjam flock.cjam < flock.secret; echo
1
$ cjam flock.cjam <<< "1 2 3 4 5"; echo
0
Деннис
источник
1
737262825 208413108 3974530688 3445680972 2916831257работает, но не арифметическая прогрессия. Факторинг за 3 часа 20 минут. 512-битные числа, по-видимому, выполнились за 72 часа за 75 долларов на EC2 два года назад, поэтому я думаю, что это было бы безопасно.
Питер Тейлор
@PeterTaylor: возвращает 1, но последние три целых числа больше MAX_INT, поэтому это недопустимый ключ. При этом 3 ч 20 м впечатляют. Алгоритм, который я использовал, занял 16 часов для 256-битного полупростого числа ...
Деннис
Я думал, что где-то там должны быть отрицательные числа, потому что дельты были почти правильными, но не совсем. Я займусь этим.
Питер Тейлор
1
737262825 208413109 -320436607 -849286323 -1378136039
Питер Тейлор
@PeterTaylor: Это тот самый. Я надеюсь, что 512-битная версия длится дольше.
Деннис
-2

С 212 (треснувший)

Это та же идея , как мое предыдущее представление , golfed более тщательно, с ошибкой исправлена Проходящими 0,0,0,0,0 (спасибо Денниса за указание на ошибке). Компилировать с -std = c99.

#define L long long
p(L x){x=abs(x);for(L i=2;i<x;i++){if((x/i)*i==x)return 0;}return(x>1);}
f(a,b,c,d,e){char k[99];L m;sprintf(k,"%d%d%d%d%d",e,d,c,b,a);sscanf(k,"%lld",&m);
return p(a)&p(b)&p(c)&p(d)&p(e)&p(m);}
Orby
источник
Любая последовательность (арифметическая или нет) отрицательных простых чисел будет работать. Два примера: -7 -37 -67 -97 -127,-157 -127 -97 -67 -37
Dennis
Да, мой код просто изобилует ошибками. Ответ закись дал вдоль линии, что я искал. Но хорошая работа, указывающая на более очевидные ответы.
Орби