간단한 라운드 함수 구현 만으로도 부분적으로 나와있는 코드를 충분히 연결할 수 있습니다.
입출력값들을 이미 인터넷에 많이 나와있으니 해당 자료들을 참고해 해결해주세요!
1. DES의 알고리즘
▶Input: 64비트의 평문(m1,m2,m3, ......,m64)과 64비트의 키(k1,k2,k3, ......,k64)
키에는 8의 배수 번째 비트마다 parity bit(오류검증비트)가 포함되어 있다.
key schedule 과정에서 이 비트들은 버려야 한다 ← pc1표에서 자동으로 버려진다
*(odd)parity bit란? 앞에 7개의 비트 중에 1의 갯수가 짝수이면 1, 홀수이면 0이다
→ 1의 갯수를 홀수로 만들어주기 위해 추가하는 비트임.
↔even parity bit → cipher only DES key search(DES를 공격하는 기법)에서 사용함
▶라운드: 16
▶Output: 64비트의 암호문(c1,c2,c3, ......,c64)
(1) Key Schedule
KEY 64비트가 들어가 48비트씩 16라운드 subkey를 만든다.
① PC1표를 이용해 K를 C와 D로 28비트씩 쪼갠다.
C= (k57,k49,k41, .... ,k36)
D= (k63,k55,k47, .... ,k4)
② 각각 라운드마다 정해진 횟수만큼 C와 D를 각각 왼쪽으로 로테이션(<<<) 시킨다.
( i=1,2,9,16 1번, i=나머지 2번)
③ C와 D를 합치고 PC2표를 이용해 56비트의 KEY를 48비트로 줄인다.
④ ②~③과정을 16번 반복해 16개의 subkey(48비트)를 만든다.
(2) IP를 이용한 초기전치
IP표를 이용해 초기전치를 해 64비트의 평문의 자리를 바꾼다.
(k1,k2,k3, ......,k64) → (k58,k50,......,k7)
(3) L과 R로 32비트씩 평문을 쪼갠다.
(4) R만 f함수를 통해 key schedule로 만든 subkey와 연산한다.
*f함수의 구조:
① E함수를 이용해 32bit 에서 48bit로 확장된다.
*확장 방법: 표대로 하면 되지만 4개씩 끊어 8개로 만든다음 양 옆에서 한 개씩 가져온다.
② 48비트로 확장된 평문을 subkey와 xor 연산
③ 앞에서부터 6비트씩 8개로 나뉜다.
④ 각각 sbox1, 2, .... 8까지 들어가 4비트씩 나온다
*연산 방법
r6r5r4r3r2r1(16)에서
행(row):r6r1 (범위: 0~3)
열(col):r5r4r3r2 (범위: 0~31)
⑤ 다시 합쳐준다. → 4x8=32bit가 된다.
⑥ p함수에 들어가 다시 자리가 바뀐다.
(5) L과 (L⨁R)이 다음라운드 L과 R로 교차되어서 들어간다.
(6) 2~5번이 16번 반복된다.
(7) 마지막 라운드에서는 5번과정만 생략한다. (irregular swap)
(8) L과 R을 합쳐 IP-1 에 들어가 다시 전치된다.
IP-1 의 output이 함수의 output 즉 cipher가 된다.
2. C언어 코드
∨ C언어 알고리즘을 코딩한 이유: 속도가 빠르다.
파이썬의 경우 내장된 함수와 모듈이 많아서 사실 간편하지만 속도가 C보다 느려 암호 알고리즘을 코딩할 때는 잘 이용하지 않음!
→힘든점: 로테이션(<<<)이 없다. 따라서 KEY Schedule에서 이용하는 LEFT Rotation함수를 직접 만들어야한다.
*코드 구성:
배열을 이용하지 않고 비트의 shift(<<)를 이용해서 unsigned long long 변수 하나로 코딩했다.
평문과 키는 16진수로 16자를 입력받았으며 암호문도 16진수로 출력했다. 사실 입력받는 형태는 노상관, 64비트면 된다.
unsigned long long plaintext = 0x00;
unsigned long long cipertext = 0x00;
unsigned long long key = 0x00; 코드의 효율성 따위는 생각하지 않았다...(2일만에 하느라..) → 나중에 시간이 남으면 필요없는 과정 싹 지워서 재업할 것.
학부 수준에서 배운 shift연산과 매개변수, 포인터를 적절히 사용한 코드이다..ㅎ
(1)Key Schedule :미리 16라운드의 Key를 만들어 놓고 가져다 쓰는 방식을 사용하였다.
unsigned long long subkey[16] = { 0x00, };*함수 형식: void key_sc(unsigned long long key, unsigned long long subkeys[])
∨PC1과 PC2를 이용해 key를 전치시킬때 사용할 PC함수
*함수 형식: unsigned long long pc(unsigned long long var, int pc[], int number)
unsigned long long pc(unsigned long long var, int pc[], int number)
{
int a;
unsigned long long numb = 0x00;
unsigned long long aft_ch = 0x00;
for (a = 0; a < number; a++) //(컴퓨터는 0부터 센다)
{
numb = var >> ((number + 8) - pc[a]); //원하는 자리의 비트를 63번째까지 shift(뒤에 비트를 삭제해줌)
if (number == 56) //64->56(pc1)
{
numb = numb << (number + 7); // 63번째 비트를 0번째 자리로 가져간다.
numb = numb >> (a + 8); //long long은 64비트로 이뤄져있기 때문에 56비트를 만들기 위해서는 8을 더해줌
aft_ch = (aft_ch | numb);
}
else//number==48 //56->48(pc2)
{
numb = var >> ((number + 8) - pc[a]);
numb = numb << (number + 15);
numb = numb >> (a + 16);
aft_ch = (aft_ch | numb);
}
}
return aft_ch;
}
① PC1표를 이용해 K를 C와 D로 28비트씩 쪼갠다.
☆PC1표를 이용해 먼저 전치 후 쪼갠다.
key는 long long 형이기때문에 강제형변환을 이용한다.
int pc1[56] = {
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
};
key = pc(key, pc1, 56); //pc1를 이용해 먼저 전치한다.
//c와 d에는 각각 28비트씩 저장되므로 int형을 선언한다.
unsigned int c = (unsigned int)(key >> 28); //key앞부분 28비트를 위해 뒤 28비트를 shift로 없앰
unsigned int d = (unsigned int)(key & 0x0fffffff); //key 앞부분을 0와 and연산시켜 0으로 만듬.
② 각각 라운드마다 정해진 횟수만큼 C와 D를 각각 왼쪽으로 로테이션(<<<) 시킨다.
( i=1,2,9,16 1번, i=나머지 2번)
unsigned int rotation[16] = { 1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1 };
c = rotation_l(c, rotation[i]); //i번째 round(0부터 15까지) rotation 횟수만큼 표에서 가져와 함수의 매개변수로
d = rotation_l(d, rotation[i]);∨ 로테이션 함수
* 함수 형태: unsigned int rotation_l(unsigned int num, unsigned int n)
★32비트 int 형에서 28비트를 로테이션하는 것
return (((num << n) & 0x0fffffff) | (num >> (28 - n)));
③ C와 D를 합치고 PC2표를 이용해 56비트의 KEY를 48비트로 줄인다.
//c뒤에 d가 와야함, 56비트이기 때문에 long long 형 subkey에서는 8~63비트를 사용함.
unsigned long long subkey=0x00;
subkey = (((unsigned long long)c) << 28); //c를 long long형으로 강제 형변환 하고 28비트 만큼 왼쪽으로 옮긴다. (뒤에 28비트를 만들어주기 위해)
subkey = (subkey | d);
subkeys[i] = pc(subkey, pc2, 48);
//subkeys[i]는 각각 라운드마다 사용할 subkey들을 담고 있는 subkey들의 모임이다.
//key_sc의 매개변수이고, for 문을 이용해서 배열에 차례로 저장할 것이다. ④ ②~③과정을 16번 반복해 16개의 subkey(48비트)를 만든다.
→ for문을 이용(0~15)
(2) IP를 이용한 초기전치
*함수 형식: unsigned long long ip(unsigned long long plaintext)
plaintext(평문)을 매개변수로 받아 초기전치 후 값을 return해 main함수에서 다시 plaintext에 저장하는 방식
plaintext = ip(plaintext); unsigned long long num = 0x0000000000000000;
int i;
unsigned long long aftpt = 0x00;
char ip[64]
= { 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,56,48,40,32,24,16, 8, 0,58,50,42,34,26,18,10,
2,60,52,44,36,28,20,12, 4,62,54,46,38,30,22,14, 6 };
for (i = 0; i < 64; i++)
{
num = plaintext >> (63 - ip[i]); //원하는 자리의 비트를 63번째 자리로 보냄
num = num << 63; //63번째 비트를 0번째 자리로 보냄
num = num >> i;
aftpt = aftpt | num; //or계산을 이용해 계속 저장
}
return aftpt;
(3) L과 R로 32비트씩 평문을 쪼갠다.
left = (unsigned int)(plaintext >> 32); //앞 32비트사용, shift를 이용해 뒤 32비트를 없애고 그자리로 옮김
right = (unsigned int)((plaintext << 32) >> 32); //앞 32비트를 없애기 위해 32비트 shift를 한뒤 다시 뒤 32비트로 옮김(4) R만 f함수를 통해 key schedule로 만든 subkey와 연산한다.
*함수 형식: unsigned int f(unsigned int right, unsigned long long key)
① E표를 이용해 32bit 에서 48bit로 확장된다.
int e[48] =
{ 31,0,1,2,3,4,
3,4,5,6,7,8,
7,8,9,10,11,12
,11,12,13,14,15,16,
15,16,17,18,19,20,
19,20,21,22,23,24,
23,24,25,26,27,28,
27,28,29,30,31,0 };
//위 그림의 표와 다른 이유는 컴퓨터는 0부터 세기 때문에 1씩 빼줌.
unsigned long long using = 0x00;
int i;
unsigned long long save = 0x00;
for (i = 0; i < 48; i++) //key schedule과 똑같은 방식으로 전치함. 48bit로 만들어야하기때문에 48비트만큼 반복
{
using = using & 0x0;
using = (unsigned long long)(right >> (31 - e[i])); //원하는 자리의 비트를 63번째로 옮김.
using = using << 63; //63번째 자리에 있는 비트를 0번째로 가져옴.
using = using >> (i + 16);
save = (save | using);
}
② 48비트로 확장된 평문을 subkey와 xor 연산
save= (save ^ key); ∨ sbox함수를 정의해줌.(③ ~ ⑤ 을 담고 있다) →48비트를 입력받아 32비트를 출력한다.
*함수 형식: unsigned int s_box(unsigned long long using)
<sbox표>
:[sbox번호][행][열]
unsigned int sb[8][4][16] = {
{
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
}
}; //8개의 sbox 4행 16열 ->3차원 배열③ 앞에서부터 6비트씩 8개로 나뉜다. , ④ 각각 sbox1, 2, .... 8까지 들어가 4비트씩 나온다
unsigned char rows[8] = { 0x00, };
unsigned char cols[8] = { 0x00, };
unsigned char num = 0x00;
int i;
for (i = 7; i>=0 ; i--) //맨뒤 48비트 부터 차례대로 right shift 하기 위해
{
num = using; //longlong 형 변수(8바이트)를 char형 변수(1바이트)에 담음으로서 강제 형변환이 일어나 맨앞 56비트가 손실됨
rows[i] = num & 0b00100001; //r6과 r1만 남기기 위해 and연산
rows[i] = (rows[i] & 0b00000001) | ((rows[i] >> 5) << 1);
// row[i]&0b00000001: r1만 남김
// (row[i]>>5)<<1: r6을 2번째 자리에 저장
// or연산으로 2비트짜리 수가 됨
cols[i] = num << 3; //앞 r6을 사라지게함(char형은 8비트임으로 r1 ~ r6 앞에 0으로 2개가 채워져 있는 상태임)
cols[i] = cols[i] >> 4; // 뒤 r1을 사라지게 함
using = using >> 6; //row와 col값을 저장한 r1 ~ r6은 shift 연산으로 사라지게 함
}
⑤ 다시 합쳐준다. → 4x8=32bit가 된다.
unsigned int aft = 0x00;
unsigned int out = 0x00;
int row = 0x00;
int col = 0x00;
int i;
for (i = 0; i < 8; i++)
{
out = out & 0x00;
out = sb[i][row[i]][col[i]];
out = out << (28 - 4 * i); //앞에서 부터 4비트 씩 차례대로 저장하기 때문에
aft = aft | out;
}
return aft;
⑤ p함수에 들어가 전치된다.
*함수 형식: unsigned int P(unsigned int R)
∨ ip함수와 숫자와 표만 다르기때문에 따로 기록 안함.
(5) L과 (L⨁R)이 다음라운드 L과 R로 교차되어서 들어간다.
(6) 2~5번이 16번 반복된다.
unsigned int pre_left= 0x00;
for (r = 0; r < 16; r++)
{
pre_left = pre_left & 0x00;
pre_left = left;
left = left & 0x00;
left = right;
right = (f(right, subkey[r]));
right = (pre_left^right);
}
(7) 마지막 라운드에서는 5번과정만 생략한다. (irregular swap)
→나는 16라운드까지 그냥 swap하고 다시 바꿔주는 걸 선택했다 (중간에 막 설정하려니까.. 헷갈려서 ㅎ)
pre_left = left;
left = right;
right = pre_left;
(8) L과 R을 합쳐 IP-1 에 들어가 다시 전치된다.
IP함수와 마찬가지로 L과 R을 합쳐서 ciphertext에 저장한 후 매개변수로 받아 전치 후 값을 return해 main함수에서 다시 ciphertext에 저장하는 방식
cipertext = (unsigned long long)left; //left를 강제 형변환해서 ciphertext에 저장한다.
cipertext = cipertext << 32; //32-63비트를 사용하고 있기 때문에 0-31까지 사용하도록 shift연산한다.
cipertext = cipertext | (unsigned long long)right;
cipertext = ip_re(cipertext); *함수 형식: unsigned long long ip_re(unsigned long long ciphertext)
∨ ip함수와 표만 다르기때문에 따로 기록 안함.
원래 암호들은 거의 역함수를 가지고 있는데 DES는 역함수가 필요하지도 않고 만들지도 못한다. (E함수같이 확장함수가 있기 때문에)
이론공부만 제대로 한다면 사실 배열가지고 되게 쉽게 만들 수 있다.
하지만 배열을 가지고 하면 살짝 복잡해지고 변수를 여러개 사용해야하는 불편한 점이 있기 때문에 컴퓨터의 비트연산의 장점을 이용했다.
AES보다는 연산들이 쉽기 때문에 DES를 먼저 하게 되었다. AES는 GF연산 + 행렬 해야하기 때문에 그리고 입력 비트가 128, 196, 256비트이기 때문에 input받을 때 이용할 수 있는 자료형이 없어서 배열을 어쩔 수 없이 사용해야한다.
어쨋든 DES끝~
이해 안가는 부분이 있으시면 댓글 달아주세요~~~~
'암호 > 암호 알고리즘' 카테고리의 다른 글
| [AES] 알고리즘 정리 (0) | 2021.03.06 |
|---|---|
| [DES] C언어 버전 full 코드 (0) | 2020.07.24 |
