Текст книги "Криптография и свобода"

Автор книги: Михаил Масленников

сообщить о нарушении

Текущая страница: 9 (всего у книги 23 страниц) [доступный отрывок для чтения: 9 страниц]

В мирное время, т.е. во времена обычных соревнований, в этом фойе дежурили две бабули – то ли администраторши, то ли билетерши. На время чемпионата мира все их контрольные функции взяло на себя КГБ, а бабули первое время сидели безо всякого дела. Но это продолжалось недолго. Вскоре они, как только куколки-чешки покидали свои автоматы, стали делать таинственные знаки и тотчас же из близлежащих кустов появлялись другие такие же бабули с трехлитровыми банками, которые бабули-агенты тащили к чешскому автомату.

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

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

Глава 4. Шифры на новой элементной базе

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

Здесь надо немного окунуться в ту «докомпьютерную» эпоху. Что такое микропроцессор – представление об этом было весьма расплывчатое. Что-то такое, что реализовано с помощью никому тогда не ведомого процессора, но только очень маленького, размером с копеечную монету. Живьем микропроцессор мало кто видел, только общие сведения: способен выполнять некоторые операции с двоичными векторами, достаточно быстро по сравнению с типовыми логическими элементами. Один раз, еще в Высшей Школе КГБ, нам, рассказывая про микропроцессоры того времени, сказали, что их стоимость сравнима со стоимостью золота, сопоставимого по весу с микропроцессором.

Сначала, как только я пришел на работу в отдел Степанова, там загорелись идеей создать специализированный криптографический процессор, ориентированный на выполнение определенных криптографических преобразований. Что это должны быть за преобразования – тоже не было единого мнения. Преобразования для системы с открытым распределением ключей? Или для симметричного шифрования, без которого система с открытым распределением ключей теряет всю свою эффективность? В общем, начальный период создания криптографического процессора прошел в абстрактных криптографических спорах, которые были спущены на грешную землю одним простым вопросом, заданным спорщикам инженером, приглашенным из Зеленоградского завода Ангстрем, на котором предполагалось изготавливать эти процессоры:

– А какой толщины должен быть слой лакового покрытия вашего процессора?

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

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

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

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

– Мы постарались придумать максимально простую для реализации криптосхему. Вы можете прикинуть оценки ее стойкости?

Ребята молодые, может быть старше меня года на 3-4. Один из них уже начальник сектора, пишет диссертацию. Эта тема – шифры на новой элементной базе – интересует многих. На 4 факультете кафедра математики подготовила два солидных отчета о проведенных исследованиях по аналогичной теме, несколько человек уже защитились. Новое, перспективное направление, что же оно из себя представляло?

Здесь я вынужден извиниться перед читателем этой книги, не имевшим ранее никаких дел с математикой. Сейчас придется немного залезть в теорию групп и теорию подстановок, со своими специфическими терминами: симметрическая группа, циклическая подстановка, свойство 2-транзитивности и т.п. Может быть неискушенный читатель пробежит эту часть «по-диагонали», не вдаваясь особо в подробности и не забивая себе в голову всех этих премудростей. Но в математике, как и в любой другой области науки, иногда удается получить красивый результат, и, чтобы оценить его красоту, надо немного вникнуть в детали, подробности, предшествующие его получению. Так что читатель, окунувшийся в начинающиеся ниже математические дебри (не такие уж и сложные, как может показаться на первый взгляд!), в конце концов будет вознагражден одной красивой «изюминкой».

Большинство традиционных электронных шифраторов реализовано с помощью «балалаек», работающих с битами. В этих «балалайках» в ячейки регистра сдвига могут быть записаны только два элемента – 0 или 1, такой регистр сдвига называется регистром сдвига над полем GF(2) – полем Галуа из двух элементов. Операции с битами тоже весьма простые: сложение и умножение по модулю 2, а также отрицание. Все методы анализа подобных «балалаек» ориентированы на двоичные операции, на операции в поле GF(2).

Если же мы вместо битов переходим к байтам, то появляется много нового. Традиционные операции с байтами можно осуществлять несколькими способами. Например, сложение и вычитание могут быть с переносом или без переноса, т.е. или это будут операции в кольце вычетов по модулю 256, или покоординатное сложение бит. Но самое интересное обобщение происходит с операцией отрицания. Отрицание (инверсия) бита – это фактически подстановка на множестве из 2 элементов. Когда всего 2 элемента, то мощность симметрической группы S₂ составляет всего 2! = 2, всего две подстановки: тривиальная единичная (ничего не меняется) и инверсия, когда 0 переходит в 1, а 1 – в 0. Мощность же симметрической группы S₂₅₆ составляет 256! – совершенно фантастическое число. Введение подстановки в регистр сдвига, работающий с байтами, а не с битами, переворачивает все привычные методы криптографического анализа. Совершенно другие операции, а следовательно, нужны и другие подходы к анализу и оценке стойкости таких схем, чем те, которые использовались в традиционных двоичных «балалайках».

