Задачи по криптографии

Уважаемые друзья!

Мы открываем на нашем сайте задачник. Время от времени мы будем добавлять в него очередную задачу по криптографии или смежным областям математики. В течение месяца решения задачи будут приниматься по адресу: agievich at bsu by. Имена решивших задачу верно будут (по умолчанию) опубликованы на сайте. Ровно через месяц будет оглашаться верное решение, возможно из числа присланных.

В задачах участвуют:

Алиса. Любит разговаривать по открытым каналам связи. Забывает пароли и вложения к электронным письмам.

Боб. Любит разговаривать с Алисой. Читает «Искусство программирования» и «Искусство войны».

Трент. Ему доверяют Алиса и Боб. Делает то, что должен делать. Делает это хорошо. Не делает ничего лишнего. Надежен. Проложил к Алисе и Бобу секретные каналы связи.

Виктор. Интересуется всем. В особенности перепиской Алисы и Боба. Владеет искусством перевоплощения, практиками обфускации и таинствами конкатенации. Измеряет мощность своих компьютеров акрами.

Дополнительные персонажи будут появляться по мере развития событий.

Приступаем.

Задача № 60. Zerosum

Найти попарно различные 128-битовые слова X₁, ..., X₁₂₈ такие, что сумма

X₁ + X₂ + ... + X₁₂₈ + Belt₀(X₁) + Belt₀(X₂) + ... + Belt₀(X₁₂₈)

состоит из одних нулей. Здесь + обозначает поразрядное по модулю 2 сложение двоичных слов (XOR), Belt₀ – зашифрование Belt (СТБ 34.101.31)  на нулевом ключе. 

Дата публикации: 11.07.2017.

Решение: pdf.

Задача № 59. Размножение вирусов

Компьютер Боба заражен вирусом, который непрерывно размножается. Одну миллисекунду вновь рожденный вирус обживается, а затем каждую следующую миллисекунду производит новую копию самого себя. Все началось с одной единственнной копии. Боб обратился за помощью к Тренту, и тот нашел ошибку в программе вируса. Оказывается, что, как только количество копий станет кратно 2³², все они будут мгновенно уничтожены, и компьютер будет спасен. Стоит ли Бобу надеяться на спасение? Если да, то как долго придется ждать?

Дата публикации: 11.05.2017.

Правильно решили: М. Казловский, В. Палуха

Решение: pdf.

Задача № 58. Такт Belt

На i-м такте Belt (СТБ 34.101.31) 128-битовое слово X преобразуется в 128-битовое слово Y. Входы и выходы задаются четырьмя 32-разрядными регистрами a, b, c и d. Преобразование задается набором из семи 32-разрядных тактовых ключей:

Доказать, что для любой пары (X,Y) найдется ровно 2⁹⁶ наборов тактовых ключей, переводящих X в Y.

Дата публикации: 11.04.2017.

Решение: pdf.

Задача № 57. Отпечатки пальцев-II

Боб использует в качестве пароля случайную десятичную строку длины n. Пароль вводится на сенсорном устройстве Suxen. Виктор может разглядеть отпечатки пальцев Боба и узнать, сколько в пароле нулей, единиц, двоек и так далее. Виктор может воспользоваться наблюдениями и уменьшить число паролей, которые требуется проверить. Если, например, Виктор знает, что в пароле ровно одна единица, то ему требуется проверить не 10ⁿ, а только n 9^n-1 паролей. Во сколько раз уменьшается среднее число паролей, которые требуется проверить Виктору?

Дата публикации: 11.02.2017.

Правильно решили: В. Палуха.

Решение: pdf.

Задача № 56. 2017

Бобу требуется по заданной точке P эллиптической кривой найти 2017-кратную точку, т.е. сумму 2017 экземпляров P. В  распоряжении Боба – операции сложения, вычитания, удвоения и утроения точек. Бобу нужно организовать вычисления, затратив как можно меньше операций. Например, с помощью представления 2017 = 3⁷ - 2 * 3⁴ - 3² + 1 Боб может найти кратную точку за 11 операций: 7 утроений, 1 удвоение, 2 вычитания и 1 сложение. Можно ли еще быстрее?

Дата публикации: 11.01.2017.

Правильно решили: В. Палуха (10 операций).

Решение: pdf.

Задача № 55. Открыть все

Бобу нужно как можно быстрее открыть n замков, используя 2n ключей. Каждый ключ открывает ровно один замок, и каждый замок открывается ровно двумя ключами. Боб решил открывать замки поочередно, перебирая оставшиеся ключи. Как только ключ подошел, Боб откладывает его и переходит к следующему замку. Алиса критикует Боба. Она предлагает переходить к следующему замку только после того, как найден второй ключ от текущего замка. Алиса утверждает, что при применении ее стратегии среднее число попыток (проверок ключа в замке) будет меньше. Кто прав – Алиса или Боб?

Дополнительный вопрос (*): существуют ли стратегии с еще меньшим средним числом попыток?

Дата публикации: 11.12.2016. 

Правильно решили: В. Палуха (спасибо за подробности).

Решение: pdf.

Задача № 54. Омографическая атака

10 символов русского и английского алфавитов имеют одинаковое начертание. Это A, B, E, K, M, H, O, P, T, X. Виктор открыл агенство по регистрации имен в доменной зоне Трента. На самом деле Виктор готовится к омографической атаке. Он ищет одинаково записываемые слова (доменные имена), осмысленные и в русском, и в английских языках. Первое из найденных им слов: MOPE. Виктор собирается предложить Бобу зарегистрировать русское доменное имя и одновременно самому зарегистрировать английский зеркальный аналог. Виктор добивается того, чтобы пользователи сайта Боба вводили пароли на зеркале Виктора. Найдите как можно больше подходящих русско-английских слов, чтобы помочь Тренту составить словарь запрещенных доменных имен и тем самым защититься от атаки Виктора.

