МЕТОД ПОСТРОЕНИЯ ПОЛИНОМА ОДНОЙ ПЕРЕМЕННОЙ НАД КОНЕЧНЫМ ПОЛЕМ РАУНДОВОЙ ФУНКЦИИ БЛОЧНЫХ ШИФРОВ

  • Сергей Алексеевич Белов Московский государственный университет имени М.В. Ломоносова http://orcid.org/0000-0002-7923-0129

Аннотация

В работе предлагается метод построения раундовой функции в виде полинома одной переменной над конечным полем. Предложенный метод основан на вычислении исходного криптографического преобразования в специальных точках конечного поля и последующем обращении матрицы Вандермонда. Для этого класса матриц существуют алгоритмы вычисления обратной матрицы, которые значительно эффективнее стандартного алгоритма обращения с помощью метода Гаусса. В работе был использован алгоритм Трауба, вычислительная сложность которого пропорциональна квадрату размера заданной матрицы. Метод применим для блочных итеративных шифров специального вида (SP-сеть). Для этого класса шифров приведены математические оценки алгебраических параметров полиномов раундовых функций над конечным полем. Количественные значения оценок посчитаны для актуального российского стандарта шифрования «Кузнечик». Представлены оценки вычислительной сложности предлагаемого метода. Проведены практические вычисления полиномов одной переменной для преобразования над конечными полями с различными характеристиками. Приведены практические результаты измерений времени работы при построении полиномов в конечных полях различной размерности. С помощью представленного метода в явном виде вычислен многочлен одной переменной над конечным полем раундовой функции блочного шифра PRESENT.

Сведения об авторе

Сергей Алексеевич Белов, Московский государственный университет имени М.В. Ломоносова

аспирант, факультет вычислительной математики и кибернетики

Литература

[1] Biham E., Shamir A. Differential cryptanalysis of DES-like cryptosystems. Journal of Cryptology. 1991; 4(1):3-72. DOI: 10.1007/BF00630563
[2] Matsui M. Linear cryptanalysis method for DES cipher. Workshop on the Theory and Application of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1993. Pp. 386-397. DOI: 10.1007/3-540-48285-7_33
[3] Jakobsen T., Knudsen L.R. The interpolation attack on block ciphers. International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, 1997. Pp. 28-40. DOI: 10.1007/BFb0052332
[4] Nyberg K., Knudsen L.R. Provable security against a differential attack. Journal of Cryptology. 1995; 8(1):27-37. DOI: 10.1007/BF00204800
[5] Rijmen V. et al. The cipher SHARK. International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, 1996. Pp. 99-111. DOI: 10.1007/3-540-60865-6_47
[6] Moriai S., Shimoyama T., Kaneko T. Interpolation attacks of the block cipher: SNAKE. International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, 1999. Pp. 275-289. DOI: 10.1007/3-540-48519-8_20
[7] Althaus H., Leake R. Inverse of a finite-field Vandermonde matrix (Corresp.) IEEE Transactions on Information Theory. 1969; 15(1):173-173. DOI: 10.1109/TIT.1969.1054253
[8] Kleibanov S.B., Norkin K.B., Prival'skii V.B. Inversion of the Vandermond matrix. Automation and Remote Control. 1977; 38(4):600-601. Available at: http://mi.mathnet.ru/eng/at7343 (accessed 10.05.2018).
[9] Traub J.F. Associated polynomials and uniform methods for the solution of linear problems. Siam Review. 1966; 8(3):277-301. DOI: 10.1137/1008061
[10] Parker F.D. Inverses of Vandermonde matrices. The American Mathematical Monthly. 1964; 71(4):410-411. DOI: 10.2307/2313246
[11] Björck Ȧ., Pereyra V. Solution of Vandermonde systems of equations. Mathematics of Computation. 1970; 24(112):893-903. DOI: 10.1090/S0025-5718-1970-0290541-1
[12] Gohberg I., Olshevsky V. The fast generalized Parker-Traub algorithm for inversion of Vandermonde and related matrices. Journal of Complexity. 1997; 13(2):208-234. DOI: 10.1006/jcom.1997.0442
[13] Yan S., Yang A. Explicit algorithm to the inverse of Vandermonde matrix. 2009 International Conference on Test and Measurement. Hong Kong, 2009. Pp. 176-179. DOI: 10.1109/ICTM.2009.5413083
[14] Bayev V.V. Some lower bounds on the algebraic immunity of functions given by their trace forms. Problems of Information Transmission. 2008; 44(3):243-265. DOI: 10.1134/S0032946008030071
[15] Kuzmin A.S., Markov V.T., Nechaev A.A., Shishkov A.B. Approximation of Boolean functions by monomial functions. Discrete Mathematics and Applications. 2006; 16(1):7–28. DOII: 10.1515/156939206776241255
[16] Kuzmin A.S., Nozdrunov V.I. Relationship between the coefficients of polynomials over GF(2n) and weights of Boolean functions represented by them. Prikladnaya Diskretnaya Matematika. 2014; 4(26):28-46. Available at: https://elibrary.ru/item.asp?id=22636126 (accessed 10.05.2018). (In Russian)
[17] Carlet C. Boolean Functions for Cryptography and Error-Correcting Codes. Y. Crama, P. Hammer (Eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering (Encyclopedia of Mathematics and its Applications). Cambridge: Cambridge University Press, 2010. Part III. Pp. 257-397. DOI: 10.1017/CBO9780511780448.011
[18] Feistel H. Cryptography and computer privacy. Scientific American. 1973; 228(5):15-23. DOI: 10.1038/scientificamerican0573-15
[19] Bogdanov A. et al. PRESENT: An Ultra-Lightweight Block Cipher. P. Paillier, I. Verbauwhede (Eds.) Cryptographic Hardware and Embedded Systems – CHES 2007. CHES 2007. Lecture Notes in Computer Science. Vol. 4727. Springer, Berlin, Heidelberg, 2007. Pp. 450-466. DOI: 10.1007/978-3-540-74735-2_31
Опубликована
2018-09-30
Как цитировать
БЕЛОВ, Сергей Алексеевич. МЕТОД ПОСТРОЕНИЯ ПОЛИНОМА ОДНОЙ ПЕРЕМЕННОЙ НАД КОНЕЧНЫМ ПОЛЕМ РАУНДОВОЙ ФУНКЦИИ БЛОЧНЫХ ШИФРОВ. Современные информационные технологии и ИТ-образование, [S.l.], v. 14, n. 3, p. 586-593, sep. 2018. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/423>. Дата доступа: 29 mar. 2024 doi: https://doi.org/10.25559/SITITO.14.201803.586-593.
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук