Алгоритмы шифрования: история и математические основы

Содержание

1. 1. Эволюция шифрования: от древности до цифровой эры3
2. 2. Математический фундамент: теория чисел и модулярная арифметика5
3. 3. Классические и современные симметричные алгоритмы8
4. 4. Асимметричные алгоритмы и перспективы криптографии11

1. Эволюция шифрования: от древности до цифровой эры

Потребность скрыть сообщение от чужих глаз стара как сама письменность. Одним из первых документально зафиксированных методов стала замена букв по сдвигу алфавита. Шифр Цезаря, названный в честь римского полководца I века до н.э., сдвигал каждую букву на три позиции. Сегодня такой приём кажется наивным, ведь в нём всего 25 возможных вариантов ключа, но для своего времени это был прорыв. Примерно тогда же на Ближнем Востоке использовали шифр Атбаш, где первая буква алфавита менялась на последнюю, вторая на предпоследнюю. Эти простые моноалфавитные системы, где каждая буква всегда заменялась одной и той же другой буквой, оставались основой криптографии более полутора тысяч лет.

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

Решающий скачок произошёл в XX веке, когда на сцену вышли машины и математика. Во время Второй мировой войны британская разведка сосредоточила усилия в поместье Блетчли-парк. Группа математиков и логиков, среди которых выделялся Алан Тьюринг, работала над взломом немецкой шифровальной машины «Энигма». Тьюринг разработал электромеханическую

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

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

2. Математический фундамент: теория чисел и модулярная арифметика

Теория чисел попала в фундамент криптографии не случайно. Её объекты, целые числа, допускают строгие утверждения и одновременно создают огромные вычислительные трудности. Центральное место занимают простые числа, то есть числа, делящиеся только на единицу и на самих себя. Их распределение хаотично, но подчиняется закону, открытому Гауссом и Лежандром: количество простых, не превышающих x, приблизительно равно x / ln(x). Эта двойственность (предсказуемость на больших промежутках и непредсказуемость в конкретной точке) делает простые числа удобным строительным материалом для шифров.

Наибольший общий делитель (НОД) двух чисел вычисляется алгоритмом Евклида. Он лежит в основе проверки взаимной простоты. Для криптографии важнее другое: если НОД(a, n) = 1, то у a существует мультипликативное обратное по модулю n. Иными словами, найдётся такое число b, что a * b ≡ 1 (mod n). Нахождение b выполняется расширенным алгоритмом Евклида за O(log n) операций. Это позволяет делить в модулярной арифметике. Функция Эйлера φ(n) подсчитывает количество чисел от 1 до n, взаимно простых с n. Для произведения двух простых p и q получаем φ(pq) = (p - 1)(q - 1). Именно эта формула связывает теорию чисел с практикой шифрования.

Модулярная арифметика работает с остатками от деления. Запись a ≡ b (mod m) означает, что m делит разность a - b. Все операции (сложение, умножение, возведение в степень) выполняются над остатками. Для компьютеров это удобно: результат всегда ограничен модулем. Ключевое свойство сравнений: если a ≡ b (mod m) и c ≡ d (mod m), то a + c ≡ b + d (mod m) и a * c ≡ b * d (mod m). Это позволяет менять порядок вычислений, не меняя результата. Например, 2^10 = 1024, а 1024 mod 7 = 2, поэтому 2^10 ≡ 2 (mod 7).

Возведение в степень по модулю (основной примитив асимметричных систем) требует особого подхода. Наивное перемножение экспоненты раз, как в случае 2^1000, нереально. Алгоритм быстрого возведения в квадрат и умножение сокращает число операций до O(log e). Идея проста: показатель представляется в двоичном виде, и на каждом шаге основание возводится в квадрат по модулю, а результат домножается при наличии единичного бита. Так, 3^50 mod 100 вычисляется за несколько десятков умножений, а не за пятьдесят. Эта эффективность при обратной неэффективности задачи дискретного логарифмирования образует асимметрию, на которой строятся шифры.

