Исследование классических криптоподсистем на линейных кодах в задачах кодирования и декодирования данных информационно-управляющих систем

УДК 004.9:622.276

ИССЛЕДОВАНИЕ КЛАССИЧЕСКИХ КРИПТОПОДСИСТЕМ НА ЛИНЕЙНЫХ КОДАХ В ЗАДАЧАХ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ДАННЫХ ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ

С.Н. Шевцов, А.П. Титов, Ю.В. Гусаров, О.А. Калашникова

Аннотация. В статье представлен сравнительный анализ криптоподсистем на линейных кодах Х. Нидеррайтера и Р. МакЭлиса. Показано, что крипто-подсистемы на базе данных подходов обладают практически одинаковой стойкостью к информационным атакам. Однако если передача данных характеризуется низкой скоростью, то скорость кодирования (декодирования) в криптосистеме Х. Нидеррайтера выше по сравнению с системой Р. МакЭлиса.

Ключевые слова: информационно-управляющая система (ИУС), крипто-подсистема, криптостойкость, шифр, код.

THE STUDY OF CLASSICAL CRYPTOPROTECTED ON LINER CODES IN THE TASKS OF ENCODING AND DECODING DATA INFORMATION MANAGEMENT SYSTEMS

S.N. Shevtsov, A. P. Titov, Y.V. Gusarov, O.A. Kalashnikov

Abstract. The article presents a comparative analysis of Cryptoprotected on linear codes Niederreiter and McEliece. It is shown that cryptographic systems based on these approaches have almost the same resistance to information attacks. However, if the data transmission is characterized by low speed, the speed of encoding (decoding) in the cryptosystem of Niederreiter higher compared to the system McEliece, thus, the architecture of the cryptosystem of Niederreiter is more optimal.

Keywords: information management system, cryptographic system, cryptographic resistance, cipher, code.

Задача кодирования и декодирования линейных кодов передачи информации является актуальной при защите внутренних и внешних потоков данных информационно-управляющей системы (ИУС) [3]. #Р-полнота декодирования линейного кода доказана для двоичного и других алфавитов, что также справедливо как для ранговых, так и для метрик Хэмминга. Однако для некоторых семейств кодов эта за-

<4Ь

МФЮА МОСКОВСКИЙ ФИНАНСОВО-ЮРИДИЧЕСКИЙ УНИВЕРСИТЕТ

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

Данный подход позволяет построить однонаправленную функцию с возможностью прохода. Применение надежной криптосистемы в ИУС является актуальной и важной задачей по защите информационных потоков. Существует два основных типа криптосистем с открытым ключом, построенных на основе линейных кодов. Первый тип был исследован Нидеррайтером [15], второй тип был разработан МакЭлисом [14]. В первом случае декларируется проверочная матрица кода, а шифртекст представляются в виде ошибки, которая является открытым текстом. Во втором случае декларируется порождающая матрица кода, а шифртекстом является искусственно ошибочно искаженное кодовое слово.

Основное отличие криптосистемы Нидеррайтера является то, что алфавит открытого текста совпадает с алфавитом символов проверочной матрицы, при этом все элементы выбираются из одного базисного поля. В то же время, криптосистемы МакЭлиса используют подкоды над подполями, а базовое поле используется только для задания проверочной матрицы кода Гоппы.

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

Если порождающая и проверочная матрицы в системах Ни-деррайтера и МакЭлиса задаются одинаковым кодом, то стойкость обеих ИУС можно считать одинаковой. Для использования семейства линейных кодов в криптосистеме ИУС с открытыми ключами необходимо выполнение следующих условий. Первое, - семейство кодов должно содержать большое число значений, чтобы избежать

<4Ь

МОСКОВСКИЙ ФИНАНСОВО-ЮРИДИЧЕСКИЙ УНИВЕРСИТЕТ МФЮА

полного перебора по ним. Второе, - кодирование и декодирование для любого кода из семейства должны быть простыми, если доступно полное описание кодов ИУС. Декодирование кода, при отсутствии его полного описания, должно быть сложным. Указанные условия являются необходимыми, но недостаточными для построения стойкой криптосистемы ИУС. В свою очередь, Нидеррайтером были предложены обобщенные коды Рида-Соломона, а МакЭлисом -двоичные коды Гоппы.

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

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

