1. 블록 암호 운용 모드

블록 암호를 이용하여 여러 블록으로 이루어진 메시지를 암호화하고 복호화하는 방법이다

대표적인 운용 모드에는 ECB, CBC, CFB, OFB, CTR이 있다. 여기서는 ECB와 CTR을 살펴본다

1.1 전자 코드북 모드

전자 코드북 모드(Electronic Codebook, ECB)

평문을 블록으로 나눈 뒤, 각 블록을 같은 키로 독립적으로 암호화하는 방식이다

1.1.1 암호화와 복호화

구분	연산
암호화	$C_{i} = E_{K} (P_{i})$
복호화	$P_{i} = D_{K} (C_{i})$

각 블록은 다른 블록의 처리 결과에 의존하지 않으므로 암호화와 복호화 모두 병렬 처리 할 수 있다

1.1.2 반복 패턴의 노출

같은 키를 사용하면 동일한 평문 블록은 항상 동일한 암호문 블록으로 변환된다

$P_{i} = P_{j} \Rightarrow C_{i} = C_{j}$

예를 들어 평문 블록이A | B | A라면 암호문에도 X | Y | X와 같은 반복 구조가 남는다

공격자는 실제 내용을 몰라도 어떤 위치의 평문 블록들이 같은지 알아낼 수 있다

ECB의 패턴 노출

이미지나 문서처럼 반복되는 블록이 있는 데이터를 암호화하면 구조가 드러날 수 있다. 따라서 ECB는 일반적인 여러 블록 메시지의 암호화에 적합하자 않다

1.2 카운터 모드

카운터 모드(Counter Mode, CTR)

블록마다 다른 카운터 값을 암호화하여 키스트림을 생성하고, 이를 평문과 XOR하는 방식이다

1.2.1 암호화

$i$ 번째 블록의 카운터 값을 $T_{i}$ 라고 하면 다음과 같다.

$C_{i} = P_{i} \oplus E_{K} (T_{i})$

카운터 값 $T_{i}$ 를 준비한다
카운터를 암호화하여 키스트림 $E_{K} (T_{i})$ 를 생성한다
키스트림을 평문 블록과 XOR하여 암호문을 얻는다

카운터는 일반적으로 초기값에서 시작하여 블록마다 1씩 증가시킨다

1.2.2 복호화

암호화할 때와 동일한 키와 카운터 값으로 키스트림을 생성한 뒤, 암호문과 XOR한다

$P_{i} = C_{i} \oplus E_{K} (T_{i})$

같은 키스트림을 두 번 XOR하면 상쇄되므로 원래 평문을 얻는다

복호화할 때도 암호화 연산 $E_{K}$ 를 사용하므로, 블록 암호의 복호화 연산 $D_{K}$ 는 필요하지 않다

1.2.3 카운터 관리

같은 키 아래에서는 카운터 입력값이 중복되지 않아야 한다. 이 조건은 한 메시지 내부뿐 아니라 여러 메시지 사이에도 적용된다

실제로는 메시지를 구분하는 논스와 메시지 내부의 블록 카운터를 결합할 수 있다. 이 값들은 일반적으로 비밀일 필요는 없지만, 중복되지 않도록 관리해야 한다

카운터 재사용

같은 키와 카운터를 재사용하면 동일한 키스트림이 생성된다. 이는 앞서 살펴본 반복키 XOR 방식과 마찬가지로 평문 사이의 관계를 노출시키며, 한 평문을 알면 다른 평문까지 복원할 수 있다

1.2.4 CTR의 장점

장점	설명
병렬 처리	각 카운터를 독립적으로 암호화하여 여러 블록을 동시에 처리할 수 있다
하드웨어, 소프트웨어 효율성	여러 연산 장치와 프로세서의 병렬 처리 기능을 활용하기 쉽다
사전 계산	평문을 받기 전에도 키와 카운터만으로 키스트림을 준비할 수 있다
임의 접근	앞의 블록을 처리하지 않고 원하는 블록을 바로 처리할 수 있다
구현의 단순성	암호화와 복호화 모두 블록 암호의 암호화 연산만 사용한다
안전성 분석	적절한 블록 암호와 카운터 관리 조건 아래에서 안전성을 분석할 수 있다

1.2.5 무결성의 한계

CTR은 암호문 변조를 자체적으로 탐지하지 못한다

공격자가 암호문의 특정 비트를 뒤집으면 복호화된 평문의 같은 위치 비트도 뒤집힌다. 따라서 변조 탐지가 필요하면 별도의 메시지 인증 기능이나 인증된 암호화 방식을 사용해야 한다

1.3 ECB와 CTR의 비교

구분	ECB	CTR
블록 암호의 입력	평문 블록	카운터 블록
반복 평문 블록	같은 암호문 블록으로 변환된다	서로 다른 카운터로 반복 패턴을 숨긴다
병렬 처리	가능	가능
키스트림 사전 계산	해당 없음	가능
복호화에 사용하는 연산	$D_{K}$	$E_{K}$ 와 XOR
주요 주의점	평문의 반복 패턴 노출	같은 키 아래에서 카운터 재사용 금지
변조 탐지	자체적으로 제공하지 않음	자체적으로 제공하지 않음

2. AES

AES(Advanced Encryption Standard)

128 비트 블록을 처리하며, 128, 192, 256비트 키를 사용하는 대칭키 블록 암호이다

