This article will introduce the implementation principle and scalability of the elliptic curve-based digital signature algorithm Ed25519.

Written by: Ah Wei

Ed25519 is a digital signature algorithm based on elliptic curve, which is efficient, secure and widely used. It is used in TLS 1.3, SSH, Tor, ZCash, WhatsApp and Signal. This article mainly explains the following points:

1. Introduce a little knowledge of group theory, the purpose is to let everyone have an intuition about the principle of Ed25519 and its scalability problem. For a deeper understanding, you need to refer to other materials;
2. Explain the implementation of ed25519 for version 1.0.1 of the rust library ed25519-dalek;
3. Explain the extensibility of the library.

Math Essentials Review

Definition and properties of groups

Group theory is the content of abstract algebra research, but some ideas of abstract algebra are very familiar to programmers. Inheritance in object-oriented is a good example. We all know that after subclasses inherit the parent class, they can use the methods defined in the parent class. Abstract algebra can be understood as defining some properties for an abstract data structure, and the theorems derived from these properties hold true for all subclasses.

Using the metaphor just now, let's see how the data structure of group is defined.

A group consists of an operation (denoted by any binary operation) and some elements, satisfying the following properties:

Many interesting theorems can be derived from this:

To give a few examples:

• The integers ..., −2, −1, 0, 1, 2, ... and addition are a group because they satisfy the above four properties
• Integers and multiplication are not groups because they do not satisfy reversibility, 4 x 1/4 = 1, but 1/4 is not an integer

Group Theory Terminology Snipped Over

Lagrange Theorem

Now introduce a very interesting theorem, the derivation of this theorem is in the video cited at the end of the article.

** "The order of the group is divisible by the order of the subgroup."**

Why is this theorem interesting, not only because its proof process connects a lot of knowledge just introduced, but also because of the following conclusions:

**“If the order of a group is a prime number, then according to Lagrange’s theorem, the order of the subgroup must be or. All elements in the group are generators except

Implementation of Ed25519

Now let's talk about Ed25519, which is one of the EdDSA algorithms. EdDSA has 11 parameters (the specific selection of these parameters has a great impact on the security and performance of the algorithm. For the specific selection of Ed25519, please refer to the link (

