OK, that makes sense. Thanks! (And thanks to Trevor for giving me the answer
off-list.)
So let me hard-fork this thread and ask a followup meta-question: The fact
that 8 was the cofactor of the curve is apparently something most (if not all)
people on this list already knew. But how? Neither the Ed25519 paper nor the
Curve25519 paper mentions it (AFAICT).
In trying to back-solve the answer to this question myself I was led to RFC7748
Appendix A, which was very enlightening, but contained this (to me) cryptic
comment:
"For primes congruent to 1 mod 4, the minimal cofactors of the curve and its
twist are either {4, 8} or {8, 4}.”
Where the heck did *that* come from? Digging through the references, I
happened to stumble upon this:
http://www.hpl.hp.com/techreports/97/HPL-97-128.pdf
which seems like it’s the answer to that particular question. But even this
(apparently) elementary fact seems to be almost deliberately obscured in the
literature. Even https://safecurves.cr.yp.to doesn’t mention it, which is
another indication that all this is just taken to be common knowledge.
Another data point: I asked a similar question to this once before and was
pointed to the Handbook of Elliptic and Hyperelliptic Curve Cryptography by
Cohen & Fry et al. The word “cofactor” appears in that 800-page tome on 22
pages. The first appearance of the word is this passage on page 218:
"If the cofactor N/p is sufficiently small, the computations can be done modulo
N without any addi- tional cost since multiplications are usually performed at
a word level.”
i.e. the word is introduced in an offhand way and defined only in passing, as
if the reader is expected to already know what a cofactor is and why it’s
important.
BTW: Smart’s result came as a complete shock to me. Every intro to ECC on the
web says something isomorphic to “ECC is secure because DLP over elliptic
curves is hard.” But if I’m understanding this correctly, that statement is
actually not true at all. The correct statement is (AFAICT) something more
like, “DLP over elliptic curves with cofactor >1 is hard, otherwise it’s easy.”
Bottom line: there seems to be a huge disconnect between the importance of
cofactors on the one hand and the information available about them on the
other. On the one hand, cofactors seem to be so important that all this stuff
that I just learned about seems to be common knowledge, and on the other hand,
even now that I know it I *still* can’t figure out how I could have learned it
other than asking this apparently stupid question.
So my meta-question is: *was* this a stupid question? Did everyone really
already know this except me? And if so, how?
On Nov 1, 2016, at 10:30 AM, Mike Hamburg <[email protected]> wrote:
> The 8s are the cofactor of Ed25519. The idea is that you may check the
> equation's projection on the order-q subgroup, instead of in the whole group.
> Depending on implementation, this may make things easier. For example,
> libdecaf projects everything into the order-q subgroup.
>
> This is not supposed to make a difference because everything is supposed to
> live in the order-q subgroup. But if someone generates their key or nonce
> wrong, then it makes a difference.
>
> The problem with giving implementers the option is that it could allow
> fingerprinting or forking attacks. I'd rather see a hard requirement one way
> or the other.
>
> Sent from my phone. Please excuse brevity and typos.
>
>> On Nov 1, 2016, at 09:04, Ron Garret <[email protected]> wrote:
>>
>>
>>> On Nov 1, 2016, at 7:14 AM, Peter Schwabe <[email protected]> wrote:
>>>
>>> Trevor Perrin <[email protected]> wrote:
>>>
>>> Dear Trevor,
>>>
>>>> One last tweak to consider is clearing the cofactor in verification.
>>>> Currently XEdDSA does "cofactorless verification", i.e. it takes a
>>>> signature (R, s) and checks R == sB - hA. We could change it to cR ==
>>>> c(sB - hA). VXEdDSA would be unchanged.
>>>>
>>>> This has no effect on valid signatures, but adding the cofactor
>>>> multiplication means signers could create signatures with a few
>>>> different values of R for the same s (which has no security relevance,
>>>> I think, and does not cause "malleability" because the signer's choice
>>>> of R is included in the hash).
>>>>
>>>> Advantages to current "cofactorless" approach:
>>>> - matches existing code like (ref10, libsodium)
>>>> - less code, doesn't need a "point comparison" function (can encode,
>>>> then compare)
>>>> - less computation (by tiny amount, 1% or something)
>>>>
>>>> Advantages to changing to "cofactor" approach:
>>>> - Allows batch verification of signatures (I'm told), that can give ~2x
>>>> speedup
>>>> - Preferred approach in Ed25519 paper, "EdDSA for more curves" paper,
>>>> and CFRG draft
>>>
>>> The Ed25519 paper says
>>>
>>> "The verifier is /permitted/ to check this stronger equation and
>>> to reject alleged signatures where the stronger equation does not
>>> hold. However, this is not /required/; checking that
>>> 8SB=8R+8H(\encode{R},\encode{A},M)A is enough for security."
>>>
>>>
>>> You could decide to do the same; allowing both for verification in the
>>> specification and leaving the choice to the implementation. If I
>>> understand correctly, this gives you the advantages of both approaches,
>>> right?
>>
>> Possibly naive question: What is “this stronger equation” that the paper
>> refers to? Because the immediately preceding equation is:
>>
>> SB = rB + H(\encode{R},\encode{A},M)aB = R + H(\encode{R},\encode{A},M)A
>>
>> which is actually two equations. The first:
>>
>> SB = rB + H(\encode{R},\encode{A},M)aB
>>
>> relies on the secret key a, so that does not seem particularly useful. But
>> the second equation:
>>
>> SB = R + H(\encode{R},\encode{A},M)A
>>
>> Is (AFAICT) identical to the earlier “weaker” equation:
>>
>> 8SB = 8R+8H(\encode{R},\encode{A},M)A
>>
>> except for factoring out the 8’s. (Where did those 8’s come from anyway?
>> They seem completely unmotivated.)
>>
>> What am I missing?
>>
>> rg
>>
>> _______________________________________________
>> Curves mailing list
>> [email protected]
>> https://moderncrypto.org/mailman/listinfo/curves
_______________________________________________
Curves mailing list
[email protected]
https://moderncrypto.org/mailman/listinfo/curves
