36

Подача ответов на конкурс завершена! Промежуточные итоги будут скоро подведены, окончательные итоги — после завершения параллельного конкурса взломщиков. Спасибо всем, кто принимал участие!


Итак, мы проводим очередное соревнование! Это соревнование необычное, оно состоит из двух частей. Тема задания — проверка пароля.

Мы ведь все помним, что краткость — сестра таланта? Первая часть задания состоит в разработке как можно более короткой функции, проверяющей пароль. На вход функция должна получать строку в идиоматичном для выбранного вами языка виде (char* или wchar_t* для C, то же или std::string/std::wstring для C++ и т. д.), на выход выдавать логическое значение (снова-таки в принятой в вашем языке форме, например, int в C и bool в C++). Логическое значение «истина» соответствует тому, что введённая строка является правильным паролем.

Пароль придумываете вы сами, и должны будете раскрыть его в конце конкурса. Длина вашего пароля не должна превышать 64 символов (code point'ов для unicode-строк), но функция должна уметь обрабатывать строки разумно произвольной длины (помещающиеся в половину доступной виртуальной памяти). Если ваша функция выдаёт true и для других строк, ничего страшного, все они тоже считаются подходящими паролями.

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

Почему же это задание сложное? Почему тривиальная функция () => true не подходит? Дело в том, что в ход игры вмешиваются игроки второй части вопроса — начинающие талантливые хакеры. Любой из хакеров может попытаться взломать вашу функцию: подобрать такую строку (возможно, длиннее 64 символов и не обязательно совпадающую с задуманным вами паролем), что ваша функция вернёт на ней true. Взломанные функции выбывают из конкурса. Править вашу функцию после того, как опубликован взлом, нельзя. Править вашу функцию более чем через сутки после опубликования нельзя. Но вы можете написать альтернативную функцию отдельным ответом, не более трёх в общей сложности на одного участника. Красть чужие функции нехорошо. Хакерам будет дано 3 дня на взлом каждой их ваших функций.

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

Ограничения: Функция не должна содержать undefined behaviour (если оно есть в вашем языке/компиляторе), предполагать стабильность или нестабильность вычислений с плавающей точкой, полагаться на случайные числа или текущие дату/время/информацию из внешних источников (включая обращение к сторонним сервисам, в том числе и в интернете). Функция должна быть детерминистической, то есть, менять свой результат лишь при изменении входных данных, и данные должны передаваться в неё лишь через входной параметр. Функция не должна пользоваться библиотеками кроме стандартных библиотек языка, и ни в коем случае не должна пользоваться сторонними крипто-, хэширующими и математическими библиотеками (или отдельными функциями/процедурами/методами/...). Функция не должна также обращаться к специальным криптографическим конструкциям, встроенным в оборудование (пример). Функция не должна запускать сторонних процессов (кроме возможно копий/частей программы). Функция должна на вашем пароле на вашем компьютере выдавать положительный результат за не более чем минуту вычислений. Функция имеет право упасть, это также считается положительным ответом. То есть, если хакер сможет «положить» вашу функцию, она считается взломанной. (Но он не может передавать в функцию испорченную строку: nullptr, невалидную память, или например содержащую встроенные нули для C. Другими словами: хакер не должен использовать UB или рефлексию сам.)

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

При неоднозначности лучше переспросите в code golf-чате. Окончательное решение при отсутствии консенсуса остаётся за организатором конкурса.

Продолжительность конкурса — одна неделя, а точнее, окончание в 23:59:59 29.05.2017 по UTC. Новые решения после этого срока в зачёт не принимаются. Время окончания конкурса хакеров равно времени окончания конкурса криптографов плюс трое суток; взломанные после этого срока функции считаются выдержавшими испытание. Вы должны будете предоставить пароль после окончания конкурса хакеров. Если ваша функция не выдаёт истину или падает на вашем пароле, она снимается с конкурса.

Победителем конкурса будет объявлена самая короткая невзломанная программа, которая выдержит проверку «своего» пароля.

Языки для конкурсных программ допускаются лишь те, для которых есть общедоступный компилятор под общедоступные платформы (одна из: Windows XP+, Linux не более, чем пятилетней свежести, Mac OS). Просьба не злоупотреблять экзотическими языками. В ответ желательно включить полную компилируемую программу, будет учитываться лишь длина функции проверки (а также ваших функций, вызываемых из неё).

Конкурс хакеров проходит здесь.

Обсуждение вопроса ведётся в code golf-чате, если вам непонятно условие, спрашивайте там (ну в крайнем случае в комментариях, если у вас недостаточно репутации).

Удачи всем участникам!


Турнирная таблица:

#leadership { border-collapse: collapse; } #leadership td, #leadership th { padding: 5px; } #leadership th { text-align: center; }
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<script src="https://rawgit.com/vladd/bd3338bbfa8163530e63717f2305a4d1/raw/4be1307d8a82bf7ea1f961cda9e90cde59e75eaf/ruso-winnertable-669381-v2.js"></script>
<h1>Таблица лидеров</h1><table id="leadership"><tr><th></th><th>Автор</th><th>Язык</th><th>Ток.</th><th>Взлом?</th><th>Осталось</th><th>Хор?</th><th></th></tr></table>

31
  • 2
    @avp взломщик видит исходник функции и чтобы "взломать" её, он должен предоставить аргумент, при котором функция вернёт условный true (или упадёт).
    – user181100
    22 мая 2017 в 19:23
  • 1
    То есть я правильно понял, что надо написать функцию, которую взломщик не сможет развернуть и выудить из нее исходный пароль или положить ее?
    – Alex Krass
    22 мая 2017 в 19:26
  • 1
    @AlexKrass: Именно так! Да ещё и короткую при этом.
    – VladD
    22 мая 2017 в 19:27
  • 2
    Так это и не вопрос, вот в чем дело.
    – zb'
    27 мая 2017 в 15:13
  • 2
    @zb' вы можете оставить свой голос "против" на Мете в обсуждении. Если отрицательный ответ будет лидировать - вопросы-соревнования появляться перестанут. Но в данный момент разрешение соревнований лидирует с разгромным счетом - 44/7. 29 мая 2017 в 5:22

27 ответов 27

13

Python 3.2+, 172 токена (время на взлом истекло)

def check(p):
    i=lambda x:int.from_bytes(x.encode('utf-16le','surrogatepass'),'big')
    try:return i(p)**65537%i('쳞\ue7e2䄝\uf03a듌垴ﮍ믚騾갢䳡︪ۡ䓽㒞䇑⮚⯎사᳀ᗦ딵㎹勤ㅵᕛ\uda35竹彽㝼꤅熎')==i('꼬㶳ꖅ慘钽\uf0fe젬\uf4fcᆎ횹鸝ᝄ幎垡륿ᖽﮠ鹰\uec89ᮒ핪篜Ⱃ⏾≅刳ﬖ睘쁽뭊㧇읚')
    except:return False

Ответ:

>>> check('簅䊆蓐鷃礤匹崚콂퉾횏練\ue611ﯻ⁼\uec77酢툖ᒆ뻉쇓\ufbcf')
True

Алгоритм - возведение в степень по модулю, как в RSA. Пароль - выхлоп os.urandom.

Использование decode с 'surrogatepass' позволяет преобразовать практически любой набор байт в строку. Помогает уменьшить количество токенов.

2
  • 2
    Так, погодите. Значит, синус использовать нельзя - а длинное возведение в степень - это типа нормально?! 23 мая 2017 в 13:47
  • @Abyx: Время на взлом истекло, опубликуете пароль (и комментарии к алгоритму, если можно)?
    – VladD
    26 мая 2017 в 14:24
11

C#, 96 токенов (снята с участия автором)

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

public bool check(string str)
{
    ulong hash = 14695981039346656037;
    for (var i = 0; i < str.Length; i++)
         hash = (hash ^ (byte) str[i]) * 0x100000001b3;
    return hash==7512177054858691173;
}

Ответ: 4354351213674675880334221324354351213-rsa

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

UPDATE

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

19
  • Для уточнения. Максимальное значение для ulong 18446744073709551615 (0xFFFFFFFFFFFFFFFF). hash = 14695981039346656037 (0xCBF29CE484222325). Возьмём для примера, что строка состоит из 1 символа, тогда hash ^ str[i] изменит максимум 3 последние цифры. Само число так и останется большим. Если его умножить на 0x100000001b3, то не будет ли это считаться переполнением (UB)?
    – Vitaly
    24 мая 2017 в 14:42
  • @Vitaly: В C# нет UB, переполнение просто возвращает результат по модулю размера результата.
    – VladD
    24 мая 2017 в 19:42
  • 1
    @Vitaly Спасибо за вопрос и спасибо VladD за ответ! :) Я разверну чуть подробнее ответ и скажу, что да это будет считаться переполнением потому что выходит за рамки, но это не UB..я под этот алгоритм я не просто так выбрал C#. В C# без операции checked { }, по умолчанию переполнение превращает максимальное число в минимальное без ошибки. Предположим ulong.MaxValue + 1 будет равно ulong.MinValue, т.е. 0, +2 == 1 и т.д. Это поведение определенно и везде одинаково в C#.
    – Firepro
    24 мая 2017 в 20:25
  • 1
    @VladD Хочется все-таки победить собственными силами, а здесь же победа не моя, а победа трех великих ученых. Я лишь в течении дня искал в этом алгоритме коллизии на цифрах, но не смог найти (я думаю, что они тоже это делали) и решил, что это будет отличная головоломка для всех и кто-нибудь его взломает, но я так понимаю, что не нашел никто и этот простой алгоритм оказался для всех сложнее, чем я думал. Я поступлю честно по отношению к другим участникам, и сниму эту функцию с участия. Я думаю, этот пост подскажет многим участникам, на чем основываться при написании функций :)
    – Firepro
    27 мая 2017 в 0:12
  • 2
    @Firepro: Большое спасибо за вашу принципиальность!
    – VladD
    27 мая 2017 в 9:54
