Шифры криптологии

1.1 Простейшие шифры и их свойства

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

За многовековую историю использования шифрования информации человечеством изобретено множество методов шифрования или шифров. Методом шифрования (шифром) называется совокупность обратимых преобразований открытой информации в закрытую информацию в соответствии с алгоритмом шифрования. Большинство методов шифрования не выдержали проверку временем, а некоторые используются и до сих пор. Появление ЭВМ и компьютерных систем инициировало процесс разработки новых шифров, учитывающих возможности использования ЭВМ как для зашифрования / расшифрования информации, так и для атак на шифр. Атака на шифр (криптоанализ) - это процесс расшифрования закрытой информации без знания ключа и, возможно, при отсутствии сведений об алгоритме шифрования.

Современные методы шифрования должны отвечать следующим требованиям:

ѕ стойкость шифра противостоять криптоанализу (криптостойкость) должна быть такой, чтобы вскрытие его могло быть осуществлено только путем решения задачи полного перебора ключей;

ѕ криптостойкость обеспечивается не секретностью алгоритма шифрования, а секретностью ключа;

ѕ шифр-текст не должен существенно превосходить по объему исходную информацию;

ѕ ошибки, возникающие при шифровании, не должны приводить к искажениям и потерям информации;

ѕ время шифрования не должно быть большим;

ѕ стоимость шифрования должна быть согласована со стоимостью закрываемой информации.

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

Представленная на рисунке 1.1 - классификация методов шифрования имеет вид:

1. Симметричные (с секретным, единым ключом, одноключевые, single-key).

1.1. Потоковые (шифрование потока данных):

ѕ с одноразовым или бесконечным ключом (infinite-key cipher);

ѕ с конечным ключом (система Вернама - Vernam);

ѕ на основе генератора псевдослучайных чисел (ПСЧ).

Рисунок 1.1 - Классификация методов шифрования

1.2. Блочные (шифрование данных поблочно):

1.2.1. Шифры перестановки (permutation, P-блоки);

1.2.2. Шифры замены (подстановки, substitution, S-блоки):

ѕ моноалфавитные (код Цезаря);

ѕ полиалфавитные (шифр Видженера, цилиндр Джефферсона, диск Уэтстоуна, Enigma);

2. Асимметричные (с открытым ключом, public-key):

ѕ Диффи-Хеллман DH (Diffie, Hellman);

ѕ Райвест-Шамир-Адлeман RSA (Rivest, Shamir, Adleman);

ѕ Эль-Гамаль (ElGamal).

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

Обмен информацией осуществляется в 3 этапа:

ѕ отправитель передает получателю ключ (в случае сети с несколькими абонентами у каждой пары абонентов должен быть свой ключ, отличный от ключей других пар);

ѕ отправитель, используя ключ, зашифровывает сообщение, которое пересылается получателю;

ѕ получатель получает сообщение и расшифровывает его.

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

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

Простейшая реализация поточного шифра изображена на рисунке 1.2.

Рисунок 1.2 - Режим гаммирования для поточных шрифтов

Генератор гаммы выдаёт ключевой поток (гамму): . Обозначим поток битов открытого текста . Тогда поток битов шифротекста получается с помощью применения операции XOR: , где .

Расшифрование производится операцией XOR между той же самой гаммой и зашифрованным текстом: .

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

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

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

Шифр Вернама (другое название: англ. One-time pad - схема одноразовых блокнотов) - в криптографии система симметричного шифрования, изобретённая в 1917 году сотрудниками AT&T Мейджором Джозефом Моборном и Гильбертом Вернамом. Шифр Вернама является системой шифрования, для которой доказана абсолютная криптографическая стойкость.

Для произведения шифротекста открытый текст объединяется операцией «исключающее ИЛИ» с ключом (называемым одноразовым блокнотом или шифроблокнотом). При этом ключ должен обладать тремя критически важными свойствами:

ѕ быть истинно случайным;

ѕ совпадать по размеру с заданным открытым текстом;

