3
$\begingroup$

Suppose we need a special Elliptic curve on prime field $Fp$, for some reason, that the order of the generator must be $6*q$, where q could be a big prime, does this weak the ECC encryption? What's the possible attack vector towards this kind of curves?

I'm just a beginner in ECC, so hope this is not a silly question.

$\endgroup$
  • $\begingroup$ This is a valid question. So, why has somebody voted it down? $\endgroup$ – user27950 Nov 29 '16 at 11:04
  • 3
    $\begingroup$ @Cryptostasis The chances of that person returning are minimal and "we" don't know. The question is - if you think is a valid question - why haven't you voted it up? $\endgroup$ – Maarten - reinstate Monica Nov 29 '16 at 12:12
  • 1
    $\begingroup$ Why do you want such an unusual generator and which properties do you expect out of it? And what ECC do you plan on using? $\endgroup$ – CodesInChaos Nov 29 '16 at 13:02
  • $\begingroup$ @CodeInChaos I was trying to prove $a\equiv b\pmod n$, without reveal a and b, but this way looks problematic. $\endgroup$ – andj Nov 30 '16 at 0:18
  • $\begingroup$ Sounds like the Socialist millionaire problem $\endgroup$ – CodesInChaos Nov 30 '16 at 12:16
7
$\begingroup$

The question is a bit broad. Generating secure elliptic curves is highly non-trivial, see for example this question, which contains references to this and this paper.

Considering a black box group, the fact that it has order $6\cdot q$ does not break the DLP. What happens is that the DLP can easily be reduced to a group of order $q$ by eliminating the cofactor 6. So being a multiple of 6 does not break DLP, nor does it help.

However, an elliptic-curve group is of course not black box. In some particular cases we can use properties that reduce the ECDLP to simpler DLP's, for example in the case of supersingular or anomalous curves. These are criteria which have to be taken into consideration when choosing the curve, to make sure the corresponding ECDLP is hard.

However, cryptographic protocols rely on assumptions which are similar, but not exactly the same as the ECDLP. For example, the Diffie-Hellman assumption does not reduce to ECDLP. Therefore, we also have to choose curves in such a way that attacks on our particular protocol are avoided. There are many attacks which target an elliptic-curve-based protocols by using properties of the underlying curve. Important examples are small-subgroup attacks (very relevant here!) and twist attacks. There are many more examples.

In conclusion, having order $h\cdot q$ for a large prime $q$ and some integer $h$ is necessary to build secure elliptic-curve-based protocols. It is however not sufficient. Obtaining a secure elliptic curve of order $6\cdot q$ is possible, but you'll want to take many more properties into account before deciding to use it. This is very non-trivial, so generate your own curves with care.

$\endgroup$
2
$\begingroup$

It might depend on the specific protocol you are implementing.

If a generator $G$ has order $6*q$ then I think it's fair to assume you can generate private keys in $(0,6q)$ meaning you could end up with a valid public key $Q = q*G$.

Now, this could be supplied to another user in an ECDH key agreement.

The other user will compute $k*Q$ but this has only $6$ possible outcomes (since $Q$ has order $6$), thus it will be possible to recover the value of $k \mod 6$.

In this, common scenario, the ECDLP is just reduced to the $q$-order subgroup, which we assume is secure, so this is not a break.

But there might be cases/protocol where contributory behavior is required, meaning that a user shouldn't be able to force the result in a small range, as it's possible in this case. In this scenario it would be a break. That said, contributory behavior is usually not a requirement.

$\endgroup$

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.