Русский / Russian English / Английский

Сейчас на форуме: averitas, shura_k, Xlab0s, hnrtkjby8945yub8n, JC (+7 невидимых)
 · Начало · Статистика · Регистрация · Поиск · ПРАВИЛА ФОРУМА · Язык · RSS ·

 eXeL@B —› Основной форум —› RSA восстановить public exponent или...
<< . 1 . 2 . 3 . >>
Посл.ответ Сообщение

Ранг: 30.6 (посетитель)
Статус: Участник

Создано: 26 декабря 2006 02:17 · Поправил: soho New!
Цитата · Личное сообщение · #1

... или я чего-то не догоняю.
Разбираюсь с прогой - защищена старой библиотекой LockBox, используется RSA.
При расшифровке регистрации создается пара ключей private и public. Затем явно задается модуль и экспонента для private ключа и, ессно этим и расшифровывается.
Вопрос: если я ничего не напутал, то как найти экспоненту для public ключа?

Ранг: 30.6 (посетитель)
Статус: Участник

Создано: 26 декабря 2006 07:31 New!
Цитата · Личное сообщение · #2

(Гм, чувствую себя в танке, засевшем в гринпинской трясине)
Нет, кешна описание теоремы найти не составило труда...
В любом случае спасибо

Ранг: 30.6 (посетитель)
Статус: Участник

Создано: 26 декабря 2006 07:37 New!
Цитата · Личное сообщение · #3

Для примера, там используется два разных RSA-ключа 128 и 256:
N128 = 21DBB838DFC93DA702AA69A11EEB6E93
D128 = EBE37EB917D3CEDB958D5E1AA4E47161

N256 = E938A5AAEA14477DD1506E060334D9E0FA1F238B7F14A60C90649D11EF4A92C3
D256 = 856ACB79EAEABC6C1614796673C08B3D96F520235144BDDA861FD942DE023C86


Ранг: 353.0 (мудрец)
Статус: Участник
resreveR

Создано: 26 декабря 2006 07:56 · Поправил: lord_Phoenix New!
Цитата · Личное сообщение · #4

21DBB838DFC93DA702AA69A11EEB6E93 = 39AE7D5BD6591F * 9644B365015792180D
вперед юзать методу, которую я описал.. факторизация заняла доли секунды.. жду пока Ара сбрутить E ;)
soho пишет:
Нет, кешна описание теоремы найти не составило труда...
В любом случае спасибо

заюзай миракл..там есть все,что тебе надо


Ранг: 793.4 (! !)
Статус: Участник
Шаман

Создано: 26 декабря 2006 19:29 New!
Цитата · Личное сообщение · #5

У меня брут E для lockbox->RSA-256 заняло 1ч 20 мин. Но там брут был на сех фрэймах построен, без них я думаю 20 мин вполне бы хватило.


Ранг: 353.0 (мудрец)
Статус: Участник
resreveR

Создано: 26 декабря 2006 21:12 New!
Цитата · Личное сообщение · #6

если все таки брутить, то используя миракл. да и брут не в лоб, а "умный" (описал в первом моем посте в этой теме). и брут то будет быстрый. но лично мне нравится метод, описанный выше. и E не надо, и расшифровка намного быстрее


Ранг: 1288.1 (!!!!)
Статус: Модератор

Создано: 27 декабря 2006 06:22 New!
Цитата · Личное сообщение · #7

lord_Phoenix
А как насчет 256? Мне просто катострофически некогда, хотя бы почитаю что говорят...Вообще очень хорошо было бы статейку накатать про RSA. Очень уж много вопросов про это...Можно объеденить усилия и наебошить приличную мегастотью, с примерами...

Ранг: 135.2 (ветеран)
Статус: Участник

Создано: 27 декабря 2006 06:27 · Поправил: alexey_k New!
Цитата · Личное сообщение · #8

Ara
дейсвительно, статья нужна, но не на примере конкретной проги, а П0лноЕ описалово RSA + примеры: на собственном крякми (+ можно и на чужом), и на конкретных прогах (не сильно вдаваясь в подробности)...
ИМХО

ЗЫ
как-то читал Fucking Hoax (кажись так), там есть уроки Crypto для новичков, хде разжованы (причем хорошо) хэш ф-ии, но я слышал, что этот журнал уже не выпускают (как всегда бывает), может что подобное замутить?...


