Русская Википедия:Криптосистема ГПТ

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Криптосистема ГПТ (Габидулина-Парамонова-Третьякова) — криптосистема с открытыми ключами, основанная на ранговых кодах, разработанная в 1991 году Э. М. Габидулиным, А. В. Парамоновым и О. В. Третьяковым на основе криптосистемы McEliece.

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

Большинство версий системы были взломаны Р. Овербеком.

Описание

Открытый текст

В качестве открытого текста может использоваться любой <math>k</math>-вектор <math>m = (m_1, m_2,...,m_k) </math>, <math> m_s \in \mathbb F_{q^N}, s = 1,2,...,k</math>.

Открытый ключ

Открытым ключом является порождающая матрица размера <math> k \times (n + t_1)</math>:

<math>G_{pub} = S[X</math> <math>G_k]P</math>,

где:

• <math>G_k</math> — порождающая матрица <math>(n, k, d)</math> кода с максимальным ранговым расстоянием <math>d</math> для длины кода <math>n \le N</math> с количеством символов <math>k</math>, задающаяся матрицей следующей формы:
  

<math>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} </math>

где <math>g_1, g_2,..., g_n</math> — любой набор элементов расширенного поля <math> \mathbb F_{q^N}</math>, линейно независимых над полем <math> \mathbb F_q</math>.

главная матрица <math>G_k</math> используется для исправления ошибок. Ошибки ранга не более <math>\tfrac{n-k}{2}</math> могут быть исправлены.

• Cтроковый скремблер <math>S</math> — невырожденная квадратная матрица порядка <math>k</math> над полем <math> \mathbb F_{q^N}</math>
• <math>X</math> — матрица искажений размера <math>(k \times {t_1})</math> над полем <math> \mathbb F_{q^N}</math> со столбцовым рангом <math>Rk_{col}(X</math> | <math>\mathbb F_q) = t_1 </math> и рангом <math> Rk(X</math> | <math>\mathbb F_{q^N}) = t_X,</math> <math> t_X \le t_1</math>.
  

Матрица <math>[X</math> <math>G_k]</math> имеет столбцовый ранг <math>Rk_{col}([X</math> <math>G_k]</math> | <math>\mathbb F_q) = n + t_1 </math>.

• Столбцовый скремблер <math>P</math> — квадратная матрица порядка <math>(t_1 + n)</math> над полем <math> \mathbb F_q</math>.
• <math>t_1 + n</math> может быть больше <math>N</math>, но <math>n \le N</math>.

Закрытый ключ

В качестве закрытого ключа выступает набор <math>(S, G_k, X, P)</math>, а также алгоритм быстрого декодирования МРР-кода, в котором используется матрица проверки четности <math>H^{(n-k) \times n}</math>, такая, что <math>G_kH^T = 0:</math>

<math>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}</math>,

где <math>h_1, h_2, ..., h_n</math> — элементы расширенного поля <math>\mathbb F_{q^N}</math>, линейно независимые над основным полем <math>\mathbb F_q</math>

Матрица <math>X</math> не используется для расшифровки криптотекста и может быть удалена после вычисления закрытого ключа.

Оптимальные параметры кода

• Длина кода <math>n \le N</math>,
• Размерность <math>k = n - d + 1</math>,
• Ранговое расстояние кода <math>d = n - k + 1</math>

Шифрование

Соответствующий открытому тексту криптотекст вычисляется следующим образом:

<math> c = mG_{pub} + e = mS[X</math> <math> G_k]P + e</math>,

где <math>e</math> — искусственный вектор ошибок ранга не выше <math>t_2</math>, причем <math> t_1 + t_2 \le t = \lfloor \tfrac{n-k}{2} \rfloor</math>.

Дешифрование

Законный получатель, получая <math> c </math>, выполняет следующие действия:

1. Вычисляет <math> c' = (c_1', c_2',...,c_{t_1+n}') = cP^{-1} = mS[X</math> <math>G_k] + eP^{-1}</math>
2. Из <math> c'</math> выделяет подвектор <math>c = (c_{t_1+1}', c_{t_1+2}',..., c_{t_1+n}') = mSG_k + e</math>, где <math>e</math> — подвектор <math>eP^{-1}</math>
3. Применяет алгоритм быстрого декодирования для исправления ошибки <math>e</math>
4. Получает <math>mS</math>
5. Восстанавливает <math>m = (mS)S^{-1}</math>

В данной системе размер открытого ключа составляет <math>V = k(t_1+n)N</math> бит, а скорость передачи информации <math> R=\tfrac {k} {t_1+n}</math>.

Взлом

Автоморфизм Фробениуса

Введем автоморфизм Фробениуса: <math> \sigma(x) = x^q, </math> <math>x \in \mathbb F_{q^N}</math>. Он обладает следующими свойствами:

