암호의 이해 #10

1. 암호화 전송이란?

데이터 전송시 타인의 불법적인 방법에 의해 데이터가 손실되거나 변경되는 것을 방지하기 위해 데이터를 변환하여 전송하는 방법.

2.. 암호화의 필요성 및 효과

가. 암호화의 필요성

- 자료의 디지털 화가 급속도로 증가

- 네트워크를 통한 자료의 전송이 증가

- 해킹등을 통한 자료의 유출이 발생

- 디지털 자료의 유출시 빠르게 유포되어 피해가 커짐

- 유출된 디지털 자료의 회수가 어려움

나. 암호화의 효과

- 자료의 안전한 보관 및 상대방으로의 전달이 가능

- 자료의 전송 중 변경 방지

- 내가 받은 정보가 중간에 누군가의 의해 변경되었는지 확인 가능

- 상대방이 메시지를 보내고도 보내지 않았다고 부인할 수 없게 함

- 서버 등 중요한 자산에 허락되지 않은 사용자의 접근을 차단할 수 있음

- 서버 등 중요한 자산은 패스워드 같은 낮은 수준의 인증 수단보다 훨씬 강력한 인증 수단을 활용할 수 있음.

3. 암호의 발전

가. 고전암호

분류	종류	시기
1세대 암호	대치/치환 (Substitution) - Caesar 방식, Vigenere 방식 등  환치(Transposition) 방식	고대 그리스 ~ 19세기 말
특징	- 정해진 키 값을 이용하여 암호화, 복호화를 수행 - 암호문에 나타나는 문자의 빈도 수, 주기 등 통계적인 특성을 조사하여 해독 가능

분류	종류	시기
2세대 암호	기계 암호(독일 Enigma, 영국 Colossus, 스위스 Hagelin 등)	20세기 전반부(전신의 발명 ~ 제2차 세계대전 이전)
특징	- 전신(Telegraph)의 등장과 1차 대전의 영향으로 급속히 발전 - 수학적으로 약간 진보 - 긴 블록을 암호화 할 수 있는 복잡한 기계들을 사용함으로써 해독에 엄청난 계산이 필요하도록 한 점이 특징

나. 현대 암호(3세대 암호)

분류	종류	시기
3세대 암호	공개키(대칭키) 방식 - 블록 암호, 스트림 암호 비밀키(비대칭키) 방식 - RSA (Rivest, Shamir, Adleman), ECC (Elliptic Curve Cryyptosystem) 등	제2차 세계대전 종전 이후 ~ 현재
특징	- 정수론, 유한군론, 타원곡선, 가환대수, 대수 기하, 조합이론, 그래프이론, 격자이론, 확률론, 수리논리 등      다양한 고급 수학 이론을 사용  - 암호화 알고리즘을 공개하여 효율성과 안정성 확보  - 비 군사용(민수용) 암호의 사용 증가
현대 암호의 조건	- 기밀성, 안정성  - 효율성  - 무결성  - 인증  - 부인방지

4. 1세대(고전) 암호

가. 대치/치환 암호중 Caesar 방식 (단일 치환 방식)

시저 암호는 가장 오래된 암호 중 하나이며, 대표ㅛ적인 대치로서 평문 문자를 다른 문자로 일대일로 대응시켜 암호문을 만들어 내는 방식이다.

시저 암호는 영문 문자에 0부터 25까지 번호를 부여하고, 이 문자를 비밀키와 조합하여 나머지 연산을 수행한다.

원리

평문을 구성하는 요소들의 위치를 암호키에 해당하는 수만큼 이동하여 암호화하는 방식

예시

암호키가 3인 경우

A->X, B->Y, C->Z..

I LOVE YOU(평문) -> L ORYH BRX(암호문)

암호화/복호화

암호용 비밀키가 K 라고 가정하고, 평문은 P, 암호문은 C라고 표시

- 암호화 C=P+K mod 26

- 암호화 P=C+K mod 26

특징

- 쉽고 빠르게 암호화 및 복호화가 가능

- 항상 같은 문자로 암호화 되고, 문자의 출현 빈도를 이용하여 암호키를 유추할 수 있음.

나. 대치/치환 암호 중 Vigenere 방식 (다중치환방식)

