28.01.2017 09:42
pokamest_nikak 43 6100 Источник
Привет. В этой статье я расскажу, как можно очень сильно заморочиться. Как несколько мыслей могут захватить голову на годы, и даже повлиять на жизнь. Я расскажу, как складывать и умножать числа, как вычислить md5, а может и искать числа из гипотезы Эйлера.

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

Глава 1. Сложение


Итак, поехали. Начнем со сложения. Числа мы представляем в виде последовательности битов

$inline${a0,a1,a2,a3…} , $inline$
$inline${b0,b1,b2,b3…}, $inline$
$inline${x0,x1,x2,x3…}, $inline$
где $inline$a0, b0$inline$ — младшие биты.

Под переменной $inline$x$inline$ я подразумеваю результат операций.

Давайте же попробуем сложить эти числа. Чему будет равен нулевой бит суммы? Если биты $inline$a0$inline$ и $inline$ b0$inline$ равны, то $inline$x0$inline$ будет равен нулю, и 1 в противном случае, то есть $inline$x0 = a0\ XOR\ b0$inline$. Далее логические операторы будут записываться проще для экономии драгоценного пространства интернета так: $inline$AND \equiv $inline$*, $inline$OR \equiv $inline$+.

Теперь первый бит. Он будет зависеть от нулевого бита, если оба нулевых бита равны единице, то будет добавляться бит к первому. Назовём эту компоненту бит переноса. Итого, мы имеем три компонента, влияющих на первый бит. Это $inline$a1, b1$inline$ и $inline$(a0 * b0)$inline$.

Первый бит будет равен единице если один из этих компонентов равен единице, или все три. Это записывается так:

$inline$a1*b1*(a0 * b0) + !a1*b1*(a0 * b0) + a1*!b1*(a0 * b0) + a1*b1*!(a0 * b0)$inline$.

Ужас. Я даже не уверен что я это правильно сейчас записал.

Я ввел для удобства тернарную операцию $inline$XOR3$inline$ — она дает единицу, когда нечетное количество аргументов равно единице.

Далее, второй бит. С ним всё то же самое — он зависит от трех компонентов: $inline$a2,b2$inline$, и бита переноса из первого бита. Теперь бит переноса первого бита зависит от трех компонент: $inline$a1, b1$inline$, и предыдущего бита переноса. Если два из трех этих компонент будут равны единице, то бит переноса тоже будет равен единице. Эта тернарная функция у меня называется $inline$AND3$inline$: она дает единицу если два из трех битов равны единице. Формула попроще: $inline$AND3(a,b,c) = (a*b) + (a*c) + (b*c).$inline$

Ну а следующие биты будут определяться так же как и второй бит. В цикле это выглядит так: считаем бит переноса $inline$p(i-1)$inline$, и считаем бит результата $inline$x(i)$inline$

$inline$p2=AND3(a2,b2,p1)$inline$
$inline$x3=XOR3(a3, b3, p2)$inline$
$inline$p3=AND3(a3,b3,p2)$inline$
…

Вот, мы научились складывать числа.

Вот как выглядит сумма 5-битных чисел
------------BIT 0-----------------
!a0*b0 OR
a0*!b0

------------BIT 1-----------------
a0*a1*b0*b1 OR
!a1*!b0*b1 OR
!a0*!a1*b1 OR
a0*!a1*b0*!b1 OR
a1*!b0*!b1 OR
!a0*a1*!b1

------------BIT 2-----------------
a0*a2*b0*b1*b2 OR
!a1*a2*!b0*!b2 OR
!a0*!a1*!a2*b2 OR
!a2*!b0*!b1*b2 OR
!a0*!a2*!b1*b2 OR
!a0*!a1*a2*!b2 OR
a0*a1*a2*b0*b2 OR
a1*a2*b1*b2 OR
a2*!b0*!b1*!b2 OR
!a0*a2*!b1*!b2 OR
a0*a1*!a2*b0*!b2 OR
!a1*!a2*!b1*b2 OR
!a1*!a2*!b0*b2 OR
!a1*a2*!b1*!b2 OR
a0*!a2*b0*b1*!b2 OR
a1*!a2*b1*!b2

