6.0 [초보강좌] 알고리즘 탐구

[whitebono]

이번 강좌는 암호화 알고리즘에 대해서 해보겠습니다.

-잠깐타임!

알고리즘이란?

수학용어로서 알고리즘은 잘 정의되고 명백한 규칙들의 집합 또는 유한 번의 단계 내에서 문제를 풀기 위한 과정이다. 예를 들면, 주어진 정확도에 맞도록 x의 코사인 값을 계산하기 위한 대수적인 과정도 알고리즘에 해당된다. 경험적 지식(heuristic)과 반대되는 용어이다.

컴퓨터용어로서 알고리즘은 어떤 문제의 해결을 위해 컴퓨터가 사용 가능한 정확한 방법을 말한다. 알고리즘은 여러 단계의 유한한 집합으로 구성되는데, 여기서 각 단계는 하나 또는 그 이상의 연산을 필요로 한다.
이 때 컴퓨터가 각 연산들을 수행하기 위해서는 다음의 조건을 만족해야 한다.

① 명확성:각 연산들은 명확한 의미를 가져야 한다.
② 효율성:각 연산은 원칙적으로 일정한 시간 내에 사람이 연필로 할 수 있어야 한다.
③ 입력:외부 입력자료가 있을 수 있다.
④ 출력:하나 이상의 결과가 나온다.
⑤ 종결성:유한 번의 연산 후에는 끝나야 한다.

하지만 여기서는 알고리즘의 수학적 개념이 더 정확할 것 같군요.
암호화는 영어로 Encryption라고 합니다.
암호화는 흔히 알고리즘이라는 수학적 공식을 써서 암호화와 복호화의 과정을 거칩니다.

-잠깐타임!
복호화 : 암호문을 다시 원래의 데이터로 변환하는 과정
암호화 : 임의의 데이터를 암호문으로 변환하는 과정

흔히 들어보셨을 지도 모르지만
PEM(Privacy Enhanced Mail) : E-mail을 전송하기 전에 자동으로 암호화하는 방법을 제공하며, RSA 방식을 사용해서 암호화
PGP(Pretty Good... )~
암호화 알고리즘은 들어보셨을 지도 모르겠습니다.

-잠깐타임!
암호화의 정의

        - 특정한 알고리즘이나 방법을 통하여 전달되는 문서의 무결성, 기밀성, 인증, 부인방지를
           확보하는 행위

혹시나 해서 쓰는데요.
암호화의 필요성은

첫번째. 평문을 네트워크를 통해 전송하는 경우 많은 위협요소에 노출되므로 이를 예방할 수 있다.

두번째. 전송되는 문서에 대한 무결성을 확보할 수 있다.

암호화를 하기에 앞서서 암호화는 다음과 같은 조건을 만족해야 합니다.

● 암호문을 복호화하면 원래의 평문을 얻어야 한다:

P=Decrypt(Encrypt(P)).

● 암호화 하는 함수 Encrypt는 누구나 계산할 수 있다.


● 개인키(복호화키)를 모르면 Decrypt는 현실적으로 계산하기 어렵다.


● 개인키(복호화키)를 알고 있으면 Decrypt를 쉽게 계산할 수 있다.


● 공개키(암호화키)로부터 개인키(복호화키)를 구하는 것은 현실적으로 불가능하다.


● 사용자의 공개키와 사용자의 신분(Identity)를 연결할 수 있는 공개키 기반구조(PKI)가 필요하다.

"아 근데 도대체 암호화는 어떻게 하느냐?" 하시는 분!

암호화의 방법에는

          1) 전치 : 알파벳 순서를 바꾸는 방법(예: 평문 ABCDE --> 암호문 ACDBE)
          2) 대체 : 약속된 문자의 치환(예: 평문 ABCDE  --> 암호문 12345)
          3) hybrid : 전치와 대체를 같이 사용

가 있습니다. '이것은 기초적 암호화 방법입니다.

대표적 암호화의 알고리즘은 DES대칭키알고리즘과 RSA공개키알고리즘이라는 것이 있습니다.

