Issue 186, article 2


KVT, 2016, Issue 186, pp.5-15

UDС 519.72


Anisimov A.V.

Taras Shevchenko National University of Kiev, Ukraine

Introduction. Two-level system of encoding integers by linear forms aPn + bQn, where Pn and Qn are linear recurrent sequences. These sequences are defined by factoring quadratic irrationalities into continued fractions. Firstly, a number x is represented as a form x = aAn + bBn, where An / Bn is a convergent to some fixed quadratic irrationality. At the second stage the triple (a, b, n) is encoded by a maximal linear form of another linear recurrent sequence (a, b, n) -> cPn + dPn+1. The sequences An, Bn, Pn are considered as hidden symmetric keys given by coefficients of corresponding quadratic irrationalities. Properties of such encodings are established.

The purpose of the article is to develop and study a nondeterministic system of cryptographic integer encoding by means of linear recurrent sequences.

Methods. We used methods of continued fractions, properties of linear forms, and bijective encoding of natural numbers.

Results. We proved as a theorem that such a system of encoding is absolutely resistant to passive crypto-attacks. With some further additions it is also resistant to stronger types of attacks.

Conclusion. The proposed system of integer encoding is easy to construct, and it has some proven properties that allows using it as a primitive basic procedure for light weighted cryptography.

Keywords: Linear forms, continued fractions, nondeterministic cryptography.

Download full text (ru)!


1 Bellare, M., Rogaway,P.: Optimal Asymetric Encryption In: De Santis, A. (ed) Advances of Cryptology: Proceedings of EURO-CRYPT ’94, LNCS, 1995. vol. 950, pp. 92-111.

2 Anisimov A. V. Data Coding by Linear Forms of Numerical Sequences. Cybernetics and Systems Analysis, 2003, No 1, pp. 3-15.

3 Anisimov A. V. Integer representation in the mixed base (2,3). Cybernetics and Systems Analysis, 2009, No 4, pp. 3-18

4 Anisimov A. V. Two-base numeration systems. Cybernetics and Systems Analysis, 2013, No 4, pp. 1-14.

5 Anisimov A. V. Prefix Encoding by Means of the (2,3)-Representation of Numbers. IEEE Transactions on Information Theory, 2013, vol. 59, No 4, pp. 2359-2374.

6 Anisimov A. V. Zavadskyi I. A. Robust Prefix Encoding Using Lower (2,3) Number Representation. Cybernetics and Systems Analysis, 2014, No 2, pp.1-15.

Received 03.10.2016