------------BIT 3-----------------
a2*a3*b2*b3 OR
a2*!a3*b2*!b3 OR
a3*!b0*!b1*!b2*!b3 OR
!a1*!a2*!a3*!b0*b3 OR
a0*a1*a2*!a3*b0*!b3 OR
!a3*!b0*!b1*!b2*b3 OR
!a0*!a2*!a3*!b1*b3 OR
a1*a3*b1*b2*b3 OR
a0*a2*a3*b0*b1*b3 OR
!a0*!a1*!a3*!b2*b3 OR
!a0*!a3*!b1*!b2*b3 OR
!a0*!a1*a3*!b2*!b3 OR
!a2*!a3*!b0*!b1*b3 OR
a0*a1*a3*b0*b2*b3 OR
a0*a1*a2*a3*b0*b3 OR
a0*a2*!a3*b0*b1*!b3 OR
!a1*!a3*!b1*!b2*b3 OR
!a0*a3*!b1*!b2*!b3 OR
!a2*a3*!b0*!b1*!b3 OR
!a2*!a3*!b2*b3 OR
!a1*a3*!b0*!b2*!b3 OR
a0*!a3*b0*b1*b2*!b3 OR
!a0*!a1*!a2*a3*!b3 OR
!a0*!a2*a3*!b1*!b3 OR
!a1*!a2*!a3*!b1*b3 OR
!a0*!a1*!a2*!a3*b3 OR
!a2*a3*!b2*!b3 OR
a0*a1*!a3*b0*b2*!b3 OR
a1*!a3*b1*b2*!b3 OR
a1*a2*!a3*b1*!b3 OR
a0*a3*b0*b1*b2*b3 OR
!a1*!a2*a3*!b0*!b3 OR
!a1*!a3*!b0*!b2*b3 OR
!a1*a3*!b1*!b2*!b3 OR
a1*a2*a3*b1*b3 OR
!a1*!a2*a3*!b1*!b3

------------BIT 4-----------------
!a0*!a2*!a3*a4*!b1*!b4 OR
!a0*!a3*a4*!b1*!b2*!b4 OR
a3*!a4*b3*!b4 OR
a3*a4*b3*b4 OR
!a0*!a1*!a3*a4*!b2*!b4 OR
a0*a2*!a4*b0*b1*b3*!b4 OR
!a2*!a3*!a4*!b2*b4 OR
a4*!b0*!b1*!b2*!b3*!b4 OR
a0*a1*a2*a3*a4*b0*b4 OR
!a2*!a4*!b2*!b3*b4 OR
!a1*!a2*!a4*!b1*!b3*b4 OR
!a1*a4*!b1*!b2*!b3*!b4 OR
!a1*!a3*!a4*!b0*!b2*b4 OR
a0*a1*a2*a3*!a4*b0*!b4 OR
!a1*!a2*!a3*!a4*!b0*b4 OR
a1*a3*a4*b1*b2*b4 OR
a2*a4*b2*b3*b4 OR
a0*!a4*b0*b1*b2*b3*!b4 OR
!a2*a4*!b0*!b1*!b3*!b4 OR
a0*a4*b0*b1*b2*b3*b4 OR
!a0*!a1*!a3*!a4*!b2*b4 OR
a0*a1*a3*!a4*b0*b2*!b4 OR
a1*a2*a3*a4*b1*b4 OR
a1*a2*!a4*b1*b3*!b4 OR
a0*a2*a3*a4*b0*b1*b4 OR
a2*!a4*b2*b3*!b4 OR
a0*a1*a2*!a4*b0*b3*!b4 OR
!a0*!a4*!b1*!b2*!b3*b4 OR
!a1*!a2*!a3*a4*!b0*!b4 OR
!a0*!a1*a4*!b2*!b3*!b4 OR
!a0*!a1*!a2*!a3*a4*!b4 OR
a0*a1*!a4*b0*b2*b3*!b4 OR
a1*a2*a3*!a4*b1*!b4 OR
a1*a2*a4*b1*b3*b4 OR
!a1*!a2*!a3*!a4*!b1*b4 OR
!a4*!b0*!b1*!b2*!b3*b4 OR
a1*a3*!a4*b1*b2*!b4 OR
a0*a1*a3*a4*b0*b2*b4 OR
!a2*!a3*!a4*!b0*!b1*b4 OR
!a1*!a2*a4*!b0*!b3*!b4 OR
!a0*!a1*!a2*!a4*!b3*b4 OR
!a0*!a1*!a2*a4*!b3*!b4 OR
a2*a3*a4*b2*b4 OR
!a1*!a3*a4*!b1*!b2*!b4 OR
!a3*!a4*!b3*b4 OR
a0*a1*a4*b0*b2*b3*b4 OR
!a1*!a4*!b1*!b2*!b3*b4 OR
!a0*!a3*!a4*!b1*!b2*b4 OR
!a1*!a3*!a4*!b1*!b2*b4 OR
a2*a3*!a4*b2*!b4 OR
!a2*!a3*a4*!b2*!b4 OR
a0*a3*!a4*b0*b1*b2*!b4 OR
a1*!a4*b1*b2*b3*!b4 OR
a0*a3*a4*b0*b1*b2*b4 OR
!a2*!a3*a4*!b0*!b1*!b4 OR
!a1*a4*!b0*!b2*!b3*!b4 OR
!a1*!a2*!a3*a4*!b1*!b4 OR
!a3*a4*!b0*!b1*!b2*!b4 OR
!a1*!a3*a4*!b0*!b2*!b4 OR
!a3*!a4*!b0*!b1*!b2*b4 OR
!a0*a4*!b1*!b2*!b3*!b4 OR
a1*a4*b1*b2*b3*b4 OR
!a0*!a2*a4*!b1*!b3*!b4 OR
!a0*!a1*!a4*!b2*!b3*b4 OR
!a0*!a1*!a2*!a3*!a4*b4 OR
!a1*!a2*!a4*!b0*!b3*b4 OR
!a2*a4*!b2*!b3*!b4 OR
!a0*!a2*!a4*!b1*!b3*b4 OR
!a2*!a4*!b0*!b1*!b3*b4 OR
a0*a2*a4*b0*b1*b3*b4 OR
!a0*!a2*!a3*!a4*!b1*b4 OR
!a3*a4*!b3*!b4 OR
!a1*!a4*!b0*!b2*!b3*b4 OR
a0*a2*a3*!a4*b0*b1*!b4 OR
!a1*!a2*a4*!b1*!b3*!b4 OR
a0*a1*a2*a4*b0*b3*b4

