Математические основы криптографии

Шифр замены является простейшим, наиболее популярным шифром. Типичными примерами являются шифр Цезаря, «цифирная азбука» Петра Великого и «пляшущие человечки» А. Конан-Дойля. Как видно из самого названия, шифр замены осуществляет преобразование замены букв или других «частей» открытого текста на аналогичные «части» шифрованного текста. Понятно, что, увеличив алфавиты, т.е. объявив «части» буквами, можно любой шифр замены свести к замене букв. Теперь уже легко дать математическое описание шифра замены. Пусть X и Y – два алфавита открытого и соответственно шифрованного текстов, состоящие из одинакового числа символов. Пусть также g: X " Y – взаимнооднозначное отображение X в Y. Это значит, что каждой букве х алфавита X сопоставляется однозначно определенная буква у алфавита У, которую мы обозначаем символом g(х), причем разным буквам сопоставляются разные буквы. Тогда шифр замены действует так: открытый текст x₁x₂...x_n преобразуется в шифрованный текст g(х₁)g(x₂)...g(x_n).

Шифр перестановки, как  видно из названия, осуществляет преобразование перестановки букв в открытом тексте. Типичным и древнейшим примером шифра перестановки является шифр «Сциталь». Обычно открытый текст разбивается на отрезки равной длины, и каждый отрезок шифруется (т.е. в нем переставляются буквы) независимо. Пусть, например, длина отрезков равна n и σ – взаимнооднозначное отображение множества {1,2, ..., n} в себя. Тогда шифр перестановки действует так: отрезок открытого текста x₁...x_n преобразуется в отрезок шифрованного текста x_σ(1)...x_σ(n).

Важной проблемой при  практическом использовании шифров замены и перестановки является проблема удобного запоминания отображений g и σ. Ясно, что легко запоминать некоторые отображения: например, отображения «небольших» размеров, отображения, реализуемые каким-нибудь предметом (сциталь в шифре «Сциталь» и т.п.). Если же отображение «большого» размера, то процесс запоминания сильно усложняется. Например, широко известны биграммные шифры. В них преобразовывались биграммы (пары букв). Поскольку количество биграмм превышает 1000, то на практике биграммные шифры выглядят как специальные книжки.

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

Популярным способом запоминания отображения σ, т.е. шифра перестановки, является следующий. Пусть, например, n=20. Берем прямоугольную таблицу размера 4x5, вписываем в нее открытый текст «по строкам», а шифрованный текст считываем «по столбцам». Возможны и более хитрые способы вписывания и считывания.

2.5 Абсолютно стойкий шифр

 

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

Обсудим особенности  строения абсолютно стойкого шифра  и возможности его практического  использования. Типичным и наиболее простым примером реализации абсолютно стойкого шифра является шифр Вернама, который осуществляет побитовое сложение n-битового открытого текста и и битового ключа: y_i=x₁+k_i, i=1,...,n.

Здесь x₁...x_n – открытый текст, k₁...k_n – ключ, y₁...y_n – шифрованный текст; символы складываются по таким правилам: 0+0=0, 0+1=1+0=1, 1+1=0.

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

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

2) равенство длины  ключа и длины открытого текста;

3) однократность использования  ключа.

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

Но, оказывается, именно эти условия и делают абсолютно  стойкий шифр очень дорогим и  непрактичным. Прежде чем пользоваться таким шифром, мы должны обеспечить всех абонентов достаточным запасом случайных ключей и исключить возможность их повторного применения. А это сделать необычайно трудно и дорого. Как отмечал Д. Кан: «Проблема создания, регистрации, распространения и отмены ключей может показаться не слишком сложной тому, кто не имеет опыта передачи сообщений по каналам военной связи, но в военное время объем передаваемых сообщений ставит в тупик даже профессиональных связистов. За сутки могут быть зашифрованы сотни тысяч слов. Создание миллионов ключевых знаков потребовало бы огромных финансовых издержек и было бы сопряжено с большими затратами времени. Так как каждый текст должен иметь свой собственный, единственный и неповторимый ключ, применение идеальной системы потребовало бы передачи, по крайней мере, такого количества знаков, которое эквивалентно всему объему передаваемой военной информации».

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

2.6 Теория и практика стойкости шифра

 

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

Обычно эту мысль  выражают так: противник с неограниченными  ресурсами может вскрыть любой  неабсолютно стойкий шифр.

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

Поэтому у пользователя остается единственный путь – получение  практических оценок стойкости. Этот путь состоит из следующих этапов:

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

2.7 Без атаки на ключ

 

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

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

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

1) в осмысленных текстах  любого естественного языка различные  буквы встречаются с разной  частотой, а действие подстановки  «переносит» эту закономерность  на шифрованный текст;

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

2.8 Криптосистема RSA

 

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

