ВЕБ ПОД ЗАМКОМ!
Технологии для создания защищенных соединений

Kirion (kkr@mailru.com)

Спецвыпуск Xakep, номер #030, стр. 030-014-2

Одним из первых практически применимых алгоритмов стал алгоритм RSA (назван по инициалам создателей: R.Rivest, A.Shamir, L.Adleman). Математический принцип на самом деле несложен, но чтобы не загружать твои бедные компьютерные мозги еще и формулами :), попытаюсь объяснить "на пальцах". Имеются два числа: наш открытый и закрытый ключи. Они математически связаны с некоторым третьим числом, однако никак не связаны между собой. Открытый ключ доступен любому человеку, его можно разослать всем друзьям, повесить на паге и т.д. - с его помощью будет шифроваться инфа. Над информацией производится необратимая математическая операция с помощью открытого ключа и третьего числа (необратимая - это значит по открытому ключу, третьему числу и результату нельзя будет узнать исходные данные). Обратная же операция возможна только с использованием математической зависимости между закрытым ключом и третьим числом. Еще не уснул? Если все же горишь математическим любопытством - загляни на врезку, там все объяснено в формулах.

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

ПРИМЕРНЫЙ АЛГОРИТМ ШИФРОВАНИЯ RSA

Берем два простых числа p и q. Вычисляем их произведение n(=p*q). Выбираем число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть у числа e и числа (p-1)(q-1) не должно быть общих делителей (НОД - наибольший общий делитель). Решаем в целых числах уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y. Два числа (e,n) - это открытый ключ, размещай, где хочешь. Число d - это и есть закрытый ключ, который позволит расшифровывать все, что зашифровано с помощью пары чисел (e,n). Смотри на скрин с формулами и читай дальше. При шифровании инфа разделяется на блоки, к каждому из которых применяется операция из пункта (1), где m - инфа, а с - шифрованная инфа. Операция возведения в степень по модулю простого числа является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является значительно более сложной. Даже если некто знает числа e и n, то по c прочесть исходные сообщения m он не может никак, кроме как полным перебором m. Все бы было совсем плохо, если бы не теорема Эйлера, частный случай которой утверждает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (1). Для дешифровки информации воспользуемся этой формулой. Возведем обе ее части в степень (-y). Получится равенство (2). Теперь умножим обе ее части на x: результат смотри под пунктом (3). А поскольку у нас есть равенство e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. Отсюда следует равенство (5). Применим это к нашему шифрованному сообщению: получим пункт (6). Все легко, правда :)?