9

C, 73 токена (взломан)

x86, little-endian

int f(char* s) {
    uint32_t a = 0, b, i = 0;
    if (s[0] && s[1] && s[2])
        a = *(uint32_t*)s;
    b = a;
    while (++i)
        a = a * 7 + 7;
    return a + b == 980355503;
}

Взломан @Mike, ссылка.

15
  • while (++i) — UB? Знаковое переполнение же, писали в чате. Да и размерность int-а может быть разной (привет x64!); как результат — платформозависимое количество итераций. 22 мая 2017 в 20:23
  • И ещё: вы проверяете первые три символа, но считываете в a четыре (и снова int...). Так планировалось, или вы забыли в условии ... && !s[3]? 22 мая 2017 в 20:26
  • @Arhad, s[3] не забыл.
    – Qwertiy
    22 мая 2017 в 20:29
  • little / big indian?
    – Qwertiy
    22 мая 2017 в 20:29
  • 1
    @Arhad, почему? Неправильный пароль может быть любой длины.
    – avp
    22 мая 2017 в 20:52
9

Python 3, 100 токенов (взломан)

def check(s):
  try:
    return int(s[:32], 16) * int(s[32:], 16) == 0x116a53fdcf374e3d8a4a19ca59a8017fd3680e7b707f9ed834a8ac4538586845
  except:
    return False

Взломан @Firepro, ссылка.

9

Python 3, 107 токенов (взломан)

Исправил уязвимость предыдущего ответа.

def check(s):
  try:
    x = int(s[:32], 16)
    return x > 1 and x * int(s[32:], 16) == 0x620fe07bca360829f97c33bd0aa64795a27c2cc4f67dd5d699a0af7cccb86d1f
  except:
    return False

Взломан @Firepro, ссылка.

9

C, 180 токенов (взломан)

