java - Java 中的 DES 实现 : Error during Key Generation Phase

Question

我是一名学生，正在做一个小项目 - DES 实现。
我之前对将 64 位 key 转换为 56 位 key 有疑问，多亏了这里收到的一些指导，我可以成功地做到这一点。

我将我的实现分为 key 生成阶段(我为 16 轮中的每一轮生成一个新 key )和加密阶段。

但是，我无法生成正确的 key 。
我使用“abcdefgh”作为键手动做了一个例子，但我无法在我的程序中重现结果。

DES key 生成阶段包括:

将 56 位 key 划分为 2 个 28 位 key 。我将 4 个字节中的 28 位存储为 leftkey28[4] (最后 4 位为 0) & rightkey28[4] (前 4 位为 0)

这些 28 位组使用 (<< 1 & << 2 在原始算法中进行左循环移位，然后组合以获得新的 56 位 key )。但是，因为这个问题，我暂时放弃了左移2，只左循环了1。仍然，这个问题的根源是无法追踪的。

问题似乎在行 Round#2 Byte#2在我的输出中。

对于找出根本原因的任何指导或提示，我将不胜感激。
(
附言我以前从来没有做过这么多的位操作!
代码没有根据 Java 规则/约定进行优化或编写，因为我只是想让它在做任何其他事情之前工作
)

提前致谢。

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;