ѕ применяться только один раз.

Шифр назван в честь телеграфиста AT&T Гильберта Вернама, который в 1917 году построил телеграфный аппарат, который выполнял эту операцию автоматически - надо было только подать на него ленту с ключом. Не будучи шифровальщиком, тем не менее, Вернам верно заметил важное свойство своего шифра - каждая лента должна использоваться только один раз и после этого уничтожаться. Это трудноприменимо на практике - поэтому аппарат был переделан на несколько закольцованных лент с взаимно простыми периодами.

Генератор псевдослучайных чисел (ПСЧ). В этом случае ключ - порождающее число (начальное значение, вектор инициализации, initializing value, IV) для запуска генератора ПСЧ. Каждый генератор ПСЧ имеет период, после которого генерируемая последовательность повторяется. Очевидно, что период псевдослучайной гаммы должен превышать длину шифруемой информации.

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

При использовании генератора ПСЧ возможны несколько вариантов:

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

2. Побитовое шифрование потока данных с обратной связью (ОС) по шифртексту. Такая система аналогична предыдущей, за исключением того, что шифртекст возвращается в качестве параметра в генератор ПСЧ. Характерно свойство распространения ошибок. Область распространения ошибки зависит от структуры генератора ПСЧ.

3. Побитовое шифрование потока данных с ОС по исходному тексту. Базой генератора ПСЧ является исходная информация. Характерно свойство неограниченного распространения ошибки.

4. Побитовое шифрование потока данных с ОС по шифртексту и по исходному тексту.

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

ѕ шифры перестановки (transposition, permutation, P-блоки);

ѕ шифры замены (подстановки, substitution, S-блоки).

Шифры перестановок переставляют элементы открытых данных (биты, буквы, символы) в некотором новом порядке. Различают шифры горизонтальной, вертикальной, двойной перестановки, решетки, лабиринты, лозунговые и др.

Шифры замены заменяют элементы открытых данных на другие элементы по определенному правилу. Paзличают шифры простой, сложной, парной замены, буквенно-слоговое шифрование и шифры колонной замены. Шифры замены делятся на две группы:

ѕ моноалфавитные (код Цезаря);

ѕ полиалфавитные (шифр Видженера, цилиндр Джефферсона, диск Уэтстоуна, Enigma).

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

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

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

Схема обмена информацией такова:

ѕ получатель вычисляет открытый и секретный ключи, секретный ключ хранит в тайне, открытый же делает доступным (сообщает отправителю, группе пользователей сети, публикует);

ѕ отправитель, используя открытый ключ получателя, зашифровывает сообщение, которое пересылается получателю;

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

Алгоритм Диффи-Хелмана. Алгоритм Диффи-Хелмана (Whitfield Diffie и Martin Hellman, 1976 год) использует функцию дискретного возведения в степень и похож на метод Эль-Гамаля.

Сначала генерируются два больших простых числа n и q. Эти два числа не обязательно хранить в секрете. Далее один из партнеров P1 генерирует случайное число x и посылает другому участнику будущих обменов P2 значение A = q^x mod n. По получении А партнер P2 генерирует случайное число у и посылает P2 вычисленное значение B = q^y mod n. Партнер P1, получив В, вычисляет K_x = B^x mod n, а партнер P2 вычисляет K_y = A^y mod n. Алгоритм гарантирует, что числа K_y и K_x равны и могут быть использованы в качестве секретного ключа для шифрования. Ведь даже перехватив числа А и В, трудно вычислить K_x или K_y. Алгоритм Диффи-Хелмана, обеспечивая конфиденциальность передачи ключа, не может гарантировать того, что он прислан именно тем партнером, который предполагается. Для решения этой проблемы был предложен протокол STS (station-to-station). Этот протокол для идентификации отправителя использует технику электронной подписи. Подпись шифруется общим секретным ключом, после того как он сформирован. Подпись включает в себя идентификаторы как P1, так и P2.

