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

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

Рассмотренная процедура повторяется для каждого уровня проектирования, приводя в конечном итоге к варианту с оптимальной структурой.

Криптография появлиась одновременно с письменностью в древних государствах: Индии и Египте. Использовались перестановки, замена букв.

4-6 вв. Греция и Спарта

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

Шифр-тиблицы Энея. Он придумал книжный шифр.

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

Шифр Цезаря – сдвиг алфавита на 3 и замена сдвинутой буквой.

Аристотелю приписывалось дешифрование с сциталы (использовался конус).

Применение криптографии в древности было случайным.

В арабском мире криптографический анализ систематически разрабатывался, в Европе о нем узнали позже.

Эпоха возрождения

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

15 в.

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

16в.

В Германии появилась первая печатная книга по криптографии.

Появилась идея многоалфавитной замены.

Шифр сеньора Белазо – номер пароля означал номер применяемой замены.

Начало 16 в.

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

Кордано впервые предложил использовать сам открытый текст в качестве ключа. Шифр решетка Кордано Привел доказательства оценки стойкости ключей на основе числа ключей.

Начал появляться научный криптоанализ. Потребители: военно-дипломатическая и финансовая сфера.

17-18 вв. Эра «черных кабинетов».

Появление дешифровальных отделений.

Наполеон во время походов использовал таблицу кодов.

В России дешифровальные отделения появились при Иване Грозном. Шифры применяли замены и перестановки.

Реорганизация при Петре – привлекались математики Гольбах и Эйлер. Для криптографии эти открытыия еще не использовались.

18 в.

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

19 в.

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

Гаммирование – парольная фраза (фиксированный отрезок). Фраза разбивается на такие же отрезки, вычиляется гамма. Бит информации складывается с битом гамма.

Шифр Вижнера – частный случай гаммирования.

Керкгоффс выдвинул принципы:

- только криптоаналитики могут судить о качестве шифра,

- разделение алгоритма и ключа.

Нужно доверять только секретному ключу, не доверять алгоритму.

80е гг. 19 в.

Криптографию изучает военная академия.

Открытия в математике, применение механических устройств, развитие статистических методов.

20 в.

Криптография стала механической, затем – электрической.

Доступ к зашифрованным текстам, легко вклиниться в связь.

К Первой мировой войне криптография не успела еще хорошо развиться.

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

Элетро – механическая машина «Нигма» представляла собой набор 25 дисков.

Тьюринг изобрел первый компьютер.

20 в.

Работы Шенона. Он придумал принцип рассеивания и перемешивания, которые используются сейчас (маленькое изменение текста должно рассеиться по всему тексту через несколько итераций). Ввел понятие стойкости текста, избыточности информации(можно убрать 25% английского текста без потери смысла).В зашифрованном тексте вероятность появления буквы должна приближаться к 0,5.

1929г. - труд Шенона «Математическая теория криптографии».

Понятие совершенной секретности: априорные знания противника совпадают с апостериорными. Понятие количества информации понимает как вероятностное – не очень верно.

Самый краткий способ описать инофрмацию – количество информации - Коломогоров:

- количество информации по Колмогорову

Шенон использовал вероятностные характеристики текста, Колмогоров – смысловое содержание.

По Шенону идеальный шифр – шифр Вернома (лента одноразового использования).

Так как ключ должен иметь размер текста, то его сложно передать, поэтому на пратике не используется.

30 гг. Появились телефонные шифраторы.

50 гг. Появились электронные устройства, появилась потребность в новых исследованиях.

Так как компьютеры обрабатывали информацию блоками, то появились блочные шифры.

78 г. DES (Data Encryption Standard)– не военный шифр.

Метод вскрытия не больше сложности, то есть не меньше 16 циклов, длина блока 64 бита.

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

Сейчас появились алгебраические методы.

70 гг. Появилась работа Диффи и Хеллмана. Они предложили криптографию с открытым ключом, также предложили процедуру установления ключа.

Использовали возведение в степень по модулю:

Если знаем a, b и n, то нет эффективных способов найти x – задача дискретного логарифмирования.

Криптосистема с открытым ключом Меркля – Хелламана – представить число в виде суммы чисел заданного набора. Эта задача является NP – сложной.

Обобщили утсановление ключа – критографический протокол.

Односторонняя функция: вычислить легко, обратно – сложно.