1
$\begingroup$

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;
}
$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I updated my implementation, and I found another issue I don't know what to do with. Because XOR is the subtraction the value of new_r can be larger then value of r. For example if old_r = 87 and r = 4 the quotient = 4. This gives us new_r = 87 ^ (4 << 4) 87 ^ 64 = 23. During next iteration I have to calculate quotient = msb(4) - msb(23) = -2 Should I shift r right in this case? $\endgroup$ – Filip Franik Jul 7 '15 at 14:43
  • $\begingroup$ @FilipFranik: actually, you can't shift right. Instead, what you need to do in that case is skip that iteration of EEA, reswap r, s, t, and do that again. $\endgroup$ – poncho Jul 7 '15 at 14:51
  • $\begingroup$ Thanks, but I still don't get it. What exactly an I supposed to swap? I tried swapping r with old_r (same for others) and still got wrong results. There is no new_r being calculated so I guess I cannot swap it. Could you please point me towards a book or website that covers this algorithm in "bit vector" approach? $\endgroup$ – Filip Franik Jul 7 '15 at 19:22
  • $\begingroup$ @FilipFranik: try swapping r with new_r, s with new_s and t with new_t. In essence, you're doing the same logic, but with the assumption that r << quotient (and the other shifts by quotient) is 0 $\endgroup$ – poncho Jul 7 '15 at 19:35
  • $\begingroup$ I added that swap, but still my unit tests are still broken. You can see my latest source code above. For a = 83 I end up with t = 465 % 283 = 182 $\endgroup$ – Filip Franik Jul 7 '15 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.