Дата публикации: 11.10.2016.

cryptographer99 (НЕ аббревиатуры, НЕ междометия, НЕ союзы, НЕ частицы):

OH OM
BAP BOP MAT MAX MOP MOT ОКА OPT POM POT TOM TOP
АTOM BATT BEEP KAMA MAMA MOPE ТАРА
MOTET TOTEM

Upd1 (23.01.2017). Трент забыл про букву C (спасибо Д. Попову за подсказку). Дополнения в словарь (спасибо cryptographer99 за программу):

AC
COM COP OCA OCT TEC
BOCK COPT COXA PACA
BACCA CAPOC MECCA

Upd2 (23.01.2017). Самое длинное слово:

TOPEPO (тореадор vs a hybrid between the tomato and the sweet pepper)

Задача № 53. Карта кодов

Алиса получила от Трента карту с 40 кодами. Каждое утро Алиса обращается к серверу Трента, и в ответ получает запрос со случайным номером кода. Алиса находит нужный код на карте и возвращает его Тренту. Если Алиса ошибается, то сервер блокируется на 3 суток. Виктор перехватывает все запросы Трента и все ответы Алисы. После n суток наблюдений, накопив n кодов (некоторые из них могут повторяться), Виктор обращается к серверу Трента от лица Алисы. Если номер кода в запросе Трента уже отправлялся, то Виктор предъявляет нужный код и получает доступ к серверу. Если же номер не отправлялся, то Виктор ошибется (код очень длинный) и сможет повторить попытку аутентификации только через 3 суток. Как Виктору выбрать n, чтобы минимизировать среднее время ожидания успеха аутентификации? 

Дата публикации: 11.07.2016.

Правильно решили: В. Палуха.

Решение: pdf.

Задача № 52. Код доступа

Замок чемодана запирается 4-значным десятичным кодом. Цифры кода задются 4 роторами. Для подбора кода Виктор поворачивает некоторый из роторов либо по часовой стрелке, либо против часовой, увеличивая либо уменьшая на 1 (по модулю 10) цифру ротора. Каждый набранный на роторах код сравнивается с истинным. В случае совпадения замок отпирается. В случае несовпадения Виктор может поворачивать роторы и дальше. Может ли Виктор гарантированно открыть замок после 9999 поворотов? Если да, то как он должен действовать. Вначале замок закрыт.

Дата публикации: 11.05.2016.

Правильно решили: В. Палуха, hellman.

Решение: pdf.

Задача № 51. А была ли ошибка?

Боб написал программу для шифровальной машины Amgine. Алиса оценила объем программы и стиль программирования Боба. Алиса утверждает, что программа содержит ошибку с вероятностью α. В ответ Боб разработал систему из n тестов. Тест номер i обнаруживает ошибку с вероятностью p_i независимо от других тестов. Все тесты прошли успешно. Какова вероятность того, что в программе все-таки есть ошибка?

Дополнительный вопрос (★): Изменятся ли выводы, если учитывать результат очередного теста сразу после его выполнения?

Задача № 50. Граф

В функции хэширования Bash план криптографического перемешивания задается специальным ориентированным графом. Это граф на 8 вершинах, из каждой  вершины выходит 3 дуги, в каждую вершину заходит 3 дуги, любые 2 вершины можно связать маршрутом длины 2, в любую вершину можно вернуться за 2 шага ровно 2 способами. Докажите, что любой подходящий граф перенумерацией вершин можно преобразовать в следующий:

Дата публикации: 11.03.2016.

Решение: pdf.

Задача № 49. L3

В функции хэширования Bash используется преобразование L3. Оно ставит в соответствие тройке 64-разрядных слов (w₀, w₁, w₂) новую тройку (W₀, W₁, W₂), в которой
    W₀ = w₀ ⊕ w₁ ⊕ w₂,
    W₁ = w₁ ⊕ w₀⁸ ⊕ W₀⁵³,
    W₂ = w₂ ⊕ w₂¹⁴ ⊕ (w₁ ⊕ W₀⁵³)¹.
Здесь w^d – результат циклического сдвига слова w на d позиций в сторону старших разрядов. Постройте алгоритм обращения L3, т. е. определения (w₀, w₁, w₂) по (W₀, W₁,  W₂). Постарайтесь использовать в алгоритме как можно меньше сложений ⊕ и сдвигов.

Дата публикации: 11.02.2016.

Решение: pdf.

Задача № 48. Биективный S-блок

Боб строит S-блок, который выполняет преобразование 16-разрядных слов с помощью следующей функции языка Си:

u16 S(u16 x) {

    static const u16 S0[256] = {...};

    static const u16 S1[256] = {...};

    register u32 y0 = S0[x & 255];

    register u32 y1 = S1[x >> 8];

    return (y0 + 1) * (y1 + 1) % 65537 - 1;

}

Найти заполнение массивов S0 и S1, при котором S-блок будет биективным.

Дата публикации: 11.01.2016.

Правильно решили: hellman.

Решение: pdf.

Задача № 47. DH-d

Пусть G – циклическая группа большого простого порядка. Трент разработал алгоритм DH-d, который по образующему g группы G и ее элементу g^x находит g^xd. Здесь d – небольшое натуральное число. Как с помощью машины DH-d решить задачу Диффи – Хеллмана: по (g, g^x, g^y) найти g^xy. Предложите решение с минимальным числом обращений к машине.

Дата публикации: 11.01.2016.

Примечание. Внеочередная задача, одна из задач олимпиады NSUCRYPTO-2015.

Решение: pdf.

Задача № 46. Шифрмашина

Шифрмашина работает с двоичной лентой, в начале которой записано входное слово длины n, а затем идут нули. Машина зашифровывает входное слово, возвращая результат на его месте. Шифрмашина может выполнять две операции:

1) менять местами любые два символа ленты;

2) применять к первым m символам ленты фиксированную подстановку S.

