учитывая алгоритм хеш-функции, как преобразовать его в схему?
Самое главное, мы сначала хотим лучше сформулировать проблему
- Какая хэш-функция?
- Нужна ли нам схема для полной хеш-функции и ввода фиксированной длины [что, кажется, лучше всего соответствует вопросу], или для некоторой части хеш-функции [например, раунд хеш-функции с вводом одного дополненного блока сообщений в связанный материал, если я правильно прочитал]?
- Зачем нам «схема»? Это повлияет на характер того, что мы производим.
- Доказательство с нулевым разглашением с использованием хэша, как в связанном примере? Это приведет к выражению в виде длинной цепи ворот, ограниченных некоторыми разновидностями (здесь исключающее ИЛИ, И, и ИНВ)
- Проверка того, как чистый SAT-решатель обрабатывает решение некоторых проблем, связанных с хешем (например, прообразом)? Выражение, как правило, будет еще более ограниченным (без XOR), с другой стороны, отрицание обычно бесплатно.
- Оптимизированная реализация в кремнии или FPGA? Как правило, слишком глубокая чистота Логическое выражение будет бесполезным, нам потребуются промежуточные защелки, и если все это не будет глубоко конвейеризировано или хэш будет ужасно нерегулярным, у нас будет некоторая логика, повторно используемая в раундах. Я не буду это освещать.
- В какой форме мы хотим получить результат? Для чисто булевой схемы большинство форматов будут нумеровать переменные. Я думаю, пример имеет 512 входов, пронумерованных от 0 до 511, 116246 вентилей (по одному на строку), каждый из которых производит одну новую переменную, всего 116758 переменных, и 256 выходов (это могут быть переменные от 116502 до 116757, я не уверен), с этим описанным в первых двух строках по некоторому простому соглашению. Ниже приведены одни ворота на строку, я думаю, для каждого
- количество входов [1 для НЕ и 2 для остальных в примере]
- количество выходов [1 в примере]
- список входных данных
- список [одного] выхода(ов)
- имя ворот [XOR, AND, INV в примере]
Остальное в целом следует технике пещерного человека, чтобы съесть мамонта (по одному куску за раз) и прогрессу оттуда (инструменты).
Мы выполняем алгоритм шаг за шагом, разворачивая каждый цикл и выражая каждый шаг в виде булевых уравнений. Например, если все переменные 32-битные (как в SHA-256):
- заявление вроде
С = А ^ В может быть преобразовано в 32 новые переменные для C, выводимые 32 вентилями XOR, что требует 32 строк. Нам нужно следить за номерами, обозначающими новые переменные, присвоенные С.
Э = С + Д требует промежуточных переменных, поэтому больше строк. Нам нужно 30 полные сумматоры, а затем два упрощенных (без переноса для старшего бита, который, таким образом, сводится к одному XOR; без переноса для первого, который, таким образом, сводится к одному XOR и одному AND).F = (Е<<3)|(Е>>29) не потребует строки, только переназначение переменных для Е.
Есть несколько приемов, с помощью которых иногда можно получить более простые выражения, но для хэшей, представляющих криптографический интерес, выражение останется длинным. Если бы это было не так, хеш был бы слабым.
Достаточно легко создать программу, которая делает это с нуля, и по моему опыту это проще, чем найти и освоить что-то адекватное. Существующие инструменты могут быть полезны для автоматического упрощения выражений, но для большинства криптографических хэшей небольшой анализ уравнений хеш-функций позволит добиться максимального упрощения и может дать лучшие результаты, чем автоматизированные инструменты.
