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

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

Nightshade пишет:
Чем-то мне напомнило рса, но пока не проверял эту мысль.
у РСА возведение в степень экспоненты а не умножение

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

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

Да уже посмотрел.
пока понял такую вещь $3FFFC =262140
67108865/262140 = 256
Делится нацело значит остатка не даст.
И
262140/ 5257 =49 - тоже нацело

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

v18 := 5257 * ( v17) не?
изначально эта формула подразумевает ща счет МОД множественные решения

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

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

Похоже на то.
v17 - word. Значит меньше $3FFFC
Отсюда v17 mod $3FFFC =v17
Нет не получается
v17 = $7802
($7802*67108865 ) mod $3FFFC = $8002

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

Во-первых, 67108865 делится на 262140 вполне себе с остатком.
Во-вторых, полагаю, что текущая форма записи не полная, ибо как минимум умножение тоже происходит по модулю.
В-третьих, расширенный алгоритм Евклида вполне должен это решать.

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

Ненавижу флудерастов вроде промикса.
Вообщем
(x * 67108865)mod $3FFFC =y
x=y-$800
такая бодяга получается. Видно мы что-то не проходили про mod...
Мля меня похакал виндозный калькулятор-он не показывает остаток в программерском виде

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

Вроде как: v17=((v18/(5257*5))*35293 mod 0x3FFFC)

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

v18 := 5257 * ((67108865 * v17) mod $3FFFC);
v17= 30722 v18 = 172271890
((172271890/5257) * 35293 mod $3fffc) /5 = 50414
v17 - word v18 -dword

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

Ясен пень, что в 32 бита обратная формула не влезет! Считать, правильно научились бы, а потом уже претензии предъявляли бы!

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

Ну покажи как в 32 битах это посчитать

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

А, вообще, однозначного решения данного уравнения не существует - есть целых 5 решений в кольце 0x3FFFC по известному v18:

v17=(((v18/(5257*5))*35293) mod 0x3FFFC)+(k*0x3FFFC/5) mod 0x3FFFC,где k=0,1,2,3,4

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

Я правильно понял.
Упрощаем выражение.
v18 = 5257 * ((67108865 * v17) % 0x3FFFC)
v18 = 5257 * ((67108865 % 0x3FFFC)* (v17 % 0x3FFFC))
v18 = 5388425 * (v17 % 0x3FFFC)

Отсюда, вариант решения
v17 = (v18 / 5388425) +0x3FFFC
или
v17 = ((v18 / 5388425) +0x3FFFC) % 0x3FFFC

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

Не получается по этим формулам найти

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

A так?

V17:= (v18*$3FFFC)/(5257*67108865)

-----
Чтобы правильно задать вопрос, нужно знать большую часть ответа. Р.Шекли.

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

V17:= (v18*$3FFFC)/(5257*67108865) - по этой формуле всегда 0
Все должно влезать в 32 бита

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

У вас умножение происходит в кольце. В кольце нет операции деления, есть понятие обратного элемента и умножения на него. И ищется он через РАЕ, про который я выше написал. Забудьте про деление.

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

А можно тоже самое только простым языком?

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

Никакой формулы-решения не может быть, это алгоритм.
Обратите внимание. Ваша задача - решение сравнений (67108865 * v17) mod $3FFFC
Кроме этого заметьте, что 67108865 > $3FFFC, поэтому сократим 67108865 до 1025 (1025 = 67108865 mod $3FFFC).
Задача - найти x в выражении (1025 * x) mod $3FFFC
О решении задачи можно почитать в разделе Решение сравнений на Википедии.

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

Это функция из шифровки траффика клиент-сервер. Поскольку сервер это расшифровывает -формула решение есть

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

если честно, то похоже на elgamal, а именно подпись

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

(x*4000000 +x) mod (40000-4)=y
нельзя это разложить как-то красиво? Может компилятор оптимизировал операции?
Заметил что последний байт х и у всегда одиннаковый.
изначально х из 2 байт
call _rand_0
movzx eax, ax
mov [ebp+var_14], eax

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

Вы точно прочитали статью на Википедии?

Я, конечно, не спец в криптографии и математике, но, насколько я понимаю уравнение
a*x mod b = с
нельзя решить простым выражением.

Нужно взять НОД(с, a) пусть он равен d
поделить a, b, c на d (a1=a/d, b1=b/d, c1=c/d)
получим уравнение
a1*x mod b1 = c

