Alice and Bob are using DHKE in the group $\mathbb{Z}_p^ * $, where $p = 1031 = 2 \cdot 5 \cdot 103 + 1$. Their generator $g = 2$, which generates a multiplicative group of order $515$ in $\mathbb{Z}_{1031}^ * $. This group has a subgroup consisting of $5$ elements $\{ 1,518,264 = {518^2},660 = {518^3},619 = {518^4}\} $. Eve uses this subgroup to find out DH keys exchanged by Alice and Bob. In one exchange, Alice sends ${2^a} = 919$ to Bob. Eve intercepts the message, raises $919$ to the power $103$ and gets $619\,\bmod \,1031$. Eve sends $A = 619$ to Bob. Bob replies by sending ${2^b} = 270$. Eve intercepts it, raises $270$ to the power $103$, gets $660\,\bmod \,1031$, and sends $B = 660$ to Alice. Eve now finds the integer value of DH key ${B^a} = {A^b}$ computed by Alice and Bob without knowledge of $a$ and $b$, and actually without any more computations modulo $1031$. Explain how this is possible, and give the value of the resulting DH key.
My solution:
Eve was smart enough to come up with a subgroup $S < \mathbb{Z}_{1031}^ * $ such that $\left| S \right| = 5$ and $S = \left\langle {518} \right\rangle $. By Lagrange theorem we know that all elements of $S$ must have an order $1$ or $5$. Thus it follows that $\left| 1 \right| = 1{\text{ and }}\left| {518} \right| = \left| {264} \right| = \left| {660} \right| = \left| {619} \right| = 5$. Furthermore, we know that $S = \left\langle {264,518,619,660} \right\rangle $.
Alice sends to Bob ${2^a} = 919$, when Eve stops the message she computes ${({2^a})^{103}} = {(919)^{103}} = 619 = {518^4}$ and hence Bob receives $619 = {518^4}$. Bob sends to Alice ${2^b} = 270$, when Eve stops the message she computes ${({2^b})^{103}} = {(270)^{103}} = 660 = {518^3}$ and hence Alice receives $660 = {518^3}$.
The value of the key is $$K = {B^a} = {660^a} = {518^{3a}} = {518^{4b}} = {619^b} = {A^b}$$Clearly the usage of much smaller subgroup with the following properties allow Eve to forge the message and limit a search domain to $5$ values. However, i do not understand how Eve can find the integer value of the key without knowing $a$ or $b$ and without more computations modulo $1031$.
For different values of $a$ and $b$ the generator of $S$ - $518$ will produce one of five possible values that will satisfy the equality. The only way i see Eve finds the key is by trying all five possible values (e.g small exhaustive search). In this way Eve does not need to do more computations modulo $1031$ as she knows the elements of $S$.
However the problem asks to give the value of the key. Does it mean that i have to try all $5$ values from $S$ or the key can be indeed determined uniquely without performing exhaustive search on $S$?
