Криптосистема Сидельникова

Система Сидельникова, как и все асимметричные криптосистемы, использует открытый и закрытый ключи. Открытый ключ используется для шифрования сообщений и не является секретным. Закрытый ключ используется для расшифровки и должен быть известен только стороне, которой предназначаются зашифрованные сообщения. Задача владельца закрытого ключа заключается в том, чтобы замаскировать порождающую матрицу ${\displaystyle G}$, зная которую, криптоаналитик сумеет восстановить исходное сообщение. Для этих целей используются матрицы ${\displaystyle P}$ и ${\displaystyle A}$, описанные далее в алгоритме. Вычисления всюду происходят в ${\displaystyle k}$-мерном подпространстве пространства ${\displaystyle \mathbb {F} _{2}^{n}}$.

Процесс генерации ключей происходит следующим образом[1]:

1. Выбирается код Рида-Маллера с определенными параметрами ${\displaystyle r}$ и ${\displaystyle m}$ (где ${\displaystyle r}$ - порядок кода, а ${\displaystyle 2^{m}}$ - длина кодового слова).
2. Генерируется случайная ${\displaystyle n\times n}$ перестановочная матрица ${\displaystyle P}$.
3. Генерируется случайная невырожденная ${\displaystyle k\times k}$ матрица ${\displaystyle A}$.
4. Вычисляется матрица ${\displaystyle E=AGP}$.
5. Матрица ${\displaystyle E}$ и число исправляемых кодом ошибок ${\displaystyle t}$ образуют открытый ключ, а матрицы ${\displaystyle (A,G,P)}$ — закрытый ключ криптосистемы.

Для кодирования при помощи линейных кодов (в частности, при помощи кода Рида-Маллера), необходимо представить информационное сообщение ${\displaystyle m}$ в виде последовательности из ${\displaystyle 0}$ и ${\displaystyle 1}$. Эта битовая последовательность шифруется следующим образом[1]:

1. Вычисляется вспомогательный вектор ${\displaystyle \mathbf {a} =mE}$.
2. Случайным образом генерируется вектор ошибок ${\displaystyle \mathbf {e} }$ размерности ${\displaystyle n}$, содержащий единицы не более чем в ${\displaystyle t=2^{m-r-1}-1}$ разрядах.
3. Передаваемый шифртекст вычисляется путём сложения ранее вычисленных векторов ${\displaystyle \mathbf {b} =\mathbf {a} +\mathbf {e} }$.

Шифртекст, полученный по общедоступному каналу, представляет из себя вектор ${\displaystyle \mathbf {b} =mE+\mathbf {e} }$, где ${\displaystyle m}$ - информационное сообщение. Для расшифровки криптограммы[2]:

