Implementação em software do Esquema de Assinatura Digital de Merkle e suas variantes
Resumo
Neste trabalho é descrita uma implementação eficiente em software do esquema de assinatura digital Merkle e suas variantes XMSS, CMSS e GMSS. Nossa implementação é baseada nas funções de resumo SHA-2 e SHA-3 com nível de segurança de 128 bits e executado em um processador Intel Core i7 2.2 GHz. As principais contribuições deste trabalho são um estudo aprofundado do esquema de assinatura digital Merkle e uma implementação otimizada para a plataforma Intel com instruções de 64/128 bits.
Palavras-chave:
criptografia pós-quântica, assinaturas digitais, esquema de Merkle
Referências
Bernstein, D., Buchmann, J., and Dahmen, E. (2009). Post-quantum cryptography. pages 35–93. Springer.
Bertoni, G., J.Daemen, M.Peeters, and Assche1, G. (2012). The keccak sponge function family SHA-3. http://keccak.noekeon.org/.
Buchmann, J., Coronado, C., Dahmen, E., Döring, M., and Klintsevich, E. (2006). CMSS– an improved merkle signature scheme. In Progress in Cryptology – INDOCRYPT 2006, LNCS 4329, pages 349–363. Springe-Verlag.
Buchmann, J., Dahmen, E., Ereth, S., Hülsing, A., and Rückert, M. (2011a). On the security of the winternitz one-time signature scheme. In German Research, pages 1– 17.
Buchmann, J., Dahmen, E., and Hülsing, A. (2011b). XMSS-a practical secure signature scheme based on minimal security assumptions. In Cryptology ePrint Archive - Report 2011/484. ePrint.
Buchmann, J., Dahmen, E., Klintsevich, E., Okeya, K., and Vuillaume, C. (2007). Merkle signatures with virtually unlimited signature capacity. In Applied Cryptography and Network Security - ACNS 2007, LNCS 4521, pages 31–45. Springer.
Buchmann, J., Dahmen, E., and Schneider, M. (2008). Merkle tree traversal revisited. In Proceedings of the 2nd InternationalWorkshop on Post-Quantum Cryptography, pages 63–78. Springer-Verlag.
Diffie, W. and Hellman, M. E. (1976). New directions in cryptography. In IEEE Trans. Information Theory, pages 644–654. IT-22.
Dods, C., Smart, N., and Stam, M. (2005). Hash-based digital signature schemes. In In Cryptography and Coding, LNCS 3796, pages 96–115. Springer.
Johnson, D., Menezes, A., and Vanstone, S. (2001). Elliptic Curve Digital Signature Algorithm ECDSA. page 36–63. Springer-Verlag.
Katz, J. and Lindell, Y. (2008). Introduction to modern cryptography. pages 127–133. Chapman.
Merkle, R. (1987). A digital signature based on a conventional encryption function. In Proceedings of Crypto ’87, pages 369–378. Springer.
Merkle, R. C. (1979). Secrecy, Authentication, and Public Key Systems. Stanford Ph.D. thesis.
NIST (1994). Digital Signatures Algorithm (DSA). FIPS-186, http://www.itl.nist.gov/fipspubs/fip186.htm.
NIST (2007). Digital Signature Standard (DSS). FIPS PUB-186-2, http://csrc.nist.gov/publications/fips.
NIST (2008). Sha-256. FIPS PUB 180-3, http://csrc.nist.gov/publications/fips.
Rivest, R., Shamir, A., and Adleman, L. (1977). A method for obtaining digital signatures and public-key cryptosystems. pages 120–126. Communications of the ACM.
Shor, P. (1994). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. IEEE Computer Society Press.
Shoufan, A. and Huber, N. (2010). A fast hash tree generator for merkle signature scheme. In Circuits and Systems (ISCAS), pages 3945–3948. IEEE International Symposium.
Shoufan, A., Huber, N., and Molter, H. (2011). A novel cryptoprocessor architecture for chained merkle signature scheme. In Microprocessors and Microsystems, pages 34–47. Elsevier.
Springle, K., Dai, W., Pavlov, I., and Collin, L. (2012). Modified version of the sha-256. http://svn.r-project.org/R/trunk/src/extra/xz/check/sha256.c.
Szydlo, M. (2003). Merkle tree traversal in log space and time. In Prepint version, 2003.
Vuillaume, C., Okeya, K., Dahmen, E., and Buchmann, J. (2009). Public Key Authentication with Memory Tokens. Development.
Bertoni, G., J.Daemen, M.Peeters, and Assche1, G. (2012). The keccak sponge function family SHA-3. http://keccak.noekeon.org/.
Buchmann, J., Coronado, C., Dahmen, E., Döring, M., and Klintsevich, E. (2006). CMSS– an improved merkle signature scheme. In Progress in Cryptology – INDOCRYPT 2006, LNCS 4329, pages 349–363. Springe-Verlag.
Buchmann, J., Dahmen, E., Ereth, S., Hülsing, A., and Rückert, M. (2011a). On the security of the winternitz one-time signature scheme. In German Research, pages 1– 17.
Buchmann, J., Dahmen, E., and Hülsing, A. (2011b). XMSS-a practical secure signature scheme based on minimal security assumptions. In Cryptology ePrint Archive - Report 2011/484. ePrint.
Buchmann, J., Dahmen, E., Klintsevich, E., Okeya, K., and Vuillaume, C. (2007). Merkle signatures with virtually unlimited signature capacity. In Applied Cryptography and Network Security - ACNS 2007, LNCS 4521, pages 31–45. Springer.
Buchmann, J., Dahmen, E., and Schneider, M. (2008). Merkle tree traversal revisited. In Proceedings of the 2nd InternationalWorkshop on Post-Quantum Cryptography, pages 63–78. Springer-Verlag.
Diffie, W. and Hellman, M. E. (1976). New directions in cryptography. In IEEE Trans. Information Theory, pages 644–654. IT-22.
Dods, C., Smart, N., and Stam, M. (2005). Hash-based digital signature schemes. In In Cryptography and Coding, LNCS 3796, pages 96–115. Springer.
Johnson, D., Menezes, A., and Vanstone, S. (2001). Elliptic Curve Digital Signature Algorithm ECDSA. page 36–63. Springer-Verlag.
Katz, J. and Lindell, Y. (2008). Introduction to modern cryptography. pages 127–133. Chapman.
Merkle, R. (1987). A digital signature based on a conventional encryption function. In Proceedings of Crypto ’87, pages 369–378. Springer.
Merkle, R. C. (1979). Secrecy, Authentication, and Public Key Systems. Stanford Ph.D. thesis.
NIST (1994). Digital Signatures Algorithm (DSA). FIPS-186, http://www.itl.nist.gov/fipspubs/fip186.htm.
NIST (2007). Digital Signature Standard (DSS). FIPS PUB-186-2, http://csrc.nist.gov/publications/fips.
NIST (2008). Sha-256. FIPS PUB 180-3, http://csrc.nist.gov/publications/fips.
Rivest, R., Shamir, A., and Adleman, L. (1977). A method for obtaining digital signatures and public-key cryptosystems. pages 120–126. Communications of the ACM.
Shor, P. (1994). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. IEEE Computer Society Press.
Shoufan, A. and Huber, N. (2010). A fast hash tree generator for merkle signature scheme. In Circuits and Systems (ISCAS), pages 3945–3948. IEEE International Symposium.
Shoufan, A., Huber, N., and Molter, H. (2011). A novel cryptoprocessor architecture for chained merkle signature scheme. In Microprocessors and Microsystems, pages 34–47. Elsevier.
Springle, K., Dai, W., Pavlov, I., and Collin, L. (2012). Modified version of the sha-256. http://svn.r-project.org/R/trunk/src/extra/xz/check/sha256.c.
Szydlo, M. (2003). Merkle tree traversal in log space and time. In Prepint version, 2003.
Vuillaume, C., Okeya, K., Dahmen, E., and Buchmann, J. (2009). Public Key Authentication with Memory Tokens. Development.
Publicado
11/11/2013
Como Citar
OLIVEIRA, Ana Karina D. S.; LÓPEZ, Julio.
Implementação em software do Esquema de Assinatura Digital de Merkle e suas variantes. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 13. , 2013, Manaus.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2013
.
p. 295-308.
DOI: https://doi.org/10.5753/sbseg.2013.19553.