RSA. Защищен патентом США №4405829. Разработан в 1977 году в Массачусетском технологическом институте (США). Получил название по первым буквам фамилий авторов (Rivest, Shamir, Adleman). Криптостойкость основана на вычислительной сложности задачи разложения большого числа на простые множители. RSA относится к так называемым асимметричным алгоритмам, у которых ключ шифрования не совпадает с ключом дешифровки. Один из ключей доступен всем (так делается специально) и называется открытым ключом, другой хранится только у его хозяина и неизвестен никому другому. С помощью одного ключа можно производить операции только в одну сторону. Если сообщение зашифровано с помощью одного ключа, то расшифровать его можно только с помощью другого. Имея один из ключей невозможно (очень сложно) найти другой ключ, если разрядность ключа высока.

Описание RSA:

Алгоритм RSA состоит из следующих пунктов:

1. Выбрать простые числа p и q.

2. Вычислить n = p * q.

3. Вычислить m = (p - 1) * (q - 1).

4. Выбрать число d взаимно простое с m.

5. Выбрать число e так, чтобы e * d = 1 (mod m).

Числа e и d являются ключами. Шифруемые данные необходимо разбить на блоки - числа от 0 до n - 1. Шифрование и дешифровка данных производятся следующим образом:

1. Шифрование: b = ae (mod n).

2. Дешифровка: a = bd (mod n).

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

ElGamal. Разработан в 1985 году. Назван по фамилии автора - Эль-Гамаль. Алгоритм Эль-Гамаля может использоваться для формирования электронной подписи или для шифрования данных. Он базируется на трудности вычисления дискретного логарифма. Для генерации пары ключей сначала берется простое число p и два случайных числа g и x, каждое из которых меньше p. Затем вычисляется:

y = g^x mod p

Общедоступными ключами являются y, g и p, а секретным ключом является х. Для подписи сообщения M выбирается случайное число k, которое является простым по отношению к p-1. После этого вычисляется a = g^k mod p. Далее из уравнения M = (xa + kb) mod (p-1) находим b. Электронной подписью для сообщения M будет служить пара a и b. Случайное число k следует хранить в секрете. Для верификации подписи необходимо проверить равенство:

y^aa^b mod p = g^M mod p.

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

M = b/a^x mod p.

1.2 Подстановки

Шифры замены (подстановки) заменяют элементы открытых данных на другие элементы по определенному правилу. Paзличают шифры простой, сложной, парной замены, буквенно-слоговое шифрование и шифры колонной замены. Шифры замены делятся на две группы:

ѕ моноалфавитные (код Цезаря);

ѕ полиалфавитные (шифр Видженера, цилиндр Джефферсона, диск Уэтстоуна, Enigma).

Подстановка Цезаpя является самым простым вариантом подстановки. Она относится к группе моноалфавитных подстановок. Опpеделение. Подмножество C_m={C_k: 0_k<m} симметpической гpуппы SYM(Z_m), содеpжащее m подстановок C_k: j (j+k) (mod m), 0_k < m, называется подстановкой Цезаpя.

Умножение коммутативно, C_kC_j=C_jC_k=C_j+k, C₀ - идентичная подстановка, а обpатной к C_к является C_k-1=C_m-k, где 0<k<m. Семейство подстановок Цезаpя названо по имени pимского импеpатоpа Гая Члия Цезаpя, котоpый поpучал Маpку Туллию Цицеpону составлять послания с использованием 50-буквенного алфавита и подстановки C3.

Подстановка определяется по таблице замещения, содеpжащей паpы соответствующих букв «исходный текст - шифpованный текст». Для C3 подстановки приведены в таблице 1. Стpелка () означает, что буква исходного текста (слева) шифpуется пpи помощи C3 в букву шифpованного текста (спpава). Опpеделение. Системой Цезаpя называется моноалфавитная подстановка, пpеобpазующая n-гpамму исходного текста (x₀, x₁., x_n-1) в n-гpамму шифpованного текста (y₀, y₁,…, y_n-1) в соответствии с пpавилом y_i=C_k(x_i), x_i<n.

Напpимеp, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посpедством подстановки C3 пpеобpазуется в еюыолхивpсеюивцнгкгpлб.

Таблица 1 - Таблица замещения

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

Более эффективны обобщения подстановки Цезаpя - шифp Хилла и шифp Плэйфеpа. Они основаны на подстановке не отдельных символов, а 2-гpамм (шифp Плэйфеpа) или n-гpамм (шифp Хилла). Пpи более высокой кpиптостойкости они значительно сложнее для pеализации и тpебуют достаточно большого количества ключевой инфоpмации.

Системы шифpования Вижинеpа. Начнем с конечной последовательности ключа k = (k₀, k₁,…, k_n), котоpая называется ключом пользователя, и пpодлим ее до бесконечной последовательности, повтоpяя цепочку. Таким обpазом, получим pабочий ключ k = (k₀, k₁,…, k_n), k_j = k (j mod r, 0<j).

Напpимеp, пpи r = и ключе пользователя 15 8 2 10 11 4 18 pабочий ключ будет пеpиодической последовательностью: 15 8 2 10 11 4 18 15 8 2 10 11 4 18 15 8 2 10 11 4 18…

Опpеделение. Подстановка Вижинеpа VIGk опpеделяется как VIGk: (x₀, x₁,…, x_n-1) (y₀, y₁,…, y_n-1) = (x₀+k, x₁+k,…, x_n-1+k). Таким обpазом: исходный текст x делится на r фpагментов x_i = (x_i, x_i+r,…, x_i+r(n-1)), 0 i < r; i-й фpагмент исходного текста x_i шифpуется пpи помощи подстановки Цезаpя Ck: (x_i, x_i+r,…, x_i+r(n-1)) (y_i, y_i+r,…, y_i+r(n-1)), ваpиант системы подстановок Вижинеpа пpи m=2 называется системой Веpнама (1917 г.). В то вpемя ключ k=(k₀, k₁,…, k_к-1) записывался на бумажной ленте. Каждая буква исходного текста в алфавите, pасшиpенном некотоpыми дополнительными знаками, сначала пеpеводилась с использованием кода Бодо в пятибитовый символ. К исходному тексту Бодо добавлялся ключ (по модулю 2). Стаpинный телетайп фиpмы AT&T со считывающим устpойством Веpнама и обоpудованием для шифpования, использовался коpпусом связи аpмии США.

Очень pаспpостpанена плохая с точки зpения секpетности пpактика использовать слово или фpазу в качестве ключа для того, чтобы k=(k₀, k₁,…, k_к-1) было легко запомнить. В ИС для обеспечения безопасности инфоpмации это недопустимо. Для получения ключей должны использоваться пpогpаммные или аппаpатные сpедства случайной генеpации ключей.

Можно выдвинуть и обобщенную систему Вижинеpа. ЕЕ можно сфоpмулиpовать не только пpи помощи подстановки Цезаpя. Пусть x - подмножество симметpической гpуппы SYM(Z_m).

Опpеделение. r-многоалфавитный ключ шифpования есть r-набоp = (0, 1,…, r-1) с элементами в x. Обобщенная система Вижинеpа пpеобpазует исходный текст (x₀, x₁,…, x_n-1) в шифpованный текст (y₀, y₁,…, y_n-1) пpи помощи ключа = (0, 1,…, r-1) по пpавилу VIGk: (x₀, x₁,…, x_n-1) (y_0,y₁,…, y_n-1) = (0 (х₀), 1 (х₁),…, n-1 (x_n-1)), где используется условие i = i mod r. Следует пpизнать, что и многоалфавитные подстановки в пpинципе доступны кpиптоаналитическому исследованию. Кpиптостойкость многоалфавитных систем pезко убывает с уменьшением длины ключа. Тем не менее такая система как шифp Вижинеpа допускает несложную аппаpатную или пpогpаммную pеализацию и пpи достаточно большой длине ключа может быть использован в совpеменных ИС.

