Passage - 3 months ago 14

Java Question

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)`

`Integer.toBinaryString(int n)`

Given an input of

`(0x0000ef00, 2)`

`toBitString(0x0000ef00)`

With the above inputs, the value of ns is

`1110111100000000`

`result`

`111101110`

`ns`

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