Криптосистема, основанная на новых ранговых кодах

Автор: Нгуен З.Х.

Журнал: Труды Московского физико-технического института @trudy-mipt

Статья в выпуске: 3 (39) т.10, 2018 года.

Бесплатный доступ

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

Еще

Ранговые коды, система гпт, порождающая матрица

Короткий адрес: https://sciup.org/142220439

IDR: 142220439

Текст научной статьи Криптосистема, основанная на новых ранговых кодах

Пусть GF(q^ - базовое конечное поле, a GF(q ^m ) - его расширение степени т. Пространство векторов GF(q^m ) ^m длины т снабдим ранговой весовой функцией: ранговый вес вектора д = (gi д2 ... g_m) Е GF(q ^m ) ^m равен максимальному числу координат, линейно независимых над базовым полем.

Линейное пространство векторов размерности п над расширенным полем GF(q ^m ) обозначается GF(q ^m )ⁿ. Оно состоит из векторов с координатами из расширенного поля:

v = [«о щ • • • «у п - 1] , d^ Е GF(q ^m Y

Ранг вектора и определяется как максимальное число линейно независимых над основным полем GF(q) координат вектора.

В этой статье мы рассмотриваем только случай когда п = т.

Векторным ранговым кодом У называется любой набор векторов из векторного пространства GF (q^m')^m.

Ранговым расстоянием d векторного кода У называется наименьший ранг попарных разностей кодовых векторов:

d = min Rk(v1 — v₂), Уһ ^2 € У • гіі=гі2

Линейный векторный ранговый [т, k, d]-KOfl над GF(q^m~) — это k-мерное подпространство пространства векторов GF(q^m)^m с ранговым расстоянием d. Число векторов в k-мерном подпространстве равно q^mk.

Из границы Синглтона следует k < т — d + 1.

Если достигается знак равенства, то код называется кодом с максимальным ранговым расстоянием (МРР-кодом).

Линейные ранговые коды определяются порождающейся матрицей [1]:

G k =

( 91

9m \

1 2 ⁹ m

€ GF(qm')m.

\ 9?

, к

qk—

9m /

2. Система ГПТ

Система ГПТ с открытым ключом предложена Габидулиным, Парамоновым, Третьяковым в 1991 году [2]. Открытый текст - это любой k-вектор т = (т1, т ₂ ,•••, тк),т _і € GF(q^m) Открытый ключ - это k х (т + t) матрица.

G _pHb = S ( Y G k ) Р .

Здесь G _pub € GF(q^mX) ^k ^x ^m - _Это открытый ключ, известный всем пользователем.

Матрица S € GF(q^m') ^k ^x ^k - это строчный скремблер, который перемешивает строки последующих матриц.

Матрица Y € GF(q ^m )^xt - это матрица искажения, имеющая ранг t.

Матрица G _k (2) - порождающая матрица рангового кода.

Матрица Р € GF (q)(^t+^m)^x(^t+^m) - это столбцевой скремблер, который перемешивает столбцы матрицы (Y G _к).

Секретные ключи - это матрицы S, Y, G _k ,P и быстрый алгоритм декодирования МРР кода.

Шифрование: Пусть т - открытый текст. Тогда шифротекст задается соотношением с — TirCxp^h + eart, (4)

где e _art - вектор искусствешюй ошибки рангового веса t2 < t = (п — k + 1)/ 2. Расшифрование: После получения шифротекста с легальный пользователь вычисляет:

с = (С1,С2, ••• , Ct i +m) = cP ^-1 = mS [Y G _k + X ] + еР^-1.

′

Из вектора с извлекает подвектор:

^с" = ^(ct+1, ^Ct+2, * * * , ^Cti +m) = ^mSG k ^{+ mSX +} e^t,

где e _art - под вектор eP ^-1. Применяя к вектору с быстрый алгоритм декодирования, легальный пользователь находит вектор mS и открытый текст как вектор т.

Атаки Овербека: Овербек в работе [3] предложил следующую структурную атаку, цель которой восстановить закрытые ключи G _pub.

Искусственная ошибка e _art является исправляемой ранговой ошибкой. Столбцевой скремблер Р нужно выбрать так, чтобы вектор e _art P ^-1 являлся исправляемой ранговой ошибкой. В этом случае:

Rkcoi( e art) = Rk( e _a rt P 1) < t = [^-

—

Овербек показал, что систему ГИТ можно взломать в полиномиальное время. Критический момент атаки обоснован при условии, что все элементы матрицы Р находятся в базовом поле G F_q.

Пусть ст(ж) = х^ч для ж G GF _q N будет автоморфизмом Фробениуса. Для матрицы Т = (t _i j ) над полем GF _q N нусть a( T = (a(t _i j )) = (tq ). Для любого целого числа s пусть с ⁸ ( Т ) = ст(ст ^- ¹ ( Т )). Очевидно что cr ^N = ст, а ст имеет следующие простые свойства:

• ст(а + Ь) = ст(а) + тт(ЬУ
• тт(аЬ) = ст(а)ст(Ь).
• Если матрица Р над полем F _q то с( Р ) = Р .

Для возлома системы ГПТ криптоаналитик для некоторого целого числа и из открытого ключа G _pub = S [ У G k] Р сформировал расширенный ключ G _ext , _key следующим образом:

	^Gpub		S	[ У	G k ]	Р
	V^pub)		c( S )	[с( У )	^c( ^Gk ^)]	Р
^G ext, pub —	c2( G pub ) * * *	=	c²( S ) • • •	[т²( У ) • • •	т² ( G k )] •••	Р •••	. (6)
	т ( G pub)		c^u( S )	К(У)	c^u( G k)]	Р

Здесь использовано свойство, что ст( Р ) = Р, если матрица Р над полем Fq. Перепишите

эту матрицу так:	G ext,pub = S ext[ y ext G ext] P , (7)
где	S ext = Diag[ S c( S ) •••c^u(S)],

W ext =

У с( У )

•

i ^Gext =

G k c( G k )

•

• c^u( y )

•

. c^u( G k)_

Выбрать и = m — k — 1. (8)

Для матрицы k х ti

У = ■ У11 У21 • • У12 • У22 • * * • ^1,ti • Y2ti • • . (9) • . Kk,i * Kk,2 • • • ^k,tj удалить последнюю строку, получается матрица (к — 1) х ty

У 1 =

■ Y11

Y21

•

^Y 12 •

^Y22 •

1 1 1

• ^Y1,ti
• ^Y2,t1

•

. (10)

. Yk-yi

^Yk-1,2 •

• ^Y k-1,t1_

Из матрицы У удалить первую строку, получается матрица:

' Y21

^Y 22 •

• ^Y2,t1

У 2 =

•

^Y k-1,1

_ Yky

^Yk-1,2 •

^Yk,2 •

•

• ^Y k-1,ti
• ^Yk,t₁

(И)

Функция Т: F ^k ^ ^t 1 ^ F(k ^1)xt1, если У € F^¹ то g^N дім giN

Т ( У ) = W = а( У 1) — У 2

̃︀

S ext

W ext

^G _| PU = 0,

Пусть

Используя в виде У ^(у ) Wext = . . (12) • ^^-1(У) подходящие преобразования строк, можно переписать расширенный ключ ^ 5 Z | Gn-11 р Gpub,ext — Sext у^ | о P , V10/ где G,, 1 - порождающая матрица (т, т — 1, 2) МРР кода.

Найти решение систем уравнений:

где вектор-столбец u над полем F_g N длины ty + т. Представлять вектор Pu^T как:

PU = \ у Щ^Т .

Здесь вектор у имеет длину ty и вектор Һ имеет длину т. Тогда система (11) эквивалентна следующей системе:

Zy^T + g һ = о,

W ext y^T = 0.

Предположим, что выполнено следующее условие:

Rk( W ext I Fg N ) = t^

тогда уравнение (16) имеет только тривиальное решение у ^Т = 0. Следовательно, уравнение (15) примет вид

G _n -i h^T = 0.

Из этого можно найти первую строку проверочной матрицы для кода с порождающей матрицей (2). Затем вычислить вето матрицу.

3. Новая система Шики

В настоящее время найдены новые МРР-коды с частично разрушенной структурой. Порождающая матрица новых кодов может быть представлена в следующем виде:

( 5k =

/gi + ngf g ^q

q²

•

g2 ⁺ ng? •

g^q •

q²

92 •

„ , q„q^k\

• gm ⁺ ngm '

„ q

• gm

q²

• gm

•

. q ^k ^- ¹

\ gi

n n k — 1

g2q •

•

q ^-

• gm /

ч ^т - 1

G GF(q^mVn G GFq N (у) = у — = ( —1)^mk.

Проверочная матрица имеет такой вид:

/ h ^qk — у һ \ һ^

и = ^^к+" G GF(q^m).

Атака Овербека на новую систему Шики: Аналогично для системы ГПТ используется такой же подход к взломе кода Шики.

Из открытого ключа G _pub = S [ У G _k ] P сформирован расширенный ключ G _ext , _ke,_y следующим образом:

	^Gpub		S	[ У	G k ]	P
	^ ⁽ ^Gpub)		ct ( S )	[ст( У )	a( G k )]	P
^Gext, pub —	CT ² ( G pub ) •••	=	ct ² ( S )	[ст²( У )	CT ² ( ( 5k )]	P	. (19)
	CT^u ( G pub)		••• ct^u ( S )	••• К(У)	••• CT^u( G k)]	••• P

Здесь использовано свойство, что а(Р) = P, если матрица Р над полем Fq. Перепишем эту матрицу так:

Gext, pub — Sext [У ext Gext]P, где

S ext = Diag[ S ^( S ) •••^ ^u ( S )],

W ext =

У ст( У )

•

i ^Gext =

G k

CT( G k)

•

_ CT^u( y )_

•

L CT^u( G k)J

Выберем u — m — k — 1. Для матрипы k x t1

■ У11 У21 У = • • У12 • • • yi,ti У22 • • • y2,t1 « • • « • • • . ^k,1 « • • 1 k,2 1 k,ti_ удалив последнюю строку, получаем матрицу (k — 1) x t1:

У11 У12 • • • Y1,ti

У 1 =

У21 У22 • • • Y2t i

• • • •
• • • •
• • • •

_ Yk— 1,1 Yk— 1,2 • • • Yk—1,t1_

После удаления из матрицы Y первой строки, получается матрица

Пусть

W ext =

Y 2 =	' X21 • • •	Y22 ••• 1 • 1 • 1 •	Y2,ti " 1 1 1
Y 2 =	^Yk-i,i	^Yk-i,2 • • •	^Yk-i,t1
	. Yki	^Yk,2 • • •	Yyy .
Функция Т: F^¹ ^ Fqt^i)xt1,	если Y	G F^.to

Т( Y ) = W = a( Y 1) - Y 2

Y a( Y )

* * * a'^^Y )

Теорема 1. Для любих элементов а и b из GF(p^m-)

(а + b)^p = а^р + ЬР

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

Г* = S ^{Z Z} । ^Gml Р

^pub^ ^S ^W | 0 J ^ .

где G _m имеет следующий вид:
/ 9i + ngf		। q^k 92 ⁺ 992	1 q^k \ • • • 9m + 99m
	q	q	„ q
	9i	92	• • • 9m
	q²	q²	_q q²
	91 •	92 *	• • • ⁹m •
̃︀ ^Gm —	• • qfc-1	* * k-1	1 • q^{k —1}
	9i	92q ⁱ	• • • 9m
	_{q q}^k+" 1	_q _q^k+"1	q n q^k+1
	9І + »7^q 9І •	92 ⁺ 9 ^q 92 *	• • • 9m + 9^q 9m
	• • , _qm - k _nm-k _q ^m \9i + ^ 9i	* * _q ^m ^- k _qm-k _q ^m 92 ⁺ 9 92	1 • • •• 9m^m—k+9^qm—k 9m)

Требуется найти решение системы уравнений:

S_ext [_тTf | ^Gml Ри^г = 0, (21)

[W ext | 0 J , ^V '

где вектор-столбец и над полем F_q N длины ti + т. Представим вектор Ри^Т как

Ри^т = [ у һ ]^т .

Здесь векторы у и һ имеют длину ti и т соответственно. Тогда система (21) эквива лента следующей системе:

Zy^T + G т һ^т = 0,

W ext y^T = 0.

Предположим, что выполнено следующее условие:

Rk(W ext | FqN) = ti, тогда уравнение (23) имеет только тривиальное решение ут = 0. Следовательно, уравнение (22) примет вид

G _mh^T = о.

Например: Рассмотрим случай m = 7, t2 = 1,t = 2, k = 3, d = 5. При декодировании не используется матрица S, функция сигма от Р не меняет вид матрицы, поэтому здесь рассмотрим только часть расширенного ключа [ У G _k ].

В случае стандартной системы ГПТ они имеют следующий вид:

У =

Y11

У21

Y31

Y12

У22 , G k =

Y32

9q q2

. 91

9q q2

Для кода Шики:

"У11

Y12"

/ । q³

/ 91 ⁺ 991

92 + 99^q3 •

1 q³

• 97 ⁺ 997

У =

^Y21

У22

, ^Gext,pub — 1 ⁹1

9^q •

•• 9^q

. Y31

^32.

1 q²

\ 91

q²

92 •

q²

•• 97

При попытке взломать систему с помощью расширенного ключа для системы ГПТ:

[ У ext

^Gext] =

( ^Y11

У21

Y31 y q

^Y31

^Y3^q1

^Y31

^Yn ^{- Y}21

^Y2^{q - Y}31 у^q2 - y^q

^Jn ^Y21

vq² - v⁴

^Y21 ^Y31

' 3 - 4

k y& - y&

Y12

Y22

^Y 32 ү ^q

^Y32

_q2

^Y32

_q3

^Y32

^Y12 ^{— Y}22

^Y22 ^{— Y}32 у ^q ² _ y^q

^Y12 ^Y22

Y2 ^q 2 - Y3^q2

у^q3 _ y^q2

^Y12 ^Y22

ү^q3 _ y^q2

^Y22 ^Y32

91 9^q

q² 91

q³91

q⁴91

q⁵91

о о о о о о

92 • • •

_q q

92 • • •

q²

92 • • •

q³

92 • • •

q⁴

92 • • •

q⁵

92 • • •

0 •••

9^q

q²

q³

q⁴

q⁵

)

Для кода Шики:

^[У ext ^Gext] —

/ Y11

Y21

Y31

Y ^q

^Y11 y q

^Y31

2 ^v

^Y31 ^ү/ - ^Y31

\ ^Y' - ^V/

Y12

^Y22

^Y32

Y ^q

^Y12

Y ^q

^Y32

^Y>2

^Y 2 > 2 - ^Y’2

Y q - Y3^q2

91 + 99^q39^q

q²

9^{q +} 9^q 9^qi

Y 91 9q²+9^q2 9q⁵q⁴91

о о

92 + 99^q3 9^qq²

9^{q +} 9^q 9^ q³

9^q + 9^q2 9 ^q q⁴

···

97 + 99^q3

9^q

q²

9^{q +} 9^q 9^q4

q³

^q2 + 9^q2 9^q' q⁴

^⎞

Список литературы Криптосистема, основанная на новых ранговых кодах

Габидулин Э.М. Лекции по алгебраическому кодированию. M.: МФТИ, 2015.
Gabidulin E.M., Paramonov A.V., Tretjakov O.V. Ideals over a Non-commutative Ring and Their Application in Cryptology//Advances in Cryptology Eurocrypt’ 91. LNCS 547. 1991. P. 482-489.
Overbeck R. Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes//Journal of Cryptology. 2008. V. 21, N 2.

Статья научная