Studying different implementations of Ed25519 I see that some of them check the order and canonicity of input public key and signature and some other not. Why this difference? Are these tests relevant in the sense that points specially chosen points to be non-canonical or have an small order reduce the strength of the algorithm against forgery or tampering?


Public key: Generally, no. If a legitimate signer is trying to pull a fast one on you, they already have the power to sign messages that you will accept. So why would they bother feeding you a point that is not generated by the standard base point, when they could just feed you bogus signed messages?

Signature: Generally, no. The verification equation for a signature $(R, s)$ under public key $A$ on a message $m$, where $A$ is a curve point, $R$ is a curve point, $s$ is a scalar, and $m$ is a bit string, is $$[8 s] B = [8] R + [8 H(R, A, m)] A.$$ If $A$ is an 8-torsion point, then the legitimate signer is already pulling a fast one on you—$(\mathcal O, \ell)$ is a valid signature on any message $m$. If two points $R$ and $R'$ differ by an 8-torsion point, i.e. if $[8](R - R') = \mathcal O$, then they will both make valid signatures—meaning if a forger could forge one they could forge the other. But a forger who doesn't know one signature to begin with still can't find one in the first place.

I add the ‘generally’ qualifier because maybe you rely on some properties that signature schemes are not generally expected to provide, such as uniqueness of signatures—as noted, it is easy given a signature $(R, s)$ under $A$ on a message $m$ to find another signature $(R', s') \ne (R, s)$ under $A$ on $m$: pick $s' = s$ and $R' = R + Q$, where $Q$ is any 8-torsion point other than the identity $\mathcal O$. The assumption of signature uniqueness caused Monero some trouble last year, but most applications do not rely on this.

| improve this answer | |
  • $\begingroup$ Thanks. Bibliography over the wire is nor explicit enough in their conclusions. I just wanted a clear and justified answer to be sure that the code I'm using (not writing) is good for my purposes. $\endgroup$ – user3368561 Feb 15 '18 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.