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

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

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

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

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

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

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

Генерация ключа

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

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

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

Шифрование

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

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

Расшифрование

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

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

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

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

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

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

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

Сущность атаки

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

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

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

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

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

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

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

	$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$.

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

См. также

• 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 (англ.) // Прикладная дискретная математика. Приложение — TSU, 2013. — Iss. 6. — P. 48—49. — ISSN 2226-308X; 2411-2313