Jump to content

Curve25519

From Wikipedia, the free encyclopedia
(Redirected from X25519)

In cryptography, Curve25519 is an elliptic curve used in elliptic-curve cryptography (ECC) offering 128 bits of security (256-bit key size) and designed for use with the Elliptic-curve Diffie–Hellman (ECDH) key agreement scheme. It is one of the fastest curves in ECC, and is not covered by any known patents.[1] The reference implementation is public domain software.[2][3]

The original Curve25519 paper defined it as a Diffie–Hellman (DH) function. Daniel J. Bernstein has since proposed that the name Curve25519 be used for the underlying curve, and the name X25519 for the DH function.[4]

Mathematical properties

[edit]

The curve used is , a Montgomery curve, over the prime field defined by the prime number (hence the numeric "25519" in the name), and it uses the base point . This point generates a cyclic subgroup whose order is the prime . This subgroup has a co-factor of , meaning the number of elements in the subgroup is that of the elliptic curve group. Using a prime order subgroup prevents mounting a Pohlig–Hellman algorithm attack.[5]

The protocol uses compressed elliptic point (only X coordinates), so it allows efficient use of the Montgomery ladder for ECDH, using only XZ coordinates.[6]

Curve25519 is constructed such that it avoids many potential implementation pitfalls.[7]

The curve is birationally equivalent to a twisted Edwards curve used in the Ed25519[8][9] signature scheme.[10]

History

[edit]

In 2005, Curve25519 was first released by Daniel J. Bernstein.[5]

In 2013, interest began to increase considerably when it was discovered that the NSA had potentially implemented a backdoor into the P-256 curve based Dual_EC_DRBG algorithm.[11] While not directly related,[12] suspicious aspects of the NIST's P curve constants[13] led to concerns[14] that the NSA had chosen values that gave them an advantage in breaking the encryption.[15][16]

"I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry."

— Bruce Schneier, The NSA Is Breaking Most Encryption on the Internet (2013)

Since 2013, Curve25519 has become the de facto alternative to P-256, being used in a wide variety of applications.[17] Starting in 2014, OpenSSH[18] defaults to Curve25519-based ECDH and GnuPG adds support for Ed25519 keys for signing and encryption.[19] The use of the curve was eventually standardized for both key exchange and signature in 2020.[20][21]

In 2017, NIST announced that Curve25519 and Curve448 would be added to Special Publication 800-186, which specifies approved elliptic curves for use by the US Federal Government.[22] Both are described in RFC 7748.[23] A 2019 draft of "FIPS 186-5" notes the intention to allow usage of Ed25519[24] for digital signatures. The 2023 update of Special Publication 800-186 allows usage of Curve25519.[25]

In 2018, DKIM specification was amended so as to allow signatures with this algorithm.[26]

Also in 2018, RFC 8446 was published as the new Transport Layer Security v1.3 standard. It recommends support for X25519, Ed25519, X448, and Ed448 algorithms.[27]

Libraries

[edit]

Protocols

[edit]

Applications

[edit]

Notes

[edit]
  1. ^ Starting with Windows 10 (1607), Windows Server 2016
  2. ^ a b c Via the OMEMO protocol
  3. ^ Only in "secret conversations"
  4. ^ a b c d Via the Signal Protocol
  5. ^ Only in "incognito mode"
  6. ^ Used to sign releases and packages[52][53]
  7. ^ Exclusive key exchange in OpenSSH 6.7 when compiled without OpenSSL.[54][55]

References

