Wikipedia:Reference desk/Archives/Mathematics/2015 February 13

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 13

Massey-Omura cryptosystem

From three-pass protocol:

The Massey-Omura Cryptosystem was proposed by James Massey and Jim K. Omura in 1982 as a possible improvement over the Shamir protocol. The Massey-Omura method uses exponentiation in the Galois field GF(2ⁿ) as both the encryption and decryption functions. That is E(e,m)=m^e and D(d,m)=m^d where the calculations are carried out in the Galois field. For any encryption exponent e with 0<e<2ⁿ-1 and gcd(e,2ⁿ-1)=1 the corresponding decryption exponent is d such that de ≡ 1 (mod 2ⁿ-1). Since the multiplicative group of the Galois field GF(2ⁿ) has order 2ⁿ-1 Lagrange's theorem implies that m^de=m for all m in GF(2ⁿ)^* .

I have been able to get the Shamir three-pass protocol to work, but I don't know how to do this one. How do I perform "calculations...carried out in the Galois field"? — Melab±1 ☎ 21:18, 13 February 2015 (UTC)

See Finite field arithmetic. In brief: Addition in the field is bitwise XOR. Multiplication is the usual positional long addition (XOR with shifts), except that whenever a nonzero bit ends up left of the bit length, you add (XOR) a constant bitstring with the constant's MSB aligned to it and thus cancel it, repeating until there only zeros left of the rightmost n bits. The constant is determined by the representation of the field (the irreducable poynomial). Exponentiation is repeated by multiplication, which can be done pretty efficiently through exponentiation by squaring. There is a lot of code online if you Google finite field arithmetic, Galois field arithmetic etc. —Quondum 23:01, 13 February 2015 (UTC)

An arguably more elegant but much less common approach, which works only for fields of order $2^{2^{k}}$, is to use the first $2^{2^{k}}$ nimbers with the standard nimber sum (bitwise xor) and product. -- BenRG (talk) 23:17, 13 February 2015 (UTC)

You lost me at "usual positional long addition". Can I have an example, maybe, or what is so special about using polynomials in such a convoluted way? — Melab±1 ☎ 15:33, 19 February 2015 (UTC)