как получить x?

← →
я_только_учусь (2010-07-30 11:05) [0]

есть формула a := ( (x * b) mod c ) xor d;

нам известны значения a, b, с и d - как исходя из этого создать формулу что бы узнавать значения x?
например:

255 = ( (x * 104084 ) mod 128079 ) xor 48413;

также я знаю что в данном случае x будет равен 31544. но значения могут меняться и нужно вывести формулу.

сразу хочу сказать что это не лабораторная работа или что то подобное.
просто встала задача по дешифровке некого блока данных, во всем остальном разобрался, а именно на этом :(

← →
Palladin © (2010-07-30 11:16) [1]

для mod нет обратной операции

← →
Anatoly Podgoretsky © (2010-07-30 11:26) [2]

Удалено модератором

← →
Dennis I. Komarov © (2010-07-30 11:31) [3]

> я знаю что в данном случае x будет равен 31544

не только

← →
Sha © (2010-07-30 11:32) [4]

Проще всего составить таблицу значений функции,
потом инвертировать ее.

← →
я_только_учусь (2010-07-30 11:34) [5]

то есть оставить всякую надежду? x невозможно определять? :(

← →
И. Павел © (2010-07-30 11:39) [6]

Когда выполняется операция (x * b) mod c мы теряем информацию от целой части. Тоесть для разных x*b операция mod может дать одинаковый результат. Можно получить все эти варианты, а потом выбрать нужный по каким-то критериям.

← →
И. Павел © (2010-07-30 11:40) [7]

> все эти варианты

В виде формулы. А так их бесконечно много.

← →
Sha © (2010-07-30 11:41) [8]

[4] - это общий ответ.

Чтобы разобраться в твоем случае,
для начала надо знать, как объявлены переменные.

← →
Anatoly Podgoretsky © (2010-07-30 12:06) [9]

> И. Павел (30.07.2010 11:39:06) [6]

Для указаной формулы это в первом приближение 2^64 для одного С

← →
И. Павел © (2010-07-30 12:15) [10]

> Для указаной формулы это в первом приближение 2^64 для одного
> С

Может быть задача имеет физический смысл и у X есть своя ОДЗ и можно будет как-то сразу откинуть большую чась значений.

← →
я_только_учусь (2010-07-30 12:17) [11]

спасибо всем за ответы. я пришел в выводу что x это некий ключ дешифровки
переименуем x в DecKey. также я определил формулу шифрования данного блока и там присутствует некий ключ шифрования (как я понимаю), назовем его EncKey.в общем виде это теперь выглядит так:

Encrypt: (шифруется байт a)
b := ( (d xor a) * EncKey) mod c;

Decrypt:
a := ( (DecKey * b) mod c ) xor d;

осталось разобраться как можно найти валидную пару EncKey с DecKey. или возможно это модификация алгоритма шифрования RSA? как Вы считаете?

← →
И. Павел © (2010-07-30 12:24) [12]

> [11] я_только_учусь (30.07.10 12:17)

Вас что, не снабдили всеми нужными инструкциями дешифровки в центре? Тогда глотайте капсулу с цианидом.

← →
я_только_учусь (2010-07-30 12:29) [13]

> И. Павел © (30.07.10 12:24) [12]
юмор оценён, но можно ли по теме? спасибо

← →
И. Павел © (2010-07-30 12:42) [14]

Если b, c и d - константы, то можно составить таблицу - какой DecKey какому x предположительно соответствует. (т.е. [4])
А иначе - перебирайте DecKey. Этот алгоритм для этого и сделан, чтобы оказалось слишком много вариантов для расшифровки. Ну или ищите слабое место метода (если его название вам известно).

> Если b, c и d - константы

Ну т.е. я имею ввиду, что если это не предыдующие символы в коде.

← →
я_только_учусь (2010-07-30 12:58) [16]

b c d - константы. задачи из найти x, в ходе дискуссии превратилась в задачу
как найти валидную пару EncKey с DecKey.

мысль с перебором любопытная. примерный диапазон можно узнать
e = c mod (d xor a). диапазон от e*2 до e div 2.

спасибо. буду пробовать.

> И. Павел (30.07.2010 12:15:10) [10]

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

> есть формула a := ( (x * b) mod c ) xor d;

вот представьте: a=1, b=1, c=2, d=0
т.е. 1 = x mod 2;
это равенство справедливо для любого нечётного x; какое выбирать будем?

← →
я_только_учусь (2010-07-30 16:41) [19]

задача создания валидной пары EncKey DecKey решена при помощи алгоритма Евклида. всем спасибо за помощь. тему можно закрывать.

> И что генератором случайных чисел выбирать что л

дык можно тогда сразу им и воспользоваться.

как получить x? Найти похожие ветки