Отвечая на письмо в haskell-cafe, нафигачил пример.
http://thesz.mskhug.ru/svn/cryptomatrix/
Там сделано умножение матриц (не уверен насчёт правильности, но для примера сойдёт), операции которого (+ и *) можно перегрузить. Интересно было посмотреть на поведение умножения с такой перегрузкой. Для обычного умножения матриц есть интересное наблюдение: если матрицы независимы (ну, разной природы), полного ранга и имеют ненулевые коэффициенты вне диагонали, то произведение этих матриц становится всё плотнее и плотнее. Например, умножение двух ленточных матриц с шириной лент N и M даст ленточную матрицу с шириной ленты (N+M).
Что это означает. Что для криптографического преобразования, в котором мы хотим перемешать все биты со всеми, мы можем сделать факторизацию "матричных умножений". Результирующая матрица будет плотной, а промежуточные будут достаточно разрежены (но с регулярной структурой, наподобие ленточных или блочно-диагональных). Линейность же можно убрать с помощью нелинейных преобразований: заменив сложение на Исключающее ИЛИ, умножение на циклический сдвиг вправо. Или на что-нибудь другое.
PS
Идею подал permea_kra, как я понял.
PPS
Там очень интересно!
Например, "перемножение" блочно-диагональных матриц с +≡XOR и *≡"умножение по модулю 257" не даёт увеличение плотности. ;)
То есть, эти две операции взаимодействуют друг с другом нехорошим для стойкости образом. ;)
Там сделано умножение матриц (не уверен насчёт правильности, но для примера сойдёт), операции которого (+ и *) можно перегрузить. Интересно было посмотреть на поведение умножения с такой перегрузкой. Для обычного умножения матриц есть интересное наблюдение: если матрицы независимы (ну, разной природы), полного ранга и имеют ненулевые коэффициенты вне диагонали, то произведение этих матриц становится всё плотнее и плотнее. Например, умножение двух ленточных матриц с шириной лент N и M даст ленточную матрицу с шириной ленты (N+M).
Что это означает. Что для криптографического преобразования, в котором мы хотим перемешать все биты со всеми, мы можем сделать факторизацию "матричных умножений". Результирующая матрица будет плотной, а промежуточные будут достаточно разрежены (но с регулярной структурой, наподобие ленточных или блочно-диагональных). Линейность же можно убрать с помощью нелинейных преобразований: заменив сложение на Исключающее ИЛИ, умножение на циклический сдвиг вправо. Или на что-нибудь другое.
PS
Идею подал permea_kra, как я понял.
PPS
Там очень интересно!
Например, "перемножение" блочно-диагональных матриц с +≡XOR и *≡"умножение по модулю 257" не даёт увеличение плотности. ;)
То есть, эти две операции взаимодействуют друг с другом нехорошим для стойкости образом. ;)