[정보] 암호학

1. 암호학

1.1 암호 알고리즘
1.1.1 암호 관련 용어
o 핵심가이드
- 암호시스템의 관련 용어와 정보보호 서비스의 개념 이해


(1) 암호시스템의 관련 용어
(가) 평문
송신자와 수신자 사이 주고받고자 하는 내용을 적은 일반적인 문장으로 모든 사람들이 이해할 수 있는 일반 형태의 문장을 말한다. 평문은 암호화의 대상이 되는 문장으로 한글이나 영어 등의 일반 언어로 작성된 문장이다.
(나) 암호문
송신자와 수신자 사이에 주고받고자 하는 내용을 제 3자가 이해할 수 없는 형태로 변형된 문장을 암호문이라 한다.

(다) 암호화
평문을 제 3자가 알 수 없도록 암호문으로 변형하는 과정을 말하며 일반적으로 암호화 과정은 송신자가 수행한다.
(라) 복호화
암호문을 다시 일반인들이 이해할 수 있는 평문으로 변환하는 과정을 말하며, 일반적으로 복호화 과정은 암호문을 수신한 수신자가 수행한다.
(마) 키
평문의 암호화 과정이나 암호문의 복호화 과정에 필요로 하는 파라미터로 암호 화키와 복호화 키로 나누어진다.
(바) 암호 알고리즘
암호 알고리즘은 암호화와 복호화에 사용되는 수학적인 함수이며, 암호 알고리즘은 암호화에 사용되는 암호화 알고리즘, 복호화에 사용되는 복호화 알고리즘이 있다.

(사) 암호해독
암호의 목적은 제3자의 도청으로부터 평문을 보호하는 데 있다. 암호해독은 암
호방식의 정당한 사용자가 아닌 제3자가 불법적으로 암호문으로부터 평문을 원복
하는 시도를 말하며, 암호해독은 암호화에 사용된 암호키를 찾거나 부대 정보를
이용하여 암호문으로부터 평문을 찾는 과정을 말하며 암호 공격이라고도 한다.
(아) 송신자와 수신자
통신망 상에서 비밀리에 평문을 주고받는 사람들을 말하며, 평문을 암호문으로
변경하여 수신자에게 전달하는 사람이 송신자이며 암호문으로부터 평문을 복호화
하는 사람이 수신자이다.
(자) 공격자
암호방식의 정당한 참여자가 아닌 자로 암호문으로부터 평문을 해독하려는 제
3자를 공격자라 한다. 특히, 송/수신자 사이의 암호통신에 직접 관여하지 않고 네
트워크상의 정보를 관찰함으로써 공격을 수행하는 공격자를 도청자라 한다.
(차) 암호체계 (암호시스템)
암/복호화 열쇠, 평문, 암호문을 포함한 암/복호 알고리즘을 말한다.




(2) 정보보호 서비스 개념


(가) 무결성
메시지전송 중 인가되지 않은 자, 혹은 인가되지 않은 방법으로 정보가 변조되지 않아야 하는 성질



(나) 기밀성
인가된 자만이 접근하여 취득하여야 하는 성질


(다) 부인봉쇄
송수신자가 송수신 사실에 대한 부인을 할 수 없도록 하는 성질


(라) 인증
인가된 자만이 정보 혹은 정보시스템에 접근하여야 하는 성질

-인증 : 어떤 사람이나 사물이 실제로 신고된 바로 그 사람(또 는 바로 그 것)인지를 판단하는 과정이다. 개별 또는 인터넷을 포함한 공공 네트워크 에서의 인증은 대개 로그온 시 암호의 사용을 통해 이루어진다. 암호를 알고 있는 사 람은 일단 믿을만한 사용자라고 간주된다.


- 인가(Authorization)는 정보를 전송하는 데 있어서 전송 주체가 되는 송신자와 수 신자가 정당한지를 확인하기 위한 절차를 말한다.



(마) 가용성
컴퓨터 시스템이 인가 당사자가 필요할 때 이용할 수 있게 하는 것


(바) 접근제어
특정 권한을 가진 자만 접근할 수 있도록 하는 것


(사) 전자서명
정보의 송/수신 과정에서 정보의 송신자와 수신자의 인증과 전송되는 정보의 무결성을 보장하는 성질


o 기밀성 - 오직 인가된 사람들에게만 정보가 열람되어야 한다는 것으로 위조와 가로채기 공격 유형에 취약하다.


o 무결성 - 송신측에서 수신측까지 정보의 변조 없이 전송되어야 한다는 것으로 변조 공격 유형에 취약하다.


o 가용성 - 권한이 있는 사용자의 경우 필요할 때 항상 업무 정보 및 서비스를 사용
할 수 있어야 한다는 것으로 차단 공격 유형에 취약하다.


1.1.2 암호 공격 방식
o 핵심가이드
- 각종 공격방식에 대한 방법의 분류와 이해
- 안전성의 개념 이해


(1) 보안공격
전송되는 메시지에 대한 불법적인 공격자의 위협
(가) 수동적 공격


1) 전송되는 파일을 도청
불법적인 공격자가 전송되는 메시지를 도중에 가로채어 그 내용을 외부로 노출시키는 공격 (메시지의 내용 공격)


2) 트래픽 분석
전송 메시지의 암호화로 도청을 통한 메시지 내용 파악이 불가능하더라도 메시지의 송신측과 수신측 신원의 파악 가능 (메시지 존재에 대한 공격 - 익명성 제공으로 방어)


(나) 능동적 공격


1) 메시지 변조
전송되는 메시지들의 순서를 바꾸거나 또는 메시지의 일부분을 다른 메시지 로 대체하여 불법적인 효과를 발생시키는 공격


2) 삽입공격
불법적인 공격자가 정당한 송신자로 가장하여 특정 수신자에게 메시지를 보내어 역시 불법적인 효과를 발생시키는 공격


3) 삭제공격
정상적인 통신시설의 사용, 관리를 방해하는 서비스 거부 공격, 특정 수신자 에게 전송되는 메시지의 전부 또는 일부가 공격자에 의해 삭제되는 것.


4) 재생공격
공격자가 이전에 특정 송신자와 수신자간에 행해졌던 통화내용을 도청하여 보관하고 있다가 나중에 재생하여 전송하는 공격


(2) 암호공격 방식
암호 해독자가 도청한 암호문으로부터 그에 해당하는 평문이나 비밀키를 도출하 는 수동적 공격법


(가) 암호문 단독 공격 (Ciphertext only attack)
암호 해독자는 단지 암호문 C만을 갖고 이로부터 평문 P이나 키 K를 찾아내는 방법으로 평문 P의 통계적 성질, 문장의 특성 등을 추정하여 해독하는 방법


(나) 기지 평문 공격 (Known plaintext attack)
암호 해독자는 일정량의 평문 P에 대응하는 암호문 C를 알고 있는 상태에서 해독하는 방법으로 암호문 C와 평문 P의 관계로부터 키 K나 평문 P를 추정하여 해하는 방법


(다) 선택 평문 공격 (Chosen plaintext attack)
암호 해독자가 사용된 암호기에 접근할 수 있어 평문 P를 선택하여 그 평문 P 에 해당하는 암호문 C를 얻어 키 K나 평문 P를 추정하여 암호를 해독하는 방법



(라) 선택 암호문 공격 (Chosen ciphertext attack)
암호 해독자가 암호 복호기에 접근할 수 있어 암호문 C에 대한 평문 P를 얻어 내 암호를 해독하는 방법


(3) 안전성 개념
주어진 암호 시스템의 안전성을 말할 때는 두 가지 관점이 있다. 첫 번째는 암호 시스템을 공격하기 위해 필요한 계산량이 매우 커 현실적으로 공격할 수 없는 경우 를 계산적으로 안전하다고 말한다. 둘째는 무한한 계산능력이 있어도 공격할 수 없는 경우를 무조건적으로 안전하다고 말한다. 암호 알고리즘 사용자가 해야 할 일은 다음 두 기준 중의 하나 또는 전부를 만족하는 알고리즘을 개발하는 것이다.
o 암호 해독 비용이 암호화된 정보의 가치 초과
o 암호 해독 시간이 정보의 유효 기간 초과




1.1.3 정보이론 [1급]
o 핵심가이드
- 엔트로피의 개념 이해
- 키 결정(판정)거리의 개념 이해


(1) 엔트로피
엔트로피는 1948년 Shannon에 의해 도입된 정보량 또는 정보의 불확실도를 측정
하는 수학적 개념이다. 즉, 유한개의 사건을 가지는 확률변수 X에 대해 확률 분포
p(X)를 알 때 발생하지 않는 사건의 불확실도를 엔트로피라 하며 H(X)로 나타낸다.


(가) 엔트로피의 정의
X를 유한 집합 위에서 정의된 확률 변수라 하고 확률 분포를 p(X)라 하자. 이


확률 분포에 대한 엔트로피 H(X)는 다음과 같이 정의된다.
H(X) =- Σ
n
i = 1
p i log 2p i
여기서 p i = p(X = x i )이다.
만약 모든 사건이 발생할 확률이 1n 이면 H(X) = log 2n이다.
또한 H(X)≥0 이고 H(X)=0이 필요충분조건은 적당한 i에서 p i =1이고 그 외에서는 p j=0인 경우이다.

(2) 키 결정(판정)거리
암호계 (P, C, K, E, D)에서 |C|=|P|이고 열쇠가 같은 확률로 주어졌다고 할 때
충분히 큰 n에 대하여 주어진 길이 n인 암호문 문자열에 대하여 기대되는 의사열쇠
의 개수  . 는
S n ≥ |K ||P |nR L-1 이다. 실제로 n이 증가하면 |K ||P |nR L-1은 0에 접근한다.
한편  . 이 0이 되는 n을 암호계의 키 거리라 하고 n 0으로 나타낸다. 즉, n 0은 충분한 계산시간이 주어진 경우에 유일한 열쇠를 찾을 수 있는 암호문의 평균량이다.




1.1.4 스트림 암호
o 핵심가이드
- 스트림암호의 정의
- 동기식/비동기식 스트림 암호의 특징 및 비교
- 스트림암호의 암호화 방법 [1급]
- LFSR의 특징과 비선형 결합논리에 대한 이해 [1급]
- 안전성 개념(선형복잡도, 주기, 상관관계 공격, 랜덤 특성, 대수적 공격) [1급]


(1) 스트림 암호의 개념
평문과 같은 길이의 키 스트림을 생성하여 평문과 키를 비트단위로 XOR하여 암호문을 얻는 방법이다.


(2) 스트림 암호 종류
(가) 동기식 스트림 암호


1) 암호화와 복호화에서 상호 동기화가 필수
2) 전송도중 변조되어도 후속 암호문에 오류의 영향이 파급되지 않음
3) 의도적인 변조가 복호화 단계에서 검출 불가



(나) 자기 동기식 스트림 암호
1) 암호문이 전송도중 변경되어도 자기 동기화가 가능
2) 변조된 암호문이 후속 암호문 복호화에 사용되지 않아 오류파급이 제한적
(3) 선형 귀환 시프트 레지스터(LFSR)
LFSR을 이용하면 유한상태머신으로 달성할 수 있는 최대 주기의 수열을 얻을 수
있으며, 수학적인 분석이 용이하다. 특히 선형 복잡도라는 측도를 사용하면 다음에
출력될 값을 예측하기 위해 필요한 수열의 양을 계산할 수 있는 장점이 있다. LFSR
의 길이가 작으면 쉽게 해독될 수 있다. 따라서 주어진 수열을 표시할 수 있는
LFSR들의 길이 중 최소의 길이를 선형 복잡도라고 정의한다.
......
Sk-2 ...... Output
ak-1 ak-2 a1 a0
Sk-1 S1 S0
(그림 4-1) LFSR의 동작도
o si
= c1si-1 + c2si-2 + … + crsi-r mod 2, i≥r
LFSR의 초기상태가 [sr-1, sr-2,…,s1,s0]이면 LFSR는 다음과 같은 선형 점화식을 만족하는 수열 s0, s1, s2 ….을 생성한다.
o 쉬프트 레지스터의 연속적인 상태는 주기 p를 가진다. (p≤2r)
o r개의 플립플롭으로 구성된 LFSR이 생성하는 수열의 최대 주기는 p = 2r-1이다.


