Matrix GF2 Algebra

On A5/1 Explained IV

By Juan Chamero, juan.chamero@intag.org, as of April 2006

Going Backwards

How to invert GF2 Matrices

    In this peculiar process where shift  registers are feed from their right lsb with Kj unity vectors with its unique nonzero component located at its rightmost bit, the C*K product of any order is reduced to the XORing of last column of C matrices by Kj vectors. The algebra of states transition will take the form:

Si(9) = Ci(1)^8*Si(0) + Ci(1)^8*K1 + Ci(1)^7*K2 + ……. + Ci(1)^1*K8 + K9

Si(9) = C(i)^8*Si(0) + XOR of MiK(0=>9) row vectors

Si(9) = MiK(0=>9)XOR

Where the matrices MiK(0=>9) (with corresponding K bits diffused in it) , corresponding to traversing from states 0 to 9 are built with as many rows as the path to traverse (9 states ó 9 rows) having the following structure:

Row 1 ó C1(8) ó [0  k1  0  k1]

Row 2 ó C1(7) ó [k2 0   k2  0]

Row 3 ó C1(6) ó [k3 k3  0 k3]

Row 4 ó C1(5) ó [0  k4  k4  0]

Row 5 ó C1(4) ó [0  0   k5 k5]

Row 6 ó C1(3) ó [k6 0   0  k6]

Row 7 ó C1(2) ó [0  k7  0   0]

Row 8 ó C1(1) ó [0  0   k8  0]

Row 9 ó C1(0) ó [0  0   0  k9]

    As we see Mi matrices are very easy to generate provided we have pre computed all the Ci’s transition matrices. As we are going to generalize soon this procedure could be applied to non zero initial states and for any traverse.

For register R1 the nine steps Mi is as follows:

0 1 0 1

0 0 0 0

1 1 0 1

0 1 1 0

0 0 0 0

1 0 0 1

0 1 0 0

0 0 0 0

0 0 0 1

0 0 1 0

And XOR is even simpler because key bit equal to 0 eliminate the corresponding row. The XOR of the six non zero binary vectors give us the resulting state Si(9) = [0 0 1 0]

    Let’s see the procedure when initial states are non zero. For instance how to “jump” directly from state S1(4) = [1 0 1 0] to the same S1(9) throughout a direct jump of 5 steps.

S1(9) = C1(5)*S1(4) + M1(5=>9)(XOR)

M1(4=>9)

0 0 1 1  ó k5=0

1 0 0 1  ó k6=1

0 1 0 0  ó k7=1

0 0 1 0  ó k8=0

0 0 0 1  ó k9=1

1 1 0 0 that XORed with the regular transition (in absence of K) from S1(4) to S1(9) via C1(5)*S1(4)  that gives us 1 1 1 0 it reproduces S1(9) = (1 1 0 0) XOR ( 1 1 1 0) = (0 0  1 0)

    Algebraically we may define states as:

(1)  Si(a) = C1(b-a)*Si(b) + M1(a=>b)XK(a=>b)

Where the operation X stands for XOR bitwise between M1(a=>) XORed versus K(a=>b), being K(a=>b) a K bits vector that circularly goes from a=>b. Concerning A5/1 matrices Mi that go from Si(0) to Si(64) have the following dimensions:

M1(0 =>64): 64x19

M2(0 =>64): 64x22

M3(0 =>64): 64x23

And Mi matrices coefficients are formed with Ci matrices last columns from Ci(1) to Ci(64). Our problem is how we may go backwards algebraically. Going forward is trivial as we have demonstrated applying (1), in A5/1:

S1(64) = C1(64)*S1(0) + M1(1=>64)XK

S2(64) = C2(64)*S2(0) + M2(1=>64)XK

S3(64) = C3(64)*S3(0) + M3(1=>64)XK

As A5/1 proceed to make all Si(0) equal to zero in this mixing with K, expressions simplify to

Si(64) = Mi(1=>64)XK

Returning to our example we have:

M1(1=>9)XK

C1(8) last column: 0101 ó K1

C1(7) last column: 1010 ó K2

C1(6) last column: 1101 ó K3

C1(5) last column: 0110 ó K4

C1(4) last column: 0011 ó K5

C1(3) last column: 1001 ó K6

C1(2) last column: 0100 ó K7

C1(1) last column: 0010 ó K8

C1(0) last column: 0001 ó K9

Result: 0010

That represents the following set of 4 equations:

k2 + k3 + k6 = 0 = S1(9) (3) ó bit 3 msb

k1 + k3 + k4 +k7 = 0 = S1(9) (2) ó bit 2

k2 + k4 + k5 + k8 = 1 = S1(9) (1) ó bit 1

k1 + k3 + k5 + k6 + k9 = 0 = S1(9) (0) ó bit 0

And for next register we get

M2(1=>9)XK

C2(8) last column: 010 ó K1

C2(7) last column: 101 ó K2

C2(6) last column: 011 ó K3

C2(5) last column: 111 ó K4

C2(4) last column: 110 ó K5

C2(3) last column: 100 ó K6

C2(2) last column: 101 ó K7

C2(1) last column: 010 ó K8

C2(0) last column: 001 ó K9

Giving place to the following set of equations:

k2 + k4 + k5 + k6 + k7 = 1 = S2(9) (2) ó bit 2 msb

k1 + k3 + k4 + k5 + k8 = 1 = S2(9) (1) ó bit 1

k2 + k3 + k4 + k7 + k9 = 0 = S2(9) (0) ó bit 0

And for last register R3 we get

M3(1=>9)XK

C3(8) last column: 11 ó K1

C3(7) last column: 10 ó K2

C3(6) last column: 01 ó K3

C3(5) last column: 11 ó K4

C3(4) last column: 10 ó K5

C3(3) last column: 01 ó K6

C3(2) last column: 11 ó K7

C3(1) last column: 10 ó K8

C3(0) last column: 01 ó K9

Giving place to the following set of equations:

k1 + k2 + k4 + k5 + k7 + k8 = 1 = S3(9) (1) ó bit 1 msb

k1 + k3 + k4 + k6 + k7 + k9 = 0 = S3(9) (0) ó bit 0

S1(9) (3) ó 0 1 1 0 0 1 0 0 0                k1

S1(9) (2) ó 1 0 1 1 0 0 1 0 0     k2

S1(9) (1) ó 0 1 0 1 1 0 0 1 0     k3

S1(9) (0) ó 1 0 1 0 1 1 0 0 1     k4

S2(9) (2) ó 0 1 0 1 1 1 1 0 0     k5

S2(9) (1) ó 1 0 1 1 1 0 0 1 0     k6

S2(9) (0) ó 0 1 1 1 0 0 1 0 1     k7

S3(9) (1) ó 1 1 0 1 1 0 1 1 0     k8

S3(9) (0) ó 1 0 1 1 0 1 1 0 1     k9

    This is then the final expression that given K generates at the end of the “K mixing process”: M*K = S(9), and in the general case:

M*K = S

For the ciphering run and consequently its inversion:

M´S = K

Retrieve the private keyword from a S(64) state, being M´ the inverse matrix of M.

k2 + k3 + k6 = 0

k1 + k3 + k4 +k7 = 0

k2 + k4 + k5 + k8 = 1

k1 + k3 + k5 + k6 + k9 = 0

k2 + k4 + k5 + k6 + k7 = 1

k1 + k3 + k4 + k5 + k8 = 1

k2 + k3 + k4 + k7 + k9 = 0

9k1 + k2 + k4 + k5 + k7 + k8 = 1

k1 + k3 + k4 + k6 + k7 + k9 = 0

Eq 9: k9= k1 + k3 + k4 + k6 + k7

k2 + k3 + k6 = 0

k1 + k3 + k4 +k7 = 0

k2 + k4 + k5 + k8 = 1

k1 + k3 + k5 + k6 + 0 + k1 + k3 + k4 + k6 + k7 = 0 = k4 + k5 + k7

k2 + k4 + k5 + k6 + k7 = 1

k1 + k3 + k4 + k5 + k8 = 1

k2 + k3 + k4 + k7 + 0 + k1 + k3 + k4 + k6 + k7 = 0 = k1 + k2 + k6

k1 + k2 + k4 + k5 + k7 + k8 = 1

k2 + k3 + k6 = 0

k1 + k3 + k4 +k7 = 0

k2 + k4 + k5 + k8 = 12

k4 + k5 + k7 = 0

k2 + k4 + k5 + k6 + k7 = 1

k1 + k3 + k4 + k5 + k8 = 1

k1 + k2 + k6 = 0

k1 + k2 + k4 + k5 + k7 + k8 = 1

Eq. 8: k8 = 1 + k1 + k2 + k4 + k5 + k7

k2 + k3 + k6 = 0

k1 + k3 + k4 +k7 = 0

