ON SOME CRYPTOSYSTEMS BASED ON ALGEBRAIC CODES

Full Text

Введение

В 1978 г. Мак-Элисом предложена первая криптосистема, основанная на алгебраических блоковых кодах [1]. В ее основе лежит маскировка быстрого алгоритма декодирования посредством умножения исходной порождающей матрицы G на случайную невырожденную матрицу, которая, в частности, является секретным ключом криптосистемы. Полученный результат (открытый ключ) представляет собой порождающую матрицу, имеющую вид случайно выбранных линейно независимых векторов. Злоумышленник, имеющий только открытый ключ, вынужден использовать сложный алгоритм неалгебраического декодирования (NP-полная задача). Законный пользователь, знающий секретный ключ, снимает действие маскировки и применяет быстрый алгебраический алгоритм декодирования (полиномиально разрешимая задача). Данная криптосистема на данный момент остается криптостойкой, так как нет ни одного эффективного алгоритма нахождения секретного ключа. Более того, данная криптосистема является одним из претендентов на официальную постквантовую криптосистему [2].

Криптосистема Мак-Элиса при использовании кодов Гоппы считается криптостойкой. Для декодирования кодов Гоппы хорошо известен алгоритм Паттерсона [3]. Но он применим только для двоичных кодов Гоппы. При этом заметим, что любой алгоритм декодирования обобщенных кодов Рида — Соломона можно применить и для кодов Гоппы над любым полем. Для обобщенных кодов Рида — Соломона и кодов Гоппы подобные алгоритмы рассматривались в работах [4–7].

 

1. Криптосистема Мак-Элиса

   Классическая криптосистема. Пусть G — порождающая матрица [n, k, d]-кода над GF (q), исправляющего t и менее ошибок (в оригинальной статье предлагается использовать двоичные сепарабельные коды Гоппы), C — невырожденная матрица порядка k над полем GF (q), P и D — перестановочная и диагональная матрицы порядка n соответственно (для двоичных кодов матрица D не используется).

   Матрица G�

   = C · G · P · D является открытым ключом абонента A, как и параметры n, k, t.

   Маскирующие матрицы C, P, D и порождающая матрица G являются секретным ключом абонента A.

   В силу того, что матрицы C, P , D невырождены, матрица G�

   является порождающей матрицей

   эквивалентного кода. Предположим, что абонент B хочет передать абоненту A сообщение x длины k с компонентами из GF (q). Алгоритм шифрования, предложенный Мак-Элисом, выглядит следующим образом.

   1. Случайным равновероятным образом генерируется вектор ошибок e длины n над GF (q) веса не более t.

   2. Абонент B вычисляет шифрованное сообщение y = xG� + e, которое по открытому каналу связи передает абоненту A.

Вектор ошибок e, генерируемый на первом шаге, является случайным параметром шифра, который значительно усложняет криптоанализ. При wt(e) = t сложность дешифрования будет максимальной. Также заметим, что при каждом таком шифровании вектор e должен генерироваться заново. Для расшифрования сообщения абонент A совершает следующие действия.

1. Умножение полученного вектора на матрицу (PD)−1: � = yD−1P−1. При этом � = yD−1P−1 =

   y

   x = xC, wt(e) = wt(e).

   �

   y

    

   x = xC.

2. Декодирование вектора �

   y, т. е. получение вектора �

3. Нахождение исходного сообщения x путем умножения вектора �

xC−1.

Замечание 1. Пусть G и H — порождающая и проверочная матрицы некоторого линейного кода, C и D — невырожденные квадратные матрицы подходящих размеров (для вычисления CG, DH). Порождающие матрицы CG и G задают один и тот же линейный код, так как GHT = O, тогда и только тогда, когда CGHT = O. Аналогично проверочные матрицы H и DH задают один и тот

хо

 

же линейный код. Это значит, что для декодирования вектора x на втором шаге приведенного выше алгоритма применяется проверочная матрица H (если она необ � дима), соответствующая матрице G.

Модернизированная криптосистема. Для того чтобы уменьшить объем параметров криптосистемы Мак-Элиса, имеется модернизированная версия данной криптосистемы [8], которая использует порождающую матрицу G в канонической форме: G = (Ik , Qk×(n−k)). В этом случае вместо

хранения k × n элементов достаточно хранить только матрицу Q размера k × (n − k). Более того, для

Рацеев С.М., Череватенко О.И., Чернявская В.А. О некоторых криптосистемах, основанных на алгебраических кодах

64Ratseev S.M., Cherevatenko O.I., Chernyavskaya V.A. On some cryptosystems based on algebraic codes

 

