Реализация и криптоанализ шифра гаммирования

Пример

Исходное сообщение из букв русского алфавита преобразуется в числовое сообщение заменой каждой его буквы числом по следующей таблице:

Для зашифрования полученного числового сообщения используется шифрующий отрезок последовательности A1 {\displaystyle A_1 ~ \, \!}, A2 {\displaystyle A_2 ~ \, \!},… подходящей длины, начинающийся с A100 {\displaystyle A_{100} ~ \, \!}.

При зашифровании каждое число числового сообщения складывается с соответствующим числом шифрующего отрезка. Затем вычисляется остаток от деления полученной суммы на 30, который по данной таблице заменяется буквой. Восстановите сообщение КЕНЗЭРЕ, если шифрующий отрезок взят из последовательности, у которой A1=3 {\displaystyle A_1 = 3 ~ \, \!}и Ak+1=Ak+3(k2+k−1) {\displaystyle A_{k+1}=A_k +3(k^2+k-1) ~ \, \!}для любого натурального k.

Решение:
Заметим, что Ak+1−Ak=(k+1)3−k3+2 {\displaystyle A_{k+1} — A_k = (k+1)^3-k^3+2 ~ \, \!} для всех натуральных k. Складывая почленно эти равенства при k=1,2,…,(n-1), получим An–A1=n3−3+2n {\displaystyle A_n – A_1 = n^3-3+2n ~ \, \!}. По условию A1=3 {\displaystyle A_1=3 ~ \, \!}. Следовательно, справедливо соотношение An=n3+2n {\displaystyle A_n = n^3 + 2n ~ \, \!}.
Ясно, что при расшифровании так же, как и при зашифровании, вместо чисел A100 {\displaystyle A_100 ~ \, \!}, A101 {\displaystyle A_{101} ~ \, \!}, A102 {\displaystyle A_{102} ~ \, \!}, A103 {\displaystyle A_{103} ~ \, \!}, A104 {\displaystyle A_{104} ~ \, \!}, A105 {\displaystyle A_{105} ~ \, \!}, A106 {\displaystyle A_{106} ~ \, \!} можно воспользоваться их остатками от деления на 30. Так как для каждого целого неотрицательного i:

(100+i)3+2(100+i)=i3+2i+30z {\displaystyle (100+i)^3 + 2(100+i)=i^3 + 2i + 30z ~ \, \!}
где z — некоторое целое число, то получаем следующие остатки при делении чисел A100,…,A106 {\displaystyle A_{100}, … ,A_{106} ~ \, \!} на 30:

Заключительный этап представлен в таблице:
Таблица 22. Дешифрование сообщения

Исходное сообщение: КВАДРАТ

Задача криптоанализа для шифров гаммирования

Основной задачей криптоанализа является нахождение  γ{\displaystyle ~ \gamma }

На основе априорного предположения распределения открытых текстов  P{x∈X}{\displaystyle ~ P\{x \in X \}} и распределения ключей  P{γ∈K}{\displaystyle ~ P\{\gamma \in K \}} (цель) можно вычислить распределение шифротекстов  P{y∈Y}{\displaystyle ~ P\{y \in Y \}}

 y=x+γ{\displaystyle ~y = x + \gamma }

 p{x=i}=pi{\displaystyle ~ p \{x = i\} = p_i}

 p{γ=i}=ri{\displaystyle ~ p \{\gamma = i\} = r_i}

 p{y=i}=si{\displaystyle ~ p \{y = i\} = s_i}

Рассмотрим распределение вероятностей появления различных символов в шифротексте в зависимости от символов ОТ и гаммы в векторном виде:

 p{y=i}=∑p{x=j}p{γ=i−jmodn}=∑pjri−jmodn{\displaystyle ~p \{y = i\} = \sum p\{x = j\}p\{\gamma = i-j\bmod n \} = \sum p_jr_{i-j\bmod n}}

 si=∑j=n−1pjri−jmodn{\displaystyle ~s_i = \sum_{j=0}^{n-1}p_jr_{i-j\bmod n}}

 S=PR{\displaystyle ~S = PR},

где  S{\displaystyle ~S } — вектор распределений шифротекста,

 R{\displaystyle ~R } — вектор распределений гаммы,

 P{\displaystyle ~P} — вектор распределений открытого текста.

 S=(s⋮sn−1){\displaystyle ~S = \begin{pmatrix} s_0 \\ \vdots \\ s_{n-1} \end{pmatrix}}

 R=(r⋮rn−1){\displaystyle ~R = \begin{pmatrix} r_0 \\ \vdots \\ r_{n-1} \end{pmatrix}}

 P=(ppn−1⋯p1p1ppn−1⋯p2p2p1ppn−1⋯p3⋮⋮⋮  ⋮){\displaystyle ~P = \begin{pmatrix} p_0 & p_{n-1} & \cdots & p_1 \\ p_1 & p_0 & p_{n-1} \cdots & p_2 \\ p_2 & p_1 & p_0 & p_{n-1}\cdots & p_3 \\ \vdots & \vdots & \vdots & ~~ & \vdots \end{pmatrix}}

