Краткая история развития криптографических методов.

Исторически сложились и дошли до наших дней три подхода к защите информации.

1. Физическая защита носителя информации.Данный подход предполагает использование комплекса различных средств защиты, а также нестандартной передачи и хранения информации (голуби, курьеры, сейф, проводная и кабельная связь, «радиовыстрел», СИЧ - передача и другие). Одновременно, при данном подходе разрабатывались и методы уничтожения информации при угрозе ее захвата, а также методы обнаружения тайной перлюстрации. Идеалом данного метода является создание защищенного канала передачи информации, к которому противник физически не в состоянии получить доступа.

2. Стеганография.Данный подход предполагает применения комплекса средств, при помощи которых скрывается сам факт передачи информации (симпатические чернила, «микроточка» и т.д.). Идеал данного подхода – создание скрытого канала связи. Здесь заслуживает здесь внимания предложение греческого полководца Энея (Спарта, V – IV вв. до н. э.). Наряду с известным «диском Энея», который представлял собой шифр замены букв на расстояние между узелками на послании - нити, он предложил и такой способ. На «невинном» тексте, который обычно писался на деревянных дощечках, покрытых воском, мелкими, малозаметными точками отмечались буквы, несущие секретное сообщение. Эту идею уже в XVI веке повторил английский государственный деятель Ф.Бэкон. Вместо точек он, предложил известный «двухшрифтовый шифр», где использовались два малоразличимых шрифта. Заслуга Бэкона заключается также и в том, что он первый предложил кодировать буквы латинского алфавита двоичным кодом. Эта идея широко используется и в наши дни. Дальнейшее развитие идей Энея привело к появлению так называемых книжных шифров. Они уже многократно описаны и дошли до наших дней. Немцы в начале XX века использовали в агентурной переписке эти шифры, в которых вместо невидимых точек, проколов в тексте прикрытия значимые буквы выделялись невидимой точкой, поставленной с использованием симпатических чернил. Недостаток книжных шифров - необходимость постоянно иметь с собой заранее оговоренную книгу. Поэтому появились его разновидности: стихотворный шифр, шифр по слову лозунгу и т. д. Здесь стеганография объединяется с криптографией. Ключом шифра является книга, стихотворение, слово - лозунг и т.д. Сам "шифрованный текст" имеет невинный вид.

3. Криптография. Этот подход предполагает использование шифров. Идеал – использование открытого канала связи. При этом противник, зная о факте передачи и имея физический доступ к информации не может понять ее смысла, если не владеет секретным ключом.

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

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

Перейдем к краткому изложению исторической эволюции шифров.

В древнем мире появились два основных вида шифров:

- шифры замены;

- шифры перестановки.

Класическим примером шифра замены является шифр Цезаря (около I века до нашей эры). Этот шифр задается подстановкой следующего вида (применительно к латинскому алфавиту):

Верхний алфавит - это алфавит отрытого текста. Нижний алфавит, представляющий собой циклический сдвиг верхнего алфавита влево на 3 шага, есть алфавит шифрованного текста. Буква А открытого текста заменялась на букву D в шифрованном, буква В - на букву Е и т.д. Все буквы открытого текста заменялись по этой подстановке. В связи с этим этот шифр в последующем стал называться шифром простой (одноалфавитной) замены. В наши дни под шифром Цезаря понимаются все шифры, в которых нижняя строка является циклическим сдвигом верхней на произвольное число шагов. Однако поскольку этот сдвиг не меняется в процессе шифрования, то шифр остается шифром простой (одноалфавитной) замены.

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

Шифр усложнился, в нем появилось

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

Возникла идея построения "псевдослучайного" алфавита шифрованного текста В качесиье ключа Вл;бирился легко запоминающийся пароль. Haпример слово «THE TABLE". Это слово без повторов букв выписывалось в нижней строке:

THEABL......

Затем к нему добавлялись пропущенные буквы алфавита:

THEABLCDF......Z.

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

Атбаш– шифр некоторых фрагментов библейских текстов. Правило зашифрования: i-я буква алфавита заменялась буквой с номером n – i + 1, где n – число букв алфавита. Один из простейших шифров простой замены.

Табличка и диск Энея – (Спарта, V – IV вв. до н. э.). Приспособления с нанесенным алфавитом (ключевой элемент), на которые наматывалась нить с узелками напротив соответствующих букв. Шифрвеличины – расстояния между узелками.

Квадрат Полибия – (Древняя Греция). Таблица с буквами алфавита, заменяемыми номерами строки и столбца (i, j). Один из простейших шифров простой замены.

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

Дальнейшее развитие шифров замены пошло по пути появления многоалфавитности шифрованного текста, а также введения так называемого биграммного шифрования. Впервые эту идею (биграммности) предложил в 1563 году итальянец Порта. Открытый текст разбивался на пары букв (при необходимости к нему добавлялась произвольная буква алфавита). Шифром являлась таблица размером Z x Z (26 х 26 = 676 клеток). В каждую клетку помещался один из 676 заранее придуманных экзотических знаков (геометрические фигуры, образы и т.д.). Первая буква пары определяла строку таблицы, вторая ее столбец. На их пересечении и находился шифрованный знак. Ввиду громоздкости и сложности практического применения этот шифр не нашел распространения. Весомый вклад в биграммное шифрование внес англичанин Уитстон. Он использовал в 1854 году в своем шифре PlayFair (честная игра) простой квадрат размером 5x5=25 (редуцированный латинский алфавит, в котором буква J отождествлялась с буквой I). В таблице в произвольном (ключевом) порядке располагались 25 букв алфавита. Биграмма, лежащая в одной строке, заменялась биграммой из букв, находящихся циклически справа от букв открытого текста. Биграмма, лежащая в одном столбце, также шифровалась по правилу циклического сдвига столбца сверху вниз. Биграммы, расположенные в разных строках и столбцах, заменялись на буквы, стоящие в противоположных углах прямоугольника, построенного на исходной биграмме. Это было существенным усилением шифров побуквенной замены. Тем не менее, этот шифр является шифром простой замены, но на уровне биграмм.

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

Следующий шаг в развитие идеи многоалфавитности шифров внес в 1518 году аббат Тритемий (Германия). Он предложил использовать шифр, вошедший в историю как «таблица Тритемия». Строится квадрат размером Z x Z (26 х 26). Первая строка квадрата есть естественный алфавит. Вторая строка - сдвиг первой (по циклу) на одну букву влево. Последующие строки также являются циклическими сдвигами предыдущей строки. При шифровании первой буквы открытого текста используется первая строка, при шифровании второй - вторая и т.д. При зашифровании Z+1 - ой (27 - буквы) буквы производится возврат к первой строке. Таким образом, алгоритм шифрования является периодическим с периодом Z. Заметим также, что алгоритмы шифрования и расшифрования различны.

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

Француз де Виари выдвинул идею формализации процесса шифрования по шифру Виженера. По сути дела он предложил математическое представление процесса шифрования. В современном изложении эта идея сводится к следующему.

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

Итак, пусть шифруется открытый текст:

p = p₁p₂… p_п , p_i.Î A = {0,1,2,…,25}

(применительно к латинскому алфавиту).

Гамма шифра имеет вид:

k = k₁k₂… k_m , k_i.Î A

Тогда шифрование по шифру Виженера имеет следующее представление. При использовании таблицы Тритемия:

C = E(p) = (p + k_i) mod 26

где p - i-я буква шифрованного текста. При расшифровании имеем:

p = D(C) = (C – k_i) mod 26.

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

При использовании таблицы Бофора получим:

C = E(p) = (k – p) mod 26

p = D(C) = (k – C) mod 26.

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

Офицер прусской армиии Казисский (XIX век), а затем и известный криптограф США Фридман продемонстрировали эффективные способы дешифрования шифров короткопериодического гаммирования. Поэтому в дальнейшем возникла проблема создания гаммы большого периода, образумой из короткого ключа - лозунга. Эта идея и реализуется в современных шифраторах. Значительный вклад в развитие многоалфавитных шифров внес в начале XIX века американец Джефферсон (будущий президент США). Шифратор Джефферсона представлял собой 25 – 36 дисков одинакового размера с пермемешанными алфавитами на боковой поверхности. Множество ключей – расстановка букв на дисках, расстановка дисков на оси, выбор набора дисков из запаса.