алгоритмов кодирования и декодирования требуется меньшее число операций. Также вместо матриц C, P, D в качестве секретного ключа хранится только перестановка элементов множества L и многочлен G(x) кода Γ(L, G).

Как утверждается в работе [8], криптостойкость модернизированной версии эквивалентна криптостойкости классической версии криптосистемы Мак-Элиса. Итак, сначала вычисляется открытый ключ G криптосистемы на основе параметров q, m, n, r.

1. Случайным образом генерируется многочлен G(x) степени r над полем GF (qm) (например, можно сгенерировать неприводимый многочлен).

2. Случайным образом выбираются n элементов поля GF (qm), не являющиеся корнями многочлена G(x), которые определяют множество L. Если G(x) неприводим, то можно взять любые различные n элементов поля GF (qm).

3. Вычисляется проверочная матрица H′ над полем GF (qm) размера r × n на основе L и G(x), r =

   = deg G(x).

4. С помощью элементарных преобразований строк матрица H′ приводится к систематическому виду CH′ (некоторые столбцы такой матрицы образуют единичную матрицу, а невырожденная матрица C является произведением соответствующих матриц элементарных преобразований), а затем с

   (n k) k

    

   помощью перестановки столбцов приводится к виду H = (QT

   − ×

   , In−

   k ), т. е. матрица CH′ справа

   умножается на перестановочную матрицу P : H = CH′P . К множеству L применяется такая же

   перестановка (обозначение L оставим прежним).

5. На основе матрицы H вычисляется порождающая матрица G в канонической форме: G =

= (Ik , Qk×(n−k)).

В итоге матрица G является открытым ключом криптосистемы. Как видно из алгоритма, для получения H требуется некоторая невырожденная матрица C и перестановочная матрица P . Заметим, что если n = qm, то L = GF (qm). Также в качестве G(x) чаще всего выбирают неприводимый многочлен над GF (qm). Множество L для данной криптосистемы является случайным и держится в секрете. Алгоритм шифрования в модернизированной версии не отличатся от классической, разве что на него требуется меньшее число операций. Для того чтобы абоненту B передать абоненту A сообщение x длины k с компонентами из GF (q), требуется выполнить следующие шаги.

1. Абонент B случайным равновероятным образом генерирует вектор ошибок e длины n над GF (q)

   веса не более t.

2. Абонент B получает шифрованное сообщение y = xG + e = x(I, Q) + e = (x, xQ) + e, которое по открытому каналу связи передает абоненту A.

Для расшифрования сообщения абонент A совершает следующие действия.

1. По вектору y вычисляется синдромный вектор S (синдромный многочлен S(x)).

2. С помощью алгоритма декодирования полиномиальной сложности находится вектор e веса не более

   t, который имеет синдром S.

3. После этого вычисляется кодовый вектор u = y − e, из которого извлекается сообщение x (из первых k позиций вектора u).

Есть несколько оснований для использования кодов Гоппы в криптосистеме Мак-Элиса:

1) существуют быстрые алгоритмы полиномиальной сложности декодирования кодов Гоппы; 2) код Гоппы легко генерировать, но очень сложно обнаружить «замаскированный» код Гоппы; 3) код Гоппы можно построить с помощью любого неприводимого многочлена над GF (2m), при этом порождающая матрица кода будет иметь «почти случайный» вид.

Заметим, что для любой фиксированной длины n существует «очень много» различных кодов Гоппы. Пусть N (q, s, r) — число неэквивалентных неприводимых кодов Гоппы над полем GF (q) длины qs и степени r многочлена G(x). Точной формулы для N (q, s, r) пока неизвестно. В работе [9] приводятся верхние границы для N (q, s, r), которые являются точными для некоторых небольших значений параметров. Например, число двоичных неприводимых кодов Гоппы длины n = 128 и степенью неприводимого многочлена r = 10 оценивается сверху числом N (2, 7, 10) = 1037499670492467 > 1015.

А для числа N (2, 7, 15) (т. е. для кодов той же длины 128 с неприводимым многочленом G(x) степени 15) уже выполнено равенство N (2, 7, 15) = 23765478069520611201643781 > 2 · 1025. Если увеличить длину

Вестник Самарского университета. Естественнонаучная серия. 2021. Том 27, № 1. С. 62–73

Vestnik of Samara University. Natural Science Series. 2021, vol. 27, no. 1, pp. 62–73 65

 

кодов до n = 4096 (чтобы обеспечивался должный уровень криптостойкости системы Мак-Элиса), то для данной границы уже при r = 7 получаем N (2, 12, 7) = 13728607731106143 > 1016.