/*
 * gcc crypt.c -o crypt
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define M 0x2B72576B913FD740
#define S 0xB72576B913FD7400

typedef unsigned char uchar;

int check(uchar * pwd) {
    ulong s = M, i, j, k;
    for (i = 0, j = strlen(pwd); i < j; i++) for (k = 0; k < 8; k++) s = k & 0xC ? (i[pwd] & (1 << k) ? s ^ i[pwd] : s >> 1) : (*(pwd + i) & k ? s << 2 : s ^ S);
    return s == 0x0832CB347454C8AF;
}

int main(int argc, char ** argv) {
    if (argc < 2) {
        printf("Usage: %s string\n", argv[0]);
        return 1;
    }
    int s = strlen(argv[1]);
    uchar * pwd = calloc(s + 1, sizeof(char));
    memcpy(pwd, argv[1], s);
    printf("Result: %s\n", check(pwd) ? "OK" : "FAIL");
    free(pwd);
    return 0;
}

Взломан @Mike, ссылка.

2
  • 2
    Эй, это уже ваш 4й ответ! По правилам же только 3 ответа допускаются. 24 мая 2017 в 13:50
  • Один из ответов (не подошедших по критериям) удалил. Если нужно, могу, так же, заменить вариант, который не подошёл. А что касается, "не более 3 ответов", то этот пункт, видимо, я упустил. Условия, действительно, длинные.
    – Vitaly
    24 мая 2017 в 13:59
8

C++, 59 токенов (взломан)

Пусть будет c++ из-за bool :)

bool check(const char *str)
{
    uint64_t h = 5381;
    int c;

    while (c = *str++)
        h = ((h << 5) + h) + c;

    return h == 1180004904744509286;
}

Взломан @m9_psy, ссылка.

4
  • 4
    Тривиальный Бернштейн (оно же DJBHash) в 64-бит упаковке наверное тоже не будет взломан нашими хакерами.
    – avp
    22 мая 2017 в 20:45
  • @alexolut: А какая разрядность вашего unsigned long? А то на системах, где 1180004904744509286 в него не влезает, будет всегда false.
    – VladD
    22 мая 2017 в 21:38
  • @VladD уточнил тип.
    – αλεχολυτ
    23 мая 2017 в 3:48
  • 2
    Возможный (не умею в C) ответ - ru.stackoverflow.com/a/669513/189819
    – m9_psy
    23 мая 2017 в 5:07
8

C#, 37 токенов (взломан)

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

Вот разминочка для мозга :)

public static bool check(string str)
{       
   int hash = 0;
   foreach(var c in str) hash ^= (hash * 23) + c;
   return hash==766862343;
}

Взломан @AlexKrass, ссылка.

1
8

Javascript, 858 токенов (время на взлом истекло)

Ну-ну, попробуйте взломать! :-)

function hash(str) {
  var 
    e32 = 0x100000000,
    f = (x,y,z) => x&y|~x&z,
    g = (x,y,z) => (x&y|x&z|y&z) + 0x5A827999,
    h = (x,y,z) => (x^y^z) + 0x6ED9EBA1,
    sf = [3,7,11,19],
    sg = [3,5,9,13],
    sh = [3,9,11,15],
    pf = [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15],
    pg = [0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15],
    ph = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],
    rot = (x,s) => ((x << s | x >>> (32-s)) + e32) % e32,

    a = 0x01234567,
    b = 0x89abcdef,
    c = 0xfedcba98,
    d = 0x76543210,
    i, j,
    data = [...str].map(c => c.charCodeAt(0))

  data.push(0x80)
  while(data.length % 16 != 14) data.push(0)

  data.push((str.length * 32) % e32)
  data.push(Math.floor((str.length * 32) / e32) % e32)

  for (var j=0; j<data.length; j+=16) {
    const [aa,bb,cc,dd] = [a,b,c,d]
    for (var i=0; i<16; i++) {
      [a, b, c, d] = [d, rot((a + data[j+pf[i]] + f(b,c,d))%e32, sf[i%4]), b, c]
    }
    for (var i=0; i<16; i++) {
      [a, b, c, d] = [d, rot((a + data[j+pg[i]] + g(b,c,d))%e32, sg[i%4]), b, c]
    }
    for (var i=0; i<16; i++) {
      [a, b, c, d] = [d, rot((a + data[j+ph[i]] + h(b,c,d))%e32, sh[i%4]), b, c]
    }
    [a,b,c,d] = [(a+aa)%e32, (b+bb)%e32, (c+cc)%e32, (d+dd)%e32]
  }

  return [a,b,c,d].map(x => [4,0,12,8,20,16,28,24].map(y => ((x >> y) & 15).toString(16)).join("")).join("")
}

function check(str) {
    return hash(str) == "7eaf037aa05ffa6f5a0844d8f891570f";
}

console.log(check("Это был почти md4 :-)"));

3
  • Функция не должна пользоваться библиотеками кроме стандартных библиотек языка, и ни в коем случае не должна пользоваться крипто-, хэширующими и математическими библиотеками (или отдельными функциями/процедурами/методами/...).
    – Alex78191
    23 мая 2017 в 20:02
  • @Alex78191: ну самописными-то можно... Уточню-ка я условие.
    – VladD
    23 мая 2017 в 21:30
  • @Danis в смысле - как? 21 ноя 2020 в 20:05
8

C#, 294 токена (время на взлом истекло)

№2 (вторая попытка)

public bool check(string pass) 
{
    try 
    {
        string subfind = string.Concat((char)1, (char)3, (char)17, pass.Substring(58, 5));

        return string.Join("", pass.Take(58).Select(p =>
        {
            int rand = p * 2017 % pass[63];
            var sv = new List<int>();

            var q = from sub in subfind where sub <= rand select sub;
            while(q.Any())
            {
                sv.Add(q.Max());
                rand -= q.Max();
                if (sv.Count > 8) break;
            }

            var regroup = "";
            for (int i = 0; i < subfind.Length; i++)
            {
                regroup += sv.Contains(subfind[i]) ? "1" : "0";
            }

            return (char)regroup.Select(pq => pq == '0' ? 0 : 1).Aggregate((a, b) => a * 2 + b);
        })) == "nulla molestie ligula mauris dictum sed pellentesque ipsum";
    }
    catch { return false; }
}

Взлом функции

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

Само решение:

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

Сравнивая описание алгоритма в той же вики и код, находим следующее. Зашифрованной строкой является "nulla molestie ligula mauris dictum sed pellentesque ipsum", часть закрытого ключа передается в строке следующих пяти символах pass.Substring(58, 5). Одно из чисел находится в позиции pass[63], второе вычисляется как обратный элемент по модулю pass[63] для числа 2017.

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

int[] w = new int[] { 1, 3, 17, 47, 233, 578, 3077, 9672 };

Выбираем число q так, что бы оно было больше суммы значений w.

int q = 14832;

Проверяем, что для него существует обратный элемент, это будет наш r.

static void Main(string[] args)
{
    var inverse = Inverse(2017, 14832);
}

private static int Inverse(int a, int m)
{
    int x, y;
    int g = GCD(a, m, out x, out y);
    if (g != 1)
        throw new ArgumentException();
    return (x % m + m) % m;
}

private static int GCD(int a, int b, out int x, out int y)
{
    if (a == 0)
    {
        x = 0;
        y = 1;
        return b;
    }
    int x1, y1;
    int d = GCD(b % a, a, out x1, out y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

Получили r = 9361

Ну а дальше остается только перешифровать.

static string alternative(string pass) 
    {
        int[] w = new int[] { 1, 3, 17, 47, 233, 578, 3077, 9672 };
        int q = 14832;
        int r = 9361;

        int[] b = new int[] { 
            w[0] * r % q, 
            w[1] * r % q, 
            w[2] * r % q, 
            w[3] * r % q, 
            w[4] * r % q, 
            w[5] * r % q, 
            w[6] * r % q, 
            w[7] * r % q };

        string passbits = string.Join("", Encoding.UTF8.GetBytes(pass).Select(byt => Convert.ToString(byt, 2).PadLeft(8, '0')));

        var a = Regex.Split(passbits, @"(.{8})").Where(p => p != "").Select(p =>
        {
            int sum = 0;
            for (int i = 0; i < 8; i++)
                sum += Convert.ToInt32(p[i].ToString(), 2) * b[i];
            return (char)sum;
        });

        return string.Join("", a) + string.Join("", w.Skip(3).Take(5).Select(p => (char)p).Union(new List<char>() { (char)q })); 
    }

И скормить ответы нашей функции, у меня в основном вышли иероглифы на различных значениях ключей и чисел.

check("辄왝轏轏燌⩁ꌗꍌ轏鿮顰늕瓵鿮⩁轏瓵ꀣ왝轏燌⩁ꌗ燌왝蒨瓵顰⩁谦瓵爁늕왝ꌗ⩁顰鿮谦⩁葳鿮轏轏鿮辄늕鿮顰頻왝鿮⩁瓵葳顰왝ꌗ/éɂఅ◈㧰");
check("仐䵵㮅㮅⳵၏䢧寲㮅䑒䥣䁓ㅊ䑒၏㮅ㅊ垝䵵㮅⳵၏䢧⳵䵵㱁ㅊ䥣၏㜰ㅊ䁀䁓䵵䢧၏䥣䑒㜰၏⣶䑒㮅㮅䑒仐䁓䑒䥣㘘䵵䑒၏ㅊ⣶䥣䵵䢧GãȳЉ࿗៟");
check("윙찆铌铌蟣⩁뺫铌陥ꈧ뀩陥⩁铌뀩좲찆铌蟣⩁뺫蟣찆엲뀩⩁沆뀩먰ꈧ찆뺫⩁陥沆⩁鎥陥铌铌陥윙ꈧ陥분찆陥⩁뀩鎥찆뺫1̦ϒࠝ✏㧰");
2
  • "Длина вашего пароля не должна превышать 64 символов" vs pass[66]?
    – Qwertiy
    23 мая 2017 в 13:55
  • @Qwertiy, не заметил ошибку, извиняюсь, уменьшил длину пароля до нужного ограничения.
    – Alex Krass
    23 мая 2017 в 14:19
8

C#, 109 токенов

Зарядка для хвоста.

public static bool check(string str)
{
    ulong hash = 0;
    int l = str.Length, a = l / 2;
    string str1 = str.Substring(0, a), str2 = str.Substring(a, l- a);
    foreach (var c in str1)
        foreach (var i in str2)
            hash ^= ~hash * 198349 + (ulong)(i%(c+1));
    return hash == 16396813230762036365;
}

Ответ: mа$t3rсгу

8

C++, 69 токенов (время на взлом истекло)

auto check(std::string s) {
    auto h = 6508530148971001438ull;
    for (uint8_t c : s)
        h = (h * 14886173955864302971ull) ^ c;
    return !h;
}

Вариация на тему FNV-0 64-bit.

Firepro свой FNV1a с конкурса снял, поэтому мы это исправим новым ответом!

Пароль это конечно же 8 (почти) случайных байт. Успешного перебора!


Ответ: check("@\t!\xfbTD-\x18")


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

Берем заготовку пароля

>>> struct.pack("d", math.pi)
b'\x18-DT\xfb!\t@'

и прогоняем ее через FNV0

auto fnv0(std::string const& s) {
    uint64_t h = 0;
    for (uint8_t c : s) {
        h = (h ^ c) * 0x100000001b3;
    }
    return h;
}

fnv0("\x18-DT\xfb!\t@") == 6508530148971001438

Считаем число обратное к 0x100000001b3 (modular multiplicative inverse):

>>> pow(0x100000001b3 , 2**63-1, 2**64)
14886173955864302971
>>> 14886173955864302971 * 0x100000001b3 % 2**64
1

меняем порядок операций, и получаем функцию check.
Пароль при этом тоже разворачивается и становится @\t!\xfbTD-\x18.


Как это ломать:

TL;DR: перебором за несколько минут.

Перепишем функцию check() как

h0 = 6508530148971001438;
h1 = (h0 * 14886173955864302971) ^ s[0];
...
h8 = (h7 * 14886173955864302971) ^ s[7]
return h8 == 0;

Заметим, что h7 равно s[7] * 0x100000001b3, и у этого числа много нулей, например 0x0000ff000001b14d для s[7] == 0xff. Это позволяет ускорить перебор, не делая вычисление h8.

Получаем вот такую функцию OpenCL:

kernel void func(uint s0, global uint* result) {
  size_t i = get_global_id(0);
  if (i >= 256*256) return;
  ulong h0 = 6508530148971001438ul;
  ulong h1 = (h0 * 14886173955864302971ul) ^ s0;
  ulong h2 = (h1 * 14886173955864302971ul) ^ (i >> 8) & 0xFF;
  ulong h3 = (h2 * 14886173955864302971ul) ^ (i & 0xFF);
  for (unsigned s3 = 0; s3 != 256; ++s3) {
    const ulong h4 = (h3 * 14886173955864302971ul) ^ s3;
    for (unsigned s4 = 0; s4 != 256; ++s4) {
      const ulong h5 = (h4 * 14886173955864302971ul) ^ s4;
      for (unsigned s5 = 0; s5 != 256; ++s5) {
        ulong h6 = (h5 * 14886173955864302971ul) ^ s5;
        ulong h7 = h6 * 14886173955864302971ul;
        if ((h7 & 0xffff00fffff00000ul) == 0) {
          result[i] = (s3 << 16) | (s4 << 8) | s5;
          return;
        }
      }
    }
  }
}

У меня она выполняется примерно 6 секунд, это позволяет дойти до s0 == '@' за минуты.

5
  • 1
    Ну и зачем ещё одно умножение-и-xor? Скучно же. И изобрели FNV ведь не вы? Какая доблесть в публикации алгоритма, придуманного умными дядьками?
    – VladD
    27 мая 2017 в 22:54
  • Никого не смущает !h??? Есть сомнения что автор сам не знает правильный ответ))
    – xirbm
    30 мая 2017 в 12:44
  • А можно пару ссылок на оригинальный FNV-0 или лучше код, а то я гуглить не умею.
    – xirbm
    30 мая 2017 в 14:43
  • @Abyx, Не особо шарю в С, но мне кажется алгоритм ответа чуть-чуть привязан к знанию ответа. Не вижу s6 в func. Получи строку str для "своей" хеш-функции, где h0=FNV0(str) = 424578851499022793
    – xirbm
    31 мая 2017 в 13:54
  • @Abyx, А видео карта какая?
    – xirbm
    1 июн 2017 в 4:03
7

C#, 74 токена (взломан)

Ответ № 1. Попробуем что-нибудь совсем простое, язык C#.

public static bool check(string p)
{
    try
    {
        int n = -977;
        foreach(var c in p)
            n += p.Aggregate((_, __) => (char)(_ + __));

        return p.Substring(12, 5) == (n / 2).ToString() ? true : false; 
    } catch { return false; }
}

Взломан @Firepro, ссылка.

2
7

Ruby 1.9.2+, 205 токенов (взломан)

def g_c(password)
  r = []; password.chars.sort{|a,b| r << a; a.ord - b.ord}
  r.join
end

def m_p
'MS__Myyyp_rreepMS_uuuuuaossassdrrq11___draaaaoossMMMS__eeeeppprruuuuy0788-08500555-0222277887477277725524423355233344477-0001255555555577788001111MMMMMMMMMMMMMMMMMM'
end

def check(password)
  g_c(password) == m_p
end

Уточнённая версия, не зависящая от реализации сортировки в конкретном руби:

class Array 
   def partition3
      a = Array.new(3) {|i| []}
      each do |x|
         a[yield(x)].push x
      end
      a
   end

   def qsort(&block)
      return self.dup if size <=1
      c,l,r = partition3 {|x| block.call(first,x)}
      l.qsort(&block) + c +  r.qsort(&block)
   end
end

def g_c(password)
  r = []; 
  password.chars.to_a.qsort{|a,b| r << ((r.size % 4 == 0 ) ? a : b); a.ord <=> b.ord}
  r.join
end

def check(password)
  g_c(password) == 'My_EMtraMFixMPasMordM(83M199M32EE-(8E619E132-(83-199-3288619813236113211199yyxtry_ixyPasyord_xtr__ix_Pas_ordxtraxxasxordtraitssotdrarassrrdaaaodiodss'
end

Взломан @VladD, ссылка.

26
  • Думаю не особо зависит. Точнее на тех данных которые есть он будет однозначно один и тот же. не зависимо от версии
    – Чад
    23 мая 2017 в 12:21
  • Исходя из описания этой функции в реализации руби. Могу добавить конкретную реализацию конечно, хотя сути это не изменит.
    – Чад
    23 мая 2017 в 12:23
  • 1
    для строки 'Hello, world!' текущий ruby генерирует eHollHHelw rdll oooow,,,Heelloo, в то же время IronRuby генерирует ello,,,,, woorrlllllddddddddd!!!!!!!!!!!! 23 мая 2017 в 13:14
  • 1
    А для python2.x И python 3.x различия тоже должны учитываться например? Это версия языка а не версия интерпретатора. В руби можно так же написать что в версии 2.0.x и в версии 2.3.x один и тот же код будут работать по разному. Если, конечно это проблема, могу встроить функцию сортировки явно и самопально, хотя это из разряда 'моя программа для виндовс не запускается на linux'
    – Чад
    23 мая 2017 в 13:20
  • 1
    @Чад с чего бы двум совершенно разным реализациям использовать один алгоритм сортировки? 23 мая 2017 в 14:09
7

Python 3, 189 токенов

Ну, теперь не взломаете!

def i(x):
    y = 0
    for i in range(len(x)):
        y += ord(x[i]) * 0xFFFF ** i
    return y

def c(s):
  try:
    x = i(s[:32])
    return x > 1 and x * i(s[32:]) == i('锼ԯ獆湳巩樋ꬁ옃\uf35e꺕䍔\udc02嗉旋ꗶ\uf723㇉랎\ue3d0\uea64像㪡ώ浑㤥\udd93僉䆦햲\udd7b\ud93b㻜叕䕎ꩠ陋컲襦캹ꃷ宊\uf14e욏肪\ude3a艎㒗Ģ또ሎ婢翈蚱ႉΑ桔ᅅ凹ᡎ哨朤뽝ꚜ鐔')
  except:
    return False

Вам надо разложить это число на множители (309 цифр):

103885866244747381663615014343439738509398529989572625404989988315137697040223344857852085986157148263429988190803798673714482791480965400051780365963630448634611947249214382745760025418403983231982081656737500352492523151600463727256295721224125884702295398456027019890543321464255995380923386472902008862899
1
  • 2
    Кто же знал, что тут такие внимательные и находчивые взломщики :)
    – pank
    25 мая 2017 в 20:14
7

Java, 393 токена (время на взлом истекло)

import java.util.*;

class Solution
{
    public static boolean check(String pwd)
    {
        String chk = "176230078174140160185101136122101089205201025138070243083056221017027225235135030144152073240059092027236208249148115073214246072102240160193049088024192124080088214163068";
        if ( ( pwd == null ) || ( pwd.length() * 3 != chk.length() ) ) return false;

        int n = pwd.length();
        char[] src = pwd.toCharArray();
        int[] res = new int[n];

        Arrays.fill(res, 0);

        for ( int i = 0; i < n*4; ++i )
            for ( int j = 0; j < n*4; ++j )
                res[(i+j)/8] ^= ((src[i/8] >> (i % 8)) & (src[n/2 + j/8] >> (j % 8)) & 1) << ((i+j) % 8);

        for ( int i = 0; i < n; ++i )
            if ( res[i] != Integer.parseInt(chk.substring(i*3, i*3 + 3)) )
                return false;

        return true;
    }

    public static void main(String[] args)
    {
        System.out.println(check((new Scanner(System.in)).nextLine()));
    }
}

Пароль:

// конечно, есть и другие варианты, способные пройти проверку
System.out.println(check("Do you really believe yourself to be a master of fencing?"));

О решении:

Разобравшись с тем, что делает функция, нетрудно составить уравнения (в булевой алгебре) для каждого бита зашитого в функцию большого числа (переменными будут биты строки-пароля).
Каждое полученное уравнение будет являться, помимо всего прочего, полиномом Жегалкина.
Полностью раскрывать алгоритм не буду, но напомню для наводки одно из свойств "исключающего или": ~X = X ^ 1
P.S.: аккуратно реализованный алгоритм решения отрабатывает за считанные секунды и выдаёт все варианты пароля

7

Python 2, 321 токен (время на взлом истекло)

# coding: utf-8
import copy

MY_PASSWROD = "0106BD6DE78317D077D1720060D29970D51809E09442410459450453"

pk = "Lorem ipsum blah-blah ключ"

a = 256


def MAGIC(k):
    b = range(a)
    j = 0
    for i in range(a):
        j = (j + b[i] + k[i % len(k)]) % a
        b[i], b[j] = b[j], b[i]

    x = 0
    y = 0
    c = map(int, (" ".join([str(c) for c in copy.deepcopy(b)]).split(" ")))
    while True:
        x = (x + 1) % a
        y = (y + c[x]) % a
        c[x], c[y] = c[y], c[x]

        K = c[(c[x] + c[y]) % a]
        yield K


def test_U(s):
    if not s:
        s = pk
    s = [ord(c) for c in s]
    m = MAGIC(s)
    answer = ""
    for c in pk:
        answer += "%02X" % (ord(c) ^ m.next())
    return answer == MY_PASSWROD

# Вне конкурса, пример использования
def tester(target_string):
    ans = test_U(target_string)
    if ans:
        print "WIN"
    else:
        print "LOSE"

if __name__ == '__main__':
    # Давай, перебери меня
    tester("")
    tester("yolo")
    tester("ЮНИКОД")
    tester("*"*2**28)

Это RC4. Ответ - \x00Я люблю тортики. ڝڞ Хочу тортик.∰™. Лишнее барахло (лишний юникод в префиксе/суффиксе) - исключить какой-нибудь хитрый подбор по словарю.

6
  • 1
    Ну и зачем было вставлять строку c = map(int, (" ".join([str(c) for c in copy.deepcopy(b)]).split(" ")))? Она как-то улучшает RC4? :-) 23 мая 2017 в 12:43
  • Если это известный алгоритм, то стоит хотя бы упомянуть об этом в условии.
    – VladD
    23 мая 2017 в 23:06
  • 1
    @VladD, это действительно RC4, отпираться бесполезно. В неизвестности алгоритма большая доля интереса. Одно дело написать - это RSA прямо (тоже в вопросах есть), а другое дело оставить код без пояснений, чтобы кто-нибудь неискушенный (вроде меня) позарился на небольшой размер кода и размял мозги. В ходе разминаний я на практике понял, почему с RSA взятки гладки. Если написать, что используется RSA, то никто и пробовать не станет - известно, что алгоритм сложно поддается "взлому" и останется пытать разлчиные вырожденные для атаки случаи.
    – m9_psy
    23 мая 2017 в 23:32
  • @m9_psy: Ну с одной стороны конечно да, можно считать это одним из шагов взлома. С другой стороны интересно же разгадывать шифр своего коллеги, а не мировых спецов по криптографии? Ну и если верить википедии, то у вас ARC4.
    – VladD
    24 мая 2017 в 8:19
  • @m9_psy попробуй взломай AES 2048 бит. RC4 взломаешь?
    – Alex78191
    24 мая 2017 в 16:45
7

C/C++, 222 токена (время на взлом истекло)

Little-endian 256-bit hash на основе широко известного 32-bit Murmur

#include <stdio.h>
#include <stdint.h>
#include <string.h>

static inline void
step (uint32_t *h, uint8_t c) // MurmurOAAT
{
  (*h) ^= c;
  (*h) *= 0x5bd1e995;
  (*h) ^= ((*h) >> 15);
}

// 256-bit hash
int
pass (const char *p)
{
  uint32_t hash[8] = {0};
  uint64_t res[4] = {0x56ba9b8ecd0060fd, 0xbb746d2bb6e93110,
                     0x15313f6bdc32584e, 0xca5267ffc8a1e4b4};
  
  if (p && *p) {
    int i, j = 0, l = strlen(p);
    uint8_t *d = (uint8_t *)p;
    
    for (i = 0; i < 64; i++, j++)
      step(hash + j % 8, d[i % l] + i + l);
  }

  return memcmp(hash, res, sizeof(hash));
}

int
main (int ac, char *av[])
{
  int endian = 1;
  printf("%s-endian\n", *((char *)&endian) ? "little" : "big");
  
  return puts(pass(av[1]) == 0 ? "Guess" : "Fail") == EOF;
}
6

C/C++, 104 токена (не подходит)

С/C++ little-endian

/*
  Compile: g++ passcr.c 
  Test:    ./a.out [password-to-guess]
 */
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <math.h>

