Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Постараюсь объяснить третий этап (набросок).
29.06.04 15:07 Число просмотров: 4503
Автор: volizar Статус: Незарегистрированный пользователь
|
Постараюсь объяснить третий этап (набросок).
Предположим, надо факторизовать некое число А.
Находим b, c и d , как на первой стадии. A=b*c+d.
Суть в том, что (b-k)*(c+x)=b*c+d. k - это отклонение, шаг. х - неизвестное.
После преобразований (d я отбросил,т.к. оно не сильно влияет)
приходим к следующему х = (kc) / (b - k).
Можно отбросить и k в знаменателе, тогда имеем: х = kc / b .
Если учесть, что в RSA c / b это где-то 10 в третьей-четвертой степени,
а k-max возьмем, скажем, 10 в пятой-седьмой степени,
то имеем число х-мах= 10^9.
Обратите внимание, что к и х максимальные, их можно отрегулировать и т.д.
Я к чему?
Отклонение х-мах на 9-10 знаков говорит о том, что только последние 9-10 знаков(максимум) изменятся. А остальные останутся на месте. И здесь нам поможет таблица.
По ней мы можем спускаться и вылавливать подходящие пары.
Если у нас таблица окончаний на глубину 15- 20,
то можно сравнивать 10-12 цифр слева по лексикографическому принципу (как в словаре).
Сравнивать придется ТОЛЬКО окончания, а сами большие числа будут где-то в базе,
куда каждый будет обращаться при раздаче.
Вероятность, что кандидатов будет много ничтожно мала. Поэтому процесс будет достаточно динамичным.
В любом случае, есть смысл просчитать, сколько эта процедура может занять времени.
В-общем, что мы имеем?
Мы имеем RSA-число А.
Имеем универсальную таблицу окончаний делителей этого числа (на глубину 20, 30, 40 цифр. Нужно найти оптимальную глубину).
Компьютеры запрашивают некоторый интервал чисел, сканируют таблицу и в случае нахождения пары-кандидата (вероятность чего чрезвычайно мала) проверяют ее с помощью алгоритма №1 или посылают на проверку.
Никаких сложных и больших вычислений не требуется.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