Алгоритм классической криптосистемы МакЭлиса выглядит следующим образом. Закрытый ключ криптосистемы состоит из трех частей. Первая часть - это матрица С размером к х п, которая необходима для генерации кода Гоппы, исправляющего ^ ошибок. Вторая часть закрытого ключа представляет собой матрицу перестановок Р размером п х п. Третья часть - некоторая случайная невырожденная матрица S размером к х к. Матрица перестановок и матрица S необходимы для того, чтобы скрыть структуру открытого ключа.

<jb

МФЮА МОСКОВСКИЙ ФИНАНСОВО-ЮРИДИЧЕСКИЙ УНИВЕРСИТЕТ

Матрица Gpub является открытым ключом размером k х n, вычисляется из матриц закрытого ключа Gpub = SG'P. Из выражения для Gpub видно, что открытый ключ содержит информацию о закрытом ключе, тем не менее она удачно скрывается. Грубой атакой за приемлемое время невозможно осуществить восстановление закрытого ключа по заранее известному открытому.

При шифровании сообщения случайным образом выбирается невырожденный вектор z длины n над полем GF(2), для которого вес Хэмминга не превосходит t. Шифртекст вычисляется по формуле:

c = mG + z

На первом этапе при расшифровании вычисляется вектор С = cG-1.

Далее, на основе алгоритма декодирования кода Гоппы находится m', для которого метрика d;i(m 'G,c) не превосходит значения t. На итоговом этапе находится открытый текст, для которого зарегистрированный пользователь умножает полученный ml на матрицу обратную S.

Описанный алгоритм является достаточно высокоскоростным и функционирует на порядок быстрее, чем алгоритм RSA. Тем не менее, классический алгоритм МакЭлиса не особо распространен, поскольку размер открытого ключа является достаточно большим. Исходя из этого, длина шифртекста получается в два раза больше, чем открытый ключ, что вызывает сложности в процессе эксплуатации системы.

Матрица S необходима, для того чтобы разбить существующие связи так, чтобы матрица Gpub имела вид без определенных закономерностей. При этом код, определяемый матрицей Gpub будет случайным. Алгоритм декодирования произвольного кода дает возможность осуществить прямую атаку на систему МакЭлиса.

Исследованию вопросов декодирования случайного линейного кода посвящено большое количество работ. В работах [10; 4] представлены относительно результативные алгоритмы, для которых также получены оценки трудоемкости при использовании в крип-топодсистеме МакЭлиса.

Один из подходов к взлому криптоподсистемы МакЭлиса состоит в нахождении открытого сообщения по шифртексту. Пусть,

<4Ь

МОСКОВСКИЙ ФИНАНСОВО-ЮРИДИЧЕСКИЙ УНИВЕРСИТЕТ МФЮА

в соответствии с (1) шифрсообщение перехвачено. Выделив из полученного шифртекста порождающую матрицу, существует возможность декодирования по информационным совокупностям. По МакЭлису сложность алгоритма вычисляется по формуле

Например, пусть выбран код Гоппы с параметрическими значениями: п = 1024, к = 524, t = (ё - 1) / 2 = 50. При выполнении атаки способом перебора, параметры в примере подбираются так, что ее произвести невозможно. Существует порядка 10149 полиномов О(х), более 103 векторов упорядочения и порядка 10750 различных матриц S. При таких параметрах атака прямым способом за приемлемое время не возможна. В рассматриваемом примере сложность атаки составляет порядка Ж1 = 289 операций.

Известно несколько оптимизаций алгоритма МакЭлиса [11] для параметров кода п = 1024, к = 654, t =37. Вычислительная сложность атаки при этом составляет порядка Ж1 = 275.

В работах Е. Крука [8; 9] показана возможность значительно улучшить алгоритм восстановления открытого сообщения без знания ключей. В алгоритме, предлагаемом Е. Круком, количество операций для реализации атаки составляет

Для рассмотренного примера в алгоритме Крука количество операций составляет порядка Ж1 = 259. Данный результат является лучшим для рассмотренного вида атак на классическую криптопод-систему МакЭлиса. При отказе от декодирования всех сообщений, ограничившись относительно небольшой заметной их частью, возможно также понижение уровня сложности.

Еще одной идеей вскрытия криптоподсистемы МакЭлиса является восстановление закрытого ключа по открытому. Структурные

<j!b

МФЮА МОСКОВСКИЙ ФИНАНСОВО-ЮРИДИЧЕСКИЙ УНИВЕРСИТЕТ

