Свёртка булевых функций.

Я тот же вопрос задал на кл https://exelab.ru/f/index.php?action=vthread&forum=6&topic=25760

Есть некоторая функция, не аналоговая", те булевые операции вперемешку с обычной математикой.

Как решать что то на подобие (A xor B) + C ?

Как понимаю нужна некоторая теория и теоремы, как это делается ?

Это нужно что бы свернуть морф/вм код.

 

Indy_, А, В, С какой диапазон значений принимают?

 

В логических уравнениях для раскрытия скобок конъюнкция аналогична умножению, дизъюнкция сложению.
Сложение для каждого разряда:
z(n)=x(n)^y(n)^o(n-1) ;строгая дизъюнкция 2 разрядов и переноса
o(n)=(x(n)&y(n))|(x(n)&o(n-1))|(y(n)&o(n-1)) ;если хотя бы 2 из трех участвующих разрядов равны 1, то перенос 1.
(A^B)+C бесполезно решать в комплексе, не зная каждого разряда в A^B у тебя не будет переносов для суммы разрядов старше первого неизвестного. Так что раскрыть скобки для всего числа нельзя, если пробовать сделать это для каждого разряда, то по-моему туфта получится.

 

Indy_,
1) А В С - слова определенного размера? Если бы был еще сдвиг на простое число, выглядело бы как один раунд RC5. В криптографии есть поверье, что операции из разных алгебр увеличивают нелинейность и больше шансов, то они не сводимы к более простому случаю.
2) A B C - функции. Тогда от скольки переменных? булева функция это полоска из нулей и единиц.
3) что есть свертка? Есть разные контексты в которых смысл этого слова плавает. Ближе всего свёртка последовательностей, но тогда не подходит. Свёртка является линейным преобразованием входящих в неё последовательностей, а операция + (с переносом разряда) хоть и слабо, но нелинейна. А может быть, это похоже на residual block. Есть контексты в которых "свёртка" не разворачивается, сжимается с потерей инфы, если свернуть морф код, что будет выполняться? Если бы это были слова одной длинны, выглядело бы как раунд в сети фейстиля и инфа(байты) бы однозначно востанавливалась.

 

f13nd,
> В логических уравнениях для раскрытия скобок конъюнкция аналогична умножению, дизъюнкция сложению.

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

q2e74,

> В криптографии есть поверье, что операции из разных алгебр увеличивают нелинейность и больше шансов, то они не сводимы к более простому случаю.
> Свёртка является линейным преобразованием входящих в неё последовательностей, а операция + (с переносом разряда) хоть и слабо, но нелинейна.

Ну вот хоть намёк на какую то матчасть. Где это описано, приведите плз линк.

--- Сообщение объединено, 2 май 2019 ---

UbIvItS,

А кто же наперёд знает, у нас есть код, но он не исполнился и значений нет.

 

Тогда наверное должен знать, что логическая операция над двумя 32битными полями это 32 логических операции. А арифметика вся на переносах.

 

Indy_, в общем виде не решаются == нужна хотя бы система из трёх уравнений типа..

(А ксор В) + С = м
А + В = д
А + С = т
======
но если ты решишь такую систему.. хех, дажЪ слов нет

 

Indy_, книга булевы функции в теории кодирования и криптологии (Логачев Сальников Ященко) $2.4 (у меня в бумажном виде это 97 стр)

у меня скачалась отсюда джвю
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=2ahUKEwiT1uPht_3hAhURs4sKHYbgB5gQFjABegQIAxAB&url=https://epdf.tips/-2f8710f2c5fee43228855708362714d314384.html&usg=AOvVaw2oiA7xtrhMxPK_mlqeyZML

есть еще источник, может он будет ближе и понятнее. Книга Алгоритмы построение и анализ (Кормен Лейзерсон Ривест(тот самый что сделал RC5)) Про свертку одна страница 716 подраздел 32.1

 

q2e74,

Вот хоть какая то матчать, утверждают что ничего такого нет. Спасибо!

 

Фомичев Методы дискретной математики в криптологии на стр 230 вообще употребляет слово свёртка как синоним имитовставки. А так как сейчас время, где модно "сверточные нейронные сети", слово свёртка вообще плохой ориентир.

 

q2e74,
Ну свёртка кода в нашей области понятие очень старое и понятное, как и обратная операция(морфинг).