Ранг: 353.0 (мудрец)
Статус: Участник
resreveR

Создано: 27 декабря 2006 06:40 New!
Цитата · Личное сообщение · #9

Ara
с 256 все также, просто мне лень было ждать 40 минут, пока факторизнется N. =)
Ara пишет:
Вообще очень хорошо было бы статейку накатать про RSA. Очень уж много вопросов про это...Можно объеденить усилия и наебошить приличную мегастотью, с примерами...

я за.. время есть..
alexey_k пишет:
дейсвительно, статья нужна, но не на примере конкретной проги, а П0лноЕ описалово RSA + примеры: на собственном крякми (+ можно и на чужом), и на конкретных прогах (не сильно вдаваясь в подробности)...
ИМХО

могу написать именно про сам алго - математику.. на примере крякмисов.. таких с рса у меня навалом.. ну также упомяну всякие "хитрости", вроде метода шифрования без E =)


Ранг: 1288.1 (!!!!)
Статус: Модератор

Создано: 27 декабря 2006 06:44 New!
Цитата · Личное сообщение · #10

Крякмисы не катят, берем конкретные проги. Их тоже навалом. И делаем путную статью.Наверно, после праздников


Ранг: 353.0 (мудрец)
Статус: Участник
resreveR

Создано: 27 декабря 2006 06:50 New!
Цитата · Личное сообщение · #11

Ara
давай =) а крякмисы как раз катят, именно на них можно показать конкретные атаки на рса не нарушая ничьих прав ;) давай так - проги ищешь ты =) для стандартного примера(конверторы) - с шифровкой, прога у меня уже есть.. давай линк на прогу, которую ломает топикстартер =)

Ранг: 135.2 (ветеран)
Статус: Участник

Создано: 27 декабря 2006 06:52 New!
Цитата · Личное сообщение · #12

lord_Phoenix
Буду очень рад (и не только я), если напишешь...

Ранг: 135.2 (ветеран)
Статус: Участник

Создано: 27 декабря 2006 06:56 New!
Цитата · Личное сообщение · #13

lord_Phoenix
вот, точно не помню, но либо ALL Video Converter, либо #1 Video Converter - там RSA точно есть.


Ранг: 1288.1 (!!!!)
Статус: Модератор

Создано: 27 декабря 2006 06:59 New!
Цитата · Личное сообщение · #14

lord_Phoenix пишет:
давай линк на прогу, которую ломает топикстартер =)

www.serfox.com/files/CC2Setup.exe


Ранг: 353.0 (мудрец)
Статус: Участник
resreveR

Создано: 27 декабря 2006 07:19 New!
Цитата · Личное сообщение · #15

начну писать завтра мб..
alexey_k
все конверторы кароч =)
Ara
спс

Ранг: 30.6 (посетитель)
Статус: Участник

Создано: 27 декабря 2006 08:16 · Поправил: soho New!
Цитата · Личное сообщение · #16

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


Ранг: 353.0 (мудрец)
Статус: Участник
resreveR

Создано: 27 декабря 2006 08:28 · Поправил: lord_Phoenix New!
Цитата · Личное сообщение · #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 - простые.. не знаю,что тебя смутило - не вижу никаких проблем.. пиши конкретнее =)

Ранг: 30.6 (посетитель)
Статус: Участник

Создано: 27 декабря 2006 08:51 New!
Цитата · Личное сообщение · #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 с тем, чтобы отсеивать "плохие". Или неправильно?


Ранг: 353.0 (мудрец)
Статус: Участник
resreveR

Создано: 27 декабря 2006 09:01 · Поправил: lord_Phoenix New!
Цитата · Личное сообщение · #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

Ранг: 30.6 (посетитель)
Статус: Участник

Создано: 27 декабря 2006 09:49 · Поправил: soho New!
Цитата · Личное сообщение · #20

lord_Phoenix "убрал" для пущей формализации
имелось ввиду, что на этапе факторизации N отбираются те P и Q, которые удовлетворяют условию (см. выше), ну или его упрощенной форме.
Кста, во ходу поисков готовых bigint библиотек попалась на глаза т.н. Arageli (_http://www.unn.ru/cs/arageli), которая, кроме всего прочего, позволяет производить символические вычисления (!)


Ранг: 353.0 (мудрец)
Статус: Участник
resreveR

Создано: 27 декабря 2006 10:06 New!
Цитата · Личное сообщение · #21

что ты несешь =) я тебе про шифрование без E, что тебе собственно и надо, а ты мне про факторизацию..

