История развития криптографии от шифра Цезаря до AES

Содержание

1. 1. От тайнописи к науке: истоки криптографии3
2. 2. Эра машин: от Энигмы к DES5
3. 3. Современные стандарты: от DES к AES8
4. 4. Криптография сегодня: вызовы и перспективы10

1. От тайнописи к науке: истоки криптографии

Криптография начиналась как ремесло, а не как наука. Задача стояла простая: сделать сообщение бесполезным для постороннего, даже если оно перехвачено. Следы этой практики уходят в глубокую древность. В Древнем Египте писцы сознательно искажали иероглифы в погребальных текстах, превращая надписи в головоломку. Смысл был не столько в защите данных, сколько в сокрытии имён богов от непосвящённых, однако сам принцип искажения текста уже применялся.

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

Первым задокументированным алгоритмом подстановки считается шифр Цезаря. Гай Юлий Цезарь в «Записках о Галльской войне» описал способ, которым пользовался для переписки с легионами. Суть метода в том, что каждая буква заменялась на букву, отстоящую от неё на три позиции в алфавите. А становилась Г, Б превращалась в Д, и так далее. Получатель, зная сдвиг, возвращал буквы обратно. Примечателен этот шифр не сложностью, а тем, что это полноценный алгоритм: задаётся правило преобразования открытого текста в шифротекст, и это правило описывается математически.

Средневековье добавило криптографии системности, но существенного прогресса не дало. В Европе тайнопись оставалась уделом дипломатов,

алхимиков и заговорщиков. Перелом случился в эпоху Возрождения, когда итальянские гуманисты стали рассматривать шифры как предмет изучения. Леон Баттиста Альберти, архитектор и теоретик искусства, в 1466 году выпустил трактат «О шифрах», где предложил многоалфавитную замену. Его диск из двух вращающихся колец позволял менять алфавит подстановки в зависимости от позиции символа, что делало частотный анализ почти бесполезным. Спустя столетие французский дипломат Блез де Виженер обобщил эту идею. Его шифр использовал ключевое слово для определения сдвига каждой буквы: если ключом было «LEMON», первая буква текста сдвигалась на позицию L, вторая на E, и так далее. Виженер называл своё изобретение «непробиваемым», и почти триста лет оно действительно не поддавалось вскрытию.

К XIX веку накопилось достаточно материала, чтобы криптография оформилась в дисциплину. Шифры перестали быть набором разрозненных приёмов. Появились первые классификации, и наиболее устойчивым оказалось деление на два базовых типа. Подстановка меняет символы: вместо А пишется В, вместо В пишется Г. Перестановка сохраняет буквы, но меняет их порядок, как в скитале. Всё разнообразие шифров, от военных кодов до дипломатических систем, сводилось к этим двум операциям или их сочетаниям. Эта типология, закреплённая в работах криптографов XIX века, стала основой, на которой позже появились и роторные машины, и компьютерные алгоритмы.

2. Эра машин: от Энигмы к DES

Первая половина XX века превратила криптографию из ремесла одиночек в инженерную дисциплину. Ручные шифры, где ошибка писаря сводила на нет всю работу, уступили место механизмам. Апогей этой механизации, немецкая роторная машина «Энигма», принятая на вооружение вермахтом в 1926 году. Внутри её корпуса три ротора с 26 позициями каждый соединялись через коммутационную панель, давая астрономическое число начальных настроек. Оператор выбирал конфигурацию на сутки, вводил текст, и лампочки высвечивали шифрограмму. Машина не шифровала букву одинаково дважды подряд: после каждого нажатия роторы поворачивались, меняя электрическую цепь. Это был колоссальный шаг вперёд по сравнению с ручными таблицами.

Однако именно автоматизация породила фатальные слабости. Главная из них, симметрия: шифрование и дешифрование были зеркально идентичны при одинаковой настройке. Криптоаналитики союзников быстро поняли, что буква никогда не шифруется сама в себя. Добавим сюда процедурные ошибки немцев: использование шаблонных приветствий, повторяющихся ключей и метеосводок. Эти «крючки» превращали стойкий на бумаге шифр в решаемую головоломку. Польские математики во главе с Марьяном Реевским ещё в 1932 году построили первые дешифровальные машины, используя математическую теорию групп. Их работа легла в основу того, что сделал Алан Тьюринг в Блетчли-Парке.

Тьюринг подошёл к задаче как к логической проблеме, а не как к упражнению в терпении. Его «Бомба», электромеханический аппарат весом в тонну, не искала ответ перебором всех настроек. Вместо этого машина использовала известные открытые тексты и метод «криб»: предположение о фрагменте сообщения, которое отсекало миллионы невозможных комбинаций. «Бомба» проигрывала возможные положения роторов, проверяя логические противоречия. Когда находилось согласование, настройка

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

После войны наступила эпоха электроники, но криптография оставалась закрытой сферой военных ведомств. В 1970-х годах бизнес и банки потребовали стандартизации. Так в 1977 году Национальное бюро стандартов США приняло DES, Data Encryption Standard. Разработанный в IBM на основе более ранней системы «Люцифер», DES стал первым блочным шифром, открыто опубликованным для всеобщего использования. Его архитектура опиралась на сеть Фейстеля: блок данных в 64 бита делился на две половины, которые итеративно перемешивались через 16 раундов с подстановками и перестановками. Ключевая особенность сети Фейстеля в том, что шифрование и дешифрование используют одну и ту же структуру с инвертированным порядком ключей. Это позволяло реализовать алгоритм даже на слабом железе того времени.

