Нужна помощь в реверсе алго. Есть выражение
v18 := 5257 * ((67108865 * v17) mod $3FFFC);
Как получить V17? Чем-то мне напомнило рса, но пока не проверял эту мысль.

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

если я понял всю логику, то в упрощенном варианте решение задачи такое:
x = A*y mod n
y = x*A^(-1) mod n
что по сути и есть rsa

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

Nightshade Формулу сегодня проверял с доказательством. Для v17 из 0..3FFFB работает
Обратное преобразование тоже верное. Лень его переписывать и ввязываться в спор : можно ли делить
на 0х1489 или обязательно обратное искать. Делить можно, а можно обратное найти. По условию там все помещается в 32 бита(и даже чуть меньше).
Промикс скорее всего расширил мою чуть дальше 0..3FFFB. Я тоже могу посмотреть, но ты так и не ответил : v17 полное слово или ?

Av0id Лень смотреть RSA, но тут необратимый алгоритм, т.к. при первом умножении сначала делают mod 2^32 , а потом mod 0x3FFFC Да и 0x3FFFC число составное. А в РСА вроде простые используют.
++++++++++++++++++
Глянул в вики. В РСА берут по модулю p*q - где p, q - простые.

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

v17 - изначально word
v18 - dword

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

Странно, что спор возник на ровном месте
Все очень просто ! Все правильно сказал Archer и Wyfinger, а Promix_17 все реализовал в правильной формуле.
Но можно еще понятнее :
Если v18 = 5257 * ((67108865 * v17) % 0x3FFFC) и v17 - word v18 - dword , то v17 = ((v18 / 5257) * 49001) % 0xCCCC

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

LazyCat Я не спорю, а говорю все погрязли в формулах и не думают.
Вот ты написал %0xСССC - отсюда следует, что v17 не может быть больше 0xCCCB
Это почему? Оно же word .
А я свою формулу проверил и в теории и на практике, прогнав на десятке образцов.
Могу и чужую теперь исправить... позжее. Вчера и так до часу не спал.

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

tundra37 пишет:
Вот ты написал %0xСССC - отсюда следует, что v17 не может быть больше 0xCCCB
Это почему? Оно же word .
Про это хорошо написал Promix_17, при значениях >0xcccb начинаются повторы (т.е. коллизии) и разные v17 дают одинаковые v18, т.е. расшифровка неоднозначна Это всегда так бывает при работе по модулю !

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

LazyCat Увы должен разочаровать. Для v17 в диапазоне 0..FFFF нет коллизий. И даже в диапазоне 0..3FFFB их очень мало - всего 0xF00 Все выкладки наверно портит начальное усечение до 32 бит, хотя на словах все вроде верно.

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

tundra37 пишет:
Увы должен разочаровать. Для v17 в диапазоне 0..FFFF нет коллизий
Ндааа... Вот уж не думал, что до этого дойдет
(67108865 * 1) % 0x3FFFC = (67108865 * 0xCCCD) % 0x3FFFC
(67108865 * 2) % 0x3FFFC = (67108865 * 0xCCCE) % 0x3FFFC
и т.д.

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

LazyCat Я про это и говорю. Вы забыли про усечение до 32 бит
(67108865 * 0xCCCD) % 0x3FFFC != ((67108865 * 0xCCCD) % 2^32) % 0x3FFFC
((67108865 * 0xCCCD) % 2^32) % 0x3FFFC = 0x100СD !!!

Я понимаю, что программу тяжко писать, но есть калькулятор - в инженерном виде он до 16 байт держит.
Ну и олли можно запустить.

Ну и раз вы так любите формулы :

0x4000001*v17=v17+0x4000000*((v17-v17%0x40)+v17%0x40)
(v17-v17%0x40) =0x40*nnn поэтому при умножении на 0x4000000 по модулю 2^32 дает 0 !!!
Поэтому получаем мою формулу
(0x4000001*v17) % 2^32 = v17+0x4000000*(v17%0x40)
Теперь мы в пределах 32 бит и можно все брать по модулю 0x3FFFC
0x4000000 % 0x3FFFC = 0x400
((0x4000001*v17) % 2^32) % 0x3FFFC = v17+0x400*(v17%0x40)

Подчеркну, что формула возможно перестанет работать только когда в V17 будут старшие биты(26 и т.д)
Но по условию v17 всего 16 бит.

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