비제네르 암호는 다중치환방식으로 하나의 평문 문자가 여ㅕ러 개의 암호 문자로 대치될 수 있는 방식이다.

즉 e라는 문자가 q로 대치되거나 f,j,x 등으로도 대치될 수 있는 방식이다. 

시저 암호의 단점 중 하나인 하나의 평문 문자가 항상 동일한 암호 문자로 대치되는 것을 개선한 것이다.

원리

암호키를 이용하여 주기적으로 문자의 위치마다 다른 이동 암호 방식을 사용

예시

- 암호키가 k=(2,8,15,7,4,17) = "ciper" 인 경우

A -> 1

B -> 2

C -> 3

D -> 4

....

평문	K	C	R	O	N	G
키	2	8	15	7	4	17
암호문	M	K	G	V	R	X

특징

- 단일 치환 방식의 출현 빈도 노출 문제를 극복할 수 있음

- 키의 표현이 단순해짐

다. 환치방식

원리

평문을 구성하는 요소들의 위치를 다양한 방식으로 바꾸는 암호 방식

예시1

평문 : AIR IS A NECESSITYY WITHOUT WHICH NOBODY CAN LIVE

단계1 : 평문의 작업 단위를 결정한다. Ex) 6문자

단계2 : 평문을 정해진 열 단위로 표현한다.

	A	B	C	D	E	F
1	A	I	R	I	S	A
2	N	E	C	E	S	S
3	I	T	Y	W	I	T
4	H	O	U	T	W	H
5	I	C	H	N	O	B
6	O	D	Y	C	A	N
7	L	I	V	E

단계3 : 열 기준으로 다시 표현한다.

ANIHIOL IETOCDI RCYUHYYV IEWTNCE SSIWOA ASTHBN

예시2

자리 바꿈 맵을 이용한 방식

평문 : AIR IS A NECESSITY WITHOUT WHICH NOBODY CAN LIVE 

단계1 : 평문의 작업 단위를 결정한다. Ex) 6문자

단계2 : 자리 바꿈 맵을 이용하여 각 요소의 자리를 바꾼다.

원래위치 1 2 3 4 5 6 

바꿀위치 2 5 3 6 1 4

AIRISA NECESS

SARAII SNCSEE

특징

- 자리 바꿈 암호 방식도 추측이 가능하여, 안정성을 높이기 위해 자리 바꿈을 여러번 반복하여 암호화

- 배열 등을 이용하여 쉽게 컴퓨터에 적용 가능

- 대치/치환과 환치를 함께 사용한 혼합방식을 권장. (현대 대칭 알고리즘은 모두 혼합방식을 사용)

5. 2세대(기계) 암호

전신의 등장과 1차 세계대전의 영향으로 암호분야가 크게 발전하였고, 수학적으로도 약간 진보하였다. 

손으로 직접 작성하던 1세대 암호와는 달리 긴 블록을 암호화 할 수 있는 복잡한 기계들을 사용함으로써 엄청난 계산이 필요하도록 한 점이 특징이다. 기계식 암호화는 1세대 암호에 비해 복잡성 등이 크게 증가하긴 하였으나, 이후 컴퓨터의 발전과 함께 몰락하게 되었다.

Enigma - 독일

- 제 1차 세계대전 이후 1918년 독일의 엔지니어인 아르투어 세르비우스가 발명

- 자판, 입력축, 랩프, 스크램블러, 반사판, 배전반 등으로 구성

- 영문 알파벳 26자를 다른 26자로 바꾸도록 설계된 원통을 이용, 원통은 교체가 가능

- 자판을 이용하여 암호화할 문장을 입력하면 스크램블러가 돌아가면서 암호화된 문장으로 만들어 램프로 표시

Colossus - 영국

- Enigma의 암호를 해독하기 위해 영국 블레츨리 파크에서 개발

- 암호에서 드러나는 통계적 규칙을 찾아내고 암호의 유형을 확인하기 위해 콜로서스 라는 컴퓨터 개발

- 콜로서스는 프로그램으로 운영되는 전자식 디지털 컴퓨터의 시초

