Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

The Diffie-Hellman on curve25519 is usually calculated using the base point $(9,…)$ which induces a cyclic subgroup of $G:=\{\infty\}\cup(E(F_{p^2})\cap(F_p\times F_p))$ with index 8, i.e. there is a prime $p_1$ such that $|G|=8p_1$ and the order of $(9,…)$ is $p_1$. An attacker does not have to use a multiple of $(9,…)$ though and can even choose an element in the twist group $T:=\{\infty\}\cup(E(F_{p^2})\cap(F_p\times \sqrt 2 F_p))$ which has order $|T|=4p_2$ for a prime $p_2$.

Contributory behaviour (afaik) describes the property that none of the participants of the Diffie-Hellman exchange can force the outcome to be one of a small set of values. Such a property is for example interesting to defend against something like the triple handshake attack. The website on curve25519 lists 12 values to reject to assure contributory behaviour.

I understand where eleven of these come from, namely the elements of the subgroups of order 8 and 4 of $G$ and $T$ respectively. As they both share the same identity element ($\infty$) there are $8+4-1=11$ of those elements.

(If an element is not in those subgroups of order 8 and 4, then its order is $\geq \min(p_1,p_2)$ and thus the set of possible values that result out of the multiplication with the private scalar of the other party is large.)

Which of the 12 elements listed on the website is not one of the above eleven and why is it there?

share|improve this question
    
Discussion of the effect of weak points on Ed25519 signatures It's possible to forge messages that crypto_sign_open verifies if the public key is zero –  CodesInChaos Jun 17 at 14:38
    
@CodesInChaos: Very interesting application… Regarding the discussion there: I'm torn between arguing that this property is not at all a weakness of the implementation and that relying on such notion would be the fault of the protocol (similarly as I would see non-malleability as an unreasonable requirement of a signature scheme). And on the other hand I see the length extension property of the SHA2 family as a weakness and struggle to justify why this property is any different to it and why signature schemes shouldn't also be build as strongly as possible. –  Perseids Jun 17 at 20:31

1 Answer 1

up vote 7 down vote accepted

There are actually only 5 unique $x$-coordinates one needs to be concerned about:

  • $(0, \ldots)$
  • $(1, \ldots)$
  • $(-1, \ldots)$
  • $(x_1, \ldots)$
  • $(x_2, \ldots)$,

where

$$\begin{eqnarray} x_1 =& 393823572354896145817230607815530211125 \\ & 29911719440698176882885853963445705823 \end{eqnarray} $$ and $$\begin{eqnarray} x_2 =& 32560625091655743179598362635611063129 \\ & 4008115727848805560023387167927233504 \end{eqnarray}. $$

These correspond to the $x$-coordinates of points of small order on the curve and its twist, as you have pointed out. The remaining values you see are the multiples of those coordinates below $2^{256}$:

  • $0 \equiv 2^{255}-19 \equiv 2(2^{255}-19) \pmod{2^{255}-19}$
  • $1 \equiv 2^{255-19} + 1 \equiv 2(2^{255}-19) + 1 \pmod{2^{255}-19}$
  • $2^{255} - 19 - 1 \equiv 2(2^{255}-19) - 1 \pmod{2^{255}-19}$
  • $x_1 \equiv 2^{255} - 19 + x_1 \pmod{2^{255}-19}$
  • $x_2 \equiv 2^{255} - 19 + x_2 \pmod{2^{255}-19}$

These extra values are checked because curve25519 was designed to accept any $256$-bit string as public-key, and each value has one or more 256-bit representations modulo $2^{255}-19$.

share|improve this answer
1  
Thx. Quite interestingly (0,…) stands out from the others, because the specification defines $X(Q)$ - which normally is the x-coordinate of $Q$ - as zero for $Q=\infty$. Still (0,0) is a valid point on the curve, so the image "0" of $X$ that is listed on the website refers to both $\infty$ and (0,0). Furthermore there is no $y\neq 0$ with (0,$y$) being an element on curve. So while the other dots refer to multiple y-coordinates for the same x-coordinate, the dots in (0,…) refer to the special case of the $X$ map. –  Perseids Jun 15 at 22:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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