Decompositions of the recursive matrices and its application to the implementation of the linear transformations

Stepan Davydov, Vasily Shishkin

Abstract


We study linear transformations defined by the recursive matrices in this article. Such transformations are used, for example, in the Kuznyechik block cipher and the PHOTON family of lightweight hash functions. We have found all solutions of the equation X −1 (S T ) mX = S m for any invertible recursive matrix S m. We propose two ways of recursive matrices decomposition and its application to the software implementation of the linear transformations. Our implementations are sufficiently fast and require rather small amount of memory. We note, matrix (S T ) m implements multiplication by polynomial x m over the ring Q[x]/f(x). This matrix is also MDS matrix and has rather efficient software implementation. Proposed for recursive matrices Implementation 4 is 23% slower then implementation with LUT­tables, but it uses 8 times less memory. Since the inverse of the recursive matrix has the same decomposition, decryption software implementation is also efficient. We consider, our implementations may be useful for low­resource devices with software implementation of algorithms. We demonstrate the table with different software implementation results of the block cipher Kuznyechik in conclusion.

Full Text:

PDF (Russian)

References


Shannon Claude E. Communication theory of secrecy systems // Bell Syst. Tech. J. –– 1949. –– Vol. 28. –– P. 656–715.

Biham Eli, Shamir Adi. Differential cryptanalysis of des­like cryptosystems // Journal of Cryptology. –– 1990. –– Vol. 4. –– P. 3–72.

Matsui Mitsuru. Linear cryptanalysis method for des cipher // International Conference on the Theory and Application of Cryptographic Techniques. –– 1994.

Malyshev F. M. The duality of differential and linear methods in cryptography, in russian // Mathematical Aspects of Cryptography. – 2014. – Vol. 5. – P. 35–47. – URL: https://doi.org/10.4213/mvk128.

Cryptographically significant mds matrices over finite fields: A brief survey and some generalized results / Kishan Chand Gupta, Sumit Kumar Pandey, Indranil Ghosh Ray, Susanta Samanta // Adv. Math. Commun. –– 2019. –– Vol. 13. –– P. 779–843.

V. Dolmatov A. Degtyarev. Gost r 34.11­2012: Hash function // Request for Comments. – 2013. – no. RFC: 6986. – URL: https: //datatracker.ietf.org/doc/html/rfc6986.

Guo Jian, Peyrin Thomas, Poschmann Axel. The photon family of lightweight hash functions. – Vol. 2011. – 2011. – 08. – P. 222–239.

Gost r 34.12­2015: Block cipher «kuznyechik» // Request for Comments. – 2016. – no. RFC: 7801. – URL: https://datatracker.ietf.org/doc/html/rfc7801.

Advanced encryption standard (aes) // Federal Information Processing Standards. – November 26, 2001. – no. Publication 197. – URL: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197­upd1.pdf.

Diffie Whitfield, Ledin George. Sms4 encryption algorithm for wireless networks // IACR Cryptol. ePrint Arch. – 2008. – Vol. 2008. –P. 329. – URL: https://eprint.iacr.org/2008/329.pdf.

Information technology – security techniques – hash­functions – part 3: Dedicated hashfunctions // ISO/IEC. –– 2004. –– no. 10118­3. –URL: https://www.iso.org/standard/39876.html.

S. V. Dorokhin S. S. Kachkov A. A. Sidorenko. Implementation of «kuznyechik» cipher using vector instructions, in russian //MIPT works. – 2018. – Vol. 10, no. 4 (40).

Tolba Mohamed F., Youssef A. Improved meet­in­the­middle attacks on reduced round kuznyechik // ICISC. – 2017.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162