Предложенный способ (прибор) дискового шифрования получил широкое распространения в XX веке (дисковые шифраторы, «Энигма», «Хагелин»).

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

Примеры шифров многозначной замены:

Омофоны – (Италия, XIV век) - Гласным буквам соответствует несколько различных шифрвеличин. Автор Чикко Симонетти.

Шифры пропорциональной замены - (Италия, XV век) – Каждой букве ставится в соответствие несколько шифрвеличин, в зависимости от частоты, с которой эта буква встречается в тексте. Автор Габриэль де Лавинда. (Аналог - Миланский ключ – 1469 г).

Шифр Ардженти – (17 век) Внедрено смешение алфавита сдвигом от ключевого слова, введены "пустышки" для изменения частотных характеристик текста, многозначная замена, буквенный код.

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

Шифры перестановки также получили заметное развитие и дошли до наших дней. Классический пример такого шифра - шифр Сцитала (изобретение спартанцев примерно IV век до нашей эры): ремешок навивался на цилиндр (деревянный или металлический). Итальянец Кардано уже в середине XVI столетия предложил новый шифр перестановки - известную «решетку Кардано». В основе лежало решение кубического уравнения вида x³ + px + q = 0, предложенного другим итальянским математиком Тарталья:

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

Далее появились шифры перестановки по лозунгу. Здесь буквы шифра переставлялись по ключу - лозунгу, по которому составлялся так называемый номерной ряд. Пусть, например лозунг есть слово "THE TABLE". В нем 8 букв. Пронумеруем буквы лозунга в соответствии с их алфавитным порядком. Получим номерной ряд: 75381264. Открытый текст разбивается на блоки из 8 букв. Первая буква блока встает на 5 - место, вторая - на 6 - е, третья на 3 - е, четвертая - на 8 - е и т.д. При необходимости открытый текст добавляется произвольным набором букв до числа, кратного 8. К XX веку эти шифры усложнились. Появились так называемые маршрутные перестановки, шифры вертикальной перестановки и т.д.. Они детально описаны в изданиях на тему о криптографии.

На развитие криптографии оказывает большое влияние научно - технический прогресс. Изобретение книгопечатания породило шифры, основанные на ключе - книге (книжный шифр, книжная гамма, книжный код и т.д.). Появление телеграфа, радио, телефона дало мощный стимул к разработке новых шифров. Особое влияние на развитие криптографии оказали ЭВМ, распространившимися в середине XX века. Заметим кстати, что первая в мире современная ЭВМ ("Колосс", Великобритания) была разработана в процессе проведения английской операции "Ультра" - дешифрование основного шифратора фашистской Германии ("Энигма"). Появились следующие новые виды шифраторов:

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

Электронные шифраторы, программные реализации. Аппаратные реализации на основе микросхем СБИС. Программные реализации – несколько позже. Самая известная и заметная программная реализация – PGP Фила Циммермана.

Развитие математики привело к становлению криптографии как точной математической науки. Здесь следует упомянуть в первую очередь имена У.Фридмана и К.Шеннона (США). Клод Шеннон в 1944 году в своем труде «Теория секретных систем связи» формализовал задачи синтеза и анализа шифров. Там же были введены понятия принципов рассеивания и перемешивания (конфузия, диффузия), теоретической и практической стойкости, совершенного шифра. Введено рассмотрение языка как вероятностный процесс. Предложена концепция избыточной информации естественного языка. (The, of, and, to, a, in, that, it, is, i – более 25% слов любого английского текста в любой криптограмме.) Определена теоретическая мера стойкости – энтропийная характеристика (неопределенность шифра по открытому сообщению). Энтропия показывает насколько "близка" средняя криптограмма и N букв к единственному "решению". Также введено понятие расстояния единственности – минимального размера криптограммы, необходимого для однозначного расшифрования (для совершенного шифра - бесконечность). Разделены понятия теоретической и практической стойкости. Задолго до Шеннона – советский академик А. А. Марков предложил марковские модели - зависимость появления букв в тексте от предыдущих букв. А в 60-е годы – А. Н. Колмогоров, различие удельной энтропии на букву для текстов разного смыслового содержания.

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