(가) 비선형 결합논리
LFSR을 단독으로 사용하는 것은 쉽게 해독되기 때문에 출력 수열을 비선형 결합하여 스트림 암호를 구성한다.
LFSR을 이용한 스트림 암호는 크게 두 가지 형태로 볼 수 있는데 하나는 출력 수열만을 비선형 결합하는 것이고 다른 하나는
LFSR의 동작을 제어함으로써 선형 복잡도가 큰 수열을 얻는 방법이다.


1) 비선형 여과 생성기(Nonlinear Filter Generator)
비선형 여과 생성기는 하나의 LFSR과 비선형 함수로 구성된다. 비선형 함수는 LFSR의 각 단에 있는 내용을 변수로 하여 출력을 생성한다.
2) 비선형 결합 생성기(Nonlinear Combination Generator)
비선형 결합 생성기는 여러 개의 LFSR과 비선형함수로 구성된다. 동작방식은 LFSR들을 동시에 동작시킨 후 각각의 출력을 비선형 함수의 입력 변수로 하여 최종 출력수열을 얻는다.


(나) 시각 제어 논리
하나의 LFSR의 출력에 의해 다른 LFSR의 동작을 제어하는 논리를 통칭하여 시작제어 논리라 한다.
1) Cascade Generator
n개의 LFSR로 구성되며 i번째 LFSR의 출력과 그 전단의 출력의 XOR로 i+1 번째 LFSR동작을 제어하는 방식
2) Stop and Go Generator
두개의 LFSR로 구성되는데 하나의 LFSR출력이 ‘0’인 경우에는 다른 LFSR을 동작시키지 않고 ‘1’인 경우에만 LFSR을 동작시키는 방식
3) Alternating Step Generator
세 개의 LFSR을 이용하여 출력이 랜덤하지 않은 문제점을 효과적으로 극복 하였다. LFSR1의 출력수열이 ‘0’이면 LFSR2를 동작시키고, ‘1’이면 LFSR3를 동 작시켜 LFSR2의 출력과 LFSR3의 출력을 XOR하여 최종출력을 결정한다.
4) Shrinking Generator
기존의 시각 제어 논리는 LFSR의 작동을 제어하였지만 Shrinking Generator 는 출력을 제어한다. LFSR1의 출력이 ‘0’이면 LFSR2의 출력을 내보내지 않고, ‘1’인 경우에만 LFSR2의 출력을 최종 수열로 한다.


(다) 상관관계 공격과 Summation Generator
상관관계 공격과 선형복잡도 문제를 동시에 해결할 수 있는 수단으로 Summation Generator가 제안되었다. Summation Generator는 두개의 LFSR 출 력을 정수로 고려하여 더하고 Carry는 피드백 시키는 형태이다.


(4) 키 수열의 안전성
(가) 키 수열 주기의 길이
주기를 가지기 때문에 수열의 일부가 노출되면 위험하다. 안전한 키 수열의 주 기는 스트림 암호가 적용되는 응용분야에 전적으로 의존한다.


(나) 유사-난수열의 조건
키 수열은 무작위로 선정된 진정한 난수열이어야 예측이 불가능하다.

o Golomb의 공리계
( ) (2 1)(2 1) 1
1
0
=
. .
=Σ.
=
+
p
i
i i t
p
C(t) 2S 2S if t = 0, K if 1 ≤ t ≤ p-1
C t S S (그림 4-2) Golomb의 공리계
- 매 주기마다 발생되는 ‘1’의 개수와 ‘0’의 개수의 차이는 기껏해야 1이다.
- 매 주기마다 길이가 짧은 연속적인 값들이, 길이가 긴 연속적인 값들보다
더 자주 나타난다.
- P의 주기에서 두 가지 값을 가지는 자기상환함수 C(t)가 존재한다.


(다) 상관공격
비선형함수에 의하여 출력되는 열쇠이진수열의 주기와 복잡도는 LFSR의 크기 와 비선형함수에 의존된다. 그러나 열쇠이진수열이 어떤 LFSR에 의한 출력수열과 상관관계가 있으면 이 성질을 이용하여 열쇠를 쉽게 찾을 수 있는 해독법이 있 다. 이와 같은 해독법을 상관공격이라 한다.


(라) 랜덤 특성
스트림 암호 체계에서 보안을 유지하기 위해서는 적어도 다음 세 조건이 만족 되어야 한다.


1) 키를 선택할 수 있는 방법의 가짓수를 충분히 크게 함으로써 암호해독으로 하여금 키 전부를 시험해 볼 수 없도록 하여야 한다.


2) 보안이 유지되기 위해서는, 생성되는 무한 이진수열들의 주기를 알 수 있어 야 한다. 이 값을 아는 경우에는 이보다 짧은 길이의 평문만을 해독하면 되 기 때문이다.


3) 암호문은 반드시 ‘랜덤' 하여야 한다.
어떤 무한 이진수열이 랜덤하다라는 말은, 이 수열의 유한개의 연이은 항들 만으로는 그 다음 항을 예측할 수 없음을 뜻한다. 물론, finite state machine에 의하여 생성되는 수열은 진정한 의미에서 랜덤하지 않다. 실제로, 이러한 수열 의 항들은 주기적으로 반복되고, 따라서 이 수열의 순환마디로부터 모든 항을 알 수 있다. 그러나, 수열의 주기가 충분히 큰 경우에는 이 수열의 난수성



4)(randomness)을 정의할 수 있다. Golomb은 주기를 갖는 무한 이진수열의 난수성에 관한 공리계 를 설정하였는데, 위의 세 공리 1), 2), 3)를 만족시키는 수열을 흔히 G-random수 열 이라고 한다.
앞에서 말한 좋은 난수성을 가진 무한 이진수열을 생성하는 방법에는 여러 가 지가 있으나, 거의 모든 방법이 Shift register를 이용하고 있다. 이와 같이 Shift register를 이용하는 주된 이유는, 비교적 싸고 손쉽게 구입할 수 있고 Shift register에 의하여 생성되는 수열의 성질을 수학적으로 연구할 수 있기 때문이다.


(5) FCSR
Summation Generator의 정수덧셈을 확장시켜 LFSR의 동작에서 XOR대신에 정수 덧셈을 하는 쉬프트 레지스터가 FCSR이다. FCSR을 스트림 암호의 기본요소로 사용 하면 선형 복잡도 측면 주기의 반 정도가 되는 장점이 있다.


(6) 대수적 공격 <최근 동향> [1급]
대수적 공격은 알려진 입출력 쌍을 가지고 내부 알고리즘의 기본 대수 방정식을 이용하는 방법으로, 과포화된 다변수 연립 방정식을 통하여 변수의 값을 얻고 이를 이용하여 키를 복구해내는 방법이다. 대수적 공격은 초기에 공개키 알고리즘인 HFE에 적용되었고, 이후 SERPENT, AES와 같은 대수적 성질을 가지는 블록 암호 의 분석에 적용되었다. 이 공격법은 이후 블록암호 보다 적용이 용이한 LILI-128, E0 등의 여러 스트림 암호의 분석에 사용되었다.


(가) 대수적 공격의 특성
1) 주어진 알고리즘에 대한 대수적 방정식들이 과포화(overdefined, 방정식의 개수가 변수의 개수가 많은 경우)라면 대수적 공격은 확률 1로 내부 변수 (초기 상태 혹은 마스터 키)의 값을 찾을 수 있다.


2) 대수적 공격의 복잡도는 오직 내부 변수의 개수에만 의존하고 변수 값을 구 하기 위한 복잡도는 변수 개수의 증가에 따라 지수적으로는 증가하지는 않 는다.


(나) 대수적 공격을 효과적으로 적용하기 위한 문제
1) 낮은 차수의 대수적 방정식을 찾는 문제
2) 연립 방정식을 효율적으로 계산하여 해를 찾는 문제
(다) 대수적 공격의 대응책
대수적 공격에 안전하기 위해서는 변수 대 방정식의 비가 높아야 하고, 이를
달성하기 위해서는 내부 변수는 높은 비선형 함수를 이용하여 적절히 갱신되어야
한다. 또한 내부 변수의 갱신 비율이 높으면 높을수록 라운드 수가 증가함에 따
라 변수 대 방정식의 수가 감소하지 않는다.
(라) 대수적 공격에 안전한 소프트웨어 구현에 적합한 스트림 암호의 설계 시 고
려해야할 사항
1) 키 스트림의 출력 길이
변수 대 방정식의 비가 출력의 길이가 길면 길수록 감소한다. 라운드 당 출
력 길이가 작을수록 대수적 공격에 보다 안전할 수 있으므로, 라운드 당 출력
길이의 사이즈를 신중히 고려해야 한다. 출력의 길이가 많아지면 많아질수록
방정식 대 변수의 비율이 점점 줄어들어 과포화 상태 혹은 비율 1의 값에 수렴
할 수 있어 대수적 공격에 대한 내성이 작아질 수 있다.
2) 비선형 방정식의 형태
음함수(Implicit Function)형태의 방정식은 높은 차수의 변수를 직접적으로 사
용하지 않기 위해서는 추가적인 변수가 필요한 반면, 양함수(Explicit Function)
의 경우에는 이러한 추가적 변수가 필요하지 않다. 따라서 대수적 차수가 같더
라도 음함수 형태의 방정식이 사용되었다면 양함수에 비해 보다 많은 내부 변
수를 갖게 되어 대수적 공격에 내성을 가지게 되므로, 비선형 함수도 신중히
고려하여 설계되어야 한다.
3) 내부 변수의 위치 및 갱신 과정
내부 변수들이 갱신되어 변하는 위치 등도 대수적 공격의 안전성에 영향을
준다. 구체적으로 설명하자면, 내부 변수를 이용하여 출력 스트림을 생성할 때,
내부 변수의 값을 그대로 출력 할 경우 내부 변수의 값이 그대로 노출되어 대
수적 공격에 대한 내성이 작아질 수 있다. 또한 내부 변수를 통해 출력 스트림
생성시 내부 변수의 위치가 주기적인 간격만을 이용하여 생성하거나 전체 내부
변수 값을 이용하지 않고 특정 부분의 변수만을 이용할 경우, 내부 변수의 주
기적 성질을 이용한 공격 등에 취약할 수 있다. 따라서 알고리즘의 설계시 내
부 변수의 위치 및 갱신 과정을 신중히 선택해야 한다.




1.1.5 블록 암호
o 핵심가이드
- 블록암호의 개요 및 구조
- 블록암호 운영모드의 이해
- 블록암호 알고리즘들의 구조와 특성, 안전성, 암/복호화 과정, 키의 크기, 사용된
연산, 개발된 국가와 개발년도