In addition, it is worth mentioning that this algorithm uses an elliptic curve called Curve25519 (. For the elliptic curve, we only need to know that there are many, many points on it, and the addition of these points can get new points. The new point is still On the curve. These points and this addition can form a group. Note that the elliptic curve addition (is specially defined.

We agree on the following notation:

This is an interactive algorithm, but it doesn't matter, there is a trick called the Fiat – Shamir heuristic (It can convert any interactive algorithm into a non-interactive algorithm. Eventually we will use a non-interactive algorithm.

The digital signature algorithm will give us the following API:

KeyGen implementation

Output a private key and a public key:

1. Randomly generate a seed (this seed has 32 bytes. We use a cryptographically secure random number generator that comes with the system.

pub fn generate(csprng: &mut T) -> SecretKeywhere

T: CryptoRng + RngCore,

{

let mut sk: SecretKey = SecretKey([0u8; 32]);

csprng.fill_bytes(&mut sk.0);

sk

}

2. Expand the seed just now to 64 bytes (that is, xseed in the figure. The low 32 bytes of xseed are our private key (aka a). The high 32 bytes are called nonce, which will be used later In it, its function is similar to domain sperator.

pub struct ExpandedSecretKey { // xseed pub(crate) key: Scalar, // a

pub(crate) nonce: [u8; 32], // nonce

}

fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {

let mut h: Sha512 = Sha512::default();

let mut hash: [u8; 64] = [0u8; 64];

let mut lower: [u8; 32] = [0u8; 32];

let mut upper: [u8; 32] = [0u8; 32];

h.update(secret_key.as_bytes());

hash.copy_from_slice(h.finalize().as_slice());

lower.copy_from_slice(&hash[00..32]);

upper.copy_from_slice(&hash[32..64]);

// This step is clamp

lower [0] &= 248;

lower [31] &= 63;

lower [31] |= 64;

ExpandedSecretKey{ key: Scalar::from_bits(lower), nonce: upper, }

}

3. Use the private key to generate the public key (the public key is a point on the elliptic curve. Specifically, we use the base point of the elliptic curve to perform elliptic curve multiplication to obtain the public key. The scalar in the multiplication is obtained by pairing the private key Do a hash to get it.

pub struct ExpandedSecretKey { // xseed pub(crate) key: Scalar, // a

pub(crate) nonce: [u8; 32], // nonce

}

fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {

let mut h: Sha512 = Sha512::default();

let mut hash: [u8; 64] = [0u8; 64];

let mut lower: [u8; 32] = [0u8; 32];

let mut upper: [u8; 32] = [0u8; 32];

h.update(secret_key.as_bytes());

hash.copy_from_slice(h.finalize().as_slice());

lower.copy_from_slice(&hash[00..32]);

upper.copy_from_slice(&hash[32..64]);

// This step is clamp

lower [0] &= 248;

lower [31] &= 63;

lower [31] |= 64;

ExpandedSecretKey{ key: Scalar::from_bits(lower), nonce: upper, }

}

Implementation of Sign

Here you can mention the Fiat Shamir technique mentioned earlier. In fact, you only need to replace all the random numbers provided by Verifier with the result of a hash function. See code comments for details.

pub fn sign(&self, message: & [u8] , public_key: &PublicKey) -> ed25519::Signature {

let mut h: Sha512 = Sha512::new();

let R: CompressedEdwardsY;

let r: Scalar;

let s: Scalar;

let k: Scalar;

h.update(&self.nonce);

h.update(&message);

r = Scalar::from_hash(h); // r is a random number in our interactive algorithm, but here we use a hash.

R = (&r * &constants::ED25519_BASEPOINT_TABLE).compress(); // R = [r] B

h = Sha512::new();

h.update(R.as_bytes());

h.update(public_key.as_bytes());

h.update(&message);

k = Scalar::from_hash(h); // h = Sha512(R || A || M)

s = &(&k * &self.key) + &r; // s = r + h * a, h is originally a random number

InternalSignature { R, s }.into()

}

Implementation of Verify

impl Verifiered25519::Signature for PublicKey {

#[allow(non_snake_case)]

fn verify(

&self,

message: & [u8] ,

signature: &ed25519::Signature

) -> Result<(), SignatureError>

{

let signature = InternalSignature::try_from(signature)?;

let mut h: Sha512 = Sha512::new();

let R: EdwardsPoint;

let k: Scalar;

let minus_A: EdwardsPoint = -self.1;

h.update(signature.R.as_bytes());

h.update(self.as_bytes());

h.update(&message);

k = Scalar::from_hash(h); // The calculation of h is the same as in sign, h=Sha512(R||A||M)

R = EdwardsPoint::time_double_scalar_mul_basepoint(&k, &(minus_A), &signature.s); // R’ = [s] B - [h] A

if R.compress() == signature.R { // If R'==R, then the verification result is true.

Ok(())

} else {

Err(InternalError::VerifyError.into())

}

}

}

code address (

Scalability issues

There are many places to pay attention to in the implementation and use of cryptographic algorithms. When we say that a digital signature algorithm is secure, it generally means that even if the attacker can obtain the signature of any message (Chosen Message Attack), the attacker still cannot forge the signature. Ed25519 satisfies this property, but it does not mean that Ed25519 is absolutely safe. It is also mentioned in the original paper that the scalability problem is acceptable, and the original algorithm has this problem.

In this way, both the newly constructed signature and the old signature can be verified successfully. The malleability problem tells us that the signature is not deterministic relative to the message and the public key. When the signature algorithm has a malleability problem and the code assumes that the signature is deterministic, there are likely to be loopholes.

According to the standard (in fact, there is no scalability problem. Because in the verification process, we will check whether it is less than, if the check result is not true, the verification fails. But the standard (appears later than the paper (so in the actual environment, There are still implementations of Ed25519 that have scalability issues and require implementations that we examine.

Summarize

Thanks

*Thanks to Safeheron, a leading one-stop digital asset self-custody service provider, for providing professional technical advice. *

References

[1] .

[2] .

[3] .

[4] .

[5] . Researchers Use Group Theory to Speed Up Algorithms — Introduction to Groups