можно/реально ли понять логику?

как получилась строка "07383-05447-3444-960118" из четырех dword:
cR0 = 0xA2F737BD (2734110653)
cR1 = 0x4F0837CD (1325938637)
cR2 = 0x2A9E0B91 (0715000721)
cR3 = 0xD4260213 (3559260691)

Известно только, что в преобразовании могло участвовать только ROR, ROL и арифметические операции.
Знак "-" носит чисто разделительный характер, т.е. проставляется уже после преобразования.

 

Relic
Попробуй составить всевозможные выражения, содержащие указанные тобой операции.

 

crypto
Кхе.. это ж сколько вариантов-то?

 

Relic
Прилично, при этом скобки надо не забывать расставлять.
Можешь еще такой способ попробовать. Пусть M = {cR0, cR1, cR2, cR3} - твое исходное множество. Случайно выбираем из него два элемента и выполняем над ними случайную операцию, полученный результат, во-первых сравниваем с искомым числом и если не сопадает, проверяем, совпал ли результат хотя бы с одним элементом множества M. Если получился новый элемент, добавляем его к M. И так расширяем множество M до тех пор, пока не получим искомое число (дай-то бог!), либо пока компьютер не сдохнет, либо пока не надоест заниматься фигней...

 

(5^3) = 125 без скобок. Напиши програмку.

 

n0name
Это ты мало насчитал. Пусть, например, выражение имеет длину 4 (4 операции):
* OP * OP * OP * OP * (* твои операнды).
На место * можно подставить любой из операндов. В качестве OP может быть любая из 6 операций. Итого получаем
4*6*4*6*4*6*4*6*4 = 1327104.
Это без учета скобок.

А для длины N получаем 4*(24^N).

 

Ёпрст!! А может существует какое ПО, на "вход" которого можно подавать исходные данные, а на "выходе" получать всевозможные комбинации?

 

Relic

Я такого не знаю, напишешь, будет твое

Попробуй второй способ, даже интересно, что получится.

 

Если 07383054473444960118 - число в десятичной системе, то можно предположить, что вычисления происходят в 64-битной арифметике. Если дополнительно предположить, что ROR и ROL применяются только к 32-битным числам и из арифметических действий используется только сложение, то получается всего 32^4 = 2^20 возможностей. Если какое-то из этих допущений нарушается, то выражений будет.. хм.. очень много ) Понятно, что результатов не может быть больше чем 2^64, но можно ли автоматизировать их перебор - не знаю.

 

crypto

Это какой именно?
Кстати, если будет известна вторая пара - "вход" и "выход" - можно как-то облегчить реверсинг алгоритма преобразования?

 

Stiver
Скорее всего из арифметических операций действительно используются только + и -. Результатов, понятно, не может быть больше, чем 2^64, но алгоритмов их получения из данных может быть очень много.
Relic

Мой второй ответ.
А насчет количества известных пар - теоретически да, чем больше, тем лучше, но как это использовать на практике (кроме как при отсеивании вариантов) х.з.

 

Насчет 2^20 наврал конечно, их значительно больше. В общем пытаться перебрать все выражения - дело дохлое, надеяться можно только на большую удачу.

 

crypto
6^3. Я насчитал 5 операций вместо 6ти =)
6 типов операций. 3 операции между 4 числами(в лучшем случае =)). 3 цикла от 0 до 5, и будут перебраны все варианты операций.

 

n0name
Все равно не понимаю, почему так мало. А как насчет таких комбинаций:
(((cR0 ROR k1) + (cR1 ROL k2)) ROL k3) + ((cR2 ROL k4) + (cR3 ROR k5)) + ... и так далее.
При этом могут меняться операнды cR*, значения сдвигов и т.д.

 

crypto
Хе если со скобками и для ROL/ROR вносятся отдельные коэффициенты то конечно вариантов гораздо больше.
Но и у тебя не учитываются k1,k2,.... С ними всё гораздо сложнее.

 

n0name
Не учитываются, согласен, но мы же принципиальный вопрос решаем - много вариантов или нет. А точной комбинаторикой заниматься нет пока желания, главное оценить размеры задачи.
Если грубо оценивать, получается следующее:
вариантов для примитива P типа (cRX ROR(L) k) - 4*2*32=256
каждый примитив может служить для создания нового примитива вида (P ROR(L) k), число возможностей уже 256*2*32=16384
либо примитива вида P1 + P2, тут вариантов 256*256 = 65536
Сколько из них совпадет с уже имеющимися - вопрос для исследования, но уже на второй итерации мы получили почти 80 тыс. вариантов. Дальше число будет возрастать экспоненциально.

Если все операции выполняются в 64 битах, да еще используется операция *, то кол-во вариантов будет еще больше.

 

Relic
Хотелось бы уточнить постановку задачи в плане используемых операций. Есть точная информация или догадки?

 

crypto

К сожалению, только догадки, основывающиеся на том, что иные операции (SHR, XOR и пр.) в этой проге при формировании как ключа, так и ID КПК не используются... В понедельник попытаюсь поглубже проанализировать код проги, может что прояснится...

 

Relic
Издеваешься, да? У самого прога перед глазами, код только надо уточнить, а мы тут догадками занимаемся! Нехорошо!

 

crypto
Тебе бы лишь бы продизасмить =)
А на глазок слабо?