0

First, apologies. I'm decent at math, but i don't have a degree in it. Please excuse any ignorance on my part. And if any of my math is wrong, please correct me!

So, for anyone not familiar with the diffie-hellman problem it is:

given the following:

  • g = can be any number (but usually 2, and known before hand)
  • p = an absurdly large, known prime
  • X = (ga % p)
  • Y = (gb % p)

where only a and b are unknown, find K = (g^ab) % p

Using simple math, I notice that all of the following are equal:

  • XY % p
  • (ga % p)gb % p % p
  • (gabg % p)
  • (gab % p)g % p
  • Kg % p

As long as all that math is correct, and the knowledge that Diffie-Hellman is still unsolved, that means this is the furthest you can get. the real question: when both g and p are known, what makes solving for K in (Kg % p) so difficult?

deadPix3l
  • 1
  • I think that the jump from step 2 to 3 in your argument is not correct, are you saying that $(g^a)^{g^b}$ is the same as $g^{abg}$? – Daniel Aug 12 '17 at 21:43
  • You're not going to like this answer, but it's just really hard. You can plot things like $y=g^x \mod p$ for various fixed base and modulus and what you get looks like complete buckshot (correlation 0). There's just no nice patterns like in real exponentials which give us nice logarithms. – Randall Aug 12 '17 at 21:48
  • 1
    In the ring $\Bbb{Z}/p\Bbb{Z}$ there is no exponentiation like $X^Y$. We have powers $x^n$ where $x$ is an element of the ring, but $n$ must be an ordinary integer. Well, if we assume that the base is $\neq0$, then, by Little Fermat, you can reduce the exponent modulo $p-1$. Anyway $X^Y$ is not well-defined, when $X$ and $Y$ are residue classes. My main point is that you cannot mix bases and exponents at all, and expect any usual rules of arithmetic to hold. Also, I don't think you follow even the usual rules, but I didn't even look closely. – Jyrki Lahtonen Aug 12 '17 at 23:21
  • $a$ and $b$ are integer powers in Diffie-Hellman. The OP didn't state this. – Randall Aug 12 '17 at 23:59

0 Answers0