这种按位乘法的实现有什么问题? [英] What is wrong with this implementation of bitwise multiplication?

问题描述

为了构建AES的实现，我正在尝试在Galois字段256中实现一种按位乘法的方法.我当前的乘法方法如下:

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

toBitString(int n)方法纯粹是Integer.toBinaryString(int n)的快捷方式.

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

给出(0x0000ef00, 2)的输入，此函数的输出为494(应为478).打印直接调用toBitString(0x0000ef00)确认该函数的输出符合预期(在这种情况下为1110111100000000).如果第一个输入向右移动一个字节(0x000000ef)，则输出仍为494.

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.

使用上面的输入，ns的值是1110111100000000，result的位串等效项是111101110.因此ns是正确的.

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?

推荐答案

您正在以错误的方式读取二进制字符串.

You are reading the binary string the wrong way round.

尝试一下...

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

这篇关于这种按位乘法的实现有什么问题?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！