1
$\begingroup$

I am wondering if the inversion of multiplication of polynomials is equally hard as the discrete logarithm problem used for key exchange. Or are there algorithms that weaken such an usage. I understand that it is somewhat easy to factorize if one omits the division by an irreducible polynomial.

I cannot find any comparison for the hardness of

  • multiplicative inverse in GF(2^n) mod (some irreducible polynomial)
  • Diffie Hellman using exponents of g^x mod p
  • elliptic curves

Only for the last two I was able to find some comparison which favors elliptic curves over the discrete logarithm problem as the key length is about 1/12 as opposed to Diffie Hellman for the same security.

$\endgroup$
  • $\begingroup$ What is "the hardness of elliptic curves" supposed to mean? $\endgroup$ – fkraiem Aug 19 '18 at 4:05
2
$\begingroup$

The inverse is easy, it can be done by the extended Euclidean algorithm, thus polynomial in complexity compared to the others which are exponential.

$\endgroup$
  • $\begingroup$ Okay, I understand. Due to my lack of imagination that such thing would work on a mod p, I did not know such things work. But yes, even Wikipedia tells about this. $\endgroup$ – kwasmich Aug 19 '18 at 8:18
  • $\begingroup$ So if I get it right. I have to use Diffie Hellman or Elliptic Curves to get the level of security. But can do both in GF(2^n) ? $\endgroup$ – kwasmich Aug 19 '18 at 8:26
  • 1
    $\begingroup$ That's a separate question but DH and elliptic curves are strongest in large prime fields, not extension fields. $\endgroup$ – kodlu Aug 19 '18 at 10:08
  • $\begingroup$ See this crypto.stackexchange.com/questions/48153/… $\endgroup$ – kodlu Aug 19 '18 at 10:11
  • $\begingroup$ I am a novice in the field of cryptography. So I don't know if I get the things right. To my understanding an extension field is for example $GF(2^8) \mod{m}$ where $m=x^8+x^4+x^3+x+1$ which is the smallest irreducible polynomial outside of $GF(2^8)$ (which is somewhat like a prime in $GF()$). And $GF(p)$ with $p$ prime do I still need a $\mod{m}$ to wrap the values back into the field or is $m = p$ sufficient? Or is it only the case if $p$ is prime in $\mathbb{Z}$ and also forms an irreducible polynomial in $GF$. $\endgroup$ – kwasmich Aug 19 '18 at 13:46

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.