Здравствуйте!
Обратимся еще раз к RSA (на сей раз к опровержению некоторых фундаментальных основ RSA - например, об уникальности приватного ключа для конкретной экспоненты/модуля).
Получим "сильные простые числа" (safeprime в терминологии Maple 8)
safeprime(150) -> 167
safeprime(210) -> 227
Получим модуль: 167*227=37909
Получим Euler phi: 226*166=37516
Получим инверсию экспоненты (17) по подулю phi:
17^(-1)mod 37516 = 13241
Зашифруем значение 12345 по этому модулю с экспонентой 17:
12345^(17)mod 37909 = 27734
По логике и канонам RSA для этого значения (27734) должен быть только единственный ключ - (34201)
Но это не так. Решим уравнение (решаем в Maple 8)
msolve(27734^x=12345,37909)
получим результат: {x = 3862+9379*_Z1}
где _Z1 - любое целое число, принадлежащее множеству чисел от минус бесконечности до плюс бесконечности (включая ноль).
Проверим:
27734^(3862+9379*0) mod 37909 = 12345
27734^(3862+9379*1) mod 37909 = 12345
27734^(3862+9379*(-1)) mod 37909 = 12345
Так где же уникальность ключа?

Я RSA сам конечно не выводил... Но одна интересная мысль все же есть.

Если взять число, возвести в степень и взять mod (тоесть зашифровать), получим зашифрованное число :-) Посло этого берем зашифрованное число и снова шифруем его тем же ключем. Потом снова и снова. В итоге в некоторый момент зашифровав очередное число мы вернемся к исходному числу.

Тоесть последовательность зашифровок циклична. Настоящий математик возразит мне: Любая последовательность чисел, основанная на элементах конечного множества - циклична. Да, это так, но, период цикла описаной последовательности будет намного меньше мощности использованного множества. Возможно даже что в предельном поведении период будет бесконечно малым по сравнению с мощностью. Хотя, это всего лишь интуиция.

Вообщем мысль моя такая. Рассмотрим две последовательности a{n} и b{n}.

a{n} = a{n-1}^key mod base

b{n} = a{0}^(key ± X*n) mod base

Последовательность a{n} - циклична. Первый член ее это незашифрованные данные. Так вот, мне кажется, что эти последовательности как-то связаны между собой и X может быть вычеслен через период последовательности a{n}. Вопрос о существовании X оставляю открытым :)
Но опять же, это все интуиция.

Все это интересно с теоретической точки зрения. Вот только все эти так называемые баги пока не пошатнули криптостойкость RSA.

проверим
12345^17 mod 37909 = 27734
решим уравнение, где найдем x возведений в степень ключа по исходному модулю зашифрованного значения 27734, то есть, (key*x) - некоторое число возведений в степень key, т.е в данном случае - 17

msolve(27734^(17*x)=12345,37909)
получаем {}, то есть
решений этого уравнения нет

Другой подход показывает, что решения в данном случае имеют вполне определенный период - то есть, множество решений
с^(n+k*x)=m mod n
где:
с - зашифрованное значение
m - исходное значение
n - константа, зависящая от знака и значения экспоненты
k - период, зависящий от значения экспоненты/модуля
x - любое число из Z

Например, инвертируем результат (27734) по исходному модулю - 37909
27734^(-1) mod 37909 = 4523
решим уравнения:
msolve(27734^x=12345,37909); {x = 3862+9379*_Z1}
и
msolve(4523^x=12345,37909); {x = 5517+9379*_Z1}

И в первом, и во втором случае имеем константу - 9379, являющуюся периодом для ключей (для данного модуля и экспоненты).

msolve(27734^(17*x)=12345,37909)
все же решений нет