Ко всем входным словам применяется одна и та же последовательность операций. Эта последовательность (программа шифрмашины) определяется преобразованием зашифрования – биекцией на словах длины n. При каких условиях на S с помощью шифрмашины можно реализовать любую биекцию?

Дата публикации: 11.01.2016.

Примечание. Внеочередная задача, одна из задач олимпиады NSUCRYPTO-2015.

Решение: pdf.

Задача № 45. Имя + имя

Трент поручил Бобу наладить аутентификацию между сотрудниками его организации. Боб предложил следующее решение. Сначала все сотрудники получают у Трента общий секретный ключ K. Затем для проверки подлинности друг друга пары сотрудников обмениваются своими именами. Каждый из сотрудников проверяет, что его имя отличается от имени визави, а затем вычисляет на ключе K имитовставку от своего имени, дополненного именем визави и меткой времени. Например, Алиса для аутентификации перед Бобом вычисляет имитовставку от строки

  alicebob2015-10-07T18:10:08+03:00,

а Боб – от строки 

  bobalice2015-10-07T18:10:10+03:00.

Корректность имитовставки для некоторой метки времени в 10-секундном интервале назад доказывает подлинность противоположной стороны. Трент забраковал решение Боба. Почему?

Дата публикации: 07.10.2015.

Решение: pdf.

Задача № 44. Определить режим

Шифратор Amgine реализует алгоритмы СТБ 34.101.31. Известно, что шифрование выполняется либо в режиме сцепления блоков (CBC), либо в режиме гаммирования с обратной связью (CFB), либо в режиме счетчика (CTR). Виктору требуется определить, какой из трех режимов используется. Разрешается подать на вход шифратора два открытых текста вместе с синхропосылками и получить соответствующие шифртексты. Помогите Виктору. 

Дата публикации: 07.09.2015.

Дополнительное условие (★): синхропосылки повторять нельзя.

Правильно решили: mathematic_by^★.

Решение: pdf.

Задача № 43. 3-битовый S-блок

Боб проектирует блочную криптосистему, в которой используется следующий 3-битовый S-блок, заданный многочленами Жегалкина:

  S(x₀, x₁, x₂) =  (x₁ x₂ + x₂ +  x₀ + 1, x₀ x₂ + x₂ + x₁ + x₀, x₀ x₁ + x₂).

Помогите Бобу реализовать действие S-блока 7 логическими операциями из стандартного списка: ¬ (НЕ), ∧ (И), ∨ (ИЛИ), ⊕ (исключающее ИЛИ).

Дата публикации: 07.07.2015.

Поддержка: В. Семенов.

Правильно решили: В. Палуха, mathematic_by.

Решение: pdf.

Задача № 42. QuadDH

Пусть G – циклическая группа большого простого порядка. Трент разработал алгоритм QuadDH, который по образующему g группы G и ее элементу g^x находит g^x4. Виктор всеми силами пытается заполучить описание алгоритма. Виктор считает, что с его помощью он сможет атаковать протокол Диффи – Хеллмана: по (g, g^x, g^y) находить g^xy. Восстановите ход рассуждений Виктора.

Дата публикации: 07.06.2015.

Правильно решили: mathematic_by.

Решение: pdf.

Задача № 41. Разделить подстановку

Трент выполняет шифрование слов в алфавите A = {0, 1,..., m – 1}, m – нечетное, с помощью секретной подстановки f: символ открытого текста x при шифровании меняется на символ шифртекста f(x). Трент хочет разделить подстановку f между Алисой и Бобом. Для этого Трент находит подстановки f₁ и f₂, также действующие на A, такие, что f(x) = (f₁(x) + f₂(x)) mod m. Подстановку f₁ Трент передает Алисе, а подстановку f₂ – Бобу. Помогите Тренту выполнить разделение. Докажите, что при четном m разделение невозможно.

Дата публикации: 07.05.2015.

Решение: pdf.

Задача № 40. Вычитание

Боб продолжает разработку программ шифровальной машины Amgine. Помогите Бобу переписать следующую функцию на языке Си, реализующую вычитание из большого числа a, заданного n машинными словами, одиночного машинного слова w:  

word zzSubW(word a[], register word w, size_t n) {
  register word t;
  size_t i;
  for (i = 0; w && i < n; ++i)
    t = (a[i] < w), a[i] -= w, w = t;
  t = 0;
  return w;
}

Перепишите функцию так, чтобы в ней не было локальных переменных.

Дата публикации: 07.02.2015. 

Решение: pdf.

Задача № 39. AddRot

Боб разрабатывает алгоритм шифрования, в котором к n-битовым машинным словам применяются преобразования двух типов: Add_с – сложение слова-как-числа с числом c по модулю 2ⁿ , Rot_r – циклический сдвиг слова на r битов влево, c = 1, 2,..., 2ⁿ – 1, r = 1, 2,..., n – 1. Доказать, что с помощью сложений Add_с и сдвигов Rot_r можно реализовать любое биективное преобразование машинных слов.

Дата публикации: 11.12.2014.

Примечание. Внеочередная задача, одна из задач олимпиады NSUCRYPTO-2014.

Решение: pdf.

Задача № 38. Комбинаторный компьютер

Трент научился управлять большими ансамблями квантовых частиц и построил компьютер, который может эффективно решать различные комбинаторные задачи, например, за приемлемое время вычислять значение функции
     f(n, m, k) = |{всевозможные сочетания из m  по k частиц}| mod n.
Покажите, как с помощью компьютера Трента Боб может за приемлемое время разложить на множители большое составное число.

Дата публикации: 07.12.2014.

Решение: pdf.

Задача № 37. Группа над кольцом

Боб разрабатывает криптосистему, стойкость которой базируется на сложности решения задачи дискретного логарифмирования в группе G. Эта группа составлена из элементов кольца R, операция в G задается многочленом f(x, y) над R: x * y = f(x, y). Сколько способов выбора f  имеется у Боба?

