МЕТОД ПОСТРОЕНИЯ ПОЛИНОМА ОДНОЙ ПЕРЕМЕННОЙ НАД КОНЕЧНЫМ ПОЛЕМ РАУНДОВОЙ ФУНКЦИИ БЛОЧНЫХ ШИФРОВ
Аннотация
В работе предлагается метод построения раундовой функции в виде полинома одной переменной над конечным полем. Предложенный метод основан на вычислении исходного криптографического преобразования в специальных точках конечного поля и последующем обращении матрицы Вандермонда. Для этого класса матриц существуют алгоритмы вычисления обратной матрицы, которые значительно эффективнее стандартного алгоритма обращения с помощью метода Гаусса. В работе был использован алгоритм Трауба, вычислительная сложность которого пропорциональна квадрату размера заданной матрицы. Метод применим для блочных итеративных шифров специального вида (SP-сеть). Для этого класса шифров приведены математические оценки алгебраических параметров полиномов раундовых функций над конечным полем. Количественные значения оценок посчитаны для актуального российского стандарта шифрования «Кузнечик». Представлены оценки вычислительной сложности предлагаемого метода. Проведены практические вычисления полиномов одной переменной для преобразования над конечными полями с различными характеристиками. Приведены практические результаты измерений времени работы при построении полиномов в конечных полях различной размерности. С помощью представленного метода в явном виде вычислен многочлен одной переменной над конечным полем раундовой функции блочного шифра PRESENT.
Литература
[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
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
