Что такое RSA?

Краткие основы RSA:

1. Выбираются _большие_ _простые_ числа M и N;
2. Вычисляется их произведение: Q=MxN;
3. Выбирается число D, которое должно быть взаимно простым с результатом
   умножения (M-1)x(N-1), т.е. не должно иметь с ним общих делителей, от-
   личных от единицы;
4. Вычисляется число A из выражения (AxD) mod [(M-1)x(N-1)]=1;

Таким образом, пара чисел (A,Q) будет твоим открытым ключом, а пара чисел
(D,Q) -- закрытым ключом. Понятно, что открытым ключом можно только _за-
кодировать_ исходный текст, для того, чтобы его _раскодировать_, нужен за-
крытый ключ.

    Кодирование числа P: C=M^A mod Q;
    Обратная операция:   P=C^D mod Q;

Так вот, для того, чтобы поломать PGP (сиречь RSA), необходимо и достаточно
уметь разложить число Q (которое мы возьмем, понятно, из открытого ключа,
помещенного человеком в бурные воды, скажем, Fido и/или Internet) на простые
множители. Вот тут-то и начинается самое интересное. :)
Простые множители числа -- летопись в теории чисел, над ними бились многие
математики. о увы, так ничего толком и не добились. В математике _не су-
ществует_ теорем, могущих надежно предсказать, является ли число простым.
Есть теоремы, которые могут быстро установить, что число _составное_, но
если условия теоремы не выполняются, то это не значит, что число простое:
это значит, что оно ВРОДЕ БЫ простое, и надо применять более сильные теоре-
мы, которые, увы, на машине проверяются только перебором. Далее, нет теорем,
которые помогают хотя бы оценить количество простых сомножителей числа и
порядок их величины. Так что реально число из, скажем, трехсот десятичных
знаков разложить на простые множители (если они, правда не лежат близко к
корню из числа и т.д. -- есть легкие случаи) за разумное время нереально.
Так, программа на 386SX40 раскладывает число из 17 десятичных знаков за
время, близкое к трем минутам, но время ее работы есть P*exp(n), т.е. число
из 300 знаков она будет раскладывать в exp(280) раз дольше (это около
5.1*10^279). Естественно, что если взять более быстрое точило, Cray, к
примеру, то будет побыстрее... :) о все равно не слишком. Правда, есть
более быстрые алгоритмы, решето Сива, например, но они хороши, когда со-
множители лежат близко к корню, и требуют дикое количество памяти.