Дата публикации: 07.10.2014.

Решение: pdf.

Задача № 36. Телефонный справочник

Трент поручил Бобу разработать интерактивный телефонный справочник. Боб написал программу, которая на запрос имя отвечает парой (имя, номер_телефона), сопровождаемой подписью Трента. Подпись доказывает, что абонент с определенным именем действительно имеет определенный номер телефона. К сожалению, Боб не учел, что справочник покрывает только часть имен. Помогите Бобу модернизировать программу так, чтобы она дополнительно возвращала доказательство отсутствия в справочнике абонента с определенным именем. Доказательство должно представлять собой структуру данных, подписанную Трентом. Трент опасается передавать Бобу личный ключ подписи, поэтому все доказательства должны быть созданы Трентом заранее, в момент формирования справочника.

Дата публикации: 07.08.2014.

Решение: pdf.

Задача № 35. Оценки на экзамене

Алиса получила на экзамене оценку a, Боб – оценку b. Оценки выставляются по 10-балльной шкале: a, b ∈ {1, 2,..., 10}. Алиса и Боб хотят сравнить свои оценки, не раскрывая их друг другу. В распоряжении Алисы и Боба есть 10 шкафов с замками и по 2 ключа от каждого замка. Помогите Алису и Бобу организовать следующие сравнения: 1) a = b? 2) a ≥  b?

Дата публикации: 07.06.2014.

Решение: pdf.

 

Задача № 34. Умножение и обращение

Умножение по простому модулю p = 2²⁵⁶ – 189, используемому в СТБ 34.101.45, выполняется за 1 мкс, а мультипликативное обращение по этому модулю – за 100 мкс. Бобу требуется написать программу, которая обрабатывает переменные X_i, Y_i ∈ {1, 2,..., p – 1} и на месте X_i возвращает X_i * Y_i^-1 mod p, i = 1, 2,..., 100. Вычисления должны быть выполнены не более чем за 500 мкс. Дополнительные переменные вводить нельзя. Помогите Бобу. 

Дата публикации: 07.04.2014.

Решение: pdf.

Задача № 33. 2014

В СТБ 34.101.31 используется умножение в поле из 2¹²⁸ элементов. Умножение обладает следующим свойством: возведение в квадрат a * a выполняется значительно быстрее, чем общее умножение a * b. Поэтому при возведении элемента a в определенную степень важно организовать вычисления так, чтобы минимизировать число общих умножений, не обращая внимания на число возведений в квадрат. Можно ли найти a²⁰¹⁴ с помощью 5 умножений? С помощью 4 умножений?

Дата публикации: 07.03.2014.

Правильно решили: Владимир Палуха.

Решение: pdf. 

Задача № 32. Координаты

На большом пустыре за штаб-квартирой Трента закопан металлический контейнер. В контейнере находится магнитная карта с ключом доступа к серверу. Тренту нужно разделить информацию о координатах контейнера между Алисой, Бобом и Глебом так, чтобы никто из них не мог найти контейнер самостоятельно, без информации от другой стороны. Сначала Трент решил сообщить сторонам уравнения различных прямых, которые пересекаются в точке размещения контейнера. При этом любая пара сторон (Алиса и Боб, Алиса и Глеб или Боб и Глеб) может определить точку пересечения своих прямых и найти контейнер.В последний момент Трент узнает, что в продаже появился мобильный программируемый металлоискатель (МПМИ), с помощью которого можно организовать поиск контейнера на любой траектории конечной длины. Используя МПМИ, Алиса (Боб или Глеб) может найти контейнер, выбрав в качестве траектории отрезок своей прямой, проходящий по пустырю. Тренту требуется разработать новую схему разделения информации о координатах контейнера между тремя сторонами, теперь располагающими МПМИ.

Дата публикации: 07.02.2014.

Решение: pdf.

Задача № 31. Поиск ключа DES

Алиса и Боб поспорили, кто из них быстрее найдет ключ DES, выбранный наудачу Трентом. Алиса и Боб разбили ключевое пространство пополам и Алиса начала проверять ключи, выполняя контрольные зашифрования и сравнивая результаты с данными, предоставленными Трентом. Алиса уже проверила половину своего ключевого сегмента и не нашла ключ, а Боб еще не начал проверку, что нарушает правила спора. Трент опасается, что спор может затянуться и указывает половину сегмента Боба, которая не содержат ключ. Трент предлагает Алисе поменяться с Бобом оставшимися у них частями сегментов. Следует ли Алисе меняться?

Дата публикации: 07.01.2014.

Решение: pdf.

Задача № 30. Централизованное тестирование

Трент поручил Алисе провести среди студентов тестирование по алгебре. Алиса подготовила очень сложную задачу, в которой требуется найти многочлен f(x) положительной степени с целыми коэффициентами. Боб предложил Алисе организовать проверку решения самими студентами. Боб написал программу, которая сравнивает найденное решение с искомым многочленом, внедренным в код программы. Алиса против проверяющей программы. Алиса опасается, что студент Виктор дизассемблирует код и восстановит f(x), не решая задачу. Помогите Бобу переписать программу так, чтобы определить по ней f(x) было вычислительно трудно.

Дата публикации: 07.12.2013.

Решение: pdf.

Задача № 29. Регулярное сложение

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

word zzAdd(word c[], const word a[], const word b[], size_t n) {
   register word carry = 0;
   register word w;
   size_t i;
   for (i = 0; i < n; ++i) {
      w = a[i] + carry;
      if (w < carry)
         c[i] = b[i];
      else
         w += b[i], carry = w < b[i], c[i] = w;
   }
   w = 0;
   return carry;
}

Функция написана на языке Си. Большие числа задаются массивами из n машинных слов. Буферы a и c, b и c либо не пересекаются, либо совпадают.

Дата публикации: 07.10.2013.

Решение: pdf.

