1
$\begingroup$

Given $\text{server}_\text{pub}= ((2^\text{largerandom}\bmod P) \cdot (2^{\operatorname{intvalueof}(“XXXX”)} \bmod P)^\text{pin})\bmod P$

We know the $\text{server}_\text{pub}$ and we know that $\text{pin} \in [0,9999]$. What we want to find out is the pin. You could write it as $( (2^x \bmod P) \cdot Z ) \bmod P = \text{server}_\text{pub}$

$Z$ is one of 10K values.

I think somehow since $\text{pin} \in [0,9999]$ we should be able to brute force the value but I am unable to come up with the math to do so.

$(2^\text{largerandom} \bmod P) = (\text{server}_\text{pub}\cdot(2^{\operatorname{intvalueof}(“XXXX”)^{-\text{pin}}} \bmod P)) % prime$

So the question is: how can use the fact that $\text{pin} \in [0,9999]$ to determine the value $(2^\text{largerandom} \bmod P)$. Where $\text{largerandom}\in [1, P-1]$ and $P$ is a large RFC-based prime.

$\endgroup$
3
  • $\begingroup$ Do you mean $$(2^{intvalueof(“server”)^{pin}} \bmod P)\bmod P$$ or $$2^{intvalueof(“server pin")}\bmod P)\bmod P$$ $\endgroup$
    – kelalaka
    Apr 25, 2021 at 18:10
  • $\begingroup$ @kelalaka I have refined my question, thank you for your feedback $\endgroup$ Apr 25, 2021 at 21:24
  • $\begingroup$ I think $\text{server}_\text{pub}\cdot(2^{\operatorname{intvalueof}(“XXXX”)^{-\text{pin}}} \bmod P)$ should be $\text{server}_\text{pub}\cdot(2^{\operatorname{intvalueof}(“XXXX”)\cdot\text{pin}} \bmod P)$ for consistency with the first formula. $\endgroup$
    – fgrieu
    May 14, 2021 at 7:52

1 Answer 1

2
$\begingroup$

I think somehow since $pin \in [0,9999]$ we should be able to brute force the value but I am unable to come up with the math to do so.

Unless the random number generator is broken, there is no way to recover pin; this would remain true even if we were able to compute discrete logs mod $P$ (which we can't).

The issue is that the public key is generated as:

$$server\_pub = 2^{R + N \cdot pin} \bmod P$$

(where $R$ is largerandom, and N is the publicly known intvalueof("server") value)

Even if we were able to compute the discrete log, that would give us $R + N \cdot pin \bmod (P-1)/2$ [1]; however for any potential value of $pin$, there is a value of $R$ that gives us the value consistent with the observed server_pub; because $R$ is assumed to be (almost) uniformly distributed over $[0, (P-1)/2)$ [2], that observed public value gives us no information about the value of pin.

Our inability to compute discrete logs does not change the above reasoning.


[1]: why $\bmod (P-1)/2$? That's the size of the group that $2$ generates modulo this prime

[2]: in your code, $R$ is generated uniformly randomly in the code over $[1, P-1]$; that does mean that the possible value $R \equiv 0 \bmod (P-1)/2$ is less than any other value of $R$. This would, at extremely rare occasions, allow us to deduce that a specific pin value is somewhat less likely to be the correct value - however, this is so rare (probability of us being able to deduce that is approximately $1000/ P \approx 3 \cdot 10^{-613}$) that we can ignore that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.