С чего начала кафедра математики на 4 факультете? С самого простейшего преобразования, осуществляемого с n-мерными двоичными векторами, с преобразования типа (GП)^k, где G – группа, порожденная циклическим сдвигом (G = , g =(0,1,…,2ⁿ-1)-циклическая подстановка), П – некоторая фиксированная подстановка из S₂ⁿ, а k – некоторое целое число.

Если здесь перейти от математических терминов из теории групп к обычной криптографической терминологии, то преобразование типа (GП)^k – это следующий узел.

Преобразования типа (GП)^k – это, фактически, множество подстановок вида g_x1П g_x2П… g_xkП, и задачей кафедры математики было обосновать какие-то свойства подобного множества, найти их зависимости от подстановки П. Типичная криптографическая ситуация – когда в таком узле входное слово x₁,x₂,…x_k является ключевым параметром, требуется найти подходы к его определению по нескольким известным переходам в реализуемой подстановке.

Кафедра начала с изучения группы , т.е. группы, порожденной двумя подстановками: циклическим сдвигом g и фиксированной произвольной подстановкой П. Это естественное обобщение преобразования (GП)^k, предельный случай. Свойства группы дают ответ на вопрос, что в принципе можно ожидать от нашего преобразования при увеличении длины k до бесконечности. Можем ли мы таким путем получить все подстановки или же есть какие-то запреты?

Оказалось, что если случайно и равновероятно выбрать из всей симметрической группы фиксированную подстановку П, то с вероятностью, близкой к 1, группа будет совпадать со всей симметрической группой, т.е. запретов не будет. Те подстановки П, для которых это не так, очень часто легко определяются, например, П=g, а также любая линейная подстановка, реализующая преобразование вида П(x) = ax+b, где a и b – фиксированные элементы из Z/2ⁿ.

Дальше, естественно, стали возникать вопросы: а как скоро мы сможем достичь симметрической группы? Какова будет мощность слоя (GП)^k при некотором значении k, например, при k=2 или при k=3? При каком k множество (GП)^k станет 2-транзитивным, т.е. по имеющимся в нем подстановкам любая пара (y₁,y₂), в которой y₁<>y₂, сможет перейти в любую пару (z₁,z₂), в которой z₁<>z₂? Что в общем случае можно будет сказать про обобщение 2-транзитивности – m-транзитивность?

За свойство 2-транзитивности взялись основательно, чувствовалось, что здесь могут быть интересные криптографические зацепки: если 2-транзитивность отсутствует, то появляются запреты переходов биграмм текста, широкое поле деятельности для криптоаналитика. Например, если П – упомянутая выше линейная подстановка, то для любой пары (y₁,y₂) будет справедливо соотношение:

П(y₁)– П(y₂) = (ay₁+b) – (ay₂+b) = a(y₁-y₂)

В этом случае при применении подстановки П сохраняется соотношение между разностями знаков, а поэтому кратной транзитивности заведомо не будет.

А если П – не линейная, а произвольная подстановка? При каком минимальном значении k множество (GП)^k может достичь свойства 2-транзитивности? Всего имеется 2ⁿ(2ⁿ-1) различных пар (z₁,z₂), в которых z₁<>z₂, а количество различных подстановок в (GП)^k не превосходит (2ⁿ)^k. Следовательно, свойства 2-транзитивности можно достичь только при k>=2. Можно ли при k=2?

Рассмотрим множество подстановок (GП)². Это множество реализует всевозможные преобразования произвольного значения t в значение s по формуле s = П (П (t+x₁)+x₂) при всевозможных x₁,x₂. Если бы это множество было 2-транзитивным, то для любых заранее фиксированных s₁,s₂, t₁,t₂ , в которых s₁<>s₂ и t₁<>t₂, система уравнений:

s₁ = П (П (t₁+x₁)+x₂)

s₂ = П (П (t₂+x₁)+x₂)

имела бы решение относительно x₁,x₂, а, следовательно, поскольку П – подстановка, то и система

s₁ = П (t₁+x₁)+x₂ (1)

s₂ = П (t₂+x₁)+x₂

имела бы решение для любых заранее фиксированных s₁,s₂, t₁,t₂, в которых s₁<>s₂ и t₁<>t₂

