Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
чем дальше в лес... 22.09.04 10:59 Число просмотров: 3735
Автор: kata Статус: Незарегистрированный пользователь
|
> > > Еще вопрос:
> > > Насколько я понимаю, RSA может использовать не
> совсем
> > > простые p и q, а некоторое их приближение.
> Допустим у
> > меня
> > > есть E, P1...Pk, где N=P1*...*Pk. Как на их
> основе
> > > вычислить D?
> > Вопрос остается в силе.
> > Допустим лом RSA работает для идеального случая, когда
> > N=P*Q. Как его расширить для случая, когда
> N=P1*P2*...Pk?
> > Какие ещё подводные камни могут встретьтся в
> конкретных
> > реализациях RSA?
>
> Ну, во-первых, числа RSA генерятся с достаточно большой
> вероятностью того, что они окажутся действительно простыми.
> Даже если они не простые - они всё равно удовлетворяют всем
> статистическим св-вам, которые необходимы для работы
> теоремы Эйлера, трудоёмкой факторизации и следовательно для
> них с большой долей вероятности будут работать те же
> соотношения и для d. Не обязательно всё будет работать, но
> вероятность достаточная. Ну а если не работает - то и
> шифровать на таких ключах не целесообразно - так что тут от
> того, что n!=pq мало чего зависит.
>
> По поводу ф(n), если n - произведение нескольких простых
> чисел (больше чем двух). Общая формула такая:
>
> Ф(n)=n-n/P1-n/P2-...-n/Pk+n/P1P2+n/P1P3+...+n/P2P3+n/P2P4+.
> ..+n/P(k-1)Pk-n/P1P2P3-n/P1P2P4-...-n/P(k-2)P(k-1)Pk+...+((
> -1)^k)*n/P1P2...Pk
>
> Написал, конечно, немного криво, но я не знаю как её
> записать нормально в математическом виде на клавиатуре. То
> есть из n вычитается сумма всех n/Pi, потом прибавляется
> сумма всех n/PiPj и т. д. Если какой-то простой сомножитель
> чиcла n "содержится" в нём в какой-то степени - это формулы
> не меняет. Каждый сомножитель учитывается только один раз в
> 1 степени.
>
> Ф(n), вычисленный по этой формуле от n, имеющий несколько
> простых сомножителей, так же вполне может использоваться в
> RSA - хотя применение такого вида функции Эйлера скорее
> всего на практике и не потребуется - при факторизации ты в
> любом случае найдёшь один "простой" сомножитель, а потом
> найдёшь второй "простой", поделив q=n/p. Хоть теоретически
> это и неверно, работать в большинстве случаев будет - т.
> к., повторюсь, статистические проверки проводятся именно на
> эти св-ва.
>
> P.S. Но вообще, если мало ли Ты хочешь
> реализовать алгоритм RSA на основе
> n=p1p2p3... - то Тебе поможет фукция Эйлера (см. выше),
> однако стойкость RSA упадёт критически - смысла в таком
> алгоритме уже не будет. То есть нахождение быстрого
> алгоритма факторизации действительно убьёт RSA.
Спасибо за довольно подробное письмо, но я всё равно не понял.
Я не хочу реализовать алгоритм RSA я хочу его поломать. Допустим самое трудное решено - найден достаточно быстрый алгоритм факторизации N. Остается темная область для меня - как на основе разложения N вычислить приватный ключ.
Допустим реальный алгоритм RSA сработал так, что получились не очень простые P и Q. На их основе сгенерированы D и E.
Допустим N у меня разложилось на три числа p1, p2, p3. Что мне с ними дальше делать? Перебрать 3 возможных варианта?
p1*p2 = P, p3 = Q
p1*p3 = P, p2 = Q
p2*p3 = P, p1 = Q
А если получится 4 числа? Вариантов становится 6. Так дело не пойдет. Я слышал, что чем сложнее N, тем быстрее работает взлом, по идее, но в чем идея заключается?
|
|
|
подробно о проекте
Анализ криптографических сетевых...
