Symmetric cipher on the base of non-commutative algebra of polynomials.pdf Пусть F - некоторое поле, / (x),g(x) - элементы кольца F[x], ( / о g)(x) = / (g(x)) -композиция полиномов. Кольцо F[x] с дополнительной операцией композиции являетсянекоммутативной алгеброй полиномов с тремя бинарными операциями {+ , , о}.Решение уравнения( / о g)(x) = r(x) mod h(x), /, g, h, r Е F[x], (1)относительно неизвестного многочлена f или g сводится к поиску корней, принадлежащихосновному полю F, некоторых многочленов из кольца F[x], что не являетсятрудной задачей.Уравнение (1) естественным образом возникает в задаче определения группы алгебраическихсимметрий многочлена, которая в общем случае является подгруппойгруппы Галуа этого многочлена.Свойства операции композиции многочленов позволяют предложить следующуюмодель криптосистемы. Открытыми параметрами криптосистемы являются множестворазличных многочленов { f 1(x ),... , fn(x)}, f i(x) . F[x], степени k ^ 2 и некоторыйнеприводимый над F многочлен h(x); секретным ключом является некоторая перестановкаа . Sn. Открытый текст представляется многочленом m(x) . F[x], шифртекстомбудет следующий многочлен c(x):(fa„ ◦ ■ ■ ■ о fCTi о m)(x) = c(x) mod h(x). (2)Процесс шифрования заключается в вычислении по рекуррентной формуле:c0(x) = m(x); ci(x) = (fCTi о ci-1)(x) mod h(x), i = 1, . . . , n; c(x) = cn(x).Расшифрование заключается в последовательном решении систем вида (1) относительнонеизвестных многочленов cn_ 1, ... , c1, c0 = m(x):f о ci_ 1)(x) = Ci(x) mod h(x), i = n ,. . . , 1.По мнению автора, при наличии пары «открытый текст - шифртекст» наиболеебыстрый способ определить ключ - это полный перебор всего ключевого пространствамощности n!, т. е. выбор перестановки, шифрование и сравнение результата с шифр-текстом.Основой для такого вывода является следующее. Введем обозначение f = fCTn о - ■ - оo fCT1; тогда уравнение (2) записывается в виде f оm = c mod h. Заметим, что приводитьпо модулю h(x) можно многочлен m(x) и конечный результат композиции, а многочленf нельзя, так как если мы производим вычисления в фактор-кольце F[x]/(h(x)),то композиция, в отличие от операции умножения, не является корректно определеннойв фактор-кольце операцией. Для того чтобы найти коэффициенты многочлена f ,необходимо найти корни из поля F многочлена степени порядка exp(exp n), что дажедля небольших значений числа n невозможно. Попытаться как-то разделить исходнуюзадачу на части также не представляется возможным.По мнению автора, некоммутативная алгебра полиномов слабо изучена, но имеетпри этом важные приложения. Это позволяет надеяться, что изучение этой алгебрыи предлагаемой криптосистемы представляет некоторый научный интерес.

Скачать электронную версию публикации