Цилиндр Джефферсона. В начале XIX века криптография обогатилась замечательным изобретением. Его автор - государственный деятель, первый государственный секретарь, а затем и президент США Томас Джефферсон. Свою систему шифрования он назвал «дисковым шифром». Этот шифр реализовывался с помощью специального устройства, которое впоследствии назвали шифратором Джефферсона. Конструкция шифратора может быть вкратце описана следующим образом. Деревянный цилиндр разрезается на 36 дисков (в принципе, общее количество дисков может быть и иным). Эти диски насаживаются на одну общую ось таким образом, чтобы они могли независимо вращаться на ней. На боковых поверхностях каждого из дисков выписывались все буквы английского алфавита в произвольном порядке. Порядок следования букв на различных дисках - различный. На поверхности цилиндра выделялась линия, параллельная его оси. При шифровании открытый текст разбивался на группы по 36 знаков, затем первая буква группы фиксировалась положением первого диска по выделенной линии, вторая - положением второго диска и т.д. Шифрованный текст образовывался путем считывания последовательности букв с любой линии параллельной выделенной. Обратный процесс осуществлялся на аналогичном шифраторе: полученный шифртекст выписывался путем поворота дисков по выделенной линии, а открытый текст отыскивался среди параллельных ей линий путем прочтения осмысленного возможного варианта. Хотя теоретически этот метод позволял предположить появление различных вариантов открытого сообщения, но, как показал накопившийся к тому времени опыт, это маловероятно: осмысленный текст читался только по одной из возможных линий. Шифратор Джефферсона реализует ранее известный шифр многоалфавитной замены. Частями его ключа являются порядок расположения букв на каждом диске и порядок расположения этих дисков на общей оси.

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

Криптография также числилась среди увлечений Уитстона. Когда ему уже было далеко за 50, он дешифровал архивное, длинное шифрованное письмо короля Карла I (как оказалось, весьма слабо зашифрованное небольшим по объему кодом). Впервые Уитстон продемонстрировал свое шифровальное устройство на Всемирной выставке в Париже в 1876 году. Смысл этого устройства заключается в следующем. В нем, так же, как и в шифраторе Уодсворта, просматривается влияние идей Альберти, а также и самого Уодсворта. Внешне устройство напоминает диск Альберти. Внешний диск - диск алфавита открытого текста - состоял из 27 знаков (26 букв английского алфавита и специального знака «+», означающего пробел). Внутренний алфавит определяет алфавит открытого текста и состоит из обычных 26 букв, расположенных в произвольном ключевом порядке (рисунок 1.2).

Рисунок 1.2 - Шифратор Ч. Уитстона

Энигма. Портативная шифровальная машина, использовавшаяся для шифрования и дешифрования секретных сообщений. Более точно, Энигма - целое семейство электромеханических роторных машин, применявшихся с 20-х годов XX века.

Энигма использовалась в коммерческих целях, а также в военных и государственных службах во многих странах мира, но наибольшее распространение получила в нацистской Германии во время Второй мировой войны. Именно Энигма вермахта (Wehrmacht Enigma) - немецкая военная модель - чаще всего является предметом дискуссий. Эта машина получила дурную славу, потому что криптоаналитики Антигитлеровской коалиции смогли расшифровать большое количество сообщений, зашифрованных с её помощью. Специально для этих целей была создана машина с кодовым названием Bombe, оказавшая значительное содействие Антигитлеровской коалиции в войне. Вся информация, полученная криптоанализом с её помощью, имела кодовое название ULTRA.

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

Было выпущено, по приблизительным оценкам, около 100 000 экземпляров шифровальных машин Энигма.

Рисунок 1.3 - Энигма

1.3 Перестановки

Шифры перестановок переставляют элементы открытых данных (биты, буквы, символы) в некотором новом порядке. Различают шифры горизонтальной, вертикальной, двойной перестановки, решетки, лабиринты, лозунговые и др.

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

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

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

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

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