Задача № 28. Подвесить сервер

При изучении программ поискового сервера Moctod Виктор нашел объявление переменной a:

unsigned a = 1;

Виктор выяснил, что эта переменная меняется только при обработке двух специальных поисковых запросов. При обработке запроса "Ring ring ring" переменная преобразуется следующим образом:

a = a / 2 ^ (a % 2) * 96;

а при обработке запроса "In the finite field" немного по-другому:

a ^= a / 2 ^ (a % 2) * 96;

Как только переменная a снова примет значение 1, сервер зависнет. Сможет ли Виктор подвесить сервер, выполнив 18 запросов? 19 запросов?

Дата публикации: 07.09.2013.

Решение: pdf.

Задача № 27. Секретные материалы

Активист Нед Вонс разместил в Интернет секретные материалы, зашифрованные с помощью AES-256. Каждый месяц Нед рассылает в редакции газет всего мира ключ, на котором был зашифрован очередной секретный документ, делая его содержимое общедоступным. Документы Неда производят фурор, все редакции пытаются первыми опубликовать выдержки из них. Уже второй раз подряд в газету Gnutiez приходят письма Виктора. Виктор утверждает, что умеет атаковать AES-256 и в качестве доказательства указывает первый байт следующего ключа, который будет открыт Недом. Этот прогноз каждый раз оказывается верным! В третьем письме Виктор предлагает заплатить за предсказание всех следующих ключей. Трент, который редактирует газету, отказывается платить, утверждая, что Виктор – мошенник. Почему Трент так считает?

Дата публикации: 07.08.2013.

Правильно решили: CryptoOfficer.

Решение: pdf

Задача № 26. Связь между филиалами

Компания Tenhtam является молодой и динамично развивающейся. Прием на работу в Tenhtam идет по всему миру. Для того, чтобы стать сотрудником требуется ответить всего на один вопрос: каким будет следующий элемент последовательности 4 / 10, 25 / 100, 168 / 1000, 1229 / 10000? Бобу поручено наладить защищенное взаимодействие между филиалами компании. Боб организовал в каждом филиале закрытую корпоративную сеть и установил шифровальную машину Amgine. На Amgine попадает вся исходящая корреспонденция филиала и, наоборот, Amgine доставляет сотрудникам филиала всю адресованную им корреспонденцию. Данные, передаваемые между машинами различных филиалов, зашифровываются на общем парном секретном ключе этих филиалов. Объем передаваемых данных быстро растет. Боб опасается, что Виктор, который контролирует открытые каналы связи, может накопить много шифрматериала и определить парный ключ. Поэтому каждое утро парный ключ меняется: новый парный ключ является результатом расшифрования текущей даты на старом ключе. Помогите Виктору найти парный ключ.

Дата публикации: 07.07.2013.

Правильно решили: CryptoOfficer.

Решение: pdf.

Задача № 25. PIN, PIN, PIN,…

У Боба все больше пластиковых карточек. Для каждой карточки требуется помнить PIN-код – число x от 0 до 9999. Как обычно, при трех попытках ввода неверного PIN карточка блокируется. Боб не может запомнить x наверняка. Тем не менее, при предъявлении 7 или 8 PIN-кодов конкретной карточки Боб всегда может выбрать  из них тройку, в которой обязательно окажется x. Боб решил действовать следующим образом:

1. Выбирается ключ k – натуральное число. Ключ записывается в очень защищенный блокнот.
2. PIN x зашифровывается, ему ставится в соответствие число y = (x+1)^k mod 10009. Шифртекст y сохраняется в другом, не очень защищенном блокноте.

Боб хочет организовать все так, чтобы каждому y соответствовало 7 или 8 вариантов x. Тогда Боб сможет отобрать три из них, включая правильный, и наверняка пройти аутентификацию с трех попыток. А вот Виктору, даже если он завладел двумя блокнотами, придется проверять не менее 7 вариантов. Как Боб должен выбирать k и как должно быть организовано расшифрование y?

Дата публикации: 07.06.2013.

Поправка (12.06.2013): исправлены неточности (1009 на 10009, "7 вариантов" на "7 или 8 вариантов").

Решение: pdf.

Задача № 24. Программа EulerPhi

Бобу требуется написать программу, которая определяет количество различных простых делителей заданного натурального числа n. Число n может быть очень большим, его факторизация затруднена. Однако Боб может воспользоваться программой EulerPhi, которая выполняется на суперкомпьютере Трента и за приемлемое время находит значение функции Эйлера от n. Помогите Бобу, используя следующие дополнительные данные: число простых делителей нечетно и все они имеют вид 2^s r + 1, где s – натуральное число, одинаковое для всех простых делителей, r – нечетное число.

Дата публикации: 07.05.2013.

Решение: pdf.

Задача № 23. p ± 1

Боб продолжает разрабатывать программу генерации простых чисел p >2⁵¹² для криптосистемы RSA. Для защиты от некоторых методов факторизации модуля RSA требуется генерировать такие p, что числа p ± 1 имеют максимально большие простые делители. Пусть

D(p) = (p – 1)/q₀ + (p + 1)/q₁,

где q₀ – максимальный простой делитель p – 1, q₁ – максимальный простой делитель p + 1. Какое минимальное значение может принимать величина D(p)?

Дата публикации: 07.04.2013.

Решение: pdf.

Задача № 22. Матрицы Belt

В алгоритме выработки имитовставки стандарта СТБ 34.101.31 (Belt) используются две матрицы над полем из двух элементов: 

M1 =

0 0 0 1 1 0 0 1 0 1 0 0 0 0 1 0

,

M2 =

1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0

.

Вместе с единичной матрицей M₀ они образуют множество S, которое обладает следующим свойством: сумма любого числа любых различных элементов S является обратимой матрицей. Найдите еще одну матрицу M₃, после добавления которой к S свойство останется справедливым.

Дата публикации: 07.03.2013.