-잠깐타임!

               - 대칭키 : 암호화하는 키와 복호화키(암호를 푸는 키)가 동일한 알고리즘

               - 공개키 : 암호화하는 키와 복호화키가 다른 알고리즘(예: 공인인증서 PKI)

여기서 DES가 뭔지 RSA가 뭔지는 다음에 구체적으로 알아보도록하고..

한마디로 대칭형은 대칭키알고리즘 비대칭형은 공개키알고리즘으로 알아두세요. (아 이모티콘 못써서 어지간히 불편하기는 하군..)
일반적으로 대칭키 암호의 암복호화 속도는 매우 빠르지만, 공개키 암호는 어려운 수학연산을 이용해야 하므로 암복호화 속도가 매우 느립니다.  (첨부된 예제를 통해서 아시면 바로 확인하실 수 있겠지만..)

에.. 그리고..
이제는 암호화 알고리즘의 종류에 대해서 구체적으로 알아보겠습니다.

암호화의 종류는 크게 블록암호, 스트림암호로 구분됩니다.

-잠깐타임!

블록 암호(block cipher)란?

암호문을 만들기 위해 암호 키와 알고리즘이 블럭 단위의 평문에 적용되는 대칭 암호화 방식.  

스트림 암호 [stream cipher]란?

평문을 일련의 비트열로 취급하여 한 번에 1비트씩 혹은 바이트 암호화하는 대칭 암호화 방식.

쉽게 말해서 블록과 스트림의 차이는 암호화하려는 평문을 일정한 크기(예 SEED 128 bit)의 블럭으로 분할하는지. 안하는지의 차이입니다.

블록암호안에 속해있는 암호화 알고리즘으로는 DES, DES3, DESX, RC5, BLOWFISH, CAST128, IDEA, SAFER, RC2 등이 있습니다.

스트림암호안에 속해있는 암호화 알고리즘으로는 RSA, Rabin encryption, ElGamal, Diffie-Hellman, XTR 등이 있습니다.

자 그럼 이제 구체적인 블록암호 암호화 알고리즘을 살펴보도록 하죠. 대략 펌..

1) DES


가장 널리 사용되는 암호 기법은 1977년에 현재의 미국 표준 기술 연구소(NIST)의 전신인 미국 표준국(NBS)에 위해 미 연방 정보처리 표준 46-1(FIPS 46-1)로 채택된 DES에 기초를 두고 있으며, ANSI X3.92-1981에 규정되어 있는 ANSI 표준 데이터 암호화 알고리즘(DEA; Data Encryption Algorithm)과 같은 것이다.



DES는 1975년 2월에 IBM에서 출원한 특허에 기반을 두고 있다. 이 특허는 1971년 6월과 12월에 출원된 Feistel과 Smith의 특허를 참고하여 작성되었다. DES암호에서는 다른 암호 체계에서와 같이 암호 함수에 두 개의 입력이 주어지는데 암호화될 평문과 키가 바로 그것이다. 이 경우 평문은 64비트 그리고, 키는 56비트이어야 한다.(실제로 그 함수는 64 비트의 키를 입력으로 기대하지만 56비트만이 사용되고 있으며 나머지 8비트는 패리티 비트로 사용되거나 임의의 값을 준다.)


2) FEAL(Fast Data Encipherment Algorithm)



FEAL은 1987년 일본 NTT(Nippon Telegraph and Telephone)에서 Shimizu와 Miyaguchi에 의해서 개발되었다. 처음의 FEAL은 64bit의 블록 사이즈와 64bit의 키를 가지고 4 라운드의 단계를 거치는 암호시스템으로서 높은 수행속도를 가지도록 설계되었다. 그러나 4 라운드를 거치면 쉽게 공격을 받아서 8 라운드를 거치도록 FEAL-8이라는 새로운 버전이 나왔다. 또한 최근에는 키 사이즈를 128bit로 하여 안전함을 더하고 있다.


FEAL 알고리즘을 인용한 핵심 특허로는 일본인 Shimizu-Miyaguchi의 "Data Randomization Equipment"를 들 수 있다. 이 특허는 FEAL 개념을 도입하여 정보를 randomization 하는 장치에 대한 특허이다.



