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.

Improve this question
$\endgroup$
1
  • $\begingroup$ What is "the hardness of elliptic curves" supposed to mean? $\endgroup$
    – fkraiem
    Aug 19, 2018 at 4:05

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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, 2018 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, 2018 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, 2018 at 10:08
  • $\begingroup$ See this crypto.stackexchange.com/questions/48153/… $\endgroup$
    – kodlu
    Aug 19, 2018 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, 2018 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.