Passage Passage - 20 days ago 6
Java Question

What is wrong with this implementation of bitwise multiplication?

I am attempting to implement a method for bitwise multiplication in Galois Field 256 for the sake of building an implementation of AES. My current multiplication method is as follows:

public static int multiplyPolynomials(int n, int m)
{
int result = 0x00000000;
String ns = toBitString(n);
String ms = toBitString(m);

for (int i = 0; i < ns.length(); i++)
{
if (ns.charAt(i) == '1')
{
/*
* If there's a 1 at place i, add the value of m left-shifted i places to the result.
*/
int temp = m;
for (int j = 0; j < i; j++) { temp = temp << 1; }
result += temp;
}
}
return result;
}


The
toBitString(int n)
method is purely a shortcut for
Integer.toBinaryString(int n)
.

Given an input of
(0x0000ef00, 2)
, the output of this function is 494 (should be 478). Printing a direct call to
toBitString(0x0000ef00)
confirms that the output of that function is as expected (in this case, 1110111100000000). If the first input is shifted one byte to the right (0x000000ef) the output is still 494.

With the above inputs, the value of ns is
1110111100000000
and the bit-string equivalent of
result
is
111101110
.
ns
is thus correct.

What is the error in the method above?

Answer

You are reading the binary string the wrong way round.

Try this...

public static int multiplyPolynomials(int n, int m) {
    int result = 0x00000000;
    String ns = Integer.toBinaryString(n);

    for (int i = 0; i < ns.length(); i++) {
        // Read the string the other way round...
        int bitIndex = (ns.length() - i) - 1;
        if (ns.charAt(bitIndex) == '1') {
            /*
             * If there's a 1 at place i, add the value of m left-shifted i
             * places to the result.
             */
            int temp = m;
            // Don't need a loop here, just shift it by "i" places
            temp = temp << i;
            result += temp;
        }
    }
    return result;
}

Instead of turning the number into a binary string, you could use something like this instead...

public static int multiplyPolynomials(int n, int m) {
    int result = 0x00000000;

    for (int i = 0; i < 32; i++) {
        int mask = 1 << i;

        if ((n & mask) == mask) {
            result += m << i;
        }
    }
    return result;
}

You might need to store your answer as a long to prevent overflows and it probably won't work too well with negative numbers...