- 동기화를 위한 내부 클럭, 이진법, 리본을 이용한 데이터 판독, 버퍼 메모리 사용 등 새로운 컴퓨팅 개념을 실현

Hagelin - 스웨덴, 스위스

- 1930년대 Hagelin 에 의해 개발되었으며, 이후 미국 군대에서 널리 사용됨

- 암호 기계 중에서도 소형에 속해 미군 및 스웨덴 해군 등에서 널리 사용됨

6. 3세대 (현대) 암호

가. 대칭암호화 방식

1) 대칭키의 특징

특징: 동일한 키로 평문 데이터를 암호화하고, 암호 데이터를 복호화 함. 모든 키는 비공개

종류: DES, Triple DES, AES, AES_128, AES_256 등

장점: 암호화 및 복호화의 속도가 빠르다.

단점: 키 관리의 어려움, 키 분배의 문제 등이 있다.

- 볼록암호

고정된 n 비트 블록을 n비트 블록으로 변환시키는 방식. 임의 길이의 평문을 암호화 시키기 위해서는 평문을 특정한 길이로 분할하여 볼록 암호에 입력한다.

- 스트림 암호

평문을 암호화 할 때 한번에 하나의 비트, 또는 하나의 바이트 단위로 암호화 하는 방식

RC4

2) DES (Data Encryption Standard)

특징

- IBM의 바터 투후만과 칼 마이어가 개발

- 64비트의 블록 암호화 알고리즘, 56비트의 암호화 키로 암호화, 256의 키를 생성할 수 있음.

- 대치 방식과 환치 방식을 혼합한 암호 방식

- 1970년대 미연방 표준 암호 알고리즘으로 공표되어 1990년대 후반까지 사용

- 3DES (Triple DES) 까지 개발되었고, AES 로 대체됨

- 미국 연방 정보의 데이터 보호용, ANSI의 표준 암호 알고리즘

- ABA (American Bankers Association) 에서 미국내 금융 정보의 보호 표준 등으로 사용

DES 암호화 알고리즘

1) 하나의 블록인 64비트를 L1(32비트)와 R1(32비트)로 나눈다.

2) R1을 S-Box 를 이용하여 치환 작업 하여 R2를 생성한다.

3) R2와 L1을 XOR 하여 L2를 생성한다.

4) L2와 R2의 위치를 바꾼다.

5) L3, R3의 암호문을 완성한다.

--> 이 과정을 16번 수행하는 16라운드 알고리즘.

DES 복호화 알고리즘

1) 하나의 블록인 64비트를 L3(32비트)와 R3(32비트)로 나눈다.

2) L3와 R3의 위치를 바꾸어 L2와 R2로 만든다.

3) R2를 S-Box 를 이용하여 치환 작업 하여 R1을 생성한다.

4) R1과 L2를 XOR 하여 L1을 생성한다.

5) L1, R1의 평문을 완성한다.

S-Box의 원리

--> P/T 참조

DES의 해독

- 1998년 EFF(전자 프론티어 재단)에서 무차별 대입 공격 하드웨어를 이용하여 56시간 만에 해독

- 1999년 전용 하드웨어와 분산 환경의 10만대의 PC를 이용하여 22시간 만에 해독

- 새로운 공개 알고리즘의 필요성에 대두되었고, AES(Advanced Encryption Standard)로 대체됨

Triple DES

- DES 의 복호화가 가능해짐에 따라 AES가 나오기 전까지 임시로 사용한 암호화 알고리즘

- 두 개의 암호화 키를 이용한 DES

3) AES (Advanced Encryption Standard)

특징

- 공개적인 암호학적 안전성 분석을 통해 리즈멘과 대먼의 Rijndael 알고리즘이 2000년 10월 최종 AES로 선정

- 128 비트의 평문 길이, 128비트, 192비트, 256비트 가변 길이 암호화 키 선택 가능

- 모든 알려진 공격에 대한 저항력

- 평문을 128비트 단위로 나누어 암호화, 복호화 수행, 각각의 128 비트를 8비트(1바이트)*4*4 행렬로 표현 후 연산

- AES의 기본 연산은 바이트 단위의 덧셈(비트 단위의 XOR), 곱셈 연산(mod 8차 기약 다항식)으로 수행됨

AES 암호화 구조

