Спросить
Войти
НАУЧНО-ТЕХНИЧЕСКИИ ВЕСТНИК ИНФОРМАЦИОННЫХ ТЕХНОЛОГИИ, МЕХАНИКИ И ОПТИКИ июль-август 2020 Том 20 № 4 ISSN 2226-1494 http://ntv.itmo.ru/
SCIENTIFIC AND TECHNICAL JOURNAL OF INFORMATION TECHNOLOGIES, MECHANICS AND OPTICS July-August 2020 Vol. 20 No 4 ISSN 2226-1494 http://ntv.itmo.ru/en/
HHIIIDPMAPDHHhlX ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ
УДК 004.056.55 ёок 10.17586/2226-1494-2020-20-4-539-544
ЭФФЕКТИВНАЯ РЕАЛИЗАЦИЯ СОВРЕМЕННОЙ КРИПТОСИСТЕМЫ МАК-ЭЛИСА, ПОСТРОЕННОЙ НА ОБОБЩЕННЫХ (Ь, б)-КОДАХ
И.К. Носков^ С.В. Беззатеев^
а Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация
ь Санкт-Петербургский государственный университет аэрокосмического приборостроения (ГУАП), Санкт-Петербург,
Адрес для переписки: vanya170595@gmail.com
Информация о статье
Поступила в редакцию 28.05.20, принята к печати 29.06.20 Язык статьи — русский
Ссылка для цитирования: Носков И.К., Беззатеев С.В. Эффективная реализация современной криптосистемы Мак-Элиса, построенной на обобщенных (^, 0)-кодах // Научно-технический вестник информационных технологий, механики и оптики. 2020. Т. 20. № 4. С. 539-544. ёок 10.17586/2226-1494-2020-20-4-539-544
Аннотация
Предмет исследования. Исследованы способы и подходы к реализации современной криптосистемы Мак-Элиса, построенной на сепарабельных обобщенных (Ь, G)-кодах. Метод. На основе анализа известных общедоступных источников по реализации современной криптосистемы Мак-Элиса предложен метод, который позволяет использовать обобщенные (Ь, G)-коды с нумераторами степени больше или равной второй без использования расширенного поля. Основные результаты. Разработаны подходы к реализации современной криптосистемы Мак-Элиса, построенной на обобщенных (Ь, 6)-кодах, а именно: построение проверочной матрицы обобщенного (Ь, G)-кода, использующего сепарабельный многочлен Гоппы и нумераторы различных степеней; описан подход к реализации шифрования и расшифрования сообщений в современной криптосистеме Мак-Элиса; описан способ использования процедуры Ченя для нумераторов степени второй и выше без расширения поля. Практическая значимость. Предложенные способы можно применять в разработке криптографических систем, способных противостоять атакам с использованием квантовых компьютеров, что позволит обеспечить конфиденциальность данных, а также улучшить безопасность и производительность криптосистем. Областью применения результатов работы также могут являться аэрокосмические, автомобильные, железнодорожные, сетевые мультимедийные, телекоммуникационные и мобильные системы защиты информации. Ключевые слова
коды Гоппа, обобщенные (Ь, G)-коды, алгоритмы декодирования, современная криптосистема Мак-Элиса, се-парабельный полином
doi: 10.17586/2226-1494-2020-20-4-539-544
EFFECTIVE IMPLEMENTATION OF MODERN MCELIECE CRYPTOSYSTEM ON GENERALIZED (L, G)-CODES I.K. Noskova, S.V. Bezzateevab
a ITMO University, Saint Petersburg, 197101, Russian Federation
b Saint Petersburg State University of Aerospace Instrumentation (SUAI), Saint Petersburg, 190000, Russian Federation Corresponding author: vanya170595@gmail.com Article info
Received 28.05.20, accepted 29.06.20 Article in Russian
For citation: Noskov I.K., Bezzateev S.V. Effective implementation of modern McEliece cryptosystem on generalized (L, G)-codes. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2020, vol. 20, no. 4, pp. 539-544 (in Russian). doi: 10.17586/2226-1494-2020-20-4-539-544
Abstract
Subject of Research. The paper presents the study of methods and approaches to implementation of the modern McEliece cryptosystem based on separable generalized (L, G)-codes. Method. A method is proposed based on the analysis of the well-known public sources on implementation of the modern McEliece cryptosystem that uses the
generalized (L, G)-codes with locators of degree greater than or equal to the second one without using an extended field. Mаin Results. Approaches to implementation of the modern McEliece cryptosystem based on the generalized (L, G)-codes are developed, namely: creation of a parity check matrix for the generalized (L, G)-code using a separable Goppa polynomial and locators of various degrees, description of an approach to the implementation of encryption and decryption of messages in the modern McEliece cryptosystem, presentation of the Chein&s procedure for numerators of degree greater than or equal to the second one without expanding the field. Practical Relevance. The proposed methods can be used in the development of cryptographic systems that can withstand attacks from quantum computers and ensure data confidentiality, as well as improve the security and performance of cryptosystems. Aerospace, automobile, railway, network multimedia, telecommunication and mobile information protection systems can also be the scope of the work results. Keywords
Goppa codes, generalized (L, G)-codes, decoding algorithms, modern McEliece cryptosystem, separable polynomial
Введение
В настоящее время из-за активного развития квантовых компьютеров возникла потребность в постквантовой криптографии. Исследования показали, что для противодействия атакам, использующим квантовые вычисления, размер ключа в криптографических системах должен быть существенно увеличен, а многие известные криптосистемы вообще не могут быть использованы в условиях существования квантового компьютера. Некоторые криптосистемы, построенные для постквантовой криптографии, используют двоичные неприводимые коды Гоппы [1], что является проблемой, связанной с ограничением длины кода для выбранного порядка поля.
Для решения данной проблемы можно использовать обобщенные (Ь, С)-коды [2]. Проблема заключается в том, что для обобщенных (Ь, С)-кодов плохо изучены проблемы реализации, а именно: построение нумераторов второй степени и выше, алгоритм декодирования Паттерсона для сепарабельных многочленов и процедура Ченя для декодирования. В данной статье рассмотрены возможности использования обобщенных (Ь, С)-кодов с нумераторами второй степени и выше без вычислений в расширении поля, использования процедуры Ченя для данной реализации, а также подход к реализации шифрования и расшифрования в современной криптосистеме Мак-Элиса.
Современный вариант криптосистемы Мак-Элиса
Для начала необходимо ввести несколько определений.
Определение 1 [1]. Двоичный вектор a = (а1, а2, ..., ап) является кодовым словом кода Гоппы для множества локаторов Ь = {а1, а2, ..., ап} и для многочлена О(х), который называется многочленом Гоппы, тогда и только тогда, когда выполняется сравнение
¿=1 х - а;
где а,- е ОЕ(2ш), п < 2ш, О(х) е ^ [х], degG(x) = г.
Определение 2 [1]. Код Гоппы называется сепара-бельным, если О(х) — сепарабельный многочлен.
Определение 3 [1]. Код Гоппы называется неприводимым, если О(х) — неприводимый многочлен.
Утверждение 1 [1]. Сепарабельный двоичный код Гоппы имеет избыточность г и минимальное расстояние d, определяемые неравенствами:
г < шг, d > 2г + 1.
Определение 4 [2]. Двоичный вектор a = = (а1, а2, ..., ап) является кодовым словом обобщенного (Ь, С)-кода для множества локаторов
, где /¡&(х) — формальная производная для /(х), тогда и только тогда, когда выполняется сравнение
Yfii~— =0modG(x). &=i fi(x)
Расстояние такого кода определяется неравенством [2, 3]:
I = max deg/£t).
Чтобы построить проверочную матрицу для обобщенного (Ь, С)-кода, рациональную функцию можно представить в виде [4]:
+ Ь^х1 + Ь-0то<Ю(х), Ьи е 6^(2").
Тогда уравнение (1) для обобщенного (Ь, С)-кода может быть переписано в форме:
= tflfiix) = Iflpu-I^ + Ыи-J-2 +■ ■ •
м UX) w w & &-1
+ ¿аДдХ1 + Jflpu 0 = OmodG(x),
а проверочная матрица будет выглядеть следующим образом:
bU-l &&& Vl
Очевидно, что для любого кодового слова a = (а1, а2,... , ап ) обобщенного (Ь, С)-кода определяемого сравнениями (1) и (2) будет выполняться соотношение
H•aT = 0. (4)
Здесь матрица Н состоит из элементов Ъ^ € ОР(2т). Двоичная проверочная матрица получается путем представления каждого элемента Ъ,, в виде двоичного вектор-столбца из т бит. Таким образом, полученная двоичная матрица Н будет состоять из т? строк и п столбцов.
Для построения современной криптосистемы Мак-Элиса [5, 6], использующей идеи классического алгоритма Мак-Элиса [7] и алгоритма Нидеррайтера [8], выбирается многочлен Гоппы О(х) и множество локаторов Ь в качестве секретного ключа. По выбранным О(х) и Ь строится проверочная матрица Н. Используя метод Гаусса проверочная матрица Н приводится к диагональному виду Н
Н = [Е Т],
где Е — единичная матрица, а матрица Т является открытым ключом системы шифрования.
Реализация шифрования. На вход функции шифрования подается сообщение Ь длины 256 бит, которое требуется зашифровать, и матрица Т. Алгоритм шифрования состоит из следующих шагов:
Со = Не;
Ь = #йий(е);
Я = Ь © Ь.
Результатом шифрования будут вектора Я и Со. Реализация расшифрования. На вход функции расшифрования подаются двоичный вектор Со длины т? бит, вектор Я длины 256 бит, а также секретный ключ, который состоит из множества локаторов Ь и многочлена Гоппы О(х). Алгоритм расшифрования состоит из следующих шагов:
Ь = #йий(е);
Ь = Я © Ь.
Результатом расшифрования будет вектор Ь.
Приведем более подробно схему работы алгоритма расшифрования. Легко увидеть, что значение синдрома в = Ну равно Со, поскольку первые п - к позиций вектора V = (Со, 0, 0, ..., 0) умножаются на единичную матрицу, а остальные позиции равны нулю. Так как Со = Не, где вес Хэмминга вектора е равен т и в = Ну = Со = Не, следовательно, V = С © е, где С является кодовым словом и для него выполняется соотношение (4). Это кодовое слово находится на расстоянии Хэмминга равным т от V, и такое кодовое слово, находящееся на расстоянии не большим т от V — единственно, поскольку минимальное расстояние используемого кода Гоппы не менее 2т + 1.
Вычисление открытого ключа и секретного множества локаторов для обобщенных (£,С)-кодов с локаторами первой и второй степени
Для упрощения изложения, но без потери общности, далее будет рассмотрен случай построения проверочной матрицы и открытого ключа для обобщенного (Ь, С)-кода, содержащего локаторы первой и второй степени.
Проверочная матрица для обобщенного (Ь, С)-кода с сепарабельным многочленом О(х), содержащая локаторы первой и второй степени может быть представлена в виде:
ад <?(Р,)
а,. Р/ / Р/
■• 1 +
ад с(р,) 1 <Щ
а/"1 Г1 / р/"1
- ., ■• 1 +
ад Щ) 1 <щ>
где а, € ОР(2т), р, € ОЕ(22т).
Чтобы не строить поле размера ОЕ(22т), элемент данного поля можно представить [9] в виде:
Ру = акг + су, (5)
где ак, а/ € ОЕ(2т).
Опишем теперь сложение и умножение таких элементов, задав элемент Р, = атг + ап.
+ Р/ = атг + ап + акг + а/ = (ак + ат)г + (а/ + аn),
Р-Р/ = (атг + ап)(акг + а/ = (акат)г2 +
+ (акап + а/ат)г + а/ап. (6)
Для упрощения полученных соотношений можно редуцировать их по модулю неприводимого многочлена второй степени [9]. Известно [14], что существует неприводимый многочлен вида /(г) = г2 + г + ак, ак € С¥(2т) для любого т. Таким образом, соотношение (6) можно переписать в виде:
Р-Р/ = (акг + а/)(атг + ап) = (акат)г2 + + (акап + а/ат)г + а/«п = (акап + а/ат + акат)г +
(а/ап + акат)шо(г2 + г + а/).
Подставляя значение (5) в 0(/ по модулю неприводимого многочлена, получим
С(Р/) = 0(атг + ап) = Р9 = ар? + аЬ
где ар,ап € ОР(2т); вч € ОГ(22т).
Для нахождения значений в проверочной матрице Н для локаторов второй степени необходимо найти значение, обратное значению С(Р/). Пусть аср + ау = (арг + ап)-1. Тогда
(а^ + ау)(ар2 + ап) = 1.
Из этого уравнения получим
(асР + <>(ар2 + ап) = асРр?2 + (аА + ауар)г + ауап =
= аср,р(г + ак) + (а^ + а^г + ал =
= (а^р + аА + ауар)г + (ауап + асР-рак) = = 1тоё(г2 + г + ак).
Теперь можно перейти к следующей системе уравнений:
(а.^ + аА + ауар = °
[ ауап + а^арак = 1.
Подставляя в первое уравнение значение а^ из второго уравнения получим
| ак^ + ауапак1 + «р^Ч^Ч + ауап\\~1ак- + ауар = 0
Подставляя во второе уравнение значение ау из первого уравнения получим
а а, 1 + а 2 + а &ои 1 + а &
п к п р к р
сь = а &а, & + ааа &ои
Тогда
а +а„
ап2 + апар + ар2&
ап\\ + апарак + ар\\
Зная, что
= ааг + а„ можно найти значения
элементов в столбцах проверочной матрицы Н для локаторов второй степени.
Для вычисления открытого ключа системы Мак-Элиса необходимо привести проверочную матрицу Н к виду:
Н = [Е Т],
где Е — единичная матрица; Т — оставшаяся матрица (открытый ключ системы). Для построения открытой проверочной матрицы проверочная матрица Н приводится по Гауссу. На первом этапе осуществляется так называемый прямой ход, когда путем элементарных преобразований над столбцами исходную матрицу Н приводят к ступенчатой форме, а именно, среди элементов первой строки матрицы выбирают ненулевой, перемещают его на первую позицию перестановкой столбцов (если поменялся 1-й и /-й столбцы, то необходимо поменять 1-й и /-й локаторы во множестве локаторов Ь). Затем получившаяся после перестановки первая строка складывается по модулю 2 с остальными строками, где на первой позиции элемент равен 1, обнуляя тем самым столбец под единичным элементом, стоящим на первой позиции в первой строке. Затем среди элементов второй строки матрицы находят ненулевой и аналогичным образом перемещают его на вторую позицию перестановкой столбцов, при этом меняются местами соответствующие локаторы во множестве локаторов Ь. Затем получившаяся после перестановки вторая строка складывается по модулю 2 с находящимися ниже остальными строками, где на второй позиции элемент равен 1, обнуляя тем самым столбец под единичным элементом, стоящим на второй позиции во второй строке. Эти действия выполняются со всеми строками матрицы Н. На втором этапе осуществляется так называемый обратный ход. Эта процедура повторяет прямой ход, но начинается с последней строки и идет вверх. После этого получившаяся единичная матрица Е отбрасывается, и оставшаяся часть Т матрицы Н является открытым ключом. Дополнительным результатом выполнения процедуры Гаусса над матрицей Н является получение секретного ключа Ь — переупорядоченного множества локаторов.
В результате выполнения такой процедуры Гаусса получается матрица Н и новое множество локаторов Ь с переставленными соответствующим образом элементами исходного множества Ь.
Реализация шифрования и расшифрования
Реализация шифрования. Для реализации процедуры шифрования необходимо создать двоичный вектор-столбец е длины п и веса Хэмминга ?/2, где п — длина кода; ? — степень многочлена Гоппы.
Далее данный вектор разбивается на две части следующим образом
еТ = (^Х
где е1 — вектор длины т?; е2 — вектор длины п - т?.
Затем находится результат перемножения матрицы Т на вектор е1, и результат складывается с вектором е2
Со = Те^ © е2Г.
Полученный вектор Со и будет являться результатом шифрования. Отметим, что данная процедура равносильна умножению матрицы Н = [Е Т] на вектор-столбец е = (е^е^7) и позволяет не расширять матрицу Т до матрицы Н, что приводит к ускорению вычислений.
Реализация расшифрования. Для реализации процедуры расшифрования находится следующая матрица
с элементами из 0¥(2т), для построения которой используются первые п - т1 локаторов из множества ¿:
х2 + а^х + а0= (х + в)(х + Р2т),
ОД ОД
ОД) од
а/"1 Г
ОД ОД
ОД ОД/
Матрица H1, состоящая из элементов поля ОЕ(22т), представленных в виде (3) умножается на вектор-столбец ^
= ^0Такой вариант процедуры вычисления синдрома позволяет не расширять вектор Од до вектора v, а также использовать проверочную матрицу меньшего размера. Для полученного значения синдрома c с помощью одного из алгоритмов: расширенный алгоритм Евклида, алгоритм Берлекэмпа-Месси или алгоритм Паттерсона [15] находится многочлен локаторов позиций ошибок.
Нахождение позиций ошибок с помощью процедуры Ченя. Затем из многочлена локаторов позиций ошибок находятся позиции ошибок, т. е. вектор e. Для этого можно использовать процедуру Ченя, которая в классическом варианте алгоритма декодирования помехоустойчивых кодов позволяет найти позиции вектора ошибки, на которых находятся единицы для множества локаторов первой степени. Для данной модификации алгоритма декодирования также можно использовать процедуру Ченя. Это возможно, так как полученный после декодирования полином можно представить как
а/ + а^-Х-1 +• • •+ аг0 = %(х + ау&0)(х + а/1)" &(х + ^^
где а^к — корни данного многочлена.
Чтобы использовать процедуру Ченя, можно представить элемент поля ОЕ(22т) как в (3).
Полином локаторов ошибок, состоящий из нумераторов первой и второй степени, можно представить следующим образом
а,х& + а; х-1 +"+ а;„ =
&1 &1-1 &0
= аП^ + аУ,к_1 +•+ ^
где хку + хку 1 +"+ ау,&0 — неприводимый многочлен первой или второй степени (ку € {1,2}) над полем х-1
ОР(2т) и 1 = X К
Любой неприводимый многочлен второй степени над 0¥(2т) можно представить как:
где в € 0¥{21т).
Если при подстановке элемента в, представленного как в (1), уравнение (8) обратится в ноль, значит и уравнение (7) также обращается в ноль.
В результате будет найден двоичный вектор, содержащий единицы на позициях, занумерованных локаторами, при подстановке которых уравнение (7) обратилось в ноль.
Пример 1. Рассмотрим полином локаторов ошибок я(х) над полем ОЕ(2ъ), задаваемым порождающим многочленом х3 + х + 1, который содержит нумераторы первой и второй степени
я(х) = х5 + а1х4 + а5х3 + а5х2 + а4х + а4. (9)
Пусть элемент, соответствующий проверяемому локатору позиции, равен в^
я(р) = (р)5 + а1/ + а5/ + а5(/ + а4(/ + а4. (10)
Тогда в = а1 + а2г, и проверим, является ли данный элемент корнем уравнения (9).
Найдем значения р, (в/)2, — ,(в/)5 используя представления элементов поля ОЕ(26) как многочленов с коэффициентами из поля ОЕ(2ъ) по модулю неприводимого многочлена Дг) = г2 + г + 1:
в/ = а1 + а2г,
(р/)2 = а2 + а4г2 = а2 + а4(г + 1) = = а1 + а2гтоё(г2 + г + 1),
(р/)3 = р/(в/)2 = а2 + (а3 + а5)г + а6г2 = = а2 + а2г + а6(г + 1) = а0 + а0гтоё(г2 + г + 1),
(р/)4 = (а1 + а2г)4 = а4 + а1г4 = а4 + а1г = = а4 + а1гтоё(г2 + г + 1),
(р/)5 = рД(в/)4 = (а1 + а2г)(а4 + а1г) = = а2 + а1гтоё(г2 + г + 1).
Теперь подставим полученные значения в (10) я(х) = а2 + а1г + а1(а4 + а1г) + а5(а0 + а0г) +
+ а5(а1 + а4г) + а4(а1 + а2г) + а4 = 0.
Так как данное уравнение обратилось в ноль при подстановке р = а1 + а2г, значит а1 + а2г является его корнем.
Заключение
В статье рассмотрен один из вариантов реализации современной криптосистемы Мак-Элиса, а именно предложен алгоритм, использующий обобщенные (Ь, б^-коды с нумераторами второй степени и выше без вычислений в расширении исходного поля, предложен вариант использования процедуры Ченя для данной реализации, а также подход к реализации шифрования и расшифрования.
References
Авторы
Носков Иван Константинович — аспирант, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация, Scopus ID: 57207734046, ORCID ID: 0000-0001-7758-097X, vanya170595@gmail.com
Беззатеев Сергей Валентинович — доктор технических наук, доцент, профессор практики, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация; заведующий кафедрой, Санкт-Петербургский государственный университет аэрокосмического приборостроения (ГУАП), Санкт Петербург, 190000, Российская Федерация, Scopus ID: 6602425996, ORCID ID: 0000-0002-0924-6221, bsv@aanet.ru
Ivan K. Noskov — Postgraduate, ITMO University, Saint Petersburg, 197101, Russian Federation, Scopus ID: 57207734046, ORCID ID: 0000-0001-7758-097X, vanya170595@gmail.com
Sergey V. Bezzateev — D.Sc., Associate Professor, Professor of Practice, ITMO University, Saint Petersburg, 197101, Russian Federation; Head of Chair, Saint Petersburg State University of Aerospace Instrumentation (SUAI), Saint Petersburg, 190000, Russian Federation, Scopus ID: 6602425996, ORCID ID: 0000-0002-0924-6221, bsv@aanet.ru
