Схема постквантовой электронной цифровой подписи на основе усиленной формы скрытой задачи дискретного логарифмирования – тема научной статьи по математике читайте бесплатно текст научно-исследовательской работы в электронной библиотеке КиберЛенинка

Схема постквантовой электронной цифровой подписи на основе усиленной формы скрытой задачи дискретного логарифмирования

УДК 512.552.18 003.26 Вестник СПбГУ. Прикладная математика. Информатика… 2021. Т. 15. Вып. 2 МБС 16Р10

Схема постквантовой электронной цифровой подписи на основе усиленной формы скрытой задачи дискретного логарифмирования

Н. А. Молдовян, И. К. Абросимов

Санкт-Петербургский институт информатики и автоматизации Российской академии наук, Российская Федерация, 199178, Санкт-Петербург, 14-я линия В. О., 39

Для цитирования: Молдовян Н. А., Абросимов И. К. Схема постквантовой электронной цифровой подписи на основе усиленной формы скрытой задачи дискретного логарифмирования // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2021. Т. 15. Вып. 2. С. 212-220. https://doi.org/10.21638/11702/spbu10.2021.205

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

Ключевые слова: постквантовая криптография, криптографический примитив, электронная подпись, конечная алгебра, некоммутативная ассоциативная алгебра.

Введение. Базой для криптографических преобразований, используемых для построения схем электронной цифровой подписи (ЭЦП), служат задачи факторизации и дискретного логарифмирования [1]. Безопасность применения данных схем учитывает то, что в настоящее время асимптотическая сложность наиболее эффективных алгоритмов решения этих задач для классических компьютеров — субэкспоненциальная. Предпринимаются попытки построения квантового компьютера, на котором такие задачи решаются значительно быстрее. В 1994 г. Шорр предложил алгоритм, позволяющий решить обе задачи за полиномиальное время [2]. Поэтому в случае появления квантового компьютера с достаточным числом кубитов можно будет быстро решать задачи факторизации и дискретного логарифмирования и основывающиеся на них криптосхемы окажутся нестойкими. Для сохранения всех возможных приложений криптографии с открытым ключом требуется нахождение новых вычислительно трудных задач, для решения которых как на классическом, так и на квантовом компьютерах существовали бы алгоритмы сверхполиномиальной сложности. Криптографические схемы, которые являются стойкими к атакам с применением квантового компьютера, и вычислительно трудные задачи, на которых они основаны, принято относить к постквантовой криптографии [3].

Нельзя утверждать, что создание квантового компьютера приведет к потере всех возможностей двухключевой криптографии, поскольку существует набор криптосистем, базирующихся на вычислительно трудных задачах, отличных от задач факторизации и дискретного логарифмирования. К постквантовым двухключевым криптографическим алгоритмам относятся [3] основанные на: 1) хэш-функциях; 2) кодах ис-

© Санкт-Петербургский государственный университет, 2021

правления ошибок; 3) решетках; 4) многомерных квадратичных системах. Примерами этих криптосистем соответственно могут служить подпись Меркла [4], криптосистема Мак-Элиса [5], криптосистема МТИ,иЕпсгур1 [6] и криптосистема на основе скрытых уравнений поля [7]. Однако они не вытеснили криптосистемы, базирующиеся на вычислительной трудности задач факторизации и дискретного логарифмирования, из-за недостаточной универсальности и больших длин ключа для обеспечения практических уровней безопасности (в частности, для 128-битовой стойкости в криптосистеме Мак-Элиса требуются ключи, размер которых порядка миллиона бит). Под недостаточной универсальностью криптосистемы здесь понимается то, что с ее помощью можно построить не все основные алгоритмы и протоколы двухключевой криптографии, а только какую-то их часть. Потому продолжается поиск новых вычислительно трудных задач, которые могут стать базой для постквантовых криптографических алгоритмов. По тематике постквантовой криптографии регулярно проводятся конференции [8]. Национальным институтом стандартов и технологий США был объявлен конкурс на разработку постквантовых криптоалгоритмов, которые базируются на новых вычислительно трудных задачах [9].

При поиске постквантовых криптографических примитивов значительное внимание уделяется некоммутативным алгебраическим структурам. Изучался вопрос о создании криптосхем, базирующихся на вычислительной трудности сопрягающего элемента в группах переплетений [10], однако в статье [11] были показаны сводимость этой задачи к задаче решения систем линейных уравнений и наличие принципиальных трудностей для обеспечения приемлемой стойкости. Более перспективным представляется использование задачи дискретного логарифмирования в скрытой циклической группе конечной ассоциативной алгебры с некоммутативной операцией умножения [12-15], называемой еще скрытой задачей дискретного логарифмирования. Но известная форма задания скрытой задачи дискретного логарифмирования позволяет разработать протокол открытого согласования ключа и алгоритм открытого шифрования [16], но не подходит для построения схем ЭЦП.

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

Постановка скрытой задачи дискретного логарифмирования и ее новая форма. В конечной некоммутативной группе Г автоморным отображением является отображение, задаваемое формулой

фи(д) = и о д о и-1,

где и € Г фиксирован; элемент д пробегает все элементы группы Г.

Для построения криптосхем на основе конечных некоммутативных ассоциативных алгебр необходимо наличие взаимной коммутативности операций возведения в степень и сопряжения через элемент и:

