Криптология, криптография, криптоанализ

Можно выделить следующие три периода развития крипто-логии. Первый период — эра донаучной криптологии, являв­шейся ремеслом-уделом узкого круга искусных умельцев. Нача­лом второго периода можно считать 1949 г., когда появилась ра­бота К. Шеннона «Теория связи в секретных системах», в которой проведено фундаментальное научное исследование шифров и важнейших вопросов их стойкости. Благодаря этому труду криптология оформилась как прикладная математическая дисциплина. И, наконец, начало третьему периоду было положе­но появлением в 1976 г. работы У. Диффи, М. Хеллмана «Новые направления в криптографии», где показано, что секретная связь возможна без предварительной передачи секретного клю­ча. Так началось и продолжается до настоящего времени бурное развитие наряду с обычной классической криптографией и криптографии с открытым ключом.

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

Криптология разделяется на два направления — криптогра­фию и криптоанализ. Цели этих направлений прямо противопо­ложны:

• криптография занимается поиском и исследованием мате­матических методов преобразования информации;

• сфера интересов криптоанализа — исследование возможно­сти расшифровывания информации без знания ключей;

Современная криптография включает в себя четыре крупных раздела:

• симметричные криптосистемы;

• криптосистемы с открытым ключом;

• системы электронной подписи;

• управление ключами.

Основные направления использования криптографических методов — передача конфиденциальной информации по кана­лам связи (например, электронная почта), установление подлин-

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

Криптосистемы разделяются на симметричные и асимметричные (с открытым ключом):

• в симметричных криптосистемах и для шифрования, и для дешифрования используется один и тот же ключ. Сущест­вуют весьма эффективные (быстрые и надежные) методы симметричного шифрования. Существует и стандарт на по­добные методы — ГОСТ 28147—89 «Системы обработки информации. Защита криптографическая. Алгоритм крип­тографического преобразования».

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

• в асимметричных методах используются два ключа. Один из них, несекретный (он может публиковаться вместе с ад­ресом пользователя), используется для шифровки, другой (секретный, известный только получателю) — для расшиф­ровки. Самым популярным из асимметричных является метод RSA (Райвест, Шамир, Адлеман), основанный на операциях с большими (скажем, 100-значными) простыми числами и их произведениями. Использование асиммет­ричного шифрования проиллюстрировано рис. 8.4.

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

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

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

Классы методов криптографии

Рассмотрим классификацию методов криптографического закрытия.

1. Шифрование

1.1. ЗАМЕНА (ПОДСТАНОВКА)

1.1.1. Простая (одноалфавитная)

1.1.2. Многоалфавитная одноконтурная обыкновенная

1.1.3. Многоалфавитная одноконтурная монофоническая

1.1.4. Многоалфавитная многоконтурная

1.2. ПЕРЕСТАНОВКА

1.2.1. Простая

1.2.2. Усложненная по таблице

1.2.3. Усложненная по маршрутам

1.3. АНАЛИТИЧЕСКОЕ ПРЕОБРАЗОВАНИЕ

1.3.1. С использованием алгебры матриц

1.3.2. По особым зависимостям

1.4. ГАММИРОВАНИЕ

1.4.1. С конечной короткой гаммой

1.4.2. С конечной длинной гаммой

1.4.3. С бесконечной гаммой

1.5. КОМБИНИРОВАННЫЕ МЕТОДЫ

1.5.1. Замена и перестановка

1.5.2. Замена и гаммирование

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

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

2. Кодирование

2.1. СМЫСЛОВОЕ

2.1.1. По специальным таблицам (словарям)

2.2. СИМВОЛЬНОЕ

2.2.1. По кодовому алфавиту

3. Другие виды

3.1. РАССЕЧЕНИЕ-РАЗНЕСЕНИЕ

3.1.1. Смысловое

3.1.2. Механическое

3.2. СЖАТИЕ-РАСШИРЕНИЕ

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

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

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

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

Гаммирование — этот метод заключается в наложении на исходный текст некоторой псевдослучайной последователь­ности, генерируемой на основе ключа.

Блочные шифры — последовательность (с возможным повторением и чередованием) основных методов преобразова­ния, применяемая к блоку (части) шифруемого текста. Блочные шифры на практике встречаются чаще, чем «чистые» преобразо­вания того или иного класса в силу их более высокой крипто-стойкости. Российский и американский стандарты шифрования основаны именно на этом классе шифров.

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

Кратко рассмотрим некоторые методы криптографического закрытия информации.

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

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

Используя эту таблицу, зашифруем текст: In this book the reader will wind a comprehensive survey... Получим следующее за­шифрованное сообщение: At omiy pbbe omr nrsirn / add zail s xbwgnrmrtjafr jcnfru... Однако такой шифр имеет низкую стой­кость, так как зашифрованный текст имеет те же статистические характеристики, что и исходный. Например, текст на англий­ском языке содержит символы со следующими частотами появ­ления (в порядке убывания): Е — 0,13, Т — 0,105; А — 0,081, О — 0,079 и т. д. В зашифрованном тексте наибольшие частоты появления в порядке убывания имеют буквы R — 0,12; О — 0,09, А и N по 0,07.