[edit]
  1. ^ Bernstein. "Irrelevant patents on elliptic-curve cryptography". cr.yp.to. Retrieved 2016-02-08.
  2. ^ A state-of-the-art Diffie-Hellman function by Daniel J. Bernstein"My curve25519 library computes the Curve25519 function at very high speed. The library is in the public domain."
  3. ^ "X25519". Crypto++. 5 March 2019. Archived from the original on 29 August 2020. Retrieved 3 February 2023.
  4. ^ "[Cfrg] 25519 naming". Retrieved 2016-02-25.
  5. ^ a b Bernstein, Daniel J. (2006). "Curve25519: New Diffie-Hellman Speed Records" (PDF). In Yung, Moti; Dodis, Yevgeniy; Kiayias, Aggelos; et al. (eds.). Public Key Cryptography - PKC 2006. Public Key Cryptography. Lecture Notes in Computer Science. Vol. 3958. New York: Springer. pp. 207–228. doi:10.1007/11745853_14. ISBN 978-3-540-33851-2. MR 2423191.
  6. ^ Lange, Tanja. "EFD / Genus-1 large-characteristic / XZ coordinates for Montgomery curves". EFD / Explicit-Formulas Database. Retrieved 2016-02-08.
  7. ^ Bernstein, Daniel J.; Lange, Tanja (2017-01-22). "SafeCurves: Introduction". SafeCurves: choosing safe curves for elliptic-curve cryptography. Retrieved 2016-02-08.
  8. ^ Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Yang, Bo-Yin (2017-01-22). "Ed25519: high-speed high-security signatures". Retrieved 2019-11-09.
  9. ^ Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Yang, Bo-Yin (2011-09-26). "High-speed high-security signatures" (PDF). Retrieved 2019-11-09.
  10. ^ Bernstein, Daniel J.; Lange, Tanja (2007). "Faster addition and doubling on elliptic curves". In Kurosawa, Kaoru (ed.). Advances in Cryptology – ASIACRYPT 2007. Advances in cryptology—ASIACRYPT. Lecture Notes in Computer Science. Vol. 4833. Berlin: Springer. pp. 29–50. doi:10.1007/978-3-540-76900-2_3. ISBN 978-3-540-76899-9. MR 2565722.
  11. ^ Kelsey, John (May 2014). "Dual EC in X9.82 and SP 800-90" (PDF). National Institute of Standards in Technology. Retrieved 2018-12-02.
  12. ^ Green, Matthew (2015-01-14). "A Few Thoughts on Cryptographic Engineering: The Many Flaws of Dual_EC_DRBG". blog.cryptographyengineering.com. Retrieved 2015-05-20.
  13. ^ "SafeCurves: Introduction".
  14. ^ Maxwell, Gregory (2013-09-08). "[tor-talk] NIST approved crypto in Tor?". Retrieved 2015-05-20.
  15. ^ "SafeCurves: Rigidity". safecurves.cr.yp.to. Retrieved 2015-05-20.
  16. ^ "The NSA Is Breaking Most Encryption on the Internet - Schneier on Security". www.schneier.com. Retrieved 2015-05-20.
  17. ^ "Things that use Curve25519". Retrieved 2015-12-23.
  18. ^ a b Adamantiadis, Aris (2013-11-03). "OpenSSH introduces curve25519-sha256@libssh.org key exchange !". libssh.org. Retrieved 2014-12-27.
  19. ^ "GnuPG - What's new in 2.1". August 2021.
  20. ^ A. Adamantiadis; libssh; S. Josefsson; SJD AB; M. Baushke; Juniper Networks, Inc. (February 2020). Secure Shell (SSH) Key Exchange Method Using Curve25519 and Curve448. doi:10.17487/RFC8731. RFC 8731.
  21. ^ B. Harris; L. Velvindron (February 2020). Ed25519 and Ed448 Public Key Algorithms for the Secure Shell (SSH) Protocol. doi:10.17487/RFC8709. RFC 8709.
  22. ^ "Transition Plans for Key Establishment Schemes". National Institute of Standards and Technology. 2017-10-31. Archived from the original on 2018-03-11. Retrieved 2019-09-04.
  23. ^ RFC 7748. Retrieved from rfc:7748.
  24. ^ Regenscheid, Andrew (31 October 2019). "FIPS PUB 186-5". National Institute of Standards and Technology (Withdrawn Draft). doi:10.6028/NIST.FIPS.186-5-draft. S2CID 241055751.
  25. ^ "Recommendations for Discrete Logarithm-Based Cryptography" (PDF).
  26. ^ John Levine (September 2018). A New Cryptographic Signature Method for DomainKeys Identified Mail (DKIM). IETF. doi:10.17487/RFC8463. RFC 8463.
  27. ^ E Rescorla (September 2018). The Transport Layer Security (TLS) Protocol Version 1.3. IETF. doi:10.17487/RFC8446. RFC 8446.
  28. ^ Werner Koch (15 April 2016). "Libgcrypt 1.7.0 release announcement". Retrieved 22 April 2016.
  29. ^ a b c d e f g SSH implementation comparison. "Comparison of key exchange methods". Retrieved 2016-02-25.
  30. ^ "Introduction". yp.to. Retrieved 11 December 2014.
  31. ^ "nettle: curve25519.h File Reference". Fossies (doxygen documentation). Archived from the original on 2015-05-20. Retrieved 2015-05-19.
  32. ^ Limited, ARM. "PolarSSL 1.3.3 released - Tech Updates - mbed TLS (Previously PolarSSL)". tls.mbed.org. Retrieved 2015-05-19. {{cite web}}: |last= has generic name (help)
  33. ^ "wolfSSL Embedded SSL/TLS Library | Products – wolfSSL".
  34. ^ "Botan: src/lib/pubkey/curve25519/curve25519.cpp Source File". botan.randombit.net.
  35. ^ Justinha. "TLS (Schannel SSP)". docs.microsoft.com. Retrieved 2017-09-15.
  36. ^ Denis, Frank. "Introduction · libsodium". libsodium.org.
  37. ^ "OpenSSL 1.1.0 Series Release Notes". OpenSSL Foundation. Archived from the original on 2018-03-17. Retrieved 2016-06-24.
  38. ^ "Add support for ECDHE with X25519. · openbsd/src@0ad90c3". GitHub.
  39. ^ "NSS 3.28 release notes". Archived from the original on 9 December 2017. Retrieved 25 July 2017.
  40. ^ "A pure-Rust implementation of group operations on ristretto255 and Curve25519". GitHub. Retrieved 14 April 2021.
  41. ^ "Ed25519.java". GitHub. 13 October 2021.
  42. ^ Straub, Andreas (25 October 2015). "OMEMO Encryption". conversations.im.
  43. ^ "Cryptocat - Security". crypto.cat. Archived from the original on 2016-04-07. Retrieved 2016-05-24.
  44. ^ Frank Denis. "DNSCrypt version 2 protocol specification". GitHub. Archived from the original on 2015-08-13. Retrieved 2016-03-03.
  45. ^ Matt Johnston. "Dropbear SSH - Changes". Retrieved 2016-02-25.
  46. ^ Bahtiar Gadimov; et al. "Gajim plugin for OMEMO Multi-End Message and Object Encryption". GitHub. Retrieved 2016-10-01.
  47. ^ "GNUnet 0.10.0". gnunet.org. Archived from the original on 9 December 2017. Retrieved 11 December 2014.
  48. ^ zzz (2014-09-20). "0.9.15 Release - Blog". Retrieved 20 December 2014.
  49. ^ "go-ipfs_keystore.go at master". Github.com. 30 March 2022.
  50. ^ "Apple Platform Security". Apple Support.
  51. ^ "MRL-0003 - Monero is Not That Mysterious" (PDF). getmonero.com. Archived from the original (PDF) on 2019-05-01. Retrieved 2018-06-05.
  52. ^ Murenin, Constantine A. (2014-01-19). Soulskill (ed.). "OpenBSD Moving Towards Signed Packages — Based On D. J. Bernstein Crypto". Slashdot. Retrieved 2014-12-27.
  53. ^ Murenin, Constantine A. (2014-05-01). timothy (ed.). "OpenBSD 5.5 Released". Slashdot. Retrieved 2014-12-27.
  54. ^ Friedl, Markus (2014-04-29). "ssh/kex.c#kexalgs". BSD Cross Reference, OpenBSD src/usr.bin/. Retrieved 2014-12-27.
  55. ^ Murenin, Constantine A. (2014-04-30). Soulskill (ed.). "OpenSSH No Longer Has To Depend On OpenSSL". Slashdot. Retrieved 2014-12-26.
  56. ^ "How does Peerio implement end-to-end encryption?". Peerio. Archived from the original on 2017-12-09. Retrieved 2015-11-04.
  57. ^ "Proton Mail now offers elliptic curve cryptography for advanced security and faster speeds". 25 April 2019.
  58. ^ "PuTTY Change Log". www.chiark.greenend.org.uk.
  59. ^ Steve Gibson (December 2019). "SQRL Cryptography whitepaper" (PDF).
  60. ^ "Threema Cryptography Whitepaper" (PDF).
  61. ^ Roger Dingledine & Nick Mathewson. "Tor's Protocol Specifications - Blog". Retrieved 20 December 2014.
  62. ^ "Viber Encryption Overview". Viber. 3 May 2016. Retrieved 24 September 2016.
  63. ^ Nidhi Rastogi; James Hendler (2017-01-24). "WhatsApp security and role of metadata in preserving privacy". arXiv:1701.06817 [cs.CR].
[edit]