/**
 * @author krish 2nd Aug, 2011
 */

    class DES {

final static int KEY_LENGTH = 8; // 8 byte key, 64 bits
final static int BLOCK_SIZE = 8; // 8 byte blocks, 64 bits
final static int NUM_ROUNDS = 16; // 16 rounds per block

// =======================================================================
// FOR KEY TRANSFORMATION
int[] compressionPermutation = { 14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21,
        10, 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2, 41, 52, 31, 37, 47,
        55, 30, 40, 51, 45, 33, 48, 44, 49, 39, 56, 34, 53, 46, 42, 50, 36,
        29, 32 };

// int[] keyShiftValue = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 };
// ---
// don't need this
// =======================================================================

public static void main(String[] args) {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    System.out.println("Enter an 8 char key: ");
    String inputKey, inputMsg;
    char[] inputArray;
    byte[] key64 = new byte[8];
    byte[] key56 = new byte[7];
    int counter;

    try {
        // get key, key length() >= 8 chars

        // inputKey = br.readLine();// uncomment later!!$$$$$$$
        inputKey = "abcdefgh";
        System.out.println(inputKey);
        if (inputKey.length() < 8) {
            System.out.println("Key < 8 B. Exiting. . .");
            System.exit(1);
        }
        // java char has 16 bits instead of 8 bits as in C,
        // so convert it to 8 bit char by getting lower order byte &
        // discarding higher order byte; &
        // consider only first 8 chars even if input > 8
        inputArray = inputKey.toCharArray();
        for (counter = 0; counter < 8; counter++)
            key64[counter] = (byte) inputArray[counter];

        // converting 64bit key to 56 bit key
        for (counter = 0; counter < KEY_LENGTH - 1; counter++) {
            key64[counter] = (byte) (key64[counter] >>> 1);
            key64[counter] = (byte) (key64[counter] << 1);
        }
        for (counter = 0; counter < KEY_LENGTH - 1; counter++) {
            key56[counter] = (byte) (key64[counter] << counter);
            key56[counter] = (byte) (key56[counter] | (key64[counter + 1] >>> (KEY_LENGTH - 1 - counter)));
        }
        /*
         * Conversion from 64 to 56 bit testing code
         * 
         * System.out.println("64 to 56 test:"); System.out.println(new
         * String(key56)); System.out.println(); for (int counter1 = 0;
         * counter1 < 7; counter1++) { for (int counter2 = 7; counter2 >= 0;
         * counter2--) { System.out.println(key56[counter1] & (1 <<
         * counter2)); } System.out.println(); }
         */

        // end of obtaining 56bit key

        // KEY GENERATION PHASE
        // DS USED - compressionPermutation

        byte[] leftKey28 = new byte[4];
        byte[] rightKey28 = new byte[4];
        byte circularBit;
        byte[][] newKey56 = new byte[16][7];

        // new 56 bit key for the first round, then loop for other rounds
        leftKey28[0] = key56[0];
        leftKey28[1] = key56[1];
        leftKey28[2] = key56[2];
        leftKey28[3] = (byte) (key56[3] & 11110000);

        // rightKey28[0] = (byte) (key56[3] & 00001111);
        // prob here, doesnt work as given above??
        rightKey28[0] = (byte) (key56[3] - leftKey28[3]);
        rightKey28[1] = key56[4];
        rightKey28[2] = key56[5];
        rightKey28[3] = key56[6];

        /*
         * // printing starts here System.out.print("1 Byte # 0" + "     ");
         * for (int counter2 = 7; counter2 >= 0; counter2--) {
         * System.out.print(leftKey28[0] & (1 << counter2));
         * System.out.print(", "); } System.out.println(); // printing ends
         * here
         */

        circularBit = (byte) (leftKey28[0] & (1 << 7));

        leftKey28[0] = (byte) (leftKey28[0] << 1);
        leftKey28[0] = (byte) (leftKey28[0] | ((((int) leftKey28[1]) & 0xff) >>> 7));

        leftKey28[1] = (byte) (leftKey28[1] << 1);
        leftKey28[1] = (byte) (leftKey28[1] | ((((int) leftKey28[2]) & 0xff) >>> 7));

        leftKey28[2] = (byte) (leftKey28[2] << 1);
        leftKey28[2] = (byte) (leftKey28[2] | ((((int) leftKey28[3]) & 0xff) >>> 7));

        leftKey28[3] = (byte) (leftKey28[3] << 1);
        leftKey28[3] = (byte) (leftKey28[3] | ((((int) circularBit) & 0xff) >>> 3));

        circularBit = (byte) (rightKey28[0] & (1 << 3));
        circularBit <<= 4;

        rightKey28[0] = (byte) (rightKey28[0] << 1);
        rightKey28[0] = (byte) (rightKey28[0] | ((((int) rightKey28[1]) & 0xff) >>> 7));

        rightKey28[1] = (byte) (rightKey28[1] << 1);
        rightKey28[1] = (byte) (rightKey28[1] | ((((int) rightKey28[2]) & 0xff) >>> 7));

        rightKey28[2] = (byte) (rightKey28[2] << 1);
        rightKey28[2] = (byte) (rightKey28[2] | ((((int) rightKey28[3]) & 0xff) >>> 7));

        rightKey28[3] = (byte) (rightKey28[3] << 1);
        rightKey28[3] = (byte) (rightKey28[3] | ((((int) circularBit) & 0xff) >>> 3));

        newKey56[0][0] = leftKey28[0];
        newKey56[0][1] = leftKey28[1];
        newKey56[0][2] = leftKey28[2];
        newKey56[0][3] = (byte) (leftKey28[3] | rightKey28[0]);
        newKey56[0][4] = rightKey28[1];
        newKey56[0][5] = rightKey28[2];
        newKey56[0][6] = rightKey28[3];
        // we have a new left circular shifted key in newKey56

        // done testing for newkey56[0] // left and right testing code
        for (int counter1 = 0; counter1 < 7; counter1++) {
            System.out.print("Round#0 Byte#" + counter1 + "  ");
            for (int counter2 = 7; counter2 >= 0; counter2--) {
                if (counter2 == 3)
                    System.out.print("   ");
                if ((newKey56[0][counter1] & (1 << counter2)) > 0) {
                    System.out.print("1");
                } else {
                    System.out.print("0");
                }
            }
            System.out.println();
        }
        // left and right testing code ends here

        // for round 1 to 15: left circular shift each 28 bit block by 1{
        for (int round = 1; round < NUM_ROUNDS; round++) {
            // for the first round, then loop for other rounds
            leftKey28[0] = newKey56[round - 1][0];
            leftKey28[1] = newKey56[round - 1][1];
            leftKey28[2] = newKey56[round - 1][2];
            leftKey28[3] = (byte) (newKey56[round - 1][3] & 11110000);

            // rightKey28[0] = (byte) (newKey56[round - 1][3] & 00001111);
            rightKey28[0] = (byte) (newKey56[round - 1][3] - leftKey28[3]);
            rightKey28[1] = newKey56[round - 1][4];
            rightKey28[2] = newKey56[round - 1][5];
            rightKey28[3] = newKey56[round - 1][6];

            // if (round == 1 || round == 8 || round == 15) {
            // left circular shift by 1
            circularBit = (byte) (leftKey28[0] & (1 << 7));

            leftKey28[0] <<= 1;
            leftKey28[0] |= ((((int) leftKey28[1]) & 0xff) >>> 7);

            leftKey28[1] <<= 1;
            leftKey28[1] |= ((((int) leftKey28[2]) & 0xff) >>> 7);

            // ////////////////////////error here ////////////////////////////
            leftKey28[2] <<= 1;
            leftKey28[2] |= ((((int) leftKey28[3]) & 0xff) >>> 7);
            // ////////////////////////error here //////////////////////////

            leftKey28[3] <<= 1;
            leftKey28[3] |= ((((int) circularBit) & 0xff) >>> 3);

            circularBit = (byte) (rightKey28[0] & (1 << 3));
            circularBit <<= 4;

            // //////////////////////////////////////////////////
            rightKey28[0] = (byte) (rightKey28[0] << 1);
            rightKey28[0] &= 00001111;
            rightKey28[0] = (byte) (rightKey28[0] | ((((int) rightKey28[1]) & 0xff) >>> 7));
            // //////////////////////////////////////////////////

            rightKey28[1] = (byte) (rightKey28[1] << 1);
            rightKey28[1] = (byte) (rightKey28[1] | ((((int) rightKey28[2]) & 0xff) >>> 7));

            rightKey28[2] = (byte) (rightKey28[2] << 1);
            rightKey28[2] = (byte) (rightKey28[2] | ((((int) rightKey28[3]) & 0xff) >>> 7));

            rightKey28[3] = (byte) (rightKey28[3] << 1);
            rightKey28[3] = (byte) (rightKey28[3] | ((((int) circularBit) & 0xff) >>> 7));
            // } else {
            // // left circular shift by 2
            // }

            newKey56[round][0] = leftKey28[0];
            newKey56[round][1] = leftKey28[1];
            newKey56[round][2] = leftKey28[2];
            newKey56[round][3] = (byte) (leftKey28[3] | rightKey28[0]);
            newKey56[round][4] = rightKey28[1];
            newKey56[round][5] = rightKey28[2];
            newKey56[round][6] = rightKey28[3];

            // testing code for all keys for rounds 1 to 15
            System.out.println();
            for (int counter1 = 0; counter1 < 7; counter1++) {
                System.out.print("Round#" + round + "  Byte#" + counter1
                        + "  ");
                for (int counter2 = 7; counter2 >= 0; counter2--) {
                    if (counter2 == 3)
                        System.out.print("   ");
                    if ((newKey56[round][counter1] & (1 << counter2)) > 0) {
                        System.out.print("1");
                    } else {
                        System.out.print("0");
                    }

                }
                System.out.println();
            }
            if (round == 2)
                break;
            // testing code ends

        }// for loop ends

        /*
         * // newKey56 testing code
         * System.out.println("new56key testing here"); for (counter = 0;
         * counter < NUM_ROUNDS; counter++) { System.out.println(new
         * String(newKey56[counter])); System.out.println();
         * 
         * for (int counter1 = 0; counter1 < 7; counter1++) {
         * System.out.print("Round # " + counter + " Byte # " + counter1 +
         * "     "); for (int counter2 = 7; counter2 >= 0; counter2--) {
         * System.out.print(newKey56[counter][counter1] & (1 << counter2));
         * System.out.print(", "); } System.out.println(); } }
         */

        // DO KEY COMPRESSION ROUTINE HERE

    } catch (Exception e) {
        e.printStackTrace();
    }
}
    }

    Enter an 8 char key: 
    abcdefgh
    Round#0 Byte#0  1100   0001
    Round#0 Byte#1  1000   1011
    Round#0 Byte#2  0001   0110
    Round#0 Byte#3  0100   1100
    Round#0 Byte#4  1001   1001
    Round#0 Byte#5  1011   0011
    Round#0 Byte#6  0110   1000

    Round#1  Byte#0  1000   0011
    Round#1  Byte#1  0001   0110
    Round#1  Byte#2  0010   1100
    Round#1  Byte#3  1001   1001
    Round#1  Byte#4  0011   0011
    Round#1  Byte#5  0110   0110
    Round#1  Byte#6  1101   0001

    Round#2  Byte#0  0000   0110
    Round#2  Byte#1  0010   1100
    Round#2  Byte#2  0101   1000 //error here => 0101 1001
    Round#2  Byte#3  0011   0000 //error here => 0011 0010
    Round#2  Byte#4  0110   0110
    Round#2  Byte#5  1100   1101
    Round#2  Byte#6  1010   0011

Answer 1

DES 的约定是假装你有 64 位 key (8 个字节)，但如果你真的，呃，迂腐，你用前 7 位的奇偶校验破坏每个字节的第 8 位。

我只玩过 Java，而且我看到 Java(Sun/Oracle JRE)不会费心检查奇偶校验。它只是忽略每个字节的第 8 位。

也许是 DESEngine在 BouncyCaSTLe 中会对您有所帮助。 generateWorkingKey()方法看起来很有趣:

http://www.bouncycastle.org/viewcvs/viewcvs.cgi/java/crypto/src/org/bouncycastle/crypto/engines/DESEngine.java?view=markup