Но у стандарта был врождённый порок. Длина ключа составляла всего 56 бит. Для 1977 года это выглядело солидно: перебор 72 квадриллионов комбинаций казался невозможным. Однако уже в 1993 году Майкл Винер спроектировал специализированную машину для полного перебора стоимостью около миллиона долларов. К 1998 году Electronic Frontier Foundation собрала компьютер «Deep Crack» за 250 тысяч долларов, который взломал DES за 56 часов. Позже распределённая сеть добровольцев сократила это время до 22 часов. Проблема была не в архитектуре Фейстеля, а именно в коротком ключе. Криптография упёрлась в закон Мура: вычислительная мощность росла быстрее, чем способность DES ей противостоять. Институт стандартов продлил жизнь алгоритму тройным DES, но это было полумерой.

Потребовался принципиально новый подход, который появится только в следующем десятилетии с приходом AES.

3. Современные стандарты: от DES к AES

DES продержался стандартом почти два десятилетия, но к концу XX века его судьба была решена. Ключ длиной 56 бит, когда-то казавшийся неприступным, перестал быть таковым: уже в 1999 году проект Electronic Frontier Foundation вскрыл DES примерно за сутки, перебрав все возможные комбинации на специально собранной машине. Атака полного перебора стала не теоретической угрозой, а реальным инструментом. Промышленность и правительственные структуры нуждались в новом алгоритме, который выдержал бы натиск растущих вычислительных мощностей.

Национальный институт стандартов и технологий США (NIST) объявил открытый конкурс в 1997 году. К участию приглашались криптографы со всего мира, условия были жёсткими: кандидат должен быть симметричным блочным шифром, поддерживать ключи от 128 бит и выше, работать быстро на разнообразном оборудовании и не иметь задокументированных слабостей. Из пятнадцати поданных алгоритмов в финал вышли пять, а победителем в октябре 2000 года был признан Rijndael, разработанный бельгийцами Йоаном Даеменом и Винсентом Рейменом. Годом позже NIST официально утвердил его как стандарт AES (Advanced Encryption Standard) в документе FIPS 197.

AES устроен принципиально иначе, чем предшественник. DES опирался на сеть Фейстеля, где половина блока проходит через функцию шифрования, а затем результаты перемешиваются. Rijndael использует подстановочно-перестановочную сеть: каждый байт данных проходит через нелинейную замену (S-блок), затем строки и столбцы матрицы состояния циклически сдвигаются и перемешиваются. Все операции выполняются над байтами, что делает алгоритм удобным для реализации и на 8-битных микроконтроллерах, и на 64-битных процессорах. Длина блока фиксирована и составляет 128 бит, а длина ключа выбирается из трёх вариантов: 128, 192 или 256 бит. Количество раундов зависит

от ключа: 10 для 128-битного, 12 для 192-битного и 14 для 256-битного.

Устойчивость AES к криптоанализу проверена двадцатилетней практикой. Известные атаки, такие как связанные ключи или боковые каналы, требуют либо специфических условий, либо огромных вычислительных ресурсов. Полный перебор 128-битного ключа даёт 3,4 на 10 в 38 степени комбинаций, что недостижимо даже для распределённых сетей. При этом алгоритм демонстрирует впечатляющую скорость: программные реализации обрабатывают более гигабайта данных в секунду на современных процессорах, а аппаратные ускорители встраиваются прямо в чипы, например, в наборы инструкций AES-NI от Intel и AMD.

Переход с DES на AES не был тривиальной заменой строки кода. Существующее программное обеспечение, написанное под DES, требовало переработки, а аппаратные модули, использовавшиеся в банкоматах, платежных терминалах и военной технике, подлежали замене. Компании несли затраты на миграцию, но они окупились: AES стал универсальным стандартом, принятым не только в США, но и в ISO, и в рекомендациях множества международных организаций. Он лёг в основу протоколов TLS, IPsec, шифрования дисков BitLocker и FileVault. Долгосрочная безопасность, которую обеспечил AES, позволила не менять стандарт уже более двадцати лет, что само по себе является уникальным достижением в быстро меняющемся мире криптографии.

4. Криптография сегодня: вызовы и перспективы

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

Сегодня криптография решает куда более широкий круг задач, чем простое сокрытие текста. Симметричные шифры вроде AES защищают данные, но они требуют безопасного канала для передачи ключа. Эту проблему решило асимметричное шифрование, предложенное в 1976 году Уитфилдом Диффи и Мартином Хеллманом. Оно использует пару ключей: открытый для шифрования и закрытый для расшифровки. Дополняют картину хэш-функции, которые превращают сообщение любой длины в строку фиксированного размера. Они позволяют проверить целостность данных: малейшее изменение исходного файла ведёт к полному изменению хэша. На этих трёх основах (симметричные и асимметричные схемы, хэши) построены протоколы, обеспечивающие работу цифровых подписей, защищённых соединений HTTPS и систем электронных платежей.

Однако у этой стройной системы есть уязвимое место. В 1994 году математик Питер Шор опубликовал алгоритм, который способен разложить большое число на простые множители за полиномиальное время, но только при условии наличия квантового компьютера достаточной мощности. Именно на сложности этого разложения держится безопасность алгоритма RSA, самого распространённого представителя асимметричного шифрования. Создание устойчивого к таким ошибкам квантового компьютера остаётся инженерной проблемой, но криптографы уже готовятся к худшему сценарию. Разрабатывается постквантовая криптография, в основе которой лежат задачи, не поддающиеся решению даже на

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

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