Construção de S-Boxes com Valores Ótimos de Não Linearidade Baseada em uma Relação entre o Multigrafo de Ramanujan e a Matriz da Transformação Afim
Resumo
Uma S-Box (caixa de substituição) deve ter pelo menos valores ótimos para não linearidade (N L), uniformidade diferencial e grau algébrico. Segundo a literatura, uma S-Box criptograficamente forte deve ter N L > 100. O AES (Advanced Encryption Standard) usa uma matriz binária não singular S para construir sua S-Box. Muitos trabalhos escolhem S em aproximadamente 262 matrizes não singulares ou constroem S-Box aleatoriamente, sem garantir N L > 100. Neste trabalho, identificamos que S pode ser estudada como uma matriz de adjacência (A(G)) de um multigrafo de Ramanujan e verificamos esta relação com outras A(G) do tipo rotacionais. Dessa forma, reduzimos a busca por S para a ordem de 1011 e construímos S-Boxes com N L > 100.Referências
Bondy, J. A. (1976). Graph Theory With Applications. Elsevier Science Ltd., Oxford, UK, UK.
Canteaut, A. (2016). Lecture notes on cryptographic Boolean functions. Inria, Paris, France.
Carlet, C. (2010). Boolean Functions for Cryptography and Error-Correcting Codes, page 257–397. Encyclopedia of Mathematics and its Applications. Cambridge University Press.
Carlet, C. and Ding, C. (2007). Nonlinearities of s-boxes. Finite Fields and Their Applications, 13(1):121 – 135.
Chandrasekharappa, T. (2012). Enhancement of confidentiality and integrity using cryptographic techniques. PhD thesis, Manipal University, Manipal - India.
Chandrasekharappa, T., Prema, K., and Kumara, S. (2011). S-boxes generated using affine transformation giving maximum avalanche effect. Int. J. Comput. Sci. Eng., 3(9):3185–3193.
Charles, D. X., Lauter, K. E., and Goren, E. Z. (2009). Cryptographic hash functions from expander graphs. Journal of Cryptology, 22(1):93–113.
Costache, A., Feigon, B., Lauter, K. E., Massierer, M., and Puskás, A. (2018). Ramanujan graphs in cryptography. IACR Cryptology ePrint Archive, 2018:593.
Cui, J., Huang, L., Zhong, H., Chang, C., and Yang, W. (2011). An improved AES s-box and its performance analysis. International Journal of Innovative Computing, Information and Control, 7:2291–2302.
Daemen, J. and Rijmen, V. (2002). The Design of Rijndael. Springer-Verlag, Berlin, Heidelberg.
Das, S., Zaman, J. U., and Ghosh, R. (2013). Generation of AES s-boxes with various modulus and additive constant polynomials and testing their randomization. Procedia Technology, 10:957 – 962. First International Conference on Computational Intelligence: Modeling Techniques and Applications (CIMTA) 2013.
Davidoff, G., Sarnak, P., and Valette, A. (2003). Elementary Number Theory, Group Theory and Ramanujan Graphs. Number 55 in London Mathematical Society Student Texts. Cambridge University Press.
de la Cruz Jiménez, R. A. (2019). Generation of 8-bit s-boxes having almost optimal cryptographic properties using smaller 4-bit s-boxes and finite field multiplication. In Lange, T. and Dunkelman, O., editors, Progress in Cryptology – LATINCRYPT 2017, pages 191–206, Cham. Springer International Publishing.
Deva Sinha, S. and Arya, C. (2012). Algebraic construction and cryptographic properties of Rijndael substitution box. Defence Science Journal, 62:32–37.
Hoory, S., Linial, N., and Wigderson, A. (2006). Expander graphs and their applications. BULL. AMER. MATH. SOC., 43(4):439–561.
Isa, H., Jamil, N., and Reza Z ’aba, M. (2016). Hybrid heuristic methods in constructing cryptographically strong s-boxes. International Journal of Cryptology Research, 6:1– 15.
Klima, R. and Sigmon, N. (2016). Applied abstract algebra with MAPLE and MATLAB. Textbook in mathematics. CRC Press, London, 3rd ed. edition.
Lubotzky, A., Phillips, R., and Sarnak, P. (1988). Ramanujan graphs. Combinatorica, 8(3):261–277.
Meier,W. and Staffelbach, O. (1990). Nonlinearity criteria for cryptographic functions. In Quisquater, J.-J. and Vandewalle, J., editors, Advances in Cryptology — EUROCRYPT ’89, pages 549–562, Berlin, Heidelberg. Springer Berlin Heidelberg.
Murty, M. R. (2003). Ramanujan graphs. J. Ramanujan Math. Soc, 18:1–20.
Nover, H. (2005). Algebraic Cryptanalysis of AES: An Overview. University of Wisconsin, USA, pages 1–16.
Paar, C. and Pelzl, J. (2010). The Data Encryption Standard (DES) and Alternatives, pages 55–86. Springer Berlin Heidelberg, Berlin, Heidelberg.
Shannon, C. E. (1949). Communication theory of secrecy systems. The Bell System Technical Journal, 28(4):656–715.
Sloane, N. J. A. (2019). The on-line encyclopedia of integer sequences. http://oeis.org.
Stanica, P. (2007). Graph eigenvalues and Walsh spectrum of Boolean functions. Integers: Electronic Journal of Combinatorial Number Theory, 7(2).
Tao, T. (2015). Expansion in Finite Simple Groups of Lie Type. Graduate Studies in Mathematics: 164. American Mathematical Society, United States of America.
The Sage Developers (2009). SageMath, the Sage Mathematics Software System (Version 4.3). https://www.sagemath.org.
Waqas, U., Afzal, S., Mir, M. A., and Yousaf, M. (2014). Generation of AES-like sboxes by replacing affine matrix. In 2014 12th International Conference on Frontiers of Information Technology, pages 159–164.
Canteaut, A. (2016). Lecture notes on cryptographic Boolean functions. Inria, Paris, France.
Carlet, C. (2010). Boolean Functions for Cryptography and Error-Correcting Codes, page 257–397. Encyclopedia of Mathematics and its Applications. Cambridge University Press.
Carlet, C. and Ding, C. (2007). Nonlinearities of s-boxes. Finite Fields and Their Applications, 13(1):121 – 135.
Chandrasekharappa, T. (2012). Enhancement of confidentiality and integrity using cryptographic techniques. PhD thesis, Manipal University, Manipal - India.
Chandrasekharappa, T., Prema, K., and Kumara, S. (2011). S-boxes generated using affine transformation giving maximum avalanche effect. Int. J. Comput. Sci. Eng., 3(9):3185–3193.
Charles, D. X., Lauter, K. E., and Goren, E. Z. (2009). Cryptographic hash functions from expander graphs. Journal of Cryptology, 22(1):93–113.
Costache, A., Feigon, B., Lauter, K. E., Massierer, M., and Puskás, A. (2018). Ramanujan graphs in cryptography. IACR Cryptology ePrint Archive, 2018:593.
Cui, J., Huang, L., Zhong, H., Chang, C., and Yang, W. (2011). An improved AES s-box and its performance analysis. International Journal of Innovative Computing, Information and Control, 7:2291–2302.
Daemen, J. and Rijmen, V. (2002). The Design of Rijndael. Springer-Verlag, Berlin, Heidelberg.
Das, S., Zaman, J. U., and Ghosh, R. (2013). Generation of AES s-boxes with various modulus and additive constant polynomials and testing their randomization. Procedia Technology, 10:957 – 962. First International Conference on Computational Intelligence: Modeling Techniques and Applications (CIMTA) 2013.
Davidoff, G., Sarnak, P., and Valette, A. (2003). Elementary Number Theory, Group Theory and Ramanujan Graphs. Number 55 in London Mathematical Society Student Texts. Cambridge University Press.
de la Cruz Jiménez, R. A. (2019). Generation of 8-bit s-boxes having almost optimal cryptographic properties using smaller 4-bit s-boxes and finite field multiplication. In Lange, T. and Dunkelman, O., editors, Progress in Cryptology – LATINCRYPT 2017, pages 191–206, Cham. Springer International Publishing.
Deva Sinha, S. and Arya, C. (2012). Algebraic construction and cryptographic properties of Rijndael substitution box. Defence Science Journal, 62:32–37.
Hoory, S., Linial, N., and Wigderson, A. (2006). Expander graphs and their applications. BULL. AMER. MATH. SOC., 43(4):439–561.
Isa, H., Jamil, N., and Reza Z ’aba, M. (2016). Hybrid heuristic methods in constructing cryptographically strong s-boxes. International Journal of Cryptology Research, 6:1– 15.
Klima, R. and Sigmon, N. (2016). Applied abstract algebra with MAPLE and MATLAB. Textbook in mathematics. CRC Press, London, 3rd ed. edition.
Lubotzky, A., Phillips, R., and Sarnak, P. (1988). Ramanujan graphs. Combinatorica, 8(3):261–277.
Meier,W. and Staffelbach, O. (1990). Nonlinearity criteria for cryptographic functions. In Quisquater, J.-J. and Vandewalle, J., editors, Advances in Cryptology — EUROCRYPT ’89, pages 549–562, Berlin, Heidelberg. Springer Berlin Heidelberg.
Murty, M. R. (2003). Ramanujan graphs. J. Ramanujan Math. Soc, 18:1–20.
Nover, H. (2005). Algebraic Cryptanalysis of AES: An Overview. University of Wisconsin, USA, pages 1–16.
Paar, C. and Pelzl, J. (2010). The Data Encryption Standard (DES) and Alternatives, pages 55–86. Springer Berlin Heidelberg, Berlin, Heidelberg.
Shannon, C. E. (1949). Communication theory of secrecy systems. The Bell System Technical Journal, 28(4):656–715.
Sloane, N. J. A. (2019). The on-line encyclopedia of integer sequences. http://oeis.org.
Stanica, P. (2007). Graph eigenvalues and Walsh spectrum of Boolean functions. Integers: Electronic Journal of Combinatorial Number Theory, 7(2).
Tao, T. (2015). Expansion in Finite Simple Groups of Lie Type. Graduate Studies in Mathematics: 164. American Mathematical Society, United States of America.
The Sage Developers (2009). SageMath, the Sage Mathematics Software System (Version 4.3). https://www.sagemath.org.
Waqas, U., Afzal, S., Mir, M. A., and Yousaf, M. (2014). Generation of AES-like sboxes by replacing affine matrix. In 2014 12th International Conference on Frontiers of Information Technology, pages 159–164.
Publicado
02/09/2019
Como Citar
BELLEZA, Marcio; BORGES, Fábio.
Construção de S-Boxes com Valores Ótimos de Não Linearidade Baseada em uma Relação entre o Multigrafo de Ramanujan e a Matriz da Transformação Afim. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 19. , 2019, São Paulo.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 225-238.
DOI: https://doi.org/10.5753/sbseg.2019.13974.
