Speeding up Elliptic Curve Cryptography on the P-384 Curve
Resumo
A P-384 é uma das curvas elípticas padronizadas pelo ANSI e o NIST. Ela fornece um nível de segurança de 192 bits e é usada tanto na computação de assinaturas digitais como nos protocolos de acordo de chaves. Embora várias bibliotecas criptográficas disponíveis publicamente suportam a P-384, elas possuem um baixo desempenho. Neste trabalho, apresentamos técnicas de implementação em software para acelerar operações criptográficas usando a curva P-384; primeiro, usamos as mais novas instruções vetoriais dos processadores Intel para implementar a aritmética de corpo primo; depois, propomos um escalonamento paralelo das fórmulas completas para calcular a lei de adição de pontos. Como resultado, na microarquitetura Skylake, a nossa implementação em software é 15% e 40% mais rápida do que a biblioteca OpenSSL para calcular assinaturas ECDSA e o protocolo ECDH, respectivamente.
Referências
ANSI (1999). ANS X9.62 Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA).
ANSI (2001). ANS X9.63 Public Key Cryptography for the Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography.
Aranha, D. F. and Gouvêa, C. P. L. (2009). RELIC is an Efficient LIbrary for Cryptography. https://github.com/relic-toolkit.
Bakker, P. (2008). mbed TLS. (v2.3). https://tls.mbed.org/.
Barker, E. B., Johnson, D., and Smid, M. E. (2007). SP 800-56A. Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography (Revised).
Bos, J. W., Costello, C., Longa, P., and Naehrig, M. (2015). Selecting elliptic curves for cryptography: an efficiency and security analysis. Journal of Cryptographic Engineering, pages 1–28.
Bos, J. W., Halderman, J. A., Heninger, N., Moore, J., Naehrig, M., and Wustrow, E. (2014). Elliptic Curve Cryptography in Practice, pages 157–175. Springer Berlin Heidelberg, Berlin, Heidelberg.
Bosma, W. and Lenstra, H. (1995). Complete Systems of Two Addition Laws for Elliptic Curves. Journal of Number Theory, 53(2):229–240.
Brown, D. R. L. (2009). SEC 1: Elliptic Curve Cryptography. http://www.secg.org/sec1-v2.pdf.
CNSS (2012). National Information Assurance Policy on the Use of Public Standards for the Secure Sharing of Information Among National Security Systems. CNSSP Policy 15. https://www.cnss.gov/CNSS/issuances/Policies.cfm.
CNSS (2015). Use of Public Standards for the Secure Sharing of Information among National Security Systems. CNSS Advisory Memorandum 02-15. https://www.cnss.gov/CNSS/issuances/Memoranda.cfm.
Google (2015). BoringSSL. [link].
Granger, R. and Scott, M. (2015). Faster ECC over F2521-1. In Katz, J., editor, Public-Key Cryptography – PKC 2015: 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 – April 1, 2015, Proceedings, pages 539–553, Berlin, Heidelberg. Springer Berlin Heidelberg.
Gueron, S. and Krasnov, V. (2014). Fast prime field ellipticcurve cryptography with 256-bit primes. Journal of Cryptographic Engineering, pages 1–11.
Hankerson, D., Menezes, A. J., and Vanstone, S. (2003). Guide to Elliptic Curve Cryptography. Springer-Verlag New York, Inc., Secaucus, NJ, USA.
IEEE (2000). IEEE Standard Specifications for Public-Key Cryptography. Number 1363, pages 1–228. IEEE Std 1363-2000.
Intel Corporation (2011). Intel R Advanced Vector Extensions Programming Reference. Technical report. https://software.intel.com/sites/default/files/m/f/7/c/36945.
Izu, T. and Takagi, T. (2002). Exceptional Procedure Attack on Elliptic Curve Cryptosystems. In Desmedt, Y. G., editor, Public Key Cryptography — PKC 2003: 6th International Workshop on Practice and Theory in Public Key Cryptography Miami, FL, USA, January 6–8, 2003 Proceedings, pages 224–239, Berlin, Heidelberg. Springer Berlin Heidelberg.
Käsper, E. (2012). Fast Elliptic Curve Cryptography in OpenSSL. In Danezis, G., Dietrich, S., and Sako, K., editors, Financial Cryptography and Data Security, volume 7126 of Lecture Notes in Computer Science, pages 27–39. Springer Berlin Heidelberg.
Koblitz, N. (1987). Elliptic Curve Cryptosystems. Mathematics of Computation, 48(177):203–209.
Miller, V. S. (1986). Use of Elliptic Curves in Cryptography. In Williams, H. C., editor, Advances in Cryptology — CRYPTO ’85 Proceedings, volume 218 of Lecture Notes in Computer Science, pages 417–426. Springer Berlin Heidelberg.
Niels Möller (2001). Nettle. http://www.lysator.liu.se/~nisse/nettle.
NIST (1999). Recommended elliptic curves for federal government use.
NIST (2000). Digital Signature Standard (DSS). Federal Information Processing Standards Publication 186-2. http://csrc.nist.gov/publications/fips/archive/fips186-2/fips186-2.pdf.
Pollard, J. (1975). A monte carlo method for factorization. BIT Numerical Mathematics, 15(3):331–334.
Proos, J. and Zalka, C. (2003). Shor’s Discrete Logarithm Quantum Algorithm for Elliptic Curves. Quantum Information & Computation, 3(4):317–344.
Renes, J., Costello, C., and Batina, L. (2016). Complete Addition Formulas for Prime Order Elliptic Curves. In Fischlin, M. and Coron, J.-S., editors, Advances in Cryptology – EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, pages 403–428, Berlin, Heidelberg. Springer Berlin Heidelberg.
Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126.
Solinas, J. (2000). Efficient Arithmetic on Koblitz Curves. Designs, Codes and Cryptography, 19(2-3):195–249.
Solinas, J. A. (1999). Generalized Mersenne Numbers. Technical Report CORR 99-39, Center of Applied Cryptographic Research (CACR).
The OpenSSL Project (2003). OpenSSL: The Open Source toolkit for SSL/TLS. http://www.openssl.org.
Vanstone, S., Rivest, R. L., Hellman, M. E., Anderson, J. C., and Lyons, J. W. (1992). Responses to NIST’s Proposal. Communications of the ACM, 35(7):41–54. (John Anderson communicated Vanstone’s proposal).
ANSI (2001). ANS X9.63 Public Key Cryptography for the Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography.
Aranha, D. F. and Gouvêa, C. P. L. (2009). RELIC is an Efficient LIbrary for Cryptography. https://github.com/relic-toolkit.
Bakker, P. (2008). mbed TLS. (v2.3). https://tls.mbed.org/.
Barker, E. B., Johnson, D., and Smid, M. E. (2007). SP 800-56A. Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography (Revised).
Bos, J. W., Costello, C., Longa, P., and Naehrig, M. (2015). Selecting elliptic curves for cryptography: an efficiency and security analysis. Journal of Cryptographic Engineering, pages 1–28.
Bos, J. W., Halderman, J. A., Heninger, N., Moore, J., Naehrig, M., and Wustrow, E. (2014). Elliptic Curve Cryptography in Practice, pages 157–175. Springer Berlin Heidelberg, Berlin, Heidelberg.
Bosma, W. and Lenstra, H. (1995). Complete Systems of Two Addition Laws for Elliptic Curves. Journal of Number Theory, 53(2):229–240.
Brown, D. R. L. (2009). SEC 1: Elliptic Curve Cryptography. http://www.secg.org/sec1-v2.pdf.
CNSS (2012). National Information Assurance Policy on the Use of Public Standards for the Secure Sharing of Information Among National Security Systems. CNSSP Policy 15. https://www.cnss.gov/CNSS/issuances/Policies.cfm.
CNSS (2015). Use of Public Standards for the Secure Sharing of Information among National Security Systems. CNSS Advisory Memorandum 02-15. https://www.cnss.gov/CNSS/issuances/Memoranda.cfm.
Google (2015). BoringSSL. [link].
Granger, R. and Scott, M. (2015). Faster ECC over F2521-1. In Katz, J., editor, Public-Key Cryptography – PKC 2015: 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 – April 1, 2015, Proceedings, pages 539–553, Berlin, Heidelberg. Springer Berlin Heidelberg.
Gueron, S. and Krasnov, V. (2014). Fast prime field ellipticcurve cryptography with 256-bit primes. Journal of Cryptographic Engineering, pages 1–11.
Hankerson, D., Menezes, A. J., and Vanstone, S. (2003). Guide to Elliptic Curve Cryptography. Springer-Verlag New York, Inc., Secaucus, NJ, USA.
IEEE (2000). IEEE Standard Specifications for Public-Key Cryptography. Number 1363, pages 1–228. IEEE Std 1363-2000.
Intel Corporation (2011). Intel R Advanced Vector Extensions Programming Reference. Technical report. https://software.intel.com/sites/default/files/m/f/7/c/36945.
Izu, T. and Takagi, T. (2002). Exceptional Procedure Attack on Elliptic Curve Cryptosystems. In Desmedt, Y. G., editor, Public Key Cryptography — PKC 2003: 6th International Workshop on Practice and Theory in Public Key Cryptography Miami, FL, USA, January 6–8, 2003 Proceedings, pages 224–239, Berlin, Heidelberg. Springer Berlin Heidelberg.
Käsper, E. (2012). Fast Elliptic Curve Cryptography in OpenSSL. In Danezis, G., Dietrich, S., and Sako, K., editors, Financial Cryptography and Data Security, volume 7126 of Lecture Notes in Computer Science, pages 27–39. Springer Berlin Heidelberg.
Koblitz, N. (1987). Elliptic Curve Cryptosystems. Mathematics of Computation, 48(177):203–209.
Miller, V. S. (1986). Use of Elliptic Curves in Cryptography. In Williams, H. C., editor, Advances in Cryptology — CRYPTO ’85 Proceedings, volume 218 of Lecture Notes in Computer Science, pages 417–426. Springer Berlin Heidelberg.
Niels Möller (2001). Nettle. http://www.lysator.liu.se/~nisse/nettle.
NIST (1999). Recommended elliptic curves for federal government use.
NIST (2000). Digital Signature Standard (DSS). Federal Information Processing Standards Publication 186-2. http://csrc.nist.gov/publications/fips/archive/fips186-2/fips186-2.pdf.
Pollard, J. (1975). A monte carlo method for factorization. BIT Numerical Mathematics, 15(3):331–334.
Proos, J. and Zalka, C. (2003). Shor’s Discrete Logarithm Quantum Algorithm for Elliptic Curves. Quantum Information & Computation, 3(4):317–344.
Renes, J., Costello, C., and Batina, L. (2016). Complete Addition Formulas for Prime Order Elliptic Curves. In Fischlin, M. and Coron, J.-S., editors, Advances in Cryptology – EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, pages 403–428, Berlin, Heidelberg. Springer Berlin Heidelberg.
Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126.
Solinas, J. (2000). Efficient Arithmetic on Koblitz Curves. Designs, Codes and Cryptography, 19(2-3):195–249.
Solinas, J. A. (1999). Generalized Mersenne Numbers. Technical Report CORR 99-39, Center of Applied Cryptographic Research (CACR).
The OpenSSL Project (2003). OpenSSL: The Open Source toolkit for SSL/TLS. http://www.openssl.org.
Vanstone, S., Rivest, R. L., Hellman, M. E., Anderson, J. C., and Lyons, J. W. (1992). Responses to NIST’s Proposal. Communications of the ACM, 35(7):41–54. (John Anderson communicated Vanstone’s proposal).
Publicado
07/11/2016
Como Citar
FAZ-HERNÁNDEZ, Armando; LÓPEZ, Julio.
Speeding up Elliptic Curve Cryptography on the P-384 Curve. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 16. , 2016, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 170-183.
DOI: https://doi.org/10.5753/sbseg.2016.19306.
