What is wrong with this implementation of bitwise multiplication?

0

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?

java
bit-manipulation
asked on Stack Overflow Nov 17, 2016 by Passage • edited Nov 17, 2016 by Passage

1 Answer

4

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...

answered on Stack Overflow Nov 17, 2016 by BretC • edited Nov 17, 2016 by BretC

User contributions licensed under CC BY-SA 3.0