атаки менее успешны, чем прямые, к тому же структурным атакам посвящено существенно меньше работ. В своей работе Гибсон показал, что если известен вектор упорядочения, то вскрытие крипто-подсистемы МакЭлиса может быть упрощено [5].

Другой способ получения секретных ключей основан на поиске для заранее известного кода Гоппы родительского ОРС-кода. Хейман и Шамир в своей работе [6] получили систему уравнений, которая позволяет найти секретный ключ, однако данная система имеет слишком много второстепенных решений. В работе [12] исследовались слабые ключи (ключи, для которых существует возможность восстановления проверочной матрицы кода), однако число данных ключей экспоненциально мало относительно их общего количества, из чего следует, что слабые ключи можно легко выделить на стадии генерации ключей криптоподсистемы.

Существуют варианты модификации криптоподсистемы МакЭлиса. Известна идея синтеза группы автоморфизмов кода Гоппы и добавление искусственные ошибки функции веса, превосходящей корректирующую способность кода [7]. При этом для дешифрования приходится решать задачу практически полного декодирования сообщения, вместо декодирования в пределах корректирующей способности, повышая стойкость системы к прямым атакам. Однако модификация является нестойкой и вскрытие представлено авторами [7].

Криптоподсистема Нидеррайтера, оказавшись не достаточно стойкой, была взломана. Аналитикам удалось вскрыть структуру закрытого ключа по открытому и подобрать матрицы S' и H', такие что H = S'H' [2].

cr L J

Опишем систему Нидеррайтера, построенную с помощью q-значного кода из множества Bq(n,d). Такой системе соответствует система МакЭлиса, в которой порождающие матрицы выбираются из набора A(n,n - d + 1).

Существует два вида распространенных атак на классический алгоритм Нидеррайтера. Первый - восстановление открытого сообщения абонента Y без использования секретного ключа абонентаX. В данном случае ключ составляют матрицы h, Г, D. Второй - вычисление секретного ключа абонента X с последующим вычислением открытых сообщений абонента Y.

cjb

МОСКОВСКИЙ ФИНАНСОВО-ЮРИДИЧЕСКИЙ УНИВЕРСИТЕТ МФЮА

Таким образом, криптоподсистемы ИУС на базе подходов Нидеррайтера и МакЭлиса обладают практически одинаковой стойкостью к информационным атакам, а для больших алфавитов эквивалентность криптосистем Нидеррайтера и МакЭлиса была доказана Г. Кабатянским [2].

