DES알고리즘(+Key Generator) 구현

(포스트에 그림이 없기 때문에 DES의 구조를 전혀 모르신다면 이해하기 어려울 수 있습니다.

위키 등에서 사진자료를 참고하면서 읽어주시면 이해하기 쉽습니다.)

컴퓨터 보안 과목을 수강하면서 DES64 알고리즘을 구현하게 되어 자바로 구현하였습니다.

 

 

DES란 Data Encryption Standard의 약자로써 1974년에 IBM에서 발표한 루시퍼 암호 알고리즘을 미국 NBS에서 개량하여 만든 것이 바로  DES이다.

현재는 암호의 강도가 현시대에 맞지 않아 사용하지는 않지만 공부 목적으로 구현하게 되었습니다.  

 

 

DES는 대칭키 블록암호 시스템으로써 64bit의 평문에 64bit의 키를 이용하여 암호문을 만들어내며 Feista구조를 가지고 있습니다.

이 feistal구조라는 특징 덕분에 복호화 알고리즘이 따로 없고 암호화 알고리즘에 round Key를 반대로 대입시켜 복호화를 진행하게 됩니다.

 

(Permutation - Confusion, Substitution - Diffusion)

DES 알고리즘의 순서로는 

1. 64bit의 평문을 Initial Permutation

2. 이후 16번의 Feistal 구조 Round를 진행합니다.

3. Round 내부 연산은  64bit값을 32bit씩 Left, Right로 나누고 연산을 진행합니다.

4. Right값을 다음의 Left값으로 출력하고 Right값은 연산을 거칩니다.

5. Right값은 Expansion (Permutation) 과정을 통하여 32bi값을 48bit로 늘립니다. 이때 4비트씩 나누어 해당 값의 좌측, 우측 값을 가지고와 6비트로 만들어 48비트로 만들게 됩니다.

6. 48bit로 expansion된 값은 RounKey와 XOR연산을 진행합니다.

7. 그 값을 Substitution (S-Box)를 통하여 32bit로 줄이게 되는데 6비트의 좌우측값을 행, 중간의 4비트 값을 열값으로 사용하여 테이블 값으로 치환하게 됩니다. (ex, 100010이라면 행은 10즉 2, 열은 0001즉 1 S-box의 1행2열의 값으로 치환하여 6비트를 4비트로 만듭니다.)

8. 이렇게 32bit로 치환된 값을 Left값과 XOR연산을 하고 다음의 Right값으로 출력하면 1개의 라운드가 종료됩니다.

9. 위와같은 라운드는 16번의 라운드를 거치고 마지막 Round인 16번째 라운드 종료 후 Left와 Rigth의 값을 교체하여 출력합니다.

10. 마지막으로 Initial Permutation의 반대인 Inverse Initial Permutation 연산을 진행하면 64bit 블럭 Cipher Text가 만들어지게 됩니다.

 

Key Generation 순서로는 

1. 64bit의 키를 Permuted Choice 1과정(8의 배수 번째 값들이 대응되지 않아 없어진다.)을 거치면서 56bit로 줄어들게 됩니다.

2. 56bit의 키를 좌 우로 나누워 28bit 두개로 만들고 Left Shift 연산을 진행한다.

3. Left Shift연산은 1, 2, 9, 16번째 라운드에서는 1번 Left Shift를 진행하고 나머지 라운드에서는 2번 Left Shift를 진행하게 됩니다.

4. 이렇게 만들어진 값은 다음 라운드 키를 생성과 현재 라운드 키를 생성하는데 사용됩니다.

5. 라운드키는 Left right로 나누어진 키를 합치고 Permuted Choice 2연산을 통하여 48bit로 줄어든 값이 Round Key로 사용됩니다.

 

이렇게 DES 64 bit 알고리즘이 구성되고 코드를 보면서 차례차례 알아보도록 하겠습니다.

 

  private final byte[] initialPermutationTable = {58, 50, 42, 34, 26, 18, 10, 2,
                                                    60, 52, 44, 36, 28, 20, 12, 4,
                                                    62, 54, 46, 38, 30, 22, 14, 6,
                                                    64, 56, 48, 40, 32, 24, 16, 8,
                                                    57, 49, 41, 33, 25, 17, 9, 1,
                                                    59, 51, 43, 35, 27, 19, 11, 3,
                                                    61, 53, 45, 37, 29, 21, 13, 5,
                                                    63, 55, 47, 39, 31, 23, 15, 7};
 
 // initial Permutation
    public byte[] initialPermutation(byte[] data){
        byte[] temp = new byte[64];
        for(int i=0; i<temp.length; i++){
            temp[i] = data[this.initialPermutationTable[i]-1];
        }
        return temp;
    }

initialPermutation Table을 이용하여 입력값으로 들어온 data의 값을 섞어줍니다. 
여기서 initialPermutationTable[i]-1을 해준 이유는 테이블 내부의 값이 1부터 시작하여 1을 빼주었습니다.

 

