Edwards-curve Digital Signature Algorithm (EdDSA)

Overall Description

Application Scenario

The Edwards-curve Digital Signature Algorithm (EdDSA) is a variant of Schnorr’s signature system with (possibly twisted) Edwards curves. The hardware EdDSA engine on the chip platform accelerates applications that need EdDSA signature verification or some EdDSA basic core functions. Hardware EdDSA engine executing these functions can not only reduce software overhead but also save CPU and memory resources. The processing of it is faster than software.

The advantages with EdDSA are as follows:

• EdDSA provides high performance on a variety of platforms.SW signature verification run on Ameba_pro 300MHz msglen = 1024 bytes cost: 9.5ms; HW signature verification run simulation cost 3.5 ~ 4ms.

• The use of a unique random number for each signature is not required.

• It is more resilient to side-channel attacks.

• EdDSA uses small public keys (32 or 57 bytes) and signatures (64 or 114 bytes) for Ed25519. Using 32 bytes (256 bits) public keys to verify 64 bytes signatures.

• The formulas are “complete”, i.e., they are valid for all points on the curve, with no exceptions. This obviates the need for EdDSA to perform expensive point validation on untrusted public values.

• EdDSA provides collision resilience, meaning that hash-function collisions do not break this system (only holds for PureEdDSA).

Programmers majorly use this engine to do signature verification on the chip platform for trusted boot and update. For trusted boot and trusted firmware update process, a minimum key size of EdDSA public key requirement is 256 bits (32 bytes) (ARM PSA suggestion).

Features

Realtek EdDSA engine provides basic EdDSA core functions and signature verification:

• Signature verification

  • SB = rB + H(R,A,M)aB = R + H(R,A,M)A

• Point operation

  • Scalar multiplication point

  • Point add

  • Point subtraction

  • Point decoding

• Modular operation

  • Add module

  • Sub module

  • Div module

  • Multi module

  • Hash module 1

  • Hash module 2

Architecture

There are 2 main parts inside the EdDSA architecture. A simplified block diagram of the component is illustrated in the following figure.

Functional Description

Overview

EdDSA has seven parameters, an integer b≥10; a cryptographic hash function H producing 2b-bit output; a prime power q congruent to 1 modulo 4; a (b - 1)-bit encoding of elements of the Fq; a non-square element d of Fq; an L prime between and satisfying an extra constraint described below; and an element B≠(0, 1) of the set.

\[E = \{(x, y) \in F_q \times F_q : -x^2 + y^2 = 1 + dx^2y^2\}\]

The condition that d is not a square implies that d  {0,-1}, so this set E forms a group with neutral element 0 = (0, 1) under the twisted Edwards addition law.

\[(x_1, y_1) + (x_2, y_2) = \left(\frac{x_1y_1 + x_2y_1}{1 + dx_1x_2y_1y_2}, \frac{y_1y_2 - ax_1x_2}{1 - dx_1x_2y_1y_2}\right)\]

The neutral element in the group is (0, 1). The inverse of a point (x1, y1) on E is (−x1, y1). Choice of curve for EdDSA is a twisted Edwards curve birationally equivalent to the curve Curve25519 from. We use the name Ed25519 for EdDSA with this particular choice of the curve.

Specially, Ed25519-SHA-512 is EdDSA with the following parameters: b = 256; H is SHA-512; q is the prime 2^255−19; the 255-bit encoding of F2^255−19 is the usual little-endian encoding of {0, 1, …., 2255-20}; L is the prime 2^252+27742317777372353535851937790883648493; d = −121665/121666 2 ∈ Fq; and B is the unique point (x,4/5) ∈ E for which x is positive.

Parameter	Value
p	2^255 −19
b	256
H(x)	SHA−512
D	−121665/121666= 37095705934669439343138083508754565189542113879843219016388785533085940283555
a	−1
B	(15112221349535400772501151409588531511454012693041857206046113283949847762202, 46316835694926478169428394003475163141307993866256225615783033603165251855960)
L	2^252+27742317777372353535851937790883648493

ED25519 Modular Arithmetic

Modular Inverse

For advice on how to implement arithmetic modulo p = 2^255 – 19 efficiently and securely, see Curve25519. For inversion modulo p, it is recommended to use the identity x^-1 = x^(p-2) (mod p). Inverting zero should never happen, as it would require invalid input, which would have been detected before, or would be a calculation error.

For point decoding or “decompression”, square roots modulo p are needed. They can be computed using the Tonelli-Shanks algorithm or the special case for p = 5 (mod 8). To find a square root of a, first compute the candidate root x = a^((p+3)/8) (mod p). Then there are three cases:

x^2 = a (mod p). Then x is a square root.

x^2 = -a (mod p). Then 2^((p-1)/4) * x is a square root. a is not a square modulo p.

Encoding

All values are coded as octet strings, and integers are coded using little-endian convention, i.e., a 32-octet string h h[0],…h[31] represents the integer h[0] + 2^8 * h[1] + … + 2^248 * h[31].

A curve point (x, y), with coordinates in the range 0 <= x, y < p, is coded as follows. First, encode the y-coordinate as a little-endian string of 32 octets. The most significant bit of the final octet is always zero. To form the encoding of the point, copy the least significant bit of the x-coordinate to the most significant bit of the final octet.

Decoding

Decoding a point, given as a 32-octet string, is a little more complicated.

1. Interpret the string as an integer in the little-endian representation. Bit[255] of this number is the least significant bit of the x-coordinate and denotes this value x_0. They-coordinate is recovered simply by clearing this bit. If the resulting value is >= p, decoding fails.

2. To recover the x-coordinate, the curve equation implies x^2 = (y^2 - 1) / (d y^2 + 1) (mod p). The denominator is always non-zero mod p. Let u = y^2 - 1 and v = d y^2 + 1. To compute the square root of (u/v), the first step is to compute the candidate root x = (u/v)^((p+3)/8). This can be done with the following trick, using a single modular powering for both the inversion of v and the square root.

3. Again, there are three cases:

   • If v x^2 = u (mod p), x is a square root.

   • If v x^2 = -u (mod p), set x ← x * 2^((p-1)/4), which is a square root.

   • Otherwise, no square root exists for modulo p, and decoding fails.

4. Use the x_0 bit to select the right square root. If x = 0, and x_0 = 1, decoding fails. Otherwise, if x_0 != x mod 2, set x ← p − x. Return the decoded point (x, y).

EdDSA decoding flow

EdDSA Signature Verification

Variation of an alleged signature on a message M under a public key works as follows. The verifier parses the key as A for some A ∈ E, and parses the alleged signature as (R, S) for some R ∈ E and S ∈ {0,1……L-1}. To see that signatures pass verification, simply multiply B by the equationS = (r + H(R,A,M)a) mod L, and use the fact that LB = 0, to see that

\[SB = rB + H(R,A,M)aB = R + H(R,A,M)A\]

• Formula: SB = R + H(R, A, M)A

• Formula: 8SB = 8R + 8H(R, A, M)A

  • Points A: public key

  • Points R: signature first 32bytes [0:31]

  • M: message

  • S: signature last 32bytes[32:63]

  • B: the Ed25519 base point (x, 4/5)

The verifier computes H(R, A, M) and then checks the group equation 8SB =8R+8H(R, A, M)A in E. The verifier rejects the alleged signature if the parsing fails or if the group equation does not hold. It is sufficient, but not required, to instead check R + H(R, A, M)A.

EdDSA signature verification mechanism

Registers

The system programmer may access any of the EdDSA engine relative control and status register via CPU. These registers control EdDSA core function operations including engine function enable/reset, set engine mode, set engine input data, get engine output, enable/mask/check interrupt.

RTL8721DxRTL8720ERTL8726ERTL8713ERTL8730E

NA.