# PIN-based authentication with Diffie-Hellman modular arithmetic

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.

• Do you mean $$(2^{intvalueof(“server”)^{pin}} \bmod P)\bmod P$$ or $$2^{intvalueof(“server pin")}\bmod P)\bmod P$$ Commented Apr 25, 2021 at 18:10
• @kelalaka I have refined my question, thank you for your feedback Commented Apr 25, 2021 at 21:24
• 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.
– fgrieu
Commented May 14, 2021 at 7:52

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.