ЕЛЕМЕНТИ ВЕЛИКОГО ПОРЯДКУ ДЛЯ КРИПТОСИСТЕМ З НЕАБЕЛЕВИМИ БАЗОВИМИ ГРУПАМИ
ELEMENTS OF HIGH ORDER FOR CRYPTOSYSTEMS WITH NON-ABELIAN PLATFORM GROUPS
Сторінки: 278-285. Номер: №4, 2023 (323) 
Автори:
ПОПОВИЧ БОГДАН
Національний університет “Львівська політехніка”
ORCID ID: 0000-0001-6259-2361
e-mail: bogdan.popovych@gmail.com
ПОПОВИЧ РОМАН
Національний університет “Львівська політехніка”
ORCID ID: 0009-0006-0992-0825
e-mail: rombp07@gmail.com
POPOVYCH BOGDAN
Lviv Polytechnic National University
POPOVYCH ROMAN
Lviv Polytechnic National University
DOI: https://www.doi.org/10.31891/2307-5732-2023-323-4-278-285
Анотація мовою оригіналу
Показано, як явно збудувати два елементи великого порядку, які не комутують, для випадку неабелевої групи квадратних матриць з ненульовим визначником над довільним скінченним полем. Для отримання таких двох елементів використано відомі результати про побудову елементів великого порядку в скінчених полях
загального вигляду. Ключова думка полягає в тому, щоб утворити матрицю, визначник якої дорівнює елементу великого порядку в скінченному полі. Тоді порядок елемента скінченного поля є нижньою межею для порядку матриці. Пропонується утворювати таку матрицю як добуток нижньої трикутної та верхньої трикутної
матриць. Розглянуто постквантові асиметричні криптосистеми, які використовують елементи великого порядку з вказаної групи.
Ключові слова: криптографічний захист інформації, скінченне поле, загальна лінійна група, порядок елемента, постквантова криптосистема.
Розширена анотація англійською мовою
The security of a number of well-known cryptographic primitives (Diffie-Hellman protocol, El-Gamal public key cryptosystem, ElGamal digital signature) is based on the computational complexity of the discrete logarithm problem in a finite cyclic group. In the case of both abelian and non-abelian groups, this complexity is ensured by construction of elements of high (ideally, maximum possible) order from the group. Actually, such elements are used in the implementation of corresponding asymmetric cryptosystems. However, for the case of a non-abelian group, it is not known how to explicitly obtain such elements. Therefore, it is customary to take random elements, that does not guarantee the system’s resistance to hacking. The paper shows how to explicitly construct two high order elements that do not commute for the case of non-abelian group of
square matrices with nonzero determinant over an arbitrary finite field. To obtain such two elements, known results on the construction of high order elements in finite fields of general form were used. The key idea is to form a matrix whose determinant is equal to high order element in the finite field. Then the order of this element is a lower bound for the order of the matrix. As one of the options, it is proposed to form such a matrix as a product of lower triangular and upper triangular matrices. Post-quantum asymmetric cryptosystems that use high order elements from the specified group are considered. It is shown how, using the constructed elements, to implement the cryptosystem that
is analogous to the El-Gamal cryptosystem in the non-commutative case. A simple computational example is given that illustrates the implementation of this cryptosystem in the case of 2×2 matrices with elements from a finite field with 256 elements. Cryptosystems in the field of multivariate cryptography are also considered, for the construction of which high order elements from the specified group of matrices are required. Obtained results can be used in the construction of various post-quantum primitives.
Keywords: cryptographic information protection, finite field, general linear group, order of element, post-quantum cryptosystem.
