I am currently experimenting with ed25519 and I noticed that on secret key creation, bit 254 is always set and the lower 3 bits are always cleared. I found that bit 254 is always set to protect against timing attacks in this question: When using Curve25519, why does the private key always have a fixed bit at 2^254?

But why are the lower 3 bits cleared. Obviously it has to do with the formula in the curve25519 paper: The set of secret keys is defined to be $\{\underline{n} : n \in 2^{254} + 8\{0, 1, 2, 3,\ldots, 2^{251}-1\}\}$

It's because of the 8 in there, but why is that 8 there? I suspect it has something to do with theorem 2.1 in the curve25519 paper, but I am not sure, because I do not understand fully what is being proven there.

I am experimenting with ed25519 primitives in some cryptographic routines which need me to add scalars to the secret key (add secret keys). Even if I add two well formed ed25519 secret keys, the result will not always have bit 254 set and the lower 3 bits cleared. Is this a security problem? I understand the risk for bit 254 but not the lower 3.

  • 5
    $\begingroup$ The group order is a multiple of 8. Setting the lowest bits zero, sets the scalar to a multiple of 8, ensuring that the points are in the prime-order subgroup without the small subgroup interfering. $\endgroup$ Commented Dec 18, 2013 at 13:23
  • 1
    $\begingroup$ Just to add to the above comment: This means you don't have to verify that strings represent group elements, which is typically costly. Protocols that omit this step without other countermeasures have been broken. $\endgroup$
    – K.G.
    Commented Dec 18, 2013 at 15:01
  • $\begingroup$ Please take into account that I only have a basic understanding of ECC when I ask: According to the paper, the group order of ed25519 is a prime ( $ 2^{252} + 27742317777372353535851937790883648493$ ) which by definition is not a multiple of anything. What am I missing? Also, I am looking for the implications for when I add / multiply 2 valid secret keys, I get a non multiple of 8. Does this mean this new secret key is unfit for signing messages with edDSA? $\endgroup$
    – MepAhoo
    Commented Dec 19, 2013 at 13:49
  • 1
    $\begingroup$ Answering my own questions: It seems there are 2 groups at play here. The group of the curve and the group of the generating base point. In this case the curve group is 8 * the base point group. The problem with this is descibed in the small-subgroup attack section of this link: safecurves.cr.yp.to/twist.html . Curve25519 solved this problem by making every secret key a multiple of 8. Although it seems to me this sacrifices 3 bits to prevent a 3 bit security issue. An alternative is to check the public keys before processing them, as described here: cr.yp.to/ecdh.html#validate $\endgroup$
    – MepAhoo
    Commented Dec 23, 2013 at 13:12

1 Answer 1


Clearing the lower 3 bits of the secret key ensures that is it a multiple of 8, which in turn ensures that no information, small as it may be, about the secret key is leaked in the case of an active small-subgroup attack.

The typical simple Diffie-Hellman key exchange works like this:

$$ \text{Alice} \xrightarrow{\hspace{3cm} a G \hspace{3cm}} \text{Bob} \\ \text{Alice} \xleftarrow{\hspace{3cm} b G \hspace{3cm}} \text{Bob} $$

$a$ and $b$ are Alice and Bob's secret keys, and $G$ is the base point, which is $(9,\ldots)$ in curve25519. Alice computes $a\cdot bG$, Bob computes $b \cdot aG$, and the shared secret is derived by passing $abG$ through some key derivation function.

Now, as you have noticed, the order of $G$ is $p_1 = 2^{252} + 27742317777372353535851937790883648493$, whereas the number of points in the curve itself is $8 p_1$. This means that there are a few remaining points that have small order. An active attacker can, e.g., replace Bob's message $bG$ with a point of order $8$ and be able to find $a \bmod 8$ by inspecting following messages. When every valid secret key is $0 \bmod 8$, the attacker gets nothing.

One may argue that this wastes 3 perfectly good key bits to prevent an already ineffective attack. Notice, however, that the actual security of the scheme is tied to the order of the base point, $p_1 \approx 2^{252}$. Clearing those 3 bits (out of 255) does not reduce the keyspace since it still leaves 252 useful bits, giving roughly the same keyspace as the number of points generated by $G$.

  • 1
    $\begingroup$ I kind of figured this out above, but your answer is the most complete and easy to understand for me. Also you answered the "are 3 bits wasted?" question I pose later. Thanks $\endgroup$
    – MepAhoo
    Commented Jan 1, 2014 at 15:37
  • $\begingroup$ Ahh, thanks for the explanation. I just asked a slightly expanded version of this question here : crypto.stackexchange.com/questions/29791/… $\endgroup$ Commented Oct 12, 2015 at 11:40
  • $\begingroup$ @Samuel Neves, when you say a few remaining points that have small order, how do we know the other points not inside p1, are part of a variety of small order groups? Given that points remaining are p1*8, aren't there a lot more points and as such we could have another large group? $\endgroup$
    – Woodstock
    Commented Nov 19, 2019 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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