- 330 -
(1) 블록암호의 개요
암호문을 만들기 위해 평문을 일정한 단위로 나누어서 각 단위마다 암호화 과정
을 수행하여 블록단위로 암호문을 얻는 대칭 암호화 방식이다.
[표 4-1] 대칭키 암호방식
대칭키 암호방식
암호키 관계 암호화키 = 복호화키
암호화 키 비밀
복호화 키 비밀
암호 알고리즘 비밀/공개
비밀키 수 n C 2
안전한 인증 곤란
암호화 속도 고속
(2) 블록암호 알고리즘 구조
블록암호 알고리즘은 비밀키를 이용하여 고정된 크기의 입력블록을 고정된 크기
의 출력블록으로 변형하는 암호 알고리즘에 의해 암/복호화 과정을 수행하며, 이때
출력블록의 각 비트는 입력블록과 키의 모든 비트에 영향을 받는다.
블록 암호는 주로 단순한 함수를 반복적으로 적용함으로써 암호학적으로 강한 함
수를 만드는 과정으로 개발된다. 이때 반복되는 함수를 라운드 함수라 하고 라운드
함수에 작용하는 키를 라운드 키라고 한다.
일반적인 경우 키를 입력하여 라운드 키를 발생하여 사용하는데 이러한 과정을
키 스케줄 이라 부른다. 키 스케줄은 입력된 키의 모든 비트를 균등하게 사용하여
라운드 키를 독립인 것처럼 발생시켜야 한다.
(가) Feistel 구조
Feistel구조는 3라운드 이상이며, 짝수 라운드로 구성된다. 이러한 Feistel 구조
는 라운드 함수와 관계없이 역변환이 가능하며(즉, 암/복호화 과정이 같음), 두
번의 수행으로 블록간의 완전한 확산(diffusion)이 이루어지며, 알고리즘의 수행속
도가 빠르고, 하드웨어 및 소프트웨어구현이 용이하고, 아직 구조상에 문제점이
발견되고 있지 않다는 장점을 지니고 있다.
Feistel 구조는 입력을 좌우 블록으로 분할하여 한 블록을 라운드 함수에 적용
시킨 후의 출력 값을 다른 블록에 적용하는 과정을 좌우블록에 대해 반복적으로
시행하는 방식으로, 라운드 키가 역순으로 작용한다는 점을 제외하면 암/복호화
과정이 동일하고 라운드 함수에 대한 제약 조건이 없어 DES를 비롯한 대부분의
블록암호에 채택되어 사용되고 있다.
Feistel 구조는 입력 n비트를 두개의 블록 ( L 0 , R 0 )으로 나누어 라운드 함수를
F, 라운드 키를 Ki라 할 때, i번째 라운드 과정이 다음과 같다.
o Li
= Ri
o Ri
= Li-1 . Fi(Ri-1, Ki)
(나) SPN 구조
SPN 구조는 라운드 함수가 역변환이 되어야 한다는 등의 제약이 있지만 더 많
은 병렬성(parallelism)을 제공하기 때문에 암/복호화 알고리즘의 고속화가 요구
되고 최근의 컴퓨터 프로세스(CPU)가 더 많은 병렬성을 지원하는 등의 현 추세
에 부응하는 방식이라 할 수 있다.
SPN은 입력을 여러 개의 소블록으로 나누고 각 소블록을 S-box로 입력하여 대
치시키고 S-box의 출력을 P-box로 전치하는 과정을 반복한다.
(다) Feistel구조와 SPN구조를 사용하는 알고리즘
[표 4-2] Feistel구조와 SPN구조를 사용하는 알고리즘
Feistel 구조를 사용하는 알고리즘 SPN 구조를 사용하는 알고리즘
DES SAFER
LOKI IDEA
CAST SHARK
Blowfish Square
MISTY SRYPTON
RC5, RC6, Rijndael
CAST256 SAFER+
E2 Serpent
Twofish *
Mars *
(3) 블록암호 요소의 특징
블록암호 알고리즘을 특징하는 요소로는 다음과 같은 것이 있으며, 이러한 요소
에 의해 전체 블록암호의 안전성이 결정된다.
(가) 블록 크기
입출력 블록의 비트수로, 일반적으로 더 클수록 안전하다고 보지만, 암/복호화
과정에서 시간이 더 걸린다. 주로 64비트가 널리 쓰였지만, 최근에는 128바이트를
채택하고 있다.
(나) 키 크기
비밀키의 비트수로, 일반적으로 더 클수록 이 역시 라운드키를 생성할 때 시간
이 더 걸린다. DES는 56비트를 사용하였는데 작은 키의 크기로 인하여 안전성에
큰 문제가 되었고, 최근에는 128비트나 그 이상을 주로 사용한다.
(다) 라운드 키 생성
비밀키로부터 각 라운드에 사용할 키를 생성하는 과정으로, 유사시에 라운드
키가 누출되더라도 비밀키는 안전해야 한다.
(라) 라운드 함수
암/복호화를 수행하는 핵심함수로 다양한 암호분석을 거쳐 안전하게 만들어 져
야 한다.
(마) 라운드 수
한 번의 암/복호화를 위해 반복하는 라운드 함수의 횟수로, 많을수록 더 안전
하다고 보지만 암/복호화 과정에서 시간이 더 걸린다. 근본적으로 한 번의 라운
드 함수로 충분한 안전성을 확보할 수는 없기에 라운드 함수에 대한 다양한 암호
분석을 통해 충분한 안전성을 얻을 수 있도록 라운드 횟수를 결정한다.
(4) 블록암호의 사용방식
(가) 전자코드북 모드 (Electronic Code Bool Mode)
ECB모드는 가장 단순한 방식으로 각 블록을 독립적으로 암호화 한다. 이 방식
은 동일한 평문블록은 동일한 암호문을 생성하는데 이는 안전성에 있어서 이런
점은 바람직하지 않다. 이러한 이유로 ECB모드는 잘 사용하지 않는다.
1) 암호화 : C i = E k ( P i )
2) 복호화 : P i = D k (C i )
(나) 암호블럭연결 모드 (Cipher Block Chaining Mode)
CBC모드는 초기치를 암호화한 값과 평문 블럭을 XOR하여 암호문 블럭을 생성
하고 그 암호문을 초기치로 하여 다시 암호화한 값과 평문 블록을 XOR하여 암호
문블록을 반복하여 생성하는 방식이다. 암호화에서는 특정 입력이후로 영향을 미
치지만, 복호화에서는 특정 암호문의 오류가 계속적으로 이후에 영향을 미치지는
않는다는 특징이 있다.
1) 암호화 : C i = E k (C i - 1.P i )
2) 복호화 : P i = D k (C i ).C i - 1
(다) 암호피드백 모드 (Cipher FeedBack Mode)
CFB모드는 초기치를 암호화한 값과 평문 블록을 XOR하여 암호문 블럭을 생성
하고 그 암호문을 초기치로 하여 다시 암호화한 값과 평문 블록을 XOR하여 암호
문블록을 반복하여 생성하는 방식이다. 암호화에서는 특정 입력이 이후로 영향을
미치지만, 복호화에서는 특정 암호문의 오류가 계속적으로 이후에 영향을 미치지
는 않는다는 특징이 있다.
1) 암호화 : C i = P i .E k ( I i ) < i.....r >, I i + 1 = (I i<< r) .( 0..0∥C i )
2) 복호화 : P i = C i .E k ( I i ) < i.....r >, I i + 1 = (I i<< r) .( 0..0∥C i )
(라) 출력피드백 모드(Output FeedBack Mode)
OFB모드는 초기치 Ⅳ를 암호화 하고 그 값을 다시 암호화하는 과정을 반복함
으로써 생성된 수열과 평문 수열을 XOR하여 암호문을 생성하는 방식으로, 주로
블록암호 시스템을 스트림암호 시스템처럼 사용하고자 할 때 이용된다. 이 방식
에서 암호문의 오류는 복호화 과정에서 대응되는 한 블록에만 영향을 비치므로,
영상이나 음성 같은 디지털 신호화한 아날로그 신호에 많이 사용된다.
1) 암호화 : I i = E k ( I i - 1 ),C i = P i .I i
2) 복호화 : C i = P i .E k ( I i ), P i = C i .I i
(마) 카운터 모드(Counter Mode)
Counter모드는 초기치 Ⅳ와 Ⅳ+1, Ⅳ+2,....을 암호화하여 생성된 평문수열을
XOR하여 암호문 블록을 생성하고 그 암호문을 기초로 하여 다시 암호화한 값과
평문블록을 XOR하여 암호문블록을 반복하여 생성하는 방식이다. 암호화에서는
특정 입력이 이후로 영향을 미치지만, 복호화 할 때 Ⅳ가 주어지면 미리 계산할
수 있어 평문이 주어지면 바로 암호문을 만들 수 있다는 장점이 있지만, 동일한
비밀키와 Ⅳ를 반복하여 사용할 경우 안전성에 문제가 생긴다는 약점이 있다.
1) 암호화 : C i = P i .E k ( I i ), P i = I i + 1+ 1
2) 복호화 : P i = C i .E k ( I i ),P i = I i + 1+1
(5) 블록암호 알고리즘 종류


[표 4-3] 블록알고리즘 종류와 특징
개발
국가
개발
년도
특징
블록
크기
키의
길이
라운
드수
DES 미국 1972년 NIST에서 표준으로 공표(1977년) 64 56 16
IDEA 유럽 1990년 PGP채택 64 128 8
Rijndael 벨기에 2000년 AES알고리즘으로 선정 128
128,192,
256
10,12,
14
SEED 한국 1999년 한국표준 블록암호 알고리즘 128 128 16
CRYPTON 한국 1998년 128 0-256 12
RC5 미국 1994년 알고리즘이 간단하여 속도가 빠름 64 0-256 16
FEAL 일본 1987년 S/W구현에 적합 64 64 4
MISTY 일본 1996년 차분/선형공격에 안전성증명구조 64 128 8
SKIPJACK 미국 1990년 Fortezza카드에 사용 64 80 32


(가) DES의 암/복호화 과정
현재까지 DES는 가장 널리 사용되어 왔지만 열쇠의 길이가 짧고, 컴퓨터 속도
의 개선과 암호해독기술의 발전으로 오늘날 더 이상 DES를 안전하다고만 생각하
지 않게 되었다. 최근 DES를 보완하는 끊임없는 연구로 많은 블록 암호들이 개발
되어 공개되어왔으며 또한 DES가 공모 되었던 것과 같이 새로운 암호 AES를 선
정하였다.
DES는 64비트의 평문을 46비트의 암호문으로 만드는 블록 암호 시스템으로 64
비트의 키를 사용한다. 64비트의 키(외부 키) 중 56비트는 실제의 키(내부 키)가
되고 나머지 8비트는 검사용 비트로 사용한다. 또한 DES의 안전성을 증가시키기
위하여 키의 길이를 두 배 즉, 128비트, 십진수 16개를 키로 선택한 변형된 알고
리즘을 일반적으로 사용한다. DES는 16라운드(Round)의 반복적인 암호화 과정을
갖고 있으며, 각 라운드마다 전치(Transposition) 및 대치(Substitution)의 과정을
거친 평문과 56비트의 내부키에서 나온 48비트의 키가 섞여 암호문을 만든다. 복
호화는 암호화 과정과 동일하나 사용되는 키만 역순으로 작용하는 것이다. DES는
컴퓨터 성능의 발달로 인해 보안성이 약화되어 3DES를 사용하고 있다.
1) 암호화 과정
o 64비트의 평문 P에 64비트 대칭키 K가 적용되어 세 단계를 거침
o 64비트 평문은 초기치환을 거쳐 재배열된다.
o 대체와 치환의 16회 반복
o 16회 반복으로 생성된 LE16과 RE16의 위치 교환 후 역초기치환이 적용되어
64비트 암호문이 생성됨

2) 복호화 과정
o 부분키를 역으로 적용 시키는 것을 제외하면 암호화 과정과 동일
o R i - 1 = L i
o L i - 1 = R i .f( R i - 1, k i) = R i.f(L i,K i )


(나) 3DES
DES의 56비트라는 짧은 키 길이로 인한 안전성 문제를 해결하기 위한 대안으
로 3개의 키로 DES를 3회 반복하여 사용하는 Triple DES를 사용한다. 3DES는 속
도가 DES보다 3배 정도 느리다는 단점에도 불구하고, 기존의 DES를 이용하여 쉽
게 구현되며 DES의 안전성 문제를 해결하는 장점으로 인하여 여러 표준에서 사
용되었다. 서로 다른 키로 DES 암호 방식을 반복적용하면 외형상으로는 2배의 키
길이지만 메모리 용량이 충분하면 57비트 효과밖에 얻지 못한다. 그러나 두개의
암호키를 사용하여 첫 번째 키 K1으로 암호화하고 다시 두 번째 키 K2로 복호화
한 다음 또다시 첫 번째 K1로 암호화하면 강한 암호를 얻을 수 있다.


(다) IDEA
스위스에서 1990년 Xuejia Lai, James Messey에 의해 만들어진 PES(Proposed
Encryption Standard)는 이후 1992년 IDEA(International Data Encryption
Algorithm)로 이름을 고쳐 제안하였고, 블럭 초당 177Mbit의 처리가 가능한 빠른
암호화 방법이다. IDEA은 128비트 키, 8라운드, 64비트 블록암호이며 주된 세 가
지 연산은 XOR, add mod 216, multiply mod 216+1이다. RSA와 더불어 PGP에
사용되는 방식이기도 하다.
IDEA는 블록 암호 알고리즘으로써 64비트의 평문에 대하여 동작하며, 키의 길
이는 128비트이고, 8라운드의 암호 방식을 적용한다. 또한 암호화와 복호화에 동
일한 알고리즘이 사용된다. IDEA 알고리즘은 상이한 대수 그룹으로부터의 세 가
지 연산을 혼합하는 것으로 이들은 모두 하드웨어나 소프트웨어로 쉽게 구현될
수 있다. IDEA는 16비트 단위 연산을 사용하여 16비트 프로세스에 구현이 용이
하도록 설계되었다.


1) 암호화 과정 [1급]
다른 암호화 방식과 마찬가지로 암호화 함수는 암호화될 평문과 키의 두 가
지 입력을 갖는다. 이 경우 평문은 64비트이고, 키는 128비트이다. IDEA알고리
즘은 마지막 변환함수에까지 8개의 라운드 혹은 반복들로 구성된다. 이 알고리
즘은 입력을 4개의 16비트 서브블록으로 분해한다. 각각의 반복과정은 4개의
16비트 서브블록들을 입력받고, 4개의 16비트로 된 결과블록을 생성한다. 최종
변환은 또한 4개의 16비트 블록들을 생성하는데, 이것들은 다시 64비트암호문
을 형성하기 위해 연결된다. 각 반복들은 전체 52개의 서브키에 대하여 6개의
16비트 서브키를 이용하는 반면 최종변환은 4개의 서브키를 사용한다.


2)복호화 과정 [1급]
복호화 과정은 암호화 과정과 본질적으로 같은 작업이다. 복호화는 같은
IDEA구조로서 암호문을 입력으로 사용함으로써 얻어진다. 그러나 서브키의 선
택에 있어서 다르다. 복호화 서브키 U1, ..., U52는 암호화 서브키로부터 유도된
다.




(라) SEED
SEED는 한국 정보보호센터가 1998년 10월에 초안을 개발하여 공개검증과정을
거쳐 안전성과 성능이 개선된 최종수정안을 1998년 12월에 발표하였다. 1999년 2
월 최종결과를 발표하고 128비트 블록암호표준(안)으로 한국통신기술협회에 제안
하였다. SEED알고리즘의 전체 구조는 변형된 Feistel구조로 이루어져 있으며, 128
비트 열쇠로부터 생성된 16개의 64비트 회전열쇠를 사용하여 총 16회전을 거쳐
128비트의 평문 블록을 128비트 암호문 블럭으로 암호화하여 출력한다. 이 알고
리즘의 전체 구조는 블록의 길이만 다를 뿐 DES의 구조와 같으며, 평문 블럭 128
비트를 64비트 블록을 L0과 R0로 나누어 DES와 같은 단계를 거쳐 16회전을 하여
최종출력비트를 얻는다.


1) 암호화 과정 [1급]
o SEED의 평문 128비트는 좌측 64비트 L0(64)와 우측 64비트 R0(64)로 나뉘어
입력된다.
o 우측 64비트 R0(64)는 암호화 보조키 64비트 K1(64)와 함께 f함수에 입력된
다.
o f함수의 출력 64비트 f( R 0 ( 64), K 1 )은 좌측 64비트 L0(64)와 비트별로 XOR
를 거쳐 R1(64)가 된다.
o 다시 좌측 64비트 L1(64)와 암호화 보조키 K2가 f함수에 입력된다.
o f 함수의 출력 64비트 f( R 1 ( 64), K 2 )는 좌측 64비트 L1(64)와 XOR를 거쳐
R2(64)가 된다.


(마) AES (Rijndael)
1997년 미국의 NIST는 기존의 DES를 대신할 수 있는 새로운 암호 알고리즘
(AES, Advanced Encryption Standard)을 공모하였다. 기존의 3중 DES보다 안전
하면서 128비트 이하의 키를 사용해야 한다는 조건에도 불구하고, 약 15개의 알
고리즘이 응모하였다. 2000년 안전성분석과 구현 효율성을 검증받은 5개의 후보
가운데 J. Daemen과 V. Rijmen이 제출한 Rijndael이 차세대 AES로 선정되었다.
AES의 암호화 과정의 각 라운드는 비 선형성을 갖는 S-Box를 적용하여 바이트
단위로 치환을 수행하는 SubBytes( ) 연산, 행단위로 순환 시프트를 수행하는
ShiftRows( ) 연산, Diffusion을 제공하기 위해 열 단위로 혼합하는 MixColumns(
) 연산과 마지막으로 라운드 키와 State를 XOR하는 AddRoundKey( ) 연산으로
구성된다.
[표 4-4] AES의 라운드 수(Nr)
키 길이
(Nk Words)
블록 길이
(Nb words)
라운드 수
(Nr)
AES-128 4 4 10
AES-192 6 4 12
AES-256 8 4 14
사용하는 암호화 키의 길이에 따라, 암/복호화 과정에 필요한 라운드 수는 아
래의 표와 같다.
1) 암호화 과정
o AES의 암호화 과정은 DES와 달리, 첫 번째 라운드를 수행하기 전에 먼저
초기 평문과 라운드 키의 XOR연산을 수행하므로, 암호화 과정에 필요한 전
체 라운드 키의 개수는 Nr+1개가 된다. 그리고 암호화의 마지막 라운드에
서는 MixColumns( )연산을 수행하지 않는다는 특징이 있다.
2) 복호화 과정
o AES의 복호화 과정은 암호화 과정을 역변환으로 InvSubBytes( ) 연산,
InvShiftRows( ) 연산, InvMixColumns( ) 연산, AddRoundKey( ) 연산으로
구성된다. 암호화 과정에서 마지막 라운드는 이전의 라운드들과 달리
MixColumns( ) 연산을 포함하지 않으므로, 복호화 과정의 첫 번째 라운드
가 이후의 라운드들과 달리 InvMixColumns( ) 연산을 포함하지 않는다.
복호화 과정의 첫 번째 라운드를 제외한 각 라운드는 AddRoundKey( ) 연
산, InvMixColumns( ) 연산, InvShiftRows( ) 연산, InvSubBytes( ) 순서로
연산을 수행하며 라운드 키는 암호화의 역순으로 Nr번째 라운드 키부터 사
용한다.




1.1.6 블록 암호 공격 [1급]
o 핵심가이드
- 각 공격법에 대한 기본개념 이해
(1) 차분공격에 대한 기본개념(Differental Crptanalysis)
1990년 Biham과 Shamir에 의하여 개발된 선택된 평문공격법으로, 두개의 평문
블록들의 비트의 차이에 대하여 대응되는 암호문 블록들의 비트의 차이를 이용하여
사용된 암호열쇠를 찾아내는 방법이다.
(2) 선형공격에 대한 기본개념(Linear Cryptanalysis)
1993년 Matsui에 의해 개발되어 알려진 평문 공격법으로, 알고리즘 내부의 비선
형 구조를 적당히 선형화시켜 열쇠를 찾는 방법이다.
(3) 전수공격법(Exhaustive key search)
1977년 Diffie와 Hellman이 제안한 방법으로 암호화할 때 일어날 수 있는 모든
가능한 경우에 대하여 조사하는 방법으로 경우의 수가 적을 때는 가장 정확한 방법
이지만, 일반적으로 경우의 수가 많은 경우에는 실현 불가능한 방법이다.
(4) 통계적 분석(Statistical analysis)
암호문에 대한 평문의 각 단어의 빈도에 관한 자료를 포함하는 지금까지 알려진
모든 통계적인 자료를 이용하여 해독하는 방법이다.
(5) 수학적 분석(Mathematical analysis)
통계적인 방법을 포함하며 수학적 이론을 이용하여 해독하는 방법이다.


1.1.7 인수분해 기반 공개키 암호
o 핵심가이드
- 공개키 암호시스템의 장단점
- 공개키 알고리즘들의 암호학적 안전성, 알고리즘 안전성, 변수선정 방법, 암/복호
화 알고리즘의 키 생성 및 구성
- 이차잉여류 문제 [1급]
(1) 공개키 알고리즘의 특징
데이터의 암호화에서는 공개키가 사용되고, 복호화에서는 비밀키가 사용되는 암
호시스템으로 이 시스템은 암호화 조작이 용이하고 복호화에는 방대한 조작이 필요
하지만 어떤 복호화 키가 주어지면 용이하게 역변환이 가능하게 되는 일방향성 함
수의 개념이 사용되고 있다. 공개키 암호시스템은 다수의 정보교환자 간의 통신에
적합하고 전자서명을 용이하게 실현할 수 있는 특징이 있다.
[표 4-5] 공개키 암호 암호방식
공개키 암호방식
암호키 관계 암호화키 ≠ 복호화키
암호화 키 공개
복호화 키 비밀
암호 알고리즘 공개
비밀키 수 2n
안전한 인증 용이
암호화 속도 저속
(2) 소인수 분해를 이용한 공개키 암호
(가) 소인수분해 문제
소인수 분해란 하나의 정수를 소인수로 분해하는 것을 말한다. 충분히 큰 두개
의 소수를 곱하는 것은 쉽지만, 이들 결과를 소인수 분해한다는 것은 계산적으로
매우 어렵다. RSA 등과 같은 공개키 암호 알고리즘들은 이렇게 소인수 분해의
어려움에 기반을 두고 설계되었다.


(나) RSA 암호
RSA는 1978년 Rivest, Shamir 그리고 Adleman에 의해 설계된 암호로써 Diffie
와 Hellman이 제안한 공개키 암호시스템에 대한 개념을 가장 충실히 반영한 것
으로 소인수 분해의 어려움에 그 기반을 둔 공개키 암호이다. RSA의 암호 방식
의 안전성은 소수 p와 q에 달려 있다. RSA의 암호방식의 안전성을 보장받기 위
한 소수 p와 q의 선택조건과 공개 암호화키와 비밀 복호화키의 조건들이 부가적
으로 필요하다.


1) 암/복호화 과정
o 준비과정
- 수신자 B가 공개되지 않은 홀수인 두 소수 p B , q B 의 곱 n B = p B. q B를 구
한다.
- 수신자 B는 φ( n B ) = (p B -1)(q B-1)을 구한다.
- 수신자 B는 n B와 서로서인 e B를 선택하고 d B e B≡1 mod φ ( n B )를 만족
하는 d B를 구한다.
- 수신자 B는 위에서 구한 ( n B , e B )를 공개한다.

