Ed25519
   HOME

TheInfoList



OR:

In
public-key cryptography Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
, Edwards-curve Digital Signature Algorithm (EdDSA) is a
digital signature A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature, where the prerequisites are satisfied, gives a recipient very high confidence that the message was created b ...
scheme using a variant of
Schnorr signature In cryptography, a Schnorr signature is a digital signature produced by the Schnorr signature algorithm that was described by Claus Schnorr. It is a digital signature scheme known for its simplicity, among the first whose security is based on the ...
based on
twisted Edwards curve In algebraic geometry, the twisted Edwards curves are plane models of elliptic curves, a generalisation of Edwards curves introduced by Daniel J. Bernstein, Bernstein, Birkner, Joye, Tanja Lange, Lange and Peters in 2008. The curve set is named a ...
s. It is designed to be faster than existing digital signature schemes without sacrificing security. It was developed by a team including Daniel J. Bernstein, Niels Duif,
Tanja Lange Tanja Lange is a German cryptographer and number theorist at the Eindhoven University of Technology. She is known for her research on post-quantum cryptography. Education and career Lange earned a diploma in mathematics in 1998 from the Technic ...
, Peter Schwabe, and Bo-Yin Yang. The
reference implementation In the software development process, a reference implementation (or, less frequently, sample implementation or model implementation) is a program that implements all requirements from a corresponding specification. The reference implementation o ...
is
public domain software Public-domain software is software that has been placed in the public domain, in other words, software for which there is absolutely no ownership such as copyright, trademark, or patent. Software in the public domain can be modified, distributed, ...
.


Summary

The following is a simplified description of EdDSA, ignoring details of encoding integers and curve points as bit strings; the full details are in the papers and RFC. An EdDSA signature scheme is a choice: * of
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
\mathbb_q over odd prime power q; * of
elliptic curve In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...
E over \mathbb_q whose group E(\mathbb_q) of \mathbb_q-rational points has order \#E(\mathbb_q) = 2^c \ell, where \ell is a large prime and 2^c is called the cofactor; * of base point B \in E(\mathbb_q) with order \ell; and * of
cryptographic hash function A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography: * the probability of a particular n-bit output re ...
H with 2b-bit outputs, where 2^ > q so that elements of \mathbb_q and curve points in E(\mathbb_q) can be represented by strings of b bits. These parameters are common to all users of the EdDSA signature scheme. The security of the EdDSA signature scheme depends critically on the choices of parameters, except for the arbitrary choice of base point—for example,
Pollard's rho algorithm for logarithms Pollard's rho algorithm for logarithms is an algorithm introduced by John Pollard in 1978 to solve the discrete logarithm problem, analogous to Pollard's rho algorithm to solve the integer factorization problem. The goal is to compute \gamma such ...
is expected to take approximately \sqrt curve additions before it can compute a discrete logarithm, so \ell must be large enough for this to be infeasible, and is typically taken to exceed . The choice of \ell is limited by the choice of q, since by Hasse's theorem, \#E(\mathbb_q) = 2^c \ell cannot differ from q + 1 by more than 2\sqrt. The hash function H is normally modelled as a
random oracle In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time th ...
in formal analyses of EdDSA's security. In the HashEdDSA variant, an additional
collision-resistant In cryptography, collision resistance is a property of cryptographic hash functions: a hash function ''H'' is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs ''a'' and ''b'' where ''a'' ≠ '' ...
hash function H' is needed. Within an EdDSA signature scheme, ; Public key : An EdDSA public key is a curve point A \in E(\mathbb_q), encoded in b bits. ; Signature : An EdDSA signature on a message M by public key A is the pair (R, S), encoded in 2b bits, of a curve point R \in E(\mathbb_q) and an integer 0 < S < \ell satisfying the following verification equation. \parallel denotes
concatenation In formal language, formal language theory and computer programming, string concatenation is the operation of joining character string (computer science), character strings wikt:end-to-end, end-to-end. For example, the concatenation of "sno ...
. 2^c S B = 2^c R + 2^c H(R \parallel A \parallel M) A ; Private key : An EdDSA private key is a b-bit string k which should be chosen uniformly at random. The corresponding public key is A = s B, where s = H_(k) is the least significant b bits of H(k) interpreted as an integer in little-endian. The signature on a message M is (R, S) where R = r B for r = H(H_(k) \parallel M), and S \equiv r + H(R \parallel A \parallel M) s \pmod \ell. This satisfies the verification equation: \begin 2^c S B &= 2^c (r + H(R \parallel A \parallel M) s) B \\ &= 2^c r B + 2^c H(R \parallel A \parallel M) s B \\ &= 2^c R + 2^c H(R \parallel A \parallel M) A. \end


