Comments 43
И для однобитовых переменных операция AND тождественна математическому умножению.
Обычное умножение двух чисел представлено в виде набора логических выражений для каждого бита.
То есть если мы хотим умножить 5х7, мы представляем 5 и 7 в двоичном виде, и подставляя биты в формулы можем получить частные биты результата 35.
Я это говорю к тому, что
1)текст очень трудно понять
2) не уровень хабра
3) называть отдельные биты переменными… зачем?
Зачем?
На практике это оказалось мало осуществимым. Для второго раунда будут выражения вида (a*b), для третьего (a*b) * (c*d), для четвертого ((a*b)*(c*d)) * ((e*f)*(g*h)) (звездочка означает какую-то логическую операцию). То есть, с каждым раундом длина уравнения увеличивается вдвое. Тогда я понял, что записать результат после 64 раунда не хватит жесткого диска, и взлом md5 не состоялся)
Надо бы добавить кнопку «Сжечь» для публикаций. незачем засорять ресурс, без того сильно захламленный 1сниками с видеоуроками
Можно начать с хороших обозначений. x0 заменить на x_0, * на \cdot и т.д. (Кстати, на телефоне формулы вообще не отображаются..) Затем внятно и понятно описать, что вы делаете и зачем, кому будет интересна ваша статья. В конце стоит в простом и понятном виде предоставить результат ваших изысканий, будь он теоретическим, практическим или отрицательным. Результат должен отвечать цели, поставленной в начале статьи. Не помешала бы пара картинок вместо простыней текста под спойлерами. Стоило тщательно подумать над выбором хабов. Ненормальное программирование — хорошо, а вот в математике или криптографии обычно сидят очень требовательные люди, тогда как ваша статья не имеет к этим хабам ну вообще ничего общего.
Не помешала бы пара картинок? Я даже не знаю что на них можно было бы показать. Весь результат — это и есть эти самые простыни из формул, и подход, по которому эти простыни получаются.
К математике это относится самым прямым образом — это сложение и умножение. К криптографии это тоже относится, так как асимметричная криптография — это проблема умножения простых чисел, а так же я реализовал всё вышеописанное для вычислений md5.
Сложение и умножение это арифметика. Если относить к математике каждый пост, где используется базовая арифметика, тут будет страшная помойка. Какие новые результаты вы получили относительно "проблемы" умножения простых чисел, которые были бы применимы в теоретическом исследовании криптографии или её практическом применении? Как эта статья поможет специалистам по криптографии?
Далее, озвучен тезис о том, что некоторые члены таких выражений заведомо тождественны FALSE.
Членом я подразумеваю выражение, в котором используется только оператор конъюнкции (у меня он обозначается "*").
Так вот, если научиться без упрощения выделять такие члены среди всех остальных, то задача упрощения выражений заметно облегчится. А упрощенные выражения (в нормальной дизъюнктивной форме) и будут представлять собой возможные решения.
Я абстрагируюсь от конкретных значений, и провожу все вычисления «формульно». То есть пришлось написать машину, которая умеет работать с такими вложенными выражениями: выполнять логические операции над ними, упрощать их когда нужно, подставлять t-переменные.
Для md5 эта простыня состоит из 70 тысяч логических выражений и абсолютно не наглядна, я же не могу её сюда скопировать.
Было бы достаточно показать начало вычислений для 1-2 битов, хоть в конкретных значениях, хоть в формулах. А вы сразу результат дали.
Но тем не менее этот набор выражений даёт верный конечный результат, вычисляя к примеру md5 так же, как оригинальный алгоритм.
Это и есть оригинальный алгоритм, просто в описании он дается для байт (вернее 4-байтовых значений), а у вас то же самое разделено на биты, да еще и для каждого раунда отдельно. В общем, пока вы не придумаете, как это использовать, ценность этой информации сомнительна.
Фактически я реализовал алгоритм md5 просто в формульном виде. И получил результат в виде формулы, с которой и ставил эксперименты.
В двух словах о чём эта статья для тех, кто не до конца разобрался:
Автор ищет свои пути в криптографии. В частности, ищет методы, которые можно было бы применить для поиска коллизий md5 или других функций.
А может и для проверки гипотезы Эйлера для разных n. К сожалению, практических полезных результатов автор пока не получил.
Так что и практическая ценность статьи для общественности сомнительна. А теоретическая — тут уже у каждого своё мнение.
По поводу поиска членов, тождественно равных FALSE — это SAT, и она NP-сложна.
Согласно теореме Кука, доказанной Стивеном Куком в 1971 году, задача SAT для булевых формул, записанных в конъюнктивной нормальной форме, является NP-полной.
Требование о записи в конъюнктивной форме существенно, так как, например, задача SAT для формул, представленных в дизъюнктивной нормальной форме, тривиально решается за линейное время в зависимости от размера записи формулы
А вложенные выражения не являются ни конъюнктивной нормальной формой, ни дизъюнктивной.
И согласно моим умозаключениям, эта задача поиска false-членов для класса вложенных выражений не является ни NP, ни P, и зависит от самого выражения. Я думаю это утверждение можно легко доказать от обратного, построив два вложенных выражения, которые тождественны false, и одно из них раскладывается за полиномиальное время, другое за линейное на первой же итерации подстановки.
Хотя я всё равно не понимаю, зачем вы это делаете. Если вы открыли для себя, что комбинаторные функции можно использовать для сложения и умножения чисел, я вас поздравляю, но не стоило об этом писать на хабр. И в любом случае делать это «в столбик» глупо.
У вас там сверху написано «думаю», Подумайте ещё раз.
Вложенные логические выражения