o 암호화 과정
- 송신자 A는 평문 P와 공개키를 이용하여 C≡P
d b mod n B를 계산하여 암
호문 C를 얻어 수신자 B에게 송신한다.
o 복호화 과정
- 수신자 B는 암호문 d B를 이용하여 C
d b≡P mod n B를 계산하여 평문 P를
얻는다.
o 정리
- 이러한 과정에서 B가 공개한 수 e B와 n B를 이 암호방식의 공개키라 한
다. 한편, 두 소수 p B, q B,
φ( n b ) 및 d B는 B만이 가지고 보안을 유지하고 있
어야 한다. 특히, ( n B , d B )는 암호문을 복호화 하는데 필요한 개인키라 한
다.
2) 암호학적 안전성
RSA 암호의 비도가 크게 되려면 n의 소인수 분해가 계산적으로 불가능해야
하므로 소인수 분해 알고리즘 등에 의하여 인수분해 되지 않는 꼴이어야 한다.
따라서 p와 q는 다음과 같은 조건을 만족해야 한다.
o p와 q는 같지 않고 거의 같은 크기의 자릿수이어야 한다.
o p-1과 q-1은 커다란 소인수를 각각 가져야 한다.
o p-1과 q-1의 최대 공약수는 작은 수이어야 한다.
위와 같은 조건은 n = p * q의 소인수 분해를 어렵게 만들므로 이를 이용한
RSA암호 방식의 공격을 어렵게 만든다. RSA알고리즘의 공격으로는 다음과 같
은 가능한 접근 방법이 있다.
o 전사적 공격 : 모든 가능한 개인키로서 시도한다.
o 수학적인 공격 : 두 소수의 곱을 인수분해하는 몇 가지 접근이 있다.
o 시간적인 공격 : 이것은 복호알고리즘의 실행시간에 의존한다.
(다) Rabin 암호
Rabin암호 역시 소인수분해 어려움에 안전성의 근거를 두고 있다. 결국 Rabin
암호를 해독하는 어려움과 소인수 분해를 하는 어려움은 같은 것이다.
Rabin암호는 RSA와 같은 원리를 이용하지만 암호화 과정이 RSA암호방식보다 빠
른 것이 특징이다.
1) 암/복호화 과정
o 준비과정
- 수신자 B가 공개되지 않은 p B≡3 mod 4이고 q B≡3 mod 4인 두 소수를 선

택하고 p B, q B의 곱 n B = p B .q B를 구한다.
- 수신자 B는 b를 선택하고 ( n B , b)를 공개한다.
o 암호화 과정
- 송신자 A는 평문 P와 공개키 ( n B , b)를 이용하여 암호문
C≡P( P+b) mod n B 를 구하여 A에게 전송한다.
o 복호화 과정
- 수신자 B는 암호문 C를 복호하기 위하여 n B = p B .q B임을 이용하여
p≡
1
4
+Cb
2
mod n B을 계산하여 평문 P를 얻는다.
o 정리
- 암호화 함수 Ek는 m을 법으로 한 2차 합동식이므로 암호화하는 속도가
RSA 암호와 비교하여 상당히 빠르다. 그러나 중국인의 정리에 의하여 이
차 합동식을 만족하는 해가 4가지이므로 주어진 암호문에 대하여 4가지로
복호되므로 이들 중에서 평문을 찾아야 한다. 따라서 평문을 쉽게 찾을 수
있도록 사전에 평문에 관한 정보를 약속하므로 평문을 얻는다. 이를테면,
평문으로 이용되는 수를 적당하게 제약하므로 실제로 1개의 해가 평문이
되도록 한다.
(라) 이차 잉여류 문제 [1급]
[표 4-6] 이차 잉여와 그 예
이차 잉여 이차 비잉여
이차 잉여 정의
- gcd(a, m) = 1
- x 2≡ a mod m
- x 2≡/ a mod m
이차 잉여 예 (Z13) - {1, 3, 4, 9, 10, 12} - {2, 5, 6, 7, 8, 11}
(3) 효과적인 암호구현 알고리즘 [1급]
(가) 연산의 시행회수를 줄이는 알고리즘
1) Karatsuba 방법
2) Barrett 방법
3) Takagi 방법
4) Montgomery 방법
(나) 연산의 횟수를 감소시키는 알고리즘
1) 지수의 이진표현을 이용하는 이진방법
2) 지수의 소인수분해를 이용하는 소인수 분해 방법
3) 지수의 m진 표현을 이용한 m진 이용방법
4) 지수의 가산고리를 이용하는 가산고리방법




1.1.8 확률적 공개키 암호 [1급]
o 핵심가이드
- 확률적 공개키 암호의 안전성 개념 이해
- RSA-OAEP의 이해
- BBS, Goldwasser-Micali에 대한 내용 이해


(1) 확률적 공개키 암호의 안전성 개념


(가) 의미론적 안전성(Semantically Security)
의미론적 안전성은 Goldwasser와 Micali에 의해 소개된 개념으로서 공개키 암 호 방식의 증명 가능한 안전성을 제공하기 위한 효시가 된 정의라고 볼 수 있다.
의미론적 안전성은 암호문으로부터 효율적으로 계산 가능한 것은 모두 단지 평문 의 길이만 주어졌을 때에도 효율적으로 계산 가능한 것이라는 사실을 의미한다. 즉, 평문의 길이 이외에 다른 정보가 없다면 암호문은 평문을 유추해 내는 데에 아무런 역할도 하지 못한다는 개념이 의미론적으로 안전하다는 뜻이다. 의미론적 으로 안전한 암호 방식을 사용하는 통신로 상에서 암호문을 도청하는 공격자는 평문에 대해서 아무런 정보도 얻지 못한다.


(나) NM-안전성(Non-Malleability)
NM-안전성 개념은 Dolev, Dwork, Naor에 의해서 처음 소개된 것으로 이들의
머리글자를 인용하여 DDN-안전성이라 부르기도 한다. NM-안전성을 정의할 때는
공격자의 공격 목표가 낮아진다는 것이 큰 특징이다. 이전의 안전성 개념에서의
공격자의 목표는 주어진 도전 암호문 C로부터 평문 P를 찾아내는 것이었다. 그러
나 NM-안전성 개념 정의에 나타나는 공격자의 목표는 도전 암호문 C의 평문 P
을 찾는 것이 아니고 단지 그것의 평문이 P와 알려진 방법으로 관계 지워진 어떤
암호문을 얻어내는 것이다. 즉 다른 안전성 개념에서 보다 공격 성공의 목표치가
약하기 때문에 NM-안전성에 고려되는 공격자는 그만큼 공격을 쉽게 성공시킬 수
있는 것이다. NM-안전성에 고역 관점의 안전성을 결합한 개념을 NM-CPA,
NM-CCA, NM-ACC 등으로 표현한다.


(2) RSA-OAEP
공개키 암호화의 경우(서명과 비밀키 전송에 널리 사용되고 있다) 단지 약간의 알
고리즘만이 널리 사용되고 있는데 가장 널리 사용되고 있는 알고리듬 중의 하나는
RSA이다. RSA의 알고리듬은 단지 미국에서만 특허화되어 있으며 2000년 9월에 만
료되어 자유롭게 사용될 수 있다. 공격자가 직접적으로 제공한 원값(raw value) 을
RSA를 사용해 절대로 복호화하거나 서명하지 말아야 한다. RSA는 비밀키를 드러
낼 수 있기 때문에 결과를 들어낸다. (대부분의 프로토콜은 원값이 아닌 사용자가
계산한 해쉬에 서명하는 것을 포함하거나 결과를 드러내지 않기 때문에 이는 실제
문제가 되지는 않는다) 절대로 정확히 동일한 원값을 여러 번 복호화하거나 서명하
지 말아야 한다.(원래 값이 노출될 수 있다) 이러한 두 문제 모두 임의의 패딩
(padding, 아무런 의미가 없는, 고정 길이를 갖는 레코드 또는 블록에 무의미한 문
자로 채우는 기법)을 늘 추가함으로써 해결될 수 있다. 보통의 접근 방법은
Optimal Asymmetric Encryption Padding (OAEP) 라고 불린다.
o RSAES-OAEP는 Bellare-Rogaway의 방식에 기초한 인코딩 방법이다.
Random oracle model을 바탕으로 plaintext-awareness을 주는 알고리즘이
며 Make Generation Funcion(MGF)이 필요하다.
o MGF
주어진 string을 Seed로 하여 주어진 길이만큼의 난수열을 생성하는 의사 난
수 함수이며 RSA 서명 알고리즘 중에 PKCS#1-PSS와 P1363a의 EMSR3 의
안전성은 MGF의 랜덤성에 의존한다. PKCS#1에서는 MGF로 MGF1을 사용
권고하고 있으며 MGF1에서의 해쉬함수는 SHA1을 사용한다.


(가) BBS (Blum Blum Shub)
암호적인 강도에 있어서 가장 강력한 것으로 공개적으로 증명되었다.
1) Generation 절차
o 4로 나누었을 때 나머지가 모두 3인 두 개의 큰 소수 p와 q를 선택한다.
즉,
p≡q≡3( mod 4)
n = p×q
o s가 상대적으로 n에 대해 소수인 난수 s를 선택한다.
o 아래의 알고리즘에 따라 B i 비트들의 수열을 생성한다.
X 0= s 2 mod n
for i = 1 to ∞


X i= ( X i - 1 ) 2 mod n
B i= X i mod 2
2) BBS는 암호학적으로 안전한 pseudorandom bit 발생기(CSPRBG)라고 한다.
o CSPRBG는 정의된 순서에 따라 다음 비트 시험을 통과함으로써 정의된다.
=> “출력 수열의 첫 번째 k개의 비트들이 입력에서 1/2 보다 월등히 큰
확률로.   번째를 예측할 수 있는 다항-시간 알고리즘이 없다면 한
pseudorandom bit 발생기가 다음 비트 시험을 통과했다"고 말한다.


(나) Goldwasser-Micali
암호문으로부터 평문의 어떤 부분 정보도 노출되지 않는 암호 방식. 인수분해
문제와 제곱 잉여의 원리를 이용한 확률 암호를 정의.
1) 준비 과정
o 수신자 B는 공개되지 않은 홀수인 두 소수 pB, qB의 곱 nB = pB qB를 구하
고 nB를 법으로 한 제곱비잉여로 ( b
n B )= 1를 만족하는 b를 생성하고 (nB,
b)를 공개한다.
2) 암호화 과정
o 송신자 A는 평문 P∈{0, 1}를 암호화하기 위하여 Zn*의 원소 r을 선택한다.
o 송신자 A는 (b, r, nB)를 이용하여 C≡bPr2
mod nB 를 계산하여 암호문 C를
B에게 송신한다.
3) 복호 과정
o 수신자 B는 nB=pBqB를 이용하여 C가 nB를 법으로 한 이차잉여인가 또는 이
차 비잉여 인가를 판정한다.
o 수신자 B는 평문을 C가 이차잉여이면 0으로, 이차 비잉여이면 1로 복호한
다.
이 암호에는 Zn*의 원소인 암호문이 nB를 법으로 이차잉여와 이차 비잉여일 확
률은 각각 1
2
인 원리를 추가하였다. 따라서 암호문으로부터 평문의 어떤 정보도
노출되지 않으며 암호문의 일부에 대응되는 평문이 노출되어도 이외 평문에 대한
정보가 노출되지 않는 장점이 있다. 그러나 암호화 단위가 1비트이므로 효율적이
아니다.


1.1.9 이산대수 기반 공개키 암호


o 핵심가이드

- 345 -
- 유한체의 이산 대수 문제 이해
- ElGamal 암호체계의 변수 선정법, 암/복호화 순서 및 방법, 사용된 연산, 안전성
- Diffie-Hellman 키 교환체계의 변수 선정법, 암/복호화 순서 및 방법, 사용된 연
산, 안전성
- 타원곡선 이산대수 문제(ECDLP)의 이해 [1급]
- 타원곡선 공개키 암호시스템의 변수 선정법, 암/복호화 순서 및 방법, 사용된 연
산, 안전성 [1급]


