1
$\begingroup$

I am trying to get my head around the methods involved in ECDH and am confused by the public keys that are used. Alice picks a random number A from 1 to P - 1 and then computes A⋅g (g being the publicly agreed generator, with a high order) using point addition and multiplication. She then publishes this value. In order to arrive at a shared secret, Bob must then also pick a random number B and compute B⋅(A⋅g).

Now, the shared secret can only be one of the points which can be generated from A⋅g through point addition and multiplication and, as such, if A⋅g has a low order surely there are very few potential results of Bob's calculation of the shared secret. Because an attacker would have access to A⋅g and the parameters of the curve (as they are publicly agreed) would they not be able to discern whether Alice's public key had a low order? If this was the case would a brute force attack not be sufficient to discover the shared secret?

There must be a mistake in my reasoning somewhere and I just can't see it, else are the random numbers re-computed if A⋅g has a low order to avoid this very attack?

Thanks for the help.

$\endgroup$
  • $\begingroup$ Hint: Lagrange's theorem. $\endgroup$ – yyyyyyy Jan 25 '18 at 21:37
  • $\begingroup$ @yyyyyyy I think I understand the theorem but don't see how it solves this issue. Thank you for the hint but I don't think I'm good enough to get it without further clarification. $\endgroup$ – Joz Jan 25 '18 at 21:42
1
$\begingroup$

$g$ is a generator and is of order $P$. Lagrange's theorem says that the order of an element in a group $\mathbb{G}$ divides the order of the group.

In your case, one has $\mathbb{G} = \langle g \rangle$. Therefore, the order of an element $a = Ag \in \mathbb{G}$ is a divisor of $P$. If $P$ is a prime, its two divisors are $P$ and $1$. Hence, either $a$ is of order $P$, either $a$ is of order $1$ (in the latter case, $a$ is the neutral element ---the point at infinity on an elliptic curve given by a Weierstrass equation).

$\endgroup$
  • $\begingroup$ And in case it's not clear, standard curve parameters (like SECG/X9.62/NIST, Brainpool, etc) are chosen so that the subgroup order is a large prime. This computation is difficult, but is only done once per curve. BTW the same is true for standardized integer-DH parameters like rfc2412, but people often use ad-hoc parameters for integer-DH (with the risk of small-subgroup attack) whereas nobody tries to do ad-hoc parameters for EC. $\endgroup$ – dave_thompson_085 Jan 26 '18 at 5:09

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.