Русская Википедия:Криптосистема Сидельникова
Криптосистема Сидельникова (Мак-Элиса—Сидельникова) — криптографическая система с открытым ключом, основанная на криптосистеме McEliece. Была предложена математиком, академиком Академии криптографии РФ Владимиром Михайловичем Сидельниковым в 1994 годуШаблон:Sfn. Сидельников предложил данную криптосистему, поскольку для системы McEliece к тому времени уже были найдены алгоритмы, взламывающие её за полиномиальное, либо субэкспоненциальное время работыШаблон:Sfn.
Алгоритм, используемый в криптосистеме Сидельникова, основан на сложности декодирования кода Рида-МаллераШаблон:Sfn. Порождающая матрица такого кода имеет размеры <math>k \times n,</math> где
- <math>k = \sum_{k=0}^r C_m^k, n = 2^m</math>
При использовании кода Рида-Маллера можно выбирать ключи меньшего размера, чем в криптосистеме McEliece; а также добиться высокой скорости расшифровки, так как для данного кода существуют быстрые алгоритмы декодированияШаблон:Sfn. Более того, криптосистема Сидельникова, как и любая система, построенная на линейных кодах, не является уязвимой для атак, которые станут возможны с появлением квантового компьютера.
Реального применения данная криптосистема не нашла, так как, несмотря на некоторые улучшения по сравнению с системой McEliece, была взломана в 2007 годуШаблон:Переход.
В некоторых источниках упоминается как криптосистема Мак-Элиса—Сидельникова.
Генерация ключа
Система Сидельникова, как и все асимметричные криптосистемы, использует открытый и закрытый ключи. Открытый ключ используется для шифрования сообщений и не является секретным. Закрытый ключ используется для расшифровки и должен быть известен только стороне, которой предназначаются зашифрованные сообщения. Задача владельца закрытого ключа заключается в том, чтобы замаскировать порождающую матрицу <math>G</math>, зная которую, криптоаналитик сумеет восстановить исходное сообщение. Для этих целей используются матрицы <math>P</math> и <math>A</math>, описанные далее в алгоритме. Вычисления всюду происходят в <math>k</math>-мерном подпространстве пространства <math>\mathbb{F}_2^n</math>.
Процесс генерации ключей происходит следующим образомШаблон:Sfn:
- Выбирается код Рида-Маллера с определёнными параметрами <math>r</math> и <math>m</math> (где <math>r</math> - порядок кода, а <math>2^m</math> - длина кодового слова).
- Генерируется случайная <math>n \times n</math> перестановочная матрица <math>P</math>.
- Генерируется случайная невырожденная <math>k \times k</math> матрица <math>A</math>.
- Вычисляется матрица <math>E = AGP</math>.
- Матрица <math>E</math> и число исправляемых кодом ошибок <math>t</math> образуют открытый ключ, а матрицы <math>(A, G, P)</math> — закрытый ключ криптосистемы.
Шифрование
Для кодирования при помощи линейных кодов (в частности, при помощи кода Рида-Маллера), необходимо представить информационное сообщение <math>m</math> в виде последовательности из <math>0</math> и <math>1</math>. Эта битовая последовательность шифруется следующим образомШаблон:Sfn:
- Вычисляется вспомогательный вектор <math>\mathbf a = mE</math>.
- Случайным образом генерируется вектор ошибок <math>\mathbf e</math> размерности <math>n</math>, содержащий единицы не более чем в <math>t = 2^{m-r-1} - 1</math> разрядах.
- Передаваемый шифртекст вычисляется путём сложения ранее вычисленных векторов <math>\mathbf b = \mathbf a + \mathbf e</math>.
Расшифрование
Шифртекст, полученный по общедоступному каналу, представляет собой вектор <math>\mathbf b = mE + \mathbf e</math>, где <math>m</math> - информационное сообщение. Для расшифровки криптограммыШаблон:Sfn:
- Вычисляется вектор <math>\mathbf b' = \mathbf bP^{-1}</math>, являющийся вектором кода Рида-Маллера с порождающей матрицей <math>G</math>, искаженный не более, чем в <math>t</math> разрядах. Строго говоря, вектор ошибок <math>\mathbf e</math> при таком подходе также умножается на матрицу <math>P^{-1}</math>, но для алгоритма декодирования это не имеет значения, так как его вес при перестановках, очевидно, остается прежним.
- С помощью какого-либо алгоритма декодирования кода Рида-Маллера находится вектор <math>\mathbf a'</math>, удовлетворяющий условию <math>\mathbf b' = \mathbf a'G + \mathbf e</math>.
- Вычисляется информационное сообщение <math>m = \mathbf a'A^{-1}</math>.
Атака на криптосистему
Сидельников в одной из своих статей показал несостоятельность криптосистемы McEliece на основе кодов Рида-Соломона, найдя способ взлома такой системы за полиномиальное времяШаблон:Sfn. В связи с этим, а также, желая устранить некоторые недостатки системы McEliece, Сидельников предложил и описал криптосистему, построенную на кодах Рида-МаллераШаблон:Sfn.
Несмотря на то что Сидельников считал свою криптосистему надежной, в 2007 году криптографы Л. Миндер и А. Шокроллахи изобрели весьма оригинальный способ взломать систему Сидельникова. В основе метода лежало утверждение о том, что <math>RM(0, m) \subset RM(1, m) \subset \ldots \subset RM(m, m)</math> для любого <math>m</math> (здесь мы подходим к коду, как к линейному пространству, натянутому на базис из кодовых векторов)Шаблон:Sfn.
Обозначим за <math>RM(r, m)^\delta</math> код Рида-Маллера после применения к нему оператора перестановки. Тогда, найдя каким-либо способом перестановочную матрицу, которая использовалась при генерации закрытого ключа, можно, вычислив матрицу <math>P^{-1}</math> (это получится сделать, так как для любой перестановочной матрицы существует обратная), найти матрицу <math>G^* = AG</math>; поскольку открытым ключом в системе Сидельникова является матрица <math>AGP</math>, умножив которую на <math>P^{-1}</math>, можно найти <math>G^*</math>Шаблон:Sfn.
Остается лишь вычислить матрицу <math>A</math>. Для решения данной задачи матрицы <math>G^*</math> и <math>E</math> записываются рядом, и с помощью линейных преобразований строк матрица <math>G^*</math> приводится к матрице <math>G</math>, которая для данного кода Рида-Маллера заранее известна. В итоге имеется цепочка преобразований <math>(G^*|E) \rightarrow (G|A^{-1})</math>, что следует из элементарых сведений о линейной алгебре. Вообще говоря, матрицу <math>A</math> можно и не искать, так как достаточно легко показать, что матрицы <math>AG</math> и <math>G</math> порождают один и тот же код Рида-МаллераШаблон:Sfn.
Сущность атаки
Миндер и Шокроллахи в своей статье предложили следующий способ поиска перестановочной матрицы:
- Ищутся кодовые векторы кода <math>RM(r, m)^\delta</math>, которые с очень большой вероятностью принадлежат коду <math>RM(r - 1, m)^\delta</math>. Находится достаточное количество таких векторов, чтобы построить базис пространства <math>RM(r - 1, m)^\delta</math>. Поиск базируется на утверждении о том, что код Рида-Маллера порядка <math>r</math> является подпространством того же кода порядка <math>r - 1</math>, а также на свойствах кодовых векторов с минимальным весом.
- Повторяется шаг 1 до получения кода <math>RM(1, m)^\delta</math>.
- Переставляя определённым образом столбцы <math>RM(1, m)^\delta</math>, возможно отыскать исходный код <math>RM(1, m)</math> с вероятностью более <math>1/2</math> (потребуется максимум 2 итерации для получения положительного результата)Шаблон:Sfn. Иными словами, возможно найти оператор перестановки, использовавшийся для генерации закрытого ключа.
Временные оценки алгоритма взлома
При временном анализе алгоритма за входной параметр принимается число <math>n = 2^m</math>, являющееся размерностью кодового слова. Порядок кода <math>r</math> полагается малым в сравнении с <math>m</math>, так как код Рида-Маллера при больших порядках достаточно бесполезен в плане практического применения (в частности, число исправляемых им ошибок при увеличении <math>r</math>, становится очень мало). Наиболее вычислительно сложной частью всего алгоритма является поиск кодовых слов с минимальным весом, так как все остальные операции выполняются за заведомо полиномиальное времяШаблон:Sfn.
Асимптотическая оценка сложности алгоритма: <math>O(poly(n))\cdot e^{O(poly(log(n)))}</math>. Для больших порядков кода <math>r</math> задача становится вычислительно сложной, так как существенно возрастает время, затрачиваемое на поиск кодовых слов с минимальным весомШаблон:Sfn.
Экспериментальное время работы
Миндером и Шокроллахи была проведена серия экспериментов на компьютере с тактовой частотой 2,4 ГгцШаблон:Sfn. Результаты можно видеть в таблице:
| <math>r = 2</math> | <math>r = 3</math> | <math>r = 4</math> | |
|---|---|---|---|
| <math>m = 5~(n = 32)</math> | <math>< 0{,}01c</math> | ||
| <math>m = 6~(n = 64)</math> | <math>< 0{,}01c</math> | ||
| <math>m = 7~(n = 128)</math> | <math>0{,}02c</math> | <math>5{,}261c</math> | |
| <math>m = 8~(n = 256)</math> | <math>0{,}081c</math> | <math>2{,}059c</math> | |
| <math>m = 9~(n = 512)</math> | <math>0{,}0448c</math> | <math>3{,}462c</math> | <math>176{,}914c</math> |
| <math>m = 10~(n = 1024)</math> | <math>2{,}46c</math> | <math>26{,}6c</math> | <math>82197{,}4c</math> |
| <math>m = 11~(n = 2048)</math> | <math>18{,}34c</math> | <math>1192{,}71c</math> | <math>-</math> |
Время работы при <math>r = 3, m = 7</math> является результатом погрешности в реализации алгоритма.
Обобщенная система Сидельникова
Сидельников также предложил усиленный вариант своей криптосистемы с использованием <math>u</math> порождающих матриц. Иными словами, публичный ключ в такой системе рассчитывается как <math>|AG_1, AG_2\ldots, AG_u|P</math>, где первый множитель - составная матрица размером <math>un \times k</math>.
Миндер и Шокроллахи в своей статье показали, что взлом усовершенствованной таким образом криптосистемы по сложности не отличается от взлома криптосистемы с единственной порождающией матрицей, так как разбиение кода на блоки оказывается весьма простой задачейШаблон:Sfn.
См. также
Примечания
Литература
Шаблон:^ Шаблон:Добротная статья