// Returns 0 - false, 1 - OK
int
pass (const char *p)
{
  double hash[2] = {2.87, 3.62};
  uint64_t result[2] = {0xc037bb81ea8b2770, 0x3fc8e0d99aef179d};

  while (p && *p) 
    hash[0] -= (hash[1] += ((hash[1] * hash[0]) / ((double)(*p++))));

  return memcmp(hash, result, sizeof(hash));
}

int
main (int ac, char *av[])
{
  int endian = 1;
  printf("%s-endian\n", *((char *)&endian) ? "little" : "big");

  return puts(pass(av[1]) == 0 ? "Guess" : "Fail") == EOF;
}
17
  • 1
    Математику ж мы запретили?
    – VladD
    22 мая 2017 в 22:07
  • @VladD, в условиях так много букв, что запрет на libm я проглядел. Завтра поправлю на что-нибудь просто перемешивающее битики.
    – avp
    22 мая 2017 в 22:21
  • @VladD, как править, чтобы подходил? Просто отредактировать код в вопросе, чтобы собиралось без -lm (выбросить sin())?
    – avp
    23 мая 2017 в 18:08
  • Да, например, так. Хотя если убрать синус, то не всё равно будет неправильно по правилу «Функция не должна полагаться на ... нестабильность вычислений с плавающей точкой». Т. к. сложение double'ов в языке не определено строго и зависит от опций оптимизатора, например.
    – VladD
    23 мая 2017 в 18:13
  • 2
    Смысл в том, чтобы хакеры взламывали видимый им алгоритм, а не пытались раскопать невидимый, и только потом его взламывали. Этот конкурс — алгоритмический, а не на дизассемблирование libc с машины автора вопроса.
    – VladD
    23 мая 2017 в 21:16
