Главная | Обратная связь

История криптографии

Лекция № 8. Криптография

Основы криптографии

История криптографии

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

Историю криптографии условно можно разделить на 4 этапа:

· Наивная криптография;

· Формальная криптография;

· Научная криптография;

· Компьютерная криптография.

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

Большинство из используемых шифров сводились к пере­становкеили моноалфавитной подстановке. Одним из первых зафиксированных примеров является шифр Цезаря, состоящий в замене каждой буквы исходного текста на другую, отстоящую от нее в алфавите на определенное число позиций. Другой шифр, полибианский квадрат, авторство которого приписывает­ся греческому писателю Полибию, является общей моноалфа­витной подстановкой, которая проводится с помощью случайно заполненной алфавитом квадратной таблицей (для греческого алфавита размер составляет 5x5). Каждая буква исходного тек­ста заменяется на букву, стоящую в квадрате снизу от нее.

Этап формальной криптографии(кон. XV века - нач. XX века) связан с появлением формализованных и относительно стойких к ручному криптоанализу шифров. В европейских странах это произошло в эпоху Возрождения, когда развитие науки и торговли вызвало спрос на надежные способы защиты информации. Важная роль на этом этапе принадлежит Леону Батисте Альберти, итальянскому архитектору, который одним из первых предложил многоалфавитную подстановку. Данный шифр, получивший имя дипломата XVI века Блеза Вижинера, состоял в последовательном «сложении» букв исходного текста с ключом (процедуру можно облегчить с помощью специальной таблицы). Его работа «Трактат о шифре» (1466г.) считается пер­вой научной работой по криптологии.

Одной из первых печатных работ, в которой обобщены и сформулированы известные на тот момент алгоритмы шифро­вания является труд «Полиграфия» (1508г.) немецкого аббата Иоганна Трисемуса. Ему принадлежат два небольших, но важ­ных открытия: способ заполнения полибианского квадрата (первые позиции заполняются с помощью легко запоминаемого ключевого слова, остальные - оставшимися буквами алфавита) и шифрование пар букв (биграмм).

Простым но стойким способом многоалфавитной замены (подстановки биграмм) является шифр Плейфера, который был открыт в начале XIX века Чарльзом Уитстоном. Уитстону при­надлежит и важное усовершенствование - шифрование «двой­ным квадратом». Шифры Плейфера и Уитстона использовались вплоть до первой мировой войны, так как с трудом поддавались ручному криптоанализу.

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

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

Одной из первых подобных систем стала изобретенная в 1790 году Томасом Джефферсоном, будущим президентом США механическая машина. Многоалфавитная подстановка с помощью роторной машины реализуется вариацией взаимного положения вращающихся роторов, каждый из которых осуще­ствляет «прошитую» в нем подстановку.

Практическое распространение роторные машины получили только в начале XX века. Одной из первых практически исполь­зуемых машин, стала немецкая Enigma, разработанная в 1917 году Эдвардом Хеберном и усовершенствованная Артуром Кирхом. Роторные машины активно использовались во время второй мировой войны. Помимо немецкой машины Enigma ис­пользовались также устройства Sigaba (США), Турех (Велико­британия), Red, Orange и Purple (Япония). Роторные системы - вершина формальной криптографии так как относительно про­сто реализовывали очень стойкие шифры. Успешные криптоатаки на роторные системы стали возможны только с появлени­ем ЭВМ в начале 40-х годов.

Главная отличительная черта научной криптографии(30-е - 60-е годы XX века) - появление криптосистем со строгим ма­тематическим обоснованием криптостойкости. К началу 30-х годов окончательно сформировались разделы математики, яв­ляющиеся научной основой криптологии: теория вероятностей и математическая статистика, общая алгебра, теория чисел, на­чали активно развиваться теория алгоритмов, теория информа­ции, кибернетика. Своеобразным водоразделом стала работа Клода Шеннона «Теория связи в секретных системах» (1949г.), где сформулированы теоретические принципы криптографиче­ской защиты информации. Шеннон ввел понятия «рассеивание» и «перемешивание», обосновал возможность создания сколь угодно стойких криптосистем.

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

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

Первым классом криптосистем, практическое применение которых стало возможно с появлением мощных и компактных вычислительных средств, стали блочные шифры. В 70-е годы был разработан американский стандарт шифрования DES(принят в 1978 году). Один из его авторов, Хорст Фейстел (со­трудник IBM), описал модель блочных шифров, на основе кото­рой были построены другие, более стойкие симметричные криптосистемы, в том числе отечественный стандарт шифро­вания ГОСТ 28147-89.

В середине 70-х годов произошел настоящий прорыв в со­временной криптографии - появление асимметричных крипто­систем, которые не требовали передачи секретного ключа между сторонами. Здесь отправной точкой принято считать работу, опубликованную Уитфилдом Диффи и Мартином Хеллманом в 1976 году под названием «Новые направления в современной криптографии». В ней впервые сформулированы принципы об­мена шифрованной информацией без обмена секретным клю­чом. Независимо к идее асимметричных криптосистем подошел Ральф Меркли. Несколькими годами позже Рон Ривест, Ади Шамир и Леонард Адлеман открыли систему RSA, первую практическую асимметричную криптосистему, стойкость кото­рой была основана на проблеме факторизации больших простых чисел. Асимметричная криптография открыла сразу несколько новых прикладных направлений, в частности системы элек­тронной цифровой подписи (ЭЦП)и электронных денег.

В 80-90-е годы появились совершенно новые направления криптографии: вероятностное шифрование, квантовая крипто­графия и другие.

Основные понятия и определения

Наукой, изучающей математические методы защиты инфор­мации путем ее преобразования, является криптология(kryptos - тай­ный, logos - нау­ка). Криптология разделяется на два направления - криптографиюи криптоана­лиз.

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

Аутентичность информа­ции состоит в подлинности авторстваи целостности.

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

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

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

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

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

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

· Управление ключами.

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

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

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

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

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

Пространство ключей К - это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита. Следует отличать понятия ключ и пароль.

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

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

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

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

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