# The strength of ECDH public keys with small order

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.

• Hint: Lagrange's theorem. – yyyyyyy Jan 25 '18 at 21:37
• @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. – Joz Jan 25 '18 at 21:42

$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).