Отсюда, вычитая одно уравнение из другого, мы приходим к одной очень важной криптографической характеристике подстановки П – матрице частот встречаемости разностей переходов ненулевых биграмм P(П) размера (2ⁿ-1)x(2ⁿ-1), а именно, на пересечении i-ой строки и j-го столбца в этой матрице стоит значение p_ij – число решений системы уравнений относительно x и y:

x-y = i (2)

П(x) – П(y) = j

где i, j <> 0.

Если при каких-то i, j <> 0 p_ij =0, то это означает, что при заранее фиксированных s₁,s₂, t₁,t₂, в которых s₁<>s₂ и t₁<>t₂, а также t₁-t₂ = i, s₁-s₂ = j, система (1) заведомо не имеет решения, ибо в противном случае имела бы решение и система (2).

Заметим, что p_ij = p₍₂ⁿ_-i)(2ⁿ_-j). Действительно, каждому решению (x₁,y₁) системы (2) можно поставить во взаимно однозначное соответствие решение (x₂,y₂)=(y₁,x₁) системы

x-y = 2ⁿ-i

П(x) – П(y) = 2ⁿ-j

если домножить на –1 оба уравнения (2).

Из системы (2) очевидно вытекает, что число ее решений равно числу значений y, при которых

П(y+i) – П(y) = j (3)

Если каждому решению (x₁,y₁) системы (2) поставить во взаимно-однозначное соответствие пару (x₂,y₂) = (П^-1(x₁),П^-1(y₁)), то такая пара будет решением системы

x-y = j (4)

П^-1(x) – П^-1(y) = i

Следовательно, число решений системы (2) будет равно числу значений y, при которых

П^-1(y+j) – П^-1(y) = i (5)

Из (3) очевидно вытекает, что сумма всех элементов p_ij в i-ой строке при любом i равна 2ⁿ. Аналогично, из (5) вытекает, что сумма всех элементов p_ij в j-ом столбце при любом j равна 2ⁿ.

Поскольку размер P(П) равен (2ⁿ-1)x(2ⁿ-1), то из условия, что сумма всех элементов p_ij в i-ой строке при любом i равна 2ⁿ следует, что если бы P(П) не содержала нулей, то в любой ее строке все элементы были бы равны 1, кроме одного, равного 2. Аналогично получаем, что в этом случае в любом столбце должны быть все элементы 1, кроме одного, равного 2.

Если при некотором y выполняется

П(y+2^n-1) – П(y) = 2^n-1, (6)

то, поскольку 2ⁿ–2^n-1 = 2^n-1, то (6) будет справедливо и при значении y₁ = y+2^n-1. Таким образом, элемент p₍₂^n-1₎₍₂^n-1₎ не может быть нечетным.

Предположим, что некоторая i-я строка целиком ненулевая. Это означает, что среди значений j_{,j1,…,j2ⁿ-1, получаемых по формуле}

j_k =П(k+i)– П(k) (7)

содержатся все ненулевые элементы из Z/2ⁿ, а какой-то один элемент встретился ровно 2 раза.

Просуммируем соотношение (7) по всем k от 0 до 2ⁿ-1. Поскольку П – подстановка, то в правой части суммы получается 0, следовательно, сумма всех значений j_k также должна быть нулевой.

Но среди j_{,j1,…,j2ⁿ-1 содержатся все ненулевые элементы из Z/2ⁿ, а какой-то один элемент встретился ровно 2 раза. Поскольку сумма (по модулю 2ⁿ) всех ненулевых элементов кольца Z/2ⁿ равна 2^n-1(2ⁿ-1) = 2^n-1, то элементом, встретившимся два раза, должно быть 2^n-1.}

Тогда, в силу свойства p_ij = p₍₂ⁿ_-i)(2ⁿ_-j) для любого значения i должно выполняться

p_i2^n-1 = p₍₂ⁿ_-i)2^n-1 = 2

и при i<>2^n-1 получается, что в 2^n-1 столбце как минимум 2 элемента равны 2. Следовательно, если некоторая i-я строка при i<>2^n-1 целиком ненулевая, то 2^n-1 столбец заведомо содержит хотя бы один нулевой элемент, т.е. множество (GП)² не является 2-транзитивным ни при какой подстановке П.

И еще отсюда сразу же вытекает, что общее число нулей в матрице P(П) не может быть меньше, чем 2ⁿ-3. В этом случае в матрице ровно две ненулевых строки, расположенных симметрично друг от друга, а в средней строке с номером 2^n-1 ровно одно нулевое значение посередине: p₍₂^n-1₎₍₂^n-1₎ = 0.

