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

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

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

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

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

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

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

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

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

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

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$. Эта битовая последовательность шифруется следующим образомШаблон:Sfn:

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

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

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

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

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

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

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

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

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

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

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

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 итерации для получения положительного результата)Шаблон:Sfn. Иными словами, возможно найти оператор перестановки, использовавшийся для генерации закрытого ключа.

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

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

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

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

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

	$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$ порождающих матриц. Иными словами, публичный ключ в такой системе рассчитывается как $|A{G}_1,A{G}_2\dots ,A{G}_u|P$, где первый множитель - составная матрица размером $un\times k$.

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

См. также

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

Литература

• Шаблон:Source
• Шаблон:Source
• Шаблон:Source
• Шаблон:Source