13-06-2023
Криптосистема Сидельникова (Мак-Элиса-Сидельникова) — криптографическая система с открытым ключом, основанная на криптосистеме McEliece. Была предложена математиком, академиком Академии криптографии РФ Владимиром Михайловичем Сидельниковым в 1994 году[1]. Сидельников предложил данную криптосистему, поскольку для системы McEliece к тому времени уже были найдены алгоритмы, взламывающие её за полиномиальное, либо субэкспоненциальное время работы[2].
Алгоритм, используемый в криптосистеме Сидельникова, основан на сложности декодирования кода Рида-Маллера[1]. Порождающая матрица такого кода имеет размеры где
При использовании кода Рида-Маллера можно выбирать ключи меньшего размера, чем в криптосистеме McEliece; а также добиться высокой скорости расшифровки, так как для данного кода существуют быстрые алгоритмы декодирования[2]. Более того, криптосистема Сидельникова, как и любая система, построенная на линейных кодах, не является уязвимой к атакам, которые станут возможны с появлением квантового компьютера.
Реального применения данная криптосистема не нашла, так как, несмотря на некоторые улучшения по сравнению с системой McEliece, была взломана в 2007 году.
В некоторых источниках упоминается как криптосистема Мак-Элиса-Сидельникова.
Система Сидельникова, как и все асимметричные криптосистемы, использует открытый и закрытый ключи. Открытый ключ используется для шифрования сообщений и не является секретным. Закрытый ключ используется для расшифровки и должен быть известен только стороне, которой предназначаются зашифрованные сообщения. Задача владельца закрытого ключа заключается в том, чтобы замаскировать порождающую матрицу , зная которую, криптоаналитик сумеет восстановить исходное сообщение. Для этих целей используются матрицы и , описанные далее в алгоритме. Вычисления всюду происходят в -мерном подпространстве пространства .
Процесс генерации ключей происходит следующим образом[1]:
Для кодирования при помощи линейных кодов (в частности, при кода помощи Рида-Маллера), необходимо представить информационное сообщение в виде последовательности из и . Эта битовая последовательность шифруется следующим образом[1]:
Криптограмма, полученная по общедоступному каналу, представляет из себя вектор , где - информационное сообщение. Для расшифровки криптограммы[2]:
Сидельников в одной из своих статей показал несостоятельность криптосистемы McEliece на основе кодов Рида-Соломона, найдя способ взлома такой системы за полиномиальное время[3]. В связи с этим, а также, желая устранить некоторые недостатки системы McEliece, Сидельников предложил и описал криптосистему, построенную на кодах Рида-Маллера[1].
Несмотря на то что Сидельников считал свою криптосистему надежной, в 2007 году криптографы Л. Миндер и А. Шокроллахи изобрели весьма оригинальный способ взломать систему Сидельникова. В основе метода лежало утверждение о том, что для любого (здесь мы подходим к коду, как к линейному пространству, натянутому на базис из кодовых векторов)[2].
Обозначим за код Рида-Маллера после применения к нему оператора перестановки. Тогда, найдя каким-либо способом перестановочную матрицу, которая использовалась при генерации закрытого ключа, можно, вычислив матрицу (это получится сделать, так как для любой перестановочной матрицы существует обратная), найти матрицу ; поскольку открытым ключом в системе Сидельникова является матрица , умножив которую на , можно найти [2].
Остается лишь вычислить матрицу . Для решения данной задачи матрицы и записываются рядом, и с помощью линейных преобразований строк матрица приводится к матрице , которая для данного кода Рида-Маллера заранее известна. В итоге имеется цепочка преобразований , что следует из элементарых сведений о линейной алгебре. Вообще говоря, матрицу можно и не искать, так как достаточно легко показать, что матрицы и порождают один и тот же код Рида-Маллера[2].
Миндер и Шокроллахи в своей статье предложили следующий способ поиска перестановочной матрицы:
При временном анализе алгоритма за входной параметр принимается число , являющееся размерностью кодового слова. Порядок кода полагается малым в сравнении с , так как код Рида-Маллера при больших порядках достаточно бесполезен в плане практического применения (в частности, число исправляемых им ошибок при увеличении , становится очень мало). Наиболее вычислительно сложной частью всего алгоритма является поиск кодовых слов с минимальным весом, так как все остальные операции выполняются за заведомо полиномиальное время[2].
Асимптотическая оценка сложности алгоритма: . Для больших порядков кода задача становится вычислительно сложной, так как существенно возрастает время, затрачиваемое на поиск кодовых слов с минимальным весом[2].
Миндером и Шокроллахи была проведена серия экспериментов на компьютере с тактовой частотой 2,4 Ггц[2]. Результаты можно видеть в таблице:
Время работы при является результатом погрешности в реализации алгоритма.
Сидельников также предложил усиленный вариант своей криптосистемы с использованием порождающих матриц. Иными словами, публичный ключ в такой системе рассчитывается как , где первый множитель - составная матрица размером .
Миндер и Шокроллахи в своей статье показали, что взлом усовершенствованной таким образом криптосистемы по сложности не отличается от взлома криптосистемы с единственной порождающией матрицей, так как разбиение кода на блоки оказывается весьма простой задачей[2].