3) IDEA(International Data Encryption Algorithm)



IDEA는 스위스 연방 기술 연구소의 Xueja Lai와 James Massey가 개발한 새로운 블록 지향 암호 알고리즘이다. 이 알고리즘은 1990년 스위스 특허청에 등록이 되었다. 차분 암호 공격에 대하여 더 강하게 설계된 개정된 알고리즘 버전은 1991년에 발표되었고, 1992년에는 좀 더 자세하게 기술되었다.



IDEA는 64 bit 블록의 데이터를 암호화하기 위해 128 bit 키를 사용하는 블록 암호이다. 대조적으로, DES도 역시 64 bit 블록의 데이터를 사용하지만 56 bit 키로 암호화된다.



IDEA는 DES를 대체할 수 있는 가장 강력한 후보의 하나로 꼽혀 왔었고 , 기존의 Feistel-type cipher들과 다른 새로운 구조의 라운드 함수를 사용하고 있어 학계의 주요 분석 대상이 되어 온 알고리즘이다. 현존 64비트 블록암호 중에서는 가장 안전한 알고리즘의 하나로 인정받고 있으며, 128비트의 고정길이 키를 사용한다. PGP에서 사용되는 블록암호이며 또한 각종 인터넷 표준들에서도 후보 알고리즘으로 올라 있으나, 미국과 유럽에서는 특허 문제가 걸려 있기도 하다.



IDEA 알고리즘과 관련된 대표적인 특허로는 Lai와 Massey가 발표한 "Device for the conversion of a digital block and use of same"을 들 수 있다. 이 특허는 IDEA 알고리즘을 사용한 암호화 장치(encryptor, 암호기)에 대한 것이다.

4) Skipjack



Skipjack은 NSA(National Security Agency)가 암호 칩으로 디자인한 암호알고리즘이다. 이 알고리즘은 80bit의 키와 32단계의 라운드를 거치기 때문에 54bit의 키와 16단계의 라운드를 거치는 DES보다 안전하다고 할 수 있다. 그러나 많은 사람들이 이에 대해 의문을 품고 있다. DES와는 달리 이 알고리즘의 자세한 사항은 기밀이다. DES는 많은 공격에 의해서 그 취약점이 밝혀졌지만 그 안전성에 대해서는 입증되었다. 그러나 Skipjack은 1998년 이전에는 공개되지 않았기 때문에 그 안전성에 대한 입증 또는 반증이 없었다. 또한 이 알고리즘은 알려지지 않았기 때문에 소프트웨어로 구현할 수 없고, 정보로부터 승인된 칩 제공자에 의해서 하드웨어로만 구현된다. 그렇지만, 우리나라 고려대 정보보호기술연구센터의 '27라운드 스킵잭(Skip Jack)에 대한 포화공격 연구" 논문이 2002년 2월초 벨기에 루벤에서 열린 세계 4대 국제 암호학술회의 가운데 하나인 'FSE2002(Fast Software Encryption 2002)'에서 채택되었는데, 이것은 미국 NSA가 개발한 블록암호 '스킵잭'을 사상 처음으로 해독한 것이었다.



5) RC2, RC5



RC2는 Rivest가 개발한 가변길이의 키를 가진 블록 암호 알고리즘이다. RC는 "Ron's Code" 또는 "Rivest's Cipher"의 약자이다. 데이터 블록은 64bit를 가지지만 키 길이는 가변이기 때문에 그 길이에 따라 안전할 수 있다. 또한 이 알고리즘을 소프트웨어로 구현했을 때 DES 보다 두 배에서 세 배까지 빠르다.



RC5는 키 길이뿐만 아니라 데이터 블록의 길이, 라운드 횟수까지도 바꿀 수 있는 빠른 블록 암호 알고리즘이다. 블록 사이즈는 32, 64, 128 bit까지 가능하고 라운드 횟수는 0부터 255까지 이다. 키 길이는 0 bit부터 2048 bit 까지 가능하다. 이러한 가변적인 키 길이 등으로 인해서 보안 강도를 조절할 수 있다. RC2 와 RC5 암호 알고리즘은 발명되자마자 공개되었기 때문에 관련 특허는 없다.



