Традиційна криптосистема за Шенноном

Вступ

Література.

Час – 2 год.

Навчальні питання

Лекція 1. Загальні відомості про криптологічні системи

Таблиця 10.3.9

[1] Элемент, степени которого пробегают все ненулевые элементы поля, называется примитивным элементом

1.... Класифікація криптологічних систем (алгоритмів) 2

2.... Традиційна криптосистема за Шенноном.. 4

3.... Статистичний опис джерела відкритих текстів. 8

1. Тилборг ван Х.К. Основы криптологии. Профессиональное руководство и интерактивный учебник. — М.: Мир, 2006, с. 10 - 19

2. К. Шеннон «Работы по теории информации и кибернетике», М., ИЛ, 1963, с. 333-369.

3. Konheim A.G. Cryptography, a Primer, John Wiley &; Sons, New York, etc., 1981.

4. Bauer F.L. Decrypted Secrets; Methods and Maxims of Cryptology, Springer Verlag, Berlin, etc., 1997.

5. Henk C.A. van Tilborg, FUNDAMENTALS OF CRYPTOLOGY. A Professional Reference and Interactive Tutorial. Eindhoven University of Technology. The Netherlands. KLUWER ACADEMIC PUBLISHERS, Boston/Dordrecht/London.

6. Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке С. – М.: Издательство ТРИУМФ, 2003

Криптология, объединяющая криптографию и криптоанализ, долгое время была секретной областью знаний в Советском Союзе. Преподавать криптографию имел право только ИКСИ — институт криптографии, связи и информатики (бывший технический факультет академии КГБ-ФСБ). Положение в корне изменилось лишь в 1990-х годах, когда стало невозможно игнорировать экстенсивное развитие компьютерных сетей, вызвавшее потребность банков, промышленных и коммерческих фирм, частных лиц в квалифицированной защите информации, чтобы предотвращать получение конфиденциальных данных неправомочными лицами и организациями, а также исключать фальсификацию и злонамеренное искажение данных. Именно в те годы некоторым гражданским вузам разрешили принять участие в подготовке криптологов, и были введены новые математические специальности в области защиты информации и компьютерной безопасности.

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

Год 1976-й стал, так сказать, "точкой бифуркации" (или "ветвления") процесса развития криптографии: Диффи и Хеллман предложили общую революционную концепцию (асимметричных) криптосистем с публичными ключами (public key cryptosystems), а также дали пример подобной системы для выработки общего секретного ключа; соответствующий протокол использует публичные каналы связи (скажем, газетные объявления). В криптосистемах с публичными ключами каждый пользователь сети имеет два ключа: секретный ключ для дешифрования и создания цифровой подписи и публичный ключ , с помощью которого другие пользователи шифруют сообщения для и проверяют его подпись. Ключ публикуется, например, в общедоступном каталоге на некотором сервере. (В России ключ часто называют "открытым", что вызывает смысловой диссонанс с "открытым" текстом, который в системах секретности (т.е. системах шифрования-дешифрования) обычно — в отличие от публичного ключа — секретен либо защищен цифровой подписью или кодом аутентификации.)

Начиная с конца 1970-х годов хлынул поток работ о криптосистемах с публичными ключами. Важно отметить, что безопасность всех таких систем зиждется на математических гипотезах о практической невозможности решения тех или иных вычислительных проблем. Например, система Диффи-Хеллмана основана на проблеме дискретного логарифмирования в конечном поле, RSA-система — на проблеме факторизации составного числа, были разработаны и реализованы криптосистемы, основанные на кодах Гоппы, исправляющих ошибки, на NP-полной проблеме "укладки рюкзака" и т.д. Теперь в сферу криптологии оказались вовлечены теория чисел и алгебра, и это резкое расширение математического инструментария вызвало большой интерес не только у специалистов, но и у многих математиков, ранее далеких от криптологии.

1. Класифікація криптологічних систем (алгоритмів)

Прежде чем приступить к классификации криптологических систем следует сделать некоторые замечания. По этапам развития можно выделить три периода развития:

· первый этап – этап донаучной криптологии (до 1949 г.);

· второй этап – этап научной криптологии с секретными ключами (с 1949 г. по семидесятые годы);

· третий этап – этап научной криптологии с использованием ЭВМ (с семидесятых по настоящее время).

Конечно, такое разделение достаточно условно, но оно учитывает основные события, повлиявшие на развитие криптологии как науки. Если в древнем мире криптологией занимались как искусством, то после опубликования знаменитой статьи К.Шеннона криптология стала наукой. Прорыв в криптоанализе был произведен с момента возникновения ЭВМ. Следует отметить, что первые опыты такого рода были предприняты во время второй мировой войны. В Англии в 1942 году вступили в строй несколько специализированных для взлома шифров ЭВМ, специально созданных для этого Аланом Тьюрингом. Это была первая в мире довольно быстродействующая ЭВМ под названием "Колосс". После этого английские криптоаналитики могли меньше чем за день вскрыть любую шифровку немецкой шифровальной машины Энигма.

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

На первом этапе развития криптологии существовало два основных типа преобразований открытых текстов – замены и перестановки.

Шифров перестановки известно достаточно большое количество – это и шифр «скитала» и шифрующие таблицы и др. Главная идея шифров перестановки является замена местоположения символов открытого текста.

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

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

· блочные

· и поточные шифры.

В блочных шифрах открытый текст разбивался на блоки фиксированной длины и подвергался шифрованию. Причем каждый блок шифровался своим шифром, но алгоритм перемешивания оставался одинаковым для всех блоков. На этом принципе построено большое количество шифров, включая американский стандарт DES и российский стандарт ГОСТ 28147-89. В блочных шифрах широко используется перемешивание.

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

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

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

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

Классификация алгоритмов шифрования представлена на рис 1.

Рис. 1. Классификация алгоритмов шифрования

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

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

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

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

Целостность: это означает, что получатель некоторых данных имеет свидетельство, что третьей стороной не было сделано никаких изменений.

Формальное определение традиционной криптосистемы, так же как и математические основы соответствующей теории, принадлежат Шеннону. На рис. 1.1 изображена общая схема традиционной криптосистемы, а на рис. 1 – оригинальная схема криптосистемы из статьи Шеннона [2].

Рис. 1.1. Традиционная криптосистема

Рис. 2. Схема общей секретной системы [2]

Остановимся на таких понятиях как язык и текст.

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

Конкатенация букв из будет называться -граммой и обозначаться посредством . Частными случаями являются биграммы ( ) и триграммы ( ). Множество всех -грамм над обозначается через .

Текст — это элемент из . Язык — это подмножество в . В случае языков программирования такие подмножества точно определяются рекурсивными правилами. В случае разговорных языков правила весьма вольные.

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

Пусть — сообщение (текст из ), которое Алиса на рис. 1.1 хочет секретно передать Бобу. Обычно оно называется открытым текстом (plaintext). Сначала Алиса преобразует открытый текст в так называемый шифртекст (ciphertext) (или криптограмму) . Этот шифртекст она и передает Бобу.