1
$\begingroup$

I'm trying to understand how Diffie Helman is still secure when $A$ ends up being a power of $g$ less than $p$.

I chose $p$, where p is prime, and $g$ is a primitive root modulo $p$.

$g=2$ and $p=29$

Now considering Alice creating her $A$ where $A=2^a\mod{29}$. If she chooses $a=30$ this results in $2^{30}=4\mod{29}$, which means I can trivially recover an $a$ with the same result $a=log_2{4}=2$ and use that to recover the shared secret.

In general any returned $A$ that is a power of $2$ less than $29$ (ie. $2,4, 8,16$) can be trivially recovered by taking $log_2{A}$ and getting a valid $a$.

How does Diffie Helman resist against this? I'm I missing something else? I know I chose a small $a$ and $p$ but it seems this problem would exist with large $a$ and $p$ too.

$\endgroup$
5
$\begingroup$

If $g^a<p$, then the discrete logarithm mod $p$ becomes plain logarithm, even for a 2048-bit $p$. So, you are right that in this case $a$ can be easily computed from $g^a$. However, this is not bad because there are only at most $\log_2 p$ such $a$s (that satisfy $g^a<p$). Compared to $p$, $\log_2 p$ is a negligible number. In other words, since $a$ is chosen uniformly at random from $p-1$ values, the probability that it falls into the first $\log_2 p$ values is negligible (in $\log_2 p$, the bit length of $p$).

$\endgroup$
2
$\begingroup$

First of all, the choice of $a$ must satisfy $1 \leq a < p$, The exponent $a = 30$, for this prime, is equivalent to the exponent $2$ because $30 \equiv 2 \mod{\phi(29)}$.

Secondly, as you stated the $p$ is very small. Thus, with a paper and pencil one can calculate the discrete log problem. When you consider, the recommended size of $p$ as 2048-bit (see at update of RFC4419) you will face the real problem.

When $a$ is chosen randomly, it will have 2047-bits with 1/2 probability-think of the MSB has 1/2 probability to equal 1. Now consider calculating discrete logarithm problem. The complexity is $\mathcal{O}(\sqrt{p})$ with Baby-step giant-step. With Pollard's kangaroo algorithm it is $\mathcal{O}(\sqrt{b-a})$ where the algorithm selects a set $\{a,\ldots, b\}$, the original paper.

$\endgroup$

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.