Talk:EdDSA

Formulas

There is some mess. The formula for Ed25519 curve is

$-x^{2}+y^{2}=1-{\frac {121665}{121666}}x^{2}y^{2}$

With two minuses indeed (see DJB paper, page 6, first equation and page 8, line 1). It is canonical Twisted Edwards curve form. The same formulas can be found in the authors' simplified source code (look at d = -121665 * inv(121666) and xx = (y*y-1) * inv(d*y*y+1) (xx is a square of x))

This curve is birationally equavivalent to Curve25519, which is Montgomery curve (DJB paper, page 7, subsection Choice of curve). Curve25519 itself "is birationally equivalent to an Edwards curve, specifically $x^{2}+y^{2}=1+{\frac {121665}{121666}}x^{2}y^{2}$" (DJB paper, page 8, line 5). Not Twisted Edwards, therefore different formula -- with no minuses. But it is not canonical EdDSA.

Then, the formulas for coord transformation. From Curve25519 to Edwards form (mentioned above): "the equivalence is x =√486664u/v and y =(u − 1)/(u + 1)" (DJP paper, page 8, line 6). From Edwards to Twisted Edwards you just need to replace x^2 with -x^2, or x with (√-1)x (sorry, no link, but this is obvious). Therefore, x =(√-486664)u/v (this edit was correct) — Preceding unsigned comment added by Hannasnow (talk • contribs)

Thanks! Just to clarify, I admit I haven't the faintest about elliptic curve math, but when I see IP users arbitrarily changing bits of math without an explanation, I view that with suspicion. It didn't seem to match the formula given in the source, that's why I reverted. -- intgr [talk] 18:03, 18 November 2014 (UTC)

Cofactor

I have another question which has been bugging me for quite some time. The DJB paper and this article says, that for verification you should check:

$${\begin{aligned}2^{c}SB&=2^{c}(r+H(R,A,M)s)B\\&=2^{c}rB+2^{c}H(R,A,M)sB\\&=2^{c}R+2^{c}H(R,A,M)A.\end{aligned}}$$

Why is the extra factor $2^{c}$ there ? I understand that $2^{255}-19=2^{3}*l$ (where $l$ is the order of the base point and also another prime). But I have no clue why $2^{3}$ should be used in the equation. Why not just check that:

$${\begin{aligned}SB&=(r+H(R,A,M)s)B\\&=rB+H(R,A,M)sB\\&=R+H(R,A,M)A.\end{aligned}}$$

There appears to be an error in above description. There should be two secrets the signer has, their private key associated with there public key and a random number used only once for this signing. I only see the number k which is hashed to produce s.

I think the original paper mentions that this is OK, but I have no clue why the first form (with the $2^{c}$) is mentioned at all.
Looking at that, to me it seems the two equations are checking exactly the same, so why is the $2^{c}$ mentioned at all ? Lundril (talk) 12:55, 10 July 2019 (UTC)

Note, it's not true that $q=2^{255}-19$ (the size of the field) is the same as $8l$ (the number of curve points). Actually that wouldn't make sense since $q$ is a large prime, so it couldn't possibly be divisible by 8.

To understand why the two equations are distinct, it helps to realize that not all points have the order $l$. Some points have order $2l$, some points have order $4l$, and some have order $8l$. Also, a handful of points have order 2,4,8. The identity point ("zero") has order 1. :-)

For a point with order $8l$, multiplying it by 8 yields another point that only has order $l$. Any point multiplied by 8 maps onto some multiple of the generator $B$. So, if we take the second equation and multiply both sides of the equation by 8 then we know all the elements of the equation are part of the order-$l$ subgroup. But, we can't go backwards, because 8 doesn't necessarily have an inverse, so we can't necessarily divide it out.

So, the second equation is more strict. While the second equation implies the first, the first equation does not imply the second. Some more useful discussion can be found at this stackexchange post --Nanite (talk) 02:58, 11 July 2019 (UTC).

