ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 07 Aug 2014 03:48:35 -0500Binary Field Multiplicationhttp://ask.sagemath.org/question/23707/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)](http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf) 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](http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-revised-spec.pdf) 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:
<pre><code>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
</code></pre>
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):
<pre><code>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=2);
sage: # Check whether the result is correct.
sage: X1 == X1_exp
True
</code></pre>
The actual questions I have right now, are:
1. Are there any limitations with regard to the maximum degree of the binary extension field with the approach I am using here?
2. If possible, can anybody point me to the mistake I am doing when operating in `GF(2^128)`?
Thanks,
MikeThu, 07 Aug 2014 03:48:35 -0500http://ask.sagemath.org/question/23707/binary-field-multiplication/