title: DES Implementation in Java: Error during Key Generation Phase
body: <p>I am a student doing a mini-project - DES implementation.
  I had a doubt previously about converting a 64 bit key to 56 bit key, and could do that successfully, thanks to some guidance received here.</p>
  
  <p>I have divided my implementation into the key-gen phase (where I generate a new key for each of the 16 rounds) and the encryption phase.</p>
  
  <p>However, I am not able to generate the correct keys.
  I did an example manually using "abcdefgh" as key and I am not able to reproduce the results in my program.</p>
  
  <p>The DES keygen phase involves:</p>
  
  <ol>
  <li><p>Dividing 56-bit key into 2 28 bit keys. I store 28 bits in 4 bytes as <code>leftkey28[4]</code> (which has the last 4 bits as 0) &amp; <code>rightkey28[4]</code> (which has the first 4 bits as 0)</p></li>
  <li><p>These 28 bit groups are left circular shifted using (&lt;&lt; 1 &amp; &lt;&lt; 2 in the original algorithm and then combined to get a new 56-bit key). However, because of this problem, I scrapped left shifting by 2 for now, and am only left circular shifting by 1. And still, the root of this problem is untraceable.</p></li>
  </ol>
  
  <p>The problem seems to be in the line <code>Round#2 Byte#2</code> in my output.</p>
  
  <p>I will be grateful for any guidance or hints towards finding out the root cause.
  (
  P.S. I have never done so much bit manipulation before!
  The code is not optimized or written according to Java rules/conventions as I just wanted to make it work before doing any other things
  )</p>
  
  <p>Thanks in advance.</p>
  
  <pre><code>    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() &gt;= 8 chars
  
          // inputKey = br.readLine();// uncomment later!!$$$$$$$
          inputKey = "abcdefgh";
          System.out.println(inputKey);
          if (inputKey.length() &lt; 8) {
              System.out.println("Key &lt; 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 &amp;
          // discarding higher order byte; &amp;
          // consider only first 8 chars even if input &gt; 8
          inputArray = inputKey.toCharArray();
          for (counter = 0; counter &lt; 8; counter++)
              key64[counter] = (byte) inputArray[counter];
  
          // converting 64bit key to 56 bit key
          for (counter = 0; counter &lt; KEY_LENGTH - 1; counter++) {
              key64[counter] = (byte) (key64[counter] &gt;&gt;&gt; 1);
              key64[counter] = (byte) (key64[counter] &lt;&lt; 1);
          }
          for (counter = 0; counter &lt; KEY_LENGTH - 1; counter++) {
              key56[counter] = (byte) (key64[counter] &lt;&lt; counter);
              key56[counter] = (byte) (key56[counter] | (key64[counter + 1] &gt;&gt;&gt; (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 &lt; 7; counter1++) { for (int counter2 = 7; counter2 &gt;= 0;
           * counter2--) { System.out.println(key56[counter1] &amp; (1 &lt;&lt;
           * 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] &amp; 11110000);
  
          // rightKey28[0] = (byte) (key56[3] &amp; 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 &gt;= 0; counter2--) {
           * System.out.print(leftKey28[0] &amp; (1 &lt;&lt; counter2));
           * System.out.print(", "); } System.out.println(); // printing ends
           * here
           */
  
          circularBit = (byte) (leftKey28[0] &amp; (1 &lt;&lt; 7));
  
          leftKey28[0] = (byte) (leftKey28[0] &lt;&lt; 1);
          leftKey28[0] = (byte) (leftKey28[0] | ((((int) leftKey28[1]) &amp; 0xff) &gt;&gt;&gt; 7));
  
          leftKey28[1] = (byte) (leftKey28[1] &lt;&lt; 1);
          leftKey28[1] = (byte) (leftKey28[1] | ((((int) leftKey28[2]) &amp; 0xff) &gt;&gt;&gt; 7));
  
          leftKey28[2] = (byte) (leftKey28[2] &lt;&lt; 1);
          leftKey28[2] = (byte) (leftKey28[2] | ((((int) leftKey28[3]) &amp; 0xff) &gt;&gt;&gt; 7));
  
          leftKey28[3] = (byte) (leftKey28[3] &lt;&lt; 1);
          leftKey28[3] = (byte) (leftKey28[3] | ((((int) circularBit) &amp; 0xff) &gt;&gt;&gt; 3));
  
          circularBit = (byte) (rightKey28[0] &amp; (1 &lt;&lt; 3));
          circularBit &lt;&lt;= 4;
  
          rightKey28[0] = (byte) (rightKey28[0] &lt;&lt; 1);
          rightKey28[0] = (byte) (rightKey28[0] | ((((int) rightKey28[1]) &amp; 0xff) &gt;&gt;&gt; 7));
  
          rightKey28[1] = (byte) (rightKey28[1] &lt;&lt; 1);
          rightKey28[1] = (byte) (rightKey28[1] | ((((int) rightKey28[2]) &amp; 0xff) &gt;&gt;&gt; 7));
  
          rightKey28[2] = (byte) (rightKey28[2] &lt;&lt; 1);
          rightKey28[2] = (byte) (rightKey28[2] | ((((int) rightKey28[3]) &amp; 0xff) &gt;&gt;&gt; 7));
  
          rightKey28[3] = (byte) (rightKey28[3] &lt;&lt; 1);
          rightKey28[3] = (byte) (rightKey28[3] | ((((int) circularBit) &amp; 0xff) &gt;&gt;&gt; 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 &lt; 7; counter1++) {
              System.out.print("Round#0 Byte#" + counter1 + "  ");
              for (int counter2 = 7; counter2 &gt;= 0; counter2--) {
                  if (counter2 == 3)
                      System.out.print("   ");
                  if ((newKey56[0][counter1] &amp; (1 &lt;&lt; counter2)) &gt; 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 &lt; 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] &amp; 11110000);
  
              // rightKey28[0] = (byte) (newKey56[round - 1][3] &amp; 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] &amp; (1 &lt;&lt; 7));
  
              leftKey28[0] &lt;&lt;= 1;
              leftKey28[0] |= ((((int) leftKey28[1]) &amp; 0xff) &gt;&gt;&gt; 7);
  
              leftKey28[1] &lt;&lt;= 1;
              leftKey28[1] |= ((((int) leftKey28[2]) &amp; 0xff) &gt;&gt;&gt; 7);
  
              // ////////////////////////error here ////////////////////////////
              leftKey28[2] &lt;&lt;= 1;
              leftKey28[2] |= ((((int) leftKey28[3]) &amp; 0xff) &gt;&gt;&gt; 7);
              // ////////////////////////error here //////////////////////////
  
              leftKey28[3] &lt;&lt;= 1;
              leftKey28[3] |= ((((int) circularBit) &amp; 0xff) &gt;&gt;&gt; 3);
  
              circularBit = (byte) (rightKey28[0] &amp; (1 &lt;&lt; 3));
              circularBit &lt;&lt;= 4;
  
              // //////////////////////////////////////////////////
              rightKey28[0] = (byte) (rightKey28[0] &lt;&lt; 1);
              rightKey28[0] &amp;= 00001111;
              rightKey28[0] = (byte) (rightKey28[0] | ((((int) rightKey28[1]) &amp; 0xff) &gt;&gt;&gt; 7));
              // //////////////////////////////////////////////////
  
              rightKey28[1] = (byte) (rightKey28[1] &lt;&lt; 1);
              rightKey28[1] = (byte) (rightKey28[1] | ((((int) rightKey28[2]) &amp; 0xff) &gt;&gt;&gt; 7));
  
              rightKey28[2] = (byte) (rightKey28[2] &lt;&lt; 1);
              rightKey28[2] = (byte) (rightKey28[2] | ((((int) rightKey28[3]) &amp; 0xff) &gt;&gt;&gt; 7));
  
              rightKey28[3] = (byte) (rightKey28[3] &lt;&lt; 1);
              rightKey28[3] = (byte) (rightKey28[3] | ((((int) circularBit) &amp; 0xff) &gt;&gt;&gt; 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 &lt; 7; counter1++) {
                  System.out.print("Round#" + round + "  Byte#" + counter1
                          + "  ");
                  for (int counter2 = 7; counter2 &gt;= 0; counter2--) {
                      if (counter2 == 3)
                          System.out.print("   ");
                      if ((newKey56[round][counter1] &amp; (1 &lt;&lt; counter2)) &gt; 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 &lt; NUM_ROUNDS; counter++) { System.out.println(new
           * String(newKey56[counter])); System.out.println();
           * 
           * for (int counter1 = 0; counter1 &lt; 7; counter1++) {
           * System.out.print("Round # " + counter + " Byte # " + counter1 +
           * "     "); for (int counter2 = 7; counter2 &gt;= 0; counter2--) {
           * System.out.print(newKey56[counter][counter1] &amp; (1 &lt;&lt; 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 =&gt; 0101 1001
      Round#2  Byte#3  0011   0000 //error here =&gt; 0011 0010
      Round#2  Byte#4  0110   0110
      Round#2  Byte#5  1100   1101
      Round#2  Byte#6  1010   0011
  </code></pre>