Заметим, что криптосистема Мак-Элиса требует очень большого объема памяти для своих параметров. Для примера, чтобы добиться 80-битной криптостойкости, для алгоритма RSA необходим 1024-битный ключ, при этом для криптосистемы Мак-Элиса требуется ключ размера не менее 450 кбит для достижения той же степени криптостойкости.

Пример 1 (классическая криптосистема Мак-Элиса). Рассмотрим расширение поля GF (2) ⊂ GF (24).

Пусть поле GF (24) строится на основе примитивного многочлена p(x) = x4 + x + 1, α — примитивный элемент поля GF (24):

	=	1100,	α5 =		α	+α2		=	0110,
+α3	=	0011,	α7 =	1	+α		+α3	=	1101,
	=	1010,	α9 =		α		+α3	=	0101,

 

α2 =
α4 =	1	+α
α6 =
α8 =	1

 

α0 = 1 = 1000, α1 = α = 0100, α2 = 0010, α3 = α3 = 0001,

 

 

α10 = α12 = α14 =

α2

+α2

 

1	+α	+α2		=	1110,
1	+α	+α2	+α3	=	1111,
1			+α3	=	1001,

 

	α	+α2	+α3	=	0111,
1		+α2	+α3	=	1011,
1				=	1000.

 

α11 = α13 = α15 =

 

Пусть L = GF (24) = {0, 1, α, α2, . . . , α14}, G(x) = x2 + x + α3. Так как след элемента α3 в поле GF (24) не равен нулю, то многочлен G(x) в этом поле не имеет корней. Поэтому из неприводимости G(x) над GF (24) следует, что код Γ(L, G) является сепарабельным, т. е. он исправляет до двух ошибок. Проверочная матрица H кода Γ(L, G) примет такой вид:

( G(0)−1 G(1)−1 G(α)−1 . . . G(α14)−1 )

H = 0G(0)−1 1G(1)−1 αG(α)−1 . . . α14G(α14)−1 =

 

( α12 α12 α4 α3 α9 α4 α α8 α6 α3 α6 α α2 α2 α8 α9 )

= 0 α12 α5 α5 α12 α8 α6 α14 α13 α11 1 α11 α13 α14 α6 α8 =

 

	1	1	1	0	0	1	0	1	0	0	0	0	0	0	1	0	
	1	1	1	0	1	1	1	0	0	0	0	1	0	0	0	1	
 	1	1	0	0	0	0	0	1	1	0	1	0	1	1	1	0	 
 = 	1	1	0	1	1	0	0	0	1	1	1	0	0	0	0	1	  .
 	0	1	0	0	1	1	0	1	1	0	1	0	1	1	0	1	 
 	0	1	1	1	1	0	0	0	0	1	0	1	0	0	0	0	 
 	0	1	1	1	1	1	1	0	1	1	0	1	1	0	1	1	 
	0	1	0	0	1	0	1	1	1	1	0	1	1	1	1	0

Так как все строки матрицы H линейно независимы, то n − k = 8, k = 8. Выписав построчно

фундаментальную систему решений системы однородных линейных уравнений HX = O, находим

	1	0	1	1	0	1	1	1	0	0	0	0	0	0	0	0	
	1	0	0	1	0	1	0	0	1	1	0	0	0	0	0	0	
 	1	1	1	0	0	1	0	0	1	0	1	0	0	0	0	0	 
 	0	1	0	1	1	1	0	0	1	0	0	1	0	0	0	0	  .
 	0	0	1	0	1	1	1	0	1	0	0	0	1	0	0	0	 
 	0	1	0	0	1	1	1	0	0	0	0	0	0	1	0	0	 
 	1	0	1	0	1	1	0	0	0	0	0	0	0	0	1	0	 
	1	1	0	1	0	0	1	0	0	0	0	0	0	0	0	1

 

порождающую матрицу кода Γ(L, G):

 

G =

 

	1	1	0	0	0	0	0	1			1	1	0	1	1	1	0	1	
	0	0	0	0	0	0	0	1			0	0	0	1	1	1	0	1	
 	0	0	0	0	0	1	1	0	 	 	1	1	0	1	0	0	1	0	 
 	1	1	1	0	1	0	1	0	  , C	 −1 = 	0	0	1	0	0	0	0	1	  ,
 	1	1	1	0	1	0	0	1	 	 	0	1	0	1	1	0	1	0	 
 	0	1	0	1	0	1	0	1	 	 	0	1	1	1	1	0	0	0	 
 	0	0	0	0	1	0	1	0	 	 	0	1	0	1	1	0	0	0	 
	0	0	0	1	0	1	1	0			0	1	0	0	0	0	0	0

 