В XX веке криптографическая деятельность вышла из под контроля государства. Появились частные фирмы - производители шифртехники на продажу и их специфические пользователи (корпорации, банки и т.д.). Наряду с лояльными пользователями криптографическими методами начали использовать и криминальные структуры. Государство не может отказаться от контроля за их деятельностью. Появилась проблема вида: "государственная и негосударственная" криптография. Был разработан ряд криптографических стандартов. Первым шагом явилась публикация DES – стандарта на симметричный блочный комбинированный криптоалгоритм. В XXI веке выходит стандарта AES. Также публикуются стандарты цифровой подписи DSS и распределения ключей X.509. Ряд таких стандартов, как: EES – стандарт с депонированием ключей, микросхема Clipper, плата Fortezza – явились попыткой правительства США (администрация Клинтона) взять под контроль ключевую систему в криптосистемах связи. В нашей стране также вышли стандарты ГОСТ на блочный алгоритм шифрования, криптографическую хэш-функцию и схему электронно-цифровой подписи.

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

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

В XX веке сформировались основные требования к шифрам. Эти требования прежде всего включают в себя следующую триаду.

1 .Криптографическая стойкость. Это способность шифра противостоять попыткам его дешифрования. Оно обычно является основным.

2. Имитостойкость. Это способность шифра противостоять попыткам "дезинформации под шифром" (имитостойкости). Цель имитации — внедрение противником дезинформации под шифром. В истории есть немало примеров такой тактики нападения.

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

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

В 1976-78 г.г. революционные идеи У. Диффи и М. Хеллмана привели к появлению ассиметричной криптографии. В настоящее время криптосистемы делятся на симметричные (классические) и ассимметричные (с открытым ключом). Проиллюстрируем принципиальную разницу между первыми и вторыми. На рис. 1. приведена схема передачи шифрованной информации при помощи симметричного шифра.

Источник сообщений – владелец информации, осуществляющий преобразование информации (шифрование) и передачу получателю шифрованных сообщений с целью защиты информации от противника,который может наблюдать передаваемые по каналу связи сообщения. Исходная информация называется открытым текстом (x), шифрованная информация – шифртекстом (y). Стороны, обменивающиеся информацией, по усмотрению выбирают шифр и ключи (k). Секретные ключи предварительно рассылаются по защищенному каналу связи. Симметричные системы используют один секретный ключ для зашифрования и расшифрования.

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

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

Рис. 1. Схема симметричного шифрования.

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

Рис.2. Схема асимметричного шифрования.

В связи с развитием современной и сложной техники защиты информации появилась потребность в подготовке соответствующих специалистов, разрабатывающих и реализующих эту технику на практике. В целях обучения таких специалистов для органов государственной службы в нашей стране создан ИКСИ Академии ФСБ РФ. Одновременно "азы" защиты информации преподают уже многие ВУЗы страны (МГУ, МИРЭА, РГГУ, МИФИ и др.). Однако следует отметить, что доступ к наиболее важным криптографическим секретам государство охраняет режимом строгой секретности (как, впрочем, и в ведущих странах Запада). Слушатели ИКСИ получают возможность ознакомления с некоторыми из этих секретов.

Параллельно с развитием криптографической деятельности развивались и соответствующие государственные структуры. В нашей стране государственные криптографические службы прошли довольно сложный путь эволюции. Многочисленные реорганизации повредили их нормальному развитию. В последнее время основным органом нашей страны являлось Федеральное Агентство правительственной связи и информации (ФАПСИ) при Президенте РФ, ныне расформированное и в основном переданное в структуру ФСБ РФ. В США стабильно развивается Агентство Национальной Безопасности (АНБ США); в Великобритании - штаб - квартира Правительственной связи и т.д.

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