Если  R{\displaystyle ~R} состоит из одинаковых значений, то каким бы не было  P,S=(1n⋮1n){\displaystyle ~P, S = \begin{pmatrix} \frac{1}{n} \\ \vdots \\ \frac{1}{n} \end{pmatrix}}

Режим выработки имитовставки

Основная статья: Имитовставка

Схема выработки имитовставки

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

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

Имитовставка вырабатывается для M ≥ 2 блоков открытого текста по 64 бит. Алгоритм следующий:

1. Блок открытых данных записывается в регистры N₁ и N₂, после чего подвергается преобразованию, соответствующему первым 16 циклам шифрования в режиме простой замены
2. К полученному результату побитно по модулю 2 прибавляется следующий блок открытых данных. Последний блок при необходимости дополняется нулями. Сумма также шифруется в соответствии с пунктом 1.
3. После добавления и шифрования последнего блока из результата выбирается имитовставка длиной L бит: с бита номер 32-L до 32 (отсчёт начинается с 1). Стандарт рекомендует выбирать L исходя из того, что вероятность навязывания ложных данных равна 2-L. Имитовставка передается по каналу связи после зашифрованных блоков.

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

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

Симметричное шифрование (гаммирование)

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

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

Гаммированием (gamma xoring) называется процесс «наложения» гамма-последовательности на открытые данные. Обычно это суммирование по какому-либо модулю, например, по модулю два, такое суммирование принимает вид обычного «исключающего ИЛИ» суммирования.

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

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

Пишем необходимые функции

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

Ксорим блоки гаммы и текста

Для начала определим функцию сложения блоков по модулю 2.

Здесь все просто и можно, я думаю, обойтись без пояснений.

Шифруем строку

Здесь — это функция развертывания ключей для алгоритма «Магма», а — функция шифрования блока алгоритмом «Магма» из нашей статьи о «Магме». Если для шифрования в режиме гаммирования захочешь использовать «Кузнечик», то эти две функции необходимо заменить на соответствующие функции «Кузнечика» ( и из статьи про «Кузнечик»).

На вход функции подаются:

• текущее значение инициализирующего вектора (ctr);
• открытое сообщение (in\_buf);
• указатель на буфер для зашифрованного сообщения (out\_buf);
• ключ шифрования (key);
• длина шифруемого сообщения (size).

Шифруем файл целиком

Здесь то же самое. Шифруем и расшифровываем файл одной функцией.

Здесь на вход функции подаем:

• файл-источник, содержимое которого необходимо зашифровать (src);
• файл, куда будет записано зашифрованное содержимое файла-источника (in\_buf);
• значение синхропосылки (init\_vect);
• ключ шифрования (key);
• размер шифруемого файла (size).

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

Увеличиваем значение счетчика на единицу

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

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

Удаляем ключи из памяти

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

В нашем случае функция предназначена для работы с «Магмой». Для «Кузнечика», я думаю, ты сможешь написать такую же функцию сам, если понадобится.

кХРЕПЮРСПЮ═

1. цЕПЮЯХЛЕМЙН б.ю., пЮГЛЮУМХМ л.й. «йПХОРНЦПЮТХВЕЯЙХЕ ЛЕРНДШ
   Б ЮБРНЛЮРХГХПНБЮММШУ ЯХЯРЕЛЮУ» гЮПСАЕФМЮЪ ПЮДХНЩКЕЙРПНМХЙЮ,1982,N8
2. яЪН д., йЕПП д., я.лЩДМХЙ «гЮЫХРЮ щбл»,л.,лХП,1982 — ПЮЯЯЛНРПЕМШ
   ОПЮЙРХВЕЯЙХ БЯЕ ЮЯОЕЙРШ ГЮЫХРШ ХМТНПЛЮЖХХ Б БШВХЯКХРЕКЭМШУ Х
   ЮБРНЛЮРХГХПНБЮММШУ ЯХЯРЕЛЮУ.
3. уНТТЛЮМ к.дФ. яНБПЕЛЕММШЕ ЛЕРНДШ ГЮЫХРШ ХМТНПЛЮЖХХ. л.,яНБ.ПЮДХН,
   1980 — МЮХАНКЕЕ ОНКМЮЪ Х ЯЕПЭЕГМЮЪ ЛНМНЦПЮТХЪ ОН РЕНПХХ Х ОПЮЙРХЙЕ
   ГЮЫХРШ ХМТНПЛЮЖХХ