Однако математическая строгость не гарантирует безопасности. В 1971 году Стивен Кук формализовал класс NP, а Ричард Карп в 1972 году показал, что многие задачи эквивалентны по сложности. Класс P содержит задачи, решаемые за полиномиальное время (умножение чисел или поиск НОД). Класс NP включает задачи, ответ которых можно проверить за полиномиальное время, но найти его, возможно, сложнее. Открытый вопрос о равенстве P и NP остаётся нерешённым, и вся современная криптография опирается на предположение, что P ≠ NP. Факторизация больших чисел, задача, лежащая в основе многих схем, не доказано принадлежит к NP-полным, но практических алгоритмов для неё нет. Самое быстрое известное решение, общий метод решета числового поля, требует субэкспоненциального времени. Это делает взлом невозможным при длине ключа в 2048 бит.

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

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

3. Классические и современные симметричные алгоритмы

Симметричные алгоритмы, где отправитель и получатель используют один и тот же ключ, остаются основой практической криптографии. Задача сводится к преобразованию открытого текста в нечитаемую последовательность битов и обратно с помощью секретного ключа. Главный инженерный вопрос в том, как построить преобразование, которое было бы необратимым без знания ключа, но простым при его наличии. Ответ дают две основные архитектуры: сеть Фейстеля и подстановочно-перестановочная сеть (SP-сеть).

Сеть Фейстеля, предложенная Хорстом Фейстелем в IBM в начале 1970-х, делит блок данных на две половины. На каждом раунде одна половина преобразуется функцией от другой половины и раундового ключа, затем результаты складываются по модулю 2 (XOR) с исходной половиной, и половины меняются местами. Ключевое свойство схемы в том, что функция шифрования не обязана быть обратимой. Для расшифровки достаточно прогнать шифротекст через ту же сеть в обратном порядке ключей. Это позволило строить компактные аппаратные реализации, что и определило популярность схемы на десятилетия.

SP-сеть работает иначе. Каждый раунд состоит из слоя подстановок (S-блоки, заменяющие части блока по таблице) и слоя перестановок (P-блоки, перемешивающие биты). Такая структура напрямую реализует принципы рассеивания и перемешивания, сформулированные Клодом Шенноном. Рассеивание размазывает статистическую структуру открытого текста по всему шифротексту, а перемешивание делает связь между ключом и шифротекстом максимально запутанной. В отличие от сети Фейстеля, SP-сеть требует обратимости всех преобразований, но она даёт лучшую скорость распространения изменений по блоку за раунд.

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

которая складывается с открытым текстом. Классический пример, шифр Вернама, использовал полностью случайную гамму той же длины, что и сообщение. Это даёт абсолютную стойкость, но требует заранее распределить огромный объём секретного материала. Практические поточные шифры (например, RC4) генерируют гамму из короткого ключа детерминированным алгоритмом. Это снимает проблему распределения, но вносит уязвимости, если гамма повторится или будет предсказуема.

Стандарт DES, принятый NIST в 1977 году, стал классическим воплощением сети Фейстеля. Он работает с 64-битными блоками и 56-битным ключом, выполняя 16 раундов. Каждый раунд включает расширение правой половины с 32 до 48 бит, XOR с раундовым ключом, прохождение через 8 фиксированных S-блоков и финальную перестановку. DES был разработан в IBM, и его ключевой особенностью стала устойчивость к дифференциальному криптоанализу. Об этом стало известно лишь в 1990-х. Однако 56-битный ключ оказался фатально слабым. В 1998 году проект Electronic Frontier Foundation взломал DES за 56 часов на специально построенной машине. Это сделало стандарт непригодным для защиты данных.

Его преемник, AES, был выбран в 2000 году по итогам открытого конкурса. Победил алгоритм Rijndael бельгийских криптографов Йоана Дамена и Винсента Рэймена. AES работает с блоками 128 бит и ключами 128, 192 или 256 бит. Это SP-сеть с 10, 12 или 14 раундами соответственно. Каждый раунд состоит из четырёх операций: SubBytes (замена каждого байта через S-блок на основе мультипликативной инверсии), ShiftRows (циклический сдвиг строк состояния), MixColumns (перемешивание столбцов через умножение в поле Галуа) и AddRoundKey (XOR с раундовым ключом). Математика поля Галуа GF(2⁸) здесь не декоративная деталь. Умножение в этом поле реализует перемешивание байтов без потери информации, а обратимые операции гарантируют корректную расшифровку.

