Abstract:
We show that many known schemes of the cryptographic key public exchange protocols in algebraic cryptography using two-sided multiplications are the special cases of a general scheme of this type. In most cases, such schemes are built on the platforms that are subsets of some linear spaces. They have been repeatedly compromised by the linear decomposition method introduced by the first author. The method allows to compute the exchanged keys without computing any private data and, consequently, without solving the hard algorithmic problems on which the assumptions are based. Here, we show that this method can be successfully applied to the following general scheme and, thus, is a universal one. The general scheme proceeds as follows. Let G be an algebraic system with the associative multiplication, for example, a group chosen as the platform. We assume that G is a subset of a finitely dimensional linear space. First, some public elements g1,…,gk∈G are taken. Then the correspondents, Alice and Bob, sequentially publicise the elements of the form φa,b(f) for some a,b∈G, where φa,b(f)=afb, f∈G and f is a given or previously built element. The exchanged key has the form
K=φal,bl(φal−1,bl−1(…(φa1,b1(gi)…))=alal−1…a1gib1…bl−1bl.
We suppose that Alice chooses parameters a,b in a given finitely generated subgroup A of G, and Bob picks up parameters a,b in a finitely generated subgroup B of G to construct their transformations of the form φa,b. Under some natural assumptions about G,A and B, we show that an intruder can efficiently calculate the exchanged key K without calculation of the transformations used in the scheme.
Keywords:
cryptography, cryptanalisis, key exchange, linear decomposition.
Citation:
V. A. Roman'kov, A. A. Obzor, “General algebraic cryptographic key exchange scheme and its cryptanalysis”, Prikl. Diskr. Mat., 2017, no. 37, 52–61
\Bibitem{RomObz17}
\by V.~A.~Roman'kov, A.~A.~Obzor
\paper General algebraic cryptographic key exchange scheme and its cryptanalysis
\jour Prikl. Diskr. Mat.
\yr 2017
\issue 37
\pages 52--61
\mathnet{http://mi.mathnet.ru/pdm594}
\crossref{https://doi.org/10.17223/20710410/37/4}
Linking options:
https://www.mathnet.ru/eng/pdm594
https://www.mathnet.ru/eng/pdm/y2017/i3/p52
This publication is cited in the following 4 articles:
M. Saracevic, S. Adamovic, N. Macek, A. Selimi, S. Pepic, “Source and channel models for secret-key agreement based on Catalan numbers and the lattice path combinatorial approach”, J. Inf. Sci. Eng., 37:2 (2021), 469–482
V. A. Romankov, “Effektivnye metody algebraicheskogo kriptoanaliza i zaschita ot nikh”, PDM. Prilozhenie, 2019, no. 12, 117–125
V. Roman'kov, “Two general schemes of algebraic cryptography”, Groups Complex. Cryptol., 10:2 (2018), 83–98
Adi Ben-Zvi, Arkadius Kalka, Boaz Tsaban, Lecture Notes in Computer Science, 10991, Advances in Cryptology – CRYPTO 2018, 2018, 255