Последние дни RSA

Евгений Firstborn Рогов

Спецвыпуск: Хакер, номер #055, стр. 055-016-5

Будущее умудрилось потихоньку наступить, а мы этого почти не заметили. Но ты еще успеешь подумать о безопасности своих данных, если начнешь прямо сейчас!

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

Каким же образом работает такая криптосистема? Не очень сложно.

Понятно, что для начала работы необходимо сгенерировать пару подходящих ключей. Делается это по следующему алгоритму:

1. Выбираются какие-нибудь достаточно большие простые числа P и Q.

2. Пусть теперь N = P * Q, а M = (P - 1) * (Q - 1).

3. Находим число D, взаимно простое с М.

4. Подбираем число E так, чтобы E * D = 1 (mod M).

Полученные таким образом пары чисел (E,N) и (D,N) станут ключами! Осталось только выбрать, какой из них будет открытым, а какой - секретным. На самом деле неважно, как будет сделан такой выбор. Но допустим, что мы выбрали секретным ключом пару (D,N) и хорошенько припрятали его от посторонних глаз. Значит, пара (E,N) будет служить открытым ключом, и мы можем смело отсылать ее своему скрытному собеседнику. Он будет использовать его, чтобы произвести шифрование секретной информации А (будем считать эту информацию числом) следующим образом: B = A^E (mod N). Шифровка B пересылается обратно (нам) и подвергается расшифровке: A = B^D (mod N). Вуаля!

Разумеется, тут есть и свои тонкости. Например, шифруемые данные необходимо разбить на блоки - числа от 0 до N - 1 (технически это легко реализуемо). Кроме того, не все действия, из которых состоит приведенный выше алгоритм конструирования ключей, так уж тривиальны. Например, выбор самих простых чисел P и Q не такой простой, особенно учитывая тот факт, что они должны обладать приличной разрядностью для того, чтобы их было практически невозможно вычислить с помощью факторизации числа N на классическом (не квантовом) компьютере. Кстати, если тебе интересны все детали реализации RSA, подними свои архивы и отыщи "Хакер Спец" за апрель 2004 года. В нем ты почерпнешь немало интересного!