Efficient pen-and-paper calculation of the Galois Field multiplication?

Question

I have been reading on multiplication over GF for the Inverse Matrix Step in AES, and I feel like converting the hex numbers to binary, multiplying them and then doing the modifications required for GF arithmetic is too time-consuming when done by hand.

It would be very helpful if someone could help me with a faster way to do it.

Answer 1

Probably the easiest way to do finite field multiplication by hand is using discrete logarithm and antilogarithm tables. For example, here's a pair of such tables for the AES field (using 3 as the base), generated using this Python code:

log| _0 _1 _2 _3 _4 _5 _6 _7 _8 _9 _A _B _C _D _E _F
---+------------------------------------------------
0_ | -- 00 19 01 32 02 1A C6 4B C7 1B 68 33 EE DF 03
1_ | 64 04 E0 0E 34 8D 81 EF 4C 71 08 C8 F8 69 1C C1
2_ | 7D C2 1D B5 F9 B9 27 6A 4D E4 A6 72 9A C9 09 78
3_ | 65 2F 8A 05 21 0F E1 24 12 F0 82 45 35 93 DA 8E
4_ | 96 8F DB BD 36 D0 CE 94 13 5C D2 F1 40 46 83 38
5_ | 66 DD FD 30 BF 06 8B 62 B3 25 E2 98 22 88 91 10
6_ | 7E 6E 48 C3 A3 B6 1E 42 3A 6B 28 54 FA 85 3D BA
7_ | 2B 79 0A 15 9B 9F 5E CA 4E D4 AC E5 F3 73 A7 57
8_ | AF 58 A8 50 F4 EA D6 74 4F AE E9 D5 E7 E6 AD E8
9_ | 2C D7 75 7A EB 16 0B F5 59 CB 5F B0 9C A9 51 A0
A_ | 7F 0C F6 6F 17 C4 49 EC D8 43 1F 2D A4 76 7B B7
B_ | CC BB 3E 5A FB 60 B1 86 3B 52 A1 6C AA 55 29 9D
C_ | 97 B2 87 90 61 BE DC FC BC 95 CF CD 37 3F 5B D1
D_ | 53 39 84 3C 41 A2 6D 47 14 2A 9E 5D 56 F2 D3 AB
E_ | 44 11 92 D9 23 20 2E 89 B4 7C B8 26 77 99 E3 A5
F_ | 67 4A ED DE C5 31 FE 18 0D 63 8C 80 C0 F7 70 07

exp| _0 _1 _2 _3 _4 _5 _6 _7 _8 _9 _A _B _C _D _E _F
---+------------------------------------------------
0_ | 01 03 05 0F 11 33 55 FF 1A 2E 72 96 A1 F8 13 35
1_ | 5F E1 38 48 D8 73 95 A4 F7 02 06 0A 1E 22 66 AA
2_ | E5 34 5C E4 37 59 EB 26 6A BE D9 70 90 AB E6 31
3_ | 53 F5 04 0C 14 3C 44 CC 4F D1 68 B8 D3 6E B2 CD
4_ | 4C D4 67 A9 E0 3B 4D D7 62 A6 F1 08 18 28 78 88
5_ | 83 9E B9 D0 6B BD DC 7F 81 98 B3 CE 49 DB 76 9A
6_ | B5 C4 57 F9 10 30 50 F0 0B 1D 27 69 BB D6 61 A3
7_ | FE 19 2B 7D 87 92 AD EC 2F 71 93 AE E9 20 60 A0
8_ | FB 16 3A 4E D2 6D B7 C2 5D E7 32 56 FA 15 3F 41
9_ | C3 5E E2 3D 47 C9 40 C0 5B ED 2C 74 9C BF DA 75
A_ | 9F BA D5 64 AC EF 2A 7E 82 9D BC DF 7A 8E 89 80
B_ | 9B B6 C1 58 E8 23 65 AF EA 25 6F B1 C8 43 C5 54
C_ | FC 1F 21 63 A5 F4 07 09 1B 2D 77 99 B0 CB 46 CA
D_ | 45 CF 4A DE 79 8B 86 91 A8 E3 3E 42 C6 51 F3 0E
E_ | 12 36 5A EE 29 7B 8D 8C 8F 8A 85 94 A7 F2 0D 17
F_ | 39 4B DD 7C 84 97 A2 FD 1C 24 6C B4 C7 52 F6(01)

To use these tables to multiply two hexadecimal numbers in the AES field, follow these steps:

1. If either of the numbers is 0, the result will also be 0, because that's how multiplication by zero works in general. In that case, you can stop here. Otherwise, follow the steps below:

2. Look up both of the numbers in the first table (the one with log in the top left corner). Specifically, for each number, find the entry at the intersection of the row matching the first hex digit and the column matching the second hex digit of the number being looked up. This is the (base 3) discrete logarithm of the number in the AES field.

   For example, let's say we want to multiply 84 and 5A. Looking at row 8_ and column _4 of the log table, we find that the base 3 discrete logarithm of 84 is F4. Doing the same for 5A, we find that its discrete logarithm (at the intersection of row 5_ and column _A) is E2.

3. Add the results of the previous step together modulo 255. That is to say, first add them together normally, and if this results in a three hex digit sum, subtract 255 (hex FF) from it. Or, equivalently, just drop the first digit (which will always be 1) and add one to what's left.

   (Technically, if the sum happens to equal FF, we should also replace it with zero. But we can ignore that special case and instead just add an extra entry into the bottom right corner of the antilogarithm table, as I have done above.)

   Continuing the example above, F4 + E2 equals 1D6. (If you can't easily do hexadecimal addition in your head, you may want to also print out a table for it.) Since this is a three-digit number, we drop the first digit and add 1, giving D6 + 1 = D7.

4. Finally, look up the result of the previous step in the antilogarithm table (i.e. the second table, labeled exp, above). This is the result of the multiplication.

   For example, looking at row D_ and column _7 in the second table above, we find that the antilogarithm of D7 (and thus the product of 84 and 5A) in the AES field is 91.

BTW, if you're worried about making mistakes in the table lookups (e.g. looking in the wrong row or column), a useful property of the two tables above is that they are (by definition) inverses of each other. Thus, you can verify a log table lookup by looking the result up in the exp table and checking that you get the original number back, and vice versa.

(The one minor exception to this symmetry is the extra entry for exp(FF) = exp(00) that I included in the exp table for convenience. If you look up FF in the exp table, you get 01, for which the log table gives the canonical logarithm 00.)

You also can use these tables for Galois field division (i.e. multiplication by inverse) by replacing the addition in step 3 above by subtraction (and adding 255 = FF to the result if it's negative). And, of course, if you want to calculate the AES Galois field inverse of a number, you can do that by dividing 01 with it. Or, equivalently, just look up its logarithm, subtract it from FF, and look up the antilogarithm of the result.

Answer 2

Let's multiply 0x84 and 0x5a using keyboard and monitor (paper and pen works the same):

Converting into binary you can do digit by digit independently and should get 10000100 and 01011010.

The minimal polynomial taken for the field with 256 elements is 0x11b for AES. You should read that as a bit in the position of $2^8$ is the same as 0x1b = 00011011 binary.

The first step is to create a multiplication table for one of the factors, let's say 0x84. The first row is the number in binary. From row to row you just append a zero, and drop the first digit (shifting all other digits one to the left). But if the first digit is 1 (corresponding to $2^8$ or $X^8$, if you remember that we do polynomial multiplication modulo the AES-polynomial), then you have to add 0x1b = 00011011. Adding is without carries, i.e., xor. You stop as soon you have 8 rows, as we work with 8-bit values.

10000100
00001000 + 00011011 = 00010011
00100110
01001100
10011000
00110000 + 00011011 = 00101011
01010110
10101100

If you've written down maybe two or three multiplication tables then the time it takes to write down such a table is limited by your typing/writing speed. Not much brain activity is needed for the arithmetic.

Now look at the binary representation of the other factor 0x5a = 01011010. Each of its digit corresponds to a row of the table: The last digit to the first row, the 2nd last to the second, and so on. Cross out every row that corresponds to a digit 0, and add up each row that corresponds to a digit 1 (sorry that 5a is symmetric, for 5b = 01011011 the first row would have a 1 in front):

0: 10000100
1: 00001000 + 00011011 = 00010011
0: 00100110
1: 01001100
1: 10011000
0: 00110000 + 00011011 = 00101011
1: 01010110
0: 10101100

As I don't know how to cross out here, I just copied the rows with a 1 at the beginning and added up each column writing the result below the line. Adding is again without carry: Write 0 if you see an even number of 1s above, and 1 if it's an odd number of 1s in the column.

00010011
01001100
10011000
01010110
--------
10010001

Convert to hex 10010001 = 0x91 to get the same result as Ilmari with his logarithm tables.

If you multiply several times with the same number, of course you can recycle the multiplication tables.