Skip to main content
Cryptography

Return to Answer

typo
Source Link
Ilmari Karonen
Ilmari Karonen
  • 46.5k
  • 5
  • 111
  • 187

  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 8384 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.

  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 83 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.

  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.

deleted 4 characters in body
Source Link
Ilmari Karonen
Ilmari Karonen
  • 46.5k
  • 5
  • 111
  • 187

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 (withusing 3 as the generatorbase), generated using this Python code:

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 (with 3 as the generator), generated using this Python code:

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:

Source Link
Ilmari Karonen
Ilmari Karonen
  • 46.5k
  • 5
  • 111
  • 187

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 (with 3 as the generator), 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 83 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.