4.2.1. Симметричные криптосистемы (единого ключа)

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

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

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

3. Разумеется, комбинируя (1) и (2), мы получаем шифр подстановки/перестановки

Пример (транспозиция). Предположим, что мы хотим зашифровать сообщение «computer algebra». Первый пример транспозиции -

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

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

и шифрованный текст имеет вид «cmuea gbaop trier». Способы взлома транспозиционных шифров можно найти в книгах (Kahn, 1967, pp. 225-226) и (Sinkov, 1968, ch. 5).

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

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

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

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

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

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

Пример. Отождествим , и т.д.:

Используя шифр Цезаря, и переписывая текст традиционным способом группами по пять символов, мы сообщение «computer algebra», эквивалентное 2,14,12,15,20 19,4,17,0,11 6,4,1,17,0, зашифровываем как 5,17,15,18,23 22,7,20,3,14 9,7,4,20,3 или, эквивалентно, как «ftpsx whudo jheud».

Одноалфавитные подстановки используют только один ключ, и их можно легко взломать, наблюдал частоту распределения символов в шифрованном тексте. Это — легкая задача, потому что имеются таблицы различных частот букв, например частоты первых букв в слове, частоты последних букв в слове, частоты диграфов (т.е. частоты сочетания: буква а, за которой следует b) и т.д. Таблица, приведенная на рис. 4.2.2, была получена Синковым из выборки из 1000 букв [см. приложения в книге (Sinkov, 1968)].

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

Рис. 4.2.2. Относительные частоты букв в английском языке.

символа. Эти шифры известны также как шифры Виженера, по фамилии французского криптографа шестнадцатого столетия Блеза де Виженера.

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

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

простой таблицей, где ключ появляется в левом столбце.

В этом случае сообщение «computer algebra» шифруется как «czwxm tpbid gplzs», где i-я буква открытого текста отображается в символ, находящийся в соответствующем столбце в i-м mod 5 алфавите шифра; например, буква открытого текста отображается в букву w, которая находится в столбце, начинающемся буквой , в алфавите, начинающемся буквой к.

Из последнего примера видно, что ключ «alkis» соответствует последовательности чисел 0, 11, 10, 8, 18, и, следовательно, шифрование может быть осуществлено последовательной записью под открытым текстом чисел и прибавлением их по модулю 26 к числам, соответствующим буквам открытого текста.

Процедура дешифровки выглядит следующим образом: число, соответствующее i-й букве открытого текста, получается прибавлением по модулю 26 числа, соответствующего i-й букве шифрованного текста, к -дополнению числа, соответствующего i-й (mod р) букве ключа. (Напомним, что получатель также знает ключ.) Например, если полученное сообщение — «czwxm tpbid gplzs», ключ — «alkis», или 0, 11, 10, 8, 18, и мы хотим вычислить вторую букву открытого текста, то прибавляем по модулю 26 число 25, соответствующее букве z шифрованного текста, к числу 15, являющемуся дополнением до 26 второй буквы ключа и получаем 14 или

Шифры Виженера считались в те дни невзламываемыми, но в 1863 г. прусский офицер по фамилии Ф.В. Касисский Kasiski) нашел простой теоретико-числовой метод поиска длины ключа и опубликовал этот результат. В многоалфавитных шифрах так же, как в шифре Цезаря, применяется сдвиг, но длина сдвига меняется, обычно периодически. Изменение сдвигов выравнивает частоты букв, обрекая на неуспех методы анализа, используемые для взлома шифров Иезаря, но характеристические частоты сохраняются в подпоследовательностях зашифрованного сообщения,

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

Период ключа может быть обнаружен поиском повторяющихся блоков в шифрованном тексте. Часть из них носит случайный характер, но основная масса получается из соответствия между повторяемыми словами или подсловами в открытом тексте и повторами в последовательности ключа. Когда это имеет место, расстояние между повторами будет кратным периоду ключа. Например, открытый текст «send more men and more arms» при использовании шифровального ключа «bhenf» даст шифрованный текст «tlrqr pyizj ohrqr pyinw nz» (если мы оставим последний блок неполным). В этом случае расстояние между двумя вхождениями равно 10, что означает, что длина ключа равна 10 или 5.

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

Пример. Если мы перенумеруем буквы от а до z, как в предыдущем примере (т.е. ), то сообщение «computer algebra», эквивалентное последовательности может быть зашифровано следующими двумя способами:

1. Используя преобразование а и мы получаем , и т.д., и, наконец, мы получаем шифрованный текст 4,16,0,1,9, 13,23,21,17,11, 17,10,5,18,17.

2. Используя преобразование мы получаем и т.д. и, наконец, получаем шифрованный текст 4,18,4,19,13, 6,10,1,1,12, 18,22,23,14,14.

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

эти шифры также считались невзламываемыми, но в 1883 г. Керчофс нашел общее решение для многоалфавитных подстановок без ограничений на тип или длину ключа [детали можно найти в книге (Kahn, 1967, pp. 236-237)]; более общее решение проблемы было дано Фридманом в 1918 г. Интересное изложение его идей мажет быть найдено в статье Гасса (Gass, 1986).

Наиболее значительный вариант шифра Виженера был предложен в 1918 г. американским инженером Вернамом (G.S. Vernam), работавшим в системе телетайпной сети AT&T (American Telephone к. Telegraph). Сообщения передавались тогда с использованием двоичного кода, и Вернам предложил прибавлять по модулю 2 случайные последовательности точек и пробелов так, чтобы вся частотная информация, корреляция между символами, периодичность и тому подобное терялись. Главный недостаток этой процедуры состоит в том, что она требует обмена огромным количеством ключей заблаговременно (т.е. один символ ключа на каждый символ сообщения). Вернам первоначально предполагал использовать или короткий ключ, или линейную комбинацию коротких ключей, но оба подхода оказались уязвимыми. С одной стороны, использование короткого ключа уязвимо по результатам типа Касисского, с другой стороны, как было доказано майором американских войск связи Мауборном, использование линейных комбинаций коротких ключей может быть успешно проанализировано по существу той же техникой, которая используется против систем бегущего ключа.

И Фридман, и Мауборн пришли к выводу, что для безоговорочно надежной криптосистемы ключ должен быть таким же длинным, как сообщение, и непоследовательным (т.е. нерегулярность каждого символа ключа должна быть по крайней мере так же велика, как среднее информационное содержание на символ открытого текста). Если мы предположим, что М — верхняя граница длин всех возможных сообщений, то мы выбираем ключевую последовательность по крайней мере такой же длины, как М; все ключевые последовательности тогда равновероятны. Если работа ведется по модулю 26, открытый текст имеет вид и каждый символ - представлен одним из чисел от 0 до 25, то ключевая последовательность — это , где — случайно выбранное число между 0 и 25. Тогда каждый символ шифрованного текста равен Эта схема называется шифром одноразового блокнота, и такое название связано с тем, что процесс шифровки/дешифровки использует выписанные перечни

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

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

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

Лучшая из известных систем ручного диграфового шифрования принадлежит английскому ученому Плейферу. По этой схеме перемешанная алфавитная последовательность записывается в квадрате 5x5. (Буква «j» опускается, поскольку она встречается довольно редко и может быть потом восстановлена в контексте.) Так, например, мы может взять

и сообщение «computer algebra» шифруется как «ghwvc qzglk osrda», при этом пара «со» отображается в пару «gh», где g находится

в той же строке, что и с (обратите внимание на параллелограмм, задаваемый буквами ) и т.д. Из этого примера читатель легко может вывести правила шифрования текста, когда две буквы лежат в одной строке или столбце [явно эти правила сформулированы в работе Синкова (Sinkov, 1968, р. 114)]. Используя подсчет частот диграфов, Мауборн провел криптоанализ этой схемы в 1914 г.

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