(1) 유한체의 이산대수
(가) 유한체의 이산대수문제
이산대수 문제는 군(group)을 이용한다. 일반적으로 차수가 t인 집합 G의 원소
g와 집합 G의 다른 원소 .  .. 가 주어졌을 때 x를 구하는 것은 어려우며 이를
이산대수 문제(DLP: Discrete Logarithm Problem)라 한다. 여기서 0≤x≤t-1이다.
y는 g를 x번 곱한 결과이다. 원소 g는 전형적으로 G의 모든 원소들을 생성하거
나 또는 적어도 0에서 t-1사이의 모든 정수들을 가지고 누승함으로서(즉, 반복적
으로 그룹 연산을 함으로서)큰 부분집합을 생성할 수 있다. 원소 g가 군 내의 모
든 원소들을 생성할 수 있다면 원소 g를 생성자(generator)라고 한다.
유한체의 이산대수문제는 유한체의 곱셈군에 대한 이산대수문제이다. 소인수분
해 문제와 마찬가지로 이산대수 문제는 일방향 함수의 어려운 문제라 여겨지고
있다. 이러한 이유로 이산대수 문제는 ElGamal 시스템과 DSS를 포함한 여러 공
개키 암호 시스템들의 기초를 이루어 왔다. 이들 시스템들의 안전성은 이산대수
를 계산하기가 어렵다는 가정에 의존하고 있다.
이산대수 문제는 유한체(finite fields)상에서 보다 임의의 군(group)상에서 훨씬
더 어려운 듯하다. 즉, 이것은 타원 곡선(elliptic curve)군에 기초한 암호 시스템
의 동기 부여이다. 일반적으로 임의의 군 내에서 이산대수를 계산하기 위한 동작
시간(running time)은 o(. )이다. 여기서 p는 군의 위수(order)이다.


(나) ElGamal
EIGamal은 1985년 이산 대수 문제에 바탕을 둔 공개키 암호시스템이다.
1) 준비과정
o 소수 q와 체 F a에서 위수가 큰 임의의 원소 g를 공개한다.
o 사용자 A는 자신이 암호문을 전달받기 위하여 임의의 정수 A를 0 < a <
q-1 이 되도록 하고 g a mod q를 계산하고 a는 공개하지 않고 g a mod q를
공개한다.
2) 암호문 전달과정
o 사용자 B는 임의의 k를 선택하여 P g ak mod q를 계산하고 평문 P의 암호문
으로 ( g k,P g ak )을 A에게 보낸다.
o 사용자 A는 개인키 a를 이용하여 ( g k ) a≡g ak mod q를 계산하고 P g ak을
g ak로 나누어 평문 P를 구한다.


(다) Diffie-Hellman
1) 준비과정
o 사용자 A와 사용자 B가 사용할 소수 p와 원시원소 g를 상의하여 결정
2) 개인키 생성
o 사용자 A는 a를 선택하고 g amod p 를 계산하여 공개하고 사용자 B는 b를
선택하고 g b mod p를 계산하여 공개한다.
o 사용자 A는 사용자 B의 공개키 g b mod p와 자신의 개인키 a를 이용하여
( g b ) a mod p를 계산하고, 사용자 B는 사용자 A의 공개키 g amod p와 자신
의 개인키 b를 이용하여 ( g a ) b mod p를 계산하여 공동 비밀키로 사용한다.
o 실제로 K≡( g a ) b≡( g b ) a mod p 이므로 A와 B는 같은 비밀키를 공유할 수
있다. 또, 이산대수를 구하는 어려움 때문에 g amod p와 g b mod p로부터 a,b
를 얻을 수 없으므로 g ab mod p를 구할 수 없기 때문에 안전하다.
즉, 만나는 번거로움 없이 K를 비밀키로 결정하여 안전하게 공유하고 이용
할 수 있다.
(2) 타원곡선 암호 (Elliptic Curve Cryptosystem) [1급]
타원곡선상의 이산대수 문제를 통해 제안된 암호 시스템으로 RSA 알고리즘보다
작은 비트수를 가지고 동일한 암호의 강도를 지닐 수 있다. 스마트카드나 휴대폰
등 키의 길이가 제한적인 무선 환경이나 작은 메모리를 가지고 있는 시스템에 적합
하다.


(가) 타원곡선 이산대수 문제
실수체 위에서 정의된 타원곡선과는 달리 유한체 Fq에서 정의된 타원곡선은 유
한개의 원소들로 이루어지며, 연산에 있어서 실수체 위에서 정의된 타원곡선에서
와 달리 계산오류가 없이 정확한 값을 얻는 장점이 있다.
타원곡선 위에 한 점 P의 위수를 n이라면 집합 H={P, 2P,…,nP=O}는 군 E(Fq)
의 순환부분군이다. 즉, 군 H의 임의의 원소 Q에 대하여 적당한 자연수 k가 존재
하여 Q=kP이다. 한편, k와 P를 알면 Q를 구하는 것은 어렵지 않지만, n이 충분
히 클 경우에 점 P와 점 Q가 주어질 때, k를 구하는 것은 쉽지 않다. 이를 타원
곡선 이산대수 문제(ECDLP: Elliptic Curve Discrete Logarithm Problem)라 한다.


(나) 타원곡선 Diffie-Helloman 비밀키 교환 시스템
사용자 A와 B는 우선 자기 자신의 개인키와 공개키를 만들기 위해 유한체 Fq
와 그 위에서 정의되는 타원곡선 E를 정하여 공개하고 반드시 생성원일 필요는
없지만 위수가 충분히 큰 E 위의 원소 Q를 선택하여 공개한다.
1) 준비 과정
o 두 사용자 A와 B가 사용할 타원곡선 E와 위수가 충분히 큰 E 위의 원소 Q
를 결정한다.
2) 비밀키 생성 과정
o 사용자 A와 B는 각각 임의의 정수 a, b를 선택하여 자신의 개인키로 보관
하고, aQ와 bQ를 계산하여 공개한다.
o 사용자 A와 B가 비밀키를 공유하기 위하여, 사용자 A는 B의 공개키 bQ에
자신의 개인키 a를 곱하여 P=abQ를 구하고 사용자 B도 같은 방법으로
P=abQ를 구하여 비밀키를 생성한다.


(다) 타원곡선 Massey-Omura 암호방식
1) 준비 과정
o 유한체 Fq에서의 타원곡선 E의 점의 개수 N을 구한다.
2) 암호문 전달 과정
o 사용자 A와 사용자 B는 각각 eA와 eB를 선택하고 각각 dA=eA
-1 mod N과
dB=eB
-1 mod N을 계산하여 각각 (eA, dA)와 (eB, dB)를 개인키로 한다.
o 사용자 A는 평문 P와 자신의 키 eA를 이용하여 eA(P)를 계산하여 사용자 B
에게 보낸다.
o 사용자 B는 eA(P)를 수신하고 자신의 키 eB를 이용하여 eB(eA(P))를 계산하여
사용자 A에게 보낸다.
o 사용자 A는 eB(eA(P))를 수신하고 자신의 키 dA를 이용하여
dA(eBeA(P))=eB(P) 를 계산하여 사용자 B에게 보낸다.
o 사용자 B는 eB(P)를 수신하고 자신의 키 dB를 이용하여 dB(eB(P))=P를 계산
하여 평문 P를 얻는다.
(라) 타원곡선 ElGmal 암호방식
1) 준비 과정
o 두 사용자 A와 B가 사용할 타원곡선 E와 위수가 충분히 큰 E의 원소 Q를
결정한다.
2) 암호문 전달 과정
o 사용자 A는 자신이 암호문을 전달받기 위하여 임의의 정수 eA를 선택하고
개인키로 보관하고 eA(Q)를 계산하여 공개한다.
o 사용자 B는 임의로 정수 k를 선택하여 kQ를 계산하고, 평문 P의 암호문으
로 순서쌍(kQ, P+k(eA(Q)))를 사용자 A에게 보낸다.
o 사용자 A는 kQ에 자신의 개인키 eA를 곱하여 eA(kQ)를 구하고 이를 이용하
여 P+k(eA(Q))-eA(kQ)를 구하여 평문 P를 얻는다.


1.2 해쉬함수와 전자서명
1.2.1 해쉬함수 일반
o 핵심가이드
- 해쉬함수의 성질
- 해쉬함수의 특성과 그 핵심 논리
- 생일역설과 안전성개념
(1) 해쉬함수의 성질
해쉬함수 h가 가져야 할 기본 성질들로는 다음과 같은 것들이 있다.
(가) 역상 저항성
주어진 임의의 출력값 y에 대해, y=h(x)를 만족하는 입력값 x를 찾는 것이 계
산적으로 불가능하다.
(나) 두 번째 역상 저항성
주어진 입력값 x에 대해 h(x)=h(x'), x≠x'을 만족하는 다른 입력값 x'을 찾는
것이 계산적으로 불가능하다.
(다) 충돌 저항성
h(x)=h(x')을 만족하는 임의의 두 입력값 x, x'을 찾는 것이 계산적으로 불가능
하다.
(2) 전자서명에 이용되는 해쉬 함수의 특성
(가) 해쉬함수의 계산 효율이 양호해야 한다.
(나) 약 일방향성 (Weak onewayness)
해쉬값 H로부터 h(M) = H되는 서명문 M을 찾는 것은 계산상 불가능해야 한
다.
(다) 강 일방향성 (Strong onewayness)
어떤 서명문 M과 그의 해쉬값 H=h(M)가 주어졌을 때 h(M')=H되는 서명문
M‘≠M을 찾는 것이 계산상 불가능해야 한다.
(라) 충돌 회피성(collision freeness)
h(M)=h(M')되는 서명문 쌍(M, M') (M≠M')을 찾는 것이 계산상 불가능해야 한
다.
여기서 첫 번째 특성은 해쉬함수의 성능조건이고 두 번째, 세 번째, 네 번째 특성
은 해쉬 함수의 안전성에 관한 제약이다. 두 번째, 세 번째 특성은 해쉬 함수의 역
함수를 계산하는 것을 방지하는 기능을 말하며 네 번째 특성은 서명자가 서명문 M
을 서명하여 전송하고 나중에 M'를 서명하여 전송하였다고 주장하는 이른바 내부
부정을 방지하기 위한 기능이다.
(3) 생일역설과 해쉬함수의 안전성 개념
해쉬 함수의 특성 중 충돌 회피성은 서로 다른 서명문 M, M'의 해쉬값 H가 동
일한 값을 갖지 않는다는 조건이나 실제의 경우 서명문 M의 길이가 해쉬값 H보다
훨씬 길기 때문에 충돌은 반드시 발생하기 마련이다. 이러한 충돌 회피성조건을 만
족하기 위해서는 동일한 해쉬값 H를 갖는 서로 다른 서명문 M과 M'를 찾는 것이
어려워야 된다.
동일한 해쉬값 H를 갖는 서명문 M과 M'를 구하는 문제는 흔히 생일 공격으로
설명된다. 생일이 같은 날일 확률이 12 이려면 몇 명의 사람이 있어야 하나 그 결
과는 23명이다.
일반적으로 해쉬값 H가 같아질 확률이 1/2이 되려면 서명문 M의 수가 몇 개나
있어야 하는 문제는 K = 1.17 M이다. 따라서 생일 공격을 차단하기 위해서는 적
어도 128비트, 즉 264비트 서명문을 비교해야 하는 경우 이상이어야 한다. 예로 DSS
에서는 160비트로 제한하고 있다.


1.2.2 블록암호 이용 방식
o 핵심가이드
- 각종 해쉬함수 종류
n비트의 블록 암호를 이용하여 만들어진 해쉬함수들은 (n비트)단일 길이의 해쉬

값을 생성하는 것과 (2n비트) 이중 길이의 해쉬값을 생성하는 해쉬함수로 나누어
진다.
[표 4-7] n비트 블록 암호에 기초한 해쉬함수의 요약
해쉬함수 (n, k, m) 해쉬 비율
Matyas-Meyer-Oseas (n, k, m) 1
Davies-Meyer (n, k, m) k/n
MDC-2(DES) (64, 56, 128) 1/2
MDC-4(DES) (64, 56, 128) 1/4




1.2.3 전용 해쉬 함수
o 핵심가이드
- 전용 해쉬함수들의 핵심 내용과 비교
- 해쉬함수 공격의 이해
전용 해쉬함수란 블록 암호 혹은 모듈 연산과 같은 기존의 시스템 성분들을 다시
이용하지 않고 해쉬만을 목적으로 최적화된 수행을 하도록 디자인된 해쉬함수이다.


(1) MD4
MD5의 초기 버전으로서, 입력 데이터(길이에 상관없는 하나의 메시지)로부터 128
비트 메시지 축약을 만듦으로써 데이터 무결성을 검증하는데 사용되는 알고리즘이
다.
(가) MD4의 설계 원칙
1) 수학적인 가정 없이 안전한 해쉬함수를 설계한다.
2) 해쉬함수의 수행속도는 가능한 빨라야 한다. 특히, 소프트웨어로 구현 했을
때의 속도를 고려한다.
3) 알고리즘은 단순하며 구현이 용이해야한다.
4) little-endian 구조(word의 최하위 바이트가 low-address 바이트 위치에 있는
구조)를 고려한 알고리즘을 설계한다.


