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

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

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

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

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

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


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

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

Ты запутался. В проге должен быть только Modulus N и публичная экспонента. Приватную тогда можно найти с помощью RSATool2. Я ковырял прогу с LockBox. Но там автор закосячил и вместо публичной E экспоненты заюзал приватную D. Возможно у тебя также. Я находил E путём брутфорса, ушло чуть больше часа. Прога была Easy Karaoke Recorder. Брутфорс писал на основе самплов из LockBox. Отличить приватную от публичной легко. Приватная довольно большая, а публичная максимум FFFFFFFFh.

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

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

RSA Tool by tE!, там в эбауте кажись было.
А еще поисщи статью про взлом bart's crackme (по-моему так) от EOD/ucf там было что-то на эту тему.


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

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

PE_Kill пишет:
Отличить приватную от публичной легко. Приватная довольно большая, а публичная максимум FFFFFFFFh

Ты не прав. Паблик экспонента может быть такая же, как приватная. И юзать ее можно, также, как и приватную. Особой роли это не сыграет, все равно придется брутить точно также. Т.е. можно смело использовать в проге N и D или N и E пары, по барабану.

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

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

PE_Kill именно эта ситуевина и здесь - имеется приватная экспонента D. Про брутфорс думал, но в последнюю очередь - хотелось бы найти Е более м-м-м... научными методами, что-ли.
alexey_k спасибо, попробую найти.

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

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

Ara пробовал подсовывать в RSA Tool приватную экспоненту в качестве E - в результате не получалось расшифовать ключевую строку в тот же вид, что и у сабжевой проги (т.е. у сабжа при расшифровке получается напр. "23233", а у меня "Qef$56wedk+)(*&", такого рода)

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

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

soho
во нашел, тока на буржуйском, хотя у мну гдето на русском есть (дома)
eoda.by.ru/Data/Solutions/xt_ninja/ninja_sol.htm

ЗЫ
там оказывается и на русском, чет я тупанул

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

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

а вот еще, сходи на crackmes.de там крякмисов в крипто полно (а к ним и решения)...


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

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

soho ты скажи хоть что за прога. В LockBox очень просто можно определить какое число чем является.

Ara в LockBox приватная экспонента того же размера, что и Modulus N.

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

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

alexey_k интересные линки, как-то совсем забыл про такие...
PE_Kill прога зовется Coins Collector v2.5.0.21


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

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

soho пишет:
Ara пробовал подсовывать в RSA Tool приватную экспоненту в качестве E - в результате не получалось расшифовать ключевую строку в тот же вид, что и у сабжевой проги (т.е. у сабжа при расшифровке получается напр. "23233", а у меня "Qef$56wedk+)(*&", такого рода)

Так у тебя ничего не получится.
Возьми BigInt Calculator, потренируйся на коротких ключах криптовать-декриптовать текст, потом смотри прогу.


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

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

если есть N и D, то найти E можно только брутом

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

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

lord_Phoenix
а помоему нет , в туторе для какого-то крями (с того же crackmes.de) был способ (изврвтный правда, но был)

ЗЫ
могу и ошибаться


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

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

PE_Kill пишет:
Ты запутался. В проге должен быть только Modulus N и публичная экспонента

нифига, N и E нужны для шифровки, а N и D для расшифровки
alexey_k
ну сначала попробуй (врядли конечно авторы так затупили) 10001h. но тут выход - брут, причем не тупой брут с проверкой шифровки/расшифровки с текущим E, а более быстрый...
сколько бит N? если не очень большое - факторизуй его и дальше в бруте для каждого E проверяй:
D=E^(-1) mod ((P-1)*(Q-1))
так как это будет значиетльно быстрее чем вычисление M^E mod N. но для этого - надо факторизовать N.
также ни в коем случае не юзай сам локбокс в бруте - заюзай миракл хотя бы.. или либу раптора.. ну вообщем скорость, скорость и еще раз скорость.

пс. с удовольствием выслушаю тебя, если найдешь другой способ найти E

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

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