6

C, 144 токена (взломан)

/*
 * gcc crypt.c -o crypt
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SI sizeof(UINT)
#define SC sizeof(char)

typedef unsigned int UINT;
typedef unsigned char BYTE;
typedef const char * CSTR;

UINT check(CSTR pwd) {
    UINT m[] = {0xB38F0E32, 0x8639E96A, 0x35B6E758, 0}, s = m[2], t, * c;
    while (*pwd) {
        c = m;
        t = *((UINT *)pwd);
        while (*c) t ^= *c++;
        s ^= t;
        s = s << 8 | s >> ((SI << 3) - 8);
        pwd += SI;
    }
    return s;
}

int main(int argc, char ** argv) {
    if (argc < 2) {
        printf("Usage: %s string\n", argv[0]);
        return 2;
    }
    UINT s = strlen(argv[1]), a = s % SI ? 1 : 0;
    char * pwd = calloc(s / SI * (SI + a) + 1, SC); // to prevent segfault
    memcpy(pwd, argv[1], s);
    printf("Result: %s\n", check(pwd) == 0x7720AEAA ? "OK" : "FAIL");
    return 0;
}

Взломан @pavel, ссылка.

6

C, 57 токенов (взломан)

Довольно простой алгоритм.

int f(wchar_t* s)
{
    uint64_t h = 0;
    if (wcslen(s) < 60) return 0;
    for (uint64_t i = 1; *s++; h += *s*i + *(s-1) * i, i++);
    return h == 0x75F00B5;
}

Взломан @pank, ссылка.

7
  • Не умею в С, но *(s-1) - это не неопределенное поведение? При первой итерации 25 мая 2017 в 11:21
  • @Андрей, нет такого на итерации. Там пустое тело цикла.
    – Qwertiy
    25 мая 2017 в 11:26
  • @Андрей, в данном случае - нет. Строка начинает считываться со второго символа, т.к. *s++.
    – eanmos
    25 мая 2017 в 11:26
  • @Андрей, длина пароля неважна. *(s-1) - это предыдущий символ, по отношению к текущему.
    – eanmos
    25 мая 2017 в 11:31
  • "\uF152\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\u7001\u0001\u0001\u0001\u0001\u0001\u0001\u0001\u0001\u0001\u0001\u0001\u0001\u0001\u0001\u0001\u0001" 25 мая 2017 в 12:03
6

C, 301 токен (взломан)

Версия 3.

Как и обещал - работа со строками.

/*
 * gcc crypt.c -o crypt
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned char uchar;

int check(uchar * pwd) {
    uchar * a = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~";
    int d = strlen(a), i, j;
    for (i = 0, j = strlen(pwd); i < j; i++) {
        if (strchr(a, pwd[i]) == NULL) pwd[i] = a[pwd[i] % d];
        if (i > 0) pwd[i - 1] = a[(((pwd[i - 1] ^ pwd[i]) << 1) * pwd[i]) % d];
    }
    return !strcmp(pwd, "Tp9?k=HDN&nD{9 ~JzUYG3h>lF {`> K<% pm~J>y E=2B=y+<x+nf@*%kDZ;z/'WYbWOk'usw>Z");
}

int main(int argc, char ** argv) {
    if (argc < 2) {
        printf("Usage: %s string\n", argv[0]);
        return 1;
    }
    int s = strlen(argv[1]);
    uchar * pwd = calloc(s + 1, sizeof(char));
    memcpy(pwd, argv[1], s);
    printf("Result: %s\n", check(pwd) ? "OK" : "FAIL");
    free(pwd);
    return 0;
}

Взломан @Mike, ссылка.

3
  • У вас функция не возвращается bool/int, исправляйте.
    – VladD
    24 мая 2017 в 9:19
  • Упс, упустил. Поправил.
    – Vitaly
    24 мая 2017 в 10:39
  • Взлом: ru.stackoverflow.com/questions/669462/…
    – Mike
    26 мая 2017 в 12:42
6

C, 584 токена (870)

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

#include <string.h>

#define m(x, y) (x < y ? x : y)

int check(char *s)
{
    int S[64] =
        {226, 70,158,126,107, 48,154, 93,168,  8,222,222,131,241, 67,  3,
         162,176, 96,197,113,101, 76,128,139, 18, 88,137,192,232,134, 34,
         108, 16,232, 71,108,233, 79,  8,241,123,200,130,  5,190,136, 27,
         164,107,  9,255,192,  8,239,125,249, 29,242, 88,216, 17,157,191};
    int A[65] = {0}, B[65], C[65] = {0}, *a = A, *b = B, *c = C, l = strlen(s), *t, i, j, k;
    char m, n, p, q;
    for (i = 0; i < 65; ++i)
        B[i] = i;
    for (i = 1, m = 0; i <= 64; ++i, m = p, t = c, c = b, b = a, a = t) {
        for (j = 1, n = 0, p = S[i-1], *a = *b + 1; j <= m(l, 64); ++j, n = q) {
            q = s[j-1];
            k = q != p;
            a[j] = m(b[j] + 1, m(a[j-1] + 1, b[j-1] + k));
            if (p == n && q == m)
                a[j] = m(a[j], c[j-2] + k);
        }
    }
    return b[l] == 8;
}
1
  • Эхм. Напомню, что это как бы гольф, и смыслом является минимальное, а не максимальное количество токенов.
    – VladD
    26 мая 2017 в 20:04
6

C/C++, 391 токен (время на взлом истекло)

Классика на хешировании

bool crypt(char *s){
    int i;
    long long m[3][9] = {1000000009LL,
                  1000000000013LL,
                    1000000000039LL,
                    999999999989LL,
                    100000000019LL,
                    100000000003LL,
                    1000000000000001LL,
                    1000000000000003LL,
                    1000000000000009LL,
                    994324858,
                  410165024251LL,
                  882143347009LL,
                  450913810178LL,
                  75177384683LL,
                  52035486628LL,
                  536516625723718LL,
                  167996437453997LL,
                  860362117327470LL };
    for (;*s;s++)
        for (i=9;~--i;)
            m[2][i] = (m[2][i] * 37 + *s)%m[0][i];
    bool r = 1;
    for (i=9;~--i;)
        r &= m[1][i]==m[2][i];
    return r;
}
4
  • Точная длина считается так: общее количество чимволов, но идентификаторы и ключевые слова схлопываются в 1 символ, и пробелы/концы строк не считаются.
    – VladD
    23 мая 2017 в 20:26
  • По этой причине переменные можно называть длинно. А можно и не называть.
    – VladD
    23 мая 2017 в 20:28
  • @VladD у вас скрипт есть или вы руками?)
    – pavel
    23 мая 2017 в 20:28
  • Замены идентификаторов просматриваю в полуавтоматическом режиме, т. к. могут быть строки, подсчёт непробельных символов скриптом.
    – VladD
    23 мая 2017 в 20:29
6

С++, 64 токена (взломан)

Вот еще один алгоритм, шуточный. Будет смешно, если его так и не взломают...

#define rot(x) ((x) << 7 | (x) >> 25)

auto check(char* str) {
    auto h = 0;
    for (; *str; str++)
        h = rot(h * 123456789) ^ *str;
    return h == -77;
}

Взломан @xirbm, ссылка.


Эх, просто нашли коллизии без всякого криптоанализа. Ну да, простой перебор тут тоже должен работать, только причина тут вовсе не в разрядности типа int.

Обратите внимание на вот это выражение: (x) >> 25. Что здесь происходит? А здесь происходит знаковый сдвиг вправо на 25 разряда. Поэтому реальная энтропия внутреннего состояния алгоритма - 7 бит вместо 32х. Неудивительно, что так быстро нашлись коллизии :-)

3
  • Зачем нужен криптоанализ в таких шуточных вещах? Если вы желаете его провести, то я могу помочь. Ибо ваше утверждение про 7 бит неверное. Прийти вам нужно не к 2(7), а к 2(6)+2(31) P.S. n(k)= n в степени k. Если бы энтропия была 7 бит, мы бы с большой вероятностью могли подобрать ответ из одного символа
    – xirbm
    30 мая 2017 в 6:45
  • @xirbm и этот символ имеет код -77 на системах, где символы - знаковые. 30 мая 2017 в 7:23
  • @xirbm если же рассматривать только ASCII-символы, то первый символ нужен чтобы получить отрицательное число на втором шаге. 30 мая 2017 в 7:37
5

Haskell, 277 токенов

f n
    | mod (2^n) 0x9fdb8b8a004544f0045f1737d0ba2e0b274cdf1a9f588218fb435316a16e374171fd19d8d8f37c39bf863fd60e3e300680a3030c6e4c3757d08f70e6aa871033 == 0x8c8050e78c71ebd1f5237b68c329213e6110eb4b8658354e8091838043047edc6d3a0fbec9461258fb75bd6a0601e1dc60c0187e9da40a784a972fb452abb2a1 = True
    | otherwise = False

main = do
         s <- getLine
         let n = read s :: Int
         print (f n) >> main
1
  • 1
    Ну опять стандартные алгоритмы из учебника, ну сколько можно?
    – VladD
    26 мая 2017 в 19:43
4

Python 2.7, ~207 токен (время на взлом истекло)

r = []

def gc_sort(a, b):
  global r
  r.append((b,a)[len(r) % 4 == 0])
  return (1,(-1,0)[a<b])[a>b]

def g_c(password):
  global r
  r = []
  list(password).sort(gc_sort)
  return ''.join(r)

def check(password):
  return g_c(password) == "yyMySMS_u_u_epeureSMaPS_sruespreoposwyosrpp_dao__So_TSeshoh_a_ernhh__STe9PMe&P9d7M&93S9&3aP763aP1&3a437659365_7311_701&_xsuwx_pswu_reada(10&*61(*_5033_4213_wuww"

Пароль: My_SuperPassowrd_Than_9&73614510xwe(*32w

Алгоритм в реализации руби был взломан. Хотя, мне кажется, если там бы был использован не qsort для сортировки, было бы не так просто. Но, на мой взгляд, идея получилась интересная.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.