Гаммирование

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 02:38, 12 июня 2016.

Источник 1

В общем виде

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

Возможны различные варианты наложения гаммы на сообщение:

TemplateExampleIcon.svg Пример Примеры
Примерами шифров гаммирования являются Шифр Цезаря, при этом у него постоянная , и Шифр Виженера


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

TemplateDifinitionIcon.svg Определение «Определение - Криптоанализ»
Криптоанализ (от греч. κρυπτός — скрытый и анализ) — наука о методах получения исходного значения зашифрованной информации, не имея доступа к секретной информации (ключу), необходимой для этого. В большинстве случаев под этим подразумевается нахождение ключа. В нетехнических терминах, криптоанализ есть взлом шифра (кода). Термин был введён американским криптографом Уильямом Ф. Фридманом в 1920 году.

Основной задачей криптоанализа является нахождение

На основе априорного предположения распределения открытых текстов и распределения ключей (цель) можно вычислить распределение шифротекстов


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

,

где - вектор распределений шифротекста,
- вектор распределений гаммы,
- вектор распределений открытого текста.

Если состоит из одинаковых значений, то каким бы не было

Cм. также

Источник 2

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

Алгоритм

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

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

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

Ключом является символы последовательности – ее называют гаммой. А шифртекст получается по правилу

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

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


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

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

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

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

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

Пример

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

Числовая замена букв
А Б В Г Д Е Ж З И К Л М Н О П
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14
Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29


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

При зашифровании каждое число числового сообщения складывается с соответствующим числом шифрующего отрезка. Затем вычисляется остаток от деления полученной суммы на 30, который по данной таблице заменяется буквой. Восстановите сообщение КЕНЗЭРЕ, если шифрующий отрезок взят из последовательности, у которой и для любого натурального k.

Решение: Заметим, что для всех натуральных k. Складывая почленно эти равенства при k=1,2,…,(n-1), получим . По условию . Следовательно, справедливо соотношение . Ясно, что при расшифровании так же, как и при зашифровании, вместо чисел , , , , , , можно воспользоваться их остатками от деления на 30. Так как для каждого целого неотрицательного i:

где z - некоторое целое число, то получаем следующие остатки при делении чисел на 30:

Остатки при делении на 30
0 3 12 3 12 15 18

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

Шифрованное сообщение К Е Н З Э Р Е
Числовое шифрованное сообщение 9 5 12 7 27 15 5
Шифрующий отрезок 0 3 12 3 12 15 18
Числовое исходное сообщение 9 2 0 4 15 0 17
Исходное сообщение К В А Д Р А Т

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

Гаммирование в ГОСТ

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

Для выработки случайных 64-битных чисел в ГОСТ 28147-89 определен специальный математический генератор, который будет рассмотрен чудь позже. Т.о. шифрование и расшифровка данных в режиме гаммирования производится путем наложения зашифрованных псевдослучайных чисел.

У этого и следующего режимов есть интересная особенность: т.к. генератор псевдослучайных чисел необходимо инициализировать начальным 64-битным значением, в качестве которого очень часто используется текущее время зашифровки, то в разное время при шифровании одного и того же массива данных под один и тот же пароль можно получить разные шифртексты! При этом значение, которым был проинициализирован генератор посылается получателю вместе с массивом зашифрованных данных и называется синхропосылкой или начальным заполнителем по терминологии ГОСТа.

ГОСТ 28147-89 определяет в качестве синхропосылки или начального заполнителя не само число, полученное из какого-либо источника (например, текущее время), а результат зашифровки этого числа по алгоритму зашифрования. Т.о. используя текущее время или что-то иное в качестве начального заполнителя необходимо это число предварительно зашифровать, а затем уже инициализировать им генератор.

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

Рекуррентный генератор последовательности чисел (РГПЧ)

Это и есть тот самый генератор чисел, который используется при шифровании гаммированием. На каждом шаге он выдает 64-битное число, которое по сути состоит из двух 32-битных чисел, которые генерируются по-отдельности. Фактически существуют два РГПЧ для старшей и младшей частей.

Числа, которые выдает РГПЧ обозначим через , где A - младшая, а B - старшая части числа. Индекс числа Q обозначает номер шага на котором числа получены, так индекс i - 1 означает предыдущий шаг. - синхропосылка или начальный заполнитель. Выработка происходит следующим образом:

, где .

, где .

Если , то .

Число B не может получиться нулевым. Константы и даны в шестнадцатеричной системе счисления.

Ссылки