------------BIT 5-----------------
a0*a1*a4*b0*b2*b3 OR
a2*a3*b2*b4 OR
a1*a2*a3*a4*b1 OR
a2*b2*b3*b4 OR
a0*a1*a3*a4*b0*b2 OR
a0*a4*b0*b1*b2*b3 OR
a1*a4*b1*b2*b3 OR
a0*a2*b0*b1*b3*b4 OR
a1*a3*b1*b2*b4 OR
a2*a4*b2*b3 OR
a0*a1*a2*b0*b3*b4 OR
a0*b0*b1*b2*b3*b4 OR
a0*a1*a3*b0*b2*b4 OR
a0*a1*b0*b2*b3*b4 OR
a1*a2*a3*b1*b4 OR
a4*b4 OR
a2*a3*a4*b2 OR
a0*a1*a2*a3*b0*b4 OR
a1*a2*b1*b3*b4 OR
a1*a2*a4*b1*b3 OR
a3*a4*b3 OR
a0*a1*a2*a3*a4*b0 OR
a1*b1*b2*b3*b4 OR
a1*a3*a4*b1*b2 OR
a0*a3*a4*b0*b1*b2 OR
a0*a2*a3*b0*b1*b4 OR
a0*a3*b0*b1*b2*b4 OR
a0*a2*a3*a4*b0*b1 OR
a0*a1*a2*a4*b0*b3 OR
a3*b3*b4 OR
a0*a2*a4*b0*b1*b3

Да, теперь это число имеет на один бит больше: сумма чисел может дать один новый бит.

А вот столько членов в каждом бите суммы
В бите 0: 2
В бите 1: 6
В бите 2: 16
В бите 3: 36
В бите 4: 76
В бите 5: 156
В бите 6: 316
В бите 7: 636
В бите 8: 1276
В бите 9: 2556
В бите 10: 1023

Членом я подразумеваю слагаемое после приведения выражения в дизъюнктивную нормальную форму (понапридумывали же терминов), проще говоря после приведения к виду как выше записана сумма по пяти битам.

Глава 2. Умножение


Глава вторая, умножение. Складывать мы научились, значит умеем и умножать! Да, столбиком, как учили в школе, только над двоичными числами. В цикле это будет выглядеть следующим образом: к первому операнду прибавляем второй операнд, сдвинутый побитово на $inline$i$inline$ бит, и умноженный в каждом бите на $inline$i$inline$-й бит первого операнда. Видимо псевдокодом это будет выглядеть нагляднее:

    var big, small // наши числа 
    for (int i = 0; i < small.bits.size(); i++ ) {
        var big_tmp = big;
        for (int j = 0; j < big.bits.size(); j++) {
            big_tmp.bits[j] = big.bits[j] * small.bits[i];
        }
        result = (result + big_tmp.operator_SHIFT_LEFT(i));
    }

При умножении чисел длинной m и n бит получится число длиной m+n бит.

Упрощение результата умножения занимает очень много ресурсов, и выглядит очень многочленно, вот произведение трех-битовых чисел:

Показать
------------BIT 0-----------------
a0*b0

