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

Криптосистема Сидельникова (Мак-Элиса—Сидельникова) — криптографическая система с открытым ключом, основанная на криптосистеме McEliece. Была предложена математиком, академиком Академии криптографии РФ Владимиром Михайловичем Сидельниковым в 1994 году^[1]. Сидельников предложил данную криптосистему, поскольку для системы McEliece к тому времени уже были найдены алгоритмы, взламывающие её за полиномиальное, либо субэкспоненциальное время работы^[2].

Алгоритм, используемый в криптосистеме Сидельникова, основан на сложности декодирования кода Рида-Маллера^[1]. Порождающая матрица такого кода имеет размеры $k\times n,$ где

k=\sum _{k=0}^{r}C_{m}^{k},n=2^{m}

При использовании кода Рида-Маллера можно выбирать ключи меньшего размера, чем в криптосистеме McEliece; а также добиться высокой скорости расшифровки, так как для данного кода существуют быстрые алгоритмы декодирования^[2]. Более того, криптосистема Сидельникова, как и любая система, построенная на линейных кодах, не является уязвимой для атак, которые станут возможны с появлением квантового компьютера.

Реального применения данная криптосистема не нашла, так как, несмотря на некоторые улучшения по сравнению с системой McEliece, была взломана в 2007 году^>>>.

В некоторых источниках упоминается как криптосистема Мак-Элиса—Сидельникова.

Генерация ключа править

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

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

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

Шифрование править

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

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

Расшифрование править

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

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

Атака на криптосистему править

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

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

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

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

Сущность атаки править

Миндер и Шокроллахи в своей статье предложили следующий способ поиска перестановочной матрицы:

Ищутся кодовые векторы кода $RM(r,m)^{\delta }$ , которые с очень большой вероятностью принадлежат коду $RM(r-1,m)^{\delta }$ . Находится достаточное количество таких векторов, чтобы построить базис пространства $RM(r-1,m)^{\delta }$ . Поиск базируется на утверждении о том, что код Рида-Маллера порядка $r$ является подпространством того же кода порядка $r-1$ , а также на свойствах кодовых векторов с минимальным весом.
Повторяется шаг 1 до получения кода $RM(1,m)^{\delta }$ .
Переставляя определённым образом столбцы $RM(1,m)^{\delta }$ , возможно отыскать исходный код $RM(1,m)$ с вероятностью более $1/2$ (потребуется максимум 2 итерации для получения положительного результата)^[2]. Иными словами, возможно найти оператор перестановки, использовавшийся для генерации закрытого ключа.

Временные оценки алгоритма взлома править

При временном анализе алгоритма за входной параметр принимается число $n=2^{m}$ , являющееся размерностью кодового слова. Порядок кода $r$ полагается малым в сравнении с $m$ , так как код Рида-Маллера при больших порядках достаточно бесполезен в плане практического применения (в частности, число исправляемых им ошибок при увеличении $r$ , становится очень мало). Наиболее вычислительно сложной частью всего алгоритма является поиск кодовых слов с минимальным весом, так как все остальные операции выполняются за заведомо полиномиальное время^[2].

Асимптотическая оценка сложности алгоритма: $O(poly(n))\cdot e^{O(poly(log(n)))}$ . Для больших порядков кода $r$ задача становится вычислительно сложной, так как существенно возрастает время, затрачиваемое на поиск кодовых слов с минимальным весом^[2].

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

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

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

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

Обобщенная система Сидельникова править

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

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

См. также править

Примечания править

↑ ¹ ² ³ ⁴ ⁵ Chizhov, Borodin, 2013.
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ Minder, Shokrollahi, 2007.
↑ Сидельников, Шестаков, 1992.

Литература править

Сидельников В. М., Шестаков С. О. О системе шифрования, построенной на основе обобщенных кодов Рида–Соломона // Дискретная математика — 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 (англ.) // Прикладная дискретная математика. Приложение — TSU, 2013. — Iss. 6. — P. 48—49. — ISSN 2226-308X; 2411-2313

[_51464d5b21273037-1] ¹ ² ³ ⁴ ⁵ Chizhov, Borodin, 2013.

[_7a358e378edd199d-2] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ Minder, Shokrollahi, 2007.

[_5e51e3c54261368b-3] Сидельников, Шестаков, 1992.

[1]

[2]

[3]