k2 + k4 + k5 + 1 + k1 + k2 + k4 + k5 + k7 = 1 => k1 + k7 = 0

k4 + k5 + k7 = 0

k2 + k4 + k5 + k6 + k7 = 1

k1 + k3 + k4 + k5 + 1 + k1 + k2 + k4 + k5 + k7 = 1 => k2 + k3 + k7 = 0

k1 + k2 + k6 = 0

k2 + k3 + k6 = 0

k1 + k3 + k4 +k7 = 0

k1 + k7 = 0

k4 + k5 + k7 = 0

k2 + k4 + k5 + k6 + k7 = 1

k2 + k3 + k7 = 0

k1 + k2 + k6 = 0

Eq. 7: k7 = k2 + k3

k2+ k3 + k6 = 0

k1 + k3 + k4 + k2 + k3 = 0 => k1 + k2 + k4 = 0

k1 + k2 + k3 = 0 => k1 + k2 + k3

k4 + k5 + k2 + k3 = 0 => k2 + k3 + k4 + k5 = 0

k2 + k4 + k5 + k6 + k2 + k3 = 1 => k2 + k3 + k4 + k5 + k6= 1

k1 + k2 + k6 = 0

k2+ k3 + k6 = 0

k1 + k2 + k4 = 0

k1 + k2 + k3 = 0

k2 + k3 + k4 + k5 = 0

k2 + k3 + k4 + k5 + k6= 1

k1 + k2 + k6 = 0

Eq. 6: k6 = k1 + k2

k2+ k3 + k1 + k2 = 0 => k1 + k3 = 0

k1 + k2 + k4 = 0

k1 + k2 + k3 = 0

k2 + k3 + k4 + k5 = 0

k2 + k3 + k4 + k5 + k1 + k2= 1 => k1 + k3 + k4 + k5  = 1

k1 + k3 = 0

k1 + k2 + k4 = 0

k1 + k2 + k3 = 0

k2 + k3 + k4 + k5 = 0

k1 + k3 + k4 + k5  = 1

Eq. 5: k5 = 1 + k1 + k3 + k4

0k1 + k3 = 0

k1 + k2 + k4 = 0

k1 + k2 + k3 = 0

k2 + k3 + k4 + 1 + k1 + k3 + k4 = 0 => k1 + k2 = 1

k1 + k3 = 0

k1 + k2 + k4 = 0

k1 + k2 + k3 = 0

k1 + k2 = 1

Eq. 4: k4 = k1 + k2

k1 + k3 = 0

k1 + k2 + k3 = 0

k1 + k2 = 1

Eq. 3: k3 = k1

k1 + k2 + k1 = 0 => k2 = 0

k1 + k2 = 1

k2 = 0

k1 + k2 = 1

Eq. 2: k2 = 0

k1 = 1

Eq. 1: k1 = 1

Now going backwards

k1 = 1

k2 = 0

k3 = k1 = 1

k4 = k1 + k2 = 1 + 0 = 1

k5 = 1 + k1 + k3 + k4 = 1 + 1 + 1 + 1 = 0

k6 = k1 + k2 = 1 + 0 = 1

k7 = k2 + k3 = 0 + 1 = 1

k8 = 1 + k1 + k2 + k4 + k5 + k7 = 1 + 1 + 0 + 1 + 0 + 1 = 0

k9 = 0 + k1 + k3 + k4 + k6 + k7 = 0 + 1 + 1 + 1 + 1 + 1 = 1

K(9) = M´*S(9) = [1 0 1 1 0 1 1 0 1]

    The procedure is straightforward like in the conventional Gauss Jordan method, by eliminating a variable at a time and once we get k1 going “forward“ we may proceed “backwards to solve k2 by using the (n-1) equation between k1 and k2, and then k3 using the (n-2) equation between k1, k2 and k3, and so on and so forth to get kn. To have a general procedure we may compute n times this replacement algorithm for a matrix US of n “Unity States”:

US1 = [1 0 0 ……………0]

US2 = [0 1 0 ……………0]

US3 = [0 0 1 ……………0]

……………………………..

USn = [0 0 0 ……………1]

Pseudo Gauss-Jordan XOR Algorithm => US => M´

Appendices

A) something about the XOR matrix logic

    Let’s see how we should deal with the classical algebra operations aOb where the Operator symbol O stands for product (.), division (/), addition (+), subtraction (-) respectively.

a + b = c has the following outcomes:

a – b = c bound to a = b + c, using the same table