ASKSAGE: Sage Q&A Forum - Latest question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 25 Jun 2016 06:18:09 -0500Linear Algebra in Finite Fields (Goppa Codes)http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/Context:
I am trying to calculate a generator matrix for Goppa codes.
We are working in GF(16), e is a generator of GF(16), and we are given the polynomial
g = (x+e)*(x+e^14)
F.<e> = GF(16)
p = e.minpoly()
p
R.<x> = PolynomialRing(F)
g=(x+e)*(x+e^14)
i calculate the parity check matrix with coefficients in GF(16) as follows
H = matrix(F,2,12)
for i in range (2,14):
f=-((g(x)-g(e^i))/(x-e^i))*(1/g(e^i))
print("i=%s %s"%(i,f))
ff=R(f) # coerce to polynomial with canonical injection
H[0,i-2]=ff.list()[0]
H[1,i-2]=ff.list()[1]
i=2 (e^3 + e^2 + e + 1)*x + e^3 + e
i=3 (e^3 + e^2)*x + e^2 + e + 1
i=4 (e^3 + e^2)*x + e^3 + e
i=5 e*x + e^3 + 1
i=6 (e^3 + e^2 + e)*x + e^3 + e^2
i=7 x
i=8 (e^3 + 1)*x + e^2 + e + 1
i=9 (e^2 + 1)*x + e^2 + 1
i=10 (e^3 + e^2 + e)*x + e^2
i=11 (e^3 + 1)*x + e^3 + e + 1
i=12 (e^3 + e^2 + e + 1)*x + e^3 + 1
i=13 e*x + e^3 + e^2
H is a 2x12 matrix in GF(16)
now I am are interested in getting a 8x12 matrix corresponding to 8 equations. We get 4 equations for each row of H.
i am considering a vector of size 12 of unknowns c=(c1,c2,...,12) [with possible values 0 or 1], and for each row, we will look at the equation row_i * c=0 and we group terms corresponding to 1,e,e^2,e^3 and because this is a basis of GF(16) we know that the coefficients of 1,e,e^2,e^3 are 0. I want to extract those equations.
var('c1','c2','c3','c4','c5','c6','c7','c8','c9','c10','c11','c12')
C=matrix([[c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12]])
H*C.T
[ (e^3 + e)*c1 + (e^3 + e + 1)*c10 + (e^3 + 1)*c11 + (e^3
+ e^2)*c12 + (e^2 + e + 1)*c2 + (e^3 + e)*c3 + (e^3 + 1)*c4 + (e^3 +
e^2)*c5 + (e^2 + e + 1)*c7 + (e^2 + 1)*c8 + e^2*c9]
[(e^3 + e^2 + e + 1)*c1 + (e^3 + 1)*c10 + (e^3 + e^2 + e + 1)*c11 +
e*c12 + (e^3 + e^2)*c2 + (e^3 + e^2)*c3 + e*c4 + (e^3 + e^2 + e)*c5 + c6
+ (e^3 + 1)*c7 + (e^2 + 1)*c8 + (e^3 + e^2 + e)*c9]
for example for the first row the equation corresponding to e should be
(c1+c10+c2+c3+c7 =0)
could u please tell me how to recover the equation
AND to get the answer in matrix form
the next step of course is to find a basis for the kernel. How do we do that in SAGE ?
[of course it can be done by hand, but i want to be able to write the program]
PS. i am rather new to SAGE and to cryptography, i am following the MOOC from INRIA on fun-mooc
thank youfaguiSat, 25 Jun 2016 06:18:09 -0500http://ask.sagemath.org/question/33915/Binary 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,
MikemikemichiThu, 07 Aug 2014 03:48:35 -0500http://ask.sagemath.org/question/23707/