Метод гаммиpования становится бессильным, если злоумышленнику становится известен фpагмент исходного текста и соответствующая ему шифpогpамма. Пpостым вычитанием по модулю получается отpезок ПСП и по нему восстанавливается вся последовательность. Злоумышленники может сделать это на основе догадок о содеpжании исходного текста. Так, если большинство посылаемых сообщений начинается со слов «СОВ.СЕКРЕТНО», то кpиптоанализ всего текста значительно облегчается. Это следует учитывать пpи создании pеальных систем инфоpмационной безопасности.

1.5 Шифры взбивания

Результат шифрования можно ощутимо улучшить, если вместо перестановки использовать линейное преобразование: s=L*t, где L - невырожденная матрица случайного линейного преобразования бит, или, что то же самое, детерминант L не равен нулю. И хотя расшифровывание в этом случае придется осуществлять решением систем линейных уравнений, но каждый бит шифровки начинает уже зависеть от каждого бита текста. Шифры на основе этого преобразования называют скрамблерами или взбивалками. К сожалению, доля невырожденных матриц с увеличением их размера стремительно убывает. Детерминант матрицы L, как и ее элементы, может быть равен либо 0, либо 1. Если det(L)=0, то матрица вырождена. Для того, чтобы матрица L была невырожденной, случайной и при расшифровании не нужно было производить много вычислений, американскими криптографами был предложен алгоритм, легший в основу стандартного криптографического преобразования DES. Суть его одного шага можно описать следующей схемой. Входной блок данных делится пополам на левую L' и правую R' части. После этого формируется выходной массив так, что его левая часть L» представлена правой частью R' входного, а правая R» формируется как сумма L' и R' операцией XOR. Далее, выходной массив шифруется перестановкой с заменой. Можно убедиться, что все проведенные операции могут быть обращены и расшифровывание осуществляется за число операций, линейно зависящее от размера блока. В то же самое время, после нескольких таких взбиваний можно считать, что каждый бит выходного блока шифровки может зависеть от каждого бита сообщения. С увеличением числа взбиваний порча единственного бита в шифровке делает нечитаемой половину текста, что обусловлено побайтовой перестановкой. Если бы перестановка была побитовая, то весь текст от ошибки в единственном бите перестал бы читаться.

1.6 Стандарт DES

Самым распространенным и наиболее известным алгоритмом симметричного шифрования является DES (Data Encryption Standard). Алгоритм был разработан в 1977 году, в 1980 году был принят NIST (National Institute of Standards and Technology США) в качестве стандарта (FIPS PUB 46). Алгоритм шифрования не является секретным и был опубликован в открытой печати. За все время использования этого шифра не было обнародовано ни одного случая обнаружения слабых мест в алгоритме шифрования.

DES является классической сетью Фейстеля с двумя ветвями. Данные шифруются 64-битными блоками, используя 56-битный ключ. Алгоритм преобразует за несколько раундов 64-битный вход в 64-битный выход. Длина ключа равна 56 битам. Процесс шифрования состоит из четырех этапов. На первом из них выполняется начальная перестановка (IP) 64-битного исходного текста (забеливание), во время которой биты переупорядочиваются в соответствии со стандартной таблицей. Следующий этап состоит из 16 раундов одной и той же функции, которая использует операции сдвига и подстановки. На третьем этапе левая и правая половины выхода последней (16-й) итерации меняются местами. Наконец, на четвертом этапе выполняется перестановка IP-1 результата, полученного на третьем этапе. Перестановка IP-1 инверсна начальной перестановке.

Ниже на рисунке показан способ, которым используется 56-битный ключ. Первоначально ключ подается на вход функции перестановки. Затем для каждого из 16 раундов подключ K_i является комбинацией левого циклического сдвига и перестановки. Функция перестановки одна и та же для каждого раунда, но подключи K_i для каждого раунда получаются разные вследствие повторяющегося сдвига битов ключа.

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

Рисунок 1.4 - Общая схема DES

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

2. Практический пример использования теоретического материала