InfoCity
InfoCity - виртуальный город компьютерной документации
Реклама на сайте







Размещение сквозной ссылки

 

Криптография и криптоанализ: вековая проблема человечества


Александр Алексеев


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

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

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

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

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

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

Коды появились в глубокой древности в виде криптограмм (по-гречески - тайнопись). Порой священные иудейские тексты шифровались методом замены. Вместо первой буквы алфавита писалась последняя буква, вместо второй - предпоследняя и так далее. Этот древний метод шифрования назывался атбаш. Известно, что шифровалась переписка Юлия Цезаря (100 - 44 гг. до н. э.) с Цицероном (106 - 43 г.г. до н. э.).

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

В Древней Греции (II в. до н.э.) был известен шифр, называемый "квадрат Полибия". Шифровальная таблица представляла собой квадрат с пятью столбцами и пятью строками, которые нумеровались цифрами от 1 до 5. В каждую клетку такого квадрата записывалась одна буква. В результате каждой букве соответствовала пара чисел, и шифрование сводилось к замене буквы парой чисел.

Идею квадрата Полибия проиллюстрируем таблицей с русскими буквами. Число букв в русском алфавите отличается от числа букв в греческом алфавите, поэтому и размер таблицы выбран иным (не квадрат 5x5, а прямоугольник 8x4).

1 2 3 4 5 6 7 8
1 А Б В Г Д Е Ж З
2 И Й К Л М Н Щ П
3 Р С Т У Ф Х Ц Ч
4 Ш Щ Ъ Ы Ь Э Ю Я

Зашифруем фразу: КРИПТОГРАФИЯ:

23 31 21 28 33 27 14 31 11 35 21 48

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

Термины


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

В настоящее время проблемами защиты информации занимается криптология (kryрtos - тайный, logos - наука). Криптология разделяется на два направления - криптографию и криптоанализ. Цели этих двух направлений криптологии прямо противоположны.

Криптография - наука о защите информации от несанкционированного прочтения ее посторонними лицами. Криптография занимается разработкой и исследованием методов шифрования информации.

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

Сфера интересов криптоанализа противоположная - разработка и исследование методов дешифрования (раскрытия) шифрограммы даже без знания секретного ключа.

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

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

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

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

Шифры


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

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

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

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

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

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

Алгоритмы шифрования с открытым ключом используют так называемые необратимые или односторонние функции. Эти функции обладают следующим свойством: при заданном значении аргумента x относительно просто вычислить значение функции f(x), однако, если известно значение функции y = f(x), то нет простого пути для вычисления значения аргумента x.

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

  1. Разложение больших чисел на простые множители (алгоритм RSA, авторы - Райвест, Шамир и Адлеман - Rivest, Shamir, Adleman).
  2. Вычисление логарифма или возведение в степень (алгоритм DH, авторы - Диффи и Хелман)
  3. Вычисление корней алгебраических уравнений.

Рассмотрим простейший пример необратимых функций. Легко в уме найти произведение двух простых чисел 11 и 13. Но попробуйте быстро в уме найти два простых числа, произведение которых равно 437. Такие же трудности возникают и при использовании вычислительной техники для отыскания двух простых сомножителей для очень большого числа: найти сомножители можно, но потребуется много времени.

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

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

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

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

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

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

В США для передачи секретных сообщений наибольшее распространение получил стандарт DES (Data Encryption Standard). "Тройной DES" предусматривает для повышения стойкости сообщения троекратное шифрование данных с разными ключами. Стандарт шифрования данных DES был разработан фирмой IBM в начале 70-х годов и первоначально назывался Lucifer.

Сложный алгоритм DES использует ключ длиной 56 бит и требует от криптоаналитика перебора 72 квадриллионов (1015) возможных ключевых комбинаций. Недостатком шифра DES является малая длина ключа - 56 бит и медленная программная реализация (большой объем вычислений).

Свое развитие DES получил в ГОСТ 28147-89, который увеличил длину ключа до 256 бит.

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

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

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

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

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

Криптоанализ


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

В таблице приведены относительные частоты появления русских букв.

Буква Частота Буква Частота Буква Частота Буква Частота
о 0.09 0.038 з 0.016 ж 0.007
е, ё 0.072 л 0.035 ы 0.016 ш 0.006
а 0.062 к 0.028 б 0.014 ю 0.006
и 0.062 м 0.026 ь,ъ 0.014 ц 0.004
н 0.053 д 0.025 г 0.013 щ 0.003
т 0.053 п 0.023 ч 0.012 э 0.003
с 0.045 у 0.021 й 0.01 ф 0.002
р 0.04 я 0.018 х 0.009

Относительная частота появления пробела или знака препинания в русском языке составляет 0,174.

Приведенные цифры означают следующее: среди 1000 букв текста в среднем будет 174 пробела и знака препинания, 90 букв "о", 72 буквы "е" и т.д.

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

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

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


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


Реклама на InfoCity

Яндекс цитирования



Финансы: форекс для тебя








1999-2009 © InfoCity.kiev.ua