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