Безпека низки відомих криптографічних примітивів (протокол Діффі-Хелмана, криптосистема Ель-Гамаля з відкритим ключем,цифровий підпис Ель-Гамаля) ґрунтується на складності проблемидискретного логарифму в скінченній циклічній групі. Хоча проблему дискретного логарифму формулюють для будь якої скінченої групи, але в застосуваннях до криптології добре вивчені лише кілька груп: мультиплікативні групи простого та розширеного скінченних полів (алгоритм Діффі-Хелмана), група взаємно простих з числом pq (p,q–прості) і менших за нього натуральних чисел (криптосистемаRSA), група точок еліптичної кривої над скінченним полем. Усі наведені групи є абелевими. Для більшості інших груп, зокрема неабелевих, складність проблеми дискретного логарифму є недостатньо дослідженою. У всіх випадках (як абелевих, так і неабелевих груп) складність проблеми дискретного логарифма забезпечується наявністю в групі елемента великого порядку (в ідеалі твірного елемента групи). Тому питання дослідження складності задачі дискретного логарифма, а також пов’язане з ним питання побудови елементів великого порядку в неабелевих групах, залишається актуальним.
УДК 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.