(2) MD5
o 128비트 출력
o 512비트 블록단위로 처리
o 4라운드 64단계로 구성
(가) MD4와 MD5의 차이
1) MD4는 16단계의 3라운드를 사용하나 MD5는 16단계의 4라운드를 사용한다.
2) MD4는 각 라운드에서 한번씩 3개의 기약함수를 사용한다. 그러나 MD5는
각 라운드에서 한번씩 4개의 기약 논리 함수를 사용한다.
3) MD4는 마지막 단계의 부가를 포함하지 않지만, MD5의 각 단계는 이전 단
계의 결과에 부가된다.


(3) SHA-1
o 160비트 출력
o 512비트 블록단위로 처리
o 4라운드 80단계로 구성


(4) RIPEMD-160
o 21워드 입력값을 5개의 워드 출력값으로 변환시킨다. 각 입력블록은 동시에
각기 다른 압축 함수에 의해 실행된다.
o 임의의 길이의 메시지를 512비트-블록단위 처리
o 160비트 출력
[표 4-8] MD5, SHA-1, RIPEMD-160 비교


(5) 해쉬함수 공격의 종류 및 그 특성 [1급]
(가) 일치블록 연쇄공격
새로운 메시지 M'를 사전에 다양하게 만들어 놓았다가 공격하고자 하는 메시
지 M의 해쉬함수값 h(M)과 같은 해쉬함수 값을 갖는 것을 골라 사용하는 공격
(나) 중간자 연쇄공격
전체 해쉬값이 아니라 해쉬 중간의 결과에 대한 충돌쌍을 찾는다. 특정 포인트
를 공격대상으로 한다.
(다) 고정점 연쇄공격
압축함수에서 고정점이란 f(H i - 1, x i) = H i - 1을 만족하는 쌍 ( H i - 1, x i )를 말
한다. 그러한 메시지 블록과 연쇄변수 쌍을 얻게 되면 연쇄변수가 발생하는 특정
한 점에서 임의의 수의 동등한 블록들 x i를 메시지의 중간에 삽입해도 전체 해
쉬값이 변하지 않는다.
(라) 차분 연쇄공격
1) 다중 라운드 블록암호의 공격
다중 라운드 블록암호를 사용하는 해쉬 함수에서, 입력값과 그에 대응하는
출력값의 차이의 통계적 특성을 조사하는 기법을 사용
2) 해쉬함수의 공격
압축함수의 입출력 차이를 조사하여, 0의 충돌쌍을 주로 찾아내는 방법을 사
용.
(마) 최근 동향
최근 Wang의 공격으로 표준 해쉬함수 SHA의 안전성에 문제가 발견되어 미국
NIST는 2005년 10월 해쉬함수 워크샵을 개최하여 해쉬함수의 안전성을 강화하는
방안을 논의하는 자리를 마련하였다. 이 워크샵에서 해쉬함수의 정의, 설계 요구
조건, 압축함수의 설계기법 등에 대하여 심도있는 재검토가 필요하다는 공감대가
형성되었으며 장기적으로 용도에 따라 다양한 해쉬함수를 개발해야 한다는 쪽으
로 논의가 진행되었다.




1.2.4 해쉬 함수 설계 원리 [1급]
o 핵심가이드
- 압축함수의 정의
- 패딩기법
- MDC 해쉬함수의 안전성
- 일방향 함수의 정의
- MAC 설계방법


(1) 압축함수와 패딩기법
(가) 압축함수란
크기가 고정된 해쉬함수로 압축성, 계산의 용이성에 일방향 성질을 추가시킨
함수이다. 하지만 정의역이 제한되어 있어 고정된 크기의 입력값을 갖는다. 즉, m
비트 크기의 입력을 n비트 크기의 출력값으로 압축시킨다. ( m > n )


(나) 패딩기법
블록 단위로 해쉬하는 방법에서 일반적으로 블록 길이를 맞추기 위해 해쉬하기
전에 메시지에 대한 비트열이 패딩된다. 패딩된 비트는 보내는 사람과 받는 사람
이 동의한다면 전송 또는 저장될 필요가 없다.
1) 패딩방법 1
o 입력 : 비트길이가 n인 데이터 x.
o 출력 : 비트 길이가 n의 배수인 패딩된 데이터 x'.
o 패딩 : 비트 길이가 n의 배수가 되도록 필요한 만큼 x에 '0'비트들을 패딩
한다.
2) 패딩방법 2
o 입력 : 비트 길이가 n인 데이터 x.
o 출력 : 비트 길이가 n의 배수인 패딩된 데이터 x'.
o 패딩 : x에 ‘1’비트를 패딩한다. 비트 길이가 n의 배수가 되도록 필요한 만
큼 데이터 x에 ‘0’비트들을 패딩한다.
위의 패딩방법 1은 데이터의 뒤에 붙은 ‘0’비트가 패딩 ‘0’비트와 구별되지 않으
므로 모호하다. 이런 방법은 다른 수단에 의해 수신자에게 데이터의 길이를 알려
줄 수 있다면 좋은 방법이 될 수 있다. 패딩방법2는 패딩되지 않은 데이터 x와
패딩된 데이터 x'사이에 일대일 관계가 있으므로 모호하지 않다.


(2) MD-method
(가) MDC 해쉬 함수의 안전성
안전하고 효율적인 MDC 해쉬함수 h( )는 다음 조건을 만족하는 함수이다.
1) 함수 h( )는 공개된 함수이고 어떠한 비밀키도 함수계산에 사용되지 않는다.
2) 변수 m의 길이에는 제한이 없고 h(m)의 길이는 l비트로 고정된다.
( l > 64 )
3) h( )와 m이 주어졌을 때 h(m)의 계산은 용이하여야 한다.
4) m가 h(m)이 주어졌을 때 h(m')=h(m)을 만족하는 m'( ≠m)을 찾는 것은 계
산적으로 불가능해야 한다.
[표 4-9] MDC
구분 입력 출력 해쉬율
MDC-2 n 2n 1/2
MDC-4 n 2n 1/4
(3) Universal One-Way Hash Function
(가) 일방향성
임의의 해쉬값 h(M)이 주어졌을 때 그것에 대해서 입력 메시지 M를 도출해 내
는 것이 불가능한 조건
(4) 해쉬 함수를 이용하여 MAC을 설계하는 방법
(가) MAC의 안전성
안전하고 효율적인 MAC 해쉬함수 h( )는 다음 조건을 만족하는 함수이다.
1) 함수 h( )는 공개된 함수이고 비밀키 k가 함수 계산에 사용된다.
2) 변수 m의 길이에는 제한이 없고 h(k, m)의 길이는 l비트로 고정된다.
(l ≥ 64)
3) h( ), m 그리고 k가 주어졌을 때 h(k, m)의 계산은 용이하여야 한다.
4) 여러 쌍의 {mi, h(k, mi)}가 관측되었다고 할지라도 이를 이용하여 비밀키 k
를 도출한다거나 또는 임의의 m'( ≠mi)에 대해서 h(k, m')을 계산해 내는 것
역시 계산적으로 불가능해야 한다.
[표 4-10] 해쉬유형 표
해쉬 유형 설계 목적 이상적인 길이 공격자의 목적
OWHF
역상 저항;
두 번째 역상 저항
2n
2n
역상 생성;
같은 상을 갖는 다른 역상 생성
CRHF 충돌 저항 2n/2 충돌 생성
MAC
키 회복불능;
계산 저항
2t
Pf=max(2-t, 2-n)
MAC키 찾기;
새로운(메시지, MAC) 생성




1.2.5 전자서명 일반
o 핵심가이드
- 전자서명의 조건들
- 수기 서명과 전자서명의 차이점 분석
- 공개키 기반 구조(PKI)의 개념 및 구성객체 종류
- PKI 인증서 관리구조
- 서명위조와 안전성에 대한 개념
- 메시지 복원형과 메시지 부가형의 차이


(1) 전자서명의 조건
(가) 위조 불가 조건
합법적인 서명자만이 전자 문서에 대한 전자 서명을 생성할 수 있어야 한다.
(나) 서명자 인증 조건
전자 서명의 서명자를 누구든지 검증할 수 있어야 한다.
(다) 부인 불가 조건
서명자는 서명 후에 자신의 서명 사실을 부인할 수 없어야 한다.
(라) 변경 불가 조건
서명한 문서의 내용은 변경될 수 없어야 한다.
(마) 재사용 불가 조건
전자 문서의 서명은 다른 전자 문서의 서명으로 사용될 수 없어야 한다.


(2) 수기 서명과 전자서명의 차이점
(가) 서류에 서명하는 문제
수기서명에서는 서명이 서류의 일부분인 반면에 전자서명은 서명되는 서류의
일부분이 아니며 서류의 전체이다.
(나) 서명을 확인하는 인증문제
수기 서명에서는 실제의 서명과 비교함으로써 증명되는 반면, 전자서명은 공개
된 알려진 인증 알고리즘에 의하여 증명될 수 있다. 즉, 수기 서명은 보는 사람에
따라 주관적이므로 위조여부의 식별에 차이가 있지만 전자서명은 모든 사람에게
객관적이므로 위조여부의 식별에 차이가 없다.
(다) 복사의 문제
수기 서명에서는 실제의 서명을 복사하기 힘들지만 전자서명에서는 똑같이 복
사될 수 있다.


(3) X.509 인증서
(가) X.509인증서의 역사
전자서명을 위한 인증서는 디지털 형태로 표준화가 필요하다. 인증서는 온라인
상에서 배포되고 검증할 수 있어야 하기 때문에 현재 가장 널리 쓰이는 디지털
인증서 형태는 X.509인증서이다. 1988년 ITU(International Telecommunications
Union)에 의해 표준으로 개발된 X.509인증서는 1993년 두 번째 버전이 출시되면
서 2개의 인식자가 첨가되었고, 1997년 세 번째 버전에 다시 확장영역이 추가되
면서 표준으로 자리 잡게 되었다. 1988년 처음 등장한 X.509인증서는 강력하고 유
연한 메커니즘으로 다양한 정보를 포함할 수 있으며, ASN.1구조를 채택하여 꾸준
히 발전하고 있다. 특히 IETF(Internet Engineering Task Force)가 인터넷상에서
X.509인증서 사용을 결정함에 따라 X.509인증서의 확장영역에 인터넷 사용에 필
요한 요건을 정하게 되면서 획기적인 발전을 이루었다.