Решение: pdf.

Задача № 21. Деление на малые простые

Боб разрабатывает программу генерации простых чисел для криптосистемы RSA. Первым этапом теста простоты большого натурального числа a, заданного n ≥ 8 32-разрядными словами, является проверка его делимости на малые простые val. Для этого Боб использует следующую функцию языка Си, которая находит остаток a mod val:

uint32 zzModVal(const uint32 a[], size_t n, uint32 val)
{
    uint32 r = 0;
    uint64 divisor;
    while (n--)
        divisor = r,
        divisor <<= 32,
        divisor += a[n],
        r = (uint32)(divisor % val);
    return r;
}

Для определения остатка требуется выполнить n делений uint64 % uint32 и еще 2n сложений и сдвигов. Программа Боба будет использоваться в шифровальной машине Amgine. Деление на этой машине выполняется неэффективно, в 8–10 раз медленнее умножения. Перепишите функцию zzModVal так, чтобы в ней использовалось не более 4 делений uint32 % uint32, не более 2n умножений uint32 * uint32, а суммарное число сложений и сдвигов увеличилось не более чем в 2 раза.

Дата публикации: 07.02.2013.

Поправка (05.03.2013): "... не более 2n + 2 умножений...".

Решение: pdf.

Задача № 20. Истинно-истинно случайные буквы

Трент подарил Бобу истинно-истинно случайный 6-гранный кубик, результаты бросков которого независимы и равновероятны. Бросая кубик, Боб генерирует истинно-истинно случайные буквы русского алфавита. Верно ли, что для генерации отдельной буквы (одной из 33) Боб может использовать менее √ 5  бросков кубика в среднем?

Дополнительный вопрос (∗): верно ли, что для генерации отдельной буквы английского алфавита (одной из 26) потребуется больше √ 5  бросков в среднем?

Еще один дополнительный вопрос (★): изменятся ли ответы на предыдущие вопросы при замене √ 5   на 21163 / 9721?

Дата публикации: 07.01.2013. 

Правильно решили: Владимир Палуха.

Решение: pdf.

Задача № 19. Социальная сеть

Алиса и Боб зарегистрировались в социальной сети и вошли в группу любителей рок-группы The Group. Группа секретная, все ее члены, и только они, знают секретный ключ K. Ключ используется в алгоритмах шифрования СТБ 34.101.31 (режим гаммирования с обратной связью).

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

Виктор не входит в группу, не знает K, он знает только, что Алиса и Боб уже который год разыскивают треки песен "Alice goes to France" и "Bronze goes to Bob". Виктор, в свою очередь, желает получить слова секретной песни "Navajo know". Помогите Виктору.

Дата публикации: 07.12.2012.

Правильно решили: CryptoOfficer.

Решение: pdf.

Задача № 18. Генерация простых 

Боб генерирует простые числа, используя теорему Диемитко: если q – нечетное простое, R – четное, R < 4(q + 1), n = qR + 1 и для некоторого целого a выполняются условия:

1) n делит a^qR – 1;

2) n не делит a^R – 1,

то n – простое.

Для построения простого n битовой длины k (2^{k – 1} < n < 2^k) Боб находит [k / 2]-битовое простое q (выбирает малое простое или генерирует q снова с помощью теоремы Диемитко). Затем Боб выбирает R так, что n = qR + 1 имеет нужную длину k и проверяет условия 1) и 2) для случайного a.

Алгоритм Боба содержит ошибку. Найдите составное n, которое Боб может признать простым. 

Дата публикации: 07.11.2012. 

Поправка (05.12.2012): "... Боб выбирает четное R так, что...".

Решение: pdf.

Задача № 17. Серийное производство

Трент наладил серийное производство шифровальных машин Amgine и выпустил первую серию из n машин. Производственные ресурсы Трента практически неограниченны и Виктор не может сделать никаких априорных выводов об объеме серии. Однако известно, что машины снабжены последовательными серийными номерами (от 1 до n) и выдаются абонентам в случайном порядке. Виктор узнал, что Алиса получила машину с номером 539, Боб – с номером 734, а Глеб – с номером 222. Помогите Виктору оценить n.

Дата публикации: 07.10.2012.

Подходящие оценки: CryptoOfficer.

Решение: pdf.

Задача № 16. Специальное умножение

В стандарте ЭЦП Узбекистана O'z Dst 1092:2009 используется специальное умножение x ® y = x + (1 + x R) y mod p, где p – простой модуль, R – произвольный вычет по этому модулю. Покажите, как можно найти 100-ую степень x относительно операции ®, использовав не более десяти умножений и двух сложений / вычитаний по модулю p. Разрешается проводить предвычисления с p и R.

Дата публикации: 07.09.2012.

Правильно решили: CryptoOfficer, axiomatikos.

Решение: pdf.

Задача № 15. FNV

 Функция хэширования FNV (isthe.com/chongo/tech/comp/fnv/) обрабатывает сообщение msg из size октетов следующим образом:

uint32 fnv32(const uint8* msg, size_t size)
{
  uint32 hash = 2166136261;
  while (size--)
    hash ^= *msg++,
    hash *= 16777619;
  return hash;
}

Найдите сообщение msg, которое имеет нулевое хэш-значение.

Дата публикации: 07.08.2012.

Правильно решили: CryptoOfficer.

Решение: pdf. 

Задача № 14. Матрицы

В системе связи используется протокол Диффи – Хеллмана. Выбран простой модуль p = 2¹²⁷ − 1 и найден первообразный корень g по модулю p. Алиса, Боб,... выбирают наудачу личные ключи a, b,... ∈ {1,2,..., p − 1} и записывают их на собственные сверхзащищенные носители Dractrams. Для связи друг с другом Алиса и Боб, а также другие пары абонентов, обмениваются открытыми ключами g^a, g^b и определяют общий ключ K = (g^a)^b = (g^b)^a (приведение mod p опускается). Трент обратил внимание на то, что вырабатываемый парами ключ K будет всегда одним и тем же. Это может использовать Виктор, который непрестанно прослушивает каналы связи. Абоненты понимают озабоченность Трента, но не хотят менять надежно защищенные личные ключи. Выход предложил Боб:

1. Публикуется детерминированный алгоритм, который по номеру сеанса строит матрицу M порядка 127 над полем из двух элементов. Матрица M обратима и строится как псевдослучайная.
2. Числа от 0 до 2¹²⁷ − 1 отождествляются с двоичными векторами размерности 127. Личный ключ k (как вектор) умножается на матрицу M и произведение (как число) обозначается через M(k).
3. Алиса определяет сеансовую матрицу M и посылает Бобу одноразовый открытый ключ g^M(a).
4. Боб определяет сеансовую матрицу M и посылает Алисе одноразовый открытый ключ g^M(b).
5. Алиса и Боб вычисляют общий сеансовый секретный ключ K_M = g^M(a)M(b).

Виктор утверждает, что сможет определить личные ключи Алисы и Боба, перехватив данные 130 сеансов связи. Прав ли Виктор? 

Дата публикации: 07.07.2012.

Правильно решили: CryptoOfficer. 

Решение: pdf. 

Задача № 13. Протокол аутентификации

Алиса и Боб проводят взаимную аутентификацию, которая состоит в проверке знания общего секретного ключа θ. На этом ключе стороны выполняют шифрование пар 16-байтовых блоков. Используются  алгоритмы шифрования в режиме сцепления блоков СТБ 34.101.31. При шифровании выбираются нулевые синхропосылки. Аутентификация проводится по следующему протоколу:

1. Боб выбирает случайный блок X_B и посылает его Алисе.
2. Алиса выбирает случайный блок X_A и посылает Бобу зашифрованную пару (X_A, X_B).
3. Боб выполняет расшифрование принятого сообщения, получая (X_A', X_B'), а затем сравнивает X_B' с X_B. Если блоки отличаются, то Боб завершает протокол с ошибкой. В противном случае Боб признает подлинность Алисы и отсылает ей зашифрованную пару (X_B, X_A).
4. Алиса выполняет расшифрование принятого сообщения, получая (X_B'', X_A''), а затем сравнивает X_A'' c X_A. Если блоки отличаются, то Алиса завершает протокол с ошибкой. В противном случае Алиса признает подлинность Боба.

Покажите, как Виктор, который не знает θ, может ввести Алису в заблуждение, выдав себя за Боба.

Дата публикации: 07.06.2012.

Правильно решили: CryptoOfficer, axiomatikos.

Решение: pdf.

Задача № 12. Деление многочленов

Боб реализует деление многочленов над полем из двух элементов. Многочлены задаются двоичными словами по правилам СТБ 34.101.31. Боб написал программу на языке C++, в которой многочлен,  заданный строкой октетов poly, нацело делится на многочлен g(x).

void polyDiv(uint8* poly, size_t n)
{
  uint8 a = 0;
  for (int i = 0; i < n; i++)
  {
     a ^= poly[i];
     a ^= a << 2;
     a ^= a << 4;
     poly[i] = a;
     a >>= 6;
  }
}

Найдите g(x).

Дата публикации: 07.05.2012.

Правильно решили: axiomatikos.

Решение: pdf.

Задача № 11. Умножение многочленов 

Боб реализует умножение многочленов над полем из двух элементов. Многочлены задаются двоичными словами по правилам СТБ 34.101.31. Боб утверждает, что при определенном заполнении массивов log1, log2, crt1, crt2 следующая программа на языке C++ реализует умножение многочлена a на многочлен b: 

uint16 mul8x8(uint8 a, uint8 b)
{
  static const uint8 log1[256] = {???};
  static const uint8 log2[256] = {???};
  static const uint16 crt1[256] = {???};
  static const uint16 crt2[256] = {???};

  if (a == 0 || b == 0)
    return 0;

  uint16 d1, d2;
  if (((d1 = log1[a]) += log1[b]) > 255)
    d1 -= 255;
  if (((d2 = log2[a]) += log2[b]) > 255)
    d2 -= 255;

  return crt2[d1] ^ crt1[d2];
}

Восстановите заполнение массивов.

Дата публикации: 07.04.2012.

Правильно решили: axiomatikos.

Решение: pdf.  

Задача № 10. Поиск вирусов

Боб проверяет заражение программ на своем компьютере вирусами V₁,...,V_n. Как только в проверяемой программе обнаружена сигнатура некоторого из вирусов, Боб помещает эту программу в карантин и переходит к следующей программе. Известно, что программа заражена вирусом V_i с вероятностью p_i независимо от других вирусов. Известно также, что для проверки заражения V_i требуется время t_i. В какой очередности Боб должен проверять сигнатуры вирусов, чтобы среднее время проверки было минимальным?

Дата публикации: 07.03.2012. 

Решение: pdf.

Задача № 9. Отпечатки пальцев

Боб использует в качестве пароля случайную двоичную строку длины n. Пароль вводится на сенсорном устройстве Dapi. Виктор может разглядеть отпечатки пальцев Боба и узнать, сколько в пароле единиц и сколько нулей. Виктор может воспользоваться наблюдениями и уменьшить число паролей, которые требуется проверить. Если, например, Виктор знает, что в пароле ровно одна единица, то ему требуется проверить не 2ⁿ, а только n паролей. Во сколько раз уменьшается среднее число паролей, которые требуется проверить Виктору?

Дата публикации: 07.02.2012.

Решение: pdf.

Задача № 8. Генерация ключа