Неправильно поставил задачу - и ошибся :((
Решение все-таки есть! _DEN_ прав

Решаю следующим образом: (синтаксис Maple)
шифруем 12345^17 mod 37909 = 27734
x:=27734; // начальное зашифрованное значение
while(x<>12345) //зашифрованное значение
do
x:=power(x,17)mod 37909;//повторное шифрование
end do

Остановился на 4591
то есть: 27734^(17^4591)mod 37909 = 12345

ECk
Вот ты всё говоришь "для данного модуля и экспоненты". Почитай ещё раз про генерацию ключей RSA. Открытый ключ - "экспонента" - берётся отнюдь не с потолка (обычно 10001h). При "правильно" выбранной экспоненте закрытый ключ определяется однозначно. И всё "работает" как часы ;)

"Для данной экспоненты" - я имею в виду такую экспоненту, которая не имеет общих множителей с (p-1) и (q-1) - это из RFC 2313 "RSA encryption"

RFC 2313 PKCS #1: RSA Encryption March 1998

6. Key generation
This section describes RSA key generation.
Each entity shall select a positive integer e as its public exponent.
Each entity shall privately and randomly select two distinct odd
primes p and q such that (p-1) and e have no common divisors, and
(q-1) and e have no common divisors.
The public modulus n shall be the product of the private prime
factors p and q:
n = pq .
The private exponent shall be a positive integer d such that de-1 is
divisible by both p-1 and q-1.

К тому же, если экспонента имеет общие множители с phi от (p*q) - инверсия не существует.
Так что, экспонента по отношению к множителям, составляющим модуль, подобрана правильно.
Теперь о модуле: множители представляют из себя "сильные" простые числа - то есть числа p, вида (p-1)/2=q, где и p и q - простые числа.
(167-1)/2=83; 167 и 83 - простые числа.
(227-1)/2=113; 227 и 113 - простые числа.
Так что и множители для модуля подобраны правильно(в рамках стандарта).

Пожалуйста - экспонента 10001h (2^16+1)
Множитель 1 - 57119
Множитель 2 - 12107
(сильные простые числа)
модуль - 691539733
Euler phi 57118*12106=691470508
Инверсия(ключ d) (2^16+1)^(-1)mod 691470508 = 249632913
Шифруем 12345^(2^16+1)mod 691539733 = 676728080
решаем:
msolve(676728080^x=12345,691539733);
получаем:
{x = 249632913+345735254*_Z1}
проверяем:
power(676728080,(249632913+345735254*0)) mod 691539733;
результат: 12345
power(676728080,(249632913+345735254*1)) mod 691539733;
результат: 12345
power(676728080,(249632913+345735254*-1)) mod 691539733;
результат: 12345
на всем протяжении Z

Мысль такая.

a = b^k mod N

a - Зашифрованные данные
b - Исходные данные
k - Открытый ключ
N - Модуль

b^k mod N = b^k - m*N, где m - целое положительное, обладающее свойством:

b^k - m*N >= 0,
b^k - (m+1)*N <= 0.

Тогда для расшифровки данных, незная ключа достаточно решить уравнение

m = (b^k - a) / N, или
b = (a + m*N)^(1/k)

Одно уравнение, две неизвестных. Но у нас есть условия:

1-е: a < N
2-е: b < N
3-е: b^k - m*N >= 0
4-е: b^k - (m+1)*N <= 0
5-е и главное: Все числа - натуральные и, быть может, нулевые.

Т.е. уравнение в совокупности с данными пятью условиями теоретически должны дать единственный ответ. Напомню, нас интересует решение в целых.
Сегодня весь день пытался решить в общем виде. Результата пока нет.
На практике будет достаточно следующее...

Имеется неизвестное незашифрованное число b0 и произвольное целое число t, обладающее свойством: t < N
Вычислим для него m:

m = (t^k - a) / N

Если удасться по полученному m поставить знак между b0 и t (определить, кто больше а кто меньше), то задача решена и RSA останется только на страницах учебников истории.

Понимаю, звучит довольно самонадеяно...
Но все же хотелось бы выслушать чужие мнения по этому поводу.

:)
http://cryptography.ru/db/msg.html?mid=1161209
Почитайте. Освежите знания.