Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Про n=p1p2p3.. 22.09.04 09:46 Число просмотров: 4172
Автор: Heller <Heller> Статус: Elderman
Отредактировано 22.09.04 09:52 Количество правок: 1
|
> > Еще вопрос:
> > Насколько я понимаю, 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.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
