Открытый ключ с закрытыми глазами

kIlka (kilka@linkin-park.ru)

Спецвыпуск Xakep, номер #041, стр. 041-008-3

Чтобы еще ускорить работу программы, перед тестом Лемана число проверяют с помощью заранее заготовленного набора 16-битных простых чисел - p[]. Далее : нет, ты не угадал. Никто не делит каждое новое число на них до посинения. Составляется таблица остатков от деления начального случайного числа на p[] - r[]. Далее случайное число увеличивается на delta. Используется равенство p mod p[] = (delta + r[]) mod p[] (оно следует из того, что (a + b) mod n = (a + (b mod n)) mod n).

Получив r и h (а следовательно, и n = r * h), переходят к подбору e. Напомню, что e - небольшое число, взаимно простое с t=(r-1)*(h-1). Для этого подставляем в e 3, 5, 7, 9 и т.д. пока НОД(e, t) != 1. НОД - наибольший общий делитель, который ищется с помощью алгоритма Евклида. В двух словах его можно описать так. Пусть нужно найти НОД(u, v). Присваиваем r = u mod v. Далее u = v, v = r. И так до тех пор, покуда v != 0. Если v = 0, то НОД(u, v) = u. Подробнее об алгоритме Евклида, а также о бинарном методе нахождения НОД смотри в [1].

Напомню, что для вычисления d нужно вычислить обратное в группе вычетов - e^-1. Как это сделать? Существуют методы, построенные на модифицированном алгоритме Евклида. О них опять же можно прочитать в [1]. Реализация есть в [2]. Кроме того, можно заглянуть в исходники PGP.

Моя реализация, к сожалению, не содержит алгоритмов для генерации ключа. Тебе придется писать их самому. Общие рекомендации даны, однако неплохо бы было посмотреть на примеры реально работающих программ. Рекомендую GnuPG - версию PGP, распространяемую под лицензией GPL. Кроме того, довольного много исходников есть на http://z0mbie.host.sk/.

Немного о симметричных алгоритмах

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

Вообще говоря, под названием RC5 скрывается целое семейство алгоритмов, отличающихся длиной ключа, длиной блока и количеством раундов. Для реализации на x86 наиболее подходит вариант с 64-битным блоком данных (каждый блок хранится в двух dword’ах). В алгоритме используется всего 3 операции - исключающее или (XOR), сложение и циклический сдвиг (влево и вправо). Перед шифрованием, с использованием значения ключа, заполняется массив dword’ов длиной 2 * r + 2 - S[], где r - количество раундов. Механизм шифрования легче всего понять из листинга:

void rc5(dword *data, int blocks) // data - указатель на данные; blocks - количество блоков

{

for(int i = 0; i < blocks; i++)

{ // Обозначим A = data[0] - первую половину сообщения, B = data[1] - вторую

data[0] += S[0]; // A = A + S[0]

data[1] += S[1]; // B = B + S[1]