А есчо есть такой нюанс что я не математик, те ваш док открыл, но мне эти формулы мало о чём говорят.

В любом случае хоть какая то основа, спс.

 

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

 

Это не взлом шифров. Это в вмпротекте адрес примитива зашифрован ксором с константой, циклическим сдвигом на константу, свопом байт и сложением с константой. И пассажир хочет заменить эти 4 действия на одно для любого значения на входе, чтобы упростить. Не смейтесь.

 

f13nd,

Я не говорил что для любого значения. А если выражение не именно это, а произвольное можно свернуть.. нужно определить что вообще свёртка возможна. Как это сделать ?

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

 

В контексте ты берешь значение, ксоришь, сдвигаешь, свопаешь и складываешь, я опять говорю очевидные вещи? Если у тебя есть возможность установить, что значение используется единожды или несколько раз, но везде с теми же преобразованиями, ты можешь исключить преобразования и посчитать преобразованное значение. И саму функцию выбросить можешь, если выбрасыватель может нормально анализировать и преобразовывать код не испортив его. Можешь посмотреть модель псевдокода гидры, но и она на замахивается на полный анализ, там fallthrough простенький.

 

f13nd,

> Если у тебя есть возможность установить, что значение используется единожды или несколько раз, но везде с теми же преобразованиями, ты можешь исключить преобразования и посчитать преобразованное значение.

Как бы я это сам понял, зачем за мной повторять.

 

Говна кусок для макак. Криптография это прежде всего алгебра и алгебраическая геометрия. Даже криптоанализ блочных шифров выполняется при помощи базисов Грёбнера, потому что требуется решать системы полиномиальных уравнений над конечным полем. Когда я еще учился в универе, у нас старшая исследовательская группа таким образом ломанула шифрование Нокии и двух человек потом позвали в нокию работать. Можно гуглить инфу по словам типа Groebner bases AES.
Будущее криптографии это вещи типа системы McEliece и криптографии на решетках (NTRUCrypt), а не булевы функции

 

Aoizora,

Как можно узнать что выражение не может быть упрощено/обратимо, те не решаемо ?

 

Какое выражение? Общего случая может не быть. Есть способы минимизации булевых функций.
Еще задача может звучать просто, а на деле закопаешься.

--- Сообщение объединено, 5 май 2019 ---

Мне это вообще кажется напрасной тратой времени, поскольку все эти логические операции - просто детали реализации математической идеи, а криптография работает в конечных полях и там свои формулы и теоремы. Можно героически пытаться побороть все эти вычисления на ассемблере, но не зная, что за алгоритм там реализован, это будет тяжело. Криптозащиту пишут профессиональные математики, которые проигрывают с подливой с попыток все это реверсить. Это хуже чем есть слона целиком.

 

ну что за дичь. алгебраическая геометрия это коммутативная алгебра, это как раз для шифров плохо, а вот для кодов очень хорошо. булевые функции, или описание через полиномы, или описание алгебры через множество и табличное соответсвие - это всё формы представления. Как описание алгоритма решения прикладной задачи через разные языки программирования. Для каких-то вещей удобно что-то, для каких-то нет.

что такое булевая функция? например, 2e74 - это 2=0010 e=1110 7=0111 4=0100 итого 0010111001110100 . 16 нулей и единиц 16 = 2^4. Можно задать таблицу соответсвия:
0000 0
0001 0
0010 1
0011 0
это было "2" в 2e74. Это просто форма представления. Конкретно эта функция самодвойственная, т.е. симметричная относительно центра, а значит прекрасно сжимается. А можно искать полиномы что бы получить выходной бит от четырех булевых переменных, что бы описать этот мат.объект. Но в некоторых задачах это не нужно. А если у вас есть алгебраическая структура, то это слабость алгоритма шифрования, но сила алгоритма помехоустойчивого кодирования. И если ваш шифр оказался близок к коду, то с какой-то вероятностью вы можете опираться на предсказания отталкиваясь от результатов кода, но неизбежно где-то будете лажать. Но впринципе, это уже взлом алгоритма шифрования. Поэтому и ищут через уравнения, но в идеальном случае должна быть такая вакханалия, которую описывать через уравнения будет во много раз длиннее чем просто описать каждый случай отдельно.