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

Тема в разделе "WASM.CRYPTO", создана пользователем Indy_, 2 май 2019.

  1. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    Я тот же вопрос задал на кл https://exelab.ru/f/index.php?action=vthread&forum=6&topic=25760

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

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

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

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

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    Indy_, А, В, С какой диапазон значений принимают?
     
  3. f13nd

    f13nd Well-Known Member

    Публикаций:
    0
    Регистрация:
    22 июн 2009
    Сообщения:
    1.953
    В логических уравнениях для раскрытия скобок конъюнкция аналогична умножению, дизъюнкция сложению.
    Сложение для каждого разряда:
    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 у тебя не будет переносов для суммы разрядов старше первого неизвестного. Так что раскрыть скобки для всего числа нельзя, если пробовать сделать это для каждого разряда, то по-моему туфта получится.
     
  4. q2e74

    q2e74 Active Member

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

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    f13nd,
    > В логических уравнениях для раскрытия скобок конъюнкция аналогична умножению, дизъюнкция сложению.

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

    q2e74,

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

    Ну вот хоть намёк на какую то матчасть. Где это описано, приведите плз линк.
    --- Сообщение объединено, 2 май 2019 ---
    UbIvItS,

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

    f13nd Well-Known Member

    Публикаций:
    0
    Регистрация:
    22 июн 2009
    Сообщения:
    1.953
    Тогда наверное должен знать, что логическая операция над двумя 32битными полями это 32 логических операции. А арифметика вся на переносах.
     
  7. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    Indy_, в общем виде не решаются == нужна хотя бы система из трёх уравнений типа..

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

    q2e74 Active Member

    Публикаций:
    0
    Регистрация:
    18 окт 2018
    Сообщения:
    988
    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
     
    Последнее редактирование: 2 май 2019
    Indy_ нравится это.
  9. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    q2e74,

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

    q2e74 Active Member

    Публикаций:
    0
    Регистрация:
    18 окт 2018
    Сообщения:
    988
    Фомичев Методы дискретной математики в криптологии на стр 230 вообще употребляет слово свёртка как синоним имитовставки. А так как сейчас время, где модно "сверточные нейронные сети", слово свёртка вообще плохой ориентир.
     
  11. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    q2e74,
    Ну свёртка кода в нашей области понятие очень старое и понятное, как и обратная операция(морфинг).

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

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

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    Indy_, взлом шифров мат. методами в основном не имеет практического приложения. смотри какие возможности у тебя есть влиять на заданную систему и увидишь как быстро можно собирать данные для разрешения задачи.
     
  13. f13nd

    f13nd Well-Known Member

    Публикаций:
    0
    Регистрация:
    22 июн 2009
    Сообщения:
    1.953
    Это не взлом шифров. Это в вмпротекте адрес примитива зашифрован ксором с константой, циклическим сдвигом на константу, свопом байт и сложением с константой. И пассажир хочет заменить эти 4 действия на одно для любого значения на входе, чтобы упростить. Не смейтесь.
     
  14. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    f13nd,

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

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

    f13nd Well-Known Member

    Публикаций:
    0
    Регистрация:
    22 июн 2009
    Сообщения:
    1.953
    В контексте ты берешь значение, ксоришь, сдвигаешь, свопаешь и складываешь, я опять говорю очевидные вещи? Если у тебя есть возможность установить, что значение используется единожды или несколько раз, но везде с теми же преобразованиями, ты можешь исключить преобразования и посчитать преобразованное значение. И саму функцию выбросить можешь, если выбрасыватель может нормально анализировать и преобразовывать код не испортив его. Можешь посмотреть модель псевдокода гидры, но и она на замахивается на полный анализ, там fallthrough простенький.
     
    Последнее редактирование: 3 май 2019
  16. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    f13nd,

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

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

    Aoizora Active Member

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

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    Aoizora,

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

    Aoizora Active Member

    Публикаций:
    0
    Регистрация:
    29 янв 2017
    Сообщения:
    351
    Какое выражение? Общего случая может не быть. Есть способы минимизации булевых функций.
    Еще задача может звучать просто, а на деле закопаешься.
    --- Сообщение объединено, 5 май 2019 ---
    Мне это вообще кажется напрасной тратой времени, поскольку все эти логические операции - просто детали реализации математической идеи, а криптография работает в конечных полях и там свои формулы и теоремы. Можно героически пытаться побороть все эти вычисления на ассемблере, но не зная, что за алгоритм там реализован, это будет тяжело. Криптозащиту пишут профессиональные математики, которые проигрывают с подливой с попыток все это реверсить. Это хуже чем есть слона целиком.
     
  20. q2e74

    q2e74 Active Member

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

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