[암호학] 공개키 암호 (Public Key Cryptography)

---

수학적 배경

1. 정보 이론

1-1. 정보량 (Entropy, 엔트로피)

메시지 중 의미를 가지는 모든 것을 부호화하는 필요한 비트 수

n은 알파벳 기호 수, 각 기호의 발생확률이 동일할 때 정보원 X의 엔트로피 H(X)

1-2. 중복도

1. 언어비 r

X는 메시지, N은 메시지의 길이

2. 절대비 R

L문자 언어의 절대비, ex) 알파벳의 경우 26개 => 절대비 R = log2 26

3. 중복도 D

D = R - r

 

---

암호 시스템의 안전성

• 좋은 암호 알고리즘은 평문에 대한 정보를 최소화함
• 중복도 D가 클수록 공격이 쉬움
• 암호 시스템의 엔트로피는 키 공간의 크기 K가 척도이다

암호 시스템의 엔트로피는 그 시스템에서 사용되는 비밀키의 무작위성 정도를 측정하는 지표입니다.

즉, 엔트로피가 높을수록 암호 시스템에서 사용되는 비밀키는 더 무작위적이며, 이로 인해 암호화된 데이터를 해독하는 것이 더욱 어려워집니다.

암호 시스템에서 엔트로피를 높이기 위해서는 보안적으로 안전한 난수 생성기를 사용하여 무작위적인 비밀키를 생성하거나, 더 긴 비밀키를 사용하는 등의 방법을 사용할 수 있습니다.

판별 거리 (Unicity Distance)

U : 암호를 해독하는데 암호문 몇개가 필요한지를 계산한 것

판별거리 U↑ 면, 좋은 암호 시스템 = H(K) ↑, 중복도 D↓

---

2. 복잡도 이론

2-1. 알고리즘의 복잡도

• 컴퓨터의 능력에 따라 결정됨
• 시간 복잡도 T, 공간 복잡도 S가 척도
• T, S는 입력 크기 n의 함수로 나타냄
• 알고리즘은 시간/공간 복잡도에 의해 분류

ex) 시간복잡도가

인 알고리즘의 계산량적 복잡도는 

빅오표기법, 최고차항

 

2-2. 문제의 복잡도

• 문제 자체가 가지는 복잡도
• 튜링 기계로 문제 해결하는데 필요한 최소 시간과 공간을 조사 → 문제의 복잡도 조사

다항식 시간 알고리즘 → 현실적인 시간으로 해결 가능

지수 시간 알고리즘 → 유한 시간 내에서는 실행 불가능

 

2-2-1. 복잡도의 분류

P < NP < NP-complete < PSPACE < PSPACE-complete < EXPTIME

 

Class P

결정적 알고리즘으로 다항식 시간 내에 풀 수 있는 모든 문제

Class NP

비결정 튜링 머신을 이용했을 때만 다항식 시간 내에 풀 수 있는 모든 문제
NP는 P를 포함

NP-complete

P는 NP를 포함하는지 알아보려고 만들어진 문제
"쉽게 안풀리는 문제"

P=NP
: 모든 NP문제를 결정 머신으로 다항식 시간 내에 풀 수 있음

P!=NP
: 복잡도 이론에서는 P!=NP로 믿고 있음, 아직 풀지 못함

PSPACE

모든 문제를 다항식 공간에서 풀 수 있음
NP포함

EXPTIME

문제를 지수 시간 내에 풀 수 있음

---

체(Field)

• 사칙 연산을 정의할 수 있는 집합
• 곱셈에 대하여 0이 아닌 원소가 역원을 가짐

유한체(Finite field)

• 유한 집합인 체, Galois field
• GF()로 표시
• 덧셈, 곱셈, 교환법칙, 결합법칙, 분배법칙 성립
• 암호에서는 P를 큰 소수로 하여 GF(P)에 근거한 유한체에 의한 계산 이용

---

공개키 암호

(암호화 키, 복호키)의 쌍, 서로 다른 2개의 키를 이용
암호화 키는 공개, 복호키는 비밀로 둠
대칭키 암호에 비해 암호화/ 복호 속도가 느림

어려운 수학 문제에 기초하여 알고리즘이 설계됨

• 암호
• 전자서명
• 키 분배

---

공개키 암호에서 사용되는 것

: 일방향 함수 (trapdoor one way function)

한쪽으로의 연산은 쉽게 되지만 그 역 연산은 어려운 함수

ex) 소인수 분해 문제

: 소수 p와 q를 알때 n = pq 계산은 쉬우나, p와 q 가 큰 소수 일 때 n을 보고 p와 q를 구하는 것은 어려움

 

이산대수문제(이산로그)

---

공개키 암호 절차

상대방의 공개키를 가지고 메시지 M을 암호화해서 전송, 자신의 비밀키로 암호문을 복호

B가 A에게 암호문을 전송 하는 절차

1. A는 B에게 P_A (A의 공개키)를 전송

2. B는 C = E_P_A(M)을 계산하여 A에게 전송(A의 공개키로 암호화)

3. A는 D_S_A(C) = M 복호(A의 비밀키로 복호)

 

---

공개키 암호에서 평문/암호문 처리

• 공개키 암호에서도 평문과 암호문은 블록 단위로 나누어 연산 수행
• 블록의 크기는 보통 512 또는 1024 비트
• 블록단위로 암호 연산을 수행하므로 패딩(padding)과정이 필요

 

*암호 알고리즘에서 패딩할 비트의 패턴을 정의하지 않음, 구현단계에서 적절히 패딩 실행

*대칭키 암호, 공개키 암호, 해시 함수, 전자 서명 등 암호학에서 다루는 대부분의 기초 알고리즘은 블록 단위로 연산된다.

**스트림암호 제외

 

---

공개키 암호의 안전성

공격자는 언제든 공개키에 접근 가능

- 암호화할 메시지 선택 가능

- 선택 평문 공격 가능 -> 선택 평문 공격에 강하도록 설계 되어야함

 

어려운 문제에 기반하여 설계됨

- 일방향 함수 이용

- 어려운 수학적 문제의 해결 가능성 고려