Даже с сильным блочным шифром остаётся вопрос: как шифровать данные длиннее одного блока? Ответ дают режимы работы. Самый наивный, ECB, шифрует каждый блок независимо. Он прост, но идентичные блоки открытого текста дают идентичные блоки шифротекста. Это раскрывает структуру данных, как в знаменитом примере с силуэтом пингвина. Режим CBC решает эту проблему, связывая блоки: перед шифрованием каждый блок складывается по XOR с предыдущим шифротекстом. Это делает шифрование зависимым от всей предыдущей истории, но создаёт проблему: ошибка в одном бите шифротекста портит два блока при расшифровке. Режим CTR превращает блочный шифр в поточный: шифруется счётчик, и результат складывается с открытым текстом. Это позволяет шифровать блоки параллельно и обращаться к любому блоку случайно, что критически важно для шифрования дисков и сетевого трафика. Выбор режима определяется конкретной задачей. Где-то важна параллелизация, где-то устойчивость к повреждениям, а где-то скорость.

4. Асимметричные алгоритмы и перспективы криптографии

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

Первую практическую реализацию этой идеи в 1977 году предложили Рон Ривест, Ади Шамир и Леонард Адлеман. Алгоритм RSA до сих пор остаётся стандартом индустрии. Генерация ключей начинается с выбора двух больших простых чисел p и q. Их произведение n образует модуль. Затем вычисляется функция Эйлера φ(n) = (p−1)(q−1). Открытая экспонента e выбирается взаимно простой с φ(n), а закрытая экспонента d находится из условия e·d ≡ 1 (mod φ(n)). Шифрование выглядит как возведение сообщения m в степень e по модулю n: c = m^e mod n. Расшифровка возвращает исходный текст: m = c^d mod n. Математическое обоснование опирается на теорему Эйлера: если m взаимно просто с n, то m^φ(n) ≡ 1 (mod n), что гарантирует корректность обратного преобразования. В 1991 году стандарт RSA был закреплён в документе PKCS #1, что сделало его доступным для массового использования.

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

впервые независимо разработанные Нилом Коблицем и Виктором Миллером в 1985 году. Вместо умножения по модулю здесь используется операция сложения точек на кривой вида y² = x³ + ax + b. Секретным ключом служит число k, открытым, точка Q = k·P, где P, базовая точка кривой. Задача дискретного логарифма на эллиптической кривой решается значительно труднее, чем факторизация. Поэтому ключ ECC длиной 256 бит обеспечивает уровень безопасности, сопоставимый с ключом RSA в 3072 бита. Меньший размер ключей даёт преимущества в скорости и экономии энергии, что критично для мобильных устройств и систем интернета вещей.

Современные асимметричные схемы столкнулись с новым вызовом: квантовые компьютеры. В 1994 году Питер Шор предложил алгоритм, способный за полиномиальное время решить задачу факторизации и дискретного логарифма. Это означает, что RSA и ECC будут взломаны, как только появится достаточно мощный квантовый компьютер. Ответом стала постквантовая криптография, разрабатываемая в рамках проекта NIST, который начал стандартизацию новых алгоритмов в 2016 году. Наиболее перспективным направлением считаются схемы на решётках: их стойкость основана на сложности поиска кратчайшего вектора в многомерном пространстве. Кодовые криптосистемы, например классический алгоритм Мак-Элиса, опираются на трудность декодирования случайного линейного кода. Многомерные схемы используют системы полиномиальных уравнений от многих переменных, решение которых относится к NP-трудным задачам. Каждое из этих направлений предлагает свои компромиссы между размером ключа, скоростью и надёжностью, но все они призваны сохранить конфиденциальность в эпоху, когда классические математические основы перестанут быть надёжной защитой.