4. дФЕТТ о.п. щКЕЙРПНМХЙЮ,1973,Р.46,N1 — ЬХТПНБЮМХЕ ДЮММШУ ЛЕРНДНЛ
   ЦЮЛЛХПНБЮМХЪ.
5. сНКЙЕП а.дФ., аКЕИЙ ъ.т. аЕГНОЮЯМНЯРЭ щбл Х НПЦЮМХГЮЖХЪ ХУ
   ГЮЫХРШ.-л.:яБЪГЭ,1980 — ПЮЯЯЛЮРПХБЮЧРЯЪ ЙПХОРНЦПЮТХВЕЯЙХЕ ЛЕРНДШ
   ГЮЫХРШ ХМТНПЛЮЖХХ, ГЮЫХРЮ ДЮММШУ Б ТЮИКЮУ ХКХ АЮГЮУ ДЮММШУ.
6. лЮМСХКЭЪЛЯ т.ф.,яКНЮМ м.дФ. рххщп,1976,Р.64,N12 — ДЕРЮКЭМН НОХЯЮМШ
   ЯОНЯНАШ ТНПЛХПНБЮМХЪ Х ЯБНИЯРБЮ ОЯЕБДНЯКСВЮИМШУ ОНЯКЕДНБЮРЕКЭМНЯРЕИ,
   ЙНРНПШЕ ХЯОНКЭГСЧРЯЪ ОПХ ЬХТПНБЮМХХ ДЮММШУ ЛЕРНДНЛ ЦЮЛЛХПНБЮМХЪ.

Алгоритм

Пусть нам дано некоторое сообщение, состоящее из n символов, включая пробел. Ключом является последовательность из некоторого числа i символов. Под открытый текст подписывается ключ

i i1 i2 i3 i4 … in {\displaystyle i_0\ i_1\ i_2\ i_3\ i_4\ …\ i_n ~\, \!}

γ γ1 γ2 γ γi−1 … γ {\displaystyle \gamma_0\ \gamma_1\ \gamma_2\ \gamma_0\ \gamma_{i-1}\ …\ \gamma_0 ~ \, \!}

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

Каждому знаку открытого текста и ключа ставится в соответствие некоторый вычет по модулю n.

Ключом является символы последовательности
Γi=(γ,γ1,γ2,…) {\displaystyle \Gamma_i = (\gamma_0 , \gamma_1 , \gamma_2, … ) ~\, \!}– ее называют гаммой. А шифртекст получается по правилу

y(t)=it+γt(modn) {\displaystyle y(t)=i_t + \gamma_t (mod n) ~ \, \!}

Гаммирование чаще осуществляется:

по модулю 2, если открытый текст представляется в виде бинарной последовательности;

по модулю 256, если открытый текст представляется в виде последовательности байтов;

по модулю 10, если открытый текст последовательность цифр.

Какие же требования должны быть предъявлены, чтобы обеспечить достаточное качество шифра?

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

2. Необходимо, чтобы соседние или близкие по расположению элементы последовательности {Γi{\displaystyle \Gamma_i}} отличались друг от друга. Было бы крайне желательно, чтобы различия между ними были в каждом позиции.

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

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

Сеть Фейстеля

Теперь мы готовы перейти к очень важной теме, которая открывает дверь в бескрайний мир современных систем шифрования. Сеть Фейстеля — это метод блочного шифрования, разработанный Хорстом Фейстелем в лаборатории IBM в 1971 году

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

Сеть Фейстеля оперирует блоками открытого текста, поэтому мы рассмотрим механизм ее работы на одном из блоков. С остальными блоками действия будут аналогичны.

• Блок разбивается на две равные части — левую (L) и правую (R).
• После разбиения левый подблок изменяется функцией f с использованием ключа K: . В качестве функции можно представить себе какое угодно преобразование — например, старый добрый шифр сдвига с ключом K.
• Полученный подблок складывается по модулю 2 с правым подблоком R, который до этого был не у дел: .
• Далее полученные части меняются местами и склеиваются.

Как видишь, все достаточно просто. Для того чтобы понять, как это работает, посмотри на схему:

Ячейка Фейстеля

Такая схема называется ячейкой Фейстеля. Сама сеть Фейстеля состоит из нескольких ячеек. Полученные на выходе первой ячейки подблоки поступают на вход второй ячейки, результирующие подблоки из второй ячейки попадают на вход третьей ячейки и так далее в зависимости от количества раундов сети Фейстеля. В каждом таком раунде применяется заранее определенный раундовый ключ. Чаще всего раундовые ключи выработаны из основного секретного ключа K. Когда все раунды будут пройдены, подблоки текста склеиваются, и получается нормальный такой шифротекст.

Теперь посмотрим работу сети Фейстеля на примере. Возьмем слово AVADAKEDAVRA и разобьем его на два блока по шесть символов — AVADAK | EDAVRA. За функцию возьмем шифр сдвига на число позиций, определенных раундовым ключом. Пусть секретный ключ . В качестве раундовых ключей возьмем . Для сложения по модулю 2 переведем текст в двоичный код согласно телеграфному алфавитику, которым вряд ли кто-то еще пользуется вообще.

Вот что получилось:

Теперь прогоним через сеть Фейстеля из двух раундов первый блок:

Прогон первого блока

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

Расшифрование осуществляется точно так же: шифротекст разбивается на блоки и затем подблоки, левый подблок поступает в функцию, складывается по модулю 2 с правым, и затем подблоки меняются местами. Отличие заключается в том, что раундовые ключи подаются в обратном порядке, то есть в нашем случае в первом раунде применим ключ K = 2, а затем во втором раунде K = 1.

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

Пример

Исходное сообщение из букв русского алфавита преобразуется в числовое сообщение заменой каждой его буквы числом по следующей таблице:

Для зашифрования полученного числового сообщения используется шифрующий отрезок последовательности A1 {\displaystyle A_1 ~ \, \!}, A2 {\displaystyle A_2 ~ \, \!},… подходящей длины, начинающийся с A100 {\displaystyle A_{100} ~ \, \!}.

При зашифровании каждое число числового сообщения складывается с соответствующим числом шифрующего отрезка. Затем вычисляется остаток от деления полученной суммы на 30, который по данной таблице заменяется буквой. Восстановите сообщение КЕНЗЭРЕ, если шифрующий отрезок взят из последовательности, у которой A1=3 {\displaystyle A_1 = 3 ~ \, \!}и Ak+1=Ak+3(k2+k−1) {\displaystyle A_{k+1}=A_k +3(k^2+k-1) ~ \, \!}для любого натурального k.

Решение:
Заметим, что Ak+1−Ak=(k+1)3−k3+2 {\displaystyle A_{k+1} — A_k = (k+1)^3-k^3+2 ~ \, \!} для всех натуральных k. Складывая почленно эти равенства при k=1,2,…,(n-1), получим An–A1=n3−3+2n {\displaystyle A_n – A_1 = n^3-3+2n ~ \, \!}. По условию A1=3 {\displaystyle A_1=3 ~ \, \!}. Следовательно, справедливо соотношение An=n3+2n {\displaystyle A_n = n^3 + 2n ~ \, \!}.
Ясно, что при расшифровании так же, как и при зашифровании, вместо чисел A100 {\displaystyle A_100 ~ \, \!}, A101 {\displaystyle A_{101} ~ \, \!}, A102 {\displaystyle A_{102} ~ \, \!}, A103 {\displaystyle A_{103} ~ \, \!}, A104 {\displaystyle A_{104} ~ \, \!}, A105 {\displaystyle A_{105} ~ \, \!}, A106 {\displaystyle A_{106} ~ \, \!} можно воспользоваться их остатками от деления на 30. Так как для каждого целого неотрицательного i:

(100+i)3+2(100+i)=i3+2i+30z {\displaystyle (100+i)^3 + 2(100+i)=i^3 + 2i + 30z ~ \, \!}
где z — некоторое целое число, то получаем следующие остатки при делении чисел A100,…,A106 {\displaystyle A_{100}, … ,A_{106} ~ \, \!} на 30:

Заключительный этап представлен в таблице:
Таблица 22. Дешифрование сообщения

Исходное сообщение: КВАДРАТ

Реализация шифра гаммирования на Python

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

Функция шифрования

На вход поступает открытый текст без пробелов, в виде массива символов, и ключ — гамму. Анализируем длину текста, «растягиваем» гамму до нужного размера и выполняем посимвольное сложение.

def encrypt(text, gamma):
    textLen = len(text)
    gammaLen = len(gamma)

    #Формируем ключевое слово(растягиваем гамму на длину текста)
    keyText = []
    for i in range(textLen // gammaLen):
        for symb in gamma:
            keyText.append(symb)
    for i in range(textLen % gammaLen):
        keyText.append(gamma)

    #Шифрование
    code = []
    for i in range(textLen):
        code.append(alphabeth) + alphabeth.index(keyText)) % 26])

    return code

Функция расшифрования

Работает аналогично. «Растягиваем» гамму и выполняем посимвольное вычитание ее из текста.

def decrypt(code, gamma):
    codeLen = len(code)
    gammaLen = len(gamma)

    #Формируем ключевое слово(растягиваем гамму на длину текста)
    keyText = []
    for i in range(codeLen // gammaLen):
        for symb in gamma:
            keyText.append(symb)
    for i in range(codeLen % gammaLen):
        keyText.append(gamma)

    #Расшифровка
    text = []
    for i in range(codeLen):
        text.append(alphabeth) - alphabeth.index(keyText) + 26) % 26]) 

    return text