надеюсь найдутся спецы которые помогут проверить мой алго на стойкость. Задача сводится к следующему: найти все неизвестные a, b , c, d (знач.: [1-255]), при известных x5, x4, x3, x2, x1 (знач.: [0-255]). при этом должны выполнятся все условия внутри матрицы. Что-то я даже с подсчётом вариантов перебора запутался. И есть ли способ вычислить неизвестные по-быстрому без перебора ?
spa Ключ значения - Xj. 1. Я допустил что криптоаналитику стала известна часть ключа (x5,x4,x3,x2,x1). 2. Также, он хорошо ладит с отладчиком, и он установил взаимосвязь между значениями. Чтобы открыть след байт ключа - x6, он должен определить a6,b6,c6,d6. Чтобы найти их придётся решить эту матрицу. Если это удастся - ай м фэйл Sunzer O_o оказывается проблеме не один век. спс будем примерять.
SZ Какие ещё спецы? Это часто в школьный курс линейной алгебры входит. Не говоря уже о том, что в любом вузе первый семестр математики с этого начинается... если специальность хоть как-то связана с точными науками. Обычная СЛАУ. 9 уравнений, 20 неизвестных. Если хорошо присмотреться, можно заметить, что одно из уравнений линейно зависимо от других. Соответственно получаем 8 линейно независимых уравнений и 20 неизвестных, из которых 12 являются свободными. Выбираем свободными все комбинации из букв b,c,d с номерами 1,2,3 и 5 (т.е. 3*4=12 переменных). Тогда оставшиеся восемь выражаются следующим образом: b4 = b1+b2+b3+b5 c4 = c1+c2+c3+c5 d4 = d1+d2+d3+d5 a1 = x1-(b1+c1+d1) a2 = x2-(b2+c2+d2) a3 = x3-(b3+c3+d3) a5 = x5-(b5+c5+d5) a4 = x4-(b1+b2+b3+b5+c1+c2+c3+c5+d1+d2+d3+d5) На основе приведенных диапазонов возможных значений с использованием бэктрэкинга очень быстро осуществляется перебор всех возможных решений, которых может быть от нуля до ...
SZ Максимально возможное количество решений? Довольно сложная задача... для меня по крайней мере . Согласно условию максимальное количество решений достигается при x1=x2=x3=x4=x5=255. А вот сколько именно... Чисто интуитивно прикидывая, максимальное число решений находится где-то между 10^15 и 2^96.
SZ Согласно Вашему условию подойдёт любое из них. Без всяких "брутов". Если же условие неполное, и на самом деле правильное решение только одно, то никакой "брут" не поможет, т.к. нет критериев для проверки правильности решения. За исключением случая, когда x1=x2=x3=x5=4, x4=13.
Прошу прощения если я не правильно сформулировал задачу. Но что значит критерий правильности решения: выполнение условий которые обозначены знаками +, -, =. берем произвольные числа [0-255] в качестве Xj. И находим такие числа Aj, Bj, Cj, Dj [1-255] при подстановке которых все условия выполнятся. Все числа байты, но поскольку Aj, Bj, Cj, Dj могут принимать значения только в диапазоне [1-255], то 255+1 != 0 , а = 1. Ну я правда не знаю что ещё добавить )
Я ещё упростил задачу в поисках решения ) Допустим что числа (известные и неизвестные) только 0 или 1. получился вот такой дZен-кроссворд: Задача по прежнему найти все неизвестные (принимают значения 0 или 1).
SZ То и значит. Любое решение, взятое из тех — условно скажем — 10^15 решений, будет удовлетворять всем условиям Вашего квадрата. Ну вот возьмите произвольные x1,x2,x3,x4,x5, а так же произвольные b1,b2,b3,b5,c1,c2,c3,c5,d1,d2,d3,d5. Выбранные значения подставьте в решение из #5. При подстановке полученных значений все условия выполнятся. Эта подробность увеличивает число решений от "где-то между 10^15 и 2^96" до порядка 2^96. P.S. Да... с линейной зависимостью в #5 я прогнал. Т.е. свободных переменных не 12, а 11. Собственно, это мало что меняет: число правильных решений будет порядка 2^88, а не 2^96. P.P.S. Не... Таки не прогнал. Число свободных переменных всё-таки 12, и решение в #5 верное. Но! В случае, если условие x4 = x1+x2+x3+x5 для выбранных x1,x2,x3,x4,x5 не удовлетворяется, то решений нет вообще.
да, ерунда получается. явная связь между байтами ключа x1 = x2 + x3 + x4 + x5 , где все xj известны. А что если формула управляемая и между a,b,c,d (в строках) действия точно не известны (+/-).
