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

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < February 12 ! width="25%" align="center"|<< Jan | February | Mar >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded 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)