Абонент A генерирует невырожденную матрицу C и перестановочную матрицу P :

 

C =

Рацеев С.М., Череватенко О.И., Чернявская В.А. О некоторых криптосистемах, основанных на алгебраических кодах

66Ratseev S.M., Cherevatenko O.I., Chernyavskaya V.A. On some cryptosystems based on algebraic codes

 

 0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
 0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
 0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
  0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
  1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
 0 	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0
eσ(0)   0 	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
eσ(1)  =  0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0
. . .   0  	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
e  0 σ(15) 	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
  0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
 0 	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
  0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
  0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
 0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
0	1	2 3	4 5 6	7	8 9			10	11 12			13	14 15
4	10	13 9	0 7 15	3	14 11			5	1 8			2	12 6

 





















 







 

,

 



 

P =  





 























 

( )

σ = ,

 

где σ — подстановка на множестве {0, 1, . . . , 15} (строки и столбцы нумеруем с нуля). После этого

абонент A вычисляет матрицу:

0	0	0	1	1	0	1	0	0	1	1	1	0	1	1	0	
0	0	0	0	1	0	1	0	0	1	1	0	0	0	0	1	
0	0	1	0	1	0	0	0	0	0	1	0	1	1	0	1	 
0	0	0	1	0	1	0	1	1	0	1	1	1	0	1	0	  .
1	0	0	1	0	1	1	0	1	1	0	1	0	1	1	1	 
0	1	1	0	0	0	1	1	0	1	1	1	0	0	0	0	 
0	0	0	0	1	0	0	0	1	0	0	0	1	0	1	1	 
1	1	1	0	1	0	0	1	0	1	0	0	1	1	1	1

 













 

G� = CGP = 











 

Параметры n = 16, k = 8, t = 2 и матрица G�

являются открытым ключом абонента A.

Предположим, что абонент B хочет передать абоненту A сообщение x = (0, 1, 1, 1, 0, 0, 1, 1), которое нужно предварительно зашифровать на открытом ключе абонента A. Абонент B генерирует вектор ошибок веса два и вычисляет:

y = xG� + (0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0) =

= (1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0).

Сообщение y передается абоненту A по открытому каналу связи. Для расшифрования сообщения y

абонент A проделывает следующие действия. Сначала вектор y умножается на P−1 = P T :

y = yP−1 = (0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1),

�

т. е. элементы в векторе y переставляются в соответствии с перестановкой σ. Для декодирования y

применим алгоритм Паттерсона (см. [3; 4]). По вектору y вычисляется синдромный многочлен �

�

15

S(x) ≡ ∑

i=0

 

i

 

y

�

x − αi

 

1

≡ x − 1 +

 

1

x − α3

 

1

+ +

x − α4

 

1

+

x − α7

1

+ +

x − α8

1

x − α9

1

+ +

x − α10

1

x − α14

≡ α9 + α5x (mod G(x)).

Вычисляется T (x) ≡ (α9 + α5x)−1 ≡ 1 + α14x (mod G(x)). Учитывая, что s(x) ≡ √x ≡ α9 + x (mod G(x)), вычисляется p(x):

p(x) ≡ √T (x) + x ≡ √1 + α3x ≡

≡ (1)8 + (α3)8(α9 + x) ≡ α14 + α9x (mod G(x)).

Полагается r = deg G(x) = 2, r−1(x) = G(x), r0(x) = p(x), v−1(x) = 0, v0(x) = 1. При j = 0 выполнено:

r r

deg r−1(x) = 2 > 2 , deg r0(x) = 2 ,

0

 

поэтому с точностью до константы σ(x) = r2(x) + xv0(x) = α13 + x + α3x2.

Вестник Самарского университета. Естественнонаучная серия. 2021. Том 27, № 1. С. 62–73

Vestnik of Samara University. Natural Science Series. 2021, vol. 27, no. 1, pp. 62–73 67

 

y

 

Корнями многочлена σ(x) являются X1 = α4 = α5, X2 = α6 = α7, поэтому ошибки в векторе �

новый

 

содержатся на 5-й и 7-й позициях. После исправления двух ошибок в векторе y вектор примет

�

вид

y = (0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1) = xCG = xG.

�

Так как столбцы матрицы G с номерами 7, 9–15 (нумеруя с нуля) образуют единичную матрицу, то из вектора y извлекаем вектор x = (1, 1, 1, 1, 0, 0, 0, 1). Осталось вычислить:

�

x = xC−1

�

= (0, 1, 1, 1, 0, 0, 1, 1).

 

1. Криптосистема Нидеррайтера

   Другим важным примером кодовых криптосистем является схема Нидеррайтера [10]. Открытым ключом в этой криптосистеме являются параметры n, k, t и матрица H� = CHPD, где H — проверочная матрица алгебраического [n, k, d]-кода над GF (q) (в оригинальной статье предлагалось использовать обобщенные коды Рида — Соломона, но такой вариант взломан), C — невырожденная матрица порядка

   n − k над полем GF (q), P и D — перестановочная и диагональная матрицы порядка n соответственно

   (для двоичных кодов матрица D не используется). Маскирующие матрицы C, P, D и проверочная

   матрица H являются секретным ключом абонента A.

   Предположим, что абонент B хочет передать абоненту A сообщение e длины n над GF (q) веса не более t, т. е. сообщения в этом случае не являются кодовыми словами, а представляют собой

   всевозможные векторы ошибок, которые этот код в состоянии исправлять (как помещать открытые тесты в векторы-ошибок см., напр., [11]). Шифрованное сообщение длины n−k получается следующим

   образом: y = eH� T .

   При этом наибольшая стойкость будет при wt(e) = t. Для расшифрования сообщения абонент A

   совершает следующие действия.

   1. Абонент A умножает полученный вектор на (CT )−1:

      S = y(CT )−1 = eDP T HT CT (CT )−1 = eDP T HT = eHT ,

      �

      e = eDP T , wt(�

      = wt(e).

      где � e)

       

   2. В смежном классе с синдромом S теперь с помощью алгоритма декодирования вычисляется вектор ошибок e (здесь можно применить любой алгоритм декодирования, который по синдромному

      нах

       

      вектору � одит вектор ошибок: алгоритм Сугиямы, Берлекэмпа — Месси и т. д.).

      e на PD−1: e = �

      D−1.

   3. Нахождение исходного сообщения e путем умножения вектора � eP

Заметим, что на втором шаге алгоритма расшифрования вычисляется вектор ошибок по синдромному вектору, а не по искаженному вектору.

Приведем также модификацию алгоритма расшифрования сообщения y = eH� T .

1. Умножение полученного вектора y на (CT )−1:

   S = y(CT )−1 = eDP T HT = eHT ,

   �

   e = eDP T , wt(�

   = wt(e).

   где � e)

    

   x, который является решением относительно x уравнения S =

2. Нахождение какого-либо вектора �

   = xHT (т. е. � и � имеют одинаковые синдромы и поэтому принадлежат одному смежному классу,

   e x

   e. Следовательно, x является вектором вида

   �

   � e для некоторого неизвестного информационного вектора i).

   e с помощью алгоритма декодирования, примененного для вектора

3. Нахождение вектора ошибок �

   x.

   �

    

   e на PD−1: e = �

    

   D−1.

4. Нахождение исходного сообщения e путем умножения вектора � eP

e

 

Заметим, что S = xHT — синдромный вектор и что � является одним из решений уравнения S =

= xHT относительно x. Нахождение какого-либо решения этого уравнения является простой задачей, так как это система из n − k линейных уравнений с n неизвестными. Но нахождение из всех решений

вектора минимального веса является очень сложной задачей.

Если использовать коды Гоппы, то многочлен G(x) может выступать дополнительным секретным параметром.

Рацеев С.М., Череватенко О.И., Чернявская В.А. О некоторых криптосистемах, основанных на алгебраических кодах

68Ratseev S.M., Cherevatenko O.I., Chernyavskaya V.A. On some cryptosystems based on algebraic codes

 

Теорема 1 ([12]). Пусть H — двоичная матрица размера (n − k) × n, S = eHT — ненулевой синдромный вектор, wt(e) � t. Тогда нахождение двоичного вектора e веса не более t с синдромом S является NP-полной задачей.

В работе [13] показано, что стойкости криптосистем Мак-Элиса и Нидеррайтера эквивалентны, поэтому любую эффективную атаку на одну из схем можно легко преобразовать в атаку на другую схему.

Для криптосистемы Нидеррайтера также имеется модернизированный вариант (с использованием кодов Γ(L, G)) для уменьшения объема хранимой информации. Алгоритм выработки открытого ключа H для модернизированной криптосистемы имеет следующий вид.

1. Случайным образом генерируется многочлен G(x) степени r над полем GF (qm) (например, можно сгенерировать неприводимый многочлен).