Подобными же методами легко показать, что в общем случае множество (GП)^k является 2-транзитивным при k>2 в том и только том случае, когда матрица P(П)^k-1 не содержит нулей. В частности, множество (GП)³ является 2-транзитивным тогда и только тогда, когда матрица P(П)² не содержит нулей.

Стало ясно, в каком направлении вести математические раскопки теории шифров на новой элементной базе: изучать матрицы P(П) для различных подстановок П. Здесь сразу же выделялись плохие подстановки – это линейные преобразования вида

П(x) = ax+b

В этом случае при любом фиксированном i<>0 система (2) имеет решение только при одном значении j<>0, такая матрица заведомо не будет положительной ни в какой степени и свойство 2-транзитивности недостижимо. Число нулей у такой матрицы будет максимальным.

А можно ли построить подстановки с минимально возможным числом нулей в матрице P(П)? Этот вопрос уже гораздо интереснее, простого и тривиального ответа на него нет. Пока. Но в следующих главах этой книги ситуация проясниться и в конечном итоге получится очень красивый результат.

Но это больше теоретические дебри. С точки зрения практического применения гораздо важнее знать, чего можно ожидать от матрицы P(П) при случайном и равновероятном выборе П. И здесь были доказаны очень важные теоремы о том, что в среднем ненулевых элементов в этой матрице будет примерно 2/3, что с вероятностью, близкой к 1, при случайном и равновероятном выборе П матрица P(П)² не будет содержать нулевых элементов, а группа будет совпадать с симметрической. В общем, все то, что требуется для использования подстановки П в качестве случайного разового ключа.

Вот такая была предыстория работ по шифрам на новой элементной базе. А ребята из НИИ Автоматики, по мотивам всех этих результатов, придумали следующую схему блочного шифра, работающего на основе байтового регистра сдвига и использующего только самые типовые операции с байтами, которые заложены в архитектуру появлявшихся тогда микропроцессоров. Эту схему назвали «Ангстрем-3».

В ней два регистра сдвига, работающих с байтами. В первый регистр сдвига длиной 8 байт записывается 8-байтовый блок открытого текста, во второй – ключ, или как его еще можно здесь назвать входное слово, длины Т для первого регистра. Схема крутится Т тактов, после чего заполнение первого регистра выдается в качестве 8 байтового блока шифртекста. Типичный блочный шифр, все операции сложения – в кольце Z/256, реализация – изумительно простая, если писать программу, то это буквально две-три строки.

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

– Нельзя ли выбрать Т=16?

– Нужно подумать.

Так начиналась моя осмысленная работа в Теоретическом отделе. Перед глазами – чистая тетрадь, отчеты 4 факультета и НИИ Автоматики, сиди и думай, нельзя ли выбрать Т=16.

Глава 5. Взломаем?

Итак, читатель, давай себе представим, что мы – высококвалифицированные криптоаналитики из американского АНБ. Собственный загородный трехэтажный особняк, жена-красавица, три машины, одна из которых джип для воскресных поездок к морю, ежемесячный оклад тысяч так 5-6 USD.

На этом месте мое воображение представлять что-нибудь еще просто отказывается. Так и хочется воскликнуть, немного перефразируя крылатые слова Жеглова – Высоцкого:

– Ну посмотри, какой из тебя американский криптоаналитик? У тебя же зарплата 250 рублей на лбу написана!

Так что лучше представить себе что-нибудь другое, ближе к нашей Российской действительности. Например, вот такую вот сценку, свидетелем которой мне довелось быть уже намного позже, в 1993 году в период активной работы с Центральным Банком России.

Это было вскоре после успешного внедрения системы защиты телеграфных авизо. Руководство ЦБ решило устроить селекторное совещание со всеми крупнейшими расчетно-кассовыми центрами (РКЦ) и пригласить на него разработчиков системы защиты с тем, чтобы все смогли напрямую высказать свое мнение о системе и предложения по ее совершенствованию. Но помимо системы защиты телеграфных авизо все старались воспользоваться благоприятным моментом и донести до центробанковского начальства свои заботы и печали. Так мне невольно пришлось стать свидетелем реальных будней из жизни Российской глубинки. Один момент из жизни инкассаторов (они должны были развозить секретные ключи для системы защиты авизо) запомнился особо.

– Недавно в нашем РКЦ произошло ЧП. Один из инкассаторов, будучи в нетрезвом состоянии, на спор пробил ломом бронированное лобовое стекло инкассаторской машины.

