ковыряю последний CrypKey
RSA Tolls by tE по Public Exp считает Private Exp, а мне нужно наоборот

кто может помочь проверить одну идею?

есть: Private Exp. = 0xB3A791AF1DA1A5BB, Modulus N = 0x58554667001E6CEB, PRIME P = 0x18A677D, PRIME Q = 0x3955D46287
нужно посчитать Public Exp.

-----
...или ты работаешь хорошо, или ты работаешь много...

| Сообщение посчитали полезным:

полагаю нужно вычислить e
d = (e ^ -1) mod @n
D и N получается известны
@n - эйлер от n

в математике не очень силен

попробуй e = 0x1001

| Сообщение посчитали полезным:

А какая разница, считать D через E, если известно разложение N, или наоборот? 1 алгоритм должен работать. Ну и да, обычно E берётся достаточно стандартным.
И разложение N обычно обозначается P и Q, в первом посте то ли что-то напутано, то ли хз откуда взялась D.
reversecode пишет:
d = (e ^ -1) mod n
Там обратное берётся не по N, а по Эйлеру от N.

| Сообщение посчитали полезным: reversecode

Только брутфорс

| Сообщение посчитали полезным:

reversecode
мб 0х10001 !? но не катит

Archer
поправил

tihiy_grom
а брутить в каком диапазоне е ?

-----
...или ты работаешь хорошо, или ты работаешь много...

| Сообщение посчитали полезным:

Ещё раз: один алгоритм должен работать. А именно нахождение обратного числа по модулю. Обычно через расширенный алгоритм Евклида это делается. И он достаточно быстр.
И да, меня одного смущает, что D>N, чего быть не может?

| Сообщение посчитали полезным:

Если не ошибаюсь, то решал подобную задачу с помощью математики
http://reference.wolfram.com/mathematica/ref/PowerMod.html

ed=1 mod (p-1)(q-1)

Речь об этом http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

tihiy_grom
жжешь

-----
ds

| Сообщение посчитали полезным:

выбор e, вообще то строго ограничен
можно для начала попробовать рекомендуемые
--> Link <--

| Сообщение посчитали полезным:

Если всё правильно спросил, а я посчитал, то Е=2392910853562603931 (dec)

но Арчер прав, что-то здесь не так в условии (может и не РСА)

BfoX пишет:
0х10CD889542920DE3, 0хFAB3B5F3C60243FD, 0хA077EF, 0х18FF3BD36D3
Вот тут Е = A6F98C3202BC3DAB, можете проверить.

-----
ds

| Сообщение посчитали полезным:

reversecode пишет:
выбор e, вообще то строго ограничен
Если вдаваться в ограничения на E, то таких чисел слишком много, чтобы перебрать. Строго говоря, оно должно быть меньше Эйлера от Н и взаимно простое с ним. И на этом ограничения заканчиваются. А таких чисел дофига. Остальные ограничения, типа небольшого числа единичных битов в двоичной записи, приходят из число практических соображений, что так возводить в степень быстрее, но не более того.
Так что я бы лучше РАЕ прошёлся. Меня больше смущает, что D>N, чего быть не может.

| Сообщение посчитали полезным: DimitarSerg

Делал давно, некоторые числа повторяются с твоими:
http://sebsauvage.net/paste/?606c8c2d666384f3#CJjlsUlNCjpWBYpR96A1AMr3jCyl2XT2C3JMN3m71aE=

Только у меня порядок такой:
Public Exponent (E), Modulus (N), Private Exponent(D)

Как делал слабо помню (дело было больше 5 лет назад). Но должно быть просто.
Скорее всего так:
Факторим N, вставляем вместо паблик экспоненты приватную, нажимаем Calc D. И в поле приватной экспоненты получаем - нашу паблик экспоненту. Потом меняем их местами и снова нажимаем Calc D.
С набором 0х10CD889542920DE3, 0хFAB3B5F3C60243FD, 0хA077EF, 0х18FF3BD36D3 - работает четко.

А вот с первым примером не работает, возможно криво сдампилось, проверь еще раз ключики.

| Сообщение посчитали полезным: tihiy_grom

DimitarSerg пишет:
Вот тут Е = A6F98C3202BC3DAB, можете проверить.

правильно

bbuc
да, ваши данные для старой таблицы crypkey до v7.3
у меня первые три набора - для crypkey v7.6+

у меня порядок такой:
Private Exponent(D), Modulus (N), Prime (P), Prime (Q)

нажать Calc D. не получится - ограничение числа не более 9999999999

-----
...или ты работаешь хорошо, или ты работаешь много...

| Сообщение посчитали полезным:

BfoX пишет:
нажать Calc D. не получится - ограничение числа не более 9999999999

Способ с математикой и формулой ed=1 mod (p-1)(q-1) должен всегда прокатывать ;)

Для примера:
0х7DEE2D279FC6CBDD, 0хE8F9B1360625C803, 0х6165DB5, 0х26459DE1D7

D = 0х7DEE2D279FC6CBDD (9074239947405708253)
P = 0х6165DB5 (102129077)
Q = 0х26459DE1D7(164376732119)

e * 9074239947405708253 =1 mod (102129077-1)(164376732119-1)
e * 9074239947405708253 =1 mod 16787643767110862968



PowerMod[9074239947405708253, -1, 16787643767110862968]

Shift+Enter, вуаля

add:
Если не охота ставить математику, можно посчитать онлайн


-----
ds

| Сообщение посчитали полезным: tempread, SReg

BfoX пишет:
нажать Calc D. не получится - ограничение числа не более 9999999999
Это ограничение старой версии. Вот более новая , от 2004 года:
http://rghost.net/45224057

| Сообщение посчитали полезным:

DimitarSerg пишет:
Если не охота ставить математику

на чём посоветуете реализовать?

bbuc
спасибо, посмотрю

-----
...или ты работаешь хорошо, или ты работаешь много...

| Сообщение посчитали полезным:

BfoX пишет:
вручную лопатить 128 факторизаций
Факторизацию с помощью msieve или yafu. А PowerMod на любимом языке программирования

| Сообщение посчитали полезным:

BfoX пишет:
на чём посоветуете реализовать?
Я пишу онли Делфи+асм, так что много не насоветую.
Но я бы решал с помощью FGInt, тем более там есть почти всё готовые функи, типа FGIntModExp, FGIntModInv

Если дельфа подходит - могу наваять функу.

add: или задача стоит еще и факторизировать в процессе выполнения ?

-----
ds

| Сообщение посчитали полезным:

DimitarSerg пишет:
или задача стоит еще и факторизировать в процессе выполнения ?

50/50 =)

64 надо факторизовать, остальные 64 - уже с P и Q сложены в таблицу

-----
...или ты работаешь хорошо, или ты работаешь много...

| Сообщение посчитали полезным:

BfoX
Тогда быстрее с msieve
Создать worktodo.ini и туда список всех N в десятичной системе. Будет лог-файл, который при желании можно распарсить и привести к нужному виду.

-----
ds

| Сообщение посчитали полезным:

Если нужно встроить факторизатор в свой проект, то в исходниках MIRACL есть примеры всех основных методов факторизации, они хоть и не шустрые, т.к. сам миракл не отличается скоростью, но на 64-битних числах думаю это не актуально.
* brute.c/cpp - brute force division by small primes
* brent.c/cpp - Pollard Rho method as improved by Brent
* pollard.c/cpp - Pollard (p-1) method
* williams.c/cpp - Williams (p+1) method
* lenstra.c/cpp - Lenstra's Elliptic Curve method
* qsieve.c/cpp - The Multiple polynomial quadratic sieve

| Сообщение посчитали полезным:

только про miracl хотел сказать

5559_12.04.2013_EXELAB.rU.tgz - main.cpp

| Сообщение посчитали полезным:

Вот на питоне наваял с вызовом msieve для факторизации.

для работы нужны
import re
import subprocess
import shlex

для примера использую те-же значения что и в примере DimitarSerg
D = 0x7DEE2D279FC6CBDD
PQ = 0xE8F9B1360625C803

результат
p = 102129077
q = 164376732119
e = 13599029403125677005

Для автомата нужно числа в массивы набить и сделать цикл.


4f66_12.04.2013_EXELAB.rU.tgz - blox.rar

-----
127.0.0.1, sweet 127.0.0.1

| Сообщение посчитали полезным:

Сделал цикл на данных из первого поста

d = 0x8521EBA4563F6D91
p = 0x1DEF63F9
q = 0x3E8225E8B
e = 0x361212E505A8041

d = 0x840E8442916781A7
p = 0xC29789
q = 0xBBF792605B
e = 0x1CBB2A39B1EDD697

d = 0xA510CD4E648160D1
p = 0x3D05E9
q = 0x3C8DEC1AB49
e = 0xDEFCC2A24F03971

d = 0x5A01294BBAD47089
p = 0x3B3BDC5
q = 0x1A345E32C7
e = 0x2CA42483BE7E8F41

d = 0x61451C6659D58089
p = 0x4601E7
q = 0x16F9E64EA4B
e = 0x508E11FEBC2FECFD

d = 0x7DEE2D279FC6CBDD
p = 0x6165DB5
q = 0x26459DE1D7
e = 0xBCB97530FF65FBCD

d = 0x10CD889542920DE3
p = 0xA077EF
q = 0x18FF3BD36D3
e = 0xA6F98C3202BC3DAB

ЗЫ: Добавил для проверки крипт/декрипт

316d_12.04.2013_EXELAB.rU.tgz - crypkey.py

-----
127.0.0.1, sweet 127.0.0.1

| Сообщение посчитали полезным: stas_02

спасибо всем откликнувшимся - буду разбираться с таблицами

-----
...или ты работаешь хорошо, или ты работаешь много...

| Сообщение посчитали полезным:

без проблем... с тебя эмуль ну или просто Эйлера с днем рождения поздравь

| Сообщение посчитали полезным:

drone

подключил miracl, но он не хочет брать часть данных в нех-виде - воспринимает старший разряд как знаковый. типа __int64. соответственно и не считает. придётся через msieve как посоветовал DimitarSerg

пример 0xA510CD4E648160D1, 0xE6F3725257025271

-----
...или ты работаешь хорошо, или ты работаешь много...

| Сообщение посчитали полезным:

BfoX пишет:
не хочет брать часть данных в нех-виде

мой скрипт с использованием msieve берет и эту пару

d = 0xA510CD4E648160D1
p = 0x3D05E9
q = 0x3C8DEC1AB49
e = 0xDEFCC2A24F03971

-----
127.0.0.1, sweet 127.0.0.1

| Сообщение посчитали полезным:

OKOB
спасибо, но значится питон и скрипт придётся изучать. так-то я вроде затабличил.

думал на miracl автоматизировать, но засада.

-----
...или ты работаешь хорошо, или ты работаешь много...

| Сообщение посчитали полезным:

BfoX пишет:
значится питон и скрипт придётся изучать

В личку налей данные, в личку получишь результаты.
Можешь заказать формат представления данных.

-----
127.0.0.1, sweet 127.0.0.1

| Сообщение посчитали полезным:

решено, можно закрывать тему

-----
...или ты работаешь хорошо, или ты работаешь много...

| Сообщение посчитали полезным: