2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Криптостойкость алгоритма умножения на элемент в поле Галуа
Сообщение17.10.2009, 20:17 
Пусть $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)$.

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

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

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

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

 
 
 
 Re: Криптостойкость алгоритма умножения на элемент в поле Галуа
Сообщение17.10.2009, 21:19 
Аватара пользователя
Умножаем один многочлен на другой, отнимаем единицу и раскладываем на множители. Насколько я помню (пусть меня старшие товарищи поправят, если что), раскладывать многочлены намного проще, чем числа, то есть там есть полиномиальные алгоритмы.

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

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$ на множители (если это ноль, нам не повезло :) ).

 
 
 
 Re: Криптостойкость алгоритма умножения на элемент в поле Галуа
Сообщение18.10.2009, 10:03 
Rokannon в сообщении #252570 писал(а):
Пусть $f$ - некоторый неприводимый многочлен степени $n$ в кольце многочленов над $Z_2$.
А сколько их вообще, неприводимых степени ровно n? По-моему,не более $2^{n-2}$ :cry:

 
 
 
 Re: Криптостойкость алгоритма умножения на элемент в поле Галуа
Сообщение18.10.2009, 14:53 
Аватара пользователя
Конкретные $k$ и $f$ восстановить вряд ли можно, но по $n$ линейно-независимым $x_i$ и соотв. $y_i$ можно будет получить результат для любого $x$, потому что умножения на пост. многочлен - линейное преобразование.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group