Рассмотрим допущение, в котором две взаимно ортогональные матрицы А' - открытый ключ системы МакЭлиса, и В - открытый ключ системы Нидеррайтера. Пусть оба ключа известны, так как одна из другой может быть получена как решение линейной системы алгебраических уравнений А' • (В ')Т= 0, то есть с помощью не более чем О(п3) операций.

При известном состоянии с = е(В')Т легко получить вектор b = aA' + е с некоторым вектором a G Ff таким, что с = Ь(В')Т, для этого надо найти какое-либо решение b уравнения

Пусть вектор b - шифртекст в криптосистеме МакЭлиса. Предположим, что для системы МакЭлиса существует криптографическая атака со сложностью Известен алгоритм вычисления вектора a -конфиденциальная информация в системе МакЭлиса. Тогда вектор е (конфиденциальная информация в системе Нидеррайтера), очевидно, представляется в виде е = b - aA', то есть сложность определения е совпадает со сложностью определения a.

Пусть теперь для системы Нидеррайтера известна криптографическая атака со сложностью Q. Используем в качестве шифртекста в системе Нидеррайтера вектор

где Ь — шифртекст системы МакЭлиса. Теперь можно вычислить вектор ошибок е, а затем и вектор а, который является единственным решением линейного уравнения

Две рассматриваемые криптосистемы различаются скоростью передачи. Если код характеризуется низкой скоростью, то есть к/п -малое число, то скорость передачи в системе Никдеррайтера всегда

С = х(В')Т

С = Ь(В')Т = (aA' + е)(В')Т = е(В')Т,

yA' = b - е

<4Ь

МФЮА МОСКОВСКИЙ ФИНАНСОВО-ЮРИДИЧЕСКИЙ УНИВЕРСИТЕТ

выше по сравнению с системой МакЭлиса. Поэтому архитектуру криптосистемы Нидеррайтера можно назвать более оптимальной.

Шифрование сообщения е в системе Нидеррайтера состоит в вычислении его состояния, шифрование можно произвести за О((п - к)п) операций. Сложность расшифрования равна сложности восстановления вектора е и определяется, в основном, трудоемкостью алгоритма декодирования (п,А) кода и не превосходит О(п3) операций.

Отметим также ряд достоинств системы Никдеррайтера. В криптосистеме Нидеррайтера в качестве открытой информации выступают векторы е веса 1 и менее. Для ее реализации необходимо иметь алгоритм, который отображает множество всех г-значных векторов длины 5 в множество ю^, векторов длины п и веса не больше Причем

5 < = [^Х(Ы)(Г - 1)1

1=0

- логарифм числа возможных сообщений.

Система Никдеррайтера определяется как проверочной матрицей В', так и ортогональной к ней порождающей матрицей А'. Поэтому открытым ключом этой системы следует считать матрицу, которая содержит меньшее число строк, хотя шифртекст с = еВ' на практике обычно строится с помощью матрицы В'[1].

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

Библиографический список

1. Самохина М.А. Криптоанализ систем, основанных на линейных кодах // Проблемы информационной безопасности. Компьютерные системы. 2008. № 2.

2. Сидельников В.М., Шестаков С.О. О системе шифрования, основанной на обобщенных кодах Рида-Соломона. М., 1992. Т. 3. Вып. 3.

3. Титов А.П., Шевцов С.Н., Греков А.Ю. Исследование структуры адаптивного управления безопасностью информационно-управляющих

МОСКОВСКИЙ ФИНАНСОВО-ЮРИДИЧЕСКИЙ УНИВЕРСИТЕТ МФЮА

систем // Вестник Московского финансово-юридического университета МФЮА. 2017. № 2.

4. CantcautA., ChabaudF. A New Algorithm For Finding Minimum-Weight Words in a Linear Code: Application to MCEliece's Cryptosystem and to Narrow-Sense BCII Codes of Length 511 // IEEE Trans. Inform. Theory. 1998. V 44.

5. Gibson J.K. The Security of the Gabidulin Public Key Cryptosystem. Advances in Cryptology - EUROCRYPT'96 / еd. By U.M. Maurer. LNCS 1070. 1996.

6. Heiman R., Shamir A. On the Security of Cryptosystems Based on Linear Error-Correcting Codes // Applied Mathematics. Weizmann Institute of Science. Rchovot. Israel. 1987.

7. Kobara K., Imai H. New Chosen-Plaintext Attacks on the One- Wayness of the Modified McEliece PKC Proposed at Asiacrypt-2000 // Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems. PKC-02 / еЛ by D. Naccache, P. Paillier. LNCS 2274. 2002.

8. KrukE.A. Code Based Public Key Cryptosystems. Prospective Methods for Telecommunication and Integrated Communication Systems. Moscow, 1992.

9. Kruk E.A. Bounds for Decoding Complexity of Any Linear Block Code // Problem Information Transm. 1989. V. 25. № 3.

10. Lee R.I., Brickell E.F. An Observation of the McEliece Public Key Cryptosystem // Advances in Cryptology - EUROCRYPT'88.

11. Lee R.I., Brickell E.F. An Observation of the McEliece Public Key Cryptosystem // Advances in Cryptology - EUROCRYPT'88.

12. Loidreau P., Sendrier N. Weak Keys in McEliece Public-Key Cryptosystem // IEEE Trans. Inform. Theory. 2001. V. 47, 3.

13. Loidreau Р. Strengthening McEliece Cryptosystem // Advances in Cryptology - ASIACRYPT-2000 / еd. by T. Okamoto. LNCS 1976. 2000.

14 McEliece R.J. A Public-Key Cryptosystem Based on ALgebraic Coding Theory. DGN Progress Report 42-44. Jet Propulsi on Lab. Pasadena. CA. Janary-Febrary. 1978.

15 McEliece R.J. A public Key Cryptosystem Based on Algebraic Coding Theory // JPL DSL Progress Report 42-44. 1978. Jan-Feb.

16 Niederreiter H. Knapsack-Type Cryptosystem and Algebraic Coding Theory // Probl. Control and Inform. Theory. 1986. V 15.

С.Н. Шевцов

кандидат технических наук

доцент кафедры информационных технологий

Московского финансово-юридического университета МФЮА

E-mail: sshvc@hotmail.com