Михаил Масленников - Криптография и свобода
Заметим, что pij = p(2n-i)(2n-j). Действительно, каждому решению (x1,y1) системы (2) можно поставить во взаимно однозначное соответствие решение (x2,y2)=(y1,x1) системы
x-y = 2n-i
π(x) - π(y) = 2n-j
если домножить на –1 оба уравнения (2).
Из системы (2) очевидно вытекает, что число ее решений равно числу значений y, при которых
π(y+i) - π(y) = j (3)
Если каждому решению (x1,y1) системы (2) поставить во взаимно-однозначное соответствие пару (x2,y2) = (π-1(x1),π-1(y1)), то такая пара будет решением системы
x-y = j (4)
π-1(x) - π-1(y) = i
Следовательно, число решений системы (2) будет равно числу значений y, при которых
π-1(y+j) - π-1(y) = i (5)
Из (3) очевидно вытекает, что сумма всех элементов pij в i-ой строке при любом i равна 2n. Аналогично, из (5) вытекает, что сумма всех элементов pij в j-ом столбце при любом j равна 2n.
Поскольку размер P(π) равен (2n-1)x(2n-1), то из условия, что сумма всех элементов pij в i-ой строке при любом i равна 2n следует, что если бы P(π) не содержала нулей, то в любой ее строке все элементы были бы равны 1, кроме одного, равного 2. Аналогично получаем, что в этом случае в любом столбце должны быть все элементы 1, кроме одного, равного 2.
Если при некотором y выполняется
π(y+2n-1) - π(y) = 2n-1, (6)
то, поскольку 2n–2n-1 = 2n-1, то (6) будет справедливо и при значении y1 = y+2n-1. Таким образом, элемент p(2n-1)(2n-1) не может быть нечетным.
Предположим, что некоторая i-я строка целиком ненулевая. Это означает, что среди значений j0,j1,…,j2n-1, получаемых по формуле
jk =π(k+i)- π(k) (7)
содержатся все ненулевые элементы из Z/2n, а какой-то один элемент встретился ровно 2 раза.
Просуммируем соотношение (7) по всем k от 0 до 2n-1. Поскольку π - подстановка, то в правой части суммы получается 0, следовательно, сумма всех значений jk также должна быть нулевой.
Но среди j0,j1,…,j2n-1 содержатся все ненулевые элементы из Z/2n, а какой-то один элемент встретился ровно 2 раза. Поскольку сумма (по модулю 2n) всех ненулевых элементов кольца Z/2n равна 2n-1(2n-1) = 2n-1, то элементом, встретившимся два раза, должно быть 2n-1.
Тогда, в силу свойства pij = p(2n-i)(2n-j) для любого значения i должно выполняться
pi2n-1 = p(2n-i)2n-1 = 2
и при i≠2n-1 получается, что в 2n-1 столбце как минимум 2 элемента равны 2. Следовательно, если некоторая i-я строка при i≠2n-1 целиком ненулевая, то 2n-1 столбец заведомо содержит хотя бы один нулевой элемент, т.е. множество (Gπ)2 не является 2-транзитивным ни при какой подстановке π.
И еще отсюда сразу же вытекает, что общее число нулей в матрице P(π) не может быть меньше, чем 2n-3. В этом случае в матрице ровно две ненулевых строки, расположенных симметрично друг от друга, а в средней строке с номером 2n-1 ровно одно нулевое значение посередине: p(2n-1)(2n-1) = 0.
Подобными же методами легко показать, что в общем случае множество (Gπ)k является 2-транзитивным при k>2 в том и только том случае, когда матрица P(π)k-1 не содержит нулей. В частности, множество (Gπ)3 является 2-транзитивным тогда и только тогда, когда матрица P(π)2 не содержит нулей.
Стало ясно, в каком направлении вести математические раскопки теории шифров на новой элементной базе: изучать матрицы P(π) для различных подстановок π. Здесь сразу же выделялись плохие подстановки – это линейные преобразования вида
π(x) = ax+b
В этом случае при любом фиксированном i≠0 система (2) имеет решение только при одном значении j≠0, такая матрица заведомо не будет положительной ни в какой степени и свойство 2-транзитивности недостижимо. Число нулей у такой матрицы будет максимальным.
А можно ли построить подстановки с минимально возможным числом нулей в матрице P(π)? Этот вопрос уже гораздо интереснее, простого и тривиального ответа на него нет. Пока. Но в следующих главах этой книги ситуация проясниться и в конечном итоге получится очень красивый результат.
Но это больше теоретические дебри. С точки зрения практического применения гораздо важнее знать, чего можно ожидать от матрицы P(π) при случайном и равновероятном выборе π. И здесь были доказаны очень важные теоремы о том, что в среднем ненулевых элементов в этой матрице будет примерно 2/3, что с вероятностью, близкой к 1, при случайном и равновероятном выборе π матрица P(π)2 не будет содержать нулевых элементов, а группа <g,π> будет совпадать с симметрической. В общем, все то, что требуется для использования подстановки π в качестве случайного разового ключа.
Вот такая была предыстория работ по шифрам на новой элементной базе. А ребята из НИИ Автоматики, по мотивам всех этих результатов, придумали следующую схему блочного шифра, работающего на основе байтового регистра сдвига и использующего только самые типовые операции с байтами, которые заложены в архитектуру появлявшихся тогда микропроцессоров. Эту схему назвали «Ангстрем-3».
В ней два регистра сдвига, работающих с байтами. В первый регистр сдвига длиной 8 байт записывается 8-байтовый блок открытого текста, во второй – ключ, или как его еще можно здесь назвать входное слово, длины Т для первого регистра. Схема крутится Т тактов, после чего заполнение первого регистра выдается в качестве 8 байтового блока шифртекста. Типичный блочный шифр, все операции сложения – в кольце Z/256, реализация – изумительно простая, если писать программу, то это буквально две-три строки.
Но программы будут позже, а пока, в 1980 году, эту схему предполагалось реализовывать аппаратно, с помощью типовых микропроцессоров, работающих с байтами. Идеи подстановки-ключа тоже появятся позже, первоначально предполагалосьπ выбрать и зафиксировать. А главный вопрос, который интересовал НИИ Автоматики – до какого предела можно уменьшать значение Т, количество тактов, которые должна отработать схема для зашифрования одного блока. Чем меньше Т, тем выше скорость шифрования, а это было для них определяющим фактором.
– Нельзя ли выбрать Т=16?
Нужно подумать.
Так начиналась моя осмысленная работа в Теоретическом отделе. Перед глазами - чистая тетрадь, отчеты 4 факультета и НИИ Автоматики, сиди и думай, нельзя ли выбрать Т=16.
Глава 5. Взломаем?
Итак, читатель, давай себе представим, что мы – высококвалифицированные криптоаналитики из американского АНБ. Собственный загородный трехэтажный особняк, жена-красавица, три машины, одна из которых джип для воскресных поездок к морю, ежемесячный оклад тысяч так 5 – 6 USD.
На этом месте мое воображение представлять что-нибудь еще просто отказывается. Так и хочется воскликнуть, немного перефразируя крылатые слова Жеглова – Высоцкого:
– Ну посмотри, какой из тебя американский криптоаналитик? У тебя же зарплата 250 рублей на лбу написана!
Так что лучше представить себе что-нибудь другое, ближе к нашей Российской действительности. Например, вот такую вот сценку, свидетелем которой мне довелось быть уже намного позже, в 1993 году в период активной работы с Центральным Банком России.
Это было вскоре после успешного внедрения системы защиты телеграфных авизо. Руководство ЦБ решило устроить селекторное совещание со всеми крупнейшими расчетно-кассовыми центрами (РКЦ) и пригласить на него разработчиков системы защиты с тем, чтобы все смогли напрямую высказать свое мнение о системе и предложения по ее совершенствованию. Но помимо системы защиты телеграфных авизо все старались воспользоваться благоприятным моментом и донести до центробанковского начальства свои заботы и печали. Так мне невольно пришлось стать свидетелем реальных будней из жизни Российской глубинки. Один момент из жизни инкассаторов (они должны были развозить секретные ключи для системы защиты авизо) запомнился особо.
– Недавно в нашем РКЦ произошло ЧП. Один из инкассаторов, будучи в нетрезвом состоянии, на спор пробил ломом бронированное лобовое стекло инкассаторской машины.
Вот это уже родное, а то какие-то американские криптографы с их роскошной жизнью! Так что давайте представим, что один советский криптограф на спор взялся взломать «Ангстрем-3» при Т=16. А другой (начальник) пообещал, что если взломает, то ему прибавят к ежемесячному окладу в 250 руб. еще 20 руб.
Здесь я еще раз хочу извиниться перед читателями за ту криптографическую рутину, которая сейчас последует. Что поделаешь: сказывается многолетняя привычка никогда и ничему не верить на слово, требовать ясных и четких доказательств. Заявлено: шифры на новой элементной базе, новое перспективное направление, математические результаты… Хватит общих слов! Нужны конкретные результаты! Что там было нового и как анализировались эти шифры? И здесь, признаюсь, началось с того, что первый пример шифра на новой элементной базе был самым тривиальным образом взломан. Так, как в этом примере.
