Криптография и модульная арифметика: Математика защиты данных

Модульная арифметика оперирует конечным множеством чисел. В ней результаты сложения, вычитания или умножения «заворачиваются» при достижении определенного значения — модуля (обычно обозначается как mod). Самый простой пример — циферблат часов: если сейчас 10 часов, то через 5 часов будет не 15, а 3 часа (10 + 5 ≡ 3 mod 12).

Современная криптография с открытым ключом (асимметричная криптография) строится на вычислительно сложных математических задачах. Классический пример — алгоритм RSA, названный по первым буквам фамилий его создателей (Rivest, Shamir, Adleman). Его надежность базируется на задаче факторизации: перемножить два огромных простых числа легко, но зная только результат (произведение), найти исходные простые множители — задача, на решение которой у современных компьютеров уйдут миллионы лет.

Для генерации ключей в RSA используется функция Эйлера и Малая теорема Ферма. Открытый ключ передается по незащищенному каналу и служит для шифрования сообщения, а закрытый ключ, известный только получателю, позволяет вычислить модульную экспоненту и расшифровать текст.

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

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