# What is the polynomial to use in the Massey-Omura cryptosystem?

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.

• 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? – Melab Feb 19 '15 at 16:59
• @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). – poncho Feb 19 '15 at 17:53
• How is $x+1$ a factor polynomial of $x^2+1$? – Melab Feb 19 '15 at 18:03
• @Melab: What is $(x+1) \times (x+1)$ (doing arithmetic in $GF(2)$)? – poncho Feb 19 '15 at 18:04
• Ooooh. I get what you are saying. – Melab Feb 19 '15 at 18:19