Использование модифицированной (U|U+V)-конструкции в криптосистеме McEliece

Криптосистема. McEliece, предложенная в 1978 году [1], является одним из возможных кандидатов для постквантовой криптографии [2].

Криптосистема. McEliece может быть описана, следующим образом [1].

Для генерации ключа выбирается линейный щичный (п, к, Д-код C с порождающей матрицей G, для которого известен эффективный алгоритм декодирования ошибок, весом не более t. Выбираются случайные невырожденные к хк матрица S и п х п перестановочная матрица Р. В качестве открытого ключа системы публикуется матрица G = S • G • Р. Закрытым ключом системы являются алгоритм декодирования кода C и матрицы S, и Р.

Криптосистема, характеризуется следующими параметрами:

Размер открытого ключа: PublicKepSizeo = PKSo = п • к.

Скорость кода: Ro = ^.

Для шифрования сообщения т, представленного в виде щичного вектора длины к выбирается случайный щинпый вектор е длины п веса не более t. Шифротекет рассчитывается по формуле:

c = т •G + е.                                   (1)

Для расшифрования сообщения c пользователь вычисляет С = c • Р ^-1, декодирует С алгоритмом декодирования для кода C: С ^ {ж, е} : С = ж • G + ей получает т = ж • S^-1.

«Московский физико-технический институт (государственный университет)», 2018

Оригинальная криптосистема McEliece была построена на кодах Ронны [1]. Впоследствии для увеличения скорости работы или уменьшения размеров ключей криптосистемы было предложено использовать другие коды, например коды Рида-Маллера [4], обобщенные коды Рида-Соломона [3], LDPC-коды [5] и другие. Однако для многих из предложенных вариантов криптосистемы были найдены атаки на структуру матрицы G, позволяющие вычислить закрытый ключ из открытого. Все эти атаки использовали различные особенности данных кодов. Так, атаки на криптосистему McEliece, построенную на кодах Рида-Маллера [6] или на полярных кодах [8], использовали поиск слов кода минимального веса.

Для защиты от подобных атак в нескольких работах [4] [7] было предложено использовать (и|и+У)-конструкцию и ее модификации. Данная конструкция позволяет создать код длины п из двух кодов U и V длины ^ каждый:

(U |U + V) = {(u|u + г) : Vu Е U, Vr Е V }.

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

Gu Gu

О Gv

)• ^р

матриц Gu и Gv кодов U и V из пуо.тичпого ключа - матрицы G = S •

Данная задача считается вычислительно сложной, а при использовании случайных кодов является NP-сложной [9]. В общем же случае ее принадлежность к классам Р или NP не была доказана.

Недостатком использования (и|и+У)-конструкции в криптосистеме McEliece является увеличение размеров ключей системы по сравнению с размерами ключей оригинальной системы McEliece той же криптостойкости. Так, при использовании (U|U+V) конструкции получатся следующие параметры криптосистемы:

Размер открытого ключа: PKS = 4 • п - к = 4 • PKSo.

Скорость кода: R = 2| = Ro-

2.    Модификация (U|U+V) конструкции

Для уменьшения размера порождающей матрицы (U|U+V) кода можно рассмотреть ряд модификаций.

Пусть C - (п, к, d) щичный код с порождающей матрицей G и эффективным алгоритмом декодирования ошибок веса менее t. Пусть K - случайная матрица размером L х п.

G\

Можно задать K так. чт<>бы код C. заданный порождающей матрицей G = I к ) ^(<11>1Л

(п, k + L,do < d)-KO4OM.

Если В - порождающая матрипа случайного (m,L,dp ) кода, то код D. заданный порождающей матрицей

^=(GB),

будет иметь минимальное расстояние:

dj > min(d, do + dp ).

Чтобы dj >  d. необходимо потребовать, чтобы было выполнено условие do + dp >  d. то есть чтобы выполнялось следующее условие:

d > d_B > d — d₀ >

Если B - код с максимальным кодовым расстоянием, например, код Рида-Соломона, то m — L + 1 = dp- В этом случае m = L + dp — 1- и потому

L + d — 1 > m > L + ^ — 1.

Пусть B - (L+d— 1, L, db > d) код. Код D с порождающей матрицей J, заданной согласно (2), может исправить не менее t ошибок по следующему алгоритму декодирования:

Пусть принято сообщение с = xJ + е, wt(е) < t.

• 1)    с представляется в виде: с = (2^22). ял ина 2i равна, п:

• 2)    Перебираются все вектора е, - щичные последовательности длины L;

• 3)    Для каждого е, вычисляется в, = 2i — е,К'

• 4)    в, декодируется по а.тгоритму для кода C: в, = u,G + Д; wt(^,) < t:

• 5)    Если вес вектора Д = (Д, 122 — е, В) меньше t, то x = (и, |е,), е = Д иначе повторяются пп. 2-5.

3.    Использование модифицированной (U|U+V) конструкциив криптосистеме McEliece

С учетом (3) и параметров выбранного кода B, расстояние кода D больше d и поэтому в результате работы алгоритма, декодирования всегда, найдется единственное решение.

Предложенный алгоритм декодирования по сложности в q^L раз хуже алгоритма декодирования кода C.

Способ построения кода D из C назван КА-схемой.

Пусть А - случайная матрица. размром k х L.

Можно заметить, что подкод Di ко да D, заданный порождающей матрицей Ji = G + АК АВ). имеет расстояние не меньше d. При этом код может исправить не менее t ошибок по следующему алгоритму декодирования:

Пусть принято сообщение с = xJi + е, wt(е) <  t.

• 1)    с представляется в виде: с = (zi |22), длина 21 равна п.

• 2)    Перебираются все вектора е, - q-ичные последовательности длины L.

• 3)    Для каждого е, вычис.тястся в, = 21 — е,К.

• 4)    в, декодируется по ачгорнтму для кода С: в, = u,G + Д,, wt(^,) <  t.

• 5)    Если вес вектора Д = (Д, |22 — и, АВ) меньше t, то x = ui е = Д иначе повторяются пп. 2-5.

При использовании в криптосистеме McEliece кода Di, построенного при помощи предложенной KA-схемы, открытым ключом будет являться матрица.

J = S •Ji •Р = S • (G + АК АВ) • Р.                      (4)

При этом для осуществления структурных атак на. систему необходимо отделить столбцы матриц G + АК от АВ и слова кода, заданные матрицей G от слов, заданных матрицей АК.

Без зшгпия Р вероятность случайного выбора одного столона матрицы АВ    _n +L+d — i

⁽ L + d - 1 )

Значит, при случайном выборе столбцов в среднем потребуется полиномиальное (от п)

число попыток для нахождения одного столбца матрицы АВ.

Решение второй задачи - отделения слов кода, заданных матрицей G от слов, заданных матрицей АК. - сводится к выделению ядра отображения ^д. 'заданного матрицей А. так как:

Va Е Кет^_А : a • (G + АК ) = a •G Е C.

При случайном выборе матриц А, К и В, это возможно сделать только перебором всех векторов пространства F_qk, что требует порядка (^_L) операций и, потому, является вычислительно сложной задачей.

Значит, структурные атаки на открытый ключ системы будут вычислительно сложными, при этом схема будет обладать следующими параметрами:

PKS = (п + L + d — 1) • k = п •к • (1 +---1--) = PKSo • (2 — Ro +);

п п

R =---т7— = Ro •г— • п + L + d - 1     2 — Ro +——

4.    Модификация криптосистемы McEliece

С учетом предложенных идей можно предложить и следующую модификацию криптосистемы McEliece:

Пусть C - (п, к, d) щичный код с порождающей матрицей G и эффективным алгоритмом декодирования ошибок веса менее t. Для генерации ключей выбираются случайные матрицы А и К размером к xL и Lxп соответственно, случайные невырожденные матрицы S и Р, размером к хк и п хп соответственно. Пусть h(^) - криптографически стойкая хэш-функция.

В качестве открытого ключа публикуется матрица G = S(G + АК)Р и хэш-функция

Для шифрования сообщения т, представленного в виде щичного вектора длины к выбирается случайный щпчиый вектор е длины п веса не более t. Шифротекет рассчитывается по формуле:

с = (mG + е||Дт||е)).

Для расшифрования сообщения с:

• 1)    Вычисляется с = сР^—1 = (сі |с2), длина сі равна п.

• 2)    Перебираются все вектора еі - q-ичные последовательности длины L.

• 3)    Для каждого еі вычисляется di = сі — е^К.

• 4)    di декодируется по а.тгоритму для кода C: di = x_iG + ^i, wt(^_i)< t.

• 5)    Если с2 = Һ(хі,^і), то вычисляется т = XiS^—1, иначе повторяются пп. 2-5.

5.    Заключение

Предложена модификация (U|U+V) конструкции, позволяющая использовать любые коды в криптосистеме McEliece без существенной потери производительности и увеличения размеров ключей криптосистемы по сравнению с криптосистемами McEliece на тех же кодах, не использующих модификаций. При этом увеличивается стойкость криптосистемы к структурным атакам на открытый ключ.

По сравнению с криптосистемой McEliece, использующей (U|U+V) конструкцию, предложенная модификация позволяет существенно уменьшить размеры ключей криптосистемы.