Curve25519

From HandWiki
Short description: Elliptic curve used in Internet cryptography

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

The curve used is [math]\displaystyle{ y^2 = x^3 + 486662x^2 + x }[/math], a Montgomery curve, over the prime field defined by the prime number [math]\displaystyle{ 2^{255} - 19 }[/math] (hence the numeric "25519" in the name), and it uses the base point [math]\displaystyle{ x = 9 }[/math]. This point generates a cyclic subgroup whose order is the prime [math]\displaystyle{ 2^{252} + 27742317777372353535851937790883648493 }[/math]. This subgroup has a co-factor of [math]\displaystyle{ 8 }[/math], meaning the number of elements in the subgroup is [math]\displaystyle{ 1/8 }[/math] 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]

By design, Curve25519 is immune to timing attacks, and it accepts any 32-byte string as a valid public key and does not require validating that a given point belongs to the curve, or is generated by the base point.[citation needed]

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

History

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."

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] Behavior for general SSH protocol is still being standardized as of 2018.[20][needs update]

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.[21] Both are described in RFC 7748.[22] A 2019 draft of "FIPS 186-5" notes the intention to allow usage of Ed25519[23] for digital signatures. A 2019 draft of Special Publication 800-186 notes the intention to allow usage of Curve25519.[24]

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

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.[26]

Libraries


Protocols

Applications


Notes

  1. ↑ Starting with Windows 10 (1607), Windows Server 2016
  2. ↑ 2.0 2.1 2.2 Via the OMEMO protocol
  3. ↑ Only in "secret conversations"
  4. ↑ 4.0 4.1 4.2 4.3 Via the Signal Protocol
  5. ↑ Only in "incognito mode"
  6. ↑ Used to sign releases and packages[51][52]
  7. ↑ Exclusive key exchange in OpenSSH 6.7 when compiled without OpenSSL.[53][54]