- 키의 길이에 따른 분류 : AES-128, AES-192, AES-256

	암호화 키 길이 (Nk Words)	평문 블록 길이 (Nb Words)	라운드 수 (Nr)	비고 (1Word = 8Bit)
AES-128	4	4	10	8*4*4 = 128
AES-192	6	4	12	8*6*4=192
AES-256	8	4	14	8*8*4=256

- 4단계 (1회의 순열과 3회의 치환)로 구성

바이트 치환 - ByteSub(state)

-> 블록의 바이트 대 바이트 치환을 수행하기 위해 하나의 S-box의 병렬 적용    

행 이동 - ShiftRow(state)

-> 단순 자리 바꿈

열 혼합 - MixColumn(state)

-> GF(28) 산술식을 사용한 치환

라운드 키 추가 - AddRoundKey(state)

-> 현재 블록과 확장된 키의 일부로 단순 비트 단위의 XOR

- 상태(state) 라는 2차원 배열에 각 Layer 에서 연산 수행, State는 4행의 2차원 배열로 구성, 각 행은 Nb 바이트 구성

나. 기타 대칭형 알고리즘

IDEA (International Data Encryption Standard)

개발과정

라이와 메시가 제안한 PES 발표, 암호화 강도를 개선한 IPES 발표, IDEA로 이름변경

암호화 방식

128비트의 암호화 키를 사용하여 64비트의 평문을 8라운드를 거쳐 64비트의 암호문 생성

RC5

개발과정

1994년 RCA연구서의 리베스트가 개발

암호화 방식

64비트의 암호화 키를 이용하며, 라운드 수가 가변적 알고리즘, DES 보다 10배 빠름

Skipjack

개발과정

미국가안보국에서 개발한 Clipper 칩에 내장된 블록 알고리즘

암호화 방식

80비트의 암호화 키를 이용하여, 64비트의 평문을 32라운드를 거쳐 암호화

다. 비대칭 암호화 방식의 필요성

1) 대칭키 방식의 문제점 : 암호화 키의 교환이 필요하며 키의 교환 과정에서 문제 발생

키 교환 필요

- 대칭키에서는 동일한 암호화 키를 이용하여 암호화와 복호화를 수행하므로, 통신하려는 사람들끼리만 키 공유.

- 키가 중간에 유출 될 경우, 기밀성을 보장할 수 없음.

키 관리 문제

- 키를 관리하는 사람이 많아질수록 유출 가능성이 높음

- 암호화 통신을 하는 횟수가 많아질수록 키가 유출될 가능성이 높음

- 암호화 통신의 대상이 늘어날수록 관리해야할 키도 많아짐

키가 많아졌을 때 문제점

- 많은 키를 생성하고 그 키를 상대방에게 안전하게 전달하거나 전달받아야함.

- 각 키와 그 키를 공유하는 상대방을 명확하게 파악하고 있어야 함.

- 메시지를 주고 받는 암호화 통신을 하는 상대방에 해당하는 키를 정확하게 사용해야 함.

- 모든 키를 외부 유출 없이 자신만의 안전한 장소에 보관해야 함.

2) 키 분배 센터를 이용한 키 교환

키 분배 센터

- 비밀 키를 만들어서 대칭키 암호화 통신을 원하는 사람들에게 키를 나누어 줌

- 전제조건 : 키를 분배 받는 모든 사람은 키 분배 센터를 신뢰해야 함.

장점

- 대칭키를 이용하여 암호화 통신을 하고자 하는 사람이 키를 생성할 필요가 없음

- 키의 관리를 키 분배 센터에서 담당

- 키를 암호화 하여 전송하기 때문에 키가 유출되어도 안전함.

라. 비대칭 암호화 방식 (공개키 방식)

1) 비대칭키의 특징

특징

암호화에 사용하는 키와 복호화에 사용하는 키가 다른 방식

종류

수인수분해 문제 - RSA, Rabin

이산대수 문제 - ElGamal, DSA, ECC

장점

키 관리의 어려움을 해결할 수 있다.

인증, 서명 등의 서비스를 이용할 수 있다.

단점

상대적으로 암호화/복호화의 속도가 느리다.

2) 비대칭키의 개념

