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

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

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

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

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

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

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

Система Сидельникова, как и все асимметричные криптосистемы, использует открытый и закрытый ключи. Открытый ключ используется для шифрования сообщений и не является секретным. Закрытый ключ используется для расшифровки и должен быть известен только стороне, которой предназначаются зашифрованные сообщения. Задача владельца закрытого ключа заключается в том, чтобы замаскировать порождающую матрицу , зная которую, криптоаналитик сумеет восстановить исходное сообщение. Для этих целей используются матрицы и , описанные далее в алгоритме. Вычисления всюду происходят в -мерном подпространстве пространства .

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

  1. Выбирается код Рида-Маллера с определенными параметрами и (где - порядок кода, а - длина кодового слова).
  2. Генерируется случайная перестановочная матрица .
  3. Генерируется случайная невырожденная матрица .
  4. Вычисляется матрица .
  5. Матрица и число исправляемых кодом ошибок образуют открытый ключ, а матрицы закрытый ключ криптосистемы.

Шифрование

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

  1. Вычисляется вспомогательный вектор .
  2. Случайным образом генерируется вектор ошибок размерности , содержащий единицы не более чем в разрядах.
  3. Передаваемый шифртекст вычисляется путём сложения ранее вычисленных векторов .

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

Шифртекст, полученный по общедоступному каналу, представляет из себя вектор , где - информационное сообщение. Для расшифровки криптограммы[2]:

  1. Вычисляется вектор , являющийся вектором кода Рида-Маллера с порождающей матрицей , искаженный не более, чем в разрядах. Строго говоря, вектор ошибок при таком подходе также умножается на матрицу , но для алгоритма декодирования это не имеет значения, так как его вес при перестановках, очевидно, остается прежним.
  2. С помощью какого-либо алгоритма декодирования кода Рида-Маллера находится вектор , удовлетворяющий условию .
  3. Вычисляется информационное сообщение .

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

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

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

Обозначим за код Рида-Маллера после применения к нему оператора перестановки. Тогда, найдя каким-либо способом перестановочную матрицу, которая использовалась при генерации закрытого ключа, можно, вычислив матрицу (это получится сделать, так как для любой перестановочной матрицы существует обратная), найти матрицу ; поскольку открытым ключом в системе Сидельникова является матрица , умножив которую на , можно найти [2].

Остается лишь вычислить матрицу . Для решения данной задачи матрицы и записываются рядом, и с помощью линейных преобразований строк матрица приводится к матрице , которая для данного кода Рида-Маллера заранее известна. В итоге имеется цепочка преобразований , что следует из элементарых сведений о линейной алгебре. Вообще говоря, матрицу можно и не искать, так как достаточно легко показать, что матрицы и порождают один и тот же код Рида-Маллера[2].

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

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

  1. Ищутся кодовые векторы кода , которые с очень большой вероятностью принадлежат коду . Находится достаточное количество таких векторов, чтобы построить базис пространства . Поиск базируется на утверждении о том, что код Рида-Маллера порядка является подпространством того же кода порядка , а также на свойствах кодовых векторов с минимальным весом.
  2. Повторяется шаг 1 до получения кода .
  3. Переставляя определенным образом столбцы , возможно отыскать исходный код с вероятностью более (потребуется максимум 2 итерации для получения положительного результата)[2]. Иными словами, возможно найти оператор перестановки, использовавшийся для генерации закрытого ключа.

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

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

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

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

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

Время работы при является результатом погрешности в реализации алгоритма.

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

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

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

См. также

Примечания

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.