Вот это уже родное, а то какие-то американские криптографы с их роскошной жизнью! Так что давайте представим, что один советский криптограф на спор взялся взломать «Ангстрем-3» при Т=16. А другой (начальник) пообещал, что если взломает, то ему прибавят к ежемесячному окладу в 250 руб. еще 20 руб.

Здесь я еще раз хочу извиниться перед читателями за ту криптографическую рутину, которая сейчас последует. Что поделаешь: сказывается многолетняя привычка никогда и ничему не верить на слово, требовать ясных и четких доказательств. Заявлено: шифры на новой элементной базе, новое перспективное направление, математические результаты… Хватит общих слов! Нужны конкретные результаты! Что там было нового и как анализировались эти шифры? И здесь, признаюсь, началось с того, что первый пример шифра на новой элементной базе был самым тривиальным образом взломан. Так, как в этом примере.

Вот шифровка, которую надо прочитать.

D8 C7 83 EF F9 CA 71 FA 07 55 16 9B 3A 1A 99 53 87 CC 83 9D FA 1D D6 D8 35 98 FA 84 A2 57 EE 67 F2 F1 B7 63 2D AC 6C EB 76 08 38 99 B3 D5 83 A9 31 CB 5C 03 9A 2A 3C 23 8A 8F DC 62 CD 72 C5 DE 5C E2 0C 7B A8 1E B4 96 D9 77 28 30 EA CD F9 38 89 BB 30 71 08 EC 01 50 2C E0 E2 C4 2B 03 8B 30 35 C3 10 A5 86 92 B8 06 F7 F2 00 21 BF 28 4E 0A 04 67 11 07 B6 7E 7C 5D AA 25 7F 68 1B 09 F2 81 FF E4 31 A5 41 4D CA BE D1 58 85 1F 76 F3 DE 89 03 40 9D B4 00 50 29 99 EC C9 DF BB 66 86 6D CC CA 2F 0E 93 E7 2D AB 38 F3 1B AD EE 55 09 44 B3 D6 D3 CC 4F 0A 01 0D 63 78 FA 9D D4 A1 C9 84 85 CC B5 4C D4 99 5C 4D CB 2E 92 F0 29 19 7B 85 7F 7C 9E FD 63 7F 9B 95 5A 4D D7 AF A5 CD 6E 80 5F A5 B8 9E E5 C9 AB 6F 0F CD 33 46 98 6A D5 66 21 D4 E9 19 20 3E AD 03 6E F6 6D 8A 73 F6 B2 CE 60 F1 AE 87 A7 11 18 36 46 E8 C5 3A 30 9A 24 F2 65 55 8D 49 90 BD 0D F5 FD 29 D2 56 D9 D0 A9 92 22 16 76 D9 69 67 C2 B7 6A 42 CB E2 82 36 94 ED C0 91 2E A0 9D CD B0 9B FC 5C 77 15 5A C4 ED 17 54 22 22 F2 E3 26 39 A5 4A E6 91 63 7F 60 A0 F2 EA 5C 6A FF 9F D3 0F E0 63 0E 69 97 A8 05 5A 91 07 65 52 65 E0 6C DF EA EB 28 4E B4 34 FF AC B1 36 35 C8 19 DE 44 02 8B F1 50 6F CE 1C 6C 99 55 0E 2E 92 F0 29 19 7B 85 7F E8 D3 CB 3B 84 79 D7 8E 62 88 D6 2F D1 D9 2E 9F EE B1 D6 54 85 D2 65 ED 3A 73 F8 C5 90 E5 ED DB 6F B8 A2 0F 01 D6 CA B6 B7 9C B1 31 12 EA 45 48 F6 D0 D4 A2 F0 45 3B E9 AE D1 14 04 22 2C 15 FB CA 3E 58 99 14 3F 51 29 49 43 4D 95 48 FD 6C 2F ED 48 0C C9 6B F6 BC F9 5A EE 79 E9 0C 35 A2 F4 A6 C7 4E 1E B1 2B CB F9 A3 4B 30 9F 57 51 6A 90 97 72 45 90 72 95 BE 19 7B F3 D2 41 34 18 9D E1 BA 7C EF 07 35 B3 A1 D9 CF 2D 6B 80 5C F4 73 93 A8 3B 78 B5 3D 09 00 BE 85 09 B7 98 B6 74 BE 45 40 29 43 0E 92 92 C2 AA B1 50 94 AB FD CE 2D B5 8D 4E CD 35 DD 05 EA C2 6E C0 CE 45 3F 29 4D E8 49 8C D9 7B A7 D9 2A 59 C8 50 25 F3 29 29 F0 D2 27 3B BB E7 1D 7C 58 8C 7C D4 0E E2 7F 55 16 A1 89 2D A0 8D EC 82 2B C5 6B 88 2C 45 10 D9 46 55 4B 26 CC 25 21 8E 7D D7 4C CD 7C DE A5 A1 25 15 C4 52 5D 81 66 B6 6B 48 97 F2 A7 A1 8C E4 ED 39 82 E9 7C 6A AE 4A 8A 7F B0 32 43 57 F2 E4 EB 2A 13 14 51 5E CF 03 F7 02 F2 C2 38 5A 00 79 7C 04 6D 4E 50 46 E1 8D 55 9F 98 E5 04 F4 03 8F DF 28 DC 09 AB 9C C2 9C 36 24 A9 93 43 F2 C7 2C 01 EE F6 3D 63 74 EC 04 4F 2A 64 11 69 E2 F2 BE 50 F4 46 D3 6E AA CD EE F2 87 9E 6B 46 8F 27 7D B2 9A 73 4E DB 02 64 29 90 C7 00 28 A6 3F 0A 3E 06 62 C3 76 D9 BA 75 CD AC 05 3C 51 DF 7D 29 16 44 80 0C 8B DF 53 EB C0 1E 48 04 B6 40 4F 77 75 88 D0 28 76 EE 70 B6 D5 3C 44 77 AD 6C 13 55 AC 8D 15 18 C4 6B DD FF 0C 32 60 7B 52 2F B8 0E 57 E2 01 0F A5 85 C9 69 DD DC 5D D0 60 27 64 28 43 AD 11 19 B1 25 6D AF 36 F5 80 F3 CB 54 91 F0 B6 08 B8 11 FD 5C A3 C9 41 BD 70 86 27 AB 26 AB 31 BA FE F7 36 0B 06 69 8B 65 24 B0 54 6A A0 CD F9 19 CC E3 E2 77 5F F3 D5 1B 39 99 64 0A 69 F0 B4 BF E4 6D 9B B4 63 28 B1 1C DD E5 A1 B1 87 E8 83 3D 99 C2 E0 09 3C 70 96 61 7E 9E FE FA 47 CE 91 16 FF AA 11 EA 20 A1 7E 5A BB 43 47 33 0E C4 B8 34 78 EE AF 74 EF 23 81 B3 EE 47 44 05 18 2A CB 6D 4E A4 0C 2B 2F 8D 2D 93 03 3C 91 F4 48 08 50 FB DC 91 BC 5F 7B B4 C1 2F BC 81 9E FA 57 2E 20 AB 38 0D 8D 92 A0 87 6D 58 8A B6 86 DE 31 60 94 2C D7 41 8C E8 99 CA 2E 63 D8 0E 0A A4 7C 6A FB A8 76 E1 B8 A9 4F 75 41 08 CA 74 24 9C 6F D2 86 49 E4 DF D8 88 CD BC 79 AE DE 5C 1D D1 6E 23 61 FE 38 08 C1 6E 0B 4A F5 F3 75 61 95 04 D2 8A 4F 35 4F 96 D1 9F CC F7 63 33 AB D0 75 29 74 82 68 84 5A 3A 50 1A 55 D4 37 6A 9B 12 49 C9 6F 9C 2A 83 D7 12 5C 87 0D F3 AB 67 32 BF 0A 9B 9D 9E 50 74 BD BC 75 87 E9 19 21 92 C5 C6 A8 0A 0C 6F 9E D9 09 C8 1A F4 11 81 E8 A3 52 6D 06 48 FE 04 AF 31 1C 3D 51 2B 33 B5 2F 21 85 08 F4 13 C2 8D C2 C8 7B D9 0E EC D8 F5 30 C0 0E AB D8 AB ED F5 38 3D 4A E6 06 C6 84 89 4B 29 A4 B2 56 E7 FE D3 6C 82 62 3A 1F F8 93 5A 41 EC F6 4C 1C 7E 72 91 E0 67 FD 92 9A 94 B3 45 63 FC BC 6E 3B BD 41 F7 A4 DA 0E 6B 48 E1 61 5A 7A 7F 4A 50 1E 85 99 CA 8C 47 64 5A A6 1F 5C EC BF 5D 5B 12 A3 13 D6 4A 4D CC E0 AC C7 52 CA 2B E4 1F E5 76 22 9C 91 7F AF 94 21 D6 BC F1 6E CC AA AD E7 15 77 09 10 36 8A 8D F5 35 95 41 30 43 62 C8 09 46 D3 6E AA CD EE F2 87 F0 4B E2 7C DE 71 96 58 CF 24 AF 9F 57 0E 7E 97 FC 73 06 4B 91 3C 5B 12 5E D6 E7 94 E3 4B 91 C9 2E 55 FF 64 00 7F 08 36 05 0F 1C 33 BB A6 3A C2 02 FC 5F B8 B9 4B 92 ED 8A 69 CF 37 F8 2A EA E1 6A AB A4 6F AF 6E C3 D0 B8 92 39 56 C0 38 FA 07 AD 8F 21 79 4E 95 EF B5 13 A1 59 64 70 64 D1 8A 35 1D 25 F6 C6 D5 0D 01 4E FF 62 D4 D5 50 8E A4 C3 EC C1 C0 A0 0C F8 AE 11 60 DE 21 11 8C CB A1 04 F6 04 05 6F 72 4A 27 F2 3E C0 0C 39 11 61 4B F3 CA F0 E6 0A 8C 52 A3 C3 F3 F8 21 18 0B 28 AF 47 55 03 88 A4 03 D5 B6 F0 75 EB BD E2 7C 49 56 22 76 F8 1D EA B8 5B 1A 7F CE 84 00 D5 97 84 B9 74 B3 AD 3D 13 EE F2 60