// round 내부 32bit의 right값을 48bit로 expansion
    public byte[] expantion(byte[] right){
        byte[] expentionRight = new byte[48];
        int count = 0;

        for(int i=0; i<48; i++){
            if(i%6 == 0){
                expentionRight[i] = right[ i==0 ? 31 : count-1];
            }else if(i%6 == 5){
                expentionRight[i] = right[ i==47 ? 0 : count];
            }else{
                expentionRight[i] = right[count++];
            }
        }
        return expentionRight;
    }

다음은 32bit의 right값을 48bit로 늘려주는 expansion과정입니다. 

이때 0번째 값의 좌측값은 맨마지막 값이 되고 반대로 맨마지막 값의 우측값은 0번째 값이 되기 때문에 3항연산자를 통하여 구분해주었습니다.

 

// roundKey와 expansion된 right값을 XOR연산
    public byte[] keyXor(byte[] right, byte[] key){
        byte[] result = new byte[48];
        for(int i=0; i<48; i++){
            result[i] = (byte) (right[i]^key[i]);
        }
        return result;
    }

다음은 expansion된 right값과 round Key값을 XOR 해줍니다. (^연산)

 

private final byte[][][] sBox ={
            {
                    {14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7},
                    {0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8},
                    {4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0},
                    {15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13}
            },
            {
                    {15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10},
                    {3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5},
                    {0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15},
                    {13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9}
            },
            {
                    {10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8},
                    {13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1},
                    {13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7},
                    {1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12}
            },
            {
                    {7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15},
                    {13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9},
                    {10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4},
                    {3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14}
            },
            {
                    {2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9},
                    {14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6},
                    {4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14},
                    {11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3}
            },
            {
                    {12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11},
                    {10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8},
                    {9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6},
                    {4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13}
            },
            {
                    {4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1},
                    {13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6},
                    {1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2},
                    {6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12}
            },
            {
                    {13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7},
                    {1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2},
                    {7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8},
                    {2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11}
            }
    };

public byte[] substitution(byte[] right){
        byte[] result = new byte[32];
        int count = 0;
        for(int i = 0 ;i<right.length;i = i+6 ){
            String strCol = String.valueOf(right[i]) + String.valueOf(right[i+5]);
            String strRow = String.valueOf(right[i+1]) + String.valueOf(right[i+2]) + String.valueOf(right[i+3]) + String.valueOf(right[i+4]);
            int col = Integer.parseInt(strCol, 2);
            int row = Integer.parseInt(strRow, 2);


            int s = this.sBox[i/6][col][row];
            String strS = Integer.toBinaryString(s);
            for(int x = strS.length(); x< 4; x++)
                strS = "0" + strS;
            for(int j=0; j<4; j++) {
                result[count++] = Byte.valueOf(String.valueOf(strS.charAt(j)));

            }
        }
        return result;
    }

다음은 48bit 값을 32bit로 줄여주는 substitution과정입니다. 

S-BOX는 총 8개가 있으며 6bit씩 나누어 좌우값을 행으로 중간 4비트를 열값으로 사용하여 sBox[sbox의 순서][행][열] 값을 통해 값을 가져오고 2진수로 변환 후 담아줍니다.

 

private final byte[] permutationTable = {15, 6, 19, 20, 28, 11, 27, 16,
                                            0, 14, 22, 25, 4, 17, 30, 9,
                                            1, 7, 23, 13, 31, 26, 2, 8,
                                            18, 12, 29, 5, 21, 10, 3, 24};

public byte[] permutation(byte[] right){
        byte[] temp = new byte[32];
        for(int i=0; i<temp.length; i++){
            temp[i] = right[this.permutationTable[i]];
        }
        return temp;
    }

이 값을 permutation을 진행하여 줍니다.

 

public byte[] leftXorRight(byte[] left, byte[] right){
        byte[] temp = new byte[32];
        for(int i=0; i<temp.length; i++){
            temp[i] = (byte) (left[i]^right[i]);
        }
        return temp;
    }

마지막으로 Left와 Right값을 XOR 연산해주면 Round가 끝나게 됩니다.

 

public byte[] round(byte[] left, byte[] right, byte[] key){
        byte[] resultLeft = right;

        byte[] expentionRight = this.expantion(right);
        expentionRight = this.keyXor(expentionRight, key);
        right = this.substitution(expentionRight);
        right = this.permutation(right);
        byte[] resultRight = this.leftXorRight(left, right);

        byte[] result = this.addArray(resultLeft, resultRight);

        return result;
    }

위의 과정들을 모아 하나의 Round로 만들어 주었습니다.

 

public byte[] inverseInitialPermutation(byte[] data){
        byte[] temp = new byte[64];
        for(int i=0; i<temp.length; i++){
            temp[this.initialPermutationTable[i]-1] = data[i];
        }
        return temp;
    }

16번의 라운드가 끝나면 Inverse Initial Permutation을 진행하여 Cipher Text를 만들어줍니다.

 