1. Для матрицы <math>L = (l_{ij})</math> над тем же полем <math> \sigma(L) = (\sigma (l_{ij})) = (l_{ij}^q)</math>
2. Для любого целого s: <math>\sigma^s(L) = \sigma (\sigma^{s-1}(L))</math>
3. <math>\sigma^N = \sigma</math>
4. <math>\sigma^{-1} = \sigma^{N-1}</math>
5. <math>\sigma(a+b) = \sigma(a) + \sigma(b)</math>
6. <math>\sigma(ab) = \sigma(a)\sigma(b)</math>
7. В общем случае <math>\sigma(L) \ne L</math>. Равенство достигается, если <math>L</math> — матрица над основным полем <math>\mathbb F_q</math>

Описание атаки Овербека

• Криптоаналитик вычисляет расширенный открытый ключ из открытого ключа:
  

<math> 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}</math>

Здесь использовано свойство 7 автоморфизма Фробениуса: <math>\sigma(P) = P</math>, так как <math>P</math> — матрица над основным полем <math>\mathbb F_q</math>.

• Переписывает эту матрицу как <math>G_{ext, pub} = S_{ext} [X_{ext}</math> <math> G_{ext}]</math>,
  

где

<math> S_{ext} = diag \begin{bmatrix} S & \sigma(S) & \cdots & \sigma^u(S) \end{bmatrix} </math>,

<math> X_{ext} = \begin{bmatrix} X \\ \sigma(X) \\ \vdots \\ \sigma^u(X)\end{bmatrix}</math>, <math> G_{ext} = \begin{bmatrix} G_k \\ \sigma(G_k) \\ \vdots \\ \sigma^u(G_k)\end{bmatrix}</math>.

• Выбирает <math> u = n - k - 1</math>.
  
• Определяет матрицы:
  

<math>X_1^{(k-1 \times t_1)}</math>, получаемая из <math>X^{(k \times t_1)}</math> удалением последней строки,

<math>X_2^{(k-1 \times t_1)}</math>, получаемая из <math>X^{(k \times t_1)}</math> удалением первой строки.

• Определяет линейное отображение <math> T </math>: <math>\mathbb F_{q^N}^{k \times t_1} \rightarrow \mathbb F_{q^N}^{(k-1) \times t_1}</math> по следующему правилу:

если <math> X \in \mathbb F_{q^N}^{k \times t_1} </math>, тогда <math> T(X) = Y = \sigma(X_1) - X_2</math>

• Записывает <math> Y_{ext} = \begin{bmatrix} Y & \sigma(Y) & \sigma^2(Y) & \cdots & \sigma^{u-1}(Y) \end{bmatrix} ^{\top} </math>
  

• С помощью матричных преобразований приводит расширенный открытый ключ к виду:
  

<math> \widetilde {G}_{pub, ext} = \widetilde {S}_{ext} \begin{bmatrix} Z & | & G_{n-1} \\ Y_{ext} & | & 0 \end{bmatrix} P</math>

где <math>G_{n-1}</math> — порождающая матрица <math>(n, n-1, 2)</math> МРР-кода.

• Пробует найти решение системы

<math> \widetilde {S}_{ext} = \begin{bmatrix} Z & | & G_{n-1} \\ Y_{ext} & | & 0 \end{bmatrix} Pu^T = 0</math>,

где <math>u</math> — вектор-строка над расширенным полем <math>\mathbb F_{q^N}</math> длины <math> t_1 + n</math>

• Представляет вектор <math>Pu^T</math> в виде:
  

<math>Pu^T = \begin{bmatrix} y & h\end{bmatrix}^{\top} </math>

где <math>y</math> — подвектор длины <math>t_1</math>, а <math>h</math> — длины <math>n</math>

• Теперь система уравнений эквивалентна следующей:
  

<math>\begin{cases}

 Zy^T + G_{n-1}h^T = 0,\\
 Y_{ext}y^T = 0

\end{cases}</math>

• Полагая верным условие <math>Rk(Y_{ext}|\mathbb F_{q^N}) = t_1</math>, видим, что указанная выше система имеет только тривиальное решение <math>y^T = 0</math>. Следовательно, первое уравнение из системы преобразуется к виду:

<math>G_{n-1}h^T = 0</math>.

Это позволит найти первую строку матрицы проверки четности для кода с данной порождающей матрицей <math> \widetilde {G}_{pub, ext} </math>. Следовательно, это решение взламывает описанную криптосистему за полиномиальное время. Атака Овербека требует <math>O((n+t_1)^3)</math> операций над полем <math>\mathbb F_{q^N}</math>, так как каждый шаг атаки имеет сложность не выше кубической на <math>n+t_1</math>.

Литература

• Габидулин Э. М., Пилипчук Н. И., Хонари Б., Рашван Х. Защита информации в сети со случайным сетевым кодированием // Пробл. передачи информ., 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.