2. Случайным образом выбираются n элементов поля GF (qm), не являющиеся корнями многочлена G(x), которые определяют множество L. Если G(x) неприводим, то можно взять любые различные n элементов поля GF (qm).

3. Вычисляется проверочная матрица H′ размера r × n на основе L и G(x).

4. С помощью элементарных преобразований строк и перестановки столбцов матрица H′ приводится

   (n k) k

    

   к каноническому виду H = CH′P = (QT

   − ×

   , In−

   k ). L также умножается на P справа.

5. На основе матрицы H вычисляется порождающая матрица G в канонической форме: G =

= (Ik , Qk×(n−k)).

Шифрование сообщения в модернизированной криптосистеме совпадает с классической версией y =

= eHT , разве что необходимо выполнить меньшее число операций. Для расшифрования сообщения необходимо выполнить следующие действия.

eH′T

e)

 

e = eP T , wt(�

= wt(e).

 

e, после чего

2. С помощью алгоритма декодирования по синдромному вектору S находится вектор �

вычисляется e = eP .

�

Пример 2 (классическая криптосистема Нидеррайтера). Рассмотрим, как и в примере 1, расширение

GF (2) ⊂ GF (24), L = GF (24) = {0, 1, α, α2, . . . , α14}, многочлен G(x) = x2 + x + α3, код Γ(L, G)

c проверочной матрицей H. Матрицы C и P возьмем из примера 1.

Абонент A вычисляет матрицу:

 

	0	0	1	0	0	0	1	0	1	0	1	1	0	0	1	0	
	1	1	1	1	0	0	0	0	1	0	1	1	1	0	1	1	
 	0	0	0	0	0	0	1	1	1	0	0	0	1	0	1	1	 
 = 	1	0	0	1	1	0	1	0	1	1	1	1	1	1	1	0	  .
 	1	0	1	0	1	0	0	1	1	0	1	1	1	0	1	0	 
 	0	1	1	1	0	1	0	1	1	0	0	1	1	0	0	0	 
 	0	1	1	1	0	1	0	0	0	1	0	1	1	1	0	1	 
	1	0	0	0	1	1	0	1	1	1	1	1	1	0	0	1

 

H� = CHP

 

Параметры n, k, t и матрица H�

являются открытым ключом абонента A.

Абонент B помещает сообщение x в вектор ошибок e длины n веса не более t = 2. Пусть

e = (0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0).

Абонент B шифрует сообщение e с помощью открытого ключа H� :

y = eH� = (0, 0, 0, 1, 0, 1, 1, 1).

Шифрованное сообщение y передается по открытому каналу связи абоненту A.

Абонент A, получив сообщение y, расшифровывает его следующим образом. Сначала происходит умножение вектора y на матрицу (CT )−1 = (C−1)T :

S = y(CT )−1 = (1, 1, 0, 1, 0, 1, 1, 0).

x системы уравнений xHT = S:

 

Зафиксируем частное решение �

x = (0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0).

�

Вестник Самарского университета. Естественнонаучная серия. 2021. Том 27, № 1. С. 62–73

Vestnik of Samara University. Natural Science Series. 2021, vol. 27, no. 1, pp. 62–73 69

 

После применения к вектору x алгоритма декодирования, например алгоритма Паттерсона:

�

S(x) ≡ α13 + α7x, T (x) ≡ S−1(x) ≡ α14 + αx, p(x) ≡ √T (x) + x ≡ α8 + α2x,

σ(x) = r2(x) + xv2(x) = α + x + α4x, X1 = 1 = α1, X2 = α12 = α13,

0

получаем вектор ошибок e:

�

0

 

e = (0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0).

�

Для нахождения вектора e осталось вычислить:

e = eP = (0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0).

�

 

1. Современная кодовая криптосистема

   Рассмотрим современную кодовую криптосистему [14; 15] на основе кодов Гоппы, которая использует идеи крипосистем Мак-Элиса и Нидеррайтера.

   Генерация ключа. Абонент A производит следующую последовательность действий.

   1. Генерация случайным образом неприводимого многочлена G(x) ∈ GF (2m) степени r = t.

   2. Случайным образом выбирается множество L = {α1, α2, . . . , αn} различных элементов поля

      GF (2m).

   3. Вычисляется проверочная матрица H′ размера r × n на основе множества L и многочлена G(x):

      j

       

      (H′)ij = αi−1G(αj )−1.

   4. Пусть β1, . . . , βm — базис пространства GF (2m) над GF (2) (например, если α — примитивный элемент поля GF (2m), то можно взять βi = αi−1, i = 1, . . . , m). Каждый элемент матрицы H′ заменяется двоичным вектором-столбцом длины m с компонентами из поля GF (2), где данный столбец является координатным столбцом элемента матрицы H′ в базисе β1, . . . , βm. Тем самым

      получим двоичную матрицу H�

      размера rm × n над GF (2).

       

   5. С помощью элементарных преобразований строк матрица H�

приводится к систематическому виду

H = (In−k , Q(n−k),k ). Если это невозможно, то происходит переход в шаг 1.

После таких манипуляций открытым ключом абонента A являются n, k, t, H = (In−k , Q). Секретным ключом являются параметры L и G(x) неприводимого (следовательно, сепарабельного) кода Гоппы

Γ(L, G) длины n и размерности k = n − mr.

Шифрование сообщения. Пусть h — некоторая хеш-функция (например, с длиной свертки 256), e — двоичный открытый текст веса t. Алгоритм шифрования абонентом B сообщения e на основе открытого ключа абонента B имеет следующий вид.

 

1. Вычисление двоичного вектора c0 = eHT = e(In

   −

    

   k , Q)T длины mr.

    

2. Вычисление значения хеш-функции от e: c1 = h(e).

 

Шифрованным сообщением будет являться пара (c0, c1).

Расшифрование сообщения. После получения сообщения (c0, c1) для его расшифрования абонент

A проделывает следующие шаги.

1. Вектор c0 дополняется k = n − rm нулями до длины n: v = (c0, 0, . . . , 0).

2. С помощью алгоритма декодирования находится (единственный) кодовый вектор u ∈ Γ(L, G), находящийся на расстоянии Хэмминга до вектора v не более t, т. е. d(u, v) � t (ниже приводится этому обоснование).

    

   −

    

3. Вычисляется вектор e = v u.

�

 

eHT = c0 и h(�

 

= c1, то e = � — исходный открытый текст.

e) = t, � e) e

