iwork
Удален
|
    
Здравствуйте! Вот уже долгое время мучаюсь с решением подобной системы:
================================
S(0 + K) (+) S(8 + K) = 1
S(0 + K) (+) S(4 + K) = B
S(0 + K) (+) S(2 + K) = A
S(0 + K) (+) S(1 + K) = 9
S(1 + K) (+) S(9 + K) = E
S(1 + K) (+) S(5 + K) = D
S(1 + K) (+) S(3 + K) = 7
S(2 + K) (+) S(A + K) = 2
S(2 + K) (+) S(6 + K) = 8
S(2 + K) (+) S(3 + K) = 4
S(3 + K) (+) S(B + K) = 3
S(3 + K) (+) S(7 + K) = 2
S(4 + K) (+) S(C + K) = D
S(4 + K) (+) S(6 + K) = 9
S(4 + K) (+) S(5 + K) = F
S(5 + K) (+) S(D + K) = 7
S(5 + K) (+) S(7 + K) = 8
S(6 + K) (+) S(E + K) = D
S(6 + K) (+) S(7 + K) = E
S(7 + K) (+) S(F + K) = 9
S(8 + K) (+) S(C + K) = 7
S(8 + K) (+) S(A + K) = 9
S(8 + K) (+) S(9 + K) = 6
S(9 + K) (+) S(D + K) = 4
S(9 + K) (+) S(B + K) = A
S(A + K) (+) S(E + K) = 7
S(A + K) (+) S(B + K) = 5
S(B + K) (+) S(F + K) = 8
S(C + K) (+) S(E + K) = 9
S(C + K) (+) S(D + K) = 5
S(D + K) (+) S(F + K) = 6
S(E + K) (+) S(F + K) = A
================================
, где
S(x) - обратимая функция, которая отображает множество {1,...,F} в себя (подстановка).
+ - операция сложения по модулю 16 (F)
(+) - побитовое сложение
K - неизвестный параметр
Необходимо найти K, и всю подстановку S.
В данном случае правая часть системы фиксирована, но, в принципе, может быть почти любой: число <= F, а также не может == 0.
Помогите, пожалуйста, разобраться с этим! Очень уж надо!
С уважением, Евгений.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 15 дек. 2005 3:40 | IP
|
|
Guest
Новичок
|
Во-первых, можно считать, что K=0. Дело в том, что если существует решение для ненулевого K, то его можно превратить в решение для нулевого K так S'(x) = S(x + K) (по сути K является циклическим сдвигом).
Далее, введем 64 бинарных переменных s[i,j], где i=0..15, j=0..3 и s[i,j] определена как j-й бит числа S(i). Тогда исходная система уравнений превращается в систему линейных уравнений над полем из двух элементов F={0,1}: каждому уравнению исходной системы соответствует 4 уравнения новой системы, например,
S(8) (+) S(A) = 9
превращается в
s[8,0] + s[10,0] = 1
s[8,1] + s[10,1] = 0
s[8,2] + s[10,2] = 0
s[8,3] + s[10,3] = 1
Ну а дальше работает линейная алгебра.
Можно также заменить, что переменные при разных j не могут появится в одном уравнении. Поэтому вместо одной большой системы над 64 переменными можно решать 4 меньших с фиксированным j=0,1,2,3, каждая над 16 переменными.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 15 дек. 2005 5:12 | IP
|
|
iwork
Удален
|
Хотя я уже решил эту систему, все равно спасибо!
Проблема только в том, что система имеет не одно решение! Это не есть хорошо! 
Видимо, надо искать пути нахождения точного значения одной из подстановки.
А смысл вообще такой:
Есть устройство, в котором "зашиты" число K, а также таблица подстановки S.
Устройство работает с 4х-битными числами. (1..F)
На вход подается число R.
Неизвестным (но определенным) образом вычисляется число Q, зависящее от R.
На выходе же этого устройства получается число
S(R + K) (+) Q
Q = f(R) - неизвестно
+ - сложение по модулю 16,
(+) - по модулю 2 (XOR)
Мы не имеем возможности "залезть" внутрь этого "черного ящика".
Однако у этого устройства есть переключатель, который может находится в одном из 5-ти положений: 0, 1, 2, 3, 4.
Этот переключатель инвертирует соответствующий бит числа R (0 - без инверсии, 1 - первый бит числа и т.д.)
Инверсия происходит после того, как вычислено число Q.
Т.о. на выходе получаем
S(R' + K) (+) Q
Q = f(R) - неизвестно
R' - число R с ошибкой в одном бите.
Задача: найти K и S.
Что делаю я:
Подаю на вход R, записываю результат.
Затем задействую переключатель (записываю все 4 попытки)
Получаю систему:
A = S(R + K) (+) Q
A' = S(R' + K) (+) Q
A'' = S(R'' + K) (+) Q
A''' = S(R''' + K) (+) Q
A'''' = S(R'''' + K) (+) Q
, где кол-во штрихов равно номеру бита с инверсией.
Чтобы избавиться от Q, просто XOR-ю первое уравнение поочередно с остальными и получаю
A (+) A' = S(R + K) (+) S(R' + K)
A (+) A'' = S(R + K) (+) S(R'' + K)
A (+) A''' = S(R + K) (+) S(R''' + K)
A (+) A'''' = S(R + K) (+) S(R'''' + K)
Затем беру другое R и повторяю процедуру. Получаю систему из 4*16 уравнений. Однако среди всех уравнений каждое имеет одинаковцю пару. => всего уравнений 32.
Получается система, которая определенно имеет решение (поскольку числа не произвольные, а именно посчитанные прибором).
Однако система эта имеет не одно решение...
В общем,я уже нифига не соображаю... Помогите, пожалуйста! Может есть какие-нибудь идеи?
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 15 дек. 2005 8:44 | IP
|
|
Guest
Новичок
|
От неоднозначности избавиться не удастся, и проблемы здесь теоретического, а не практического плана.
Дело в том, что если (S,f,K) является решением, то решением будет также являться (S',f,K'), где K' - любое число от 0 до 15 и
S'(x) = S(x-K'+K)
Легко проверить, что для любого Q
S'(Q+K') = S(Q+K'-K'+K) = S(Q+K)
и, значит,
S'(Q+K') (+) f(Q) = S(Q+K) (+) f(Q)
то есть черные ящики задаваемые параметрами (S,f,K) и (S',f,K') будут неразличимы извне.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 15 дек. 2005 9:11 | IP
|
|
iwork
Удален
|
Моя ошибка - не упомянул, что число Q в общем зависит не только от входного числа R, но также и от параметров системы (S, K)
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 15 дек. 2005 10:00 | IP
|
|
Guest
Новичок
|
если природа этой зависимости неизвестна, то ничего путного извлечь не удастся
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 15 дек. 2005 10:17 | IP
|
|
|
Форум
Решение системы уравнений (XOR)
