The Massey-Omura cryptosystem uses "multiplication over the finite field $GF(2^n)$. I'm just starting understand the idea of multiplying polynomials and I've searched for online calculators to use for this. Thing is, all of these calculators request that I enter some sort of polynomial modulus and I don't know which one the cryptosystem uses.


Actually, it doesn't matter (as long as the polynomial is prime, of course).

For any $n$, there's only one finite field $GF(2^n)$, however there are a number of ways of mapping those elements to bit patterns. We call that mapping a representation; one method of generating such a representation is to use a prime polynomial of degree $n+1$.

Now, between any two representations of $GF(2^n)$, there will be a mapping that converts values in one representation into values in the other; if both representations are sane (by which I mean that they perform addition by bit-wise exclusive-or of the representation), then this mapping will be linear (and hence, cheap to compute).

In Massey-Omura, the sides exchange the representations of the field elements $m^a$, $m^{ab}$, $m^b$; if there was a representation that makes this exchange weak, then the attacker could convert these three elements into that weak representation, find the value $m$ in that weak representation, and then map it back into the original representation, breaking MO in the supposedly strong representation. Hence, no representation is any stronger or weaker than any other -- the choice of representation is strictly a practical matter.

In fact, if you go to the patent, Massey and Omura suggest using a normal representation (which is an alternative to a polynomial representation); in normal representations, the operation of squaring is cheap, and they believe that this will make computing exponentiation cheaper overall. Again, this is a practical consideration -- it has no impact on security.

I will leave off with one security issue: people have recently made significant progress in computing discrete logs over $GF(p^m)$ for small $p$ (and 2 is as small as we can get), and smooth $m$. Because of this, it would appear to be wise to select a prime value of $n$; that way, these recent results do not apply.

| improve this answer | |
  • $\begingroup$ How do I know if a polynomial is "prime" (that makes no sense) and how do I determine the correct (or a correct) polynomial to use on the fly for any given n? What is a normal representation? What would a field representation for GF(2^8) look like? $\endgroup$ – Melab Feb 19 '15 at 16:59
  • $\begingroup$ @Melab: A polynomial is prime if it isn't the product of two smaller polynomials; for example, $x^2+x+1$ is prime, while $x^2+1 = (x+1)\times(x+1)$ is not. As for determining a valid representation on the fly for an arbitrary $n$, well, I don't know of a cheap way. Until you learn more, I'd suggest you stick with a fixed value of $n$ (and use a known valid polynomial). $\endgroup$ – poncho Feb 19 '15 at 17:53
  • $\begingroup$ How is $x+1$ a factor polynomial of $x^2+1$? $\endgroup$ – Melab Feb 19 '15 at 18:03
  • $\begingroup$ @Melab: What is $(x+1) \times (x+1)$ (doing arithmetic in $GF(2)$)? $\endgroup$ – poncho Feb 19 '15 at 18:04
  • $\begingroup$ Ooooh. I get what you are saying. $\endgroup$ – Melab Feb 19 '15 at 18:19

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.