Криптостойкость алгоритма умножения на элемент в поле Галуа

[Rokannon]

Пусть $f$ - некоторый неприводимый многочлен степени $n$ в кольце многочленов над $Z_2$. Факторизуя $Z_2[x]$ по этому многочлену, построим поле Галуа $GF(2^n)$. Пусть $k1$ и $k2$ - некоторый элемент данного поля и обратный к нему, соотвественно.

Используется такой алгоритм шифрования: $M$ - строка битов длины $n$. По ней строится многочлен $m$, являющийся элементом в построенном поле. $m$ умножается на $k1$ в этом поле и полученный многочлен "сворачивается" обратно в строку битов. Для дешифрации, очевидно, используется умножение на элемент $k2$.

Меня интересует следующий вопрос: Пусть противнику известно, что используется такой алгоритм шифрования. Может ли он по какому-то числу пар $(x,y)$, где $x$ - исходная строка битов, а $y$ соотвестенно её шифртекст, восстановить многочлен $f$ и элемент $k1$?

Меня не интересуют случаи, когда противник знает все пары $(x,y)$ и случай, когда противнки обладает парой $(0 ... 01,k1)$.

[Rokannon]

Пусть $f$ - некоторый неприводимый многочлен степени $n$ в кольце многочленов над $Z_2$. Факторизуя $Z_2[x]$ по этому многочлену, построим поле Галуа $GF(2^n)$. Пусть $k1$ и $k2$ - некоторый элемент данного поля и обратный к нему, соотвественно.

Используется такой алгоритм шифрования: $M$ - строка битов длины $n$. По ней строится многочлен $m$, являющийся элементом в построенном поле. $m$ умножается на $k1$ в этом поле и полученный многочлен "сворачивается" обратно в строку битов. Для дешифрации, очевидно, используется умножение на элемент $k2$.

Меня интересует следующий вопрос: Пусть противнику известно, что используется такой алгоритм шифрования. Может ли он по какому-то числу пар $(x,y)$, где $x$ - исходная строка битов, а $y$ соотвестенно её шифртекст, восстановить многочлен $f$ и элемент $k1$?

Предупреждение за дублирование тем! Темы объединены.

[Хорхе]

Умножаем один многочлен на другой, отнимаем единицу и раскладываем на множители. Насколько я помню (пусть меня старшие товарищи поправят, если что), раскладывать многочлены намного проще, чем числа, то есть там есть полиномиальные алгоритмы.

Короче говоря, плохое шифрование (возможно, я чего-то недопонимаю).

upd: sorry, плохо почитал. Но, собственно, если у нас есть пара сообщений и пара шифров, то уже можно надеяться на успех:

$$ \gathered m_1k_1 = n_1 \pmod f\\ m_2k_1 = n_2 \pmod f \endgathered $$

Ну и в итоге нам надо просто разложить $n_1m_2-n_2 m_1$ на множители (если это ноль, нам не повезло ).

[nn910]

Rokannon в сообщении #252570 писал(а):

Пусть $f$ - некоторый неприводимый многочлен степени $n$ в кольце многочленов над $Z_2$.

А сколько их вообще, неприводимых степени ровно n? По-моему,не более $2^{n-2}$

[Xaositect]

Конкретные $k$ и $f$ восстановить вряд ли можно, но по $n$ линейно-независимым $x_i$ и соотв. $y_i$ можно будет получить результат для любого $x$, потому что умножения на пост. многочлен - линейное преобразование.