0

I very well understand the Diffie-Hellman key exchange method, at least I think I do. And I was trying to implement it to try it out.

I went and calculated a very large prime number $p$ about $400$ digits long. And I set $g$ to $5$.

I generated a random secret number $a$, for example : "$42523434$".

The problem I'm facing is when I calculate $g^a \operatorname{mod} p$, $g^a$ in particular, it seems to take my computer forever to calculate it, so it seems to be impractical to give $a$ such a number so I went for a smaller number (a five digit number) which takes about a second or two to calculate.

So now we have $A=g^a \operatorname{mod} p$, with the eavesdropper knowing $g$, $p$, and $A$.

But wouldn't it be possible to brute force $a$ by trying all $100000$ combinations until what he calculates matches $A$ which wouldn't take him that long if he good computing powers? A solution to this would be increasing $a$ but increasing $a$ would make the exchange take so long that it wouldn't be a good method to exchange the keys.

Edit:

We can compute g^a mod p using such a program:

for x in range(1,100000):
    if(((g**x)%p)==A):
        print x
Ali Shriem
  • 1
  • 1
    Exactly how is your machine computing $g^a \mod p$? – Randall Aug 15 '17 at 02:52
  • @Randall I edited the question to show how you might approach finding "a" – Ali Shriem Aug 15 '17 at 03:05
  • You say the attacker need "only" try all 100,000 choices for $a$ until they match $A$, but your prime was 400 digits long (well over 1024 bits). Why would the attacker know that you decided to choose only a 5-digit integer for $a$? They wouldn't know this, unless it was an advertised vulnerability of your implementation (or, even worse, unless you TOLD them this). – Randall Aug 15 '17 at 03:16
  • Generally, in these crypto protocols that work by exponents mod $n$, the number of choices for the secret exponent is $\varphi(n)$, which is still incredibly large when $n$ is. This count of $\varphi(n)$ is due to Euler's Theorem. – Randall Aug 15 '17 at 03:17
  • In Python you should use pow(g,a,p) which is very fast. Try it! – Henno Brandsma Aug 15 '17 at 19:34

1 Answers1

1

You can increase the exponent, just use fast exponentiation algorithm. It is probably not natively implented in the exponential function you are using. And if you are using it, then you need a computer with processor that is not from the early 90's.

An example of such algorithm -

Function exp_by_squaring_iterative(g, e(xponent),p(rime)) 

if n = 0 then return 1
y := 1;
while n > 1 do
  if n is even then 
    e := (e * e) mod p;
    n := n / 2;
  else
    y := (e * y) mod p;
    e := (e * e) mod p;
    n := (n – 1) / 2;
return e * y

Algorithm taken from here https://en.wikipedia.org/wiki/Exponentiation_by_squaring, I just added the mod part and renamed some variables and removed the negative part, assuming you do not need to compute negative powers.

The other problem may be in implementation of the arbitrarily large numbers in the language you are using, in which case I recommend searching for a better library or language.

However this probably should have been posted on a crypto exchange or something to do with computers and programming languages, because I am convinced your problems are straightforward implementations of the arithmetic operations. But because you did not do that, I guess your implementation of the key exchange algorithm was done naively and that the above algorithm might help you to increase the exponent to any desired size with acceptable computational time.

TStancek
  • 1,027
  • 5
  • 14