Криптосистема ГПТ (Габидулина-Парамонова-Третьякова ) — криптосистема с открытыми ключами , основанная на ранговых кодах [1] , разработанная в 1991 году Э. М. Габидулиным , А. В. Парамоновым и О. В. Третьяковым[2] на основе криптосистемы McEliece .
Данная криптосистема, в отличие от криптосистемы McEliece, более устойчива к атакам декодирования, а также имеет меньший размер ключа[3] , что лучше подходит в условиях практического применения.
Большинство версий системы были взломаны Р. Овербеком[4] .
Открытый текст
править
В качестве открытого текста может использоваться любой
k
{\displaystyle k}
-вектор
m
=
(
m
1
,
m
2
,
.
.
.
,
m
k
)
{\displaystyle m=(m_{1},m_{2},...,m_{k})}
,
m
s
∈
F
q
N
,
s
=
1
,
2
,
.
.
.
,
k
{\displaystyle m_{s}\in \mathbb {F} _{q^{N}},s=1,2,...,k}
.
Открытым ключом является порождающая матрица размера
k
×
(
n
+
t
1
)
{\displaystyle k\times (n+t_{1})}
:
G
p
u
b
=
S
[
X
{\displaystyle G_{pub}=S[X}
G
k
]
P
{\displaystyle G_{k}]P}
,
где:
G
k
{\displaystyle G_{k}}
— порождающая матрица
(
n
,
k
,
d
)
{\displaystyle (n,k,d)}
кода с максимальным ранговым расстоянием
d
{\displaystyle d}
для длины кода
n
≤
N
{\displaystyle n\leq N}
с количеством символов
k
{\displaystyle k}
, задающаяся матрицей следующей формы:
G
k
=
[
g
1
g
2
⋯
g
n
g
1
[
1
]
g
2
[
1
]
⋯
g
n
[
1
]
⋮
⋮
⋱
⋮
g
1
[
k
−
1
]
g
2
[
k
−
1
]
⋯
g
n
[
k
−
1
]
]
{\displaystyle G_{k}={\begin{bmatrix}g_{1}&g_{2}&\cdots &g_{n}\\g_{1}^{[1]}&g_{2}^{[1]}&\cdots &g_{n}^{[1]}\\\vdots &\vdots &\ddots &\vdots \\g_{1}^{[k-1]}&g_{2}^{[k-1]}&\cdots &g_{n}^{[k-1]}\end{bmatrix}}}
где
g
1
,
g
2
,
.
.
.
,
g
n
{\displaystyle g_{1},g_{2},...,g_{n}}
— любой набор элементов расширенного поля
F
q
N
{\displaystyle \mathbb {F} _{q^{N}}}
, линейно независимых над полем
F
q
{\displaystyle \mathbb {F} _{q}}
.
главная матрица
G
k
{\displaystyle G_{k}}
используется для исправления ошибок. Ошибки ранга не более
n
−
k
2
{\displaystyle {\tfrac {n-k}{2}}}
могут быть исправлены.
Cтроковый скремблер
S
{\displaystyle S}
— невырожденная квадратная матрица порядка
k
{\displaystyle k}
над полем
F
q
N
{\displaystyle \mathbb {F} _{q^{N}}}
X
{\displaystyle X}
— матрица искажений размера
(
k
×
t
1
)
{\displaystyle (k\times {t_{1}})}
над полем
F
q
N
{\displaystyle \mathbb {F} _{q^{N}}}
со столбцовым рангом
R
k
c
o
l
(
X
{\displaystyle Rk_{col}(X}
|
F
q
)
=
t
1
{\displaystyle \mathbb {F} _{q})=t_{1}}
и рангом
R
k
(
X
{\displaystyle Rk(X}
|
F
q
N
)
=
t
X
,
{\displaystyle \mathbb {F} _{q^{N}})=t_{X},}
t
X
≤
t
1
{\displaystyle t_{X}\leq t_{1}}
.
Матрица
[
X
{\displaystyle [X}
G
k
]
{\displaystyle G_{k}]}
имеет столбцовый ранг
R
k
c
o
l
(
[
X
{\displaystyle Rk_{col}([X}
G
k
]
{\displaystyle G_{k}]}
|
F
q
)
=
n
+
t
1
{\displaystyle \mathbb {F} _{q})=n+t_{1}}
.
Столбцовый скремблер
P
{\displaystyle P}
— квадратная матрица порядка
(
t
1
+
n
)
{\displaystyle (t_{1}+n)}
над полем
F
q
{\displaystyle \mathbb {F} _{q}}
.
t
1
+
n
{\displaystyle t_{1}+n}
может быть больше
N
{\displaystyle N}
, но
n
≤
N
{\displaystyle n\leq N}
.
В качестве закрытого ключа выступает набор
(
S
,
G
k
,
X
,
P
)
{\displaystyle (S,G_{k},X,P)}
, а также алгоритм быстрого декодирования МРР-кода, в котором используется матрица проверки четности
H
(
n
−
k
)
×
n
{\displaystyle H^{(n-k)\times n}}
, такая, что
G
k
H
T
=
0
:
{\displaystyle G_{k}H^{T}=0:}
H
=
[
h
1
h
2
⋯
h
n
h
1
[
1
]
h
2
[
1
]
⋯
h
n
[
1
]
⋮
⋮
⋱
⋮
h
1
[
d
−
2
]
h
2
[
d
−
2
]
⋯
h
n
[
d
−
2
]
]
{\displaystyle H={\begin{bmatrix}h_{1}&h_{2}&\cdots &h_{n}\\h_{1}^{[1]}&h_{2}^{[1]}&\cdots &h_{n}^{[1]}\\\vdots &\vdots &\ddots &\vdots \\h_{1}^{[d-2]}&h_{2}^{[d-2]}&\cdots &h_{n}^{[d-2]}\end{bmatrix}}}
,
где
h
1
,
h
2
,
.
.
.
,
h
n
{\displaystyle h_{1},h_{2},...,h_{n}}
— элементы расширенного поля
F
q
N
{\displaystyle \mathbb {F} _{q^{N}}}
, линейно независимые над основным полем
F
q
{\displaystyle \mathbb {F} _{q}}
Матрица
X
{\displaystyle X}
не используется для расшифровки криптотекста и может быть удалена после вычисления закрытого ключа.
Оптимальные параметры кода
править
Длина кода
n
≤
N
{\displaystyle n\leq N}
,
Размерность
k
=
n
−
d
+
1
{\displaystyle k=n-d+1}
,
Ранговое расстояние кода
d
=
n
−
k
+
1
{\displaystyle d=n-k+1}
Соответствующий открытому тексту криптотекст вычисляется следующим образом:
c
=
m
G
p
u
b
+
e
=
m
S
[
X
{\displaystyle c=mG_{pub}+e=mS[X}
G
k
]
P
+
e
{\displaystyle G_{k}]P+e}
,
где
e
{\displaystyle e}
— искусственный вектор ошибок ранга не выше
t
2
{\displaystyle t_{2}}
, причем
t
1
+
t
2
≤
t
=
⌊
n
−
k
2
⌋
{\displaystyle t_{1}+t_{2}\leq t=\lfloor {\tfrac {n-k}{2}}\rfloor }
.
Законный получатель, получая
c
{\displaystyle c}
, выполняет следующие действия:
Вычисляет
c
′
=
(
c
1
′
,
c
2
′
,
.
.
.
,
c
t
1
+
n
′
)
=
c
P
−
1
=
m
S
[
X
{\displaystyle c'=(c_{1}',c_{2}',...,c_{t_{1}+n}')=cP^{-1}=mS[X}
G
k
]
+
e
P
−
1
{\displaystyle G_{k}]+eP^{-1}}
Из
c
′
{\displaystyle c'}
выделяет подвектор
c
″
=
(
c
t
1
+
1
′
,
c
t
1
+
2
′
,
.
.
.
,
c
t
1
+
n
′
)
=
m
S
G
k
+
e
″
{\displaystyle c''=(c_{t_{1}+1}',c_{t_{1}+2}',...,c_{t_{1}+n}')=mSG_{k}+e''}
, где
e
″
{\displaystyle e''}
— подвектор
e
P
−
1
{\displaystyle eP^{-1}}
Применяет алгоритм быстрого декодирования для исправления ошибки
e
″
{\displaystyle e''}
Получает
m
S
{\displaystyle mS}
Восстанавливает
m
=
(
m
S
)
S
−
1
{\displaystyle m=(mS)S^{-1}}
В данной системе размер открытого ключа составляет
V
=
k
(
t
1
+
n
)
N
{\displaystyle V=k(t_{1}+n)N}
бит, а скорость передачи информации
R
=
k
t
1
+
n
{\displaystyle R={\tfrac {k}{t_{1}+n}}}
.
Автоморфизм Фробениуса
править
Введем автоморфизм Фробениуса :
σ
(
x
)
=
x
q
,
{\displaystyle \sigma (x)=x^{q},}
x
∈
F
q
N
{\displaystyle x\in \mathbb {F} _{q^{N}}}
. Он обладает следующими свойствами:
Для матрицы
L
=
(
l
i
j
)
{\displaystyle L=(l_{ij})}
над тем же полем
σ
(
L
)
=
(
σ
(
l
i
j
)
)
=
(
l
i
j
q
)
{\displaystyle \sigma (L)=(\sigma (l_{ij}))=(l_{ij}^{q})}
Для любого целого s :
σ
s
(
L
)
=
σ
(
σ
s
−
1
(
L
)
)
{\displaystyle \sigma ^{s}(L)=\sigma (\sigma ^{s-1}(L))}
σ
N
=
σ
{\displaystyle \sigma ^{N}=\sigma }
σ
−
1
=
σ
N
−
1
{\displaystyle \sigma ^{-1}=\sigma ^{N-1}}
σ
(
a
+
b
)
=
σ
(
a
)
+
σ
(
b
)
{\displaystyle \sigma (a+b)=\sigma (a)+\sigma (b)}
σ
(
a
b
)
=
σ
(
a
)
σ
(
b
)
{\displaystyle \sigma (ab)=\sigma (a)\sigma (b)}
В общем случае
σ
(
L
)
≠
L
{\displaystyle \sigma (L)\neq L}
. Равенство достигается, если
L
{\displaystyle L}
— матрица над основным полем
F
q
{\displaystyle \mathbb {F} _{q}}
Описание атаки Овербека[4]
править
Криптоаналитик вычисляет расширенный открытый ключ из открытого ключа:
G
e
x
t
,
p
u
b
=
‖
G
p
u
b
σ
(
G
p
u
b
)
⋯
σ
u
(
G
p
u
b
)
‖
=
‖
S
[
X
G
k
]
P
σ
(
S
)
[
σ
(
X
)
σ
(
G
k
)
]
P
⋯
⋯
⋯
⋯
σ
u
(
S
)
[
σ
u
(
X
)
σ
u
(
G
k
]
P
‖
{\displaystyle G_{ext,pub}={\begin{Vmatrix}G_{pub}\\\sigma (G_{pub})\\\cdots \\\sigma ^{u}(G_{pub})\end{Vmatrix}}={\begin{Vmatrix}S&[X&G_{k}]&P\\\sigma (S)&[\sigma (X)&\sigma (G_{k})]&P\\\cdots &\cdots &\cdots &\cdots \\\sigma ^{u}(S)&[\sigma ^{u}(X)&\sigma ^{u}(G_{k}]&P\end{Vmatrix}}}
Здесь использовано свойство 7 автоморфизма Фробениуса:
σ
(
P
)
=
P
{\displaystyle \sigma (P)=P}
, так как
P
{\displaystyle P}
— матрица над основным полем
F
q
{\displaystyle \mathbb {F} _{q}}
.
Переписывает эту матрицу как
G
e
x
t
,
p
u
b
=
S
e
x
t
[
X
e
x
t
{\displaystyle G_{ext,pub}=S_{ext}[X_{ext}}
G
e
x
t
]
{\displaystyle G_{ext}]}
,
где
S
e
x
t
=
d
i
a
g
[
S
σ
(
S
)
⋯
σ
u
(
S
)
]
{\displaystyle S_{ext}=diag{\begin{bmatrix}S&\sigma (S)&\cdots &\sigma ^{u}(S)\end{bmatrix}}}
,
X
e
x
t
=
[
X
σ
(
X
)
⋮
σ
u
(
X
)
]
{\displaystyle X_{ext}={\begin{bmatrix}X\\\sigma (X)\\\vdots \\\sigma ^{u}(X)\end{bmatrix}}}
,
G
e
x
t
=
[
G
k
σ
(
G
k
)
⋮
σ
u
(
G
k
)
]
{\displaystyle G_{ext}={\begin{bmatrix}G_{k}\\\sigma (G_{k})\\\vdots \\\sigma ^{u}(G_{k})\end{bmatrix}}}
.
Выбирает
u
=
n
−
k
−
1
{\displaystyle u=n-k-1}
.
Определяет матрицы:
X
1
(
k
−
1
×
t
1
)
{\displaystyle X_{1}^{(k-1\times t_{1})}}
, получаемая из
X
(
k
×
t
1
)
{\displaystyle X^{(k\times t_{1})}}
удалением последней строки,
X
2
(
k
−
1
×
t
1
)
{\displaystyle X_{2}^{(k-1\times t_{1})}}
, получаемая из
X
(
k
×
t
1
)
{\displaystyle X^{(k\times t_{1})}}
удалением первой строки.
Определяет линейное отображение
T
{\displaystyle T}
:
F
q
N
k
×
t
1
→
F
q
N
(
k
−
1
)
×
t
1
{\displaystyle \mathbb {F} _{q^{N}}^{k\times t_{1}}\rightarrow \mathbb {F} _{q^{N}}^{(k-1)\times t_{1}}}
по следующему правилу:
если
X
∈
F
q
N
k
×
t
1
{\displaystyle X\in \mathbb {F} _{q^{N}}^{k\times t_{1}}}
, тогда
T
(
X
)
=
Y
=
σ
(
X
1
)
−
X
2
{\displaystyle T(X)=Y=\sigma (X_{1})-X_{2}}
Записывает
Y
e
x
t
=
[
Y
σ
(
Y
)
σ
2
(
Y
)
⋯
σ
u
−
1
(
Y
)
]
⊤
{\displaystyle Y_{ext}={\begin{bmatrix}Y&\sigma (Y)&\sigma ^{2}(Y)&\cdots &\sigma ^{u-1}(Y)\end{bmatrix}}^{\top }}
С помощью матричных преобразований приводит расширенный открытый ключ к виду:
G
~
p
u
b
,
e
x
t
=
S
~
e
x
t
[
Z
|
G
n
−
1
Y
e
x
t
|
0
]
P
{\displaystyle {\widetilde {G}}_{pub,ext}={\widetilde {S}}_{ext}{\begin{bmatrix}Z&|&G_{n-1}\\Y_{ext}&|&0\end{bmatrix}}P}
где
G
n
−
1
{\displaystyle G_{n-1}}
— порождающая матрица
(
n
,
n
−
1
,
2
)
{\displaystyle (n,n-1,2)}
МРР-кода.
Пробует найти решение системы
S
~
e
x
t
=
[
Z
|
G
n
−
1
Y
e
x
t
|
0
]
P
u
T
=
0
{\displaystyle {\widetilde {S}}_{ext}={\begin{bmatrix}Z&|&G_{n-1}\\Y_{ext}&|&0\end{bmatrix}}Pu^{T}=0}
,
где
u
{\displaystyle u}
— вектор-строка над расширенным полем
F
q
N
{\displaystyle \mathbb {F} _{q^{N}}}
длины
t
1
+
n
{\displaystyle t_{1}+n}
Представляет вектор
P
u
T
{\displaystyle Pu^{T}}
в виде:
P
u
T
=
[
y
h
]
⊤
{\displaystyle Pu^{T}={\begin{bmatrix}y&h\end{bmatrix}}^{\top }}
где
y
{\displaystyle y}
— подвектор длины
t
1
{\displaystyle t_{1}}
, а
h
{\displaystyle h}
— длины
n
{\displaystyle n}
Теперь система уравнений эквивалентна следующей:
{
Z
y
T
+
G
n
−
1
h
T
=
0
,
Y
e
x
t
y
T
=
0
{\displaystyle {\begin{cases}Zy^{T}+G_{n-1}h^{T}=0,\\Y_{ext}y^{T}=0\end{cases}}}
Полагая верным условие
R
k
(
Y
e
x
t
|
F
q
N
)
=
t
1
{\displaystyle Rk(Y_{ext}|\mathbb {F} _{q^{N}})=t_{1}}
, видим, что указанная выше система имеет только тривиальное решение
y
T
=
0
{\displaystyle y^{T}=0}
. Следовательно, первое уравнение из системы преобразуется к виду:
G
n
−
1
h
T
=
0
{\displaystyle G_{n-1}h^{T}=0}
.
Это позволит найти первую строку матрицы проверки четности для кода с данной порождающей матрицей
G
~
p
u
b
,
e
x
t
{\displaystyle {\widetilde {G}}_{pub,ext}}
.
Следовательно, это решение взламывает описанную криптосистему за полиномиальное время. Атака Овербека требует
O
(
(
n
+
t
1
)
3
)
{\displaystyle O((n+t_{1})^{3})}
операций над полем
F
q
N
{\displaystyle \mathbb {F} _{q^{N}}}
, так как каждый шаг атаки имеет сложность не выше кубической на
n
+
t
1
{\displaystyle n+t_{1}}
.
↑ Габидулин Э. М. Теория кодов с максимальным ранговым расстоянием (недоступная ссылка) // Пробл. передачи информ. Архивная копия от 20 декабря 2016 на Wayback Machine — 1985. — Т. 21, вып. 1. — С. 3—16.
↑ Gabidulin E.M., Paramonov A.V., Tretjakov O.V. Ideals over a Non-commutative Ring and Their Application in Cryptology Архивная копия от 16 сентября 2018 на Wayback Machine // Advances in Cryptology Архивная копия от 3 июня 2018 на Wayback Machine — Eurocrypt ’91, LNCS 547, 1991, pp. 482—489.
↑ Khan E., Gabidulin E. M., Honary B., Ahmed H. Modified Niederreiter type of GPT Cryptosystem based on Reducible Rank Codes Архивная копия от 9 июня 2018 на Wayback Machine // et al. Des. Codes Cryptogr. (2014) 70: 231. — ISSN 0925-1022
↑ 1 2 Overbeck R. Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes Архивная копия от 1 марта 2018 на Wayback Machine // Journal of Cryptology : volume 21, number 2, april 2008 — ISSN 0933-2790
Габидулин Э. М., Пилипчук Н. И., Хонари Б., Рашван Х. Защита информации в сети со случайным сетевым кодированием // Пробл. передачи информ. , 2013, том 49, выпуск 2, 92-106
Gadouleau M., Yan Zh. Security of GPT-type cryptosystems // Proc. 2006 IEEE Int. Sympos. on Information Theory (ISIT’2006) . — ISIT.2006.261627
Rashwan H., Gabidulin E.M., Honary B. A smart approach for GPT Cryptosystem Based on Rank Codes // Proc. 2010 IEEE Int. Sympos. on Information Theory (ISIT’2010). Austin, Texas, USA. June 13-18, 2010. P. 2463—2467.
Kshevetskiy A.S. Security of GPT-like cryptosystems based on linear rank codes // Signal Design and Its Applications in Communications, 2007. IWSDA 2007 . On page(s): 143—147.
Ourivski A. V., Gabidulin E. M. Column Scrambler for the GPT Cryptosystem // Discrete Applied Mathematics.128(1): 207—221 (2003).
Overbeck R. Extending Gibson’s attacks on the GPT cryptosystem // In Proc. of WCC 2005, volume 3969 of LNCS, pp. 178—188, Springer Verlag,2006.