Ри(дх) = (у>и (д))х.

Впервые задача скрытого дискретного логарифмирования была сформулирована следующим образом [13]: по заданным у = и о дх о и-1 и д требуется вычислить и и х.

Такая форма может быть использована для создания протоколов открытого распределения ключей и схем открытого шифрования. Новая форма задачи ориентирована на создание ЭЦП, так как в схеме ЭЦП возможно, чтобы каждый владелец открытого ключа мог применить свою циклическую группу. Генератором такой группы предлагается необратимый вектор конечной некоммутативной ассоциативной алгебры векторов. Как пример такой алгебры рассмотрим модифицированную алгебру кватернионов, заданную над простым конечным полем GF(p).

Операции в четырехмерных алгебрах. Пусть четырехмерные векторы заданы над полем GF(p), где р — простое число. Тогда каждый вектор V = (а, Ь, с, ¿) может быть записан в виде линейной комбинации базисных векторов е, г, к:

V = ае Ьг се ¿к.

Операции сложения, вычитания и умножения на скаляр четырехмерных векторов осуществляются обычным образом — покоординатно:

ал ± ви = (а.а,1 ± ва2)е (аЬ ± [ЗЬ2)г (ас1 ± вс2)е (а^1 ± )к.

На множестве четырехмерных векторов над конечным полем можно ввести операцию векторного умножения таким образом:

шаг 1 — представить каждый вектор-сомножитель как линейную комбинацию базисных векторов, коэффициенты которой являются координатами этого вектора:

V о и = (а,1в Ь1 г С1е ¿1к) о (а2в Ь2 г С2е ¿2к);

шаг 2 — перемножить получившиеся две линейные комбинации путем раскрытия скобок; в результате находим сумму произведений каждого слагаемого первой линейной комбинации на каждое слагаемое второй линейной комбинации:

V о и = а1а2(е о е) аЬ2(ё о г) ••• ¿^,2(к о к);

шаг 3 — выполнить перемножение получившихся произведений базисных векторов согласно таблице умножения базисных векторов (ТУБВ).

ТУБВ устроена следующим образом. Строкам и столбцам ТУБВ соответствуют базисные векторы, а ячейкам — результат их перемножения, которым является некоторый базисный вектор, умноженный на структурную константу — элемент поля GF(p).

Таблица. ТУБВ для модифицированной алгебры кватернионов

о ё г 3 к

ё ё г 3 к

г г —её ек -з

3 3 —ек —её г

к к 3 —г —ё

Необратимые векторы модифицированной конечной алгебры кватернионов. В качестве алгебры, вычисления в которой реализуют описанную далее схему ЭЦП, возьмем модифицированную конечную алгебру кватернионов, задаваемую таблицей, где е € GF(p) — структурная константа, и рассмотрим ее свойства,

используемые при дальнейшем построении алгоритмов формирования и проверки ЭЦП. Для этого требуется установить, какой вектор является единицей алгебры и какому условию удовлетворяют необратимые векторы данной алгебры.

В общем случае единицы конечных некоммутативных ассоциативных алгебр имеют нетривиальный вид, который заведомо неочевиден. Кроме того, единицы бывают различных типов — правосторонние, левосторонние, локальные двухсторонние и т. п. [12]. Далее, для краткости правосторонние единицы будем называть правыми единицами, а левосторонними — левыми. Рассмотрим вывод единицы модифицированной алгебры кватернионов. Определим сначала множества правых и левых единиц, а затем их пересечение.

Обозначим Ег множество правых единиц, тогда для любого ег € Ег и V справедливо равенство V о ег = V.

Теорема. Пусть V = (а, Ь, с, й) и ег = (х, у, г, т) — правая единица, тогда координаты правой единицы ищутся как решение системы

Доказательство. Обозначив V = (а, Ь, с, й) и ег = (х, у, г, т), выполним перемножение векторов:

Согласно условию равенства векторов, это равенство равносильно системе (1), что и требовалось доказать.

Вычислим главный определитель системы (1)

Вспомогательные определители имеют вид Дх = Д, Ду = Дх = = 0. Следовательно, учитывая (2), множество правых единиц состоит из одного вектора (1,0, 0,0).

ах — Ьеу — сег — йт = а, Ьх ау — йг ст = Ь, сх йу аг — Ьт = с, йх — сеу Ьег ат = й.

(1)

V о ег = (ае Ьг се йк) о (хе у г ге тк) = = ах(е о е) ау(е о г) аг(е о е ) ат(е о к) Ьх(г о е) Ьу(г о г) Ьг(г о е ) Ьт(г о к) сх(е о е) су(е о г) сг(е о е) ст(е о к) йх(к о е) йу(к о г) йг(к о е) йт(к о к) = = ах г ау г аг ] атк Ьх г — Ьеу е Ьегк — Ьт е сх е — сеу к — сеге стг йхк йуе — йгг — йте = = (ах — Ьеу — сег — йт)е (Ьх ау — йг ст) г (сх йу аг — Ьт)е (йх — сеу Ьег ат)к ^ ^ V = (ах — Ьеу — сег — йт)е (Ьх ау — йг ст)г (сх йу аг — Ьт)е (йх — сеу Ьег ат)к.

