Можете ли вы получить исходное десятичное число из младших значащих бит другой операции?

Question

Выполняю операцию, когда функция F(k,x) принимает два 64-битных значения и возвращает произведение их десятичных чисел. Например:

F(123,231) = 123 x 231 = 28413 

Затем число преобразуется в двоичный код и извлекаются младшие значащие биты. т.е. если 28413 = 0110111011111101, то мы принимаем 11111101, что равно 253 в десятичной системе.

Эта функция является частью сети Feistel в безопасности. При выполнении типа атаки (выбранного открытого текста) мы добираемся до точки, где у нас есть 253 и 231, но нужно выяснить, 123.

Есть ли способ, который возможен?

Answer 1

Номер

При сбрасывании наиболее значимых бит, операция оказывается моно-направленной. Чтобы восстановить 123, вы должны были бы принудительно использовать функцию с любой возможностью до тех пор, пока результат не достигнет необходимого значения.

I.e. запустите F (x, 231) для значений x до тех пор, пока результат F не станет 253.

Таким образом, зная, что один из двух входов и выход делают относительно легким переборку. Это будет зависеть от количества допустимых значений для x (например, всегда ли это трехзначное число? Всегда простое? Всегда нечетное?)

Возможно, есть несколько других ярлыков, в зависимости от шаблонов, которые умножают число 231 вы, но любое заданное значение для этого числа будет иметь разные шаблоны. например если это было 9 вместо 231, вы бы знали, что сумма цифр всегда суммируется до 9.

Answer 2

Ваша функция выполняет F(k,x) = k*x mod 256.

Ваш вопрос указан F(k,x) и x, вы можете найти k?

Когда x является нечетным, существует 2^56 решений, каждый из которых имеет k = x^-1 * F(k,x) mod 256. То есть вы вычисляете обратное значение x mod 256, и каждое возможное решение получается путем добавления кратного 256 к произведению F(k,x) с этим значением.

Если даже x нет, вы не можете вычислить инверсию, но вы все равно можете определить решения, используя подобный трюк. Вам нужно сначала вычислить количество двух (2), которые делят x, скажем, это t двое, а затем разделить 2^t с x и 256, а затем решить проблему. т.е. k = (x/2^t)^-1 * F(k,x) mod (256/2^t).

В целом использование умножений в схемах шифрования опасно, особенно из-за выбранных атак из открытого текста, поскольку злоумышленник может заставить вещи исчезнуть, чтобы упростить свою атаку. Вы можете найти примеры взлома таких шифров, как on my blog (см. Атаки хаотической хэш-функции и многократные).