Ed25519

Ed25519 is the EdDSA signature scheme using
SHA-512 SHA-2 (Secure Hash Algorithm 2) is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression ...
(SHA-2) and
Curve25519 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 th ...
where * q = 2^ - 19, * E/\mathbb_q is the
twisted Edwards curve In algebraic geometry, the twisted Edwards curves are plane models of elliptic curves, a generalisation of Edwards curves introduced by Daniel J. Bernstein, Bernstein, Birkner, Joye, Tanja Lange, Lange and Peters in 2008. The curve set is named a ...
-x^2 + y^2 = 1 - \fracx^2y^2, * \ell = 2^ + 27742317777372353535851937790883648493 and c = 3 * B is the unique point in E(\mathbb_q) whose y coordinate is 4/5 and whose x coordinate is positive.
"positive" is defined in terms of bit-encoding: ** "positive" coordinates are even coordinates (least significant bit is cleared) ** "negative" coordinates are odd coordinates (least significant bit is set) * H is
SHA-512 SHA-2 (Secure Hash Algorithm 2) is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression ...
, with b = 256. The curve E(\mathbb_q) is
birationally equivalent In mathematics, birational geometry is a field of algebraic geometry in which the goal is to determine when two algebraic varieties are isomorphic outside lower-dimensional subsets. This amounts to studying mappings that are given by rational fu ...
to the
Montgomery curve In mathematics the Montgomery curve is a form of elliptic curve introduced by Peter L. Montgomery in 1987, different from the usual Weierstrass form. It is used for certain computations, and in particular in different cryptography applications. De ...
known as
Curve25519 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 th ...
. The equivalence is x = \frac\sqrt, \quad y = \frac.


Performance

The original team has optimized Ed25519 for the
x86-64 x86-64 (also known as x64, x86_64, AMD64, and Intel 64) is a 64-bit version of the x86 instruction set, first released in 1999. It introduced two new modes of operation, 64-bit mode and compatibility mode, along with a new 4-level paging mod ...
Nehalem/ Westmere processor family. Verification can be performed in batches of 64 signatures for even greater throughput. Ed25519 is intended to provide attack resistance comparable to quality 128-bit symmetric ciphers. Public keys are 256 bits long and signatures are 512 bits long.


Secure coding

As security features, Ed25519 does not use branch operations and array indexing steps that depend on secret data, so as to defeat many
side channel attack In computer security, a side-channel attack is any attack based on extra information that can be gathered because of the fundamental way a computer protocol or algorithm is implemented, rather than flaws in the design of the protocol or algorit ...
s. Like other discrete-log-based signature schemes, EdDSA uses a secret value called a nonce unique to each signature. In the signature schemes DSA and
ECDSA In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic-curve cryptography. Key and signature-size As with elliptic-curve cryptography in general, the b ...
, this nonce is traditionally generated randomly for each signature—and if the random number generator is ever broken and predictable when making a signature, the signature can leak the private key, as happened with the
Sony PlayStation 3 The PlayStation 3 (PS3) is a home video game console developed by Sony Computer Entertainment. The successor to the PlayStation 2, it is part of the PlayStation brand of consoles. It was first released on November 11, 2006, in Japan, November ...
firmware update signing key. In contrast, EdDSA chooses the nonce deterministically as the hash of a part of the private key and the message. Thus, once a private key is generated, EdDSA has no further need for a random number generator in order to make signatures, and there is no danger that a broken random number generator used to make a signature will reveal the private key.


Standardization and implementation inconsistencies

Note that there are two standardization efforts for EdDSA, one from IETF, an informational and one from NIST as part of FIPS 186-5 (2019). The differences between the standards have been analyzed, and test vectors are available.


Software

