Главная | Обратная связь

Основные классы симметричных криптосистем

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

Моно- и многоалфавитные подстановки.

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

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

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

Блочные шифры.

Представляют собой семейство обратимых преобразований блоков (частей фиксированной длины) исходного текста. Фактически блочный шифр – это система подстановки блоков. В настоящее время блочные шифры наиболее распространены на практике. Российский и американский стандарты шифрования относятся именно к этому классу шифров.

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

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

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

 

Шифр замены

Самый простой и эффективный способ сделать текст нечитаемым – спрятать его, смешав с последовательность случайных чисел, заданной ключом. При этом информация сообщения прячется в шуме – самом информативном, по определению Шеннона, сигнале. Для этого можно использовать логическую операцию исключающего ИЛИ (XOR). Таблица истинности для операции XOR имеет следующий вид.

XOR	0	1
0
1

Обоснуем выбор случайных последовательностей для шифрования заменой. Очевидно, что, зная статистические свойства нашей последовательности, криптоаналитик попытается снизить неопределенность чтения шифровки. Если криптоаналитик знает, что в последовательности 1 встречается с вероятностью p, а 0 с вероятностью 1-p, то он тоже с вероятностью p будет предполагать наличие 1. Вероятность его успеха равна:

Эта функция достигает минимума при p=0,5. Это означает равновероятный выбор значений 1 и 0 в случайной последовательности. Если биты в случайной последовательности с одинаковой вероятностью принимают значения 0 и 1, то и биты в шифровке будут обладать тем же свойством. Действительно, пусть вероятность нулевого бита в тексте равна p, а единичного бита 1-p. Нулевой бит в шифровке появляется, когда соответствующие биты текста и последовательности равны или 0, или 1. Следовательно, вероятность появления нулевого бита в шифровке равна:

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

Из-за специфики операции XOR процедура шифрования совпадает с процедурой расшифровывания. Действительно, обозначим через t вектор бит сообщения, g - вектор случайной последовательности, s – вектор шифровки. Шифровку получаем следующим образом:

,

а сообщение из шифровки

,

т.к.

Такой шифр представляет собой многоалфавитные шифры замены.

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

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

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

Найдем их сумму: . Исходный текст может быть получен путем подбора s₀, которое неизвестно, в выражении:

t_n = s₀ + s₁ + s₂ + s₃ + … s_n

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

Другая неприятность с машинными многоалфавитными шифрами замены может возникнуть, если в сообщении встречаются большие участки пробелов или нулевых символов. Например, линия связи недозагружена, но когда нет сообщений, аппаратура шифрования не отключается. Поэтому когда сообщений нет (t=0) шифровка будет представлять собой "чистую" последовательность ключа. Если в это время с помощью специальной аппаратуры перехватить шифровку, представляющую собой ключ s=g , то можно положить на нее текст своего сообщения s'=s+t=t+g и передать искаженную шифровку по каналу связи. Получатель, расшифровав ее:

s' + g = s + t + g = t + g + g = t

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

Шифр перестановки

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

Перестановку можно рассматривать как умножение вектора сообщения на матрицу перестановки бит P с элементами 0 и 1 и размером в длину сообщения в битах. При этом возможны два случая.

1. Перестановка может делаться до наложения на сообщение случайной последовательности:

S' = P t + g

В случае если текст в сообщении отсутствует, то в канал связи попадет чистый ключ:

t = 0; S' = P 0 + g = g

2. Перестановка может делаться после наложения на сообщение случайной последовательности:

S' = P (t + g )

В случае если текст отсутствует, в канал связи поступает ключ, шифрованный перестановкой:

t = 0; S' = P (0 + g ) = P g

Обычно предпочтение отдается второй схеме.

Перестановки необходимы еще и для того, чтобы атака на ключ стала неэффективной.

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

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

Существует множество вычислительных способов перестановок. Например, широко применяется перестановка по номерам N от 0 до L-1 на основе рекуррентного соотношения:

N_i+1 = (K N_i + M) mod L

при выполнении следующих условий:

1) K и M берутся из интервала [1, L-1];

2) M взаимно просто с L;

3) K-1 делится на любой простой делитель L;

4) K-1 делится на 4, если L делится на 4.

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

Другая схема перестановки напоминает тасовку карт. Если S=A+B+C – исходный блок текста, переставляемый побайтно, то результатом перестановки будет S'=C+B+A. Разбиение на фрагменты A, B, C делается случайным образом. После нескольких тасовок исходный текст оказывается основательно перемешанным. Эта тасовка в состоянии после многократного повторения осуществить любую перестановку, но число тасовок при этом должно быть очень велико. Для быстрого получения качественной перестановки лучше употреблять перестановку пар:

For i:=1 to N

SWAP arr(i), arr(N*RND)

Next

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

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

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

 

Шифр Энигмы

Предшественницей современных криптографических машин была роторная машина, изобретенная в 1917 году Эдвардом Хеберном. Впоследствии она получила называние Энигма. Независимая промышленная версия была создана чуть позже берлинским инженером Артуром Кирхом. Промышленные образцы этой машины изготовляла фирма Siemens.

Энигма вначале представляла собой четыре вращающихся на одной оси барабана, что обеспечивало более миллиона вариантов шифра простой замены, которые определялись текущим положением барабанов. На каждой стороне барабана по окружности располагались 25 электрических контактов (сколько букв в алфавите). Контакты с обеих сторон барабана соединялись попарно случайным образом 25 проводами, формировавшими замену символов. Колеса складывались вместе и их контакты, касаясь друг друга, обеспечивали прохождение электрических импульсов сквозь весь пакет колес. Перед началом работы барабаны поворачивались так, чтобы устанавливалось заданное кодовое слово – ключ. При нажатии клавиши и кодировании очередного символа правый барабан поворачивался на один шаг. После того, как барабан делал полный оборот, на один шаг поворачивался следующий барабан (как в счетчике электроэнергии). Таким образом получался ключ заведомо гораздо более длинный, чем текст сообщения.

Например, в первом правом барабане провод от контакта, соответствующего букве U, присоединен к контакту буквы F на другой его стороне (рис. 3.1). Если же барабан поворачивался на одни шаг, то этот же провод соответствовал замене следующей за U буквы V на следующую за F букву G. Т.к. барабаны соприкасались контактами, то электрический импульс от нажатой клавиши с буквой исходного текста прежде чем достигал выхода претерпевал 4 замены: по одной на каждом барабане.

Рис. 3.1. Роторная машина Энигмы.

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

При моделировании машины Энигмы инженера Кирха на ЭВМ можно достичь хорошей устойчивости при сравнительной простоте программы.

В чем же была слабость шифра?

1. Пять барабанов могли обеспечить около 100 миллионов ключей, что позволяло их перебрать на ЭВМ за день. Если использовать не 25 латинских символов, а 256 кодов ASCII и увеличить число барабанов, то сложность раскалывания шифра существенно возрастет.

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

3. Можно сделать движение барабанов хаотичным, по случайной последовательности, вырабатываемой по ключу.

Подсчитаем число ключей такого шифра, реализованного программно. Пусть длина периода программного генератора случайных чисел равна 2²⁴. Восемь барабанов, генерируемые с помощью этого генератора, дадут вместе 2¹⁹² вариантов ключа. Если учесть еще варианты псевдослучайной последовательности, управляющей движением барабанов, то получится цифра в 2²¹⁶ вариантов ключа.

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

 

БЛОЧНЫЕ ШИФРЫ

Каким же условиям должен удовлетворять стойкий блочный шифр? Эти условия сформулировал Шеннон в ряде своих основополагающих работ по теории шифрования: такой шифр должен обладать свойствами перемешивания и рассеивания:

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

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