6) SAFER(Secure And Fast Encryption Routine)



SAFER는 1993년에 Massey에 의해 개발된 블록 암호 알고리즘이다. Byte기반 알고리즘으로 된 64 bit의 블록 사이즈와 키를 가진다. 대부분의 블록 암호 알고리즘과는 다르게 SAFER는 암호화와 복호화 하는 과정이 조금 틀리다. Byte기반으로 동작하기 때문에 스마트 카드 등과 같은 제한된 환경에서 사용될 수 있다. 처음 버전의 SAFER는 64 bit키를 가지므로 SAFER K-64라 불렸고 128 bit의 키를 가진 다른 버전은 SAFER K-128이라 불린다. 그 후 Knudsen은 보다 안전성이 강화된 Key scheduling을 제안하였으며 현재는 주로 이 버전이 사용되고 있으므로 상기의 것과 구분하기 위하여 SAFER SK-64 및 SAFER SK-128 등으로 부른다. 64비트 키를 사용할 때는 8라운드를, 128비트 키를 사용할 때는 10라운드를 사용하도록 권고되고 있다.



7) Blowfish


Blowfish는 Bruce Schneier에 의해 발명된 대칭 블록 암호 방식이며 다음의 특성을 갖도록 설계되었다.

• 빠른 속도 : Blowfish는 32 bit 마이크로 프로세스에서 1 byte당 18clock의 속도로 암호화한다.


• 간결성 : Blowfish는 5K 이내의 메모리에서도 실행될 수 있다.


• 단순성 : Blowfish의 간단한 구조는 구현이 쉽고 또한 알고리즘의 강도결정이 용이하다.


• 보안의 가변성 : 키의 길이는 가변적이며 448 bit 만큼 길어질 수 있어 높은 속도와 높은 보안성 사이의 균형이 가능하다.



8) Rijndael 알고리즘



1997년 이후 4년간 기존 56비트 데이터암호표준(DES)을 대체할 새 표준을 검토해 온 미 상무부가 'Rijndael' 공식에 따른 256비트 고등암호표준(AES: Advanced Encryption Standard)을 채택하였다. 상무부가 채택한 Rijndael AES는 128비트, 192비트, 256비트 암호를 사용하며 이를 이용해 조합할 수 있는 암호 키의 가지 수는 128비트와 256비트가 각각 340×10개와 11×10개에 이른다. 이에 비해 56비트 키는 72×10개이며 특수한 컴퓨터를 동원할 경우 몇 시간 내에 해독이 가능하다. 상무부 산하 NIST 측은 DES 암호를 1초에 풀어낼 수 있는 컴퓨터를 이용해도 128비트 키를 해독하려면 149조년이 걸린다고 주장하고 있다. 한편, 상무부는 AES를 응용한 소프트웨어의 타국 수출도 허용하였다.



그리고 이제 스트림암호로서 대표적인 알고리즘인 RSA를 간단히 소개해 보도록 하겠습니다.(흔히들 유클리드 알고리즘이라고 하시더군요.) 내용출저 네이버지식In wizard159 님의 자료.


정수론이 발달함에 의해서 혁신 적인 보안 시스템이 만들어 졌다. DES 시스템의 단점을 보완한 공개키 시스템 RSA는 상당히 큰 정수의 소인수분해가 힘들다는 점을 이용한 놀라운 암호화 시스템이다. 시스템의 개발자인 R. Rivest, A. Shamir, L. Adleman 의 첫 글자를 따서 붙여 RSA, 흔히 공개키 암호화 시스템이라 한다.



암호화와 복호화에 앞서 거쳐야 할 기본적인 과정.



1) 적당히 비슷하고 큰 소수 p, q를 구합니다.

2) 공개키 n을 생성합니다. (n=pq)

3) φ를 구합니다. φ = (p-1)(q-1)

4) gcd(s,φ)=1을 만족하는 즉 서로 소인 또다른 공개키 s를 생성합니다. 1< s < φ