а —Ье —се —й

Ь а —й с

с й а —Ь

й —се Ье а

(2)

Проверим, что этот же вектор является левой единицей, а значит, и единицей алгебры:

(1, 0, 0, 0) о (a, b, c, d) = aj bi cj dk.

Читайте также:  Смарт-карты ESMART Token, электронные идентификаторы российских СКЗИ для аутентификации и хранения ЭП - ESMART

Таким образом, (1,0,0,0) — единица модифицированной алгебры кватернионов. В случае, когда вектор (a, b, c, d) необратим, для его координат выполняется условие

a2 = —d2 (b2 c2)e. (3)

Процедуру генерации необратимого вектора можно описать следующим образом: шаг 1 — сгенерировать b,c,d G GF (p);

шаг 2 — проверить, что -(d2 (b2 c2 )e) является квадратичным вычетом (например, при помощи символа Лежандра), и если проверка завершилась неудачей, то перейти к шагу 1;

шаг 3 — вычислить а = y/—(d2 (Ь2 с2)е) в поле GF(р).

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

v = (a, b, c, d).

Локальные единицы. Каждому необратимому вектору v = (a, b, c, d) можно сопоставить множества левых и правых локальных единиц. Построим множество Er(v) правых локальных единиц для вектора v. Принимая во внимание, что а = ■s/—{d? (Ь2 с2)е), находим, что главный определитель системы (1) обратится в нуль. Исключив с помощью системы компьютерной алгебры Wolfram Mathematica из расширенной матрицы системы (1) линейно зависимые строки (а именно, 3 и 4), имеем

