ASKSAGE: Sage Q&A Forum - Latest question feedhttps://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 Multiplicationhttps://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,
MikemikemichiThu, 07 Aug 2014 03:48:35 -0500https://ask.sagemath.org/question/23707/Binary fieldshttps://ask.sagemath.org/question/11059/binary-fields/Hello, I would like to perform the following on a binary field, i.e. `GF(2^m)`.
1. Define a polynomial and solve the polynomial over a binary field.
2. Convert an element of the binary field into a bit string.
For the first, I've tried the following:
K = GF(2^7,'a');
PK.<x>=K[]; #I've also tried "x = PolynomialRing(GF(2^7,'a'),'x').gen"
f = (a^6 + a^3 + a)*x^2 + (a^6 + a^4 + a^3)*x + (a^5 + a^4 + a^3 + a^2 + 1);
print f.roots();
But the error is `TypeError: unable to coerce from a finite field other than the prime subfield`.
For the second, I would like to know how finite field elements are stored in SAGE, are they stored as vectors?
If you have any resources that could point me in the right direction, I'll be very thankful for your help!BlackadderThu, 05 Jun 2014 16:05:40 -0500https://ask.sagemath.org/question/11059/