Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Ошибка в RSA? 15.11.02 11:27 Число просмотров: 3559
Автор: Komlin Статус: Незарегистрированный пользователь
|
Ошибка в RSA?
Одно из основных утверждений RSA – утверждение о существовании и единственности решения
m^e == c (mod (n)) n=pq
и
c^d == e (mod (n)) n=pq
при условии простоты p,q и взаимной простоты e и функии Эйлера (p-1)(q-1)
К сожалению это не совсем так.
Рассмотрим выражение a mod n
Его можно представить как a mod pq == a mod p + (([a / p]) mod q) *p
[a/p] означает целую часть от деления a/p
Из него следуют выводы:
xq^p mod n = xq
xq^(yp) mod n = xq^y
xq ^ (x(p-1)) mod p = const т.е. постоянен вне зависимости от значений x,y.
Из последних утверждений следует также
(q-1)^(p-1) mod n =1
(q+1)^(p-1) mod n =1
или
(m(q+-1))^(p-1) mod n = m^(p-1) mod n
Отсюда следует, что выражения m^d mod n сводимые к a*(q+-1)^(p-1) будут иметь общие решения с a^d mod n(Напрямую использовать p-1 в качестве ключа нельзя). Способов получить такие выражения довольно много.
Пример.
Пусть есть простое q=i^t+-1
Тогда при d=t и z=(i)^(p-1)
c^d mod n = (cm)^d mod n.
Практические последствия этой формулы достаточно просты.
1) Возможен такой выбор параметров, что RSA будет работать неправильно и приведёт к потере данных
2) RSA не может применяться для цифровой подписи, т.к. одной и той же подписи могут соответствовать разные документы.
|
- Ошибка в RSA? - Komlin 15.11.02 11:27 [3559]
|
|
|
подробно о проекте
Анализ криптографических сетевых...