5) 유클리드 알고리듬을 이용하여 비밀키 d를 만듭니다. d = s^-1 (mod φ) (sd≡1 (mod φ) 를 구하는 것이지요. 무엇을 선택하든 상관없습니다.) 를 구하는 것이지요. 1< d < φ

※ 확장된 유클리드 알고리듬으로 정수 d를 구하는 법

t_0 = 0

t_1 = 1

t_j = t_(j-2)-q_(j-1)t_(j-1) mod r_0 (단, j≥2)

위 방법을 이용하여 d를 구한다.





암호화) n보다 작은 수로 메세지 M을 정한 다음,암호문 c = M^s (mod n) 을 계산하여 암호문 c를 보낸다.

복호화) M = c^d (mod n)을 사용해 복호한다.



예)



1) 소수 5와 7을 골랐습니다.

2) 공개키 n=35를 만들었지요.

3) φ=24를 구했습니다.

4) 24와 서로소인 11=s를 구했습니다.

5) 현재 공개키 (n,s) = (35,11)을 구했지요

6) 비밀키 d를 구합니다.

d = 11^-1 (mod 24)

확장된 유클리드 알고리듬의 적용.

11^-1 (mod 24) --- 주어진 식



24 = 2*11+2(=r1)

--- 24(=n)를 앞의 11(=s)로 나누어 몫과 나머지 형태로 나타낸 것. n = q(=몫)*s+r1(=나머지1)



(t_2)0-2*1 (mod 24) = -2 (mod 24) = 22(=r2) (mod 24)

--- t_(2-2)=0이므로 0-2(=q)*1(t_(2-1)=1) (mod 24) = -2 (mod 24) = 24-2 (mod 24) = 22 (mod 24)



11 = 5(=q2)*2(r1)+1(r3)

---s를 앞에서 나온 나머지 r1으로 나눈 것입니다. 검산식 형태. (현재 여기서는 나머지가 1이 나왔기 때문에 유클리드 알고리듬은 끝이 난 것입니다.)



(t_3)1-22*5 (mod 24) = -109 (mod 24) = 11 (mod 24)

--- 1(=t_(3-2)) - 22(r2)*5(q2) (mod 24) = -109 (mod 24) = 24*5-109 (mod 24)=11(mod 24)



따라서 d = 11.



암호화) 메세지 3을 암호화 해본다. 암호문 c = 3^11 (mod 35) = 12

복호화) 암호문 12를 복호화 해본다. 메세지 M = 12^11 (mod 35) = 3.



복호화가 제대로 되었다. 중요 포인트는 확장된 유클리드 알고리듬을 적용할 때, 나머지가 1이 나올 때까지 계속 반복해야 한다는 점이다.
(여기서 φ는 φ(n)을 뜻하는 오일러 함수 값입니다.)

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
RSA 알고리즘 너무 어렵게 생각하시지 마시고요. 소인수분해 하신다고 생각하세요.

-잠깐타임!

소인수분해란?
합성수를 소수인 인수로 나누는 것입니다.

스트림암호에서 쓰는 암호화방식은


●소인수분해 : RSA, Rabin encryption


●유한체의 이산대수 : ElGamal, Diffie-Hellman, XTR


●타원곡선의 이산대수 : Elliptic Curve Cryptosystem(ECC)


●부호이론(Coding theory) : McEliece


●배낭문제 : Knapsack 암호


●기타 : NTRU (격자이론), Braid-group Cryptosystem (매듭이론)

입니다.

하지만 이 많은 알고리즘 중에서 안타깝게도 완벽한 암호화 알고리즘은 현재 하나도 없다고 합니다.

우리나라에서 완벽한 알고리즘을 만드시는 분이 나오시기를 바랍니다.

첨부된 파일은 여러 알고리즘에대한 PSCCODE의 소스 예제입니다.

잘 모르시는 것은 소스를 참고하시면 되겠습니다.

pass.zip

글쓴이 : ddongswim

[남재경]

알고리즘이 아니고 귀차니즘임 ㅎㅎ,

[장게이츠]

코딩쩐다..

[myunam]

감사