Естественно предположить, что символом R зашифрована буква Е, символом О — букв Т и т. д. Это действительно соот­ветствует таблице замены. Дальнейшая расшифровка не составляет труда. Эти методы дешифровки хорошо известны из клас­сической литературы (см., например, Артур Конан Дойль «Пля-ущие человечки», или Алан Эдгар По «Золотой жук»).

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

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

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

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

Самая простая перестановка — написать исходный текст за­дом наперед и одновременно разбить шифрограмму на пятерки букв. Например, из фразы

ПУСТЬ БУДЕТ ТАК, КАК МЫ ХОТЕЛИ

получится такой шифротекст:

ИЛЕТО ХЫМКА ККАТТ ЕДУБЬ ТСУП.

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

ПУСТЬ-БУДЕТ-ТАККА-КМЫХО-ТЕЛИО.

Тогда шифрограмма, несмотря на столь незначительное из менение, будет выглядеть по-другому:

ОИЛЕТ ОХЫМК АККАТ ТЕДУБ ЬТСУП

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

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

Криптографические стандарты

Широко известны алгоритмы блочного шифрования, приня­тые в качестве государственных стандартов шифрования данных в США и России.

Data Encryption Standart. В 1973 г. Национальное бюро стан­дартов США начало разработку программы по созданию стан­дарта шифрования данных на ЭВМ. Был объявлен конкурс сре­ди фирм-разработчиков США, который выиграла фирма IBM, представившая в 1974 г. алгоритм шифрования, известный под названием DES (Data Encryption Standart).

Входные 64-битовые векторы, называемые блоками откры­того текста, преобразуются в выходные 64-битовые векторы, на­зываемые блоками шифротекста, с помощью двоичного 56-би­тового ключа К. Число различных ключей DES-алгоритма равно 2⁵⁶>7- 10¹⁶.

Алгоритм реализуется в течение 16 аналогичных циклов шифрования, где на i - u цикле используется цикловой ключ А,-, представляющий собой алгоритмически вырабатываемую выбор­ку 48 битов из 56 битов ключа К_;, i = 1,2,..., 16.

Алгоритм обеспечивает высокую стойкость, однако недавние результаты показали, что современная технология позволяет создать вычислительное устройство стоимостью около 1 млн долларов США, способное вскрыть секретный ключ с помощью пол­ного перебора в среднем за 3,5 часа.

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

DES-алгоритм явился первым примером широкого произ­водства и внедрения технических средств в области защиты ин­формации. Национальное Бюро Стандартов США организовало проверку аппаратных реализаций DES-алгоритма на специаль­ном тестирующем стенде. Только после положительных резуль­татов проверки производитель получает от Национального Бюро Стандартов сертификат на право реализации своего продукта. К настоящему времени аттестовано несколько десятков изделий, выполненных на различной элементной базе.

Достигнута высокая скорость шифрования. По некоторым сообщениям, имеется микросхема, реализующая DES-алгоритм со скоростью 45 Мбит/с. Велика доступность этих изделий: стои­мость некоторых аппаратных реализаций ниже 100 долл. США.

Основные области применения DES-алгоритма:

• хранение данных в ЭВМ (шифрование файлов, паролей);

• аутентификация сообщений (имея сообщение и кон­трольную группу, несложно убедиться в подлинности со­общения);

• электронная система платежей (при операциях с широкой клиентурой и между банками);

• электронный обмен коммерческой информацией (обмен данными между покупателем, продавцом и банкиром за­щищен от изменений и перехвата).

ГОСТ 28129-89. В 1989 г. в СССР был разработан блочный шифр для использования в качестве государственного стандарта Шифрования данных. Разработка была принята и зарегистриро­вана как ГОСТ 28147—89. И хотя масштабы применения этого ЭДгоритма шифрования до сих пор уточняются, начало его внедрению, в частности, в банковской системе, уже положено. Алгоритм несколько медлителен, но обладает весьма высокой стойкостью.

Блок-схема алгоритма ГОСТ отличается от блок-схем DES-алгоритма лишь отсутствием начальной перестановки и числом циклов шифрования (32 в ГОСТе против 16 в DES-алг ритме).

Ключ алгоритма ГОСТ — это массив, состоящий из 32-мео ных векторов X ₁, Х₂,..., Х₈. Цикловой ключ i -го цикла K_i равен Х _S, где ряду значений i от 1 до 32 соответствует следующий ряд зна­чений s:

1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8,8, 7, 6, 5, 4, 3, 2, 1.

В шифре ГОСТ используется 256-битовый ключ и объем ключевого пространства составляет 2²⁵⁶. Ни на одной из сущест­вующих в настоящее время или предполагаемых к реализации в недалеком будущем ЭВМ общего применения нельзя подобрать ключ за время, меньшее многих сотен лет. Российский стандарт проектировался с большим запасом и по стойкости на много по­рядков превосходит американский стандарт DES с его реальным размером ключа в 56 бит и объемом ключевого пространства всего 2⁵⁶. В свете прогресса современных вычислительных средств этого явно недостаточно. В этой связи DES может пред­ставлять скорее исследовательский или научный, чем практиче­ский интерес.

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