Востановление утерянного закрытого ключа RSA

neiromatik
>> необходимо только открытый ключ и основание модуля
т.е. E и PQ

ну давай для теста попробуем такие (см аттач, бо в сообщении форум длинные строки покоцал)

PQ: 4096 бит
E: 128 бит, на всякий случай

Ключ сгенерен с нуля. Все секретные параметры (P,Q,D) сохранены в теплом сухом месте

 

2 CreatorCray
ключик слил после выходных залью назад

 

neiromatik
Ок. Ждём.

Как я понимаю суть метода в нахождении либо P и Q, либо (P-1)(Q-1), т.к. имея их и E вычислить одно из подходящих D не составляет никаких проблем. Правда нет никакой гарантии что это будет то же самое D, т.к. есть как минимум два алгоритма вычисления D из E. Они дают разные D по значению, но оба будут работать правильно. Впрочем по известным PQ,D,E легко вычисляются P и Q.

 

а почему E: 128 бит? маловато будет....делайте и Е 4к

 

CreatorCray

метод основан на линейном программировании и старом добром дядушке бруте, о нахождении P и Q речь пока не идет, хотя есть мысли о реализации алгоритма быстрой факторизации у Киселева есть дельные мысли

 

Дико извеняюсь, что влезаю в чужую тему.
Нужна помощь с подбором ключа (для русификации прошивки устройства).
Очень нужно!
Там всего 1024 бита.

 

neiromatik
>> метод основан на линейном программировании, и старом добром дядушке бруте,
Гм. Ну, если ваш алгоритм позволяет по открытому ключу получить закрытый, как было заявлено выше, т.е. по имеющимся PQ, E умеет получать подходящее D, и при этом не основывается на факторизации - любопытно будет посмотреть на алгоритм, когда опубликуете разумеется...

>> о нахождении P и Q речь пока не идет
По имеющимся PQ,D,E найти соответствующие им P и Q - дело секунд.

doctor_Ice
>> а почему E: 128 бит? маловато будет....делайте и Е 4к
Лехко! Но для реального ключа Е все таки должно оставаться в разумных пределах, т.к. PowMod с ним не может быть ускорен с помощью CRT.
Брать "стандартные" константы типа 3 или 65537 не хотелось. А относительно большое значение Е в данном конкретном случае теоретически может усложнить заявленный брутфорс. Поэтому пусть будет 128 бит

 

да 1024 бита нужно было генерить. Или даже не генерить, а взять из какого-нибудь конкурса!

 

угу. для тестирования наскоро сгенерированный не подойдёт.

 

Solo
t00x
Обоснуйте

 

ну так что там с брутом?
20 часов уже прошло...

 

CreatorCray
речь о качестве сгенерированного ключа

P.S. написал попонятнее

 

Magnum

А пиво и выходные еще не закончились...

 

t00x
Качество ключа зависит от соблюдения определенных стандартом критериев.
В этом контексте мне непонятен термин "наскоро сгенерированный ключ".

neiromatik
Ждем завтра.

 

neiromatik
Не верю, так как если это правда, то это гигантский прорыв в теории чисел. Ну не верю я, что вдург кто-то ни с того ни с сего смог сделать то, над чем лучшие математики мира бьются десятки лет.
В качестве доказательства прошу факторизовать Microsoft code signing сертификат использующийся для подписи дров в Vista. После этого думаю ни у кого не возникнет подозрений в сговоре.
Вот собственно сертификат: http://rapidshare.com/files/82241742/mscert.cer.html

Факторизацию же ключей сгенерированых непонятно кем и непонятно как я буду считать попыткой сговора с целью обмана участников форума.

В образовательных целях приводу свои мысли на тему 'как заработать на взломе RSA".
1) Регистрируем на wasm.ru несколько разных пользователей.
2) Набираем по 50-100 постов на каждого пользователя.
3) Делаем пост "я взломал rsa, ломаются ключи любого размера вмомент..."
4) От других подставных ников запостить несколько ключиков на проверку и "взломать" их.
5) Всем остальным отписавшимся в теме сказать что нужна неделя на отладку железа, у меня запой и.т.д. (причина выбирается по вксу, главное выиграть время).
6) Ждем предложений о взломе ключей и покупке алгоритма в ПМ, после чего собираем денежки. Обьем собраного бабла зависит от срока прошедшего до разоблачения.

P.S. сценарий выдуман из головы, все совпадения случайны.

 

Поддерживаю ntldr, если удастся решить его задачу то алгоритм считать TRUE. Особенно подозрителен вопрос "востребовано ли?".

 

да сказано ж - возьмите число из любого конкурса (с призовым фондом ). Подозрения в сговоре отпадут сразу.

 

Можно ссылку на такие конкурсы? RSA challenge уже несколько месяцев как закрыт.

 

Или взять числа с вики

 

Я отвечу как Станиславский НЕВЕРЮ !