P vs NP с помощью однонаправленной функции.

[MerkulovaLE]

Deggial:
Сообщение MerkulovaLE выделено отсюда

Добрый вечер!

Предлагаю доказывать P vs NP с помощью однонаправленной хеш-функции.

Хеш - это преобразование массива входных данных произвольной длины в (выходную) битовую строку
установленной длины, выполняемое определённым алгоритмом.
Функция, воплощающая алгоритм и выполняющая преобразование, называется
«хеш-функцией» или «функцией свёртки».
Исходные данные называются входным массивом, «ключом» или «сообщением».
Результат преобразования (выходные данные) называется «хешем», «хеш-кодом»,
«хеш-суммой», «сводкой сообщения».

Пусть хеш переводит $480$ байт в $512$

Хеш-функция «Сцилла» (Scylla5).

Функция для $240$ бит в «логине» и $240$ бит в «пароле».
Если меньше, то дополняется нулями.

Далее путем инверсии первых $n$ бит, выравнивается количество единиц и нулей – по $120$.$(1\leqslant n \leqslant240)$. $n$ записывается $8$ битами $+$ эти $8$ бит инвертированные и столько же дополнительных $16$ бит (в $2$-х матрицах - $32$).
Имеем $2$ квадратные матрицы из $256$ элементов, $C_01$ и $D_01$.

Полученные $512$ бит представляются в виде $8$ строк по $16$ столбцов чисел от $0$ до $15$ из $4$ бит (матрица $R_01$, первая половина).

Строятся $2$ строки матрицы $T_01[0..1,0..15]$ : обе строки – сначала строки $16$ чисел от $0$ до $15$ в порядке возрастания, затем к ней применяется первая матрица $C_01$ строка за строкой сверху вниз следующим образом: если в строке $i$-тый элемент равен нулю, то элементы $i$, (i+1) mod 16 и (i+2) mod 16 первой строки $T_01$ циклически сдвигаются вправо на $1$ элемент, иначе – влево.
Вторая матрица $D_01$ строка за строкой сверху вниз применяется к $T_01$ следующим образом: если в строке $i$-тый элемент равен нулю, то элементы $i$, ((i+1) mod 16) и ((i+2) mod 16) второй строки $T_01$ циклически сдвигаются влево на $1$ элемент, иначе – вправо.

Матрица $ R_01$ достраивается до $16$ строк путем прибавления по модулю $16$ к $4$ строкам с нулевой по третью – первой строки $T_01$, и к четырем строкам с четвертой по седьмую – второй строки $T_01$ плюс $0$, $4$, $8$, $12$ позиций.

Далее строится матрица $Q_01$. Для этого берется матрица $16$x$16$,

Q_01[i,j] := (i+j) mod 16

. Далее каждая $i$-тая строка матрицы $Q_01$ изменяется с помощью соответствующей $i$-той строки матрицы $R_01$. $Q_01[i,j]$ меняется местами с $Q_01[R[i,j],j]$.

Далее производится число rounds$ = 1024$ процедуры etap1 алгоритма Сцилла .
Etap1 меняет $C_01$,$D_01$, $Q_01$ и $Т_01$. Строки $Q_01$ в соответствии с $T_01$ применяются к строкам и столбцам $C_01$ и $D_01$. $i$-тый элемент каждой строки в порядке возрастания (столбца) обрабатывается в соответствии с $k$-той ($T_01[1,i]$ или $T_01[0,i]$) строкой $Q_01$.

Он (элемент) переносится на место с индексом № $Q[i,k]$ в строке (столбце). Затем первоначальный вариант строки (столбца) применяется к $k$-той строке $Q_01$: единица меняет три элемента циклическим сдвигом на одну позицию в одну сторону, а нуль – в другую. Процедура Etap1 сильно перемешивает исходные данные. Матрица $T_01$ тоже меняется в соответствии со старыми копиями $ C_01$ и $D_01$. Это усложняет расшифровку хеша.

После – зависящий от $R_01$ и $T_01$ финал – процедуры final1 и final2. Используется первоначальная (в final2) и измененная etap1 (в final1) версии массива $T_01$.

$j$-тый элемент столбца № $T_01[0,i]$ C_01меняется местом с $R_01[i,j]$-тым элементом.
$j$-тый элемент столбца № $T_01[1,i]$ D_01меняется местом с $R_01[i,j]$-тым элементом.
Матрица $T_01$ заменяется первоначальным значением $T_01$.
$j$-тый элемент строки $C_01$ № $T_01[0,i]$ меняется местом с $R_01[j,i]$-тым элементом.
$j$-тый элемент строки $ D_01$ № $T_01[1,i ]$ меняется местом с $R_01[j,i]$-тым элементом.

Простое толкование проблемы P vs NP - если можно быстро проверить решение, можно ли его быстро получить?
Зная ключ, легко и в полиномиальное время можно получить хеш-код, но зная хеш-код, ключ можно получить
перебором, так как ключ сложным образом перемешивается, а потом к нему применяется первоначальное
значение ключа. Каждый бит в хеш-коде зависит от каждого бита ключа, и при небольшом изменении ключа,
хеш-код меняется сильно.

Ссылка https://cloud.mail.ru/public/MQco/XQvHvhkLC

[Deggial]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

MerkulovaLE

Наберите все формулы и термы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
Программный код оформляйте тегом code, короткие куски программы - тегом tt.

MerkulovaLE в сообщении #1343312 писал(а):

Вопрос к модератору: Можно ли сделать ссылку на программу с исходниками в облаке?

Можно, только помните, что ссылки (даже на книги) должны быть необязательны для понимания существа темы.
По правилам дискуссионного раздела все понятия и должны быть явно строго определены, а утверждения - доказаны. В частности, нужно дать чёткое определение хэш-функции, а доказательство $P\neq NP$ сейчас вообще отсутствует.
Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума