ВЫЧИСЛЕНИЕ МИНИМАЛЬНОЙ СТЕПЕНИ МНОГОЧЛЕНА НАД КОНЕЧНЫМ ПОЛЕМ ДЛЯ ВЕКТОРНОГО БУЛЕВОГО ОТОБРАЖЕНИЯ, ЗАДАННОГО ПОЛИНОМАМИ ЖЕГАЛКИНА
Аннотация
В работе предлагается метод построения раундовой функции в виде полинома одной переменной над конечным полем. Предложенный метод основан на вычислении исходного криптографического преобразования в специальных точках конечного поля и последующем обращении матрицы Вандермонда. Для этого класса матриц существуют алгоритмы вычисления обратной матрицы, которые значительно эффективнее стандартного алгоритма обращения с помощью метода Гаусса. В работе был использован алгоритм Трауба, вычислительная сложность которого пропорциональна квадрату размера заданной матрицы. Метод применим для блочных итеративных шифров специального вида (SP-сеть). Для этого класса шифров приведены математические оценки алгебраических параметров полиномов раундовых функций над конечным полем. Количественные значения оценок посчитаны для актуального российского стандарта шифрования «Кузнечик». Представлены оценки вычислительной сложности предлагаемого метода. Проведены практические вычисления полиномов одной переменной для преобразования над конечными полями с различными характеристиками. Приведены практические результаты измерений времени работы при построении полиномов в конечных полях различной размерности. С помощью представленного метода в явном виде вычислен многочлен одной переменной над конечным полем раундовой функции блочного шифра PRESENT.
Литература
[2] Youssef A.M., Gong G. On the Interpolation Attacks on Block Ciphers. In: Goos G., Hartmanis J., van Leeuwen J., Schneier B. (eds) Fast Software Encryption. FSE 2000. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2001; 1978:109-120. (In Eng.) DOI: 10.1007/3-540-44706-7_8
[3] Massacci F., Marraro L. Logical Cryptanalysis as a SAT Problem. Journal of Automated Reasoning. 2000; 24(1-2):165-203. (In Eng.) DOI: 10.1023/A:1006326723002
[4] Jovanović D., Janičić P. Logical Analysis of Hash Functions. In: Gramlich B. (eds) Frontiers of Combining Systems. FroCoS 2005. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2005; 3717:200-215. (In Eng.) DOI: 10.1007/11559306_11
[5] Mironov I., Zhang L. Applications of SAT Solvers to Cryptanalysis of Hash Functions. In: Biere A., Gomes C.P. (eds) Theory and Applications of Satisfiability Testing - SAT 2006. SAT 2006. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2006; 4121:102-115. (In Eng.) DOI: 10.1007/11814948_13
[6] Wang X., Yu H. How to Break MD5 and Other Hash Functions. In: Cramer R. (eds) Advances in Cryptology – EUROCRYPT 2005. EUROCRYPT 2005. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2005; 3494:19-35. (In Eng.) DOI: 10.1007/11426639_2
[7] De D., Kumarasubramanian A., Venkatesan R. Inversion Attacks on Secure Hash Functions Using satSolvers. In: Marques-Silva J., Sakallah K.A. (eds) Theory and Applications of Satisfiability Testing – SAT 2007. SAT 2007. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2007; 4501:377-382. (In Eng.) DOI: 10.1007/978-3-540-72788-0_36
[8] Dobbertin H. Cryptanalysis of MD4. In: Gollmann D. (eds) Fast Software Encryption. FSE 1996. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 1996; 1039:53-69. (In Eng.) DOI: 10.1007/3-540-60865-6_43
[9] Eibach T., Pilz E., Völkel G. Attacking Bivium Using SAT Solvers. In: Kleine Büning H., Zhao X. (eds) Theory and Applications of Satisfiability Testing – SAT 2008. SAT 2008. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2008; 4996:63-76. (In Eng.) DOI: 10.1007/978-3-540-79719-7_7
[10] Soos M., Nohl K., Castelluccia C. Extending SAT Solvers to Cryptographic Problems. In: Kullmann O. (eds) Theory and Applications of Satisfiability Testing - SAT 2009. SAT 2009. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2009; 5584:244-257. (In Eng.) DOI: 10.1007/978-3-642-02777-2_24
[11] Courtois N.T., Bard G.V., Wagner D. Algebraic and Slide Attacks on KeeLoq. In: Nyberg K. (eds) Fast Software Encryption. FSE 2008. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2008; 5086:97-115. (In Eng.) DOI: 10.1007/978-3-540-71039-4_6
[12] Erickson J., Ding J., Christensen C. Algebraic Cryptanalysis of SMS4: Gröbner Basis Attack and SAT Attack Compared. In: Lee D., Hong S. (eds) Information, Security and Cryptology – ICISC 2009. ICISC 2009. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2010; 5984:73-86. (In Eng.) DOI: 10.1007/978-3-642-14423-3_6
[13] Chaki S., Clarke E.M., Groce A., Jha S., Veith H. Modular verification of software components in C. IEEE Transactions on Software Engineering. 2004; 30(6):388-402. (In Eng.) DOI: 10.1109/TSE.2004.22
[14] Cook B., Kroening D., Sharygina N. Cogent: Accurate Theorem Proving for Program Verification. In: Etessami K., Rajamani S.K. (eds) Computer Aided Verification. CAV 2005. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2005; 3576:296-300. (In Eng.) DOI: 10.1007/11513988_30
[15] Biere A., Cimatti A., Clarke E., Zhu Y. Symbolic Model Checking without BDDs. In: Cleaveland W.R. (eds) Tools and Algorithms for the Construction and Analysis of Systems. TACAS 1999. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 1999; 1579:193-207. (In Eng.) DOI: 10.1007/3-540-49059-0_14
[16] McMillan K.L. Applying SAT Methods in Unbounded Symbolic Model Checking. In: Brinksma E., Larsen K.G. (eds) Computer Aided Verification. CAV 2002. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2002; 2404:250-264. (In Eng.) DOI: 10.1007/3-540-45657-0_19
[17] Menezes A.J. et al. Applications of Finite Fields. In: Ismail M. (eds) The Springer International Series in Engineering and Computer Science. Springer US. 1993; 199. (In Eng.) DOI: 10.1007/978-1-4757-2226-0
[18] 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. (In Eng.) DOI: 10.1134/S0032946008030071
[19] Kuzmin A.S., Markov V.T., Nechaev A.A., Shishkov A.B. Approximation of Boolean functions by monomial ones. Discrete Mathematics and Applications. 2006; 16(1):7-28. (In Eng.) DOI: 10.1515/156939206776241255
[20] 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-36. Available at: https://elibrary.ru/item.asp?id=22636126 (accessed 21.01.2019). (In Russ.)
[21] Carlet C. Boolean Functions for Cryptography and Error-Correcting Codes. Boolean Models and Methods in Mathematics, Computer Science, and Engineering (Encyclopedia of Mathematics and its Applications). Crama Y., Hammer P. (eds). Cambridge: Cambridge University Press, pp. 257-397. 2010. (In Eng.) DOI: 10.1017/CBO9780511780448.011
Это произведение доступно по лицензии 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.