Рацеев С.М., Череватенко О.И., Чернявская В.А. О некоторых криптосистемах, основанных на алгебраических кодах

70Ratseev S.M., Cherevatenko O.I., Chernyavskaya V.A. On some cryptosystems based on algebraic codes

 

Заметим, что на втором шаге алгоритма расшифрования синдром вектора v совпадает с c0: vHT =

= c0. Действительно, vHT = v(In

−k , Q

 

(n−k),k

)T = v

( In−k

QT

k,(n−k)

)

= c0. Поэтому векторы e и v имеют

одинаковые синдромы, значит, принадлежат одному смежному классу. Следовательно, искомый кодовый вектор равен u = v − e.

Замечание 2. Алгоритмы шифрования и расшифрования можно модернизировать следующим образом. Пусть x — исходный двоичный открытый текст, длина которого совпадает с длиной сверок хеш-функции h. Генерируется случайный двоичный вектор (ошибок) e длины n веса t, вычисляются c0 =

= eHT , c1 = h(e), y = x⊕c1. Шифрованным сообщением будет являться пара (c0, y). Для расшифрования производятся следующие действия: v = (c0, 0, . . . , 0), находится кодовый вектор u ∈ Γ(L, G) со свойством d(u, v) � t, вычисляются e = v − u, c1 = h(e). Тогда x = y ⊕ c1.

 

1. Протоколы аутентификации на основе кодовых криптосистем

   Построение протоколов аутентификации с нулевым разглашением можно реализовать, используя известные алгоритмы открытого шифрования. В качестве секретной информации, которой владеет доказывающая сторона A, будет использоваться секретный ключ x асимметричного шифра. Пусть Dx — алгоритм расшифрования на секретном ключе x, Ey — алгоритм шифрования на открытом ключе y. Проверяющая сторона шифрует некоторое сообщение M на открытом ключе y и передает криптограмму C = Ey (M ) абоненту A. Абонент A демонстрирует владение секретной информацией x тем, что расшифровывает сообщение своим секретным ключом: M = Dx(C) и передает сообщение M проверяющей стороне B. Для проверяющей стороны B это не несет никакой дополнительной информации о секретном ключе x, так как у B до этого было то же самое сообщение M . При этом при построении протоколов с нулевым разглашением знания нужен некоторый механизм, который позволит владельцу секретного ключа (доказывающему A) до передачи восстановленного сообщения M проверяющему B убедиться в том, что последнее уже известно проверяющему B.

   В качестве такого механизма могут использоваться алгоритмы хеширования (хеш-функции). Данный механизм используется в протоколах с нулевым разглашением, описанных в стандарте [16].

   В стандарте [16] регламентируется формирование запроса в виде пары значений (C, H), где C — шифртекст, полученный путем шифрования некоторого сообщения M по открытому ключу доказывающего A, и H — значение хеш-функции, вычисленное от сообщения M с использованием некоторой хеш-функции h: H = h(M ). Получая запрос (C, H), доказывающий имеет возможность убедиться в том, что восстановленное им из шифртекста C сообщение M известно проверяющему. Для этого достаточно вычислить значение хеш-функции от восстановленного сообщения и сравнить его со значением второго элемента запроса.

   В соответствии с [16] двухшаговый протокол с нулевым разглашением знания включает следующие шаги.

    

   1. Проверяющий B выбирает произвольное сообщение M и, используя алгоритм открытого шифрования Ey и открытый ключ y доказывающего, зашифровывает сообщение M : C = Ey (M ). Затем, используя хеш-функцию h, вычисляет значение хеш-функции от : H = h(M ). После этого он отправляет доказывающему A пару значений (C, H) в качестве своего запроса.

       

   2. Доказывающий A расшифровывает криптограмму C, используя свой личный секретный ключ x, в результате чего получает сообщение M� = Dx(C). Затем он вычисляет значение хеш-функции от

      M�: H� = h(M�), сравнивает значения H�

      M� в качестве своего ответа.

      и H, если H� = H, то отправляет проверяющему значение

       

   3. Если выполнено равенство M� = M , то проверяющий B принимает доказательство; если равенство не выполнено, то отвергает.

 

Протокол аутентификации на основе классической криптосистемы Мак-Элиса. Абонент A фиксирует порождающую матрицу G некоторого [n, k, d]-кода над GF (q), исправляющего t и менее ошибок, невырожденную матрицу S порядка k над полем GF (q), перестановочную и диагональную матрицы P и D порядка n.

Матрица G� = SGPD является открытым ключом абонента A, как и параметры n, k, t. Маскирующие матрицы S, P, D и порождающая матрица G являются секретным ключом абонента A.

Протокол аутентификации имеет следующий вид.

Вестник Самарского университета. Естественнонаучная серия. 2021. Том 27, № 1. С. 62–73

Vestnik of Samara University. Natural Science Series. 2021, vol. 27, no. 1, pp. 62–73 71

 

1. Проверяющий B генерирует случайное сообщение M длины k с компонентами из GF (q), а также вектор ошибок e длины n над GF (q) веса не более t. Вычисляет C = M G� + e, H = h(M ) и отправляет доказывающему A пару значений (C, H).

    

2. Доказывающий A вычисляет C′ = CD−1P−1, декодирует вектор M′ на основе вектора C′, вычисляет M� = M′S−1, вычисляет H� = h(M�). Если H� = H, то отправляет проверяющему значение M� в качестве своего ответа.

    

3. После этого проверяющий B проверяет равенство

M� = M .

 

Аналогичным образом можно использовать любую кодовую криптосистему в качестве основы для протокола аутентификации.

 

Выводы

Рассмотренная в работе тема является актуальной, так как затрагивает вопрос существования постквантовых криптосистем с открытым ключом. Приведены некоторые вариации кодовых криптосистем, включая некоторые современные модификации на основе кодов Гоппы. Приводится пример декодирования кода Гоппы на основе алгоритма Паттерсона. Также в работе предложен вариант протокола аутентификации на основе кодовых криптосистем. Представленный протокол имеет нулевое разглашение знания.

 

About the authors

S. M. Ratseev

Ulyanovsk State University

Author for correspondence.
Email: ratseevsm@mail.ru
ORCID iD: 0000-0003-4995-9418

Doctor of Physical and Mathematical Sciences, associate professor, Department of Information Security and Control Theory

Russian Federation, 42, Lev Tolstoy Street, Ulyanovsk, 432017, Russian Federation.

O. I. Cherevatenko

Ulyanovsk State University of Education

Email: choi2008@mail.ru
ORCID iD: 0000-0003-3931-9425

Candidate of Physical and Mathematical Sciences, associate professor, Department of Higher Mathematics

Russian Federation, 4/5, Lenin Square, Ulyanovsk, 432063, Russian Federation.

V. A. Chernyavskaya

Ulyanovsk State University of Education

Email: vera.chernya@yandex.ru
ORCID iD: 0000-0001-9875-2232

student of the Department of Information Security and Control Theory

Russian Federation, 4/5, Lenin Square, Ulyanovsk, 432063, Russian Federation.

References

Supplementary files