Сейчас на форуме: Slinger (+6 невидимых) |
![]() |
eXeL@B —› Основной форум —› RSA восстановить public exponent или... |
<< . 1 . 2 . 3 . >> |
Посл.ответ | Сообщение |
|
Создано: 26 декабря 2006 02:17 · Поправил: soho · Личное сообщение · #1 ... или я чего-то не догоняю. Разбираюсь с прогой - защищена старой библиотекой LockBox, используется RSA. При расшифровке регистрации создается пара ключей private и public. Затем явно задается модуль и экспонента для private ключа и, ессно этим и расшифровывается. Вопрос: если я ничего не напутал, то как найти экспоненту для public ключа? ![]() |
|
Создано: 26 декабря 2006 07:31 · Личное сообщение · #2 |
|
Создано: 26 декабря 2006 07:37 · Личное сообщение · #3 |
|
Создано: 26 декабря 2006 07:56 · Поправил: lord_Phoenix · Личное сообщение · #4 21DBB838DFC93DA702AA69A11EEB6E93 = 39AE7D5BD6591F * 9644B365015792180D вперед юзать методу, которую я описал.. факторизация заняла доли секунды.. жду пока Ара сбрутить E ;) soho пишет: Нет, кешна описание теоремы найти не составило труда... В любом случае спасибо заюзай миракл..там есть все,что тебе надо ----- Тут не могла быть ваша реклама ![]() |
|
Создано: 26 декабря 2006 19:29 · Личное сообщение · #5 |
|
Создано: 26 декабря 2006 21:12 · Личное сообщение · #6 |
|
Создано: 27 декабря 2006 06:22 · Личное сообщение · #7 |
|
Создано: 27 декабря 2006 06:27 · Поправил: alexey_k · Личное сообщение · #8 Ara дейсвительно, статья нужна, но не на примере конкретной проги, а П0лноЕ описалово RSA + примеры: на собственном крякми (+ можно и на чужом), и на конкретных прогах (не сильно вдаваясь в подробности)... ИМХО ЗЫ как-то читал Fucking Hoax (кажись так), там есть уроки Crypto для новичков, хде разжованы (причем хорошо) хэш ф-ии, но я слышал, что этот журнал уже не выпускают (как всегда бывает), может что подобное замутить?... ![]() |
|
Создано: 27 декабря 2006 06:40 · Личное сообщение · #9 Ara с 256 все также, просто мне лень было ждать 40 минут, пока факторизнется N. =) Ara пишет: Вообще очень хорошо было бы статейку накатать про RSA. Очень уж много вопросов про это...Можно объеденить усилия и наебошить приличную мегастотью, с примерами... я за.. время есть.. alexey_k пишет: дейсвительно, статья нужна, но не на примере конкретной проги, а П0лноЕ описалово RSA + примеры: на собственном крякми (+ можно и на чужом), и на конкретных прогах (не сильно вдаваясь в подробности)... ИМХО могу написать именно про сам алго - математику.. на примере крякмисов.. таких с рса у меня навалом.. ну также упомяну всякие "хитрости", вроде метода шифрования без E =) ----- Тут не могла быть ваша реклама ![]() |
|
Создано: 27 декабря 2006 06:44 · Личное сообщение · #10 |
|
Создано: 27 декабря 2006 06:50 · Личное сообщение · #11 Ara давай =) а крякмисы как раз катят, именно на них можно показать конкретные атаки на рса не нарушая ничьих прав ;) давай так - проги ищешь ты =) для стандартного примера(конверторы) - с шифровкой, прога у меня уже есть.. давай линк на прогу, которую ломает топикстартер =) ----- Тут не могла быть ваша реклама ![]() |
|
Создано: 27 декабря 2006 06:52 · Личное сообщение · #12 |
|
Создано: 27 декабря 2006 06:56 · Личное сообщение · #13 |
|
Создано: 27 декабря 2006 06:59 · Личное сообщение · #14 |
|
Создано: 27 декабря 2006 07:19 · Личное сообщение · #15 |
|
Создано: 27 декабря 2006 08:16 · Поправил: soho · Личное сообщение · #16 Если с брутфорсом все прозрачно, то, lord_Phoenix, с твоим решением нужен буксир для моего танка (все-таки мОзги не позволили осилить все глубину китайской мысли полутысячилетней давности)... Плз, развернутую выкладку последней системы! ![]() ![]() |
|
Создано: 27 декабря 2006 08:28 · Поправил: lord_Phoenix · Личное сообщение · #17 soho lord_Phoenix пишет: soho пишет: C = M^(dP^(-1) mod (P-1)) mod P C = M^(dQ^(-1) mod (Q-1)) mod Q это система уравнений.. для упрощения - вычислим: eP = dP^(-1) mod (P-1) eQ = dQ^(-1) mod (Q-1) получим систему: C = M^eP mod P C = M^eQ mod Q которую решим используя кит.теорему об остатках вуаля ;) C = M^eP mod P C = M^eQ mod Q это именно система, тоесть нам надо найти такое C,чтобы оба условия выполнялись - это и будет зашифрованное M. кит.теорема об остатках гласит,что система уравнений вида: a = b_1 mod c_1 a = b_2 mod c_2 ... a = b_n mod c_n всегда имеет решение.. (c_1,c_2,...c_n - простые) наша система имеет решение, так как P,Q - простые.. не знаю,что тебя смутило - не вижу никаких проблем.. пиши конкретнее =) ----- Тут не могла быть ваша реклама ![]() |
|
Создано: 27 декабря 2006 08:51 · Личное сообщение · #18 lord_Phoenix пишет: надо найти такое C,чтобы оба условия выполнялись - ага (не все потеряно!).. Другими словами, можно забыть про китайцев и записать, что M^eP mod P = M^eQ mod Q или M^((D mod (P-1))^(-1) mod (P-1)) mod P = M^((D mod (Q-1))^(-1) mod (Q-1)) mod Q прально? Тогда логично будет выразить P или Q с тем, чтобы отсеивать "плохие". Или неправильно? ![]() |
|
Создано: 27 декабря 2006 09:01 · Поправил: lord_Phoenix · Личное сообщение · #19 soho неправильно %) у нас была единственная неизвестная - C - и ты ее "убрал" =) напомню тебе,что м знаем P,Q,D,M и не знаем C. вот пример решения с помощью миракла: big m,c,ep,eq,factors[2],rem[2]; big_chinese bc; /* C = M^eP mod P */ powmod(m,ep,factors[0],rem[0]); /* C = M^eQ mod Q */ powmod(m,eq,factors[1],rem[1]); /* решаем нашу систему */ crt_init(&bc,2,factors); crt(&bc,rem,c); crt_end(&bc); ps. factors[2] - массив - P и Q ----- Тут не могла быть ваша реклама ![]() |
|
Создано: 27 декабря 2006 09:49 · Поправил: soho · Личное сообщение · #20 lord_Phoenix "убрал" для пущей формализации имелось ввиду, что на этапе факторизации N отбираются те P и Q, которые удовлетворяют условию (см. выше), ну или его упрощенной форме. Кста, во ходу поисков готовых bigint библиотек попалась на глаза т.н. Arageli (_http://www.unn.ru/cs/arageli), которая, кроме всего прочего, позволяет производить символические вычисления (!) ![]() |
|
Создано: 27 декабря 2006 10:06 · Личное сообщение · #21 |
|
Создано: 27 декабря 2006 10:10 · Личное сообщение · #22 |
|
Создано: 27 декабря 2006 10:14 · Личное сообщение · #23 |
|
Создано: 27 декабря 2006 23:40 · Личное сообщение · #24 soho ёптить столько времени прошло. Возьми сампл ил LockBox сделай брут, для soho пишет: N256 = E938A5AAEA14477DD1506E060334D9E0FA1F238B7F14A60C90649D11EF4A92C3 D256 = 856ACB79EAEABC6C1614796673C08B3D96F520235144BDDA861FD942DE023C86 Ты найдешь E за 30 мин на средней машине. ----- Yann Tiersen best and do not fuck ![]() |
|
Создано: 28 декабря 2006 00:50 · Личное сообщение · #25 |
|
Создано: 28 декабря 2006 01:45 · Поправил: infern0 · Личное сообщение · #26 soho пишет: N128 = 21DBB838DFC93DA702AA69A11EEB6E93 D128 = EBE37EB917D3CEDB958D5E1AA4E47161 n надо перевернуть p: E601338639040187 q: A418A6F3CA4B8817 n: 936EEB1EA169AA02A73DC9DF38B8DB21 e: 6171E4A41A5E8D95DBCED317B97EE3EB d: 3623 либо p: E601338639040187 q: A418A6F3CA4B8817 n: 936EEB1EA169AA02A73DC9DF38B8DB21 e: EBE37EB917D3CEDB958D5E1AA4E47161 d: 56399F882A44D58A9E2A3B14E086C0C5 второй вариант более правилен (переворот для обеих чисел) ![]() |
|
Создано: 28 декабря 2006 01:48 · Поправил: infern0 · Личное сообщение · #27 lord_Phoenix пишет: 21DBB838DFC93DA702AA69A11EEB6E93 = 39AE7D5BD6591F * 9644B365015792180D у меня получилось: PRIME FACTOR: 43 PRIME FACTOR: 80F PRIME FACTOR: 39AE7D5BD6591F PRIME FACTOR: 473F854437A8A1 причем size=126bits для 21DBB838DFC93DA702AA69A11EEB6E93 видимо надо переворачивать, ибо не должно быть столько множителей а вообще тестовые зашифрованные данные нужны ![]() |
|
Создано: 28 декабря 2006 01:59 · Личное сообщение · #28 infern0 пишет: видимо надо переворачивать, ибо не должно быть столько множителей если перевернуть, то размер будет ровно 128 бит, а множители: A418A6F3CA4B8817=E601338639040187*A418A6F3CA4B8817 хм.. я почему то сразу не подумал перевернуть, но на 2 множителя все же разложил =) infern0 пишет: n надо перевернуть p: E601338639040187 q: A418A6F3CA4B8817 n: 936EEB1EA169AA02A73DC9DF38B8DB21 e: 6171E4A41A5E8D95DBCED317B97EE3EB d: 3623 либо p: E601338639040187 q: A418A6F3CA4B8817 n: 936EEB1EA169AA02A73DC9DF38B8DB21 e: EBE37EB917D3CEDB958D5E1AA4E47161 d: 56399F882A44D58A9E2A3B14E086C0C5 имхо неверное.. ты n перевернул, а d нет.. да и заюзал d как e. в проге - расшифровка - тоесть m = c^d mod n, для кейгена надо шифровать - c = m^e mod n. надо данные для теста от топикстартера и можно все проверить ----- Тут не могла быть ваша реклама ![]() |
|
Создано: 28 декабря 2006 02:29 · Личное сообщение · #29 |
|
Создано: 28 декабря 2006 02:29 · Личное сообщение · #30 |
|
Создано: 28 декабря 2006 04:13 · Личное сообщение · #31 |
<< . 1 . 2 . 3 . >> |
![]() |
eXeL@B —› Основной форум —› RSA восстановить public exponent или... |