// DES64 암호화를 진행
    public byte[] encryption(byte[] data, byte[] key){
        KeyGenerator keyGenerator = new KeyGenerator();
        byte[][] roundKey = keyGenerator.generateKey(key);
        data = this.initialPermutation(data);


        for(int i=0; i<16; i++){
            byte[] leftData = Arrays.copyOfRange(data, 0, 32);
            byte[] rightData = Arrays.copyOfRange(data, 32, data.length);


            data = round(leftData, rightData, roundKey[i]);
        }
        // 16라운드는 left right 교체 x
        byte[] leftData = Arrays.copyOfRange(data, 0, 32);
        byte[] rightData = Arrays.copyOfRange(data, 32, data.length);
        data = addArray(rightData, leftData);
        data = inverseInitialPermutation(data);
        return data;

    }
    // DES64 복호화를 진행 (key를 반대로 입력)
    public byte[] decryption(byte[] data, byte[] key){
        KeyGenerator keyGenerator = new KeyGenerator();
        int count = 15;
        data = this.initialPermutation(data);
        byte[][] roundKey = keyGenerator.generateKey(key);

        for(int i=0; i<16; i++){
            byte[] leftData = Arrays.copyOfRange(data, 0, 32);
            byte[] rightData = Arrays.copyOfRange(data, 32, data.length);

            data = round(leftData, rightData, roundKey[count--]);
        }
        // 16라운드는 left right 교체 x
        byte[] leftData = Arrays.copyOfRange(data, 0, 32);
        byte[] rightData = Arrays.copyOfRange(data, 32, data.length);
        data = addArray(rightData, leftData);
        data = inverseInitialPermutation(data);
        return data;
    }

위의 코드는 모든 과정을 합친 Encryption (64bit) Decryption(Key를 반대로 입력) 메소드입니다.

 

다음은 Key Generation과정을 살펴보겠습니다.

 

private final byte[] permutedChoice1Table = {57, 49, 41, 33, 25, 17, 9,
                                            1, 58, 50, 42, 34, 26, 18,
                                            10, 2, 59, 51, 43, 35, 27,
                                            19, 11, 3, 60, 52, 44, 36,
                                            63, 55, 47, 39, 31, 23, 15,
                                            7, 62, 54, 46, 38, 30, 22,
                                            14, 6, 61, 53, 45, 37, 29,
                                            21, 13, 5, 28, 20, 12, 4};

public byte[] permutedChoice1(byte[] key){
        byte[] temp = new byte[56];
        for(int i=0; i<this.permutedChoice1Table.length; i++){
            temp[i] = key[this.permutedChoice1Table[i]-1];
        }
        return temp;
    }

먼저 Initial Key를 Permuted Choice과정을 통해 56bit로 만들어 줍니다.

 

// 좌우로 분리시킨 key값을 shift
    public byte[] shiftKey(byte[] key, int round){
        byte[] temp = new byte[28];
        if(round == 1 || round == 2 ||round == 9 ||round == 16) {
            temp[27] = key[0];
            for(int i = 0; i<temp.length-1; i++)
                temp[i] = key[i+1];
        }else{
          temp[26] = key[0];
          temp[27] = key[1];
          for(int i=0; i<temp.length-2; i++)
              temp[i] = key[i+2];
        }
        return temp;
    }

Left와 Right로 나누어진 Key를 Left Shift하며 1, 2, 9, 16 round에서는 1번 나머지는 2번 Left Shift를 진행합니다.

이렇게 만들어진 값은 다음 라운드의 Left, Right값으로 사용되고 현재 라운드의 키값을 만드는데 사용됩니다.

 

private final byte[] permutedChoice2Table = {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};

// shift된 값을 48bit로 permuted choice 진행
    public byte[] permutedChoice2(byte[] key){
        byte[] temp = new byte[48];
        for(int i=0; i<this.permutedChoice2Table.length; i++){
            temp[i] = key[this.permutedChoice2Table[i]-1];
        }
        return temp;
    }

위에서 Left Shift한 값을 Permuted Choice 2를 진행하여 48bit로 만들어 Round Key로 사용하게 됩니다. 

 

// 모든 round key를 만든다.
    public byte[][] generateKey(byte[] initKey){
        byte[][] key = new byte[16][48];
        byte[] choice = this.permutedChoice1(initKey);

        for(int i=1; i<17; i++){
            byte[] leftKey = Arrays.copyOfRange(choice, 0, 28);
            byte[] rightKey = Arrays.copyOfRange(choice, 28, choice.length);

            leftKey = shiftKey(leftKey, i);
            rightKey = shiftKey(rightKey, i);
            byte[] choice2 = this.permutedChoice2(addArray(leftKey, rightKey));
            key[i-1] = choice2;
        }
        return key;
    }

위의 과정을 합쳐 16번의 라운드 키를 모두 생성하여 반환하는 메소드입니다.

 

이렇게 DES64 알고리즘을 구현해봤는데 다음 포스트에서는 위의 값들을 사용하여 파일을 받아 암호화하고 다시 복호화하는 코드를 짜보도록 하겠습니다.