Определение 4.2.4. Пусть К есть -матрица, а а и d — некоторые -мерные векторы с компонентами из Шифр Хилла — это отображение вида инъективное тогда и только тогда, когда все операции выполняются по модулю т.

Для шифровки мы подразделяем открытый текст на блоки по букв каждый, заменяем каждую букву соответствующим ей элементом из образуем транспонированные вектор-столбцы и применяем данное линейное преобразование к каждому блоку а. В этом контексте используются матрицы инволюций К, являющиеся своими обратными. Они определяются условиями или (Операции выполняются по модулю .) Заметим, что поскольку то откуда следует, что Пытаясь определить матрицы инволюций, когда размерность равна 2 и мы видим, что если то можно получить только восемь таких матриц. Ясно, что случай, когда гораздо интереснее (см. также упр. 5 к этому разделу). В этом случае имеется 736 матриц инволюции, и криптограмма может быть дешифрована, даже если не известно ни одного слова минимальной длины из открытого текста. Определяются и пробуются все матрицы инволюций. Для больших дешифровка этим методом проб и ошибок уже невозможна.

Пример. Рассмотрим сообщение «computer algebra», где буквам открытого текста присвоены номера и матрицу

инволюции

вектор d полагается нулевым. Шифрованный текст принимает вид «ymzcr yxuze oirza», причем последний символ открытого текста остается без изменения. Пара «со», эквивалентная вектору (2,14), отображается на вектор который соответствует паре и т.д.

Заменяя постоянную матрицу К матрицей с переменными элементами, мы получаем разновидность предложенной выше схемы. Детали этого подхода могут быть найдены в книге Лидла и Пилца (Lidl, Pilz, 1984), другие интересные схемы описаны также Криш-намурти и Рамахандраном (Krishnamurthy, Ramachandran, 1980).

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

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

Анализ известного открытого текста. Теперь противниклмеет несколько пар открытый текст-шифрованный текст, с которыми он может работать.

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

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

смысла этого утверждения нам понадобятся некоторые основные факты теории сложности вычислений (Lewis, Papadimitriou, 1978).

Математические проблемы могут быть первично разделены на две основные категории: разрешимые и неразрешимые проблемы. Пример неразрешимой проблемы — проблема «останова» машины Тьюринга, которая эквивалентна следующей: «Пирюльник бреет всех тех, кто не бреется сам; бреет ли он себя?». (Ответ: Если бреет, то не бреет, а если не бреет, то бреет, т.е. у задачи нет ответа.)

Разрешимые проблемы могут быть далее подразделены на следующие общие категории:

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

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

NP-проблемы (недетерминистические полиномиальные), для которых известны только экспоненциальные алгоритмы, но не доказано, что алгоритмов с полиномиальным временем не существует. Очевидно, что множество -проблем образует подмножество множества -проблем, но вопрос, верно ли, что — наибольшая открытая проблема в теоретической информатике. Характеристическое свойство -проблем таково: тогда как найти решение такой проблемы очень трудно, если оно найдено, то его очень легко проверить за полиномиальное время; это свойство будет использоваться ниже.

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

Воспользуемся теперь упомянутыми выше идеями современной криптографии (Feistel, 1973; Lempel, 1979). Нас интересуют

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

Рис. 4.2.3. Ящик подстановки (-ящик) для блочных шифров: соединения между двумя переключателями можно рассматривать как ящик перестановки (Р-ящик).

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

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

конфигураций соединения, имеется только 32 возможных входа и выхода. Таким образом, нам необходимо большое количество входов и выходов, настолько большое, что для любого противника практически невозможно разобрать все конфигурации. Например, если мы имеем ящик с 128 входами и выходами, анализатор должен иметь дело с 2128 возможными блоками ввода/вывода, т.е. с настолько большим их числом, что частотный анализ больше уже не осуществим. Конечно, недостаток этой схемы в том, что она требует 2128 соединений между переключателями (в Р-ящике), что технологически невозможно (в настоящее время). Так что должен быть достигнут компромисс.

Ясно, что одно устройство с многими входами и выходами само является P-ящиком; на рис. 4.2.3 он имеет восемь входов и выходов. Несмотря на то что имеется 40320 возможных соединений, истинное найти очень легко, просто подавая на вход устройства только один бит, равный 1, а остальные равные 0 и наблюдая, где 1 появляется на выходе. В нашем примере мы можем определить соединения после семи проб. Отметим, что S-ящик — это нелинейное устройство, а Р-ящик — линейное.

Чтобы улучшить эту схему, мы должны ввести так называемые системы шифров-произведений, комбинирующие Р- и S-ящики. Впервые системы шифров-произведений были предложены Шенноном (Shannon, 1948, 1949), они состоят из слоев Р- и S-ящиков. Предположим, что P-ящики имеют по 15 входов и выходов и что S-ящики имеют их только по 3; тогда за каждым P-ящиком следует пять S-ящиков, и операция в системе шифров-произведений выполняется при условии, что вход состоит из 14 нулей и одной 1, следующим образом: первый ящик, Р, передает единственную 1 некоторому ящику S, который, являясь нелинейным устройством, может из одной 1 получить до трех 1. Эти единицы подаются затем на следующий P-ящик, который перетасовывает их и подает на следующие S-ящики, и процесс повторяется. В конце выход содержит сбалансированное число нулей и единиц. Эти идеи проиллюстрированы на рис. 4.2.4.

Рис. 4.2.4 иллюстрирует принцип, на котором основана IBM-система LUCIFER. P-ящики в системе LUCIFER имеют или 64, или 128 входов и выходов, а S-ящики — только 4. Конечно, цель разработчика состоит в том, чтобы сделать для противника как можно более сложной задачу проследить обратный путь и таким образом восстановить ключи перестановок на S и Р. Система

Рис. 4.2.4. Система шифров-произведений, где P-ящики имеют 15 входов и выходов, а S-ящики имеют их только по 3.

LUCIFER является блочным шифром высокой пробы, однако, в настоящее время она не считается надежной системой.

В 1977 г. Национальное бюро стандартов выпустило Стандарт шифрования данных (DES) с намерением создать криптографический стандарт, используемый для надежной передачи всяких данных, кроме данных, связанных с национальной безопасностью. DES-алгоритм— это блочный шифр, разработанный фирмой IBM, на основе S/P-схемы типа описанной выше системы LUCIFER. DES шифрует 64-битовые блоки открытого текста, используя 64-битовые ключи (56 битов ключа и 8 проверочных битов). Шифрование осуществляется за 16 отдельных этапов, причем на каждом этапе используется шифр-произведение под управлением 48-битового ключа. То есть на всех этапах используются различные 48-битовые ключи получаемые в соответствии с некоторым алгоритмом программы планирования из внешнего ключа К.

Хотя с точки зрения теории сложности DES выглядит надежным, размер ключа этого стандарта подвергается критике [см. (Diffie, Heilman, 1977)]. Проблема состоит в том, что 56-битовый ключ взламывается путем «анализа известного открытого текста» противником с использованием больших, но реальных, вычислительных ресурсов. Это делается методом грубой силы. Предположим, например, что известное сообщение М зашифровано при помощи DES с ключом К и что Чтобы определить К,

криптоаналитик декодирует С с каждым из 256 возможных ключей. Определив М, криптоаналитик прекращает работу и объявляет К. Хотя этот исчерпывающий поиск выглядит невозможным, решительный противник может построить компьютер специального назначения, который выполняет параллельно миллион проверок за сравнительно короткое время (< 10 часов). Однако, вероятно, увеличение размера ключа с 56 до 128 исключит исчерпывающий поиск из употребления.

Неудовлетворение стандартом DES дало импульс дальнейшим исследованиям (Diffie, Heilman, 1976) и привело к открытию асимметричных систем кодирования, также известных как криптосистемы открытого ключа. Отметим, что до сих пор все рассматриваемые системы были симметричными в том смысле, что как отправитель, так и получатель обладали одним и тем же ключом, который должен быть надежным.