Notable uses of Ed25519 include
OpenSSH OpenSSH (also known as OpenBSD Secure Shell) is a suite of secure networking utilities based on the Secure Shell (SSH) protocol, which provides a secure channel over an unsecured network in a client–server architecture. Network Working Gr ...
,
GnuPG GNU Privacy Guard (GnuPG or GPG) is a free-software replacement for Symantec's PGP cryptographic software suite. The software is compliant with RFC 4880, the IETF standards-track specification of OpenPGP. Modern versions of PGP are interoperabl ...
and various alternatives, and the signify tool by
OpenBSD OpenBSD is a security-focused, free and open-source, Unix-like operating system based on the Berkeley Software Distribution (BSD). Theo de Raadt created OpenBSD in 1995 by forking NetBSD 1.0. According to the website, the OpenBSD project em ...
. Usage of Ed25519 (and Ed448) in the SSH protocol has been standardized. In 2019 a draft version of the FIPS 186-5 standard included deterministic Ed25519 as an approved signature scheme. *
Apple Watch Apple Watch is a line of smartwatches produced by Apple Inc. It incorporates fitness tracking, health-oriented capabilities, and wireless telecommunication, and integrates with iOS and other Apple products and services. The Apple Watch was rel ...
and iPhone use Ed25519 keys for
IKEv2 In computing, Internet Key Exchange (IKE, sometimes IKEv1 or IKEv2, depending on version) is the protocol used to set up a security association (SA) in the IPsec protocol suite. IKE builds upon the Oakley protocol and ISAKMP.The Internet Key Exch ...
mutual authentication * Botan *
CryptoNote CryptoNote is an application layer protocol designed for use with cryptocurrencies that aims to solve specific problems identified in Bitcoin. Namely: * Traceability of transactions * The proof-of-work function (see Bitcoin network) * Irregul ...
cryptocurrency A cryptocurrency, crypto-currency, or crypto is a digital currency designed to work as a medium of exchange through a computer network that is not reliant on any central authority, such as a government or bank, to uphold or maintain it. It i ...
protocol Protocol may refer to: Sociology and politics * Protocol (politics), a formal agreement between nation states * Protocol (diplomacy), the etiquette of diplomacy and affairs of state * Etiquette, a code of personal behavior Science and technolog ...
* Dropbear SSH * I2Pd implementation of EdDSA *
Java Development Kit The Java Development Kit (JDK) is a distribution of Java Technology by Oracle Corporation. It implements the Java Language Specification (JLS) and the Java Virtual Machine Specification (JVMS) and provides the Standard Edition (SE) of the Java ...
15 *
Libgcrypt Libgcrypt is a cryptography library developed as a separated module of GnuPG. It can also be used independently of GnuPG, but depends on its error-reporting library Libgpg-error. It provides functions for all fundamental cryptographic building blo ...
* Minisign and Minisign Miscellanea for
macOS macOS (; previously OS X and originally Mac OS X) is a Unix operating system developed and marketed by Apple Inc. since 2001. It is the primary operating system for Apple's Mac computers. Within the market of desktop and lapt ...
* NaCl / libsodium *
OpenSSL OpenSSL is a software library for applications that provide secure communications over computer networks against eavesdropping or need to identify the party at the other end. It is widely used by Internet servers, including the majority of HTT ...
1.1.1 *
Python Python may refer to: Snakes * Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia ** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia * Python (mythology), a mythical serpent Computing * Python (pro ...
- A slow but concise alternate implementation, does not include
side-channel attack In computer security, a side-channel attack is any attack based on extra information that can be gathered because of the fundamental way a computer protocol or algorithm is implemented, rather than flaws in the design of the protocol or algorit ...
protection * Supercop reference implementation (
C language C (''pronounced like the letter c'') is a general-purpose computer programming language. It was created in the 1970s by Dennis Ritchie, and remains very widely used and influential. By design, C's features cleanly reflect the capabilities o ...
with inline
assembler Assembler may refer to: Arts and media * Nobukazu Takemura, avant-garde electronic musician, stage name Assembler * Assemblers, a fictional race in the ''Star Wars'' universe * Assemblers, an alternative name of the superhero group Champions of ...
) * Virgil PKI uses Ed25519 keys by default *
wolfSSL wolfSSL is a small, portable, embedded SSL/TLS library targeted for use by embedded systems developers. It is an open source implementation of TLS (SSL 3.0, TLS 1.0, 1.1, 1.2, 1.3, and DTLS 1.0, 1.2, and 1.3) written in the C programming lan ...


Ed448

Ed448 is the EdDSA signature scheme using
SHAKE256 SHA-3 (Secure Hash Algorithm 3) is the latest member of the Secure Hash Algorithm family of standards, released by NIST on August 5, 2015. Although part of the same series of standards, SHA-3 is internally different from the MD5-like stru ...
and
Curve448 In cryptography, Curve448 or Curve448-Goldilocks is an elliptic curve potentially offering 224 bits of security and designed for use with the elliptic-curve Diffie–Hellman (ECDH) key agreement scheme. Developed by Mike Hamburg of Rambus Crypto ...
defined in . It has also been approved in the draft of the FIPS 186-5 standard.


References


External links


Ed25519 home page
{{Cryptography public-key Public-key cryptography Elliptic curve cryptography Digital signature schemes Public-domain software with source code