(나) X.509 인증서의 ASN.1 구조
X.509 인증서의 ASN.1 구조는 크게 OID(Object Identifiers), AI(Algorithm
Identifiers), DS(Directory String), DN(Distinguished Names), GN(General
Names)의 5부분으로 나누어진다.
1) OID(Object Identifiers)
OID X.509인증서에서 OID(Object Identifiers)는 다양한 정보를 나타내기 위
해 사용된다. 예를 들면 CA가 사용하는 RSA 또는 DSA와 같은 암호 알고리즘,
인증정책 등을 X.509인증서에 기록하기 위해 사용되는 것이다.
2) AI(Algorithm Identifiers)
AI(Algorithm Identifiers)는 X.509인증서에서 암호 알고리즘과 키에 대한 정
보를 나타낸다. 예를 들면 X.509인증서가 사용하는 전자서명 알고리즘을 알 수
있고, 공개키와 관련된 알고리즘을 알 수 있는 것이다.
3) DS(Directory String)
DS(Directory String)는 X.509인증서에 텍스트(text) 정보를 나타내기 위한 것
이다. DS는 다양한 언어와 문자를 사용할 수 있도록 PrintableString,
TeletexString, BMPString, UTF8String, UniversalString 등 여러 형태로 정의된
다. PrintableString은 ASCⅡ를 지원하고, TeletexString은 북유럽 언어를 지원하
며, BMPString은 16비트로 암호화된 다양한 언어를 지원하고, UTF8String과
UniversalString은 디지털로 암호화된 다양한 언어를 지원한다.
4) DN(Distinguished Names)
DN(Distinguished Names)은 X.509인증서에 계층적으로 이름을 부여하기 위
한 것이다. 이는 국제적 디렉토리(directory)에서 X.509인증서를 식별해야 하기
때문이다.
5) GN(General Names)
GN(General Names)은 X.509인증서의 이름을 암호화하기 위한 것이다. 이를
위해 GN은 7개의 표준이름 형태를 사용한다.


(다) X.509인증서의 내용
X.509인증서의 내용은 크게 개인정보와 공개키로 구성된다. 이름과 소속 그리고
연락처(주로 전자우편 주소) 등의 개인정보가 기록되어 있고, 인증서의 발급일과
만료일 그리고 인증서의 고유성을 확보하기 위한 일련번호와 인증서를 발급한 인
증기관의 명칭이 나타나 있다. 또한 인증서에는 인증기관의 전자서명이 첨부되어
있다. 인증기관의 전자서명은 인증서가 진본임을 증명해 준다.


(라) X.509인증서 3부분
X.509인증서의 내용 X.509인증서는 크게 3부분으로 나누어진다. 개봉봉투
(Tamper-Evident Envelope)는 인증서의 모든 내용을 담고 있고, 인증서 내용
(Basic Certificate Content)은 모든 인증서가 기본적으로 갖추어야 하는 정보를 담
고 있으며, 확장영역(Certificate Extension)은 인증서에 따라 다양한 선택적 정보
를 담고 있다. 따라서 인증서 내용은 확장영역을 포함하며 개봉봉투는 인증서 내
용을 포함한다.


(4) 공개키 기반 구조(PKI)의 개념
(가) 정의
공개키 알고리즘을 통한 암호화 및 전자서명을 제공하는 복합적인 보안시스템
환경이다. 즉, 암호화와 복호화키로 구성된 공개키를 이용하여 송수신 데이터를
암호화하고 디지털 인증서를 통해 사용자를 인증하는 시스템이다.


(나) 공개키 기반구조(PKI)의 객체 구성
1) 공개키 인증서를 발급, 폐지하는 인증기관(CA)
2) 공개키와 인증서 소유자 사이의 관계를 확인하는 등록기관(RA)
3) 인증서를 발급받고, 전자문서에 서명하고 암호화를 할 수 있는 공개키 인증
서의 소유자
4) 인증기관의 공개키를 사용하여 인증경로 및 전자서명을 검증하는 사용자
5) 공개키 인증서와 CRL을 저장하는 저장소


(다) 공개키 기반구조(PKI)의 요구사항
1) 비용 및 성능을 고려한 사용자의 편의성 제공
2) 전자상거래에 대한 법적 효력유지
3) 사용자의 보안 정책 및 관리 체계 반영
5) 인증서의 생성, 획득, 취소 및 검증가능
6) PKI 기반의 전자상거래 실체 인증
7) 메시지의 무결성 보장 및 변조 검출
8) 메시지 및 전자상거래 관련자의 기밀성 보장
9) 기타의 정보보호 서비스 제공


(라) PKI 인증서 관리구조
[표 4-11] 인증서 관리구조
1) COI구조
o 자주 거래하는 관심 주제에 따라 그룹을 형성한 인증기관구조
o 인증경로가 거래 사용자간에 특별히 설정되어 저장할 인증서의 수효감소
2) 조직에 따른 구조
o 어떤 기관의 현재 계층적, 또는 부서별 조직 관계를 반영한 구조
o 조직의 계층적 상하 관계가 분명한 기관에서 유리하며 구현용이
3) 보증 단계 따른 구조
o 어떤 등급의 보증 수준을 나타내는 대상자별로 그룹을 형성한 구조
o 신뢰성 보증수준에 따른 효과적 보안정책수립
4) 복합형 인증서 관리 구조
o COI구조, 조직에 따른 구조, 그리고 보증 단계에 따른 구조 3가지의 형태를
각각 하나의 세그먼트로써 허용하는 복합적인 구조
o 한 국가의 종합적인 환경은 정부기관, 일반 상거래 관계의 기업, 또는 특수
한 분야의 서비스 조직 등 다양한 형태별 구성가능


(마) PKI 응용모델
1) SDSI(Simple Distributed Security Infrastructure)
o 1996년 X.509의 복잡성에 대응하여 보다 단순화된 방식 제안
o X.509의 기능들 중에서 인증서 정책, 제약조건, 키 생명주기 관리 등의 기능
생략
o 단순한 응용환경에서 운용할 수 있는 X.509 기능의 일부를 정의
o X.509에서 사용된 ASN.1보다 단순한 방식의 구문표현기법 사용
o 특별한 자료구조를 사용하여 단순하게 기능을 제공하는 것이 장점
o 공식적인 정책들이 요구되는 대형 조직에서는 구현하기 어려움
2) SPKI(Simple Public-Key Infrastructure)
o X.509 PKI 신뢰모델의 인증서와는 다르게 실체-기반 인증서가 아니라 신용-
기반 인증서를 정의
o 대응되는 개인키의 소유자에게 필요한 실체명을 요구하지 않고 SPKI인증서
가 공개키에 명시된 인가 또는 특권을 인정하는 새로운 기법
o SPLI 인증서의 주요목적이 어떤 동작의 인가를 부여하고 자격을 인정
o 폐쇄된 환경에서 자원들의 접근을 보호하기 위하여 특별히 사용할 수 있는
새로운 가능성 제시


(바) SET(Secure Electronic Transaction)
1) 인터넷 기반 전자쇼핑 또는 서비스 규정의 일부로써 은행카드 지불을 지원
하기 위하여 비자와 마스터 카드사가 개발한 프로토콜 하부구조
2) 공개키 기반구조는 하향식 계층구조 사용


(사) PGP(Preety Good Privacy)
1) 신뢰성의 확인은 각 사람 자신들의 믿음을 통하여 전달
2) PGP의 공개키 링의 각 키 인증서는 믿음의 유효성과 신뢰성 등급표현
3) PGP의 인증체계 기반기술은 PKI표준과 일치하지 않으며, 개별적인 획득 사
용이 쉽지만 대규모의 전자상거래를 지원하기에는 부적합


(아) S/MIME(Secure/Multipurpose Internet Mail Extension)
1) RSA데이터 보안기술 기반하여 MIME 인터넷 전자우편 형식의 표준을 확장
구현
2) PGP가 많은 사용자들에 대하여 개인적 전자우편 보안을 다룬다면, S/MIME
은 상업적인 조직의 산업적 표준을 수행
3) X.509의 버전 3에 일치하는 공개키 인증서를 사용
4) 사용된 키 관리구조는 엄격한 X.509 인증서 계층과 PGP의 신뢰모델에 대한
복합적인 방식을 채택
5) S/MIME 관리자 및 사용자들은 PGP처럼 신뢰하는 키의 목록과 CRL을 갖
고 각 클라이언트를 구성


(5) 서명 위조와 안전성 개념
(가) 위조에 대한 관점
1) 일반적 위조 불가
o 서명의 위조가 불가능한 문서가 존재
2) 선택적 위조 불가
o 어떤 정해진 문서이외에 대해서는 서명의 위조가 불가능
3) 존재적 위조불가
o 어떠한 문서에 대해서도 서명의 위조가 불가능


(나) 공격에 대한 관점
1) 수동공격
o 공개키만을 사용하여 위조
2) 일반 선택문서 공격
o 선택한 문서에 대한 서명문을 얻은 후 그 정보를 통하여 제 3의 문서의 서
명을 위조하는 공격
3) 적응적 선택문서 공격
o 매회 적응적으로 임의로 선택한 문서의 서명문을 얻은 후 그 정보를 통하여
제 3의 문서의 서명을 위조하는 공격


(6) 메시지 복원형과 메시지 부가형
(가) 메시지 복원형 전자서명(Digital Signature Scheme Giving Message
Recovery)
이 방식은 RSA와 같이 공개키로 암호화하고 비밀키로 복호화할 때 본래의 메
시지가 환원되고, 비밀키로 암호화하고 공개키로 복호화 하여도 본래의 메시지가
환원되는 방식이다. 즉, 서명자가 자신의 비밀키를 이용하여 메시지를 암호화하여
전송하면 검증자가 서명자의 공개키를 이용하여 서명된 암호문을 복호화하여 그
결과가 일정한 규칙을 만족하는 메시지가 되는지를 확인함으로써 서명을 검증하
는 방식이다. 이처럼 서명 검증 과정에서 원래의 메시지가 복원되는 방식을 메시
지 복원형 전자서명이라고 한다. 메시지 복원형 전자서명은 기존의 암호 시스템
을 이용하기 때문에 별도의 전자서명 프로토콜이 필요하지 않은 장점이 있지만,
메시지를 일정한 크기의 블록으로 나누어 각각의 블록에 대하여 서명을 하여야
하기 때문에 서명의 생성이나 검증과정에서 많은 시간이 소요되는 단점이 있다.
(나) 부가형 전자서명(Digital Signature With Appendix)
이 방식은 임의의 길이로 주어진 메시지를 해쉬 알고리즘을 이용하여 일정한
크기로 압축하고, 그 해쉬 알고리즘의 결과와 서명자의 비밀키를 이용하여 전자
서명을 생성해서 메시지를 덧붙여 보낸다. 이렇게 생성된 서명의 검증은 수신된
메시지를 해쉬한 결과와 전자서명 및 공개키를 이용하여 계산된 값을 비교함으로
써 이루어진다. 부가형 전자서명은 메시지 이외에 서명을 별도로 전송해야 하기
때문에 전송량이 조금 늘어나는 반면에 메시지가 아무리 길더라도 단 한 번의 서
명 생성만을 필요로 하기 때문에 효율적이라 할 수 있다. 임의의 길이의 메시지
를 일정한 길이로 압축해 주는 해쉬 알고리즘은 입력메시지가 조금만 변하더라도
그 해쉬 결과가 전혀 다른 값으로 변하기 때문에 서명의 위조나 메시지의 변조를
막을 수 있다. 따라서 안전한 해쉬 알고리즘을 개발하는 것이 필수적이다. 상기의
두 가지 전자서명 방식 중에서 부가형 전자서명의 장점이 비교적 크기 때문에 현
재 세계적인 추세도 부가형 전자서명을 선호하고 있다.


1.2.6 전자서명 예
o 핵심가이드
- RSA 및 ElGamal, Schnorr 전자서명의 이해
- 전자서명 표준(DSS), 국내 표준 전자서명(KCDSA)의 이해
- 타원곡선 전자서명 표준(ECDSA)의 이해 [1급]
(1) RSA 전자 서명

(그림 4-3) RSA 암호 방식을 이용한 전자 서명
(2) ElGamal 전자 서명
ElGamal 전자 서명은 이산대수 문제를 기반으로 정보보호