EsDSA and Ed25519

EdDSA(Edwards-curve Digital Signature Algorithm) is based on performance-optimized elliptic curves,such as the 255-bit curve Curve25519 and 448-bit curve Curve448-Goldilocks. The EdDSA algorithm is based on the Schnorr signature algorithm and relies on the difficulty of ECDLP problem.

Ed25519 equation

$ -x^2+y^2=1-(121665/121666)x^2y^2 $

EdDSA Key Generation

private key: $d_A$
publick key: $Q_a=d_A * G$

EdDSA Sign

Deterministically generate a secret integer: $ r=hash(hash(d_A)+msg) \bmod q $
Calculate: $ R=r * G $
Calculate: $ h=hash(R+Q_a+msg) \bmod q $
Calculate: $ s=(r+h*d_A) \bmod q $
signature: $(R,s)$ , R is a compressed point R

EdDSA verify signature

Calculate: $ h=hash(R+Q_a+msg) \bmod q $
Calculate: $ P_1=s*G $
Calculate: $ P_2=R+h*Q_a $
Return $ P_1==P_2 $

Proof

$ P_1=s*G $
$ =(r+h*d_A) *G $
$ =r*G + h*d_A*G$
$ =R+h*Q_a $
$ = P_2 $

ECDSA vs EdDSA

Both signature algorithms have similar security strength for curves with similar key length.For the most popular curves the EdDSA algorithm is slightly faster than ECDSA.But EdDSA do not provide a way to recover the singer's public key from the signature and message.

The importance of random r

Assume you generate r with a random funtion instead of hash function, if you hava two signatures with the same r value, and it means you can calculate private key using signatures with msg hash. $ s_1=r+h_1*d_A $
$ s_2=r+h_2*d_A $
$ s_1-s_2=(h_1-h_2)d_A $
$ d_A=\frac{s_1-s_2}{h_1-h_2} $

ed25519 clamping

Ed25519 Scalar private key is derivate from seed. First use Sha512 to hash the seed, then the first 32 bytes is used as un-clamped private key, the last 32 bytes is used as prefix of Signingkey;

Clamping is the action of flip some bits to the input bytes. Ed25519 private key clamping looks like so:

#![allow(unused)]
fn main() {
            scalar_bytes[0] &= 248;
            scalar_bytes[31] &= 127;
            scalar_bytes[31] |= 64;
}

ed25519_consensus: sign

#![allow(unused)]
fn main() {
 pub fn sign(&self, msg: &[u8]) -> Signature {
        let r = Scalar::from_hash(Sha512::default().chain(&self.prefix[..]).chain(msg));

        let R_bytes = (&r * &constants::ED25519_BASEPOINT_TABLE)
            .compress()
            .to_bytes();

        let k = Scalar::from_hash(
            Sha512::default()
                .chain(&R_bytes[..])
                .chain(&self.vk.A_bytes.0[..])
                .chain(msg),
        );

        let s_bytes = (r + k * self.s).to_bytes();

        Signature { R_bytes, s_bytes }
    }
}

golang ed25519: sign

func signGeneric(signature, privateKey, message []byte) {
 if l := len(privateKey); l != PrivateKeySize {
  panic("ed25519: bad private key length: " + strconv.Itoa(l))
 }

 h := sha512.New()
 h.Write(privateKey[:32])

 var digest1, messageDigest, hramDigest [64]byte
 var expandedSecretKey [32]byte
 h.Sum(digest1[:0])
 copy(expandedSecretKey[:], digest1[:])
 expandedSecretKey[0] &= 248
 expandedSecretKey[31] &= 63
 expandedSecretKey[31] |= 64

 h.Reset()
 h.Write(digest1[32:])
 h.Write(message)
 h.Sum(messageDigest[:0])

 var messageDigestReduced [32]byte
 edwards25519.ScReduce(&messageDigestReduced, &messageDigest)
 var R edwards25519.ExtendedGroupElement
 edwards25519.GeScalarMultBase(&R, &messageDigestReduced)

 var encodedR [32]byte
 R.ToBytes(&encodedR)

 h.Reset()
 h.Write(encodedR[:])
 h.Write(privateKey[32:])
 h.Write(message)
 h.Sum(hramDigest[:0])
 var hramDigestReduced [32]byte
 edwards25519.ScReduce(&hramDigestReduced, &hramDigest)

 var s [32]byte
 edwards25519.ScMulAdd(&s, &hramDigestReduced, &expandedSecretKey, &messageDigestReduced)

 copy(signature[:], encodedR[:])
 copy(signature[32:], s[:])
}

As we see, both golang ed25519 & ed25519_consensus do clamping when generate parivate scalar, golang ed25519 also do clamping when calc the random r.

input[0] &= 248  // 248 == 1111,1000
input[31] &= 127 // 127 == 0111,1111
input[31] |= 64  // 64  == 0100,0000

In rfc8032 [Key Generation]:
Interpret the buffer as the little-endian integer, forming a secret scalar s.

After the clamping, the private scalar's binary looks like below style, for visual convenience, we use big-endian style: $$ (01**,), (1-30 bytes) , (,*000) $$

The order of parent group is n, the order of prime subgroup is $ord(g)$ . As a consequence of Lagrang's Theorem, we have $ n = ord(g) \cdot d $， where d is called cofactor.

Small-Subgroup-Attack in DH:
$A=g^a, B=g^b, secret=g^{ab}$, if someone chose a point in small subgroup, then there is a high probablity of leakage of secret.

Because the cofactor is 8 , so every subgroup of edwards25519 must have one of the following orders {1,2,4,8, ord(g)}. If someone send a point H to us in DH-key-exchange, the secret $S=x*H=8x'H=e $, so when someone send a point in small group to us, the secret will also be identity element.

Setting the highest bit:
X25519 only deals with x-coordinates and there is a simple & efficient way to implement scalar multiplication of x-coordinates known as the Montgomery ladder. The problem with this is that some implementations implement it in variable-time based on the positon of the highest bit. So set the highest bit at a fixed position, the operation will run in constant time.

Why golang ed25519 do bit-setting for hashed prefix:
The implementation of golang-lang also do clamping to the random r.

Stromata Of Gimmi7