{ax — bey — cez — dw = a,

(4)

bx ay — dz cw = b.

Домножим первую строку (4) на c и вторую на d, сложим и выразим в получившемся выражении z:

(ac bd)x (—bce ad)y (—c2e — d2)z = ac bd ^ (ac bd — (ac bd)x — (—bce ad)y)

z=

— d2 — c2 e —ac — bd (ac bd)x (—bce ad)y

d2 c2e

Таким образом, z вычисляется по формуле

—ac — bd (ac bd)x (—bce ad)y

Z= ЖТс^е ‘ (5)

Аналогично из системы (4) можно вывести для w:

bce — ad (ad — bce)x (—ace — bde)y w=—т.-• (6)

d2 c2e y ‘

Из (5) и (6) следует, что множество решений примет следующий вид:

is^^:ibi2eGFMi (7)

где vo = (0,0, —ac — bd, bce — ad); vi = (d2 c2e, 0, ac bd, ad — bce); V2 = (0, d2 c2e, ad — bce, —ace — bde); e = —cPjc2.

Построим множество E¡(v) левых локальных единиц вектора v. Для этого определим решение векторного уравнения вида e¡ о v = v, где e¡ — левая единица, которое равносильно следующей системе из четырех линейных уравнений:

(ax — bey — cez — dw = a, bx ay dz — cw = b,

(8)

cx — dy az bw = c, ч dx cey — bez aw = d.

Решив систему (8) с учетом условия (3), получим множество E¡(v) левых локальных единиц для вектора v :

|-d2 с2е- : ti, t<2 G GF(p) j , (9)

в котором wo = (0,0, bd — ac, —bce — ad), w = (d2 c2e, 0, ac — bd, ad bce), w2 = (0, d2 c2e, —ad — bce, —ace — bde), e = —d2jc2.

Таким образом, для необратимых векторов модифицированной конечной алгебры кватернионов установлено существование множеств левых и правых локальных единиц, мощность каждого из них равна p2. Этот факт и формулы (7) и (9), описывающие множества правых и левых локальных единиц, используются для задания новой формы скрытой задачи дискретного логарифмирования и построения на ее основе схемы ЭЦП.

ЭЦП над необратимыми векторами. Постановка усиленной формы скрытой задачи дискретного логарифмирования. Для построения схемы ЭЦП в скрытой конечной циклической группе примем в качестве аналога алгоритм ЭЦП Шнорра [17]. Для реализации повышенной скрытности группы, в которой предполагается выполнение базовой операции возведения в степень, зададим формирование открытого ключа в виде двух элементов алгебры z и y, лежащих вне циклической группы, генерируемой степенями необратимого элемента д, для которого в конечной некоммутативной ассоциативной алгебре с единицей e существуют большие множества локальных правых и левых единиц. При этом элементы z и y принадлежат разным конечным циклическим группам, но связаны с элементами д и дх соответственно.

Процедура генерации открытого ключа состоит из семи шагов: шаг 1 — выбрать большое (например, 512 бит) простое число p; шаг 2 — выбрать случайный необратимый элемент д большого (не менее 256 бит) простого порядка q;

шаг 3 — выбрать случайные обратимые элементы d и и такие, что д о d = d о д, д о и = и о д, и о d = d о и;

шаг 4 — выбрать три числа: w, t, x;

шаг 5 — выбрать правую локальную единицу e д для элемента д ; шаг 6 — вычислить элемент согласования I = d~w о e д о и1; шаг 7 — вычислить открытый ключ y = d~w о дх о dw и z = й~г о д о и1. Равенства, используемые для расчета открытого ключа, задают усиленную форму скрытой задачи дискретного логарифмирования. Эта задача формулируется следующим образом: по заданным y = d-w о дх о dw, z = ио д о иг и I = d-w о e д о и1 при неизвестных d, и, д, Zg, w, t требуется определить x.

Процедура формирования подписи состоит в выполнении таких шагов: шаг 1 — выбрать случайное число k;

шаг 2 — вычислить разовый открытый ключ r = d-w о gk о ut; шаг 3 — вычислить первый элемент подписи: e = Fh(m||f), где m — вектор, представляющий подписываемое сообщение;

шаг 4 — вычислить второй элемент подписи: s = k ex mod q. Пара чисел (e, s) является подписью сообщения m. Процедура проверки подписи состоит в следующем: шаг 1 — вычислить r = yq-e о l о es; шаг 2 — вычислить e = Fh (m||r).

Если e = e , то подпись подлинная, иначе — поддельная.

Формальное доказательство корректности работы схемы ЭЦП можно выполнить путем подстановки правых частей формул для открытого ключа в формулу для Re :

r = yq-e о eо zs = (d-w о gx о dw)q-e о (d-w о e-g о uf) о (u-t о g о u*)» = = d-w о gx(q-e) о dw о d-w о в— о ut о u-t о gs о ut = = d-w о gx(q-e) о e о e-g о e о gs о ut = d-w о g x(q-e) о e— о gs о ut = = d-w о g-ex s о ut = d-w о gk о ut = r.

Таким образом, ЭЦП работает корректно.

Существенное отличие построенной схемы ЭЦП от схемы Шнорра состоит в том, что в схеме Шнорра вычисления в процессе проверки подлинности ЭЦП выполняются в явно заданной циклической группе, а в предложенной схеме ведутся в двух разных циклических группах, причем каждая из них отлична от циклической группы, генерируемой необратимым элементом g, который устанавливает связь между элементами открытого ключа y и z. Благодаря такому отличию обеспечивается стойкость построенной схемы ЭЦП к квантовым атакам.

Заключение. Предложена новая форма скрытой задачи дискретного логарифмирования, ориентированная на построение протоколов ЭЦП. На основе такой задачи дана схема ЭЦП и сформулированы требования к конечной некоммутативной ассоциативной алгебре, реализующей данную схему. Одним из возможных носителей этой задачи служит модифицированная конечная алгебра кватернионов. Предложен алгоритм нахождения необратимых элементов и выведены формулы, описывающие множества левых и правых локальных единиц для заданного необратимого вектора. Упомянутые алгоритм и формулы позволяют вычислить требуемые параметры схемы подписи при использовании одним из ее носителей конечной модифицированной алгебры кватернионов.

Литература

1. Menezes A. J., Van Oorschot P. C., Vanstone S. A. Handbook of applied cryptography. Boca Raton, FL: CRC Press, 1997. 780 p.

2. Shor P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on quantum computer // SIAM Journal of Computing. 1997. Vol. 26. P. 1484-1509.

3. Buchmann J., Dahmen E. Post-quantum cryptography / ed. by D. J. Bernstein. Berlin; Heidelberg: Springer, 2009. 245 p.

4. Merkle R. Ch. Secrecy, authentication, and public key systems: technical report N 1979-1. Ctanford, 1979. 193 p.

5. McEliece R. J. A public-key cryptosystem based on algebraic coding theory // DSN Progress Report 42-44. 1978. P. 114-116.

6. Hoffstein J., Pipher J., Silverman J. H. NTRU: A ring based public key cryptosystem // Algorithmic Number Theory (ANTS III). Portland, OR, June 1998 / ed. by J. P. Buhler. Berlin: SpringerVerlag, 1998. P. 267-288. (Lecture Notes in Computer Science, vol. 1423.)

7. Courtois N. The security of Hidden Field Equations (HFE) // Topics in Cryptology — CT-RSA 2001. Berlin; Heidelberg: Springer, 2001. P. 266-281. (Lecture Notes in Computer Science, vol. 2020.)

8. Post-quantum cryptography // 9th Intern. conference, PQCrypto 2021. Fort Lauderdale, FL, USA, April 9-11, 2021, Proceedings. Berlin; Heidelberg: Springer, 2021. (Lecture Notes in Computer Science, vol. 10786.)

9. Federal Register :: Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms // Federal Register. The Daily Journal of the United States Goverment. URL: https://www.gpo.gov/fdsys/pkg/FR-2021-12-20/pdf/2021-30615.pdf (дата обращения: 15.01.2021).

10. Verma G. K. A proxy blind signature scheme over braid groups // Intern. Journal of Network Security. 2009. Vol. 9, N 3. P. 214-217.

11. Myasnikov A., Shpilrain V., Ushakov A. A practical attack on a braid group based cryptographic protocol // Advances in Cryptology — CRYPT0’05. Berlin: Springer-Verlag, 2005. P. 86-96. (Lecture Notes in Computer Science, vol. 3621.)

12. Moldovyan N. A., Moldovyan A. A. Finite non-commutative associative algebras as carriers of hidden discrete logarithm problem // Bulletin of the South Ural State University. Series Mathematical Modelling, Programming & Computer Software (Bulletin SUSU MMCS). 2021. Vol. 12, N 1. P. 66-81.

13. Moldovyan D. N. Cryptoschemes over hidden conjugacy search problem and attacks using homomorphisms // Quasigroups and Related Systems. 2021. Vol. 18, N 2. P. 165-176.

14. Moldovyan D. N. Post-quantum public key-agreement scheme based on a new form of the hidden logarithm problem // Computer Science Journal of Moldova. 2021. Vol. 27, N 1 (78). P. 56-72.

15. Молдовян Д. Н., Молдовян Н. А. Особенности строения групп векторов и синтез криптографических схем на их основе // Вестн. С.-Петерб. ун-та. Сер. 10. Прикладная математика. Информатика. Процессы управления. 2021. Вып. 4. С. 84-93.

16. Молдовян Н. А., Абросимов И. К., Ковалева И. В. Постквантовый протокол бесключевого шифрования // Вопросы защиты информации. 2021. № 3 (118). С. 3-13.

Читайте также:  Нотариусы района Бутово Южное г. Москвы — 6 адресов

17. Schnorr C. P. Efficient signature generation by smart cards // Journal of Cryptology. 1991. Vol. 4, N 3. P. 161-174.

Статья поступила в редакцию 14 февраля 2021 г.

^атья принята к печати 15 марта 2021 г.

Контактная информация:

Молдовян Николай Андреевич — д-p техн. наук, проф., гл. науч. сотр.; nmold@mail.ru Абросимов Иван Константинович — мл. науч. сотр.; ivnabr@yandex.ru

Post-quantum electronic digital signature scheme based on the enhanced form of the hidden discrete logarithm problem

N. A. Moldovyan, I. K. Abrosimov

St. Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences, 39, 14 Line V. I., St. Petersburg, 199178, Russian Federation

For citation: Moldovyan N. A., Abrosimov I. K. Post-quantum electronic digital signature scheme based on the enhanced form of the hidden discrete logarithm problem. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 2021, vol. 15, iss. 2, pp. 212-220. https://doi.org/10.21638/11702/spbu10.2021.205 (In Russian)

A digital signature scheme based on the computational difficulty of the hidden discrete logarithm problem defined in finite non-commutative associative algebras is proposed. The modified quaternion algebra and its properties are considered as the algebraic carrier of the introduced post-quantum digital signature scheme. Formulas describing the set of local units associated with a given non-invertible vector of a modified quaternion algebra are derived.

A new form of the hidden discrete logarithm problem has been formulated and a digital

signature scheme has been developed on its base.

Keywords: post-quantum cryptography, cryptographic primitive, electronic signature, finite

algebra, non-commutative associative algebra.

References

1. Menezes A. J., Van Oorschot P. C., Vanstone S. A. Handbook of applied cryptography. Boca Raton, CRC Press, 1997, 780 p.

2. Shor P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on quantum computer. SIAM Journal of Computing, 1997, vol. 26, pp. 1484—1509.

3. Buchmann J., Dahmen E. Post-quantum cryptography. Berlin, Heidelberg, Springer Press, 2009, 245 p.

4. Merkle R. Ch. Secrecy, authentication, and public key systems. Technical report no. 1979-1. Stanford, 1979, 193 p.

5. McEliece R. J. A public-key cryptosystem based on algebraic coding theory. DSN Progress Report 42-44, 1978, pp. 114-116.

6. Hoffstein J., Pipher J., Silverman J. H. NTRU: A ring based public key cryptosystem. Algorithmic Number Theory (ANTS III). Portland, OR, June 1998. Berlin, Springer-Verlag Press, 1998, pp. 267-288. (Lecture Notes in Computer Science, vol. 1423.)

7. Courtois N. The security of Hidden Field Equations (HFE). Topics in Cryptology — CT-RSA 2001. Berlin, Heidelberg, Springer Press, 2001, pp. 266-281. (Lecture Notes in Computer Science, vol. 2020.)

8. Post-quantum cryptography. 9th Intern. conference, PQCrypto 2021. Fort Lauderdale, FL, USA, April 9-11, 2021, Proceedings. Berlin, Heidelberg, Springer Press, 2021. (Lecture Notes in Computer Science, vol. 10786.)

9. Federal Register :: Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms. Federal Register. The Daily Journal of the United States Goverment. Available at: https://www.gpo.gov/fdsys/pkg/FR-2021-12-20/pdf/2021-30615.pdf (accessed: 15.01.2021).

10. Verma G. K. A proxy blind signature scheme over braid groups. Intern. Journal of Network Security, 2009, vol. 9, no. 3, pp. 214-217.

11. Myasnikov A., Shpilrain V., Ushakov A. A practical attack on a braid group based cryptographic protocol. Advances in Cryptology — CRYPTO’05. Berlin, Springer-Verlag Press, 2005, pp. 86-96. (Lecture Notes in Computer Science, vol. 3621.)

12. Moldovyan N. A., Moldovyan A. A. Finite non-commutative associative algebras as carriers of hidden discrete logarithm problem. Bulletin of the South Ural State University. Series Mathematical Modelling, Programming & Computer Software (Bulletin SUSU MMCS), 2021, vol. 12, no. 1, pp. 66-81.

13. Moldovyan D. N. Cryptoschemes over hidden conjugacy search problem and attacks using homomorphisms. Quasigroups and Related Systems, 2021, vol. 18, no. 2, pp. 165-176.

14. Moldovyan D. N. Post-quantum public key-agreement scheme based on a new form of the hidden logarithm problem. Computer Science Journal of Moldova, 2021, vol. 27, no. 1 (78), pp. 56-72.

15. Moldovyan D. N., Moldovyan N. A. Osobennosti stroeniya grupp vektorov i sintez kripto-graficheskih shem na ih osnove [Features of the structure of groups of vectors and the synthesis of cryptographic schemes based on them]. Vestnik of Saint Petersburg University. Series 10. Applied Mathematics. Computer Science. Control Processes, 2021, iss. 4, pp. 84-93. (In Russian)

16. Moldovyan N. A., Abrosimov I. K., Kovaleva I. V. Postkvantovy’j protokol besklyuchevogo shifrovaniya [Post-quantum no-key encryption protocol]. Voprosi zaschity informatsii [Information security issues], 2021, no. 3 (118), pp. 3-13. (In Russian)

17. Schnorr C. P. Efficient signature generation by smart cards. Journal of Cryptology, 1991, vol. 4, no. 3, pp. 161-174.

Received: February 14, 2021.

Accepted: March 15, 2021.

Author’s information:

Nikolai A. Moldovyan — Dr. Sci. in Technics, Professor, Chief Scientific Collaborate; nmold@mail.ru

Ivan K. Abrosimov — Junior Scientific Collaborate; ivnabr@yandex.ru

1 Хэш-функции

Определение 9.1Хэш-функции — это функции, предназначенные для «сжатия» произвольного сообщения, записанного, как правило, в двоичном алфавите, в некоторую битовую последовательность фиксированной длины, называемую сверткой.

Хэш-функции применяются для тестирования логических устройств, для быстрого поиска и проверки целостности записей в базах данных.

В криптографии хэш-функции применяются для решения следующих задач:

При решении первой задачи для каждого набора данных вычисляется значение хеш-функции (называемое кодом аутентификации сообщения или имитовставкой), которое передается или хранится вместе с самими данными.

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

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

Определение 9.2Обозначим через X множество, элементы которого будем называть сообщениями, n — натуральное число. Хеш-функцией называется всякая легко вычислимая функция h: X rightarrow {0,1}^n.

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

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

Как правило, хеш-функции строят на основе так называемых одношаговых сжимающихся функцийy=f(x_1,x_2)x_1x_2mnnдлина свертки. Для получения значения h(M)Mmдлина сообщения не кратна mM_1, M_2,dots, M_Nvвектор. Если функцияfвектор можно положить равным нулевому вектору. Если же функцияfвектор можно составить из фрагментов указывающих на дату, время, номер сообщения и т.п.При таком подходе свойства хеш-функции hf

2.2 Схема Эль-Гамаля

См. [1]

Безопасность схемы основана на трудности вычисления дискретных логарифмов в конечном поле. Для генерации пары ключей выбирается простое число pgxpy=g^{x} ~(mod  p)y, g, ppgxMkp-1(r, s)

Для проверки подписи нужно убедиться, что

Первое замечание о выборе kkxkkxk

Схема Эль-Гамаля послужила образцом для построения большого семейства во многом сходных по своим свойствам схем подписи.

Пример 9.1Выберем p =11 и g = 2, а секретный ключ x = 8.

Вычислим:

Открытым ключом являются y = 3g = 2p = 11M =5k = 9GCD(9,10) = 1

Теперь находим

Итак, подпись представляет собой пару: r =6s = 3

Для проверки подписи убедимся, что:

Второе замечание. При вычислении подписи целесообразно использовать хэш-образ сообщения, а не само сообщение Mh(M)=5хеширования и шифрования с открытым ключом (в частности, RSA или Эль-Гамаля).

Алгоритм формирования подписи выглядит следующим образом:

  1. Пусть M — подписываемое сообщение. Отправитель вычисляет хеш-значение подписываемого сообщения h=h(M). Значение h должно удовлетворять неравенству 0<h<p.

  2. Отправитель выбирает случайное число k, 0<k<p-1, взаимно простое с p-1, и вычисляет числа:

    k^{-1} — число, обратное k по модулю p-1, k^{-1} существует, так как k и p-1 — взаимно просты.

  3. Подпись (r, s) добавляется к сообщению, и тройка (M, r, s) передается получателю.

Проверка подписи: получатель заново вычисляет хеш-значение присланного сообщения h(M)

Если подпись верна, то это равенство выполняется.

Отметим, что число kh(M)

2.3 Скрытый канал

См. [2]

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

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

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

В общем случае организация подсознательного канала выглядит так:

  1. Отправитель создает безобидное сообщение;
  2. Используя общий ключ с получателем сообщения, отправитель подписывает безобидное сообщение, пряча свое подсознательное сообщение в подписи;
  3. Отправитель посылает подписанное сообщение по общедоступному каналу передачи;
  4. Проверяющий читает сообщение и проверяет подпись. Не обнаружив ничего подозрительного, он передает сообщение дальше;
  5. Получатель проверяет подпись под безобидным сообщением, убеждаясь что сообщение получено от отправителя;
  6. Получатель игнорирует безобидное сообщение и, используя общий с отправителем секретный ключ, извлекает подсознательное сообщение;

Рассмотрим простейший пример организации подсознательного канала передачи информации используя цифровую подпись реализуемую по методу Эль-Гамаля.

  1. Сначала необходимо сгенерировать пару ключей, для этого выбирается простое p=11 и два случайных g=2 и x=8, причем g<p и x<p. Затем вычисляется y=g^x ~(mod  p), y=2^8 ~(mod  11) =3. Открытым ключом является (y, g, p)=(3,2,11), секретным ключом x=8;

  2. Создают безобидное сообщение M=5 и скрытое сообщение M_1=9, проверяя чтобы эти сообщения были взаимно простые с p, а также чтобы M_1=9 было взаимно простым c (p-1)=10; В нашем случае это так;

  3. Вычисляем значение цифровой подписи (a, b)

    Мы получили подпись (6,3) и в тоже время создали скрытый канал;

  4. Проверяющий может просмотреть безобидное сообщение и удостовериться что сообщение передано от отправителя с подписью (6, 3), для этого он проводит вычисления:
  5. Получатель, обладающий секретным ключом, удостоверяется в том, что сообщение пришло именно от того отправителя, с которым организован скрытый канал, для этого он проводит вычисления:
  6. Получатель восстанавливает скрытое сообщение:
Читайте также:  Как открыть файл SIG на компьютере

2.4 Цифровая подпись на эллиптических кривых

См. [3]

В качестве международного стандарта принят американский алгоритм цифровой подписи на эллиптических кривых (ECDSA). В этом стандарте используются эллиптические кривые как над полем простого порядка, так и над полем характеристики 2. Однако криптографически стойких кривых над полем характеристики 2 сравнительно мало. Поэтому мы рассмотрим ЭЦП на эллиптических кривых, заданных над полем большей характеристики.

Замечание. В России официально принят стандарт ЭЦП на эллиптических кривых над полем большей характеристики — ГОСТ 34.10-2001 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи». Выбор кривой и точки на ней подразумевает решение ряда вспомогательных задач. Прежде всего, это подсчет количества точек на кривой. Если NEpNGpN

Для получения криптографически стойкой системы ЭЦП должны выполняться следующие условия:

  1. Порядок точки G, используемой в системе ЭЦП, должен быть простым числом n> max left{ {2}^{160},4sqrt{p}right}.
  2. Nneq p и N neq p   1, где N — порядок кривой.
  3. {p}^{k} neq 1 ~(mod  n) для всех k = 1, dots, C, где C настолько велико, что вычислить дискретный логарифм в GF({{p}^{C}}) за приемлемое время невозможно.

Замечание. В настоящее время значение C = 20ENnnNnGG' in E({F}_{p})G=  frac{N}{n}cdot G'G neq mathcal{O}G = mathcal{O}G'd0<d<nQ = d cdot Gh

Первый учебный алгоритм хеширования

Входом для данного алгоритма является строка, состоящая из букв русского языка.

  1. Выбирается число h_0 — вектор инициализации. Число h_0 равно длине сообщения в символах.

  2. Для каждого символа сообщения вычисляется значение h_i=(n_i h_{i-1})^2 ~(mod  p)$, $i=1,dots,n, где n_i — номер i-й буквы сообщения в алфавите. Для удобства вычислений ниже приведен нумерованный алфавит.

  3. Значение h_n, вычисленное для последнего символа, является хеш-значением сообщения: h(M)=h_n.

Следует отметить, что вычисленное по этому алгоритму хеш-значение зависит от всех символов сообщения Mp=79g=15xkMПример 9.2Выполнить вычисление и проверку подписи сообщения M=text{"БЛЕФ"} по алгоритму Эль-Гамаля. Использовать параметры подписи:

  1. Сформируем хэш-сумму сообщения. Начальное значение h_0 равно количеству символов сообщения: h_0=4. Далее,
  2. Вычисляем число r по формуле r=g^k ~(mod  p). Для рассматриваемого примера получили:
  3. Вычисляем число u по формуле u=(h-xr) (mod p-1), для рассматриваемого примера
  4. Вычисляем значение k^{-1} по модулю p-1 с помощью расширенного алгоритма Евклида. Для рассматриваемого примера значение k^{-1}=23.

    Примечание: если полученное значение k^{-1} — отрицательное, следует взять его по модулю p-1.

  5. Вычисляем число s по формуле s=k^{-1}u (mod p-1). В примере
  6. Цифровая подпись сообщения для рассматриваемого примера: (14,37).

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

  1. Сформируем открытый ключ y абонента по формуле y=g^{x} ~(mod  p):

    Для рассматриваемого примера y=15^{34} ~(mod  79) = 38.

  2. Аналогичным образом вычисляем значения y^{r} ~(mod  p) и r^{s} ~(mod  p), а затем их произведение по модулю p.

    В примере получаем:

  3. Вычисляем значение g^{h} ~(mod  p), значение h было получено ранее.

    В примере g^{h} ~(mod  p)=15^{13} ~(mod  79)= 78.

  4. Проверяем выполнение равенства y^{r}r^{s} ~(mod  p)=g^h ~(mod  p), если равенство выполняется — подпись подлинная, то есть она была вычислена правильно.

    В примере получили 78=78, равенство выполняется, значит, подпись сгенерирована правильно.

Проверка подписи

Входные данные: сообщение MM

Выходные данные: заключение о подлинности или фальсификации подписи.

Алгоритм:

  1. Если хотя бы одно из условий 1 leq  r leq n - 1, 1leq s leq n - 1 нарушается, то подпись фальшивая и работа алгоритма закончена.
  2. Вычислить e = h(M).
  3. Вычислить v =  {s}^{-1} ~(mod  n).
  4. Вычислить {u}_{1} = e r ~(mod  n).
  5. Вычислить {u}_{2} = r v ~(mod  n).
  6. Вычислить X =  {u}_{1} cdot G    {u}_{2} cdot Q = (x, y).
  7. Если r = x ~(mod  n), то подпись действительная, иначе подпись фальшивая.

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

Пример 9.5Требуется проверить подлинность подписи (11,9) для сообщения M, хэш-образ которого e=12.Секретный ключ нам неизвестен, открытый ключ абонента, подписавшего сообщение, равен Q = dG = (384, 276).Проверка подписи начинается с проверки условий 1 leq r leq n -11leq s leq n -1

Находим точку

Наконец, сравниваем значения r = 11x ~(mod  n) = 596 ~(mod  13) = 11

Приведем пример системы электронной подписи на эллиптической кривой, пригодный для практического применения.

Пример 9.6Рассмотрим эллиптическую кривую

Её порядок

является простым числом, а порождающим элементом группы является точка

Для построения электронной подписи нужно выбрать закрытый ключ dQ=dcdot G.

Система цифровой подписи построена.

Если читатель не имеет инструмента для работы с кривыми таких размеров, предлагаем небольшую программу на языке с , вызывающую функцию библиотеки cryptopp для перемножение точек:

Для её сборки нужно подключить библиотеку cryptopp (см. параграф 1.16.2). Допустим, мы собрали программу в исполняемый файл mulpoint (или mulpoint.exe под Windows).

Программа запускается из командной строки:

и выводит результат через стандартный выходной поток. Например:

(здесь $ — приглашение командной строки linux). В нашем случае, помимо a=-3

Управление открытыми ключами

Благодаря асимметричной криптографии проблема распределения секретных ключей, рассмотренная нами в лекции 8, была решена, вернее, ликвидирована, однако, появилась новая проблема – проблема подтверждения подлинности открытых ключей. Эта проблема заключается в том, что, получая открытый ключ некоторого абонента А, пользователь должен быть уверен, что ключ принадлежит именно абоненту А, а не кому-то другому.

Дело в том, что в исходном виде система распределения ключей, предлагавшаяся Диффи и Хеллманом, давала возможность проведения различного рода атак, основанных на перехвате и подмене открытых ключей абонентов. Так, например, в лекции 11 нами была рассмотрена атака «человек-в-середине», позволявшая злоумышленнику осуществлять полный контроль над передаваемой в системе связи информацией.

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

Эти организационные структуры играют роль доверенной третьей стороны и заверяют открытые ключи абонентов своими цифровыми подписями. Таким образом, в распределенных системах связи, использующих криптосистемы с открытыми ключами, вводится понятие инфраструктуры открытых ключей (Public Key Infrastructure — PKI), включающей комплекс программно-аппаратных средств, а также организационно-технических и административных мероприятий, обеспечивающих абонентам системы связи необходимый сервис для управления их открытыми ключами.

Основным элементом инфраструктуры открытых ключей является центр сертификации ( удостоверяющий центр ) (Certification authority, CA), который обеспечивает контроль за выполнением всех процедур, связанных с изготовлением, регистрацией, хранением и обновлением ключей, сертификатов открытых ключей и списков отозванных сертификатов.

Сертификат представляет собой информацию, заверенную цифровой подписью центра, и включающую открытый ключ и другие данные об абоненте. Такими данными являются, например, идентификатор алгоритма электронной подписи, имя удостоверяющего центра, срок годности сертификата, имя пользователя, которому принадлежит сертификат. Международный стандартISO X.

Сертификат обладает следующими свойствами:

Так как сертификаты не могут быть подделаны, их можно опубликовать, поместив в общедоступный справочник.

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

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

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

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

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

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

  1. Администратор удостоверяющего центра генерирует пару (закрытый ключ, открытый ключ) и сообщает свой открытый ключ всем своим абонентам.
  2. Пользователь А выбирает закрытые ключи для выполнения операций шифрования и формирования ЭЦП, а также вычисляет соответствующие открытые ключи.
  3. Открытые ключи шифрования и подписи зашифровываются открытым ключом администратора и предъявляются в удостоверяющий центр для регистрации.
  4. Администратор удостоверяющего центра проверяет (расшифровывает своим закрытым ключом) открытые ключи пользователя А; изготавливает и подписывает сертификаты открытых ключей пользователя А и помещает их в справочники открытых ключей шифрования и открытых ключей подписей. Каждый из справочников предоставляется в распоряжение абонентов удостоверяющего центра.
  5. Любой пользователь системы может извлечь из справочника сертификат необходимого абонента, проверить подпись администратора под сертификатом (расшифровать его открытым ключом администратора) и извлечь открытый ключ.

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock
detector