1. Вычисляется вектор ${\displaystyle \mathbf {b} '=\mathbf {b} P^{-1}}$, являющийся вектором кода Рида-Маллера с порождающей матрицей ${\displaystyle G}$, искаженный не более, чем в ${\displaystyle t}$ разрядах. Строго говоря, вектор ошибок ${\displaystyle \mathbf {e} }$ при таком подходе также умножается на матрицу ${\displaystyle P^{-1}}$, но для алгоритма декодирования это не имеет значения, так как его вес при перестановках, очевидно, остается прежним.
2. С помощью какого-либо алгоритма декодирования кода Рида-Маллера находится вектор ${\displaystyle \mathbf {a} '}$, удовлетворяющий условию ${\displaystyle \mathbf {b} '=\mathbf {a} 'G+\mathbf {e} }$.
3. Вычисляется информационное сообщение ${\displaystyle m=\mathbf {a} 'A^{-1}}$.

Сидельников в одной из своих статей показал несостоятельность криптосистемы McEliece на основе кодов Рида-Соломона, найдя способ взлома такой системы за полиномиальное время[3]. В связи с этим, а также, желая устранить некоторые недостатки системы McEliece, Сидельников предложил и описал криптосистему, построенную на кодах Рида-Маллера[1].

Несмотря на то что Сидельников считал свою криптосистему надежной, в 2007 году криптографы Л. Миндер и А. Шокроллахи изобрели весьма оригинальный способ взломать систему Сидельникова. В основе метода лежало утверждение о том, что ${\displaystyle RM(0,m)\subset RM(1,m)\subset \ldots \subset RM(m,m)}$ для любого ${\displaystyle m}$ (здесь мы подходим к коду, как к линейному пространству, натянутому на базис из кодовых векторов)[2].

Обозначим за ${\displaystyle RM(r,m)^{\delta }}$ код Рида-Маллера после применения к нему оператора перестановки. Тогда, найдя каким-либо способом перестановочную матрицу, которая использовалась при генерации закрытого ключа, можно, вычислив матрицу ${\displaystyle P^{-1}}$ (это получится сделать, так как для любой перестановочной матрицы существует обратная), найти матрицу ${\displaystyle G^{*}=AG}$; поскольку открытым ключом в системе Сидельникова является матрица ${\displaystyle AGP}$, умножив которую на ${\displaystyle P^{-1}}$, можно найти ${\displaystyle G^{*}}$[2].

Остается лишь вычислить матрицу ${\displaystyle A}$. Для решения данной задачи матрицы ${\displaystyle G^{*}}$ и ${\displaystyle E}$ записываются рядом, и с помощью линейных преобразований строк матрица ${\displaystyle G^{*}}$ приводится к матрице ${\displaystyle G}$, которая для данного кода Рида-Маллера заранее известна. В итоге имеется цепочка преобразований ${\displaystyle (G^{*}|E)\rightarrow (G|A^{-1})}$, что следует из элементарых сведений о линейной алгебре. Вообще говоря, матрицу ${\displaystyle A}$ можно и не искать, так как достаточно легко показать, что матрицы ${\displaystyle AG}$ и ${\displaystyle G}$ порождают один и тот же код Рида-Маллера[2].

Экспериментальное время работы

Миндером и Шокроллахи была проведена серия экспериментов на компьютере с тактовой частотой 2,4 Ггц[2]. Результаты можно видеть в таблице:

	${\displaystyle r=2}$	${\displaystyle r=3}$	${\displaystyle r=4}$
${\displaystyle m=5~(n=32)}$	${\displaystyle <0{,}01c}$
${\displaystyle m=6~(n=64)}$	${\displaystyle <0{,}01c}$
${\displaystyle m=7~(n=128)}$	${\displaystyle 0{,}02c}$	${\displaystyle 5{,}261c}$
${\displaystyle m=8~(n=256)}$	${\displaystyle 0{,}081c}$	${\displaystyle 2{,}059c}$
${\displaystyle m=9~(n=512)}$	${\displaystyle 0{,}0448c}$	${\displaystyle 3{,}462c}$	${\displaystyle 176{,}914c}$
${\displaystyle m=10~(n=1024)}$	${\displaystyle 2{,}46c}$	${\displaystyle 26{,}6c}$	${\displaystyle 82197{,}4c}$
${\displaystyle m=11~(n=2048)}$	${\displaystyle 18{,}34c}$	${\displaystyle 1192{,}71c}$	${\displaystyle -}$

Время работы при ${\displaystyle r=3,m=7}$ является результатом погрешности в реализации алгоритма.

Сидельников также предложил усиленный вариант своей криптосистемы с использованием ${\displaystyle u}$ порождающих матриц. Иными словами, публичный ключ в такой системе рассчитывается как ${\displaystyle |AG_{1},AG_{2}\ldots ,AG_{u}|P}$, где первый множитель - составная матрица размером ${\displaystyle un\times k}$.

Миндер и Шокроллахи в своей статье показали, что взлом усовершенствованной таким образом криптосистемы по сложности не отличается от взлома криптосистемы с единственной порождающией матрицей, так как разбиение кода на блоки оказывается весьма простой задачей[2].

• McEliece
• Криптосистема Нидеррайтера

• Сидельников В. М., Шестаков С. О. О системе шифрования, построенной на основе обобщенных кодов Рида–Соломона // Дискрет. матем. — 1992. — Т. 4, вып. 3. — С. 57—63. — ISSN 2305-3143; 0234-0860
• Сидельников В. М. Открытое шифрование на основе двоичных кодов Рида–Маллера // Дискрет. матем. — 1994. — Т. 4, вып. 3. — С. 191—207. — ISSN 2305-3143; 0234-0860
• Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov Cryptosystem (англ.) // Advances in Cryptology — EUROCRYPT 2007: 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, May 20-24, 2007. Proceedings / M. Naor — Springer Berlin Heidelberg, 2007. — P. 347—360. — ISBN 978-3-540-72539-8 — doi:10.1007/978-3-540-72540-4_20
• Chizhov I. V., Borodin M. A. The failure of McEliece PKC based on Reed-Muller codes (англ.) // Prikl. Diskr. Mat. Suppl. — Tomsk State University, 2013. — Iss. 6. — P. 48—49. — ISSN 2226-308X; 2411-2313