i |
Deggial: Сообщение MerkulovaLE выделено отсюда |
Добрый вечер!
Предлагаю доказывать P vs NP с помощью однонаправленной хеш-функции.
Хеш - это преобразование массива входных данных произвольной длины в (выходную) битовую строку
установленной длины, выполняемое определённым алгоритмом.
Функция, воплощающая алгоритм и выполняющая преобразование, называется
«хеш-функцией» или «функцией свёртки».
Исходные данные называются входным массивом, «ключом» или «сообщением».
Результат преобразования (выходные данные) называется «хешем», «хеш-кодом»,
«хеш-суммой», «сводкой сообщения».
Пусть хеш переводит

байт в

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

бит в «логине» и

бит в «пароле».
Если меньше, то дополняется нулями.
Далее путем инверсии первых

бит, выравнивается количество единиц и нулей – по

.

.

записывается

битами

эти

бит инвертированные и столько же дополнительных

бит (в

-х матрицах -

).
Имеем

квадратные матрицы из

элементов,

и

.
Полученные

бит представляются в виде

строк по

столбцов чисел от

до

из

бит (матрица

, первая половина).
Строятся

строки матрицы
![$T_01[0..1,0..15]$ $T_01[0..1,0..15]$](https://dxdy-02.korotkov.co.uk/f/1/9/1/1914fd36a9d85ed382511b02d149462c82.png)
: обе строки – сначала строки

чисел от

до

в порядке возрастания, затем к ней применяется первая матрица

строка за строкой сверху вниз следующим образом: если в строке

-тый элемент равен нулю, то элементы

,
(i+1) mod 16 и
(i+2) mod 16 первой строки

циклически сдвигаются вправо на

элемент, иначе – влево.
Вторая матрица

строка за строкой сверху вниз применяется к

следующим образом: если в строке

-тый элемент равен нулю, то элементы

,
((i+1) mod 16) и
((i+2) mod 16) второй строки

циклически сдвигаются влево на

элемент, иначе – вправо.
Матрица

достраивается до

строк путем прибавления по модулю

к

строкам с нулевой по третью – первой строки

, и к четырем строкам с четвертой по седьмую – второй строки

плюс

,

,

,

позиций.
Далее строится матрица

. Для этого берется матрица

x

,
Код:
Q_01[i,j] := (i+j) mod 16
. Далее каждая

-тая строка матрицы

изменяется с помощью соответствующей

-той строки матрицы

.
![$Q_01[i,j]$ $Q_01[i,j]$](https://dxdy-02.korotkov.co.uk/f/5/b/4/5b453294936a7652de1a96f420c5857782.png)
меняется местами с
![$Q_01[R[i,j],j]$ $Q_01[R[i,j],j]$](https://dxdy-03.korotkov.co.uk/f/a/3/a/a3adc2abf0b4adefa1c0695138a6d08c82.png)
.
Далее производится число
rounds
процедуры
etap1 алгоритма Сцилла .
Etap1 меняет

,

,

и

. Строки

в соответствии с

применяются к строкам и столбцам

и

.

-тый элемент каждой строки в порядке возрастания (столбца) обрабатывается в соответствии с

-той (
![$T_01[1,i]$ $T_01[1,i]$](https://dxdy-02.korotkov.co.uk/f/1/f/8/1f89378e926846b79d292578aa6c88aa82.png)
или
![$T_01[0,i]$ $T_01[0,i]$](https://dxdy-04.korotkov.co.uk/f/3/1/8/318de999a67af04608ebcfa7f676ed7682.png)
) строкой

.
Он (элемент) переносится на место с индексом №
![$Q[i,k]$ $Q[i,k]$](https://dxdy-04.korotkov.co.uk/f/f/d/e/fdeda1dfc9f1f16e348329f0fe68f16182.png)
в строке (столбце). Затем первоначальный вариант строки (столбца) применяется к

-той строке

: единица меняет три элемента циклическим сдвигом на одну позицию в одну сторону, а нуль – в другую. Процедура
Etap1 сильно перемешивает исходные данные. Матрица

тоже меняется в соответствии со старыми копиями

и

. Это усложняет расшифровку хеша.
После – зависящий от

и

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

.

-тый элемент столбца №
![$T_01[0,i]$ $T_01[0,i]$](https://dxdy-04.korotkov.co.uk/f/3/1/8/318de999a67af04608ebcfa7f676ed7682.png)
C_01меняется местом с
![$R_01[i,j]$ $R_01[i,j]$](https://dxdy-02.korotkov.co.uk/f/5/0/5/505f0b046e808b6dfd8e3ae11c48734682.png)
-тым элементом.

-тый элемент столбца №
![$T_01[1,i]$ $T_01[1,i]$](https://dxdy-02.korotkov.co.uk/f/1/f/8/1f89378e926846b79d292578aa6c88aa82.png)
D_01меняется местом с
![$R_01[i,j]$ $R_01[i,j]$](https://dxdy-02.korotkov.co.uk/f/5/0/5/505f0b046e808b6dfd8e3ae11c48734682.png)
-тым элементом.
Матрица

заменяется первоначальным значением

.

-тый элемент строки

№
![$T_01[0,i]$ $T_01[0,i]$](https://dxdy-04.korotkov.co.uk/f/3/1/8/318de999a67af04608ebcfa7f676ed7682.png)
меняется местом с
![$R_01[j,i]$ $R_01[j,i]$](https://dxdy-04.korotkov.co.uk/f/3/0/c/30cc2981a8f144a0e213c7916f25574682.png)
-тым элементом.

-тый элемент строки

№
![$T_01[1,i ]$ $T_01[1,i ]$](https://dxdy-02.korotkov.co.uk/f/1/8/9/189565540cb43d63ca46fbeca6dbcd7382.png)
меняется местом с
![$R_01[j,i]$ $R_01[j,i]$](https://dxdy-04.korotkov.co.uk/f/3/0/c/30cc2981a8f144a0e213c7916f25574682.png)
-тым элементом.
Простое толкование проблемы P vs NP - если можно быстро проверить решение, можно ли его быстро получить?
Зная ключ, легко и в полиномиальное время можно получить хеш-код, но зная хеш-код, ключ можно получить
перебором, так как ключ сложным образом перемешивается, а потом к нему применяется первоначальное
значение ключа. Каждый бит в хеш-коде зависит от каждого бита ключа, и при небольшом изменении ключа,
хеш-код меняется сильно.
Ссылка
https://cloud.mail.ru/public/MQco/XQvHvhkLC