Однако уже в начале 1977 г. американские специалисты по компьютерным наукам Р. Ривест, А. Шамир и Л. Адлеман  придумали одну такую функцию. Система  на основе этой функции оказалась  очень практичной и получила широкое распространение под названием «система RSA» по первым английским буквам фамилий авторов.

Опишем систему RSA. Пусть n=pq, где р и q – большие простые  числа, а е – некоторое число, взаимно простое с φ(n). Найдем число d из уравнения d∙е=1(modφ(n)).

Числа р, q и d будем считать  секретными и обозначим секрет К={p,q,d}. Числа т и е будем считать  общедоступными. Множества открытых сообщений X и шифрованных сообщений Y будем считать равными X=Y={1,2,...,n-1}.

Функцию F_K ;  X"Y определим равенством F_K(x) = x^e(modn).

Свойство а) односторонней  функции с секретом выполнено  для FK очевидным образом. Проверим свойство в). Для этого просто укажем, как  при известном К инвертировать  функцию F_K: решением уравнения F_K(x)=у будет х=y^d(modn). Подробное доказательство этого факта оставляем читателю, приведем лишь необходимые выкладки без комментариев: d∙е=φ(n)∙т+1

(x^e)^d(modn) = a^φ(n)m+1(modn)=(x^φ(n))^m∙x(modn)=(1)^m∙x(modn)=x.

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

Таким образом, описанную  функцию F_K можно считать кандидатом на звание односторонней функции с секретом. Система RSA строится с помощью этой функции.

В газете «Известия» за 29 апреля 1994 г. под заголовком «Сверхсекретный  шифр разгадан за 17 лет» появилось следующее  сообщение: «Когда в 1977 году математики Рональд Ривест, Ади Шамир и  Леонард Адлеман зашифровали  фразу из нескольких слов, используя комбинацию из 129 цифр, они утверждали, что на разгадку понадобятся триллионы лет. Однако ключ к самому сложному в мире шифру «РСА-129» (RSA) был найден за 17 лет... Разгадка шифра за такой относительно короткий срок имеет огромное значение для государственных организаций и предпринимателей, которые пользуются аналогичными длинными цифровыми кодами для защиты секретных сведений в своих компьютерных базах данных...» Пока это сообщение не подтверждено научными публикациями, ясно лишь, что речь идет о том, что удалось разложить на множители то 129-значное число, которое было использовано в 1977 году. Но уже давно в реальных системах RSA используются более длинные числа.

 

                     

 

Глава III Реализация математической криптографии

Шифр Цезеря

 

Свой след в истории  криптографии оставили многие хорошо известные исторические личности. Приведем несколько наиболее ярких примеров. Первые сведения об использовании шифров в военном деле связаны с именем спартанского полководца Лисандра. Цезарь использовал в переписке шифр, который вошел в историю как ``шифр Цезаря''. В древней Греции был изобретен вид шифра, который в дальнейшем стал называться ``квадрат Полития''. Одну из первых книг по криптографии написал аббат И. Трителий (1462-1516), живший в Германии. В 1566 году известный математик Д. Кардано опубликовал работу с описанием изобретенной им системы шифрования (``решетка Кардано''). Первые действительно достоверные сведения с описанием метода шифрования относятся к периоду смены старой и новой эры и описывают шифр Цезаря - способ, которым Юлий Цезарь прятал свои записи от излишне любопытных глаз.

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

Итак, беря исходный вариант ABCDEFGHIJKLMNOPQRSTUVWXYZ

и смещая всё на 3, получаем   DEFGHIJKLMNOPQRSTUVWXYZABC,

где D=A, E=B, F=C, и т.д.

Используя эту схему, открытый текст «SECRET» шифруется в «VHFUHW». Чтобы позволить кому-то прочитать исходный текст, вы передаёте ему, что ключ -- 3.

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

Шифр Цезаря. Этот шифр реализует следующее преобразование открытого текста: каждая буква открытого текста заменяется третьей после нее буквой в алфавите, который считается написанным по кругу, т.е. после буквы ``я'' следует буква ``а''. Отметим, что Цезарь заменял букву третьей после нее буквой, но можно заменять и какой-нибудь другой. Главное, чтобы тот, кому посылается шифрованное сообщение, знал эту величину сдвига. Класс шифров, к которым относится и шифр Цезаря, называется шифрами замены.

Историческим примером шифра замены является шифр Цезаря (I век до н. э.), описанный историком  Древнего Рима Светонием. Гай Юлий Цезарь использовал в своей переписке шифр собственного изобретения. Применительно к современному русскому языку он состоял в следующем. Выписывался алфавит: А, Б, В, Г, Д, Е, ...; затем под ним выписывался тот же алфавит, но с циклическим сдвигом на 3 буквы влево: