BitShifting с BigIntegers в Java - PullRequest
Новая
       27

BitShifting с BigIntegers в Java

7 голосов
/ 28 апреля 2010

Я реализую шифрование DES в Java с использованием BigIntegers.

Я сдвигаю двоичные ключи с помощью Java BigIntegers с помощью метода BigInteger.leftShift (int n).Ключ N (Kn) зависит от результата сдвига Kn-1.Проблема, которую я получаю, заключается в том, что я распечатываю результаты после генерации каждого ключа, а сдвиг не является ожидаемым результатом.Ключ разделен на 2 Cn и Dn (слева и справа соответственно).

Я специально пытаюсь это сделать: «Чтобы сделать сдвиг влево, переместите каждый бит на одну позицию влево, за исключением первого бита,который зацикливается до конца блока. "

В зависимости от сдвига кажется, что он прибавляет O на конце.Не знаете, как это исправить.

Результаты:

c0: 11110101010100110011000011110

d0: 11110001111001100110101010100

c1: 11110101010100110011000011d1: +111100011110011001101010101000

с2: 11110101010100110011000011110000

d2: 11110001111001100110101010100000

с3: 1111010101010011001100001111000000 * 1 023 *

d3: 1111000111100110011010101010000000

* +1026 * с4: 111101010101001100110000111100000000 * тысяча двадцать-семь* * 1 028 * d4: 111100011110011001101010101000000000

с5: 11110101010100110011000011110000000000

d5: 11110001111001100110101010100000000000

с6: 1111010101010011001100001111000000000000

d 6: 1111000111100110011010101010000000000000

с7: 111101010101001100110000111100000000000000

d7: 111100011110011001101010101000000000000000

c8: 1111010101010011001100001111000000000000000

0101 11111100000101110000000000000000

* +1046 * с9: 111101010101001100110000111100000000000000000

D9: 111100011110011001101010101000000000000000000 * +1049 *

с10: 11110101010100110011000011110000000000000000000

D10: 11110001111001100110101010100000000000000000000 * 1 053 *

C11: 1111010101010011001100001111000000000000000000000

d11: 1111000111100110011010101010000000000000000000000

c12: 111101010101001100110000111100000000000000000000000

d12: 111100011110011001101010101000000000000000000000000

c13: 11110101010100110011000011110000000000000000000000000

d13: 11110001111001100110101010100000000000000000000000000

c14: 1111010101010011001100001111000000000000000000000000000

d14: 1111000111100110011010101010000000000000000000000000000

c15: 11110101010100110011000011110000000000000000000000000000

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Ответы [ 4 ]

10 голосов
/ 28 апреля 2010

BigInteger реализует целые числа с бесконечной точностью, поэтому сдвиг влево продолжит добавлять нули влево. Вам нужно повернуть: 

private static BigInteger rotateLeft(BigInteger bi) {
    BigInteger ret = bi.shiftLeft(1);
    if (ret.testBit(32)) {
        ret = ret.clearBit(32).setBit(0);
    }
    return ret;
}

Это будет довольно неэффективно для 32-битных чисел, так что вы могли бы просто использовать примитивы для вращения 28-битных половин DES. Я не знаком с алгоритмом DES, поэтому предположу, что вам нужен BigInteger для чего-то другого. 

private static BigInteger rotateLeftPrimitive(BigInteger bi) {
    int value = bi.intValue();
    return BigInteger.valueOf(((value << 1) & 0xffffffe) | ((value >>> 27) & 1));
}
4 голосов
/ 28 апреля 2010

Похоже, вам нужен циклический сдвиг влево. BigInteger.shiftLeft не является циклическим. Вам нужно будет объединить shiftLeft, shiftRight, and и or, как если бы вы использовали int и <<. 

static BigInteger allOnes(int L) {
    return BigInteger.ZERO
        .setBit(L)
        .subtract(BigInteger.ONE);
}

static BigInteger cyclicLeftShift(BigInteger n, int L, int k) {
    return n.shiftLeft(k)
        .or(n.shiftRight(L - k))
        .and(allOnes(L));
}

Теперь cyclicLeftShift(n, L, k) возвращает n циклически сдвинутых k битов влево, где окно цикла равно L.

Как это работает следующим образом: 

                               _________L__________
                              /                    \
n :                           [ABCDE][FG...........]
                              \__k__/\_____L-k_____/



n.shiftLeft(k) :       [ABCDE][FG...........][00000]
   .or
n.shiftRight(L - k) :                        [ABCDE]

   =                   [ABCDE][FG...........][ABCDE]

                               _________L__________
   .and                       /                    \
allOnes(L) :                  [111..............111]

   =                          [FG...........][ABCDE]

Смотри также

Примечание : если у вас фиксированный L, вы можете немного оптимизировать его, кэшируя allOnes(L) вместо того, чтобы вычислять его каждый раз.

1 голос
/ 28 апреля 2010

Решение более крупного вопроса 1) DES не работает и никогда не должен использоваться ни для чего, кроме работы с устаревшими системами, 2) Sun JCE уже предоставляет реализацию (как это делает BouncyCastle и другие поставщики криптографии), и 3) реализует любые Криптоалгоритм сложен, и вы действительно хотите использовать хорошо протестированную реализацию для производственного использования.

Если это классное упражнение, я бы использовал байт [] вместо BigInteger. Вам нужно будет сделать немного больше вручную, но это намного ближе к духу DES, так как оно было разработано так, чтобы его можно было легко реализовать на аппаратном уровне.

0 голосов
/ 29 апреля 2010

Я думаю, что ваша идея реализации DES с использованием битовых строк является разумной в качестве учебного пособия. Вместо непосредственного использования BigIntegers для представления этих битовых строк, я рекомендую вам создать класс BitString, который реализует именно те методы битовых строк, которые необходимы для вашего проекта. Внутри класса BitString вы можете использовать BigIntegers, но вы можете обнаружить, что простой массив int с 1 битом на элемент массива такой же легкий или простой, или, возможно, связанный список.

...