tundra37
Вы абсолютно правы ! Я и не глянул на ассемлерный листинг, а только на формулу ТС А там действительно усечение до 32 бит. Так что Ваша формула правильная !!!

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

решил не создавать новый топик, ибо задача очень похожая. ну не учили меня в институте такой математике
имеем crypted^3 mod key=Result
работаю с большими числами, по формуле РСА, но задача найти key если известен crypted и часть Result. другими словами. Как (и возможно ли это) выполняеца операция обратная mod. Тут писали про Расширенный Алгоритм Евклида, со ссылкой на РСА, пытался вникнуть ниче не получилось

-----
Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме....

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

m - msg
c - cipher
d - prvkey
e,n - pubkey

c = m^e (mod n)
m = c^d (mod n)

result = crypted ^ 3 (mod n)
crypted = result ^ d (mon n)

n = (p-1)(q-1) - функция Эйлера
d можно найти зная p и q (которые являются простыми)

ps: расширенный алгоритм Евклида используют для нахождения НОД / GCD и обратного значения e по модулю n
d = e ^ (-1) mod n
d = 3 ^ (-1) mod n

ps. к примеру в miracl достаточно просто все это сделать
powmod(m,e,n,c) - encrypt msg
powmod(c,d,n,m) - decrypt msg
xgcd(e,n,e,e,e) - e = 1 / e mod n

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

Av0id ушел курить этот материал, спасибо, к слову
Av0id пишет:
n = (p-1)(q-1) - функция Эйлера
d можно найти зная p и q (которые являются простыми)
Не факт. ибо эти числа на практике псевдо простые. ибо тест на простоту числа в 180 знаков это задачка еще та. читал както что разные проги при генерации этих простых чисел прогоняют их тестами быстрыми на делимость гдето до 1000 причем разные проги по разному. я это про то что опираца на абсолютную простоту числа нельзя

-----
Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме....

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

простыми в смысле, делятся на себя и на 1 (P, primes)

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

VodoleY пишет:
ибо тест на простоту числа в 180 знаков это задачка еще та. читал както что разные проги при генерации этих простых чисел прогоняют их тестами быстрыми на делимость

Неправ.

На данный момень максимально найденное простое число - 45-е простое число Мерсенна,
2^243,112,609-1 , это около 13 милионов знаков.


Не так сложно уж гарантированно проверить простоту 180 значного числа, все уже придумано(и реализовано в коде) до нас:
http://en.wikipedia.org/wiki/Primality_test

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

Задача сводится к нахождению множества "баз простых чисел". "Базой простого числа"(назовите правильно - редко читаю литературу по теме...) я называю k1, для которого
m - k * 2^n = p - простое число. Любое множество "баз" однозначно отображается в
множество простых чисел с перестановками. Здесь Crypted^3 - (KnownResult + k1 * 2^k2) = a * (p - 1)(q - 1) = a * key, при этом в данном случае побитовое KnownResult & (k1 * 2^k2) = 0.
Возможно, множеств "баз" подойдёт и для этого случая. Предполагаю - для любого key множество "баз ключа" состоит из (int)sqrt(max(p, q)) элементов.
То есть, в любом случае функция определения ключа, если такая будет найдена, будет возвращать не единичный массив возможных значений, даже если полностью известен результат...

P.S. Не спрашивайте меня - это то, на чём я пока остановился 1.5 - 2 месяца назад и нет пока времени дальше продолжать...
Возможно и не верно...

-----
IZ.RU

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

VodoleY пишет:
задача найти key если известен crypted и часть Result
Странная постановка задачи Обычно то что у Вас key является просто модулем, т.е. частью ключа в системе RSA и полностью известна. В Вашем случае при частичном знании Result задача вообще неразрешима ! Напротив, если известно несколько полных пар crypted:Result, то задача просто решается алгебраическими методами.

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

LazyCat а на этом форуме вооще НЕ странных постановок мало. задачу решил. правда с другого бока. Люди, кто учился подскажите. Вроде такая аксиома есть
а^3 mod m=(a mod m)^3 mod m=((a mod m)*(a mod m)*(a mod m))mod m
если да, то как называеца это раздел.. матиматики чтоли и где можно почитать по этому поводу книжки, методички и т.д.

-----
Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме....

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

eng
rus

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

называеца это раздел.. матиматики
Дискретная математика -> Теория чисел

То что ты написал, это не аксиома, а тождественные преобразования. Типа nop = xchg eax,eax

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