'des'에 해당되는 글 2건

  1. 2008.12.29 관용 암호와 공개키 암호 비교
  2. 2008.09.19 전산 보안 - DES 암호 알고리즘

관용 암호와 공개키 암호 비교

|




관용 암호와 공개키 암호 비교

 

구분

관용암호

공개키암호

작동방식

l        Feistel Cipher 구조에 기반

l        비트연산

l        Diffie and Hellman 제안

l        수학적 계산

l        비밀키 사용(싱글키, 단일키)

l        키 분배 센터 필요

l        공개키, 개인키 사용

l        키에 대한 공인 인증 필요

장점

l        속도가 빠르다

l        키의 길이가 상대적으로 길다

l        키 분배가 쉽다

단점

l        키 분배, 키 관리 문제 발생

l        계산량이 많다

운용

l        Block Size, Key Size, 라운드 수에 따라 다양한 알고리즘 존재

l        암호화블록의 운영모드 고려

l        암호화/복호화 적용

l        디지털 서명을 통한 인증

l        키 분배에 활용

알고리즘

l        DES

l        Triple DES

l        IDEA

l        Blowfish

l        RC5

l        Cast-128

l        RSA

l        Diffie-Hellman

l        DSS

l        Elliptic Curve

 


관용 암호 설명


1) Feistel Cipher
구조


    Feistel Cipher
는 관용암호에 기본이 되는 알고리즘으로서 평문블록을 두개의 블록으로 나누고 오른쪽 블록과 라운드 카 K를 입력으로 함수 F를 통과시켜서 나온 값과 왼쪽 블록을 XOR합니다. 이러한 라운드를 N번 반복해서 Cipher Text를 만드는 것이 Feistel Cipher 구조입니다.

 
2) DES 알고리즘


   앞서 살펴본 Feistel Cipher와 동일한 구조로 되어 있습니다.

 

먼저 64 비트의 평문 블록을 L0, R0의 두개로 나누고 56bit의 키를 연산을 통해 48bit의 키를 생성합니다.

이어서 R0 K1을 함수 f에 통과시켜 나온 값과 L0 XOR 연산을 수행해서 R1을 생성합니다. L1 R1이 그대로 이동합니다.

이런 연산을 16번의 라운드를 거쳐서 최종적으로 Cipher Text를 구성합니다.


3)
키분배

관용 암호의 경우 동일한 비밀키를 사용하기 때문에 키분배와 관리에 대한 문제가 발생합니다. A B가 직접 물리적으로 키를 교환하는 방식이 가장 바람직하지만 네트워크 환경에서는 적합하지 않기 때문에 KDC(Key Distribution Center)와 같은 Third Party 기관을 통하여 키를 분배하는 방식을 주로 사용하고 있습니다. 이러한 키 분배에 공개키 암호를 활용할 수도 있습니다.

 

또한 관용암호에서는 블록 모드의 운용 방식도 중요한 부분입니다만 앞에서 이미 정리했으므로 여기에서는 생략하도록 하겠습니다.

 

3. 공개키 암호 설명

 

공개키는 관용 암호와 달리 두 개의 키를 쌍으로 사용하며 키 생성에 수학적 계산이 들어갑니다. 이런 공개키는 기밀성 유지를 위한 암호화, 디지털 서명을 통한 인증, 키 분배에 활용됩니다. 각각에 대해 살펴보고 공개키 암호의 대표적인 RSA알고리즘에 대해서 정리합니다 


1) 공개키 암호화

 

송신자(Bob)은 수신자(Alice)의 공개키로 암호화 해서 전송합니다. 수신자는 수신자 본인의 개인키로 복호화합니다. 송신자는 공개키 레파지토리(Public Key ring)에서 수신자의 공개키를 가져옵니다.

 


2)
디지털 서명 인증

 

인증에 활용할 경우 송신자(Bob)는 송신자의 개인키로 암호화해서 전송합니다. 수신자(Alice)는 송신자의 공개키로 복호화해서 사용합니다. 수신자는 송신자의 공개키로 복호화 하므로 사람에 대한 인증으로 누가 보낸 것인지 확인할 수 있습니다. 이런 경우는 브로드캐스트로 메시지를 전송할 때 사용합니다.


3) RSA
알고리즘

Ron Rives, Adi Sharmir, Len Adelman이 만든 공개키 알고리즘으로 널리 사용되고 있는 독보적인 암호화 알고리즘입니다. 개인키나 공개키로 암호화하는 것이 모두 수학적으로 안전하다고 알려져 있습니다. 키를 생성하고 암호화 하는 방식은 다음과 같습니다.



위 과정을 실제 예를 들어 설명한 자료를 참고하면 다음과 같습니다.

 

먼저 두개의 소수 47 71 p q로 설정합니다.

