1
$\begingroup$

I'm trying to do a hexadecimal multiplication in GF(2^8). Now, I know the technique of shifting left the binary numbers in some cases, for example:

02 * 9E 0000 0010 * 1001 1110

you shift one time the 9E part, which results in the following: 0011 1100 and since it went above x^8, you must calculate the XOR operation with the Irreducible polynomial x^8 + x^4 + x^3 + x

and the result would be 0010 0110

I know how many spaces to shift when the first polynomial is a simple one, like 0010 or 0100, but how about when it is a little more complex? Such as 0111 or 1011?? Hoy many spaces must i shift it?

0111 = 7, so i shift 7 times? or 2 because the greates expoent in the polynomial is 2??

Your help would be very much appreciated!

$\endgroup$
2
$\begingroup$

You cannot use (just) a bit shift to multiply by $7$. Not in ${\rm GF}(2^n)$, and not in normal arithmetic either.

Shifting a number left by one bit always multiplies it by two, and shifting a number left by multiple bits is just equivalent to shifting it left by one bit several times. So shifting a number left (by one or more bits) always multiplies it by a power of two.

To multiply a number by a factor that is not a power of two, you need both shifting and addition (which in ${\rm GF}(2^n)$ is actually bitwise XOR). For example, $7 = 111_2 = 4 + 2 + 1$, so $7a = 4a + 2a + a$ for any $a$. So, to multiply some number $a$ by $7$, you can first calculate $2a$ and $4a$ by shifting $a$ left, and then add those together with $a$ itself (always remembering that, in ${\rm GF}(2^n)$, addition is actually XOR and that any results with more than $n$ bits will need to be reduced modulo the field polynomial).

More generally, we can do general multiplication in ${\rm GF}(2^n)$ by splitting one of the numbers being multiplied into a sum of powers of two (which is really easy if we're working on a binary computer), use bit shifting (and modular reduction) to multiply the other number by those powers of two, and then add the results together. Here's some pseudo-C code to illustrate this:

const int overflow = 0x100, modulus = 0x11B;  // AES GF(2^8) representation

int gf2n_multiply(int a, int b) {
    int sum = 0;
    while (b > 0) {
        if (b & 1) sum = sum ^ a;             // if last bit of b is 1, add a to the sum
        b = b >> 1;                           // divide b by 2, discarding the last bit
        a = a << 1;                           // multiply a by 2
        if (a & overflow) a = a ^ modulus;    // reduce a modulo the AES polynomial
    }
    return sum;
}

Note that you could easily turn the code above into a normal integer multiplication routine by replacing sum ^ a with sum + a and removing the last line in the while loop that reduces a modulo the AES polynomial after it has been shifted left. Those are the only ways in which Galois field arithmetic, as used in this code, differs from normal integer arithmetic.

Also note that, while the code above should work (in the sense of producing the correct results), it's probably not something you should use in production crypto code. Not only is it not particularly well optimized, but its running time depends on the value of b, which is generally not desirable if b might contain sensitive data that you don't want to leak.

(BTW, at this point you might be wondering if it wouldn't be more efficient, for example, to calculate $7a$ as $8a - a$ instead. Unfortunately, while that would work fine in normal integer arithmetic, addition and subtraction in ${\rm GF}(2^n)$ work differently, and we actually have $8 - 1 = 8 + 1 = 9 \ne 7$. But adding together distinct powers of two still works the same way in ${\rm GF}(2^n)$ as it does with normal integers, so we can still usefully work with the binary representation of numbers.)

$\endgroup$
-1
$\begingroup$

I think you are trying to do the Mix Columns step of AES which involves multiplication in GF(2^8).

Please refer the the steps shown here using the peasant's method.

I know it should have been a comment but I do not have enough reputation to do so.

$\endgroup$
-1
$\begingroup$

Although the numbers are usually displayed in hexadecimal they are processes in binary. The elements of $GF(2^8)$ are represented as polynomials with coefficients from $\mathbb{Z}_2$.

The old school method is multiplying the polynomials representation and perform reduction with an irreducible polynomial. In AES it is given 0x1b in hex representation of the polynomial.

The below referenced C code is much better and you can see it in the implementations.

uint8_t  gmul(uint8_t  a, uint8_t  b)
{
    uint8_t p=0;
    uint8_t carry;
    int i;
    for(i=0;i<8;i++)         {
        if(b & 1)
            p ^=a;
        carry = a & 0x80;
        a = a<<1;
        if(carry)
            a^=0x1b;
        b = b>>1;
    }
    return p;
}

As seen from the code, shifting always occur. If there is a carry, we perform $\oplus 0x1b;$

The amount of shifting without $\oplus 0x1b;$ depends on the input. In code, testing this is not cheap than the above implementation.


Here, I used the code above to show the sequence of operations.

  • b1. means p^=a
  • ca. means a^=0x1b;
  • as. means a<<1;
  • bs. means b<<1;
  • | means iteration step;

From your examples;

[a= 2;b= 9e] [sa.bs.|b1.sa.bs.|b1.sa.bs.|b1.sa.bs.|b1.sa.bs.|sa.bs.|sa.ca.bs.|b1.sa.bs.|]
[a= 7;b= 9e] [sa.bs.|b1.sa.bs.|b1.sa.bs.|b1.sa.bs.|b1.sa.bs.|sa.ca.bs.|sa.ca.bs.|b1.sa.ca.bs.|]

let swap(a,b)

[a= 9e;b= 7] [b1.sa.ca.bs.|b1.sa.bs.|b1.sa.bs.|sa.ca.bs.|sa.bs.|sa.bs.|sa.ca.bs.|sa.bs.|]
[a= 9e;b= 2] [sa.ca.bs.|b1.sa.bs.|sa.bs.|sa.ca.bs.|sa.bs.|sa.bs.|sa.ca.bs.|sa.bs.|]

As you can see, there is no generic shift method here.

The Wikipedia code much simpler and faster for the Mix-Cols operation that hides the if's.

$\endgroup$

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.