Одноразовая система шифрования

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

Одноразовая система шифрует исходный открытый текст

Х= (X0, X1,..., X_n_1)

в шифртекст

Y= (Y0, Y1,..., Yn-1)

Посредством подстановки Цезаря

Yi=(Xi + Ki)mod m, 0 < i < n,

где Ki — i-й элемент случайной ключевой последовательности.

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

Процедура расшифрования описывается соотношением

Хi = (Yi - Ki) mod m,

где Ki - i-й элемент той же самой случайной ключевой последовательности. Одноразовая система изобретена в 1917г. американцами Дж. Моборном и Г. Вернамом. Для реализации этой системы подстановки иногда используют одноразовый блокнот. Этот блокнот составлен из отрывных страниц, на каждой из которых напечатана таблица со случайными числами (ключами) Ki. Блокнот выполняется в двух экземплярах: один используется отправителем, а другой получателем. Для каждого символа Xi сообщения используется свой ключ Ki из таблицы только один раз. После того как таблица использована, она должна быть удалена из блокнота и уничтожена. Шифрование нового сообщения начинается с новой страницы.

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

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

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

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

6. Методы шифрования с симметричным ключом

Методы замены

Сущность методов замены (подстановки) заключается в замене символов исходной информации, записанных в одном алфавите, символами из другого алфавита по определенному правилу. Самым простым является метод прямой замены. Символам s0i исходного алфавита Ао, с помощью которых записывается исходная информация, однозначно ставятся в соответствие символы s1i шифрующего алфавита А1. В простейшем случае оба алфавита могут состоять из одного и того же набора символов. Например, оба алфавита могут содержать буквы русского алфавита.

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

· Алгоритм моноалфавитной замены:

Шаг 1. Формирование числового кортежа Loh путем замены каждого символа S0i € T0 (i=l,.., K), представленного в исходном алфавите Ао размера [l*R], на число h0i(s0i), соответствующее порядковому номеру символа Soi в алфавите Ао.

Шаг 2. Формирование числового кортежа L1h путем замены каждого числа кортежа Loh на соответствующее число h1i кортежа Lih, вычисляемое по формуле:

ha = (k1*hoi(soi)+k₂)(mod R),

где k1 - десятичный коэффициент; k₂ - коэффициент сдвига, выбранные коэффициенты к1, к₂ должны обеспечивать однозначное соответствие чисел h0i и h1i, а при получении h1i = 0 выполнить замену h1i = R.

Шаг 3. Получение шифртекста Т1 путём замены каждого числа h1i(s1i) кортежа L1h соответствующим символом S1i є T1 (i=1,.., K) алфавита шифрования А1 размера [1*R].

Шаг 4. Полученный шифртекст разбивается на блоки фиксированной длины b. Если последний блок оказывается неполным, то в конец блока помещаются специальные символы – заполнители (например, символ *).

Пример:

Исходными данными для шифрования являются:

Т0 = < М Е Т О Д _ Ш И Ф Р О В А Н И Я >;

А0 = < А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я _ >;

А1 = < О Р Щ Ь Я Т Э _ Ж М Ч Х А В Д Ы Ф К С Е З П И Ц Г Н Л Ъ Ш Б У Ю >;

R=32; K1=3; K2=15, b=4.

Пошаговое выполнение алгоритма шифрования приводит к получению следующих результатов:

Шаг 1. L0h = <12,6,18,14,5,32,24,9,20,16,14,3,1,13,9,31>.

Шаг 2. L1h = <19,1,5,25,30,15,23,10,11,31,25,24,18,22,10,12>.

Шаг 3. T1 = < С О Я Г Б Д И М Ч У Г Ц К П М Х >.

Шаг 4. T2 = < С О Я Г Б Д И М Ч У Г Ц К П М Х >.

При расшифровании:

· сначала устраняется разбиение на блоки. Получается непрерывный шифртекст Т1 длиной К символов.

· Расшифрование осуществляется путём решения целочисленного уравнения:

K1h0i+k2=R+h1i,

При известных целых величинах k1, k2, h1i и R величина h0i вычисляется методом перебора n.

Последовательное применение этой процедуры ко всем символам шифртекста приводит к его расшифрованию.

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

Таблица замены

Soi	А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш
h0i	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
S1i	К З Ц Л Б О Ь Э М А Ы С П Г Ъ У Р Я _ Ч В Ф Е И
h1i	18 21 24 27 30 1 4 7 10 13 16 19 22 25 28 31 2 5 8 11 14 17 20 23

Soi	Щ Ъ Ы Ь Э Ю Я _
h0i	25 26 27 28 29 30 31 32
S1i	Н Ш Ю Щ Т Ж Х Д
h1i	26 29 32 3 6 9 12 15

Использование таблицы замены значительно упрощает процесс шифрования. При шифровании символ исходного текста сравнивается с символами строки s0i таблица. Если произошло совпадение в i-м столбце, то символ исходного текста заменяется символом из строки s1i, находящегося в том же столбце i таблицы.

Расшифрование осуществляется аналогичным образом, но вход в таблицу производится по строке s1i.

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

· Методы полиалфавитной замены

