정보 보안

접근 통제

보안 서비스

공격의 유형

소극적 공격 : 가로챔

적극적 공격 :  두절, 변경, 위조

(a) 정보의 정상적인 흐름

(b) 가로챔                                 (c) 두절

(d) 변경                                   (e) 위조

그림 7.1  공격의 유형

보안 서비스

∙ 기밀성(confidentiality)

∙ 인증(authentication)

∙ 무결성(integrity)

∙ 부인 방지(nonrepudiation)

∙ 가용성(availability)

∙ 접근 통제(access control)

해킹 방지

악성 프로그램

숙주 프로그램이 필요한 것 : 바이러스, 로직 폭탄, 트로이 목마

독립적으로 수행되는 것 : 박테리아, 벌레

악성 프로그램이나 해커의 침입 방지

∙ 패스워드 보호

∙ 방화벽 설치

∙ 침입 검출 : OS에 있는 계정(account) 소프트웨어 활용

검출 전용 소프트웨어 설치

그림 7.2  방화벽에 의한 해킹 방지

패스워드 관리

패스워드 선택 방법

∙ 사용자가 임의로 패스워드를 선택

∙ 컴퓨터를 이용하여 랜덤한 문자 스트림을 생성하고 이를 패스워드로

사용

∙ 시스템이 주기적으로 패스워드 크래커(cracker)를 실행하여 추측되는

패스워드를 찾아 그 패스워드를 취소하고 사용자에게 통보

∙ 사용자가 패스워드를 선택하게 하고 그 패스워드의 사용 여부를 시스

템이 결정

∙ 패스워드를 최소한 8문자 이상으로 하고 적어도 하나씩의 대문자, 소문          자, 숫자를 포함

I love Young-Ran.   →  ilyr     첫 글자만 선택

Changsuk  →  vjsmhdil     키보드에서 바로 오른쪽 문자

19840405  →  !(*$)$)%     쉬프트 키를 누른 상태에서의 해당 문자

19850301  →  bjifadab     0 1 2 3 ...을 a b c d ...로 대치

white  →  black     반대말

darling  →  radnilg     문자의 위치 바꿈

love  →  lovelove     반복

soft ball  →  sobaftll     두 단어를 혼합

computer  →  ocpmture  → ixonryew  →  Ixonry4w     삼중 변환

관용 암호화

암호화 모델

보안 서비스를 제공하기 위한 요구사항

∙ 암호화 알고리즘의 선택

∙ 암호키 생성

∙ 키 분배

암호화 기법의 분류

- 해커의 해독 가능성

무조건 안전(unconditionally secure)

계산상 안전(computationally secure)

- 동작 형태에 따른 분류

대치법(substitution)

치환법(transposition)

- 평문의 처리 방법에 따른 분류

블록 암호화(block cipher)

스트림 암호화(stream cipher)

- 키에 따른 분류

비밀키(secret key) 암호화

공개키(public key) 암호화

관용 암호화 방법

송신측                     [eqn: C ~=~ E_K ( P`)]                                (7-2)

수신측

[eqn: P &~=~ D_K (C`) ## &~=~ D_K`` [E_K (P`) `]]                          (7-3)

공개키 암호화 방법

송신측

[eqn: C ~=~ E_KU_B (P`)]                               (7-4)

수신측

[eqn: P &~=~ D_KR_B (C`) ## &~=~ D_KR_B ``[E_KU_B (P`) `]]                        (7-5)

그림 7.4  관용 암호화 모델

그림 7.5  공개키 암호화 모델

대치법

Caesar 암호 : 각 문자를 세 번째 뒤에 있는 문자로 대체

평문   : a b c d e f g h i j k l m n o p q r s t u v w x y z

암호문 : d e f g h i j k l m n o p q r s t u v w x y z a b c

(예) data communication → gdwd frppxqlfdwlrq

단일 알파벳 암호 : 문자를 다른 문자로 일대일 매핑

평문   : a b c d e f g h i j k l m n o p q r s t u v w x y z

암호문 : o f j g z h r e k t a x d v q i s l u p m y n c b w

(예) data communication → gopo jqddmvkjopkqv

문자의 발생 빈도

단일 문자 : e  t  o  a  n  i  r  s  h  d  l  c  f  u  m  p  y  w  g                    b  v  k  x  j  q  z

이중 문자 : th  in  er  re  an  he  ar  en  ti  te  at  on  ha  ou  it

삼중 문자 : the  ing  and  ion  ent  for  tio  ere  her  ate  ver  ter

단어      : the  of  and  to  a  in  that  is  I  it  for  as  with  was

다중 알파벳 암호 : Vigenere 표를 이용

일정한 길이의 키를 반복하여 사용

특정 키에 평문 자체를 연결하여 자동키(autokey)로 사용

표 7.2 Vigenere 표

	a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
a	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
b	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A
c	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B
d	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C
e	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D
f	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E
g	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F
h	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G
i	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H
j	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I
k	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J
l	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K
m	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L
n	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M
o	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N
p	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O
q	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P
r	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q
s	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R
t	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S
u	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T
v	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U
w	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V
x	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W
y	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X
z	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y

(예) Gerard Joling의 “Ticket to the tropics"

computer 키를 이용하여 다중 알파벳 암호로 변환

Gotta(=got to) buy me a ticket to the tropics

Forget our love and leave this place behind me

Gonna(=going to) buy me a ticket to the tropics

And prove myself that I can live without your love

- 키를 반복하여 사용하는 경우 :

키 : c o m p u t e r c o m p u t e r c o

평문 : t i c k e t t o t h e t r o p i c s

암호문 : v w o z y m x f v v q i l h t z e g

- 키에 평문을 연결한 자동키의 경우 :

키 : c o m p u t e r i c a n l i v e w i t h o u t

평문 : i c a n l i v e w i t h o u t y o u r l o v e

암호문 : k q m c f b z v e k t u z c o c k c k s c p x

(예제 7.1)  실제로 1차대전 때 영국군이 처음 사용하였고 2차대전 때에는 미국군도 사용하였다고 하는 playfair 알고리즘을 이용하여 “love is true"를 암호화하라. 단, 사용하는 키는 computer이다.

C	O	M	P	U
T	E	R	A	B
D	F	G	H	I/J
K	L	N	Q	S
V	W	X	Y	Z

playfair 알고리즘

1. 평문을 두 문자씩 분리하여 한번에 두 문자씩 암호화한다.

2. ss와 같이 동일한 문자가 연속되면 채움 문자(filler letter) x를 삽입하여 sxs     형태로 만든다.

3. op와 같이 동일한 열에 있는 두 문자는 바로 오른쪽에 있는 문자인 mu로 암     호화한다.

4. tk와 같이 동일한 행에 있는 두 문자는 바로 아래에 있는 문자인 dv로 암호     화한다.

5. 이외의 경우에는 각 문자를 그 문자가 있는 열과 다른 문자가 있는 행이 교     차되는 부분의 문자로 암호화된다. 예를 들어, eq를 al로 암호화 한다.

평문 : lo ve is tr ue

암호문 : we wt sz ea ob

치환법

평문에 있는 문자의 위치를 바꾸는 매핑 방법

키  :  2 5 1 7 4 3 6

평문 :  s c o r p i o

n s s t i l l

l o v i n g y

o u a n n e v

a d a e r o s

암호문 : osvaasnloailgeopinnrcsoudolyvsrtine

암호 해독 과정 : 3 1 6 5 2 7 4    단어                올바른 배열

o s i p c o r (scorpio)             s c o r p i o

s n l i s l t (still s n)             n s s t i l l

v l g n o y I (loving y)     →     l o v i n g y

a o e n u v n (anne o u v)          o u a n n e v

a a o r d s e (eros a d a)          a d a e r o s

해독된 평문 :  scorpions still loving you & anne vada eros

2단계 치환법

1단계 치환 결과 : osvaasnloailgeopinnrcsoudolyvsrtine

키  : 2 5 1 7 4 3 6

치환 결과  : o s v a a s n

l o a i l g e

o p i n n r c

s o u d o l y

v s r t i n e

암호문  : vaiurolosvsgrlnalnoisoposnecyz

(예제 7.2)  다음 문장은 Scorpions의 “Still loving you"라는 노래의 가사 일부분이다. 아래에 주어진 순열표(permutation table)에 의해 문자들을 치환하는 방법으로 암호화하라.

평문 : I would try to change the things that killed our love.

순열표

ꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏ

24 40  7 11 35 19  1 15  3 31 21 42  5  9 22 27  4 33 41 12  8 30

13 44 10 17 32 39 37 14 28 20  6  2 34 18 36 29 38 26 43 16 23 25

ꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏꠏ

암호문 : nltoehInoktvlyhtulocrth.teiroahedwltdausegig

DES(Data Encryption Standard)

64비트의 평문을 56비트의 키로 암호화

∙ 높은 보안성을 제공

∙ 이해하기 쉽고 완벽하게 정의

∙ 보안성은 암호화 알고리즘에 의존하지 않고 키에 의해 제공

∙ 모든 사용자에게 유용

∙ 다양한 응용에 사용 가능

∙ 경제적으로 전자 소자로 구현 가능

∙ 사용하기 편리

∙ 알고리즘의 검증 가능

∙ 이식성 제공

그림 7.6  DES 알고리즘의 기본 구조

표 7.3  초기 순열표

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

표 7.4  키 압축 순열1 표

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

그림 7.7  DES 알고리즘의 각 단계에서의 기능

표 7.5  확장 순열표

32	1	2	3	4	5
4	5	6	7	8	9
8	9	10	11	12	13
12	13	14	15	16	17
16	17	18	19	20	21
20	21	22	23	24	25
24	25	26	27	28	29
28	29	30	31	32	1

표 7.6  단계별 쉬프트표

단계	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
쉬프트 비트수	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

표 7.7  키 압축 순열표

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

표 7.9  P-box 순열표

16	7	20	21	29	12	28	17
1	15	23	26	5	18	31	10
2	8	24	14	32	27	3	9
19	13	30	6	22	11	4	25

그림 7.8  S-box의 기능

표 7.10  최종 순열표

40	8	48	16	56	24	64	32
39	7	47	15	55	23	63	31
38	6	46	14	54	22	62	30
37	5	45	13	53	21	61	29
36	4	44	12	52	20	60	28
35	3	43	11	51	19	59	27
34	2	42	10	50	18	58	26
33	1	41	9	49	17	57	25

(예) S-Box의 입력 :“100011011100100011......”

출력 : “100001101001...”

S1             S2           S3        S4 ...

S-box의 입력 :  1 0 0 0 1 1   0 1 1 1 0 0   1 0 0 0 1 1    ...........

2     3       1    12       2     3

↘ ↙         ↘ ↙         ↘ ↙

8             6             9          .....

↓            ↓            ↓

S-box의 출력 :    1 0 0 0       0 1 1 0       1 0 0 1       ........

표 7.8  S-box 대치표

	뒤 4비트			0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
앞 2비트
S1		0		14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
		1		0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
		2		4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
		3		15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13
S2		0		15	1	8	14	6	11	3	4	9	7	2	13	12	0	5	10
		1		3	13	4	7	15	2	8	14	12	0	1	10	6	9	11	5
		2		0	14	7	11	10	4	13	1	5	8	12	6	9	3	2	15
		3		13	8	10	1	3	15	4	2	11	6	7	12	0	5	14	9
S3		0		10	0	9	14	6	3	15	5	1	13	12	17	11	4	2	8
		1		13	7	0	9	3	4	6	10	2	8	5	14	12	11	15	1
		2		13	6	4	9	8	15	3	0	11	1	2	12	5	10	14	7
		3		1	10	13	0	6	9	8	7	4	15	14	3	11	5	2	12
S4		0		7	13	14	3	0	6	9	10	1	2	8	5	11	12	4	15
		1		13	8	11	5	6	15	0	3	4	7	2	12	1	10	14	9
		2		10	6	9	0	12	11	7	13	15	1	3	14	5	2	8	4
		3		3	15	0	6	10	1	13	8	9	4	5	11	12	7	2	14
S5		0		2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
		1		14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6
		2		4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14
		3		11	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3
S6		0		12	1	10	15	9	2	6	8	0	13	3	4	14	7	5	11
		1		10	15	4	2	7	12	9	5	6	1	13	14	0	11	3	8
		2		9	14	15	5	2	8	12	3	7	0	4	10	1	13	11	6
		3		4	3	2	12	9	5	15	0	11	14	1	7	6	0	8	13
S7		0		4	11	2	14	15	0	8	13	3	12	9	7	5	10	6	1
		1		13	0	11	7	4	9	1	10	14	3	5	12	2	15	8	6
		2		1	4	11	13	12	3	7	14	10	15	6	8	0	5	9	2
		3		6	11	13	8	1	4	10	7	9	5	0	15	14	2	3	12
S8		0		13	2	8	4	6	15	11	1	10	9	3	14	5	0	12	7
		1		1	15	13	8	10	3	7	4	12	5	6	11	0	14	9	2
		2		7	11	4	1	9	12	14	2	0	6	10	13	15	3	5	8
		3		2	1	14	7	4	10	8	13	15	12	9	0	3	5	6	11

DES 동작 모드

(a) ECB 모드

(b) CBC 모드

(c) OFB 모드

(d) CFB 모드

그림 7.9  DES의 동작 모드

그림 7.10  삼중 DES 알고리즘

IDEA(International Data Encryption Algorithm)

64비트의 평문 블록을 128비트의 키로 암호화

1990년 X. Lai와 J. Massey에 의해 개발

보안성이 매우 뛰어나고 암호화 및 암호 해독 속도가 빠름

DES의 유력한 대안으로서 인정

그림 7.11  IDEA 알고리즘

공개키 암호화

1976년 W. Diffie, M. Hellman이 제안

수신자의 공개키로 전문 암호화

송신자의 비밀키로 디지틀 서명

세션키 교환

그림 7.12  인증 기능을 포함한 공개키 암호화 모델

공개키 암호화의 요구사항

요구사항

∙ 송신자가 평문을 암호화하기 용이할 것.

∙ 수신자가 공개키와 비밀키를 생성하기 용이할 것.

∙ 수신자가 암호문을 해독하기 용이할 것.

∙ 해커가 공개키를 알더라도 비밀키를 알아내기 어려울 것.

∙ 해커가 공개키와 암호문을 알더라도 해독하기 어려울 것.

표 7.11  권장되는 공개키의 길이

년도	개인	기업	정부
1995년	768비트	1280비트	1536비트
2000년	1024비트	1280비트	1536비트
2005년	1280비트	1536비트	2048비트

Knapsack 알고리즘

1978년 R. Merkle과 M. Hellman에 의해 개발

[eqn: RM W ~=~ a_1 W_1 ~+~ a_2 W_2 ~+~ cdots ~+~ a_n W_n]              (7-6)

무게 Wi인 물건이 있으면 ai = 1이고, 없으면 ai= 0

그림 7.13  knapsack 알고리즘

(예) 배낭의 무게 : 350g

[eqn: 350 &~=~ a_1 times 20 ~+~ a_2 times 30 ~+~ a_3 times 70 ~+~ a_4 times 160## &~~~~+~a_5 times 300 ~+~ a_6 times 720 ## &~=~1 times 20 ~+~ 1 times 30 ~+~ 0 times 70 ~+~ 0 times 160 ## &~~~~+~ 1 times 300 ~+~ 0 times 720]             (7-7)

배낭 속에는 ai가 1인 연필, 지갑, 노트가 들어 있음

knapsack 알고리즘에 사용되는 시퀀스

superincreasing knapsack sequence : 모든 항들 각각이 첫 번째 항부터          바로 앞의 항까지를 전부 더한 것보다 큰 시퀀스

{1, 3, 5, 11, 23, 47, ...}

비밀키로 사용

normal knapsack sequence : 과증가 knapsack 시퀀스의 각 항에 특정한           수 n을 곱한 다음 모든 항을 합한 값보다 큰 수 m으로 모듈로 나눗셈           을 한 결과로 생성된 시퀀스(m과 n은 서로소)

공개키로 사용

knapsack 알고리즘의 키 생성 과정, 암호화 및 암호 해독 방법

비밀키로 사용될 과증가 knapsack 시퀀스 선택

비밀키 : {1, 3, 5, 11, 23, 47}

공개키로 사용될 정상 knapsack 시퀀스를 구한다. (m=95, n=29)

1×29 mod 95 = 29

3×29 mod 95 = 87

5×29 mod 95 = 50

11×29 mod 95 = 34

23×29 mod 95 = 2

47×29 mod 95 = 33

⇒ 공개키 : {29, 87, 50, 34, 2, 33}

평문을 knapsack 시퀀스의 항수와 동일한 길이로 분할

공개키를 이용하여 암호화한다.(암호문은 평문의 비트 스트림중 1에 해당하는 정상 knapsack 시퀀스의 항들을 합한 값)

(예) 평문의 비트 스트림이 010110100011001100인 경우

공개키 : 29 87 50 34  2 33    29 87 50 34  2 33    29 87 50 34  2 33

평문   :  0  1  0  1  1  0     1  0  0  0  1  1     0  0  1  1  0  0

↓    ↓ ↓       ↓          ↓ ↓          ↓ ↓

87 + 34 + 2       29 +        2 + 33        50 + 34

⇓                    ⇓                    ⇓

암호문 :        123                  64                   84

수신자는 암호문에 n-1(nn-1 = 1 mod m)을 곱하고 mod m 나눗셈을 하여 얻은 값을 비밀키인 과증가 knapsack 시퀀스의 항들로 분해한다.

nn-1 = 1 mod m  ⇒  29n-1 = 1 mod 95  ⇒  n-1 = 59

암호문 ∶  123 × 59 mod 95 = 37

64 × 59 mod 95 = 71

84 × 59 mod 95 = 16

비밀키 ∶                        1   3   5  11  23  47

암호 해독 ∶ 37 = 23 + 11 + 3  ⇒   0   1   0   1   0   0

71 = 47 + 23 + 1  ⇒   1   0   0   0   1   1

16 = 11 + 5       ⇒   0   0   1   1   0   0

암호문 123 64 84는 원래의 평문 010100 100011 001100으로 해독

RSA 알고리즘

1977년 MIT대학교의 R. Rivest, A. Shamir, L. Adleman에 의해 개발

현재 가장 널리 인정받고 있는 공개키 암호화 기법

비교적 짧은 평문 블록을 암호화

디지틀 서명 및 키 교환에도 이용

RSA 알고리즘의 공개키와 비밀키를 생성하는 과정, 암호화 및 암호 해독 방법

매우 큰 소수 p, q를 선택하고, n을 계산한다.

[eqn: RM n ~=~ p ~times~ q]                                 (7-7)

(p-1)(q-1)과 서로소인 e를 선택하여 암호키로 사용

암호키 e를 이용하여 암호 해독키 d를 계산한다.

[eqn: RM ed ~=~ 1 ~mod ~[(p-1)`(q-1)]]                       (7-8)

e와 n는 공개키로 사용, d는 비밀키로 사용

송신자는 공개키 e와 n을 이용하여 평문 P를 암호문 C로 암호화하여 전송

[eqn: RM C ~=~ P^e ~mod ~n]                              (7-9)

수신자는 비밀키 d를 이용하여 수신한 암호문을 해독

[eqn: RM P ~=~ C^d ~mod ~n]                             (7-10)

∙ p와 q는 1075 ～ 10100 범위의 소수로서 크기가 비슷하여야 한다.

∙ (p-1)과 (q-1)은 큰 소수 인자를 포함하지만 최대공약수는 작아야 한다.

그림 7.14  RSA 알고리즘

(예제 7.3)  평문 15를 RSA 알고리즘으로 암호화 및 암호 해독하는 과정을 기술하라. 단, 두 소수 p, q는 매우 커야 하지만 편의상 13, 17로 선정한다.

1. 두 소수 p, q로부터 n을 계산한다.

n = p × q = 13 × 17 = 221

2. 공개키 e를 선택한다.

(p-1)(q-1) = (13 - 1)(17 -1) = 12 × 16 = 192

gcd[e,(p-1)(q-1)] = 1   ⇒   gcd(e,192) = 1

192와 서로소인 7을 공개키 e로 임의 선택한다.

3. 비밀키 d를 계산한다.

ed = 1 mod [(p-1)(q-1)]   ⇒   7d = 1 mod 192

비밀키 d로 55를 선택한다.

4. 송신측에서는 공개키 e=7을 이용하여 평문 15를 암호화한다.

[eqn: RM C ~=~ P^e ~mod ~ n]

⇒ [eqn: RM C ~=~15^7 ~mod~ 221 ~=~ 170859375~mod ~221 ~=~76]

평문 15는 76으로 암호화된다.

5. 수신측에서는 비밀키 d=55을 이용하여 암호문 76을 해독한다.

[eqn: RM P ~=~ C^d ~mod ~n]

⇒ [eqn: RM P ~=~ 76^55 ~mod~221 ~=~ 2.7845 times 10^103 ~mod~ 221 ~=~15]

키 분배

공개키를 분배

모든 사람에게 공개키 방송

공개키 디렉토리 관리 방법

증명서 발행 기관 이용

[eqn: RM C_A ~=~ E_KU_auth (`T, ~ID_A , ~KU_A `)]                  (7-11)

[eqn: RM D_KU_auth `[C_A ] ~=~ D_KU_auth `[ E_KU_auth (T, ID_A , KU_A )] ~=~ (T, ID_A, KU_A )]    (7-12)

그림 7.15  공개키 증명서 교환

관용 암호화 기법에서의 키 분배

∙ 키를 암호문의 전송로와 다른 경로로 전달

∙ 이전의 키를 이용하여 새로 사용할 비밀키를 암호화하여 전달

∙ 키분배 센터(KDC : key distribution center)를 이용

그림 7.16  관용 암호키 분배

인증

링크 및 단대단 암호화

암호화하는 위치에 따른 분류

∙ 링크(link) 암호화

∙ 단대단(end-to-end) 암호화

그림 7.17  링크 암호화

그림 7.18  단대단 암호화

그림 7.19  링크 및 단대단 암호화의 혼합 사용

해쉬 함수

인증(authentication)

∙ 전문 내용의 변조(content modification)

∙ 사용자를 위장한 전문 위조(masquerade)

∙ 전문의 순서 변조(sequence modification)

∙ 전문을 지연하는 등의 시간 변조(timing modification)

∙ 전문의 길이, 통신 빈도 등의 트래픽 분석(traffic analysis)

인증 기능 수행 방법

∙ 전문 암호화(message encryption)

∙ 암호 체크섬(cryptographic checksum)

∙ 해쉬 함수(hash function)

해쉬 함수 H(x) : 메시지 블록을 입력받아 해쉬값을 출력

∙ 임의 길이의 메시지 블록에 적용 가능

∙ 고정 길이의 출력을 생성

∙ 어떠한 x에 대해서도 H(x)의 계산 용이

∙ m이 주어지더라도 H(x)=m인 x 계산 불가능

MD5 알고리즘

1992년 R. Rivest이 개발

임의 길이의 메시지를 512비트 단위로 처리하여 128비트의 MD 생성

그림 7.22  MD5 알고리즘을 이용한 메시지 다이제스트 생성

그림 7.23  512비트 블록을 처리하는 MD5 알고리즘

메시지의 길이가 512비트의 정수배보다 64비트 적도록 패딩

512비트의 블록을 처리하는 MD5 알고리즘 4 라운드로 구성

32비트 레지스터 A, B, C, D로 구성된 128비트 버퍼가 사용

레지스터의 초기값

A = 0x01234567   B = 0x89abcdef   C = 0xfedcba98   D = 0x76543210

각 라운드는 512비트의 메시지 블록을 32비트씩 16개로 분할한 소블록 M1, M2, ..., M16에 대하여 16회의 다른 연산을 수행

단계 1 :  b, c, d에 대하여 다음과 같은 비선형 함수를 수행

F(b,c,d) = [eqn: RM (b cdot c ) ~+~ (bar b cdot d)]

G(b,c,d) = [eqn: RM (b cdot c) ~+~ (c cdot bar d )]

H(b,c,d) = [eqn: RM b ~BIGOPLUS~ C ~BIGOPLUS~ d]

I(b,c,d) = [eqn: RM C ~bigoplus~ (b cdot bar d )]

단계 2 :  단계 1의 결과와 a를 모듈로 232 덧셈

단계 3 :  단계 2의 결과와 메시지 소블록 Mi를 모듈로 232 덧셈

단계 4 :  단계 3의 결과와 표 7.12에 열거한 상수 Ti를 모듈로 232 덧셈

Ti : 232×abs(sin(i))의 정수부, i : 레디안 값

단계 5 :  s비트 좌측으로 쉬프트

단계 6 :  단계 5의 결과와 b를 모듈로 232 덧셈

단계 7 :  a를 단계 6의 결과로 대체

그림 7.24  MD5 알고리즘의 기본 연산 과정

4 라운드의 연산이 모두 수행된 다음 a, b, c, d를 레지스터 A, B, C, D와 모듈로 232 덧셈

이 결과는 후속 512비트의 메시지 블록의 연산에 사용

마지막 메시지 블록에 대한 연산이 모두 완료되었을 때의 ABCD의 값이 128비트의 메시지 다이제스트로 출력

연산 과정

FF(a,b,c,d,Mi,s,Ti) :  a = b + [(a + F(b,c,d) + Mi + Ti) <<< s]

GG(a,b,c,d,Mi,s,Ti) :  a = b + [(a + G(b,c,d) + Mi + Ti) <<< s]

HH(a,b,c,d,Mi,s,Ti) :  a = b + [(a + H(b,c,d) + Mi + Ti) <<< s]

II(a,b,c,d,Mi,s,Ti) :  a = b + [(a + I(b,c,d) + Mi + Ti) <<< s]

F, G, H, I : 비선형 함수      Mi : 32비트의 메시지 소블록

Ti : 32비트 상수              s : 좌로 쉬프트할 비트수

+ : 모듈로 232 덧셈

표 7.12  상수 Ti의 값

T1 = d76aa478         T17 = f61e2562         T33 = fffa3942         T49 = f4292244

T2 = e8c7b756         T18 = c040b340         T34 = 8771f681         T50 = 432aff97

T3 = 242070db         T19 = 265e5a51         T35 = 69d96122         T51 = ab9423a7

T4 = c1bdceee         T20 = e9b6c7aa         T36 = fde5380c         T52 = fc93a039

T5 = f57c0faf         T21 = d62f105d         T37 = a4beea44         T53 = 655b59c3

T6 = 4787c62a         T22 = 02441453         T38 = 4bdecfa9         T54 = 8f0ccc92

T7 = a8304613         T23 = d8a1e681         T39 = f6bb4b60         T55 = ffeff47d

T8 = fd469501         T24 = e7d3fbc8         T40 = bebfbc70         T56 = 85845dd1

T9 = 698098d8         T25 = 21e1cde6         T41 = 289b7ec6         T57 = 6fa87e4f

T10 = 8b44f7af        T26 = c33707d6         T42 = eaa127fa         T58 = fe2ce6e0

T11 = ffff5bb1        T27 = f4d50d87         T43 = d4ef3085         T59 = a3014314

T12 = 895cd7be        T28 = 455a14ed         T44 = 04881d05         T60 = 4e0811a1

T13 = 6b901122        T29 = a9e3e905         T45 = d9d4d039         T61 = f7537e82

T14 = fd987193        T30 = fcefa3f8         T46 = e6db99e5         T62 = bd3af235

T15 = a679438e        T31 = 676f02d9         T47 = 1fa27cf8         T63 = 2ad7d2bb

T16 = 49b40821        T32 = 8d2a4c8a         T48 = c4ac5665         T64 = eb86d391

		제 1 라운드	제 2 라운드
	연산 1	FF(a,b,c,d,M1,7,T1)	GG(a,b,c,d,M2,5,T17)
	연산 2	FF(d,a,b,c,M2,12,T2)	GG(d,a,b,c,M7,9,T18)
	연산 3	FF(c,d,a,b,M3,17,T3)	GG(c,d,a,b,M12,14,T19)
	연산 4	FF(b,c,d,a,M4,22,T4)	GG(b,c,d,a,M1,20,T20)
	연산 5	FF(a,b,c,d,M5,7,T5)	GG(a,b,c,d,M6,5,T21)
	연산 6	FF(d,a,b,c,M6,12,T6)	GG(d,a,b,c,M11,9,T22)
	연산 7	FF(c,d,a,b,M7,17,T7)	GG(c,d,a,b,M16,14,T23)
	연산 8	FF(b,c,d,a,M8,22,T8)	GG(b,c,d,a,M5,20,T24)
	연산 9	FF(a,b,c,d,M9,7,T9)	GG(a,b,c,d,M10,5,T25)
	연산 10	FF(d,a,b,c,M10,12,T10)	GG(d,a,b,c,M15,9,T26)
	연산 11	FF(c,d,a,b,M11,17,T11)	GG(c,d,a,b,M4,14,T27)
	연산 12	FF(b,c,d,a,M12,22,T12)	GG(b,c,d,a,M9,20,T28)
	연산 13	FF(a,b,c,d,M13,7,T13)	GG(a,b,c,d,M14,5,T29)
	연산 14	FF(d,a,b,c,M14,12,T14)	GG(d,a,b,c,M3,9,T30)
	연산 15	FF(c,d,a,b,M15,17,T15)	GG(c,d,a,b,M8,14,T31)
	연산 16	FF(b,c,d,a,M16,22,T16)	GG(b,c,d,a,M13,20,T32)

			제 3 라운드		제 4 라운드
	연산 1	HH(a,b,c,d,M6,4,T33)		II(a,b,c,d,M1,6,T49)
	연산 2	HH(d,a,b,c,M9,11,T34)		II(d,a,b,c,M8,10,T50)
	연산 3	HH(c,d,a,b,M12,16,T35)		II(c,d,a,b,M15,15,T51)
	연산 4	HH(b,c,d,a,M15,23,T36)		II(b,c,d,a,M6,21,T52)
	연산 5	HH(a,b,c,d,M2,4,T37)		II(a,b,c,d,M13,6,T53)
	연산 6	HH(d,a,b,c,M5,11,T38)		II(d,a,b,c,M4,10,T54)
	연산 7	HH(c,d,a,b,M8,16,T39)		II(c,d,a,b,M11,15,T55)
	연산 8	HH(b,c,d,a,M11,23,T40)		II(b,c,d,a,M2,21,T56)
	연산 9	HH(a,b,c,d,M14,4,T41)		II(a,b,c,d,M9,6,T57)
	연산 10	HH(d,a,b,c,M1,11,T42)		II(d,a,b,c,M16,10,T58)
	연산 11	HH(c,d,a,b,M4,16,T43)		II(c,d,a,b,M7,15,T59)
	연산 12	HH(b,c,d,a,M7,23,T44)		II(b,c,d,a,M14,21,T60)
	연산 13	HH(a,b,c,d,M10,4,T45)		II(a,b,c,d,M5,6,T61)
	연산 14	HH(d,a,b,c,M13,11,T46)		II(d,a,b,c,M12,10,T62)
	연산 15	HH(c,d,a,b,M16,16,T47)		II(c,d,a,b,M3,15,T63)
	연산 16	HH(b,c,d,a,M3,23,T48)		II(b,c,d,a,M10,21,T64)

kerberos

DES 암호화 기반의 제 삼자 인증 프로토콜

MIT대학교의 Athena 프로젝트에 의해 개발

클라이언트가 서버에 액세스하기 위한 kerberos 인증 절차

1. 클라이언트가 kerberos 인증 서버(AS)에게 TGT 요청

2. AS가 클라이언트에게 TGT를 반환한다.

3. 클라이언트가 티켓 허용 서버(TGS)에게 서버 티켓 요청

4. TGS가 클라이언트에게 서버 티켓을 반환

5. 클라이언트가 서버에게 서비스를 요청

6. 서버가 클라이언트에게 액세스를 허락

그림 7.25  kerberos 인증 절차