УДК 621.397

Показано, як явно збудувати два елементи великого порядку, які не комутують, для випадку неабелевої групи квадратних матриць з ненульовим визначником над довільним скінченним полем. Для отримання таких двох елементів використано відомі результати про побудову елементів великого порядку в скінчених полях загального вигляду. Ключова думка полягає в тому, щоб утворити матрицю, визначник якої дорівнює елементу великого порядку в скінченному полі. Тоді порядок елемента скінченного поля є нижньою межею для порядку матриці. Пропонується утворювати таку матрицю як добуток нижньої трикутної та верхньої трикутної матриць. Розглянуто постквантові асиметричні криптосистеми, які використовують елементи великого порядку з вказаної групи.
Ключові слова: криптографічний захист інформації, скінченне поле, загальна лінійна група, порядок елемента, постквантова криптосистема.

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.

УДК 621.397

Наведено порівняльний аналіз відомих протоколів узгодження таємного ключа через відкритий канал звʼязку. Запропоновано узагальнення відомого протоколу з використанням некомутативного множення матриць над простим скінченним полем на випадок довільного скінченного поля.
Ключові слова: протокол узгодження ключа, скінченне поле, загальна лінійна група, порядок елемента.

A symmetric cryptosystem requires a secret key agreed by both parties. The Diffie-Hellman protocol was originally proposed for its exchange via an open communication channel. It is based on the computational complexity of the discrete logarithm problemin certain finite groups (the multiplicative group of afinite field, the group of points of an elliptic curve over a finite field). The availability of a powerful quantum computer will allow solving the discrete logarithm problem in these groups. Therefore, the issue of construction of secret key exchange protocols that will be resistant to attacks using a quantum computer has become urgent.The paper provides a comparative analysis of known protocols for a secret key exchange via an open communication channel. A generalization of the known protocol using non-commutative matrix multiplication over a prime finite field for the case of an arbitrary finite field is proposed. In this protocol, two high order elements from the general linear group over a finite field should be used, which satisfy an additional condition. It consists in the fact that each of the matrices cannot be reduced to a diagonal form by conjugation transformation. This condition follows from the considerations of avoiding an attack on the protocol. It is shown how to construct such elements.For the proposed generalization of the protocol, the sizes of public and private keys, secret key, the size of the finite field, which ensure the appropriate level of security, are calculated. The dimensions of matrices (elements of the general linear group) that we use are also given. The generalization of the protocol to the case of an arbitrary finite field increases the flexibility of choosingprotocol parameters to ensure the desired level of security