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

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

 eXeL@B —› Вопросы новичков —› знатокам RSA
. 1 . 2 . >>
Посл.ответ Сообщение

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

Создано: 11 апреля 2013 22:25 · Поправил: BfoX New!
Цитата · Личное сообщение · #1

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

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

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


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

Создано: 11 апреля 2013 22:39 · Поправил: reversecode New!
Цитата · Личное сообщение · #2

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

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

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


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

Создано: 11 апреля 2013 22:44 · Поправил: Модератор New!
Цитата · Личное сообщение · #3

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

Там обратное берётся не по N, а по Эйлеру от N.

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


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

Создано: 11 апреля 2013 22:44 New!
Цитата · Личное сообщение · #4

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

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

Создано: 11 апреля 2013 22:54 New!
Цитата · Личное сообщение · #5

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

Archer
поправил

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


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

Создано: 11 апреля 2013 22:57 · Поправил: Модератор New!
Цитата · Личное сообщение · #6

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


Ранг: 234.4 (наставник)
Статус: Участник
radical

Создано: 11 апреля 2013 23:00 · Поправил: DimitarSerg New!
Цитата · Личное сообщение · #7

Если не ошибаюсь, то решал подобную задачу с помощью математики
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
жжешь


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

Создано: 11 апреля 2013 23:00 New!
Цитата · Личное сообщение · #8

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


Ранг: 234.4 (наставник)
Статус: Участник
radical

Создано: 11 апреля 2013 23:07 · Поправил: DimitarSerg New!
Цитата · Личное сообщение · #9

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

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

BfoX пишет:
0х10CD889542920DE3, 0хFAB3B5F3C60243FD, 0хA077EF, 0х18FF3BD36D3

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


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

Создано: 11 апреля 2013 23:07 · Поправил: Модератор New!
Цитата · Личное сообщение · #10

reversecode пишет:
выбор e, вообще то строго ограничен

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

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


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

Создано: 11 апреля 2013 23:35 New!
Цитата · Личное сообщение · #11

Делал давно, некоторые числа повторяются с твоими:
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


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

Создано: 12 апреля 2013 07:32 · Поправил: BfoX New!
Цитата · Личное сообщение · #12

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


правильно

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

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

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


Ранг: 234.4 (наставник)
Статус: Участник
radical

Создано: 12 апреля 2013 09:22 · Поправил: DimitarSerg New!
Цитата · Личное сообщение · #13

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

Code:
  1. PowerMod[a, -1, m]
  2. finds the modular inverse of a modulo m.


PowerMod[9074239947405708253, -1, 16787643767110862968]

Shift+Enter, вуаля

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

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


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

Создано: 12 апреля 2013 09:37 New!
Цитата · Личное сообщение · #14

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

Это ограничение старой версии. Вот более новая , от 2004 года:
http://rghost.net/45224057

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

Создано: 12 апреля 2013 10:14 · Поправил: BfoX New!
Цитата · Личное сообщение · #15

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


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

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

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

Создано: 12 апреля 2013 10:39 New!
Цитата · Личное сообщение · #16

BfoX пишет:
вручную лопатить 128 факторизаций

Факторизацию с помощью msieve или yafu. А PowerMod на любимом языке программирования


Ранг: 234.4 (наставник)
Статус: Участник
radical

Создано: 12 апреля 2013 10:45 · Поправил: DimitarSerg New!
Цитата · Личное сообщение · #17

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

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

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

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

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

Создано: 12 апреля 2013 11:24 · Поправил: BfoX New!
Цитата · Личное сообщение · #18

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


50/50 =)

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


Ранг: 234.4 (наставник)
Статус: Участник
radical

Создано: 12 апреля 2013 11:46 · Поправил: DimitarSerg New!
Цитата · Личное сообщение · #19

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

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

Создано: 12 апреля 2013 12:20 · Поправил: Vovan666 New!
Цитата · Личное сообщение · #20

Если нужно встроить факторизатор в свой проект, то в исходниках 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

Ранг: 85.4 (постоянный)
Статус: Участник

Создано: 12 апреля 2013 12:22 New!
Цитата · Личное сообщение · #21

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

{ Атач доступен только для участников форума } - main.cpp


Ранг: 520.7 (!)
Статус: Участник
Победитель турнира 2010

Создано: 12 апреля 2013 12:45 · Поправил: OKOB New!
Цитата · Личное сообщение · #22

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

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

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

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

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


{ Атач доступен только для участников форума } - blox.rar


Ранг: 520.7 (!)
Статус: Участник
Победитель турнира 2010

Создано: 12 апреля 2013 13:02 · Поправил: OKOB New!
Цитата · Личное сообщение · #23

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

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

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

{ Атач доступен только для участников форума } - crypkey.py

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


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

Создано: 12 апреля 2013 23:25 New!
Цитата · Личное сообщение · #24

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

Ранг: 85.4 (постоянный)
Статус: Участник

Создано: 15 апреля 2013 09:10 · Поправил: drone New!
Цитата · Личное сообщение · #25

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

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

Создано: 15 апреля 2013 15:40 · Поправил: BfoX New!
Цитата · Личное сообщение · #26

drone

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

пример 0xA510CD4E648160D1, 0xE6F3725257025271


Ранг: 520.7 (!)
Статус: Участник
Победитель турнира 2010

Создано: 15 апреля 2013 17:27 New!
Цитата · Личное сообщение · #27

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


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

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

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

Создано: 15 апреля 2013 19:13 · Поправил: BfoX New!
Цитата · Личное сообщение · #28

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

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


Ранг: 520.7 (!)
Статус: Участник
Победитель турнира 2010

Создано: 15 апреля 2013 20:10 New!
Цитата · Личное сообщение · #29

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


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

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

Создано: 17 апреля 2013 00:05 New!
Цитата · Личное сообщение · #30

решено, можно закрывать тему
. 1 . 2 . >>
 eXeL@B —› Вопросы новичков —› знатокам RSA
Эта тема закрыта. Ответы больше не принимаются.

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