by multiplying by the cofactor 2^c we are guaranteeing that the result is either in the subgroup of order $l$ or the identity. This is a cheap way of preventing someone trying to do something funny and get us into the sub group of size 2^c.

prng attacks

quote the article "but does not completely eliminate it, since high quality random numbers are still needed for key generation.". this does not seem to belong here. key generation is not part of the signing procedure, a key can be generated on another computer, can be generated without a computer (coins), or can be derived from another secret. also it is not specific to the DSA algorithm used. i would delete this sentence from here being not related and not meaningful. 178.21.48.33 (talk) 12:17, 28 August 2015 (UTC)

I rewrote the paragraph to clarify it. See if you like it better now? 2016-11-15T19:05Z — Preceding unsigned comment added by 128.30.60.184 (talk) 19:05, 15 November 2016 (UTC)

Sources

Are there still too many primary sources and not enough secondary sources in this article? Everything about the signature scheme, and its instantiation for Ed25519, is supported both by the two original papers describing EdDSA and extending it to more curves, and by the IETF RFC 8032. Is that enough to remove the primary sources warning, or is it also necessary to cite some tertiary Vox-style explainer?

I'm not really clear on why we even need secondary sources for an ‘analysis, evaluation, interpretation, or synthesis of the facts, evidence, concepts, and ideas’ by an author ‘at least one step removed from an event’ for the statement of a mathematical algorithm. None of this is original research—the papers cited are the original research. Other mathematical articles cite primary sources; e.g., the article on Hasse's theorem on elliptic curves cites the original thesis by Artin in which the theorem was first conjectured, and the original paper by Hasse in which the theorem was proven. --128.30.60.184 (talk) 20:03, 31 July 2017 (UTC)

I totally agree. a well respected authoritative primary source is to be ignored while an unknown and possibly inaccurate secondary source is seemingly preferred, "because secondary". Welcome to wikipedia DevilTrombone (talk) 23:14, 2 July 2020 (UTC)

Pubkey size

Isn't the pubkey size 64byte (512bit)? Secret keys are 32byte (256bit) — Preceding unsigned comment added by 141.45.12.204 (talk) 12:49, 6 December 2018 (UTC)

No: The public key is a point on the elliptic curve (Edwards curve for Ed25519). Bernstein stores a point into a byte array by storing the Y-coordinate of the point. A coordinate on this curve has 255 bits (ALMOST 32 byte). Additionally there are two solutions for the X-coordinate: One ODD (least significant bit set) solution and one EVEN (least significant bit cleared) solution. Bernstein calls ODD solutions "negative" and EVEN solutions "positive". To be able to fully decode a binary array into a point on the elliptic curve, you additionally need to know if the X-coordinate is ODD or EVEN; so you need one extra bit. Fortunately the Y-coordinate only uses 255 bits, so you have one extra bit left. This is extra bit is used to store if the X-coordinate is ODD (bit set) or EVEN (bit cleared). The result is: You need exactly 32-bytes to store a point which is on the elliptic curve.
The private key encodes: A number (stored as 256 bit number; even if the number is smaller) and a private never revealed secret string, which has also 32-bytes (this secret string is used to generate "random" numbers out of the message to be signed via hashing). So the private key has 64 byte (32 byte number, 32 byte private secret string). 194.25.174.98 (talk) 12:44, 10 July 2019 (UTC)

Intentionally misleading discussion of bit-strength

Why are you trying so desperately to confuse end users?????

Like.... https://blog.trailofbits.com/2019/07/08/fuck-rsa/ rsa is not equivalent stop fucking around.

jrabbit05 (talk) 03:22, 28 September 2019 (UTC)

FIPS-186-5 final is out

https://csrc.nist.gov/publications/detail/fips/186/5/final 2A04:4540:6A2C:DE01:E6A0:D55E:6254:DF9F (talk) 04:53, 4 March 2023 (UTC)