Если
P - первое большое простое число
Q - второе большое простое число
E - Public Exponent
и известны
N - Publuc Modulus (N = P*Q)
D - Private Exponent (D = E^(-1) mod ((P-1)*(Q-1))
то имеем два уравнения с тремя неизвестными, т.е. без брутфорса не обойтись .

Вопрос: как развернуть mod из второго уравнения с тем, чтобы выразить Е?


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

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

soho пишет:
то имеем два уравнения с тремя неизвестными, т.е. без брутфорса не обойтись

где ты увидел 3 неизвестные - для меня загадка.. мы не знаем только E, P и Q не в счет - если N не сильно большое(до 512 бит) их можно найти.
soho пишет:
Вопрос: как развернуть mod из второго уравнения с тем, чтобы выразить Е?

если бы все было так легко ;p

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

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

> Приватная довольно большая, а публичная максимум FFFFFFFFh.
E это любое число так что наибольший общаи делитель у E и (p-1)*(q-1) был единица..

> Ara в LockBox приватная экспонента того же размера, что и Modulus N.
не в тулбокс а в RSA... по идее алгоритма все операции проводятся в поле размером N (тот mod N в формулах)... это и даёт выравнивание размера...

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

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

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


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

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

alexey_k
ну и что? скажешь сервисы не брутят? =) и все-таки не видел я подобных сервисов..
SLV пишет:
не в тулбокс а в RSA... по идее алгоритма все операции проводятся в поле размером N (тот mod N в формулах)... это и даёт выравнивание размера...

э, все зависит от размера p и q, но про F(N) правильно =)

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

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

lord_Phoenix, какая разница как говорить, по сути N = P*Q


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

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

SLV
ну просто я начал с самого начала.. ты говоришь, что все зависит от N - а N ~ p,q так как это их произвдение =)

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

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

lord_Phoenix
на crackmes.de был солюшен (именно написание кейгена) для кейгенми с RSA-1024.


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

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

alexey_k
из последних крякмисов, что смотрел - с рса1024 помню только старый TKM триал от ged'а..
там тоже была расшифровка... но там были известны p и q, тость мы могли найти d и все кейгенится ;) ща вот подумал.. может быть это может помочь в твоем случае:
N=P*Q
dP = D mod (P-1)
dQ = D mod (Q-1)
имеем:
M = C^dP mod P
M = C^dQ mod P
используя кит.теорему об остатках получаем, что:
M = C^D mod (P*Q)
прикол в том, что данный метод в 4 раза быстрее просто C=M^D mod N.
E*D mod (P-1)(Q-1) = 1
исходя из метода, описанного выше:
C = M^(dP^(-1) mod (P-1)) mod P
C = M^(dQ^(-1) mod (Q-1)) mod Q
решив данные уравнения используя все ту же, кит.теорему об остатках - найдем C. тоесть получим зашифр. M, без знания E. но для всего этого намнадо знать факторы N. а если тебе именно найдо найти E - то это только брут


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

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

В этой проге RSA-128, по крайней мере очень на это похоже. Тока пришел, смотреть некогда


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

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

Ara пишет:
В этой проге RSA-128

ну тогда брутить E себе дороже :p проще разложить N и юзаюзатьlord_Phoenix пишет:
C = M^(dP^(-1) mod (P-1)) mod P
C = M^(dQ^(-1) mod (Q-1)) mod Q

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

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

lord_Phoenix пишет:
если тебе именно найдо найти E...

нет, конечно нет. Ты совверно считаешь, что нужно получить свой С из М!

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

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

lord_Phoenix
Правильно понял алгоритм действий:
1. Факторизуем N - получаем P, Q;
2. Вычисляем dP, dQ;
3. Подставляем в
C = M^(dP^(-1) mod (P-1)) mod P
C = M^(dQ^(-1) mod (Q-1)) mod Q

и вуаля?


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

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

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
которую решим используя кит.теорему об остатках
вуаля ;)


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

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

lord_Phoenix пишет:
ну тогда брутить E себе дороже

всмысле? Оно же 5 сек сбрутится..


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

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

Ara пишет:
всмысле? Оно же 5 сек сбрутится..

5 сек?? ну хз хз, чисел я не видел...и зачем брутить что-то если есть норм. метод? конечно все-таки придется факторизовать N.. давай числа..и для сравнения факторизуем его и попробуем отдельно сбрутить E?!
. 1 . 2 . 3 . >>
 eXeL@B —› Основной форум —› RSA восстановить public exponent или...

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