Binary Field Multiplication
Hi,
I was trying to verify the binary field multiplication required to perform the GHASH part of the Galois/Counter Mode (GCM) for block ciphers using Sage. In order to do so, I need to compute a multiplication in GF(2^128) using the provided irreducible polynomial p(x) = x^128 + x^7 + x^2 + x + 1.
I took Test Case 2 of Appendix B from this source. According to the specification of the standard, multiplying the ciphertext, denoted by C, with the hash subkey H (both values are represented by bit vectors containing the coefficients of their respective polynomial representation using hexadecimal basis) should give the result X1. I tried to compute the product (again represented in a hexadecimal value as provided in the standard) as follows:
sage: print version();
Sage Version 6.2, Release Date: 2014-05-06
sage: # Get test vectors from the document linked above (Test Case 2).
sage: C = Integer(0x0388dace60b6a392f328c2b971b2fe78);
sage: H = Integer(0x66e94bd4ef8a2c3b884cfa59ca342b2e);
sage: X1_exp = Integer(0x5e2ec746917062882c85b0685353deb7); # Expected product
sage: # Create the binary finite field using the given irreducible polynomial.
sage: P2.<x> = GF(2)[];
sage: p = x^128 + x^7 + x^2 + x + 1;
sage: GFghash = GF(2^128, 'x', modulus=p); GFghash
Finite Field in x of size 2^128
sage: # Create the field elements from the hexadecimal representation and multiply them.
sage: C_bf = GFghash._cache.fetch_int(C);
sage: H_bf = GFghash._cache.fetch_int(H);
sage: X1_bf = C_bf * H_bf;
sage: # Convert the field element back into a HEX representation containing the coefficients only.
sage: X1_bitvec = ''.join(map(str,X1_bf.polynomial().coeffs()));
sage: X1 = Integer(str(X1_bitvec)[::-1], base=2);
sage: # Check whether the result is correct.
sage: X1 == X1_exp
False
Unfortunately, as you can see from the output, I do not get the expected result of the multiplication (as printed in the document referenced above). Interestingly, when I perform this calculation within a smaller field (for which I can verify the result by paper and pencil), for instance in GF(2^4), the approach actually works (or at least I get the result I expected):
sage: print version();
Sage Version 6.2, Release Date: 2014-05-06
sage: # Use two elements of GF(2^4) represented by a hexadecimal coefficient bit vector.
sage: C = Integer(0xa); # a = x^3 + x = 1010(bin) = 10(dec) = a(hex)
sage: H = Integer(0xa);
sage: X1_exp = Integer(0x8); # Expected product = x^3 = 1000(bin) = 8(dec) = 8(hex)
sage: # Create the binary finite field using the given irreducible polynomial p(x) = x^4 + x + 1;
sage: P2.<x> = GF(2)[];
sage: p = x^4 + x + 1;
sage: GF16 = GF(2^4, 'x', modulus=p); GF16
Finite Field in x of size 2^4
sage: # Create the field elements from the hexadecimal representation and multiply them.
sage: C_bf = GF16._cache.fetch_int(C);
sage: H_bf = GF16._cache.fetch_int(H);
sage: X1_bf = C_bf * H_bf;
sage: # Convert the field element back into a HEX representation containing the coefficients only.
sage: X1_bitvec = ''.join(map(str,X1_bf.polynomial().coeffs()));
sage: X1 = Integer(str(X1_bitvec)[::-1], base ...