비대칭키 암호화

대칭키와 비교되어 사용되는 용어.

암호화 하는 키와 복호화 하는 키가 서로 다른 방식.

대칭키는 암호화와 복호화를 위해 사용하는 키가 하나지만, 비대칭키는 암호화와 복호화를 위해 사용되는 키가 두 개다. 따라서 비대칭키 암호화에서는 항상 키를 두 개의 쌍으로 생각한다.

비대칭 키 (공개키와 개인키)를 이용한 암호화 통신 과정

1) A는 개인키와 공개키를 생성하고, 공개키를 외부에 공개하고, 개인키는 안전하게 보관.

2) B는 A와 암호화 통신을 하기 위해 A의 공개키를 얻는다.

3) B는 A의 공개키를 이용하여 메세지를 암호문으로 만들고, A에게 보낸다.

4) A는 B에게 받은 암호문을 자기의 개인키를 이용하여 복호화 하여 메세지를 확인한다.

--> 암호화는 공개키로, 복호화는 개인키로만 가능하다.

3) 비대칭키 암호화를 사용한 키 교환 방법 : 비대칭키 암호화의 특성을 이용하여 비밀키를 안전하게 교환할 수 있는 방법

키 합의

1) B와 A는 각자 개인키를 생성

2) 개인키를 이용하여 공개키 생성

3) 공개키를 서로 교환

4) 자신의 개인키와 상대방의 공개키를 이용하여 비밀키를 생성

5) 생성된 비밀키는 B와 A 모두 동일.. 동일한 비밀키를 공유

Diffie - Hellman 키 교환 알고리즘의 예

1) 공개된 정보는 3

2) B는 자신이 정한 숫자 5를 이용하여 35=243 을 A에게 보냄

3) A는 자신이 정한 숫자 7을 이용하여 37=2187을 B에게 보냄

4) B와 A는 상대에게 받은 수에 자신의 수를 제곱승.

5) B는 21875 = 50,031,545,098,999,707 이라는 키를 알게됨

A는 2437 = 50,031,545,098,999,707 이라는 키를 알게됨. (둘이 같다)

키 전송

1) B는 대칭키 암호화를 위한 비밀키를 생성 후, A의 공개키로 암호화함.

2) 암호문을 A에게 전송

3) A는 자신의 개인키로 암호문을 복호화 함

4) B와 A는 동일한 비밀키를 공유함.

마. RSA 공개키 알고리즘

1) RSA 공개키 알고리즘의 특징

특징

미국 MIT의 Rivest, Shamir, Adleman이 공개키 암호화의 개념을 수학적으로 구체화 시킨 알고리즘

큰 수의 인수분해의 어려움을 이용한 알고리즘, 두 개의 큰 소스를 이용한 연산을 통해 공개키와 개인키를 구성.

장점

개인키 암호 해독이 불가능. (슈퍼 컴퓨터로도 1만년 이상이 소요)

단점

계산량이 많아 암호화/복호화에 오랜 시간이 걸림

동일 문자는 똑같은 숫자로 암호화되어, 랜덤한 패딩값을 삽입하여 같은 문자라도 다른 숫자로 암호화 하도록 개선

2) RSA 공개키 암호화 과정

일방향 함수를 활용

일방향 함수란 한쪽으로는 계산이 쉽게 되지만, 그 반대쪽은 계산하기가 매우 어려운 함수를 의미.

(Ex. 어떤 수의 제곱을 구하는건 쉬우나, 제곱근을 구하는 것은 어렵다.)

암호화과정

모든 사람이 고유한 N값을 갖는다. N은 두 소스의 곱이다.

1) B는 자신의 N을 p=17,159와 q=10,247 의 곱인 N=175,828,273 으로 정한다. B는 자신의 N값을 모두에게 공개.

2) N값은 B의 공개키가 되며, p와 q는 B의 개인키(사설키)가 된다.

3) A는 B의 공개키인 N을 이용하여 메시지를 암호화 하여 보낸다.

4) B는 자신의 개인키인 p,q를 이용하여 밥에게 받은 메세지를 복호화 한다.

--> 암호화는 공개키인 N으로 가능, 하지만 복호화는 오직 p,q 가 있어야 가능하다.