Далее нужно найти обратное a1 по модулю b1 (сделать это можно теоремы Эйлера, алгоритма Евклида, в помощь), пусть это будет g.

Теперь решение находится умножением полученного уравнение на g.

Это мой неграмотный перевод указанного выше раздела из статьи на википедии.

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

Прочитал, но нифига не понял.
теоремы Эйлера, алгоритма Евклида и сферический конь для меня одиннаковые понятия

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

Поскольку сервер это расшифровывает -формула решение есть
Заморочил ты всем голову. Нет решения для той функции, для которой ты привел код.
Поделив на 1489 получим остаток, который должен получится из 32-битного слова при делении на 0x3FFFC
Очевидно, что получаем неоднозначное соответствие. Но это я потом сообразил. Сначала пытался получить формулу . Поняв, что не получится, вбил команды в Олли и стал гонять.
А формула для остатка ПРОСТАЯ!!! Для диапазона v17=0-0x3FFFB такая : (v17%0x40)*0x400+v17
Если обозначить остаток через О, то v17=O-(O%0x40)*0x400 Надо только учесть, что O не попадает в диапазоны 1-3FF и некоторые другие. Для больших чисел можно легко посчитать коллизию.
50E221 и A271 -> остаток 16671 и т.д.
Вот так!!! Надо будет прогнать все числа и посмотреть точнее, что там получается.

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

Archer совершенно прав, необходимо найти обратное по модулю число.
Так как используется только 32 бита, то имеем выражение
X = (67108865 * v17) % 2**32
Надо найти число обратное по модулю (Modular multiplicative inverse) константе 67108865
A = 67108865 % 2**32
A * A**(-1) = (67108865 * A**(-1)) % 2**32
1 = (67108865 * A**(-1)) % 2**32
Используем расширенный алгоритм Евклида (а можно через сайт wolfram.com) найдем его:
A**(-1) = 4227858433
Проверка - (4227858433 * 67108865) % 2*32 = 1

Теперь
кодируем так X = (67108865 * v17) % 2**32
а раскодируем так v17 = (4227858433 * X) % 2**32

Что такое должно получиться
кодируем v18 := 5257 * (((67108865 * v17) % 2**32) % 0x3FFFC);
раскодируем v18 = v18/5257
v17 = (((4227858433 * v18) % 2**32) % 0x3FFFC)
Например
v17 = ['H','E','L','L','O']
кодируем v18 = ['0296E688', '01A03CED', '03DFC8AC', '03DFC8AC', '04D67247']
раскодируем v17= ['00000048', '00000045', '0000004C', '0000004C', '0000004F']

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

Fedonin Это все здорово. Но для байтов по моей формуле быстрее и проще.
Только вряд ли там каждый байт кодируется 4-мя. Ну правда можно кодировать 2 байта и даже почти 18 бит, только ТС не сказал про разрядность. Говорил только про 32 бита. А где?

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

Я не понимаю, чем вам моя формула не нравится? А именно v17=(((v18/(5257*5))*35293) mod 0x3FFFC)+(k*0x3FFFC/5) mod 0x3FFFC, где k=0,1,2,3,4. Если кодируются небольшие числа (символы), то берём k=0. Если хотите, сейчас напишу решение.

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

Пусть х=v18/5257, y=v17. Получается:
x=67108865*y mod $3FFFC
x=1025*y mod 262140
Т.к. НОД(1025,262140)=5, то обратного элемента к 1025 по модулю 262140 не существует
=> данное сравнение имеет решения тогда и только тогда, когда х делится на НОД(1025,262140)=5
Количество решений по модулю 262140 равно 5.Тогда,
x=1025*y mod 262140 =>
х/5=205*y mod 52428
Обратный элемент к 205 по модулю 52428 равен 35293, тогда
35293*x/5=35293*205*y mod 52428
y=35293*x/5 mod 52428 - частное решение
v17=(((v18/(5257*5))*35293) mod 52428)+(k*52428) mod 0x3FFFC, где k=0,1,2,3,4 - общее решение

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

Promix_17 Твоя формула не дает нужный результат.
Формула Тундры на 2 тестовых значениях выдала нужный результат. Не знаю насколько она правильна, но факт остается таким. Формулу Fedonin не пробовал. tundra37 спасибо. Если будут еще умные мысли - пишите. Пока топ закрывать не буду, поскольку плохо знаю вышку и мало ли в формуле есть ошибка.

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