Эта шифровка в ASCII-символах, т.е. в элементах по модулю 256, представленных в шестнадцатиричной записи. Известно, что она была получена с помощью схемы «Ангстрем-3» при Т=16 и известна подстановка П:

Что известно об открытом тексте? Это военная телеграмма, в которой содержится какой-то приказ. Начало телеграммы – стандартное: «Совершенно секретно. Приказ №», или в шестнадцатиричной записи соответствующих ASCII-символов

D1 EE E2 E5 F0 F8 E5 ED ED EE 20 F1 E5 EA F0 E5 F2 ED EE 2E 20 CF F0 E8 EA E0 E7 20 B9

Приступим к взлому, т.е. к определению неизвестного ключа х₁,х₂,…х₁₆, записанного во втором регистре сдвига.

Давайте сначала выпишем уравнения зашифрования, реализуемые этой схемой. Если (y₁,y₂,…,y₈) – блок, записанный в первом регистре сдвига «Ангстрем-3», то за один такт работы схемы он перейдет в блок (y₂,y₃,…,y₉), где y₉ = П(y₁+y₂+y₈+x₁), х₁ – первый байт неизвестного ключа. В общем случае, если последовательность всех заполнений первого регистра сдвига обозначить как у₁,у₂,….,у₂₃,у₂₄, где (y₁,y₂,…,y₈) – блок открытого текста, (y₁₇,y₁₈,…,y₂₄) – блок шифртекста, то для любого i>=9 будет справедливо:

y_i = П(y_i-8+y_i-7+y_i-1+x_i-8)

Преобразование блока (y_i, y_i+1,…y_i+7) в блок (y_i+1,y_i+2,…,y_i+8) за один такт обозначим как б_xi. Очевидно, что это взаимно-однозначное преобразование, поскольку П – подстановка:

б_xi (y_i, y_i+1,…y_i+7) = (y_i+1,y_i+2,…, П(y_i+y_i+1+y_i+7+x_i))

б_xi – это подстановка на множестве Z/2⁶⁴. Тогда все преобразование, осуществляемое схемой «Ангстрем-3», будет выглядеть как произведение подстановок:

б_{х1,х2,…,х16} = б_x1б_x2…б_x16

Рассмотрим преобразование Ф(у₁,у₂,…у₈) = (П (у₁), П (у₂),…, П (у₈)). Заметим, что

Ф^-1(у₁,у₂,…у₈) = (П^-1 (у₁), П^-1 (у₂),…, П^-1 (у₈)).

Имеем

Ф^-1б_{х1,х2,…,х16} Ф = Ф^-1б_x1б_x2…б_x16 Ф = Ф^-1б_x1ФФ^-1б_x2ФФ^-1_…ФФ^-1б_x16 Ф = ф_х1ф_х2…ф_х16 = ф_{х1,х2,…х16},

где ф_хi = Ф^-1б_xiФ

Если блок открытого текста (y₁,y₂,…,y₈) переходит в блок шифртекста (y₁₇,y₁₈,…,y₂₄) с помощью преобразования б_{х1,х2,…,х16}, т.е.

б_{х1,х2,…,х16}(y₁,y₂,…,y₈) = (y₁₇,y₁₈,…,y₂₄),

то

Ф^-1б_{х1,х2,…,х16}(y₁,y₂,…,y₈) = Ф^-1 (y₁₇,y₁₈,…,y₂₄) = (П^-1 (у₁₇), П^-1 (у₁₈),…, П^-1 (у₂₄)).

Тогда

(П^-1(у₁₇), П^-1(у₁₈),…, П^-1(у₂₄)) = Ф^-1б_{х1,х2,…,х16} ФФ^-1 (y₁,y₂,…,y₈) = Ф^-1б_{х1,х2,…,х16}Ф (П^-1 (у₁), П^-1 (у₂),…, П^-1 (у₈))

Итак, вот она, первая зацепка для анализа «Ангстрем-3»: заменяем позначно все буквы шифрованного и известного открытого текста по подстановке П^-1 и дальше используем вместо б_xi преобразования ф_хi. А теперь давайте посмотрим на эти преобразования повнимательнее.

ф_хi (y_i, y_i+1,…y_i+7)= Ф^-1б_xiФ(y_i, y_i+1,…y_i+7) = Ф^-1б_xi(П (y_i), П (y_i+1),… П (y_i+7)) =

Ф^-1(П(y_i+1), П(y_i+2),….,П(П(y_i)+П(y_i+1)+П(y_i+7)+х_i) = (y_i+1, y_i+2,…., П (y_i)+П (y_i+1)+П (y_i+7)+х_i)

Жизнь прекрасна и удивительна! Какие уравнения получились!

у_i+8 = П (y_i)+П (y_i+1)+П (y_i+7)+х_i

Возьмем-ка теперь парочку блоков открытого текста (y₁,y₂,…,y₈) (z₁,z₂,…,z₈) и соответствующие им блоки шифртекста (y₁₇,y₁₈,…,y₂₄) (z₁₇,z₁₈,…,z₂₄) и выпишем уравнения одни под другими…

у_i+8 = П (y_i)+П (y_i+1)+П (y_i+7)+х_i

z_i+8 = П (z_i)+П (z_i+1)+П (z_i+7)+х_i

Это же криптографический Клондайк! Вычитаем одно уравнение из другого и ключ пропадает!

u_i+8 = v_i+v_i+1+v_i+7 (1)

где u_i = y_i-z_i, v_i = П(y_i)– П(z_i).

Из (1) имеем:

v_i = u_i+8 –v_i+1-v_i+7 (2)

Линейное уравнение – мечта криптографа! Тут только надо найти все такие решения, при которых для каждой пары (u_i,v_i) соответствующий элемент р_ui,vi в матрице Р(П) был бы ненулевым. Поехали!

При Т=16 из (1) и (2) имеем:

u₁,u₂,…u₈, v₁,v₂,…v₈ – известны – это открытый текст

u₁₇,u₁₈,…u₂₄, v₁₇,v₁₈,…v₂₄ – известны – это шифртекст

Из (2) последовательно находим:

v₁₆ = u₂₄-v₁₇-v₂₃

v₁₅ = u₂₃-v₁₆-v₂₂

…………

v₉ = u₁₇-v₁₀-v₁₆

а затем уже из (1) – все u_i. Система (1) полностью решена!

Дальше – раздолье. Ключ опробуем позначно. Для первого байта ключа x₁ оставляем допустимыми только те значения, при которых пара (y₉,z₉) является решением системы

y₉-z₉ = u₉

П(y₉)– П(z₉) = v₉

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

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

1. Берем первые 24 знака известного нам открытого текста, соответствующие им знаки шифртекста и составляем две пары переходов из открытого текста в шифрованный.

Первая пара

Вторая пара

2. Все байты в этих парах заменяем по подстановке П^-1.

3. Для каждой из этих двух пар составляем и решаем систему линейных уравнений (1).

Первая пара

Открытый текст

Шифртекст

Сначала с помощью уравнений (2) вычисляем промежуточные значения v₁₆,v₁₅,…,v₉.

v₁₆ = u₂₄ – v₁₇ –v₂₃ = 03 –D1-D8 = 5A

v₁₅ = u₂₃ – v₁₆ –v₂₂ = 12 –5A-B0 = 08

v₁₄ = u₂₂ – v₁₅ –v₂₁ = 70 – 08-BF =A9

v₁₃ = u₂₁ – v₁₄ –v₂₀ = 11 – A9-54 = 14

v₁₂ = u₂₀ – v₁₃ –v₁₉ = A6 – 14 -6D = 25

v₁₁ = u₁₉ – v₁₂ –v₁₈ = 37 – 25 -72 = A0

v₁₀ = u₁₈ – v₁₁ –v₁₇ = FA – A0 -D1 = 89