------------BIT 1-----------------
a1*b0*!b1 OR
!a0*a1*b0 OR
a0*!b0*b1 OR
a0*!a1*b1

------------BIT 2-----------------
!a0*!a1*a2*b0 OR
a0*!b0*!b1*b2 OR
a0*!a1*!b0*b2 OR
a0*a1*a2*b0*b1*!b2 OR
a0*!a2*!b1*b2 OR
!a0*a1*!a2*b1 OR
a0*!a2*b0*b2 OR
a0*!a1*!a2*b2 OR
a2*b0*!b1*!b2 OR
a1*!b0*b1*!b2 OR
!a1*a2*b0*!b2 OR
!a0*a2*b0*!b1 OR
!a0*a1*!b0*b1

------------BIT 3-----------------
!a0*a1*b0*b2 OR
a0*a1*a2*!b0*b1*b2 OR
!a1*a2*b1*!b2 OR
a2*!b0*b1*!b2 OR
a0*!a1*a2*b0*!b1*b2 OR
!a0*a1*!a2*b2 OR
a1*!b0*!b1*b2 OR
!a0*!a1*a2*b1 OR
a1*!a2*!b1*b2 OR
a0*a1*!a2*b0*b1*!b2 OR
!a1*a2*!b0*b1 OR
!a0*a1*!b1*b2

------------BIT 4-----------------
!a0*!a1*a2*b2 OR
!a1*a2*!b1*b2 OR
a0*a1*a2*b0*b1*b2 OR
a2*!b0*!b1*b2 OR
!a1*a2*!b0*b2 OR
a0*a1*!a2*!b0*b1*b2 OR
!a0*a2*!b1*b2 OR
a1*a2*b0*b1*!b2 OR
a0*a1*!a2*b0*b1*b2

------------BIT 5-----------------
a0*a1*a2*b0*!b1*b2 OR
a1*a2*!b0*b1*b2 OR
a1*a2*b0*b1*b2 OR
a0*!a1*a2*b0*b1*b2

А вот сколько членов в битах произведения 6x6
В бите 0: 1
В бите 1: 4
В бите 2: 13
В бите 3: 41
В бите 4: 168
В бите 5: 656
В бите 6: 791
В бите 7: 778
В бите 8: 606
В бите 9: 402
В бите 10: 240
В бите 11: 135

Но это только один из вариантов упрощения громоздкого многоэтажного выражения от умножения. У вас могут получиться другие значения для старших битов, всё зависит насколько сильно вы сможете упростить логическое выражение.

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

На этом этапе я столкнулся с одной из первых заморочек. А возможно ли, посмотрев на упрощенные произведения маленьких порядков, найти какую-то зависимость, и научиться строить такую формулу.

В результате и сложения и умножения должна присутствовать симметрия относительно a и b, на младших битах она видна невооруженным глазом, а что бы её увидеть на старших битах глаз нужно вооружать.

Так вот, возможно ли построить формулу для старших бит сложения/умножения, глядя на младшие биты? У меня не получилось, может получится у вас?

Но есть и обратная сторона медали: упрощенное выражение точно будет занимать много места, поэтому упрощать произведение двух 1024-битных чисел просто не имеет смысла. Но ведь всем интересно умножать 1024-битные (особенно простые) числа, не так ли? Придётся учиться работать с вложенными логическими выражениями.

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

Глава третья, самая интересная


Возьмём к примеру md5. 64 скучных примерно одинаковых раунда. При вычислениях используются только обычные логические операторы и вышеописанная сумма. Только биты старше 32 отбрасываются. Ну вот, готово, мы умеем вычислять md5 при помощи вложенных битовых формул.

Примерно это выглядит так.

На вход md5 подадим к примеру 128 логических переменных. Вложенные переменные я обзываю переменной t, и начинаю нумеровать номерами после основных. В данном случае основные переменные (те, которые подаются на вход функции md5) от $inline$x0$inline$ до $inline$x127$inline$, а вложенные начинаются от $inline$t128$inline$. Тогда первый бит результата будет примерно таким (всё зависит в какие моменты алгоритма вы будете свёртывать выражение в t-переменную).

Например таким
md5[0] =
t67168*t70255 OR
t67167*t70255 OR
t67163*t67169*t70255 OR
!t65928*!t65929*!t65930*t65936*t67155*t67169*t70255 OR
t65929*t65937*t67155*t67169*t70255 OR
!t65928*!t65929*!t65930*t65938*t67155*t67169*t70255 OR
t65928*t65937*t67155*t67169*t70255 OR
t65929*t65939*t67155*t67169*t70255 OR
t65928*t65939*t67155*t67169*t70255 OR
t67162*t67169*t70255 OR
t67166*t70255 OR
t65937*t65930*t67155*t67169*t70255 OR
t65930*t65939*t67155*t67169*t70255