p q의 곱인 3337 n으로 설정하고 (p-1)*(q-1)의 값인 3220을 오일러n으로 선정합니다.

이어서 최대공약수를 계산해 e값인 79를 선택하고 d 값을 1019로 계산하면 공개키 (79, 3337), 개인키 (1019, 3337)이 만들어집니다.

 

암호화와 복호화는 수학 계산에 따라서 이루어집니다.

 

참고자료.

[1] William Stallings, Network Security Essentials : Applications and Standards, Prentice Hall, pp. 22-80, 2000. 

[2]http://www.sds.samsung.co.kr/itplaza/blog/personal/blog.jsp?blog_id=kimsumin75&idx=/vCS7Uqpmbs~KE/RzR9L7sM~, 삼성SDS IT지식채널

[3] http://tadoli.springnote.com/pages/1064412, tadoli님의 노트

[4] http://seonz.tistory.com/13, 선수의 세상사는 이야기 블로그





Trackback 0 And Comment 0

전산 보안 - DES 암호 알고리즘

|




이 글은 김수민님이 작성한 http://blog.naver.com/kimsumin75/20052758036 에서 가져왔습니다.
요즘 전산보안론을 배우고 있는데요..
찾아보니 이해하기 쉽게 작성해 놓으셨더라구요..
DES 암호 알고리즘을 이해하는데 도움이 많이 됩니다.

=================================================

자 드디어 본격적으로 암호 알고리즘을 공부해 봅시다.
 
DES 알고리즘을 들어가기 전에 블록 암호의 구조를 간단하게 살펴보도록 하겠습니다.
 
아래 사진은 IBM의 암호학자였던 Horst Feistel (독일) 의 사진입니다.
흐 .. 아무래도 사진을 보면 친숙해서 머리속에 더 잘 남을 것 같아 ...
하나 올려봅니다. ^^;

 
[사진 1] Horst Feistel
 
이 분이 만든 블록암호의 구조가 DES에 그대로 쓰입니다.
일명, Feistel Cipher 라고 불리는 방식입니다.
(Feistel Network 라고도 합니다.)
 
블록 암호는 주로 단순한 함수를 반복적으로 적용해서 암호학적으로 강한 함수를 만드는 과정으로 개발됩니다.
이때 반복되는 함수를 라운드 함수라고 하고, 라운드 함수에 적용되는 키는 라운드키라고 합니다.
 
라운드키 자체도 독립적으로 생성하는 것이 좋겠지만, 여러가지 관리상의 문제도 있고 하여 ... 보통은 키(비밀키)를 기반으로 라운드키를 발생시켜 사용합니다. 이러한 것을 키 스케줄이라고 합니다.
 
블록 암호는 라운드 함수를 적용하는 방법에 따라
SPN(Substitution-Permutation Network) 방식과 Feistel Cipher 로 나눕니다.
 
AES 에서는 SPN 방식을 쓰고 DES 는 Feistel 방식을 씁니다.
SPN 은 AES 알고리즘 할 때 살펴보기로 합시다.
(사실은 적당한 그림이 안 찾아지네요.. ㅋㅋㅋ)
 
아래 그림을 보세요.

[그림 1] Feistel Cipher
 
[그림 1]은 Feistel 구조를 나타내 보여주고 있습니다. (Encryption 부분만 보세요..)
평문 64bit 가 입력된다고 하면, 32bit 씩 두개로 나누어서 오른쪽 32bit 와 라운드 키 K 를 F 함수에 통과 시킵니다.
여기서 나온 결과와 왼쪽 32bit 를 XOR합니다.
이러한 과정을 라운드라 하고 라운드를 여러번 반복하게 됩니다.
 
Feistel Cipher 에서는 입력 블록을 2개로 분리하는데, 입력 블록을 2개보다 더 많이 분리하는 방식이 있습니다.
이러한 방식은 Unbalanced Feistel Cipher 라고 부릅니다.
 
블록 암호의 구조중 Feistel Cipher 에 대해서 잠깐 살펴보았는데요....
 
DES 에서는 F함수가 어떻게 구성되고 키 스케줄은 어떻게 하는가 ? 이런 의문을 가지고 .. 쭉 읽어내려 가시면 되겠습니다. ^^;
 
[DES 알고리즘]
 
AES 와 DES 를 구현해 보면 AES 가 깔끔하게 구현된다고 하였습니다.
알고리즘에 있어서 .. DES 는 어려운 수학이 사용되지 않습니다.
 
그림을 보면서 bit 연산만 잘 수행하면 됩니다. 흐 ... 말은 쉬운데 ...
 
반면, AES는 어렵다고 해야할지 모르겠지만 수학공식이 한번 사용됩니다.
그대신 복잡한 그림이 많이 필요하지 않습니다.
 
아래 그림들을 보면서 미리 쫄지 마세요... DES 는 어려운 수학은 전혀 사용되지 않습니다.
 

[그림 2] DES 알고리즘 : 데이터 암호화 부분
 
위의 [그림 2] 는 DES 알고리즘 중에서 평문을 암호화 하는 부분을 도식화 한 것입니다. 빠진 부분은 K1 ...K16 의 값인데요... 이 값은 라운드키로써 키 스케줄을 통해서 생성됩니다. [그림 3] 에서는 키 스케줄을 보여줍니다.
 
[그림 2] 를 가만히 보면 Feistel Cipher 방식과 비슷하지 않나요 ?
 
64bit 를 입력 받아서 IP(Initial Permutation) 과정을 거치면 bit 의 순서가 바뀐 64bit 가 출력됩니다.
출력된 값을 32bit 씩 나누고(좌측은 L0, 우측은 R0) ... R0 와 라운드키 K1 을 f 함수에 통과 시킨 값과 L0를 XOR 합니다. 이값은 R1 으로 가고 ..... R0 는 L1 으로 갑니다.
 
이런식으로 ... 쭉 진행됩니다. f 함수를 16번 통과할 때까지 반복됩니다(라운드 함수 16회 적용).
 
그리고 맨 마지막에서 .... IP-1(Inverse Permutation) 을 수행합니다.
 
이제 K1 ~ K16 까지의 값과 IP 와 IP-1 를 어떻게 구하는지... f 함수는 어떻게 처리되는지 알면 DES 를 구현할 수 있습니다. [그림 4] 는 f 함수를 나타내 보여 줍니다.
 
먼저 키 스케줄을 살펴봅시다.

[그림 3] DES 알고리즘 : 키 스케줄 부분
 
흠 별건 없는 것 같네요 .. 64bit 키가 입력되면 PC1 을 거쳐(56bit 로 변환) 28bit 씩 쪼개서 각각을  좌로 shift  연산 후 PC2 를 거쳐 48bit 짜리 키를 뱉어냅니다.
 
16개의 라운드 함수마다 키를 공급해 주어야 하므로 여기서도 16번 48bit 짜리 키를 뱉어냅니다.
 
일단 PC1, PC2, 좌로 shift 연산 ... 이런 것들을 알아야 완전해지겠네요 .....
 
결코 쫄지 맙시다...
어려운 수학은 없습니다.
 
별로 안 어려운데 표현이 어려울 따름입니다.
 
일단 라운드키는 공급할 수 있겠는데... 아직까지 ....좌로 shift 연산, IP, IP-1, PC1, PC2, f 함수 등의 실체가 밝혀지지 않았네요.
 
일단 f 함수의 그림을 살펴봅시다.
 

[그림 4] f 함수 (라운드 함수)
 
앗 .. [그림 4] 를 보니 드디어 .. f 함수의 실체가 밝혀지네요 ...
그런데 ... 이 무슨 ... E(Expansion), P(Permutation), S1 ~ S8 과 같이  모르는게 더 많아져 버렸네요.
f 함수 흐름만 설명하고 나서 빨간 놈들의 실체가 곧 밝혀집니다. 두둥 ~~~
 
일단 f 함수 자체는 이해가 됩니다. 그렇지요 ? ^^;
 
입력값으로 R0, K1 .... R15, K16 을 사용합니다.
 
32bit R0 값을 확장(Expansion) 하여 48bit 로 만들어 48bit K1 키와 XOR 연산합니다.
그러면 48bit 나올텐데 이 48bit 를 8개로 쪼갭니다. 한 조각은 6bit 가 되겠죠 ....?
 
이 6bit 각각이 S1 ~ S8 을 통과합니다(S-Box). 그러면 각각은 4bit 로 줄어들게 됩니다. 그래서 최종 32bit 출력이 되고 P(Permutaion) 연산을 수행하여 최종 32bit 값이 나옵니다.
 
이제 다음 빨간 글씨만 해독하면 DES 는 모두 구현할 수 있을것 같습니다. 
좌로 shift 연산, IP, IP-1, PC1, PC2, E(Expansion), P(Permutation), S1 ~ S8 
 
잠시 한숨 돌리는 차원에서 ... 한가지 짚고 넘어갑시다.
DES 는 64bit 블록 56bit 키 암호 알고리즘으로 알고 있지요 ? 그런데 ... [그림 3] 에서 보면 입력되는 키(비밀키)의 길이가 64bit 지요 ? 이상하지 않나요 ?
PC1 을 거치면서 56bit 로 줄어들게 됩니다. parity bit 를 제거해 버리는데요 .. 8번째bit 제거, 16번째bit 제거 .....
이런식을 1byte 를 없애 버립니다.
 
즉, 키 입력은 64bit 지만 실제 사용되는 것은 56bit 이라는 사실을 명심하셔야 합니다.
DES 의 키길이는 ? 이런 질문을 했을 경우에 56bit 라고 대답하는 것이 정답입니다.
 
자 이제 ... 빨간 글씨를 해독해 봅시다 .....
 
Permutation 이라는 말이 있으면 암호학 개요에서 살펴보았던 전치(transposition) 와 거의 같다고 보시면 됩니다.
S-Box 는 치환(substitution) 을 할 수 있도록 구성된 테이블입니다.
 
* IP, IP-1
 

[표 1] IP 와 IP-1  
 
위의 [표 1]을 보세요 ... 8x8 로 64개의 칸이 있고 1부터 64까지 채워져 있습니다.
표안의 숫자가 의미하는 것은 몇번째 bit 인지를 나타냅니다.
즉, IP 의 경우엔 입력된 64bit 중 58번째 bit 를 제일 앞에 위치하도록 순서를 바꾸라는 의미입니다.
50번째 bit 를 두번째로 위치하도록 하고 ...계속 진행하면서 ..
표의 순서대로 bit 의 배열을 바꾸면 되는 것입니다.
IP-1 의 경우엔 40번째 bit 가 맨 앞으로 오도록 ... 표에 적힌 숫자를 보면서 bit 의 순서를 바꾸면 됩니다.
 
* PC1, PC2
 

[표 2] PC1 : 64bit 를 56bit 로 줄임
 

[표 3] PC2 : 56bit 를 48bit 로 줄임
 
위의 [표 2]에서 보여지듯이 Permutation Choice 과정은 bit 의 순서를 바꿉니다. 하지만, 표의 칸이56개밖에 되지 않습니다. 입력은 64bit 인데 말이죠.... 즉 .. 8, 16, 24 .... 번째 bit 는 버리게됩니다.
표에서도 보면 8의 배수가 쏙~~ 빠진 것을 알 수 있습니다.
[표 3]에서는 칸이 48개입니다. 즉 56bit 를 48bit 로 바꾸는 것입니다.
 
* 좌로 shift 연산

[표 4] Key Left Shift
 
위의 [표 4]를 보시면 i 는 라운드 수를 의미합니다. [그림 3]의 키 스케줄 부분에서 C3,D3 는 즉 i 가 3일 때는 C2,D2 를 좌로 2bit shift 함으로써 구해집니다.
왼쪽으로 shift 를 할 때 오른쪽을 0 으로 채우는 것이 아니고 bit 가 순환된다는 것을 주의 하세요.
 
* E(Expansion), P(Permutation)

[표 5] Expansion : 32bit 를 48bit 로 늘임
 
위의 [표 5]를 보시면 ..... 같은 숫자가 나타나는 것을 보실 수 있습니다.
지금까지 봐왔던 표와 마찬가지로 숫자는 몇번째 bit 인지를 나타냅니다. 같은게 있으므로 키 길이가 늘어나겠죠?^^;
 

[표 6] P-Box (Permutation) : bit 의 순서를 표에 나타낸 것처럼 바꿈
 
위의 [표 6] 은 Permutation 과정인데 P-Box 라고도 얘기합니다. 32 bit 의 순서를 바꿉니다. 표에 나타낸 순서대로 ...
이것도 별로 어려울게 없는것 같네요 ...
 
* S1 ~ S (S-Box)
 
S-Box 는 지금까지 봐왔던 Permutation 과는 조금 다르게 변환이 일어납니다.
일단 아래 S-Box 표를 보시기 바랍니다.
 


[표 7] S-Box : 6bit 를 4bit 로 변환
 
위의 표에서처럼.. S-Box 는 6bit 입력을 4bit 로 변환시킵니다.
Permutation 과는 다른 방식으로 진행이 됩니다.
 
만약 011011 의 6bit 입력된다고 하면 S1 에다가 적용을 해봅시다.
먼저 행을 구하기 위해 첫번째 bit 와 마지막 bit 를 가져옵니다. 01 이 되고 즉 1이 됩니다.
열을 구하기 위해 첫번째와 마지막 bit 를 제외한 나머지 bit 를 가져옵니다. 1101 이 되고 이 값은 13이 됩니다.
 
행은 0~3까지 열은 0~15까지입니다. (1,13) 을 S1 에서 찾아보면 5가 되고 이것은 0101 이 됩니다.
즉, 6bit 입력이 4bit 로 바뀐 것을 알 수 있습니다. 이런 식으로 S-Box 치환이 진행됩니다.
 
드디어 DES 의 알고리즘이 끝이 났네요 ...
 
다음번에는 DES 의 취약키를 한번 알아보고 ... AES 로 넘어가도록 하겠습니다. ^^;




Trackback 0 And Comment 0
prev | 1 | next