Бобу требуется сгенерировать ключ, который обладает свойствами C₁,..., C_n. Боб выбирает ключ наудачу и проверяет его свойства. Как только одно из свойств не выполняется, Боб генерирует новый ключ, проверяет его и так далее, до тех пор пока не будет найден ключ, обладающий всеми свойствами. Известно, что случайный ключ обладает свойством C_i с вероятностью p_i  независимо от других свойств. Известно также, что для проверки свойства C_i требуется время t_i. В какой очередности Боб должен проверять свойства, чтобы среднее время генерации ключа было минимальным?

Дата публикации: 07.01.2012.

Правильно решили: axiomatikos.

Решение: pdf.

Задача № 7. Программа умножения

Алиса написала для Amgine программу умножения больших чисел. Программа написана на языке C:

typedef unsigned long word;
typedef unsigned long long dword;
void mul(word c[16], const word a[8], const word b[8])
{
  size_t i, j;
  word carry;
  dword mul;
  for (i = 0; i < 16; c[i++] = 0);
  for (i = 0; i < 8; ++i)
  {
    for (j = 0, carry = 0; j < 8; ++j)
      ((mul = b[i]) *= a[j]) += carry + c[i + j],
      c[i + j] = mul,
         carry = mul >> sizeof(word) * 8;
    c[i + j] = carry;
  }
}

Найдите ошибку в программе.

Дата публикации: 07.12.2011.

Правильно решили: axiomatikos.

Решение: pdf.

Задача № 6. Цифры

Трент реализовал в шифровальной машине Amgine алгоритм Digit, который берет на вход вещественное x и натуральное n, и возвращает n-й после запятой десятичный знак x. В качестве x можно использовать любое аналитически заданное выражение. Например, Digit(π, 1) = 1, Digit(π, 2) = 4. Алиса и Боб получили Amgine и решили воспользоваться еe возможностями следующим образом:

1. Стороны по секретному каналу договариваются об общем ключе k – большом натуральном числе.

2. Алиса выбирает натуральное n и вырабатывает гамму Digit(a^k, n), Digit(a^k, n + 1),..., где a = 1 + 2 cos(π / 9).

3. Символы гаммы суммируются с символами открытого текста. Полученный шифртекст отправляется вместе с n.

Виктор обрадован. Почему?

Дата публикации: 07.11.2011.

Решение: pdf.

Задача № 5. Последняя теорема Ферма

Виктор утверждает, что найденное Уайлсом доказательство последней теоремы Ферма содержит ошибку. Виктор присылает в математический журнал Selanna показатель n > 2, для которого он знает (?) решение уравнения xⁿ + yⁿ = zⁿ в натуральных числах. Трент, который редактирует журнал, просит Виктора предъявить решение. Но Виктор отказывается это сделать, предлагая Тренту сначала анонсировать его открытие. Трент находится в затруднительном положении.

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

Дата публикации: 07.10.2011.

Решение: pdf.

Задача № 4. Период последовательности

В качестве гаммы поточного шифра Алиса использует ненулевую двоичную последовательность (s_t), заданную следующим рекуррентным соотношением:

s_{t + 128} = (s_{t + 1} + 1)(s_{t + 2} + 1)...(s_{t + 127} + 1) + s_t + s_{t + 1} + s_{t + 2} + s_{t + 7}

(сложение выполняется по модулю 2). Найдите период этой последовательности.

Дата публикации: 07.09.2011.

Решение: pdf.

Задача № 3. Временной замок

Боб передает Алисе ключ K так, чтобы им можно было воспользоваться не сразу, а по истечении определенного времени. Боб выбрал простое p = 2¹²⁸ – 159 и в течение месяца рассчитывал последовательность Фибоначчи по модулю p:

F₀ = 0,  F₁ = 1,  F_n = (F_{n – 1} + F_{n – 2}) mod p,  n = 2, 3,..., 2⁶⁴ – 1.

Последний элемент последовательности Боб использовал в качестве ключа. Компьютеры Алисы уступают компьютерам Боба и поэтому Боб считает, что для определения ключа Алисе потребуется не меньше месяца. Помогите Алисе найти ключ K раньше.

Дата публикации: 07.08.2011.

Решение: pdf.

Задача № 2. Реализация Belt

Трент разрабатывает шифратор Amgine и решает использовать в шифраторе алгоритмы Belt (СТБ 34.101.31). Трент организовал реализацию алгоритмов на языке Си. Алиса написала для Трента функцию

uint32 G(uint32 x, int r);

которая выполняет преобразование G_r 32-разрядного слова x. Боб написал функцию, которая реализует такт зашифрования:

void R(uint32* a, uint32* b, uint32* c, uint32* d, const uint32* key, uint32 i)
{
  uint32 e;
  *b ^= G(*a + key[7 * i - 7 & 7], 5);
  *c ^= G(*d + key[7 * i - 6 & 7], 21);
  *a -= G(*b + key[7 * i - 5 & 7], 13);
  e = G(*b + *c + key[7 * i - 4 & 7], 21);
  *b += e;
  *c -= e;
  *d += G(*c + key[7 * i - 3 & 7], 13);
  *b ^= G(*a + key[7 * i - 2 & 7], 21);
  *c ^= G(*d + key[7 * i - 1 & 7], 5);
  e = *a, *a = *b, *b = *d, *d = *c, *c = e;
  e = 0;
}

Трента не устраивает, что в функции используется локальная переменная e. Ресурсы Amgine ограничены и на счету каждый байт стека. Помогите Бобу переписать функцию так, чтобы в ней не было локальных переменных.

Дата публикации: 07.07.2011.

Решение: pdf.

Задача № 1. Первая цифра

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

– Алиса выбирает наудачу натуральное A, не кратное 10;

– Боб выбирает наудачу натуральное B;

– в качестве цифры кода выбирается первая десятичная цифра A^B;

– A и B уничтожаются.

Виктор обрадован. Почему?

Дата публикации: 07.06.2011.

Решение: pdf.

 

---------------------------------------------------------------------

(C) Sergey Agievich [agievich@{bsu.by|gmail.com}]

---------------------------------------------------------------------