Calculating Multiplicative Inverse for Rijndael S-box using EEA

Question

I am currently learning, and I'm stuck on something that I thought is very simple. On many academic sources they suggest using Extended Euclidean Algorithm to calculate the multiplicative inverse for calculation of the S-Box, but I could not find a proper explanation how to do that. Every practical approach calculates log+antilog and uses that. But I'm stubborn and I want to use EEA!

I got my algorithm from here: https://www.youtube.com/watch?v=fq6SXByItUI

For my calculations I used values 0xCA and 0x53. When I multiply them using the Rijndael finite-field multiplication I get 1. So I know that they are each others inverses. But when I put them inside EEA I get a different value :(

0x53 = 83
0xCA = 202
0x11B = 283 (Rijndael Plynomial)

283 = 3 * 83 + 43   |   34 = (1) * 283 + (-3) * 83
 83 = 2 * 43 + 15   |   15 = (-2) * 283 + (7) * 83
 34 = 2 * 15 + 4    |   4 = (5) * 283 + (-17) * 83
 15 = 3 * 4 + 3     |   3 = (-17) * 283 + (58) * 83
  4 = 1 * 3 + 1     |   1 = (22) * 283 + (-75) * 83

The final result is correct according to google calculator.

When I use modulo 283 on both sides I get:

1 = (-75) * 83 = (283 - 75) * 83 = 208 * 83

So I got 208 instead of 202!

My experimental implementation of this procedure is here.

public static int RijndaelInverse(int a)
{
    int old_s = 0; int s = 1; int new_s = 0;
    int old_t = 0; int t = 0; int new_t = 1;
    int old_r = 0x11B; int r = 0x11B; int new_r = a;

    while (new_r > 0)
    {
        int quotient = r / new_r;

        old_s = s;
        s = new_s;
        new_s = old_s - quotient * s;

        old_t = t;
        t = new_t;
        new_t = old_t - quotient * t;

        old_r = r;
        r = new_r;
        new_r = old_r - quotient * r;
    }

    if (r > 1) return 0;
    if (t < 0) t = t + 0x11B;

    return t;
}

I tried substituting the multiplication with RijndaelMultiply and subtraction with RijndaelSubtract but that broke the whole algorithm and gave me crazy values. I think it's because the algorithm requires negative values to work, and there is no easy way of dividing polynomials that I know of.

Does anyone know how to correctly use EEA with Rijndael finite-field?

---

[EDIT] Working implementation

public static uint RijndaelInverse(uint a)
{
    uint old_s = 0; uint s = 1; uint new_s = 0;
    uint old_t = 0; uint t = 0; uint new_t = 1;
    uint old_r = 0x11B; uint r = 0x11B; uint new_r = a;

    while (new_r > 0)
    {
        var r_msb = (int)Math.Log(r, 2.0);
        var new_r_msb = (int)Math.Log(new_r, 2.0);

        int quotient = r_msb - new_r_msb;

        if (quotient >= 0)
        {
            old_s = s;
            s = new_s;
            new_s = old_s ^ (s << quotient);

            old_t = t;
            t = new_t;
            new_t = old_t ^ (t << quotient);

            old_r = r;
            r = new_r;
            new_r = old_r ^ (r << quotient);
        }
        else
        {
            new_s = s ^ new_s;
            s = s ^ new_s;
            new_s = s ^ new_s;

            new_t = t ^ new_t;
            t = t ^ new_t;
            new_t = t ^ new_t;

            new_r = r ^ new_r;
            r = r ^ new_r;
            new_r = r ^ new_r;
        }
    }

    if (r > 1) return 0;

    if (t > 0xFF) t ^= 0x11B;

    return t;
}

Answer 1

To do EEA on a finite-field, you can't perform the operations using the operations in the ring of the integers (and they're not precisely the same operations in the field either, as you're working with bit vectors, not field elements). In particular:

• When you do "addition", you need to perform the addition as done in even characteristic fields (that is, you actually do an exclusive-or).

• "Subtraction" is actually the same as "addition", so you use exclusive-or for that as well. Yes; addition and subtraction are the same thing; we're not in Kansas anymore.

• The "multiplication operation" is actually a bit shift, as so we would have something like:

  new_r = old_r ^ (r << quotient);
  

  What you want is to have (r << quotient) cancel out the msbit of old_r; To make this work, your 'divide' operation needs to effective compute how far the r needs to be shifted left so that the exclusive-or will cancel out the msbit (and hence reduce the size of r).

• The test at the bottom (if t is out of range) looks differently. It turns out (with the above changes) t will never be negative; it might be larger than 255

The Extended Euclidean algorithm can be made to work. On the other hand, I'm having a hard time seeing a situation where it is a best algorithm for this job. It's not nearly as fast as a simple table lookup, and it's not even slightly side channel resistant.