где каждая t-переменная есть другое выражение.

И в конце цепочки примерно такое
t219 =
!x6*t139*t217 OR
!x6*t140*t217 OR
t211*!t135*t217 OR
!x6*t211*t217 OR
!x10*t139*t217 OR
!x10*t211*t217 OR
!x8*t211*t217 OR
!x8*t139*t217 OR
!x9*t140*t217 OR
!x8*t140*t217 OR
!x9*t139*t217 OR
!x10*t140*t217 OR
!t135*t140*t217 OR
!x9*t211*t217 OR
!t135*t139*t217
…
t128 =
x0 OR
x5 OR
x6 OR
x4 OR
x8 OR
x7 OR
x9 OR
x3 OR
x10 OR
x2 OR
x1

Как вы поняли сложность функции md5 от 128 битов примерно равна 70000. То есть в результате мы получаем ~70000 t-переменных. Как оказалось если подать на вход 15, 256, 347, или 512 переменных, то вложенность (то есть количество t-переменных) будет примерно тем же самым. Здесь нужно сделать важную оговорку. Операция создания t-переменной во время вычислений логических выражений применяется после логических операторов $inline$AND$inline$ и $inline$AND3$inline$, после $inline$OR$inline$ и $inline$XOR3$inline$ выполняется упрощение, у меня вот так, поэтому и такой результат.

Итак, вложенная сложность md5 равна 70K. Полученную формулу в t-переменных для каждого бита будем называть переменной логического представления.

А теперь. Теперь мы делаем следующее. Берем любой хеш, и представляем его в виде битов. Там, где бит хеша равен 0, берем соответствующую переменную логического представления, там где 1 — инвертированную (оператор $inline$NOT$inline$). И складываем их оператором $inline$OR$inline$. В результате у нас получается новое вложенное логическое выражение, и приравниваем его к $inline$FALSE$inline$.

Что же это выражение означает? А оно описывает все возможные решения для заданного хеша. А если упростить, подставляя t-переменные, то решения окажутся как на ладони. Вот только упростить её не получится. На этом этапе мне пришлось покупать качественную губозакатывательную машинку.

Ну ладно, упростить не можем, но может быть хоть краешком глаза подсмотреть хоть одно возможное решение… Действительно, зачем нам все, нам бы хоть одно… И вот тут начинается вообще самое интересное. У нас есть логическая формула, которая равна $inline$FALSE$inline$. Это значит, что если на каком-то этапе упрощений какой-то член упростится в $inline$TRUE$inline$, то хеш не имеет решений. Начиная упрощать выражение, можно заметить как многие члены самоликвидируются, превращаясь в $inline$FALSE$inline$. То есть после подстановки t-переменной получается что-то типа $inline$t67234\ *\ !t67234 * …$inline$ То есть, если б мы заранее знали какой член тождественно равен $inline$FALSE$inline$, мы бы смогли избежать вычислительно ада по подстановке t-переменных в таких членах.

Итак, торжественно заявляю. Задача решения вложенного логического выражения в условиях вычислительного ада сводится к определению членов, тождественно равных $inline$FALSE$inline$. Вот и всё. Если это сделать, вы догадываетесь что произойдёт. Некоторые криптографические алгоритмы превратятся в тыкву. Вложенная сложность умножения двух 256-битных чисел — около 500К, 512-битных — 2М, 1024 — 8М, и так далее. Да, умножение чисел превращается в такую же вложенную конструкцию, только сложность побольше.

На этом этапе я изрядно потрепал свою губозакатывательную машинку. Я опробовал несколько идей, но… всё безрезультатно. Пока не нашлось признаков, по которым можно хоть как-то идентифицировать false-члены. Может мало старался. А прикиньте, оно было уже где-то рядом, а я не нашел, не дошел, вот будет обидно… Но, возможно, это моя карма — проходить половину пути. Вот как-то так.

P.S.


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

Мазай Банзаев.
Поделиться с друзьями
-->

Комментарии (43)


  1. webmasterx
    28.01.2017 12:49
    #10039802

    Так у вас в умножении что? AND или умножение чисел?


    1. pokamest_nikak
      28.01.2017 12:57
      #10039808
      +1

      a0, a1, a2, b0, b1, b2 — это булевы переменные, и a0*b0 в умножении — это a0 AND b0.


      1. webmasterx
        28.01.2017 12:59
        #10039812

        это не ответ


    1. zuborg
      28.01.2017 13:35
      #10039852
      +1

      Если речь идет о символе '*', то в тексте прямо написано, что это обозначение для AND.
      И для однобитовых переменных операция AND тождественна математическому умножению.


      1. pokamest_nikak
        28.01.2017 13:50
        #10039864

        Да, это просто такая запись для 'AND', чтобы легче читались выражения.


  1. pokamest_nikak
    28.01.2017 13:04
    #10039822
    +1

    Тогда я не понимаю вопрос.
    Обычное умножение двух чисел представлено в виде набора логических выражений для каждого бита.
    То есть если мы хотим умножить 5х7, мы представляем 5 и 7 в двоичном виде, и подставляя биты в формулы можем получить частные биты результата 35.


    1. webmasterx
      28.01.2017 13:10
      #10039826

      очень интересно посмотреть как это получится.
      Я это говорю к тому, что
      1)текст очень трудно понять
      2) не уровень хабра
      3) называть отдельные биты переменными… зачем?


      1. webmasterx
        28.01.2017 13:13
        #10039830
        +1

        И какое это имеет отношение к криптографии и математике?


        1. pokamest_nikak
          28.01.2017 13:18
          #10039834
          -2

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


          1. devpony
            28.01.2017 15:18
            #10040016
            +1

            Зачем?


          1. michael_vostrikov
            28.01.2017 15:55
            #10040046

            Если я правильно понял рассуждения в статье, с вложенными выражениями это ничем не отличается от обычного итеративного вычисления. Только там результат итерации записывается в те же переменные, а у вас получается на каждую итерацию свой набор, да еще и разделенный по битам. Поэтому t-переменных так много.


            1. pokamest_nikak
              28.01.2017 16:32
              #10040116
              -1

              Да, каждый бит результата — это отдельное логическое выражение. И результат «вычисляется» не для каких-то конкретных значений, а для логических переменных, то есть все вычисления производятся в виде логических формул, зависящих от входных битов a0,a1,a2… и от промежуточных логических переменных t_12345, которые сами являются логическими выражениями.


  1. michael_vostrikov
    28.01.2017 14:06
    #10039888
    +1

    Одно время тоже заморочился с md5. Подумал, а что если для каждого бита получить логическое выражение из тех битов, которые участвуют в вычислениях. Часть битов будет из инициализирующего вектора, то есть константы. Значит, часть выражения можно сильно сократить. Останутся 128 логических уравнений, из которых может быть получится найти одно из решений, задав часть неизвестных нулями.

    На практике это оказалось мало осуществимым. Для второго раунда будут выражения вида (a*b), для третьего (a*b) * (c*d), для четвертого ((a*b)*(c*d)) * ((e*f)*(g*h)) (звездочка означает какую-то логическую операцию). То есть, с каждым раундом длина уравнения увеличивается вдвое. Тогда я понял, что записать результат после 64 раунда не хватит жесткого диска, и взлом md5 не состоялся)


    1. pokamest_nikak
      28.01.2017 14:22
      #10039914
      -1

      Ну так вот да, если мы будем эти выражения упрощать, то они начинают занимать неприлично много места, и что самое главное сам процесс упрощения занимает очень много времени. А я не стал их упрощать, и начал записывать в виде вложенных выражений с промежуточными t-переменными. Видимо я этот момент недостаточно освятил. Я на некоторых этапах вычислений ввожу эти промежуточные t-переменные, таким образом текущее выражение сворачивается в одну переменную. Таким образом я могу получить конечный результат, только он получается в виде «вложенного» логического выражения, записанного через промежуточные логические переменные. Вот эти конструкции я и начал исследовать.


  1. old_bear
    28.01.2017 14:17
    #10039904

    На хабре отменили премодерацию статей или это жертва на заклание в выходные?


    1. webmasterx
      28.01.2017 14:21
      #10039910
      +3

      Наверное в модерации сидят люди знающие только русский язык.
      Надо бы добавить кнопку «Сжечь» для публикаций. незачем засорять ресурс, без того сильно захламленный 1сниками с видеоуроками


    1. pokamest_nikak
      28.01.2017 14:36
      #10039928
      +2

      Я готов к конструктивной критике. Мне было нелегко описывать словами эти результаты, и я знаю что текст не идеальный. Я готов подробнее объяснить, если что-то не понятно из текста и из смысла.


      1. Sirion
        28.01.2017 14:55
        #10039974

        Прошу прощения, но если вы пишете хабрапост, вы должны быть готовы описать словами то, что хотите описать. Если то, что вы хотите сказать, становится ясно только после нескольких итераций обсуждения, с этим надо идти на форум (могу порекомендовать dxdy.ru).


  1. pokamest_nikak
    28.01.2017 15:01
    #10039992

    Ну так напишите что именно непонятно! Я как раз и попытался словами расписать начиная с самого простого, и далее углубляясь в тему.


    1. devpony
      28.01.2017 15:16
      #10040012

      Можно начать с хороших обозначений. x0 заменить на x_0, * на \cdot и т.д. (Кстати, на телефоне формулы вообще не отображаются..) Затем внятно и понятно описать, что вы делаете и зачем, кому будет интересна ваша статья. В конце стоит в простом и понятном виде предоставить результат ваших изысканий, будь он теоретическим, практическим или отрицательным. Результат должен отвечать цели, поставленной в начале статьи. Не помешала бы пара картинок вместо простыней текста под спойлерами. Стоило тщательно подумать над выбором хабов. Ненормальное программирование — хорошо, а вот в математике или криптографии обычно сидят очень требовательные люди, тогда как ваша статья не имеет к этим хабам ну вообще ничего общего.


      1. pokamest_nikak
        28.01.2017 15:30
        #10040028

        Формулы сделаны по стандарту хабры — они видимо в картинки преобразуются, и картинки у вас не загружаются.
        Не помешала бы пара картинок? Я даже не знаю что на них можно было бы показать. Весь результат — это и есть эти самые простыни из формул, и подход, по которому эти простыни получаются.
        К математике это относится самым прямым образом — это сложение и умножение. К криптографии это тоже относится, так как асимметричная криптография — это проблема умножения простых чисел, а так же я реализовал всё вышеописанное для вычислений md5.


        1. devpony
          28.01.2017 16:43
          #10040136
          +1

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


          1. pokamest_nikak
            28.01.2017 16:59
            #10040146

            Проблема асимметричной криптографии — это проблема умножения больших чисел, а точнее нахождения делителей для заданного очень длинного числа. Я научился представлять результат умножения в виде набора вложенных логических выражений для каждого бита. Упростить эти выражения в общем случае вычислительно невозможно.
            Далее, озвучен тезис о том, что некоторые члены таких выражений заведомо тождественны FALSE.
            Членом я подразумеваю выражение, в котором используется только оператор конъюнкции (у меня он обозначается "*").
            Так вот, если научиться без упрощения выделять такие члены среди всех остальных, то задача упрощения выражений заметно облегчится. А упрощенные выражения (в нормальной дизъюнктивной форме) и будут представлять собой возможные решения.


    1. michael_vostrikov
      28.01.2017 16:00
      #10040052
      -1

      Вы бы привели пример с конкретным хешем. А то у вас какая-то куча формул, которые непонятно как использовать.


      1. pokamest_nikak
        28.01.2017 16:21
        #10040080

        Да вот в том то и дело, что сложно показать какой либо конкретный пример. Для md5 эта простыня состоит из 70 тысяч логических выражений и абсолютно не наглядна, я же не могу её сюда скопировать. Но тем не менее этот набор выражений даёт верный конечный результат, вычисляя к примеру md5 так же, как оригинальный алгоритм.
        Я абстрагируюсь от конкретных значений, и провожу все вычисления «формульно». То есть пришлось написать машину, которая умеет работать с такими вложенными выражениями: выполнять логические операции над ними, упрощать их когда нужно, подставлять t-переменные.


        1. michael_vostrikov
          28.01.2017 17:00
          #10040150
          +1

          Для md5 эта простыня состоит из 70 тысяч логических выражений и абсолютно не наглядна, я же не могу её сюда скопировать.

          Было бы достаточно показать начало вычислений для 1-2 битов, хоть в конкретных значениях, хоть в формулах. А вы сразу результат дали.


          Но тем не менее этот набор выражений даёт верный конечный результат, вычисляя к примеру md5 так же, как оригинальный алгоритм.

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


          1. pokamest_nikak
            28.01.2017 17:18
            #10040174

            В смысле разделено на раунды? Результат для md5 есть 128 вложенных логических выражений. Каждое из них содержит в себе все раунды, все необходимые вычисления, что бы получить соответствующий бит самого хеша.
            Фактически я реализовал алгоритм md5 просто в формульном виде. И получил результат в виде формулы, с которой и ставил эксперименты.


            1. michael_vostrikov
              28.01.2017 18:36
              #10040244

              Я про это и говорю. На каком-то из раундов вы заменяете большое выражение для вычисления бита промежуточной переменной. Еще через сколько-то раундов снова. Вы просто развернули цикл в последовательный набор выражений. Вот если бы вы придумали, как это использовать, было бы полезно.


  1. ITMatika
    28.01.2017 16:46
    #10040140

    Как я понял статью, сугубо ИМХО.
    В двух словах о чём эта статья для тех, кто не до конца разобрался:
    Автор ищет свои пути в криптографии. В частности, ищет методы, которые можно было бы применить для поиска коллизий md5 или других функций.
    А может и для проверки гипотезы Эйлера для разных n. К сожалению, практических полезных результатов автор пока не получил.
    Так что и практическая ценность статьи для общественности сомнительна. А теоретическая — тут уже у каждого своё мнение.


    1. pokamest_nikak
      28.01.2017 17:09
      #10040160
      -1

      Да, абсолютно верно. Желаемого результата получено не было. Если бы был — я бы не писал… Здесь описывается только подход, который не принёс пока конечного результата, но принёс некоторые промежуточные. Я решил вынести этот подход на суд общественности, в том числе чтобы получить хоть какой-то конструктивный фидбэк.


      1. askv
        28.01.2017 17:23
        #10040186

        Заминусуют карму, вот и весь фидбэк :)


  1. Mizari
    29.01.2017 01:18
    #10040776
    +1

    Автор изобрёл велосипед в виде функционально полной системы булевых функций. Автор, почитайте про ДНФ, КНФ, АНФ. Практической пользы нет: такие формулы экспоненциально большие, и их построение занимает экспоненциально много времени.

    По поводу поиска членов, тождественно равных FALSE — это SAT, и она NP-сложна.


    1. pokamest_nikak
      29.01.2017 01:57
      #10040796
      -1

      Согласно теореме Кука, доказанной Стивеном Куком в 1971 году, задача SAT для булевых формул, записанных в конъюнктивной нормальной форме, является NP-полной.

      Требование о записи в конъюнктивной форме существенно, так как, например, задача SAT для формул, представленных в дизъюнктивной нормальной форме, тривиально решается за линейное время в зависимости от размера записи формулы

      А вложенные выражения не являются ни конъюнктивной нормальной формой, ни дизъюнктивной.
      И согласно моим умозаключениям, эта задача поиска false-членов для класса вложенных выражений не является ни NP, ни P, и зависит от самого выражения. Я думаю это утверждение можно легко доказать от обратного, построив два вложенных выражения, которые тождественны false, и одно из них раскладывается за полиномиальное время, другое за линейное на первой же итерации подстановки.


      1. Sirion
        29.01.2017 02:21
        #10040832

        Вы ведь понимаете, что фраза «не является P» переводится на русский как «охрененно сложная, неразрешимая за разумное время»?


        1. pokamest_nikak
          29.01.2017 02:37
          #10040842
          -1

          Да, это в общем случае. В общем случае нельзя утверждать что вложенное логическое выражение является P, или NP. Оно может быть P, а может быть и NP. Попробуйте опровергнуть?


          1. Sirion
            29.01.2017 03:01
            #10040852

            Что значит «выражение является P»? Можно строгую формулировку?


            1. pokamest_nikak
              29.01.2017 03:17
              #10040878
              -1

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


  1. pokamest_nikak
    29.01.2017 03:17
    #10040876

    del


  1. andy_p
    29.01.2017 10:59
    #10041132
    +1

    Автору этой статьи следует открыть для себя boolean SAT.


    1. pokamest_nikak
      29.01.2017 13:11
      #10041264
      -1

      Поможете мне его открыть? Есть какие-нибудь источники, где можно почитать про SAT для выражений не в нормальной форме?


      1. 32bit_me
        29.01.2017 13:20
        #10041288

        Вы меня извините, что вмешиваюсь в вашу беседу, но первая ссылка в гугле по запросу boolean SAT ведёт к большой, хорошей статье в Википедии.
        Хотя я всё равно не понимаю, зачем вы это делаете. Если вы открыли для себя, что комбинаторные функции можно использовать для сложения и умножения чисел, я вас поздравляю, но не стоило об этом писать на хабр. И в любом случае делать это «в столбик» глупо.
        У вас там сверху написано «думаю», Подумайте ещё раз.


  1. osseum
    29.01.2017 12:58
    #10041250

    Я что-то не понял из статьи, как вы упрощали, подставляли вложенные выражения?


    1. pokamest_nikak
      29.01.2017 13:08
      #10041256
      -1

      Упрощение — приведение в ДНФ форму. Но в какой-то момент вычислений ДНФ-выражение становится слишком громоздким, и заменяется у меня одной t-переменной. Таким образом удаётся дойти дойти до конца алгоритма за приемлемое время. А далее, свернув все биты результата в одно выражение, обратно подставляю эти t-переменные, и привожу в ДНФ результат на каждой итерации.