AES는 미국 국립표준기술연구소(NIST가2001년 11월 26일 FIPS 197로 발표한 암호 표준이다

파이스텔(Feistel) 구조를 사용하지 않으며, 데이터 전체에 치환, 재배열, 혼합, 키 결합 연산을 반복하여 적용한다

2.1 블록 크기와 키 길이

AES의 블록 크기는 항상 128비트이며, 키 길이에 따라 라운드 수가 달라진다

구분	블록 크기	키 길이	라운드 수
AES-128	128비트	128비트	10회
AES-192	128비트	192비트	12회
AES-256	128비트	256비트	14회

블록 크기와 키 길이의 구분

AES-256도 블록 크기는 128비트이다. 이름의 숫자는 블록 크기가 아니라 키 길이를 나타낸다

2.2 상태와 키 확장

2.2.1 상태

상태(State)

AES가 처리하는 128비트 데이터 블록을 4행 × 4열의 바이트 배열로 표현한 것이다

128비트는 16바이트이므로 다음과 같이 구성된다

$128 비트 = 16 바이트 = 4 \times 4 바이트$

각 원소는 1바이트이다
각 열은 4바이트로 구성된다
각 연산을 거치면서 상태의 값과 배치가 바뀐다
마지막 연산을 마친 상태가 암호문 블록이 된다

2.2.2 키 확장

키 확장(Key Expansion)

입력된 비밀키로부터 각 단계에 사용할 라운드 키를 생성하는 과정이다

키를 워드(Word)들의 배열로 확장하며, AES에서 한 워드는 32비트, 즉 4바이트이다

각 키 결합 단계에는 상태와 같은 크기인 128비트 라운드 키를 사용한다

구분	라운드 수	초기 단계까지 포함한 라운드 키 개수
AES-128	10회	11개
AES-192	12회	13개
AES-256	14회	15개

2.3 라운드를 구성하는 연산

일반 라운드는 다음 네 연산을 순서대로 수행한다

순서	연산	역할
1	SubBytes	각 바이트를 다른 값으로 치환한다
2	ShiftRows	각 행의 바이트를 순환 이동한다
3	MixColumns	각 열의 바이트들을 행렬 연산으로 혼합한다
4	AddRoundKey	상태와 라운드 키를 XOR한다

2.3.1 바이트 치환(SubBytes)

상태의 각 바이트를 S-box에 따라 다른 바이트로 치환한다

모든 바이트에 동일한 S-box를 적용한다
바이트의 위치는 그대로 두고 값을 변경한다
비선형 변환을 제공하여 단순한 선형 관계를 이용한 분석을 어렵게 한다

2.3.2 행 이동(ShiftRRows)

각 행을 서로 다른 칸 수만큼 왼쪽으로 순환 이동한다

행	이동량
첫 번째 행	이동하지 않음
두 번째 행	1바이트
세 번째 행	2바이트
네 번째 행	3바이트

바이트의 값 자체는 바꾸지 않고, 서로 다른 열로 재배치한다

2.3.3 열 혼합(MixColumns)

각 열의 4바이트에 고정된 행렬을 이용한 연산을 적용한다

한 열의 입력 바이트들이 서로 섞인다
각 출력 바이트는 해당 열의 여러 입력 바이트에 영향을 받는다
연산은 일반적인 실수 행렬 연산이 아니라 유한체 $GF (2^{8})$ 위의 연산이다

ShiftRows와 함께 데이터의 변화가 여러 위치로 퍼지도록 한다

2.3.4 라운드 키 결합(AddRoundKey)

상태와 해당 단계의 라운드 키를 비트별 XOR한

$새 상태 = 현재 상태 \oplus 라운드 키$

네 연산 중 비밀키에서 생성한 값을 직접 결합하는 단계이다

2.4 전체 암호화 과정

AES 암호화는 초기 키 결합 -> 일반 라운드 반복 -> 마지막 라운드로 구성된다

2.4.1 초기 키 결합

평문을 상태로 배치한 뒤 첫 번째 라운드 키와 XOR한다

$상태 \leftarrow 평문 상태 \oplus K_{0}$

이 초기 AddRoundKey는 10·12·14회의 라운드 수에 포함되지 않는다

2.4.2 일반 라운드

다음 네 연산을 수행한다

SubBytes
ShiftRows
MixColumns
AddRoundKey

구분	일반 라운드 반복 횟수
AES-128	9회
AES-192	11회
AES-256	13회

2.4.3 마지막 라운드

마지막에는 다음 세 연산만 수행한다

SubBytes
ShiftRows
AddRoundKey

마지막 라운드의 차이

AES의 마지막 라운드에는 MixColumns가 없다. 초기 AddRoundKey, 일반 라운드, 마지막 라운드를 구분해야 한다

AES-128의 전체 구성은 다음과 같다

단계	수행 연산
초기 단계	AddRoundKey
1~9라운드	SubBytes → ShiftRows → MixColumns → AddRoundKey
10라운드	SubBytes → ShiftRows → AddRoundKey

2.5 복호화 과정

복호화는 암호화에서 적용한 연산을 역순으로 되돌리는 과정이다

암호화 연산	대응하는 복호화 연산
SubBytes	InvSubBytes: 역 S-box로 치환
ShiftRows	InvShiftRows: 각 행을 오른쪽으로 순환 이동
MixColumns	InvMixColumns: 역행렬 연산으로 열 혼합 복원
AddRoundKey	같은 라운드 키와 다시 XOR

AddRoundKey는 같은 값을 두 번 XOR하면 상쇄되므로 별도의 역연산이 필요하지 않다

$(X \oplus K_{i}) \oplus K_{i} = X$

복호화에서는 암호화의 마지막 라운드 키부터 역순으로 사용한다

AES-128을 기준으로 정리하면 다음과 같다

단계	수행 연산
초기 단계	마지막 라운드 키로 AddRoundKey
일반 복호화 라운드 9회	InvShiftRows → InvSubBytes → AddRoundKey → InvMixColumns
마지막 단계	InvShiftRows → InvSubBytes → 첫 번째 라운드 키로 AddRoundKey

이 그림은 10라운드를 사용하는 AES-128의 구조이다. AES-192와 AES-256은 같은 기본 구성에서 라운드 수가 각각 12회와 14회로 늘어난다

왼쪽 암호화 과정은 위에서 아래로, 오른쪽 복호화 과정은 아래에서 위로 읽는다. 가운데에서 생성된 라운드 키는 양쪽의 AddRoundKey 단계에 사용된다. 암호화의 마지막 라운드에는 MixColumns가 없으며, 복호화에서는 라운드 키를 역순으로 사용한다

2.6 구현상의 특징

AES는 바이트 단위의 변환과 XOR 연산을 반복하는 구조이다

XOR 연산으로 라운드 키를 결합한다
테이블 조회로 S-box 등의 연산을 구현할 수 있다
효율적인 소프트웨어·하드웨어 구현이 가능하다

다만 구현 방법에 따라 실행 시간이나 메모리 접근 패턴에서 정보가 누설될 수 있으므로, 알고리즘의 안전성과 구현의 안전성을 함께 고려해야 한다

3. 공개키 암호

공개키 암호 시스템

서로 연결된 공개키와 개인키의 쌍을 사용하여 암호화, 복호화 또는 서명, 검증 등의 기능을 제공하는 암호 시스템이다

키	관리 방식
공개키(Public Key)	다른 사람에게 공개한다
개인키(Private Key)	소유자만 알고 있도록 비밀로 유지한다

공격자가 알고리즘과 공개키를 알고 있어도 개인키를 계산하거나 보호된 메시지를 알아 내기는 계산적으로 어려워야 한다

3.1 대칭키 방식의 한계와 공개키 방식

3.1.1 키 분배 문제

대칭키 암호로 통신하려면 두 당사자가 같은 비밀키를 확보해야 한다

통신 전에 키를 안전하게 공유한다
또는 키 분배 센터(Key Distribution Center, KDC)를 이용한다

KDC가 침해되면 해당 기관이 관리하는 키와 통신의 안전성이 영향을 받을 수 있다

공개키 암호에서는 수신자의 공개키로 암호화할 수 있으므로, 송신자가 수신자와 동일한 비밀키를 미리 공유할 필요가 없다

3.1.2 전자서명 문제

대칭키 방식에서는 송신자와 수신자가 같은 키를 알고 있다. 따라서 두 당사자 모두 인증 정보를 만들 수 있어, 제3자에게 어느 당사자가 작성했는지 증명하기 어렵다

공개키 방식에서는 개인키로 서명하고 공개키로 검증하여 이러한 구분을 지원한다

공개키의 소유자 확인

공개키는 비밀로 유지할 필요가 없지만, 그 키가 실제 통신 상대의 것인지 확인해야 한다. 공격자의 공개키를 상대의 키로 믿고 사용하면 메시지가 공격자에게 노출될 수 있다

3.2 공개키 암호화의 구성 요소

공개키 암호화는 다음 여섯 가지 요소로 구성된다

구성 요소	역할
평문(Plaintext)	암호화할 원본 메시지
암호화 알고리즘	공개키를 사용하여 평문을 암호문으로 변환
공개키	공개할 수 있는 암호화용 키
개인키	수신자가 비밀로 유지하는 복호화용 키
암호문(Ciphertext)	암호화 결과
복호화 알고리즘	개인키를 사용하여 암호문을 평문으로 복원

각 사용자는 키 쌍을 생성하고 공개키를 공개 등록부 등에 제공하며, 개인키는 비밀로 보관한다

3.3 기밀성을 위한 공개키 암호화

Bob이 Alice에게 비밀 메시지를 보낸다고 하자

Alice가 공개키와 개인키를 생성한다
Alice는 공개키를 공개하고 개인키를 비밀로 보관한다
Bob은 Alice의 공개키로 메시지를 암호화한다
Alice는 자신의 개인키로 암호문을 복호화한다

Alice의 공개키를 $P U_{A}$ , 개인키를 $P R_{A}$ 라고 하면 다음과 같다

$C = Enc_{P U_{A}} (M)$ $M = Dec_{P R_{A}} (C)$

공개키로 암호화하는 것은 누구나 할 수 있지만, 올바른 방식으로 구성된 암호에서는 대응하는 개인키를 가진 수신자만 복호화할 수 있다

3.4 인증을 위한 개인키 사용

송신자의 개인키로 서명을 생성하고, 수신자가 송신자의 공개키로 검증하면 메시지의 출처와 무결성을 확인할 수 있다

Bob이 Alice에게 메시지를 보내는 경우 다음과 같다

Bob이 자신의 개인키로 메시지에 서명한다
Bob이 메시지와 서명을 Alice에게 보낸다
Alice가 Bob의 공개키로 서명을 검증한다

$σ = Sign_{P R_{B}} (M)$ $Verify_{P U_{B}} (M, σ)$

공개키는 누구나 알 수 있으므로 서명 검증 자체가 메시지 내용을 숨겨 주지는 않는다

이 그림은 RSQ의 가역적인 연산을 이용하여 개인키 처리와 공개키 확인의 관계를 단순화해 보여준다

서명과 암호화의 구분

전자서명을 일반적으로 “개인키로 암호화하는 것”이라고 정의하면 안 된다. 실제 전자 서명은 별도의 서명, 검증 알고리즘과 메시지 인코딩을 사용하며, 모든 공개키 알고리즘에서 키의 역할을 서로 바꿀 수 있는 것은 아니다

3.5 기밀성과 인증의 결합

기밀성과 송신자 인증을 함께 제공하려면 서명과 암호화를 결합할 수 있다

A가 B에게 메시지를 보낸다고 하자

A가 자신의 개인키로 메시지에 서명한다
메시지와 서명을 B의 공개키로 암호화한다
B가 자신의 개인키로 복호화한다
B가 A의 공개키로 서명을 검증한다

목적	송신자가 사용하는 키	수신자가 사용하는 키
기밀성	수신자의 공개키	수신자의 개인키
송신자 인증·무결성	송신자의 개인키	송신자의 공개키

그림의 키 사용 순서는 다음과 같다

$P R_{A} \to P U_{B} \to P R_{B} \to P U_{A}$

즉, 송신 측에서 적용한 두 처리를 수신 측에서 반대 순서로 해제, 확인한다

3.6 공개키 암호 시스템의 활용

활용	기능
암호화·복호화	메시지의 기밀성 보호
전자서명	송신자 인증, 무결성 확인, 부인 방지 지원
키 교환·설정	통신에 사용할 세션 키를 안전하게 공유하거나 합의

모든 공개키 알고리즘이 세 가지 기능을 모두 제공하는 것은 아니다

대표적인 공개키 기술에는 RSA와 타원곡선 기반 암호 기술 등이 있다. 구체적인 알고리즘에 따라 암호화용, 서명용, 키 합의용으로 구분된다

3.7 공개키 암호의 요구사항

A가 B에게 메시지를 보내는 경우 다음 조건을 만족해야 한다

번호	요구사항
1	B가 공개키와 개인키를 효율적으로 생성할 수 있어야 한다.
2	A가 B의 공개키로 메시지를 효율적으로 암호화할 수 있어야 한다.
3	B가 자신의 개인키로 암호문을 효율적으로 복호화할 수 있어야 한다.
4	공격자가 공개키를 알아도 개인키를 구하기 어려워야 한다.
5	공격자가 공개키와 암호문을 알아도 원래 메시지를 알아내기 어려워야 한다.
6 — 선택 조건	일부 방식에서는 두 키에 대응하는 연산을 어느 순서로 적용해도 원래 입력을 복원할 수 있다.

복호화의 정확성은 다음과 같이 나타낸다

$Dec_{P R_{B}} (Enc_{P U_{B}} (M)) = M$

여기서 효율적이라는 것은 다항 시간 안에 계산할 수 있다는 의미로 이해한다. 공격자의 역산은 효율적인 계산으로 성공하기 어려워야 한다

선택 조건인 연산의 순서 교환은 RSA의 기본 수학적 연산에서 볼 수 있지만, 모든 공개키 암호에 필요한 조건은 아니다

3.8 트랩도어 일방향 함수

앞서 살펴본 일방향 함수는 순방향 계산은 쉽지만 역상 탐색은 어려운 함수이다. 트랩도어 일방향 함수는 여기에 역산을 쉽게 만드는 비밀 정보를 추가한다

트랩도어 일방향 함수(Trapdoor One-Way Function)

공개된 정보로 순방향 계산은 쉽게 수행할 수 있지만, 특정 비밀 정보를 모르면 역산하기 어렵고 그 정보를 알면 쉽게 역산할 수 있는 함수이다

공개 매개변수를 $p k$ , 트랩도어를 $t d$ 라고 하자

계산	난이도
$p k$ 와 $x$ 를 알고 $y = f_{p k} (x)$ 계산	쉬움
$p k$ 와 $y$ 만 알고 역상 $x$ 탐색	어려움
$t d$ 까지 알고 역상 $x$ 계산	쉬움

이 구조는 공개키를 가진 누구나 계산하고, 비밀 정보를 가진 소유자는 역산할 수 있는 비대칭성을 설명한다

일방향 함수 일반이 반드시 일대일 함수일 필요는 없다. 입력과 출력이 일대일로 대응하는 경우는 일방향 순열로 구분할 수 있다

3.9 공개키 암호에 대한 공격

3.9.1 개인키 전수조사

가능한 개인키를 하나씩 시도하는 공격이다

충분히 큰 키 공간으로 전수조사를 어렵게 해야 한다
키가 커질수록 연산 비용도 증가하므로 안전성과 처리 효율을 함께 고려해야 한다

3.9.2 공개키에서 개인키 계산

공개키의 수학적 구조를 분석하여 대응하는 개인키를 구하려는 공격이다

공개키와 개인키 사이에는 수학적 관계가 있다
그러나 공개 정보만으로 그 관계를 역으로 풀기는 어려워야 한다
이러한 어려움은 계산적 가정에 의존하며, 무조건적 안전성을 의미하지 않는다

3.9.3 평문 후보 추측 공격

평문 후보 추측 공격(Probable-Message Attack)

가능한 평문 후보를 공개키로 직접 암호화한 뒤, 관찰한 암호문과 비교하여 평문을 추정하는 공격이다

암호화할 메시지가 56비트 DES 키이며 암호화가 결정적이라고 하자

공격자는 가능한 DES 키를 후보로 생성한다
각 후보를 수신자의 공개키로 암호화한다
관찰한 암호문과 같은 결과를 찾는다
일치하는 후보로 원래 메시지를 알아낸다

이 공격은 개인키를 구하지 않고도 수행할 수 있다

대응 방향

추측 가능한 평문을 항상 같은 암호문으로 만드는 구조를 피한다
적절한 무작위성을 포함하는 검증된 암호화 인코딩·패딩 방식을 사용한다
평문 후보가 적다면 공개키의 길이를 늘리는 것만으로 이 공격을 해결할 수는 없다

4. RSA

RSA

서로 다른 두 소수의 곱을 이용하여 키를 생성하고, 모듈러 거듭제곱 연산으로 암호화와 복호화를 수행하는 공개키 암호 방식이다

RSA는 977년 MIT의 Rivest, Shamir, Adleman이 개발했으며, 이름은 세 사람의 성에서 따왔다

4.1 기본 구조

RSA의 기본 연산에서는 평문과 암호문을 다음 범위의 정수로 표현한다

$0 \leq M < n, 0 \leq C < n$

여기서 $n$ 은 서로 다른 두 소수 $p, q$ 의 곱이다.

$n = pq$

값	의미	공개 여부
$p, q$	서로 다른 두 소수	비밀
$n = pq$	모듈러 연산의 기준값	공개
$e$	공개 지수	공개
$d$	개인 지수	비밀

키는 다음과 같이 구성한다

공개키: $(e, n)$
개인키: $(d, n)$

$n$ 은 두 키에 공통으로 들어가는 공개값이며, 개인키에서 비밀로 보호해야 하는 핵심 값은 $d$ 이다

4.1.1. 메시지 블록의 크기

메시지를 정수로 변환했을 때 그 값이 반드시 $n$ 보다 작아야 한다. 모든 $k$ 비트 값을 입력으로 허용하려면 다음 조건을 만족해야 한다

$2^{k} - 1 < n$

따라서 메시지를 나누고 인코딩할 때 각 블록의 값이 허용 범위를 벗어나지 않도록 해야 한다

4.2 키 생성

4.2.1 두 소수 선택

서로 다른 소수 $p, q$ 를 선택한다

$p \neq = q$

4.2.2 모듈러스 계산

두 소수를 곱하여 $n$ 을 구한다

$n = pq$

4.2.3 오일러 피 함수 계산

오일러 피 함수(Euler’s Totient Function)

$1$ 부터 $n - 1$ 까지의 양의 정수 중 $n$ 과 서로소인 정수의 개수를 나타내며, $φ (n)$ 으로 표기한다

서로 다른 두 소수의 곱 $n = pq$ 에 대해서는 다음이 성립한다

$φ (n) = (p - 1) (q - 1)$

4.2.4 공개 지수 선택

다음 조건을 만족하는 $e$ 를 선택한다

$1 < e < φ (n)$

$g cd (e, φ (n)) = 1$

즉, $e$ 와 $φ (n)$ 은 서로소여야 한다

4.2.5 개인 지수 계산

$e$ 의 모듈러 역원을 구하여 $d$ 로 사용한다

$d \equiv e^{- 1} (mod φ (n))$

이는 다음 조건과 같다

$e d \equiv 1 (mod φ (n))$

즉, 어떤 정수 $t$ 에 대해 다음을 만족해야 한다

$e d = tφ (n) + 1$

$d$ 는 확장 유클리드 알고리즘으로 구할 수 있다

역원은 일반적인 나눗셈이 아니다

$d = e^{- 1} mod φ (n)$ 은 $d = 1/ e$ 라는 뜻이 아니다. $e d$ 를 $φ (n)$ 으로 나눈 나머지가 1이 되는 정수 $d$ 를 구한다는 뜻이다

4.2.6 키 생성 결과

단계	계산
소수 선택	$p, q$
모듈러스 계산	$n = pq$
피 함수 계산	$φ (n) = (p - 1) (q - 1)$
공개 지수 선택	$g cd (e, φ (n)) = 1$
개인 지수 계산	$d \equiv e^{- 1} (mod φ (n))$
공개키	$(e, n)$
개인키	$(d, n)$

4.3 암호화와 복호화

4.3.1 암호화

송신자는 수신자의 공개키 $(e, n)$ 를 사용한다

$C = M^{e} mod n$

4.3.2 복호화

수신자는 자신의 개인키 $(d, n)$ 를 사용한다

$M = C^{d} mod n$

암호화 식을 대입하면 다음과 같다

$C^{d} mod n = M^{e d} mod n$

키를 올바르게 생성하면 다음이 성립하므로 원래 평문을 복원할 수 있다

$M^{e d} \equiv M (mod n)$

4.4 복호화가 가능한 이유

4.4.1 오일러 정리

$M$ 과 $n$ 이 서로소이면 다음이 성립한다

$M^{φ (n)} \equiv 1 (mod n)$

키 생성 과정에서 $e d = tφ (n) + 1$ 이 되도록 정했으므로 다음과 같이 계산할 수 있다

$M^{e d} = M^{tφ (n) + 1} = (M^{φ (n)})^{t} M \equiv 1^{t} M \equiv M (mod n)$

4.4.2 서로소가 아닌 평문

오일러 정리를 직접 적용하는 위 설명은 $g cd (M, n) = 1$ 인 경우에 해당한다. 그러나 RSA는 서로 다른 두 소수 $p, q$ 와 올바른 지수 $e, d$ 를 사용하면 $0 \leq M < n$ 인 모든 평문 정수에 대해 복호화된다

이는 $p$ 와 $q$ 각각에 대한 합동식을 확인한 뒤 중국인의 나머지 정리를 적용하여 설명할 수 있다

4.5 키 생성 예제

다음 소수를 선택하자

$p = 17, q = 11$

1. 모듈러스 계산

$n = 17 \times 11 = 187$

2. 피 함수 계산

$φ (n) = 16 \times 10 = 160$

3. 공개 지수 선택

$e = 7, g cd (7, 160) = 1$

4. 개인 지수 계산

$7 d \equiv 1 (mod 160)$

확장 유클리드 알고리즘을 적용하면 다음과 같다

$160 = 22 \times 7 + 6$

$7 = 1 \times 6 + 1$

두 식을 정리하면 다음을 얻는다

$1 = 7 - (160 - 22 \times 7) = 23 \times 7 - 160$

따라서 다음과 같다

$d = 23$

실제로 다음 조건을 만족한다

$7 \times 23 = 161 \equiv 1 (mod 160)$

구분	결과
공개키	$(7, 187)$
개인키	$(23, 187)$

4.6 암호화, 복호화 계산 예제

평문을 다음과 같이 정하자

$M = 88$

4.6.1 반복 제곱법

큰 거듭제곱을 그대로 계산하기보다, 제곱할 때마다 나머지를 구한 뒤 필요한 항을 곱하면 계산량을 줄일 수 있다

4.6.2 암호화

$C = 8 8^{7} mod 187$

지수를 다음과 같이 나눈다

$7 = 4 + 2 + 1$

거듭제곱	나머지 계산	결과
$8 8^{1}$	$88 mod 187$	88
$8 8^{2}$	$88 \times 88 mod 187$	77
$8 8^{4}$	$77 \times 77 mod 187$	132

따라서 다음과 같다

$8 8^{7} mod 187 = (8 8^{4} \times 8 8^{2} \times 88) mod 187 = (132 \times 77 \times 88) mod 187 = 11$

암호문은 $C = 11$ 이다

4.6.3 복호화

$M = 1 1^{23} mod 187$

지수를 다음과 같이 나눈다

$23 = 16 + 4 + 2 + 1$

거듭제곱	나머지 계산	결과
$1 1^{1}$	$11 mod 187$	11
$1 1^{2}$	$11 \times 11 mod 187$	121
$1 1^{4}$	$121 \times 121 mod 187$	55
$1 1^{8}$	$55 \times 55 mod 187$	33
$1 1^{16}$	$33 \times 33 mod 187$	154

따라서 다음과 같다

$1 1^{23} mod 187 = (1 1^{16} \times 1 1^{4} \times 1 1^{2} \times 11) mod 187 = (154 \times 55 \times 121 \times 11) mod 187 = 88$

원래 평문인 $M = 88$ 을 복원한다

4.7 RSA의 요구사항

요구사항	RSA에서의 의미
효율적인 키 생성	조건을 만족하는 $p, q, n, e, d$ 를 생성할 수 있어야 한다
효율적인 암호화	$M^{e} mod n$ 을 효율적으로 계산할 수 있어야 한다
효율적인 복호화	$C^{d} mod n$ 을 효율적으로 계산할 수 있어야 한다
개인키 보호	공개된 $e, n$ 으로부터 $d$ 를 구하기 어려워야 한다
평문 보호	공개키와 암호문만으로 평문을 알아내기 어려워야 한다

RSA의 기본 지수 연산은 적용 순서를 바꾸어도 원래 값을 복원할 수 있다

$(M^{e})^{d} \equiv (M^{d})^{e} \equiv M (mod n)$

다만 이 수학적 성질만으로 안전한 암호화나 전자서명 방식이 완성되는 것은 아니다

4.8 RSA에 대한 공격

4.8.1 전수조사 공격

가능한 개인키를 하나씩 시험하는 공격이다

충분히 큰 키 공간을 사용하여 어렵게 만들지만, 전수조사 외의 공격도 함께 고려해야 한다

4.8.2 수학적 공격

공격 방법	결과
$n$ 을 $p, q$ 로 소인수분해	$φ (n)$ 과 $d$ 를 계산할 수 있다
$φ (n)$ 을 직접 계산	$d$ 를 구할 수 있으며, $p, q$ 도 복원할 수 있다
$d$ 를 직접 계산	개인키가 노출되어 복호화할 수 있다

소인수분해에 성공하면 다음 순서로 개인 지수를 구할 수 있다

$n \to p, q \to φ (n) \to d$

또한 $φ (n)$ 을 알면 다음 관계를 이용할 수 있다

$p + q = n - φ (n) + 1$

$pq = n$ 과 $p + q$ 를 알게 되므로 두 소수도 구할 수 있다

소인수분해와 RSA 해독

소인수분해에 성공하면 RSA 개인키를 구할 수 있다. 그러나 모든 RSA 평문 복원 공격이 반드시 소인수분해와 동등하게 어렵다고 증명된 것은 아니다

4.8.3 타이밍 공격

타이밍 공격(Timing Attack)

암호 연산에 걸리는 실행 시간의 차이를 분석하여 비밀 정보에 관한 단서를 얻는 부채널 공격이다

연산 과정이 개인 지수의 값에 따라 달라지면 실행 시간에서도 차이가 나타날 수 있다. 따라서 수학적 알고리즘뿐 아니라 구현에서 발생하는 시간 차이도 고려해야 한다

4.9 소수와 개인 지수의 선택

쉽게 분석되는 키를 피하기 위한 소수 선택 조건에는 다음이 있다

$p$ 와 $q$ 의 자릿수 차이가 크지 않도록 한다
$p - 1$ 과 $q - 1$ 에 각각 큰 소인수가 포함되도록 하는 조건을 고려한다
$g cd (p - 1, q - 1)$ 이 작도록 하는 조건을 고려한다

여기서 두 소수의 길이가 비슷하다는 것과 값 자체가 지나치게 가깝다는 것은 다르다

개인 지수 $d$ 가 지나치게 작아도 공격받을 수 있다. 특히 $n^{1/4}$ 규모보다 작은 개인 지수에 대해서는, 추가 조건 아래에서 효율적인 공격이 가능하다. 따라서 복호화를 빠르게 하려고 $d$ 를 임의로 작게 선택해서는 안 된다

4.10 소인수분해 기록과 안전성

소인수분해 기록은 수의 크기뿐 아니라 알고리즘과 계산 자원의 발전에도 영향을 받는다

표는 다음 항목을 비교한다

항목	의미
십진 자릿수	소인수분해한 정수의 십진 표현 길이
대략적인 비트 수	해당 정수의 이진 표현 길이
달성 시점	소인수분해에 성공한 시기
MIPS-years	계산에 투입한 작업량을 나타내는 지표
알고리즘	소인수분해에 사용한 방법

예를 들어 표에는 1991년 약 332비트 정수부터 2005년 약 663비트 정수까지의 기록이 제시된다. 이는 과거의 기록이며, 현재의 안전한 키 길이를 직접 제시하는 표는 아니다

4.11 기본 RSA 연산과 실제 암호화의 구분

위에서 계산한 다음 식은 RSA의 기본 수학적 연산이다

$C = M^{e} mod n$

같은 평문을 같은 공개키로 처리하면 항상 같은 암호문이 나오므로, 앞서 살펴본 평문 후보 추측 공격 등에 취약하다

기본 RSA를 그대로 사용하지 않기

실제 메시지 암호화에는 기본 거듭제곱 식만 사용하지 않고, RSA-OAEP와 같은 적절한 인코딩·패딩을 포함한 방식을 사용해야 한다. 작은 소수로 구성한 계산 예제는 원리를 이해하기 위한 것이다

5. 해시 함수

암호학적 해시 함수

다양한 길이의 메시지를 입력받아 고정된 길이의 해시값으로 변환하는 함수이다

$h = H (M)$

$M$ : 입력 메시지
$H$ : 해시 함수
$h$ : 해시값 또는 메시지 다이제스트(Message Digest)

일반적인 해시 함수는 알고리즘이 공개되어 있으며 비밀키를 사용하지 않는다

5.1 기본 특징

특징	설명
다양한 입력 길이	짧은 문자열부터 긴 파일까지 처리할 수 있다
고정된 출력 길이	입력 길이와 관계없이 정해진 길이의 값을 출력한다
효율적인 계산	주어진 메시지의 해시값을 빠르게 계산할 수 있다
결정적 연산	같은 입력에는 항상 같은 해시값이 나온다
역산의 어려움	해시값에서 그에 대응하는 입력을 찾기 어려워야 한다

암호화와 달리, 해시에는 원문을 복원하는 복호화 과정이 없다. 해시값이 다르면 입력도 다르지만, 해시값이 같다고 입력까지 반드시 같은 것은 아니다

5.2 충돌

충돌(Collision)

서로 다른 두 입력 $x, y$ 가 같은 해시값을 갖는 현상이다

$x \neq = y, H (x) = H (y)$

출력 길이가 $m$ 비트이면 가능한 해시값은 $2^{m}$ 개이다. 입력의 가짓수가 이보다 많으면 서로 다른 입력이 같은 출력에 대응하는 경우가 반드시 존재한다. 따라서 안전한 해시 함수의 목표는 충돌을 없애는 것이 아니라, 공격자가 충돌을 효율적으로 찾기 어렵게 만드는 것이다

5.3 해시 함수의 요구사항

해시 함수에는 기본적인 처리 조건과 보안 조건이 필요하다

구분	요구사항
입력	다양한 길이의 메시지를 처리할 수 있어야 한다
출력	고정된 길이의 해시값을 생성해야 한다
계산	주어진 메시지의 해시값을 효율적으로 계산할 수 있어야 한다
역상 저항성	주어진 해시값에 대응하는 입력을 찾기 어려워야 한다
제2역상 저항성	주어진 입력과 같은 해시값을 갖는 다른 입력을 찾기 어려워야 한다
충돌 저항성	같은 해시값을 갖는 서로 다른 입력 쌍을 찾기 어려워야 한다

5.3.1 역상 저항성

역상 저항성(Preimage Resistance)

해시값 $h$ 가 주어졌을 때, $H (x) = h$ 를 만족하는 입력 $x$ 를 찾기 어려운 성질이다

일방향성(One-Way Property)이라고도 한다

공격자는 원래 사용된 메시지와 정확히 같은 값을 찾을 필요는 없다. 해당 해시값에 대응하는 어떤 입력이라도 찾으면 성공이다

5.3.2 제2역상 저항성

제2역상 저항성(Second-Preimage Resistance)

입력 $x$ 가 주어졌을 때, $x$ 와 다르면서 같은 해시값을 갖는 입력 $y$ 를 찾기 어려운 성질이다

약한 충돌 저항성(Weak Collision Resistance)이라고도 한다

예를 들어, 이미 정해진 정상 문서와 같은 해시값을 갖는 다른 문서를 만드는 공격을 막는 성질이다

5.3.3 충돌 저항성

충돌 저항성(Collision Resistance)

같은 해시값을 갖는 서로 다른 두 입력을 찾기 어려운 성질이다

$x \neq = y, H (x) = H (y)$

강한 충돌 저항성(Strong Collision Resistance)이라고도 한다.

제2역상 공격과 달리, 공격자가 두 입력을 모두 선택할 수 있다

구분	공격자에게 주어진 것	공격자가 찾는 것
역상 공격	해시값 $h$	$H (x) = h$ 인 입력 $x$
제2역상 공격	입력 $x$	같은 해시값을 갖는 다른 입력 $y$
충돌 공격	특정 입력이 고정되지 않음	같은 해시값을 갖는 서로 다른 입력 쌍 $x, y$

5.4 주요 활용

5.4.1 파일 변경 확인과 식별

파일의 해시값을 계산하여 저장하거나, 신뢰할 수 있는 기준값과 비교한다

해시값이 달라지면 파일 내용이 달라졌음을 알 수 있다
파일의 내용을 기반으로 식별값을 만드는 데 사용할 수 있다
다만 충돌 가능성이 있으므로 수학적으로 완전히 유일한 식별자는 아니다

해시값만으로는 송신자를 인증할 수 없다

공격자가 메시지와 해시값을 함께 바꿀 수 있다면, 변조한 메시지의 해시값도 다시 계산할 수 있다. 악의적인 변조를 확인하려면 신뢰할 수 있는 기준 해시값, MAC 또는 전자서명 등이 필요하다

5.4.2 메시지 인증 코드

메시지 인증 코드(Message Authentication Code, MAC)

송수신자가 공유하는 비밀키를 사용하여 메시지의 무결성과 출처를 확인하는 인증값이다

일반적인 해시와 달리 MAC은 키를 사용한다

구분	일반 해시	MAC
비밀키	사용하지 않음	사용함
계산 가능한 주체	메시지를 아는 누구나	비밀키를 가진 주체
주요 목적	요약값 생성, 기준값과 비교	메시지 인증·무결성 검증

HMAC(Hash-based Message Authentication Code)은 해시 함수와 비밀키를 결합하여 구성하는 MAC이다

$T = HMAC_{K} (M)$

수신자는 같은 키로 인증값을 다시 계산하여 전달받은 값과 비교한다

5.4.3 비밀번호 저장

비밀번호 원문 대신 비밀번호에서 계산한 검증값을 저장하고, 로그인할 때 입력된 비밀번호로 계산한 값과 비교할 수 있다. 그러나 단순히 빠른 해시 함수에 비밀번호를 한 번 입력하는 방식은 추측 공격을 빠르게 수행할 수 있다는 문제가 있다

실제 저장에서는 다음 요소를 함께 고려한다

솔트(Salt): 비밀번호마다 추가하는 무작위 값
비밀번호 전용 해싱: 계산 비용을 높여 대량 추측을 어렵게 하는 방식

솔트는 비밀일 필요가 없으며, 검증에 필요하므로 함께 저장할 수 있다

5.4.4 전자서명

긴 메시지 전체를 직접 처리하는 대신, 메시지의 해시값을 기반으로 서명을 생성할 수 있다

송신자가 메시지의 해시값을 계산한다
개인키를 사용하는 서명 알고리즘으로 서명을 생성한다
수신자가 메시지와 공개키를 이용하여 서명을 검증한다

이때 서로 다른 메시지가 같은 해시값을 가지면 서명을 다른 메시지에 악용할 가능성이 있으므로 충돌 저항성이 중요하다

5.5 대표적인 해시 함수

함수	출력 길이
MD5	128비트
SHA-1	160비트
SHA-256	256비트
SHA-384	384비트
SHA-512	512비트
RIPEMD-160	160비트

예를 들어 다음 메시지의 SHA-1 해시값은 160비트이며, 16진수로는 40자리이다

입력:
The quick brown fox jumps over the lazy cog

SHA-1:
de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3

목록에 포함된 함수들이 모두 같은 안전성을 갖는 것은 아니다. 특히 MD5와 SHA-1은 충돌 저항성이 깨진 함수이므로, 충돌 저항성을 요구하는 용도로 안전하다고 보아서는 안 된다

5.6 생일 공격

생일 공격(Birthday Attack)

많은 입력의 해시값을 비교하여, 생일 역설을 이용해 예상보다 적은 시도로 충돌을 찾는 공격이다

5.6.1 생일 역설

한 사람의 생일이 특정 날짜와 같은 경우를 찾는 것과, 여러 사람 중 생일이 같은 두 사람을 찾는 것은 다르다

1년을 365일로 단순화하면, 23명만 있어도 생일이 같은 두 사람이 존재할 확률이 약 50%를 넘는다

비교 대상이 늘어날수록 비교 가능한 쌍의 수가 빠르게 증가하기 때문이다

5.6.2 해시 충돌 탐색의 계산량

이상적인 $m$ 비트 해시 함수에 대해 일반적인 공격 계산량은 다음과 같다

공격	대략적인 계산량
주어진 해시값의 역상 탐색	$2^{m}$
주어진 입력의 제2역상 탐색	$2^{m}$
임의의 충돌 쌍 탐색	$2^{m /2}$

따라서 64비트 해시의 충돌 저항성은 약 $2^{32}$ 수준의 작업량에 해당한다

64비트 출력을 사용한다고 해서 모든 공격에 대해 $2^{64}$ 수준의 계산량을 요구하는 것은 아니다

5.6.3 전자서명에 대한 생일 공격

공격자가 정상 문서와 위조 문서를 조금씩 바꾸어 서로 다른 두 문서 집합을 생성한다고 하자

의미를 유지하는 정상 문서의 변형을 약 $2^{m /2}$ 개 생성한다
공격자가 원하는 위조 문서의 변형도 약 $2^{m /2}$ 개 생성한다
두 집합의 해시값을 비교한다
같은 해시값을 갖는 정상 문서와 위조 문서의 쌍을 찾는다
정상 문서에 서명하도록 유도한다
그 서명을 같은 해시값의 위조 문서에 붙여 악용한다

두 집합의 해시값이 충분히 무작위처럼 분포한다면, 이 정도 크기에서 집합 사이의 충돌 가능성이 높아진다

충돌 공격과 제2역상 공격의 차이

이미 정해진 문서 하나를 그대로 두고 같은 해시값의 다른 문서를 찾는 것은 제2역상 공격이다. 생일 공격에서는 공격자가 양쪽 문서를 모두 변형할 수 있다는 점이 중요하다

5.6.4 출력 길이의 중요성

이상적인 해시 함수에서 약 $s$ 비트 수준의 충돌 저항성을 얻으려면 대략 $2 s$ 비트 출력이 필요하다

$m = 2 s \Rightarrow 2^{m /2} = 2^{s}$

예를 들어 256비트 해시는 일반적인 생일 공격에 대해 약 $2^{128}$ 의 작업량을 요구한다. 다만 이 계산은 해시 함수 자체에 더 효율적인 약점이 없다는 가정에 따른다

6. 전자서명

전자서명(Digital Signature)

서명자의 개인키로 생성하고 공개키로 검증하여, 메시지의 출처와 무결성을 확인하고 부인 방지를 지원하는 기술이다

전자서명은 메시지 내용과 서명자의 개인키에 의존하는 비트열이다. 종이에 쓰는 서명처럼 모든 문서에 같은 모양을 붙이는 방식이 아니라, 서명 대상 메시지에 연결된 값을 생성한다

6.1 전자서명이 제공하는 기능

기능	설명
메시지 출처 인증	해당 개인키를 가진 주체가 서명했는지 확인한다
무결성 확인	서명 이후 메시지가 변경되었는지 검증한다
부인 방지 지원	서명자가 나중에 서명 사실을 부인할 때 검증 가능한 근거를 제공한다
제3자 검증	공개키를 가진 제3자도 서명을 검증하여 분쟁 해결에 활용할 수 있다

서명 대상에 날짜와 시간을 포함하면 그 정보가 변경되지 않았는지도 확인할 수 있다

서명 시각의 확인

전자서명 자체가 실제 서명 시각까지 자동으로 증명하는 것은 아니다. 서명된 날짜·시간이 사실인지 확인하려면 신뢰할 수 있는 타임스탬프 등의 추가 수단이 필요하다

6.2 전자서명의 요구사항

요구사항	의미
메시지 의존성	서명값이 서명 대상 메시지에 의존해야 한다
서명자 고유 정보 사용	위조와 부인을 막기 위해 서명자의 개인키와 같은 정보를 사용해야 한다
생성의 효율성	정당한 서명자가 서명을 효율적으로 생성할 수 있어야 한다
검증의 효율성	공개키를 이용하여 서명을 효율적으로 확인할 수 있어야 한다
저장의 실용성	메시지와 서명의 사본을 보관하기에 적절해야 한다
위조의 어려움	개인키 없이 유효한 메시지·서명 쌍을 만들기 어려워야 한다

위조의 어려움에는 다음 두 경우가 포함된다

기존 서명에 맞는 다른 메시지를 만드는 것
주어진 메시지에 대한 유효한 서명을 새로 만드는 것

6.3 직접 전자서명

직접 전자서명(Direct Digital Signature)

서명과 검증 과정이 송신자와 수신자 사이에서 직접 이루어지는 방식이다

기본 전제는 다음과 같다

송신자는 자신의 개인키를 비밀로 보관한다
수신자는 송신자의 올바른 공개키를 확보하고 있다

송신자는 메시지에 서명하고, 수신자는 공개키로 검증한다. 공개키의 신뢰성을 확인하기 위해 인증서 등을 활용하는 것은 별도의 키 관리 문제이다

6.3.1 서명 처리 방식

방식	설명
메시지 전체에 개인키 연산 적용	RSA의 기본 연산으로 인증 원리를 설명하는 단순화된 방식
해시값에 개인키 연산 적용	메시지를 해시한 뒤 그 결과에 개인키 연산을 적용
전자서명 전용 알고리즘 사용	정해진 서명 생성·검증 알고리즘을 사용

실제 전자서명은 알고리즘에 맞는 인코딩과 검증 절차를 포함한다. 따라서 서명을 단순히 개인키 암호화와 동일한 개념으로 이해해서는 안 된다

6.4 해시를 이용한 서명과 검증

6.4.1 서명 생성

송신자가 메시지 $M$ 의 해시값을 계산한다
개인키를 사용하는 서명 알고리즘으로 서명을 생성한다
메시지와 서명을 함께 전송한다

개념적으로 다음과 같이 나타낼 수 있다

$h = H (M)$

$σ = Sign_{P R_{A}} (M)$

여기서 서명 알고리즘은 내부적으로 메시지의 해시값과 필요한 인코딩 등을 처리할 수 있다

6.4.2 서명 검증

수신자는 메시지 $M$ 과 서명 $σ$ 를 받는다
송신자의 공개키 $P U_{A}$ 로 검증한다
유효한 서명인지 확인한다

$Verify_{P U_{A}} (M, σ) \in {유효, 무효}$

메시지가 변경되거나 서명이 올바르지 않으면 검증에 실패해야 한다

6.4.3 해시를 사용하는 이유

긴 메시지를 고정된 길이의 값으로 요약할 수 있다
메시지 전체에 비싼 공개키 연산을 반복하는 부담을 줄일 수 있다
서명을 메시지의 내용과 연결할 수 있다

해시 충돌을 찾을 수 있으면 같은 해시값을 갖는 다른 메시지에 서명을 악용할 가능성이 있으므로 충돌 저항성이 중요하다

6.5 RSA 전자서명의 기본 원리

RSA의 기본 연산으로 서명의 원리를 단순화하면 다음과 같다

서명자의 공개키는 $(e, n)$ , 개인키는 $(d, n)$ 이다

6.5.1 서명 생성

메시지에서 만든 정수 표현을 $h$ 라고 하면 다음과 같이 개인 지수로 처리한다

$s = h^{d} mod n$

6.5.2 서명 검증

검증자는 공개 지수로 다음을 계산한다

$v = s^{e} mod n$

RSA의 성질에 따라 다음이 성립한다

$v = (h^{d})^{e} mod n = h$

검증자는 이 결과가 메시지에서 계산한 값과 일치하는지 확인한다

기본 RSA 연산과 실제 서명

위 식은 원리 설명을 위한 단순화이다. 실제 서명에서는 해시값을 그대로 거듭제곱하지 않고, RSA-PSS와 같은 서명 방식에 정해진 인코딩·패딩 및 검증 절차를 적용해야 한다

6.5.3 그림으로 보는 처리 과정

그림 부분	내용	캡션
맨 위 흐름도	메시지 전체에 개인키 연산을 적용하고 공개키로 확인하는 개념	메시지 전체를 처리하는 RSA 인증의 기본 개념
가운데 흐름도	메시지를 해시한 뒤 서명하고, 수신 측에서 해시값을 비교	해시를 이용한 RSA 서명 생성과 검증
맨 아래 그림	개인키로 생성한 서명을 메시지와 보내고 공개키로 검증	전자서명의 생성·전송·검증 과정

가운데 그림의 기호는 다음을 뜻한다

기호	의미
$M$	메시지
$H$	해시 함수
$K R_{A}$	A의 개인키
$K U_{A}$	A의 공개키
$∥$	메시지와 서명을 이어 붙여 전송
Compare	메시지에서 계산한 해시값과 서명에서 확인한 값을 비교

6.6 직접 전자서명의 관리 문제

6.6.1 공개키의 신뢰성

수신자가 가진 공개키가 실제 송신자의 것인지 확인해야 한다. 공격자의 공개키를 송신자의 키로 잘못 받아들이면, 공격자가 생성한 서명을 정상 서명으로 믿을 수 있다

이를 해결하려면 공개키와 소유자의 신원을 신뢰할 수 있게 연결하는 수단이 필요하다

6.6.2 개인키 분실과 유출

상황	영향
개인키 분실	해당 키로 새로운 서명을 생성할 수 없다
개인키 유출	공격자가 서명자를 사칭하여 서명을 생성할 수 있다
유출 시점이 불명확함	어떤 서명이 정당하게 생성되었는지 판단하기 어려워질 수 있다

개인키를 분실했다고 해서 기존 서명을 공개키로 검증할 수 없게 되는 것은 아니다. 그러나 유출은 서명의 신뢰성에 직접적인 영향을 준다

6.7 전자서명과 다른 보안 기능의 구분

구분	일반 해시	MAC	전자서명
사용하는 키	없음	공유 비밀키	개인키·공개키
생성 가능한 주체	누구나	공유키를 가진 당사자	개인키 소유자
검증 가능한 주체	누구나 계산·비교 가능	공유키를 가진 당사자	공개키를 가진 누구나
송신자 인증	단독으로 제공하지 않음	제공	제공
제3자에게 서명자 증명	불가능	공유키만으로는 구분하기 어려움	지원
메시지 기밀성	제공하지 않음	제공하지 않음	제공하지 않음

전자서명은 메시지 내용을 숨기지 않는다. 기밀성까지 필요하다면 앞서 살펴본 것처럼 암호화를 함께 적용해야 한다

타이의 노트

노트 탐색

[컴퓨터보안] 4. 암호 도구와 응용

1. 블록 암호 운용 모드

1.1 전자 코드북 모드

1.1.1 암호화와 복호화

1.1.2 반복 패턴의 노출

1.2 카운터 모드

1.2.1 암호화

1.2.2 복호화

1.2.3 카운터 관리

1.2.4 CTR의 장점

1.2.5 무결성의 한계

1.3 ECB와 CTR의 비교

2. AES

2.1 블록 크기와 키 길이

2.2 상태와 키 확장

2.2.1 상태

2.2.2 키 확장

2.3 라운드를 구성하는 연산

2.3.1 바이트 치환(SubBytes)

2.3.2 행 이동(ShiftRRows)

2.3.3 열 혼합(MixColumns)

2.3.4 라운드 키 결합(AddRoundKey)

2.4 전체 암호화 과정

2.4.1 초기 키 결합

2.4.2 일반 라운드

2.4.3 마지막 라운드

2.5 복호화 과정

2.6 구현상의 특징

3. 공개키 암호

3.1 대칭키 방식의 한계와 공개키 방식

3.1.1 키 분배 문제

3.1.2 전자서명 문제

3.2 공개키 암호화의 구성 요소

3.3 기밀성을 위한 공개키 암호화

3.4 인증을 위한 개인키 사용

3.5 기밀성과 인증의 결합

3.6 공개키 암호 시스템의 활용

3.7 공개키 암호의 요구사항

3.8 트랩도어 일방향 함수

3.9 공개키 암호에 대한 공격

3.9.1 개인키 전수조사

3.9.2 공개키에서 개인키 계산

3.9.3 평문 후보 추측 공격

4. RSA

4.1 기본 구조

4.1.1. 메시지 블록의 크기

4.2 키 생성

4.2.1 두 소수 선택

4.2.2 모듈러스 계산

4.2.3 오일러 피 함수 계산

4.2.4 공개 지수 선택

4.2.5 개인 지수 계산

4.2.6 키 생성 결과

4.3 암호화와 복호화

4.3.1 암호화

4.3.2 복호화

4.4 복호화가 가능한 이유

4.4.1 오일러 정리

4.4.2 서로소가 아닌 평문

4.5 키 생성 예제

4.6 암호화, 복호화 계산 예제

4.6.1 반복 제곱법

4.6.2 암호화

4.6.3 복호화

4.7 RSA의 요구사항

4.8 RSA에 대한 공격

4.8.1 전수조사 공격

4.8.2 수학적 공격

4.8.3 타이밍 공격

4.9 소수와 개인 지수의 선택

4.10 소인수분해 기록과 안전성

4.11 기본 RSA 연산과 실제 암호화의 구분

5. 해시 함수

5.1 기본 특징

5.2 충돌

5.3 해시 함수의 요구사항

5.3.1 역상 저항성

5.3.2 제2역상 저항성