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;
}