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

kIlka (kilka@linkin-park.ru)

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

adc [edi], eax

lea esi, [esi+4]

lea edi, [edi+4]

loop cycle1

}

}

Оператор вычитания - точная копия оператора сложения, только вместо adc используется sbb. Почитать об ассемблере вообще и о "цепочечных" директивах можно в [6].

А кто говорил, что будет легко?

a^b mod c

Использование перегруженных операторов делает программу элегантной. В идеале хотелось бы, чтобы функции шифрования и дешифровки выглядели вроде этой: (x^d) mod n. Однако возведение в степень такого огромного числа путем перемножения заняло бы кучу времени. Поэтому операции возведения в степень и нахождения остатка объединены в функции mod_exp(Number& a, Number& b, Number& n):

Number mod_exp(Number& a, Number& b, Number& n)

{

Number r(1);

Number t;

t = a;

Number buf;

for(int i = 1; i <= return_upper_bit(b); i++)

{

if (b[i])

{

mod_mult(buf, r, t, n);

r = buf;

}

mod_mult(buf, t, t, n);

t = buf;

}

return r;

}

В этой процедуре используется известный метод возведения x в n-ую степень с использованием двоичного представления числа n. Для понимания метода рассмотрим пример. Пусть нужно возвести x в 11 степень. 11 = 1011 в двоичном коде. Тогда x^11 = x * x ^ 2 * x ^ 8. И x^11 mod n можно представить так: (x^ 8 * ((x^2 * (x mod n)) mod n)) mod n. Теперь нам необходима функция, выполняющая действие (a * b) mod n - mod_mult(a, b, n).

void mod_mult(Number& r, Number& a, Number& b, Number& n)

{

r.null(); // r = 0

for (int i = return_upper_bit(b); i >= 1; i--) // return_upper_bit - возвращает старший значащий бит

{

r.shift_left();

if (r >= n) r -= n;

if (b[i])

{

r += a;

if (r >= n) r -= n;

}

}

}

Так как х возводится в степени двойки, то операцию возведения в k степень можно заменить операцией побитового сдвига влево на k позиций. То есть x^11 mod n равносильно следующему: (x << 8 * ((x << 2 * (x mod n)) mod n)) mod n. x << k же равносильно x << 1 (x.shift_left()), выполненному k раз.

Остаток же от деления вычисляется как r -= n (как только r >= n).

Вычисление ключей

Для начала можно не заморачиваться с генерацией ключей, а доверить эту трудоемкую задачу PGP или другой сторонней программе (см. врезку). Однако в конце концов к этому придется вернуться.

Генерация ключа при помощи PGP

Как найти простые числа r и h? Действуют так: генерируют случайные числа необходимой длины и подвергают их вероятностной проверке на простоту. Для обеспечения случайности чисел можно, как в PGP, использовать время между нажатиями на клавиши при наборе какого-то текста. Далее число как-то изменяется (к примеру, увеличивается на константу).

Для проверки на простоту используются тесты Лемана, Миллера-Рабина, Соловея-Штрассена. Тест Лемана, к примеру, работает так: если для какого-то числа a величина (a ^ ((r - 1) / 2) mod r) не равна 1 или -1, то r - не простое (это следует из теоремы Ферма - см. [4]). Чем больше проверок для разных значений a - тем больше вероятность правильности ответа. Этот метод хорош тем, что обычно бракует большие составные числа уже за одну проверку.