Ранг: 30.6 (посетитель)
Статус: Участник

Создано: 27 декабря 2006 10:10 New!
Цитата · Личное сообщение · #22

Брррр, хочешь сказать, что в твоем методе P и Q берутся из неоткуда?


Ранг: 353.0 (мудрец)
Статус: Участник
resreveR

Создано: 27 декабря 2006 10:14 New!
Цитата · Личное сообщение · #23

я уже сказал, что p и q мы должны знать, тоесть для использования метода - него надо факторизовать N..


Ранг: 793.4 (! !)
Статус: Участник
Шаман

Создано: 27 декабря 2006 23:40 New!
Цитата · Личное сообщение · #24

soho ёптить столько времени прошло. Возьми сампл ил LockBox сделай брут, для
soho пишет:
N256 = E938A5AAEA14477DD1506E060334D9E0FA1F238B7F14A60C90649D11EF4A92C3
D256 = 856ACB79EAEABC6C1614796673C08B3D96F520235144BDDA861FD942DE023C86

Ты найдешь E за 30 мин на средней машине.


Ранг: 353.0 (мудрец)
Статус: Участник
resreveR

Создано: 28 декабря 2006 00:50 New!
Цитата · Личное сообщение · #25

рекилл, ну в смысл брута? я уже ведь и готовый сорс ему показал.. брутить - не наш метод, и уж тем более не на дельфи

Ранг: 160.1 (ветеран)
Статус: Участник

Создано: 28 декабря 2006 01:45 · Поправил: infern0 New!
Цитата · Личное сообщение · #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

второй вариант более правилен (переворот для обеих чисел)

Ранг: 160.1 (ветеран)
Статус: Участник

Создано: 28 декабря 2006 01:48 · Поправил: infern0 New!
Цитата · Личное сообщение · #27

lord_Phoenix пишет:
21DBB838DFC93DA702AA69A11EEB6E93 = 39AE7D5BD6591F * 9644B365015792180D

у меня получилось:
PRIME FACTOR: 43
PRIME FACTOR: 80F
PRIME FACTOR: 39AE7D5BD6591F
PRIME FACTOR: 473F854437A8A1

причем size=126bits для 21DBB838DFC93DA702AA69A11EEB6E93

видимо надо переворачивать, ибо не должно быть столько множителей

а вообще тестовые зашифрованные данные нужны


Ранг: 353.0 (мудрец)
Статус: Участник
resreveR

Создано: 28 декабря 2006 01:59 New!
Цитата · Личное сообщение · #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.
надо данные для теста от топикстартера и можно все проверить


Ранг: 353.0 (мудрец)
Статус: Участник
resreveR

Создано: 28 декабря 2006 02:29 New!
Цитата · Личное сообщение · #29

прочитав еще раз весь топик и поговорив с infern0 решил сделать вывод =)
n = 936EEB1EA169AA02A73DC9DF38B8DB21
d = 6171E4A41A5E8D95DBCED317B97EE3EB
e = 3623
можно юзать =) вообщем надо данные и еще раз данные =).

Ранг: 160.1 (ветеран)
Статус: Участник

Создано: 28 декабря 2006 02:29 New!
Цитата · Личное сообщение · #30

lord_Phoenix пишет:
и заюзал d как e

а их можно смело менять местами - возьми rsatool, сгенери ключ и попробуй


Ранг: 353.0 (мудрец)
Статус: Участник
resreveR

Создано: 28 декабря 2006 04:13 New!
Цитата · Личное сообщение · #31

рса256 в этой проге:
E:38D5
N:C3924AEF119D64900CA6147F8B231FFAE0D93403066E50D17D4714EAAAA538E9
D:863C02DE42D91F86DABD44512320F5963D8BC073667914166CBCEAEA79CB6A85
<< . 1 . 2 . 3 . >>
 eXeL@B —› Основной форум —› RSA восстановить public exponent или...

Видеокурс ВЗЛОМ