## Issue 186, article 2

DOI:https://doi.org/10.15407/kvt186.04.005

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

UDС 519.72

**SYSTEM OF CRYPTOGRAPHIC TRANSFORMATIONS OF NUMBERS BY MEANS OF LINEAR RECURRENT FORMS**

**Taras Shevchenko National University of Kiev, Ukraine**

**Introduction****. ** Two-level system of encoding integers by linear forms aP_{n} + bQ_{n}, where P_{n} and Q_{n} 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 = aA_{n} + bB_{n}, where A_{n} / B_{n} 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) -> cP_{n} + dP_{n+1}. The sequences A_{n}, B_{n}, P_{n} 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.

**Reference**

- 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.
- Anisimov A. V. Data Coding by Linear Forms of Numerical Sequences.
*Cybernetics and Systems Analysis,*2003, № 1, pp. 3-15. - Anisimov A. V. Integer representation in the mixed base (2,3).
*Cybernetics and Systems Analysis*, 2009, № 4, pp. 3-18 - Anisimov A. V. Two-base numeration systems.
*Cybernetics and Systems Analysis*, 2013, №4, pp. 1-14. - Anisimov A. V. Prefix Encoding by Means of the (2,3)-Representation of Numbers. IEEE Transactions on Information Theory, 2013, vol. 59, № 4, pp. 2359-2374.
- Anisimov A. V. Zavadskyi I. A. Robust Prefix Encoding Using Lower (2,3) Number Representation.
*Cybernetics and Systems Analysis*, 2014, № 2, pp.1-15.

**Received **03.10.2016