References

  1. ↑ Bernstein. "Irrelevant patents on elliptic-curve cryptography". https://cr.yp.to/ecdh/patents.html. 
  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". 5 March 2019. https://www.cryptopp.com/wiki/X25519. 
  4. ↑ "[Cfrg 25519 naming"]. https://www.ietf.org/mail-archive/web/cfrg/current/msg04996.html. 
  5. ↑ 5.0 5.1 Bernstein, Daniel J. (2006). "Public Key Cryptography - PKC 2006". in Yung, Moti; Dodis, Yevgeniy; Kiayias, Aggelos et al.. Public Key Cryptography. 3958. New York: Springer. pp. 207–228. doi:10.1007/11745853_14. ISBN 978-3-540-33851-2. 
  6. ↑ Lange, Tanja. "EFD / Genus-1 large-characteristic / XZ coordinates for Montgomery curves". https://www.hyperelliptic.org/EFD/g1p/auto-montgom-xz.html. 
  7. ↑ Bernstein, Daniel J.; Lange, Tanja (2017-01-22). "SafeCurves: Introduction". SafeCurves: choosing safe curves for elliptic-curve cryptography. https://safecurves.cr.yp.to. 
  8. ↑ Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Yang, Bo-Yin (2017-01-22). "Ed25519: high-speed high-security signatures". http://ed25519.cr.yp.to/. 
  9. ↑ Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Yang, Bo-Yin (2011-09-26). "High-speed high-security signatures". http://ed25519.cr.yp.to/ed25519-20110926.pdf. 
  10. ↑ Bernstein, Daniel J.; Lange, Tanja (2007). "Advances in Cryptology – ASIACRYPT 2007". in Kurosawa, Kaoru. Advances in cryptology—ASIACRYPT. 4833. Berlin: Springer. pp. 29–50. doi:10.1007/978-3-540-76900-2_3. ISBN 978-3-540-76899-9. 
  11. ↑ Kelsey, John (May 2014). "Dual EC in X9.82 and SP 800-90". https://csrc.nist.gov/csrc/media/projects/crypto-standards-development-process/documents/dualec_in_x982_and_sp800-90.pdf. 
  12. ↑ Green, Matthew (2015-01-14). "A Few Thoughts on Cryptographic Engineering: The Many Flaws of Dual_EC_DRBG". http://blog.cryptographyengineering.com/2013/09/the-many-flaws-of-dualecdrbg.html. 
  13. ↑ "SafeCurves: Introduction". https://safecurves.cr.yp.to/. 
  14. ↑ Maxwell, Gregory (2013-09-08). "[tor-talk NIST approved crypto in Tor?"]. https://lists.torproject.org/pipermail/tor-talk/2013-September/029956.html. 
  15. ↑ "SafeCurves: Rigidity". https://safecurves.cr.yp.to/rigid.html. 
  16. ↑ "The NSA Is Breaking Most Encryption on the Internet - Schneier on Security". https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1675929. 
  17. ↑ "Things that use Curve25519". https://ianix.com/pub/curve25519-deployment.html. 
  18. ↑ 18.0 18.1 Adamantiadis, Aris (2013-11-03). "OpenSSH introduces curve25519-sha256@libssh.org key exchange !". libssh.org. https://www.libssh.org/2013/11/03/openssh-introduces-curve25519-sha256libssh-org-key-exchange/. 
  19. ↑ "GnuPG - What's new in 2.1". August 2021. https://gnupg.org/faq/whats-new-in-2.1.html. 
  20. ↑ A. Adamantiadis; libssh; S. Josefsson; SJD AB; M. Baushke; Juniper Networks, Inc. (2018-06-26), Secure Shell (SSH) Key Exchange Method using Curve25519 and Curve448, I-D draft-ietf-curdle-ssh-curves-08, https://tools.ietf.org/html/draft-ietf-curdle-ssh-curves-08 
  21. ↑ "Transition Plans for Key Establishment Schemes" (in EN-US). 2017-10-31. https://csrc.nist.gov/News/2017/Transition-Plans-for-Key-Establishment-Schemes. 
  22. ↑ RFC 7748. Retrieved from rfc:7748.
  23. ↑ Regenscheid, Andrew (31 October 2019). FIPS PUB 186-5. doi:10.6028/NIST.FIPS.186-5-draft. https://csrc.nist.gov/publications/detail/fips/186/5/draft. 
  24. ↑ "Recommendations for Discrete Logarithm-Based Cryptography". https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf. 
  25. ↑ John Levine (September 2018), A New Cryptographic Signature Method for DomainKeys Identified Mail (DKIM), IETF, doi:10.17487/RFC8463, RFC 8463, https://tools.ietf.org/html/rfc8463 
  26. ↑ E Rescorla (September 2018), The Transport Layer Security (TLS) Protocol Version 1.3, IETF, doi:10.17487/RFC8446, RFC 8446, https://tools.ietf.org/html/rfc8446 
  27. ↑ Werner Koch (15 April 2016). "Libgcrypt 1.7.0 release announcement". https://lists.gnupg.org/pipermail/gnupg-announce/2016q2/000386.html. 
  28. ↑ 28.0 28.1 28.2 28.3 28.4 28.5 28.6 SSH implementation comparison. "Comparison of key exchange methods". http://ssh-comparison.quendi.de/comparison/kex.html. 
  29. ↑ "Introduction". yp.to. https://nacl.cr.yp.to/. 
  30. ↑ "nettle: curve25519.h File Reference". http://fossies.org/dox/nettle-3.1.1/curve25519_8h.html. 
  31. ↑ Limited, ARM. "PolarSSL 1.3.3 released - Tech Updates - mbed TLS (Previously PolarSSL)". https://tls.mbed.org/tech-updates/releases/polarssl-1.3.3-released. 
  32. ↑ "wolfSSL Embedded SSL/TLS Library | Products – wolfSSL". https://www.wolfssl.com/products/wolfssl/. 
  33. ↑ "Botan: src/lib/pubkey/curve25519/curve25519.cpp Source File". http://botan.randombit.net/doxygen/curve25519_8cpp_source.html. 
  34. ↑ Justinha. "TLS (Schannel SSP)" (in en-us). https://docs.microsoft.com/en-us/windows-server/security/tls/tls-schannel-ssp-changes-in-windows-10-and-windows-server. 
  35. ↑ Denis, Frank. "Introduction · libsodium". https://libsodium.org. 
  36. ↑ "OpenSSL 1.1.0 Series Release Notes". https://www.openssl.org/news/openssl-1.1.0-notes.html. 
  37. ↑ "Add support for ECDHE with X25519. · openbsd/src@0ad90c3". https://github.com/openbsd/src/commit/0ad90c3e6b15b9b6b8463a8a0f87d70c83a07ef4. 
  38. ↑ "NSS 3.28 release notes". https://developer.mozilla.org/en-US/docs/Mozilla/Projects/NSS/NSS_3.28_release_notes. 
  39. ↑ "A pure-Rust implementation of group operations on ristretto255 and Curve25519". https://github.com/dalek-cryptography/curve25519-dalek/. 
  40. ↑ "Ed25519.java". 13 October 2021. https://github.com/bcgit/bc-java/blob/bc3b92f1f0e78b82e2584c5fb4b226a13e7f8b3b/core/src/main/java/org/bouncycastle/math/ec/rfc8032/Ed25519.java. 
  41. ↑ Straub, Andreas (25 October 2015). "OMEMO Encryption". https://conversations.im/xeps/multi-end.html#usecases-setup. 
  42. ↑ "Cryptocat - Security". https://crypto.cat/security.html#encryption. 
  43. ↑ Frank Denis. "DNSCrypt version 2 protocol specification". https://github.com/jedisct1/dnscrypt-proxy/blob/master/DNSCRYPT-V2-PROTOCOL.txt/. 
  44. ↑ Matt Johnston. "Dropbear SSH - Changes". https://matt.ucc.asn.au/dropbear/CHANGES. 
  45. ↑ Bahtiar Gadimov. "Gajim plugin for OMEMO Multi-End Message and Object Encryption". https://github.com/omemo/gajim-omemo. 
  46. ↑ "GNUnet 0.10.0". gnunet.org. https://gnunet.org/gnunet0-10-0. 
  47. ↑ zzz (2014-09-20). "0.9.15 Release - Blog". https://geti2p.net/en/blog/post/2014/09/20/0.9.15-Release. 
  48. ↑ "go-ipfs_keystore.go at master". Github.com. 30 March 2022. https://github.com/ipfs/go-ipfs/blob/master/core/commands/keystore.go#L68. 
  49. ↑ "Apple Platform Security". https://support.apple.com/guide/security/welcome/web. 
  50. ↑ "MRL-0003 - Monero is Not That Mysterious". https://lab.getmonero.org/pubs/MRL-0003.pdf. 
  51. ↑ Murenin, Constantine A. (2014-01-19). "OpenBSD Moving Towards Signed Packages — Based On D. J. Bernstein Crypto". in Soulskill. Slashdot. http://bsd.slashdot.org/story/14/01/19/0124202/openbsd-moving-towards-signed-packages-based-on-d-j-bernstein-crypto. 
  52. ↑ Murenin, Constantine A. (2014-05-01). "OpenBSD 5.5 Released". in timothy. Slashdot. http://bsd.slashdot.org/story/14/05/01/1656209/openbsd-55-released. 
  53. ↑ Friedl, Markus (2014-04-29). "ssh/kex.c#kexalgs". http://bxr.su/OpenBSD/usr.bin/ssh/kex.c#kexalgs. 
  54. ↑ Murenin, Constantine A. (2014-04-30). "OpenSSH No Longer Has To Depend On OpenSSL". in Soulskill. Slashdot. http://it.slashdot.org/story/14/04/30/1822209/openssh-no-longer-has-to-depend-on-openssl. 
  55. ↑ "How does Peerio implement end-to-end encryption?". https://peerio.zendesk.com/hc/en-us/articles/204155895-How-does-Peerio-implement-end-to-end-encryption. 
  56. ↑ "Proton Mail now offers elliptic curve cryptography for advanced security and faster speeds". 25 April 2019. https://proton.me/blog/elliptic-curve-cryptography. 
  57. ↑ "PuTTY Change Log". http://www.chiark.greenend.org.uk/~sgtatham/putty/changes.html. 
  58. ↑ Steve Gibson (December 2019). "SQRL Cryptography whitepaper". https://www.grc.com/sqrl/SQRL_Cryptography.pdf. 
  59. ↑ "Threema Cryptography Whitepaper". https://threema.ch/press-files/cryptography_whitepaper.pdf. 
  60. ↑ Roger Dingledine & Nick Mathewson. "Tor's Protocol Specifications - Blog". https://gitweb.torproject.org/torspec.git/tree/tor-spec.txt?id=b5b771b19df9fc052b424228045409467a7b6414#n81. 
  61. ↑ "Viber Encryption Overview". Viber. 3 May 2016. https://www.viber.com/en/security-overview. 
  62. ↑ Nidhi Rastogi; James Hendler (2017-01-24). "WhatsApp security and role of metadata in preserving privacy". arXiv:1701.06817 [cs.CR].

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Curve25519&oldid=3381014"