Существенно более стойкими являются методы полиалфавитной замены. Такие методы основаны на использовании нескольких алфавитов для замены символов исходного текста. Формально полиалфавитную замену можно представить следующим образом. При N - алфавитной замене символ so1 из исходного алфавита Ао заменяется символом s11 из алфавита А1, S02 заменяется символом S22 из алфавита Аг и так далее. После замены Son символом S nn из An символ So(n+1) замещается символом S1 (N+1) алфавита A1и так далее.

Наибольшее распространение получил алгоритм полиалфавитной замены с использованием таблицы (матрицы) Вижинера Тв, которая представляет собой квадратную матрицу [RxR], где R - количество символов в используемом алфавите. В первой строке располагаются символы в алфавитном порядке. Начиная со второй строки, символы записываются со сдвигом влево на одну позицию. Выталкиваемые символы заполняют освобождающиеся позиции справа (циклический сдвиг). Если используется русский алфавит, то матрица Вижинера имеет размерность [32x32] (рис. 2).

АБВГД........................................................... ЪЭЮЯ_

БВГДЕ............................................................ЭЮЯ А

ВГДЕЖ...........................................................ЮЯ_АБ

_АБВГ............................................................ЫЪЭЮЯ

Рис.2. Матрица Вижинера

Шифрование осуществляется с помощью ключа, состоящего из М неповторяющихся символов. Из полной матрицы Вижинера выделяется матрица шифрования Т_ш, размерностью [(M+1),R]. Она включает первую строку и строки, первые элементы которых совпадают с символами ключа. Если в качестве ключа выбрано слово <ЗОНД>, то матрица шифрования содержит пять строк (рис. 3).

АБВГДЕЖЗИКЛМН0ПРСТУФХЦЧШЩЪЫЬЭЮЯ_

Тш = ЗИКЛМН0ПРСТУФХЦЧШЩЪЫЬЭЮЯ_АБВГДЕЖ

ОПРСТУФХЦЧШЩЪЫЬЭЮЯ_АБВГДЕЖЗИКЛМН

Я0ПРСТУФХЦЧШЩЪЫЬЭЮЯ_АБВГДЕЖЗИКЛМ

ДЕЖЗИКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ_АБВ

Рис.3. Матрица шифрования для ключа<ЗОНД>

Алгоритм зашифрования с помощью таблицы Вижинера:

Шаг 1. Выбор ключа К длиной М символов.

Шаг 2. Построение матрицы шифрования Т_ш=(Ьij) размерностью [(M+1),R] для выбранного ключа К.

Шаг 3. Под каждым символом Sor исходного текста длиной I символов размещается символ ключа k_m Ключ повторяется необходимое число раз.

Шаг 4. Символы исходного текста последовательно замещаются символами, выбираемыми из Т_ш по следующему правилу:

1) определяется символ km ключа К, соответствующий замещаемому символу s_or;

2) находится строка i в Т_ш, для которой выполняется условие k_m=bi1;

3) определяется столбец j, для которого выполняется условие:

Sor=b1j;

4) символ Sor замещается символом bij.

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

Расшифрование осуществляется в следующей последовательности:

Шаг 1. Под шифртекстом записывается последовательность символов ключа по аналогии с шагом 3 алгоритма зашифрования.

Шаг 2. Последовательно выбираются символы su из шифртекста и соответствующие символы ключа km. В матрице Тш определяется строка i, Для которой выполняется условие Km= bi1. В строке i определяется элемент bij= s1i. В расшифрованный текст на позицию г помешается символ b1j.

Шаг 3. Расшифрованный текст записывается без разделения на блоки. Убираются служебные символы.

Пример:

Требуется с помощью ключа К=< ЗОНД > зашифровать исходный текст Т=< БЕЗОБЛАЧНОЕ_НЕБО >, используя таблицу Вижинера.

Механизмы зашифрования и расшифрования представлены таким образом:

Зашифрование

Исходный текст

Ключ

Текст после замены

Шифртекст

Расшифрование

Шифртекст

Ключ

Текст после замены

Исходный текст

Методы перестановки

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

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

Криптостойкость метода зависит от длины блока (размерности матрицы). Так для блока длиной 64 символа (размерность матрицы 8x8) возможны 1,6x109 комбинаций ключа. Для блока длиной 256 символов (матрица размерностью 16x16) число возможных ключей достигает 1,4x1026. Перестановки используются также в методе, основанном на применении маршрутов Гамильтона. Этот метод реализуется путем выполнения следующих шагов:

Шаг 1. Исходная информация разбивается на блоки. Если длина шифруемой информации не кратна длине блока, то на свободные места последнего блока помещаются специальные служебные символы заполнители (например: *)

Шаг 2. Символами блока заполняется таблица, в которой для каждого порядкового номера символа в блоке отводится вполне определенное место (рис. 4).

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

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

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

Таблица Маршрут № 1 Маршрут№2

Рис. 4. Вариант 8-элементной таблицы и маршрутов Гамильтона

Из таблицы символы считываются в порядке следования номеров элементов. Ниже приводится пример шифрования информации с использованием маршрутов Гамильтона.

Пример:

Пусть требуется зашифровать исходный текст То = <МЕТОДЫ_ПЕРЕСТАНОВКИ>. Ключ и длина зашифрованных блоков соответственно равны: К=<2,1,1>, L=4. Для шифрования используются таблица и два маршрута, представленные на рис. 4. Для заданных условий маршруты с заполненными матрицами имеют вид, показанный на рис. 5.