[컴퓨터보안] 3. 현대 암호학 기법

1. 개요

기존에는 경험과 직관에 기반한 경험적 방법(Heuristic)으로 암호를 설계하고, 공격을 통해 약점을 발견하면 수정하는 과정이 반복되었다. 그러나 이러한 방식만으로는 암호의 안전성을 충분히 보장하기 어렵다. 따라서 다음과 같은 질문이 등장한다.

• “어떤 암호화 방식이 안전하다는 것을 증명할 수 있을까?”

이를 위해서는 먼저 ‘안전하다’는 것이 무엇인지 정확하게 정의해야 한다

1.1 현대 암호학의 등장

과거의 암호학은 설계자의 경험과 직관에 의존하는 기예에 가까웠으며, 설계와 분석도 주로 경험적으로 이루어졌다. 1980년대 초부터 암호학은 수학적 정의와 명시적인 가정, 엄밀한 증명을 바탕으로 하는 과학으로 발전하기 시작했다

현대 암호학의 핵심 원칙은 다음 세 가지이다

원칙	의미
형식적 정의(Formal Definitions)	보안이 무엇을 의미하는지 정확한 수학적 모델과 정의로 표현한다
가정(Assumptions)	안전성의 근거가 되는 가정을 명확하게 제시한다
안전성 증명(Proofs of Security)	명시한 가정 아래에서 암호 방식이 정해진 보안 정의를 만족함을 엄밀하게 증명한다

1.1.1 형식적 정의

형식적 정의(Formal Definitions)

암호의 안전성을 분석할 수 있도록 보안의 의미와 공격자의 능력, 공격의 성공 조건을 수학적으로 명확하게 표현하는 것이다

단순히 “해독하기 어렵다”는 설명만으로는 안전성을 정확하게 판단할 수 없다. 다음과 같은 조건을 명시해야 한다

• 보안 목표: 무엇을 보호하고, 공격자가 무엇을 알아내지 못하게 할 것인가?
• 공격자의 능력: 공격자는 어떤 정보를 얻거나 어떤 기능을 이용할 수 있는가?
• 성공 조건: 어떤 결과를 공격의 성공으로 판단할 것인가?

예를 들어, 암호문만 관찰하는 공격자와 자신이 선택한 평문의 암호화 결과까지 얻을 수 있는 공격자는 능력이 다른다. 따라서 어떤 공격자를 상대로 무엇을 보장하는지 함께 정의해야 한다

1.1.2 가정

계산적 가정(Computational Assumption)

특정 계산 문제를 주어진 계산 자원과 시간 안에 해결하기 어렵다고 가정하는 것이다

일부 예외를 제외하면 현대 암호학의 안전성은 계산적 가정에 의존한다

• 안전성의 근거가 되는 가정은 명시적으로 제시해야 한다
• 가정의 의미를 명확하게 표현해야 한다
• 숨겨진 가정이나 모호한 전제에 의존해서는 안 된다

예를 들어, 특정 조건에서의 소인수분해나 이산로그 문제를 효율적으로 해결하기 어렵다는 가정을 사용할 수 있다

가정과 증명의 구분

어떤 문제가 어렵다는 가정 자체가 증명된 사실인 것은 아니다. 암호 방식의 안전성을 증명하더라도, 그 증명이 의존하는 가정이 성립하는지 구분해서 이해해야 한다

1.1.3 안전성 증명

안전성 증명(Proofs of Security)

명시한 가정 아래에서, 설계한 암호 방식이 정해진 보안 정의를 만족함을 엄밀하게 입증하는 것이다

안전성 증명은 단순히 알려진 공격을 시험하여 문제가 없음을 확인하는 것과 다르다

• 정해진 공격 모델에서 보안 목표가 달성된다는 수학적 근거를 제공한다
• 설계 -> 공격 -> 수정을 반복하는 경험적 접근을 넘어선다
• 암호를 의도적으로 깨뜨리려는 악의적인 공격자가 존재하므로 특히 중요한다

안전성 증명의 기본 관계는 다음과 같다

• 명시한 가정이 성립한다면, 해당 암호 방식은 정해진 보안 정의를 만족한다

안전성 증명이 보장하는 범위

안전성 증명은 채택한 보안 정의, 위협 모델, 가정 안에서의 보장이다. 실제 프로그램의 구현 오류, 키 유출, 모델에서 고려하지 않은 공격까지 자동으로 방어한다는 뜻은 아니다

---

2. 암호의 안전성

암호의 안전성을 정의하려면 무엇을 보호할 것인지와 어떤 공격자를 상대할 것인지를 함께 명시해야 한다

요소	의미	핵심 질문
보안 보장/목표(Security/Goal)	달성하려는 목표 또는 공격자가 달성하지 못하도록 막으려는 것	무엇을 보호할 것인가?
위협 모델(Threat Model)	공격자가 현실에서 가지고 있다고 가정하는 능력	공격자는 무엇을 할 수 있는가?

같은 암호화 방식이라도 어떤 능력을 가진 공격자를 상대하는지에 따라 안전성 평가가 달라질 수 있다

2.1 비밀키 암호화

비밀키 암호화(Private-Key Encryption)

송신자와 수신자가 동일한 비밀키를 사용하여 메시지를 암호화하고 복호화하는 방식이다. 대칭키 암호화라고도 한다

비밀키 암호화 방식은 메시지 공간 $M$과 세 가지 알고리즘($Gen,Enc,Dec$)으로 정의된다. 메시지 공간 $M$은 해당 암호화 방식에서 처리할 수 있는 평문들의 집합이다

알고리즘	역할	입력과 출력
Gen	키 생성	비밀키 k를 생성
Enc	암호화	키 k와 평문 m을 입력받아 암호문 c를 출력
Dec	복호화	키 k와 암호문 c를 입력받아 평문 m을 출력

암호화와 복호화는 다음과 같이 표현한다

$c\leftarrow {\mathrm{Enc}}_k(m),m:={\mathrm{Dec}}_k(c)$

• $k$: 송신자와 수신자가 공유하는 비밀키
• $m\in \mathcal{M}$: 원래 메시지인 평문
• $c$: 암호화된 메시지인 암호문

정확성을 만족하려면 올바른 키로 암호화한 결과를 복호화했을 때 원래 평문이 나와야 한다

${\mathrm{Dec}}_k({\mathrm{Enc}}_k(m))=m$

정확성과 안전성의 차이

정확성은 정상적인 수신자가 원래 평문을 복원할 수 있는가에 관한 조건이다. 정확하게 복호화된다는 사실만으로 공격자에게도 안전한 암호가 되는 것은 아니다

2.2 안전한 암호화의 목표

암호화의 안전성은 단순히 키나 평문 전체를 알아내기 어렵다는 것만으로 정의할 수 없다

불충분한 설명	문제점
공격자가 키를 알아낼 수 없다	키를 몰라도 평문의 내용이 드러날 수 있다
공격자가 평문 전체를 알아낼 수 없다	평문의 90%가 드러나더라도 이 조건은 만족할 수 있다
공격자가 평문의 특정 문자를 알아낼 수 없다	문자를 모르더라도 “급여가 일정 금액 이상이다”와 같은 정보가 드러날 수 있다

따라서 공격자가 평문에 관한 추가 정보를 얻는지를 기준으로 삼아야 한다

완전한 비밀 보호의 목표

공격자가 평문에 대해 어떤 사전 정보를 가지고 있더라도, 암호문은 평문에 관한 추가 정보를 누설해서는 안 된다

중요한 것은 공격자가 평문에 대해 아무것도 모르는 것이 아니라, 암호문을 관찰하여 새로운 정보를 얻지 못하는 것이다

2.3 확률과 표기법

2.3.1 확률변수와 확률분포

확률변수

실험의 결과에 따라 서로 다른 값을 갖는 변수이다. 각 값에는 그 값이 선택될 확률이 대응한다

확률분포는 확률변수가 각 값을 가질 가능성을 나타낸다

• 각 확률은 0 이상 1 이하이다
• 가능한 모든 값의 확률을 더하면 1이다

평문, 키, 암호문에는 다음 표기법을 사용한다

구분	가능한 값들의 집합	확률변수	특정 값
평문	메시지 공간 $\mathcal{M}$	$M$	$m$
키	키 공간 $\mathcal{K}$	$K$	$k$
암호문	암호문 공간 $\mathcal{C}$	$C$	$c$

• 공간은 가능한 모든 값의 집합이다
• 확률변수는 확률에 따라 어떤 값이 선택되는지를 나타낸다
• 특정 값은 실제로 선택되거나 관찰된 개별 값이다

예를 들어 $Pr[M=m]$은 평문을 나타내는 확률변수 $M$이 특정 메시지 $m$일 확률이다

2.3.2 조건부 확률

조건부 확률

어떤 사건이 발생했다는 조건 아래에서 다른 사건이 발생할 확률이다

$\mathrm{Pr}[A\mid B]=\frac{\mathrm{Pr}[A\cap B]}{\mathrm{Pr}[B]}(\mathrm{Pr}[B]>0)$

$\mathrm{Pr}[M=m\mid C=c]$는 암호문 $c$를 관찰했을 때 평문이 $m$일 확률이다

2.3.3 독립성

두 확률변수가 독립이면 한쪽의 값을 알아도 다른 쪽의 확률분포가 달라지지 않는다. 평문 $M$과 키 $K$가 독립이면 다음이 성립된다

$Pr[M=m,K=k]=Pr[M=m]Pr[K=k]$

이는 평문에 따라 키를 선택하거나, 키에 따라 평문을 선택하지 않는다는 뜻이다

2.3.4 전확률의 법칙

어떤 사건의 확률은 가능한 경우들을 나누어 각각의 확률을 더하는 방식으로 구할 수 있다

$\mathrm{Pr}[C=c]={\sum }_{m\in \mathcal{M}}\mathrm{Pr}[C=c\mid M=m]\mathrm{Pr}[M=m]$

즉, 각 평문이 선택될 확률과 그 평문에서 암호문 $c$가 나올 확률을 곱하여 모두 더한다

2.3.5 베이즈 정리

베이즈 정리는 암호문을 관찰한 뒤 평문의 확률을 계산할 때 사용한다

$\mathrm{Pr}[M=m\mid C=c]=\frac{\mathrm{Pr}[C=c\mid M=m]\mathrm{Pr}[M=m]}{\mathrm{Pr}[C=c]}$

단, $\mathrm{Pr}[C=c]>0$이어야 한다

2.4 평문, 키, 암호문의 확률분포

2.4.1 평문의 확률분포

평문의 확률분포는 상황과 공격자의 사전 지식에 따라 달라진다

예를 들어 다음과 같은 분포를 가질 수 있다

$\mathrm{Pr}[M=\text{a}]=0.7,\mathrm{Pr}[M=\text{z}]=0.3$

이는 암호문을 보기 전부터 평문이 a일 가능성을 70%, z일 가능성을 30%로 알고 있다는 뜻이다

모든 평문이 같은 확률로 선택될 필요는 없다

2.4.2 키의 확률분포

키의 확률분포는 키 생성 알고리즘 $Gen$이 결정한다

$\mathrm{Pr}[K=k]=\mathrm{Pr}[Gen\text{이 키 }k\text{를 출력}]$

일반적으로 균등분포를 사용하지만, 모든 암호화 방식에서 반드시 균등한 것은 아니다. 또한 평문과 키는 서로 독립적으로 선택한다고 가정한다

2.4.3 암호문의 확률분포

암호문의 확률분포는 다음 실험으로 결정된다

1. $Gen$으로 키 $K$를 생성한다
2. 평문의 확률분포에 따라 메시지 $m$을 선택한다
3. $c\leftarrow {\mathrm{Enc}}_k(m)$을 계산한다

즉, 암호문의 분포는 평문 분포, 키 분포, 암호화 알고리즘과 그 안에서 사용하는 무작위성에 결정된다

2.4.4 예제: 한 글자 이동 암호

키를 0부터 25까지 균등하게 선택한다고 하자

$\mathrm{Pr}[K=k]=\frac{1}{26}$

평문의 분포가 다음과 같을 때 암호문이 b일 확률을 구한다

$\mathrm{Pr}[M=\text{a}]=0.7,\mathrm{Pr}[M=\text{z}]=0.3$

암호문이 b가 되는 경우는 다음 두 가지이다

평문	키	암호문
a	1	b
z	2	b

따라서 다음과 같다

$\begin{array}{rl}\mathrm{Pr}[C=\text{b}]& =0.7\times \frac{1}{26}+0.3\times \frac{1}{26}\\ & =\frac{1}{26}\end{array}$

2.5 완전 비밀성

완전 비밀성

암호문을 관찰하더라도 평문에 관한 확률분포가 변하지 않는 성질이다

메시지 공간 위의 모든 평문 분포, 모든 평문 $m$, 발생 가능한 모든 암호문 $c$에 대해 다음이 성립해야 한다

$\mathrm{Pr}[M=m\mid C=c]=\mathrm{Pr}[M=m](\mathrm{Pr}[C=c]>0)$

수식	의미
$\mathrm{Pr}[M=m]$	암호문을 보기 전, 평문이 $m$일 확률
$\mathrm{Pr}[M=m\mid C=c]$	암호문 $c$를 본 뒤, 평문이 $m$일 확률

예를 들어 관찰 전 어떤 평문의 확률이 70%였다면, 관찰 후에도 70%로 유지되어야 한다

평문 전체를 알아내지 못하더라도, 평문의 일부 정보가 드러나거나 후보들의 확률이 달라지면 완전 비밀성을 만족하지 않는다

2.5.1 예제: 평문을 확정할 수 있는 경우

이동 암호의 키를 0부터 25까지 균등하게 선택하고, 평문의 분포는 다음과 같다고 하자

$\mathrm{Pr}[M=\text{one}]=\mathrm{Pr}[M=\text{ten}]=\frac{1}{2}$

one은 $k=3$일 때 rqh로 암호화된다. 반면 ten을 rqh로 바꾸려면 문자마다 다른 이동량이 필요하다

문자 변환	필요한 이동량
t → r	24
e → q	12
n → h	20

이동 암호는 모든 문자에 동일한 키를 적용하므로 ten → rqh는 불가능 하다. 따라서 다음과 같다

$\begin{array}{rl}\mathrm{Pr}[C=\text{rqh}]& =\frac{1}{26}\times \frac{1}{2}+0\times \frac{1}{2}\\ & =\frac{1}{52}\end{array}$

공격자가 rqh를 관찰하면 다음과 같이 평문을 확정할 수 있다

평문 후보	관찰 전	rqh 관찰 후
one	$1/2$	1
ten	$1/2$	0

따라서 이 이동 암호는 완전 비밀성을 만족하지 않는다

2.5.2 예제: 평문을 확정하지 못하는 경우

키를 0부터 25까지 균등하게 선택하고, 평문의 분포는 다음과 같다고 하자

$\mathrm{Pr}[M=\text{hi}]=0.3,\mathrm{Pr}[M=\text{no}]=0.2,\mathrm{Pr}[M=\text{in}]=0.5$

암호문 xy를 관찰했을 때 평문이 hi일 확률을 구한다

각 평문에서 xy가 나올 가능성

평문	필요한 이동량	변환 가능 여부
hi	h → x: 16, i → y: 16	$k=16$일 때 가능
no	n → x: 10, o → y: 10	$k=10$일 때 가능
in	i → x: 15, n → y: 11	동일한 키로 변환 불가능

암호문이 xy일 확률

$\begin{array}{rl}\mathrm{Pr}[C=\text{xy}]& =\frac{1}{26}\times 0.3+\frac{1}{26}\times 0.2+0\times 0.5\\ & =\frac{1}{52}\end{array}$

관찰 후 평문이 hi일 확률

• 베이즈 정리를 적용한다

$\begin{array}{rl}\mathrm{Pr}[M=\text{hi}\mid C=\text{xy}]& =\frac{\mathrm{Pr}[C=\text{xy}\mid M=\text{hi}]\mathrm{Pr}[M=\text{hi}]}{\mathrm{Pr}[C=\text{xy}]}\\ & =\frac{\frac{1}{26}\times 0.3}{\frac{1}{52}}\\ & =0.6\end{array}$

나머지 후보도 같은 방식으로 계산하면 다음과 같다

평문	관찰 전	xy 관찰 후
hi	30%	60%
no	20%	40%
in	50%	0%

공격자는 hi와 no중 어느 것인지 확정하지는 못하지만, in일 가능성을 배제하고 나머지 후보의 확률을 갱신할 수 있다. 따라서 완전 비밀성을 만족하지 않는다

2.4.3 이동 암호의 한계

여러 문자에 동일한 이동량을 적용하면 문자 사이의 상대적인 간격과 반복 구조가 유지된다. 공격자는 이 구조를 이용하여 일부 평문 후보를 배제할 수 있다

한 글자와 여러 글자의 차이

한 글자 메시지에 26개 키를 균등하게 사용하는 이동 암호는 완전 비밀성을 만족한다. 그러나 여러 글자에 같은 키를 적용하는 이동 암호는 일반적으로 완전 비밀성을 만족하지 않는다

2.6 일회용 패드

일회용 패드(One-Time Pad, OTP)

평문과 같은 길이의 키를 평문과 독립적으로 균등하게 무작위 선택하고, 평문과 키를 XOR하여 암호화하는 방식이다. 키는 비밀로 유지하고 한 번만 사용한다

2.6.1 키 생성, 암호화, 복호화

평문, 키, 암호문은 모두 $n$비트 문자열이다

$\mathcal{M}=\mathcal{K}=\mathcal{C}=\{0,1{\}}^n$

$\{0,1{\}}^n$은 길이가 $n$인 모든 비트 문자열의 집합이며, 원소의 개수는 $2^n$개 이다

알고리즘	동작
키 생성 (Gen)	$k\in \{0,1{\}}^n$을 균등하게 무작위 선택
암호화 (Enc)	$c=k\oplus m$
복호화 (Dec)	$m=k\oplus c$

각 키가 선택될 확률은 다음과 같다

$\mathrm{Pr}[K=k]=2^{-n}$

여기서 $\oplus$는 비트별 XOR 연산이다. 두 비트가 같으면 0, 다르면 1을 출력한다

2.6.2 정확성

암호문에 동일한 키를 다시 XOR하면 원래 평문을 얻는다

$$\begin{array}{rl}{\mathrm{Dec}}_k({\mathrm{Enc}}_k(m))& =k\oplus (k\oplus m)\\ & =(k\oplus k)\oplus m\\ & =0^n\oplus m\\ & =m\end{array}$$

이는 XOR의 다음 성질 때문이다

• 동일한 값끼리 XOR하면 모든 비트가 0이 된다
• 어떤 값에 0을 XOR하면 원래 값이 유지된다

따라서 일회용 패드는 올바른 키로 복호화하면 원래 평문이 복원되는 정확성을 만족한다

2.6.3 완전 비밀성의 직관

어떤 평문 $m$과 암호문 $c$를 선택하더라도 다음을 만족하는 키가 정확히 하나 존재한다

$k=m\oplus c$

따라서 관찰한 암호문은 모든 평문 후보와 대응할 수 있다

필요조건과 충분조건

모든 평문 후보가 가능하다는 것만으로는 완전 비밀성이 증명되지 않는다. 암호문을 관찰한 뒤에도 각 평문의 확률까지 그대로 유지되어야 한다

2.6.4 완전 비밀성 증명

임의의 평문 분포와 임의의 $m,c\in {0,1}^n$을 생각하자

1. 평문이 주어졌을 때 특정 암호문이 나올 확률

$m$을 $c$로 만드는 키는 $m\oplus c$ 하나이고, 키는 독립적이고 균등하게 선택된다

$\mathrm{Pr}[C=c\mid M=m]=\mathrm{Pr}[K=m\oplus c]=2^{-n}$

2. 특정 암호문이 나올 전체 확률

전확률의 법칙을 적용한다

$$\begin{array}{rl}\mathrm{Pr}[C=c]& =\sum _{m^{\prime }\in \mathcal{M}}\mathrm{Pr}[C=c\mid M=m^{\prime }]\mathrm{Pr}[M=m^{\prime }]\\ & =\sum _{m^{\prime }\in \mathcal{M}}{2}^{-n}\mathrm{Pr}[M=m^{\prime }]\\ & =2^{-n}\end{array}$$

3. 암호문 관찰 후 평문의 확률

베이즈 정리를 적용하면 다음과 같다

$$\begin{array}{rl}\mathrm{Pr}[M=m\mid C=c]& =\frac{\mathrm{Pr}[C=c\mid M=m]\mathrm{Pr}[M=m]}{\mathrm{Pr}[C=c]}\\ & =\frac{2^{-n}\mathrm{Pr}[M=m]}{2^{-n}}\\ & =\mathrm{Pr}[M=m]\end{array}$$

암호문을 관찰해도 평문의 확률분포가 변하지 않으므로 일회용 패드는 완전 비밀성을 만족한다

균등분포인 대상

평문이 균등하게 선택될 필요는 없다. 키가 평문과 독립적으로 균등하게 선택되어야 한다. 그 결과 암호문은 균등분포를 가지며, 평문의 사전 확률은 그대로 유지된다

2.6.5 키 재사용의 위험

같은 키로 두 평문을 암호화했다고 하자

$c_1=k\oplus m_1,c_2=k\oplus m_2$

기지 평문 공격

공격자가 $m_1$과 $c_1$을 알고 있다면 키를 복원할 수 있다

$k=c_1\oplus m_1$

이 키로 두 번째 평문도 복원할 수 있다

$m_2=c_2\oplus k$

암호문만 확보한 경우

두 암호문을 XOR하면 키가 사라진다

$\begin{array}{rl}{c}_1\oplus c_2& =(k\oplus m_1)\oplus (k\oplus m_2)\\ & =m_1\oplus m_2\end{array}$

평문 전체가 즉시 드러나는 것은 아니지만, 두 평문 사이의 관계가 누설된다

일회 사용은 필수 조건

일회용 패드의 완전 비밀성은 키를 재사용하지 않는 조건에서 성립한다. 다른 메시지에는 새로운 독립적인 무작위 키를 사용해야 한다

2.6.6 활용의 한계

• 평문만큼 긴 무작위 키가 필요하다
• 키를 통신 상대에게 안전하게 전달해야 한다
• 사용한 키 구간을 다시 사용하지 않도록 관리해야 한다
• 여러 메시지를 보내려면 전체 평문 길이만큼의 새로운 키 자원이 필요하다

따라서 대규모 통신에서는 키 생성, 분배, 보관에 큰 부담이 발생한다

2.6.7 일회용 패드의 최적성

정확한 복호화가 가능하고 완전 비밀성을 만족하는 암호화 방식은 다음 조건을 만족해야 한다

$|\mathcal{K}|\ge |\mathcal{M}|$

일회용 패드는 $n$비트 키로 이 조건을 충족하므로 키 공간의 크기 측면에서 최적이다

키의 개수와 키의 길이

$|\mathcal{K}|\ge |\mathcal{M}|$는 우선 공간의 원소 개수에 관한 조건이다. 모든 $n$비트 평문과 고정 길이 이진 키를 사용하는 경우에 키 길이가 최소 $n$비트여야 한다는 결론을 얻는다

2.7 완전 비밀성의 한계

완전 비밀성은 계산 능력이 무제한인 공격자에게도 평문에 관한 추가 정보를 누설하지 않을 것을 요구한다. 이처럼 강한 보장은 충분한 키 자원을 필요로 하며, 실제 통신에서는 키 관리 부담으로 이어진다

더 실용적인 암호를 구성하기 위해 다음과 같이 요구사항을 완화할 수 있다

• 공격자를 계산 자원과 실행 시간이 제한된 공격자로 한정한다
• 공격자가 얻는 추가적인 구별 능력을 극히 작게 제한한다

이러한 접근이 계산적 비밀성(Computational Secrecy)의 출발점이다

---

3. 계산적 비밀성

완전 비밀성은 계산 능력이 무제한인 공격자에세도 평문에 관한 추가 정보를 누설하지 않을 것을 요구한다. 그러나 이를 만족하려면 긴 키와 엄격한 키 관리가 필요하다

계산적 비밀성은 다음 두 가지 방식으로 요구사항을 완화한다

• 공격자를 계산 자원과 실행 시간이 제한된 공격자로 한정한다
• 공격자가 무작위 추측보다 더 잘 구별할 가능성을 극히 작게 제한한다

계산적 비밀성(Computational Secrecy)

계산 자원이 제한된 공격자가 암호문으로부터 평문에 관한 정보를 얻거나, 어떤 평문이 암호화되었는지 구별하는 것이 사실상 불가능하도록 하는 보안 개념이다

3.1 아주 작은 확률과 제한된 계산 능력

3.1.1 아주 작은 확률

어떤 공격이 성공할 가능성이 0은 아니더라도, 그 가능성이 충분히 작다면 현실적으로 허용할 수 있다. 예를 들어 다음 확률은 매우 작다

예를 들어 다음 확률은 매우 작다

$2^{-60}\approx 8.67\times 10^{-19}$

매초 독립적으로 이 확률의 사건이 발생한다고 가정하면, 평균적으로 한 번 발생하기까지 약 365억 년이 걸린다

다만 암호의 안전성을 논할 때는 단순히 “작은 확률”이라고 표현하는 대신, 공격자의 계산량과 성공 확률 사이의 관계를 구체적으로 정의해야 한다

3.1.2 제한된 계산 능력

전수조사 공격으로 $n$비트 키를 찾으려면 최대 $2^n$개의 키를 시험해야 한다

예를 들어 키 공간이 $2^{128}$개이고 공격자가 $2^{112}$개의 서로 다른 키를 시험한다면, 균등하게 선택된 키를 그 안에서 찾을 확률은 다음과 같다

$\frac{2^{112}}{2^{128}}=2^{-16}$

공격자가 사용할 수 있는 계산량을 제한하면, 충분히 큰 키 공간을 모두 탐색하기 어렵게 만들 수 있다

큰 키 공간만으로는 충분하지 않다

전수조사보다 효율적인 공격이 존재할 수 있다. 계산적 안전성은 전수조사뿐 아니라 정의된 모델에서 허용되는 모든 효율적인 공격자를 대상으로 해야 한다

3.2 완전 구별 불가능성

계산적 비밀성을 정의하기 전에 완전 비밀성을 두 메시지를 구별하는 실험으로 다시 표현한다

완전 구별 불가능성(Perfect Indistinguishability)

공격자가 두 평문 중 하나를 암호화한 암호문을 받았을 때, 어느 평문이 암호화되었는지 무작위 추측보다 잘 맞힐 수 없는 성질이다

3.2.1 구별 실험

암호화 방식을 $\Pi =(Gen,Enc,Dec)$, 공격자를 $A$라고 하자

1. 공격자 $A$가 두 평문 $m_0,m_1$을 선택한다
2. 키 생성 알고리즘으로 비밀키 $k$를 생성한다
3. 비트 $b\in 0,1$을 균등하게 무작위 선택한다
4. 선택된 평문 $m_b$를 암호화한다

$c\leftarrow {\mathrm{Enc}}_k(m_b)$

5. 공격자에게 암호문 $c$를 제공한다
6. 공격자는 어느 평문이 암호화되었는지 추측하여 $b^{\prime }$를 출력한다
7. $b^{\prime }=b$이면 공격 성공으로 판정한다

이 실험을 ${\mathrm{PrivK}}_{A,\Pi }$로 나타내며, 성공하면 실험의 결과를 1로 기록한다

공격자는 자신이 선택한 두 평문을 모두 알고 있지만, 비밀키와 선택 비트 $b$는 모른다

3.2.2 성공 확률

공격자는 암호문을 분석하지 않고 무작위로 답해도 $\frac{1}{2}$의 확률로 성공할 수 있다. 따라서 안전성을 판단할 때는 암호문을 이용하여 이보다 더 높은 성공 확률을 얻을 수 있는가를 살펴본다

완전 구별 불가능성의 정의

모든 공격자 $A$에 대해 다음이 성립하면 암호화 방식 $\Pi$는 완전 구별 불가능성을 만족한다. $Pr[{\mathrm{PrivK}}_{A,\Pi }=1]=\frac{1}{2}$

여기서 모든 공격자에는 계산 능력이 무제한인 공격자도 포함된다. 아직 공격자를 효율적인 알고리즘으로 제한하지 않는다

예를 들어 어떤 공격자가 특정 평문 쌍에 대해 성공 확률 0.6을 달성한다면, 무작위 추측보다 더 잘 구별할 수 있으므로 완전히 구별 불가능성을 만족하지 않는다

3.2.3 완전 비밀성과의 관계

완전 구별 불가능성과 완전 비밀성은 동치이다

$\text{완전 비밀성}⟺\text{완전 구별 불가능성}$

개념	안전성을 표현하는 관점
완전 비밀성	암호문을 관찰해도 평문의 확률분포가 변하지 않는다
완전 구별 불가능성	두 평문 중 어느 것이 암호화되었는지 구별할 수 없다

같은 보안 성질을 서로 다른 방식으로 표현한 것이다

3.3 계산적 비밀성의 두 가지 접근

완전 구별 불가능성에서 공격자의 계산량을 제한하고, 작은 추가 성공 확률을 허용하면 계산적 구별 불가능성을 정의할 수 있다

접근 방식	핵심 기준
구체적 보안(Concrete Security)	실행 시간 $t$와 추가 성공 확률 $\epsilon$을 구체적인 값으로 제한한다
점근적 보안(Asymptotic Security)	보안 매개변수 $n$에 따라 실행 시간과 추가 성공 확률이 어떻게 변하는지 분석한다

3.4 구체적 보안

3.4.1 $(t,\epsilon )$-구별 불가능성

실행 시간이 $t$ 이하인 모든 공격자 $A$에 대해 다음이 성립하면, 암호화 방식 $\Pi$는 $(t,\epsilon )$-구별 불가능성을 만족한다

$\mathrm{Pr}[{\mathrm{PrivK}}_{A,\Pi }=1]\le \frac{1}{2}+\epsilon$

• $t$: 공격자에게 허용하는 최대 실행 시간 또는 계산량
• $\epsilon$: 무작위 추측보다 더 잘 맞힐 수 있는 정도의 상한

예를 들어 $\epsilon =0.001$이면, 허용된 계산량 안에서 공격자의 성공 확률은 최대 다음과 같다

$\frac{1}{2}+0.001=0.501$

$\epsilon$의 의미

$\epsilon$은 공격자의 전체 성공 확률이 아니다. 전체 성공 확률의 상한은 $\frac{1}{2}+\epsilon$이며, $\epsilon$은 무작위 추측의 성공 확률 $\frac{1}{2}$에 더해지는 부분이다

3.4.2 완전 구별 불가능성과의 관계

계산량을 제한하지 않고 추가 성공 가능성도 허용하지 않으면 완전 구별 불가능성이 된다

$(t,\epsilon )=(\infty ,0)$

계산적 접근은 이를 다음과 같이 완화한다

$t<\infty ,\epsilon >0$

3.4.3 특징과 한계

• 실제로 허용할 계산량과 성공 확률을 직접 표현할 수 있다
• 같은 암호 방식도 서로 다른 여러 $(t,\epsilon )$ 조합에 대해 평가할 수 있다
• 계산량을 측정하는 방식과 구현 환경에 따라 수치가 달라질 수 있다
• 일반적인 이론을 전개하기에는 구체적인 수치와 계산 모델을 계속 고려해야 하는 부담이 있다

3.5 점근적 보안

보안 매개변수(Security Parameter)

암호 방식의 보안 수준과 계산 비용을 조절하는 매개변수로, 일반적으로, $n$으로 나타낸다

• 정상적인 사용자가 키를 생성할 때 선택한다
• 공격자에게도 공개된다
• 키 길이 등 암호 방식의 여러 크기를 결정한다
• 정상적인 알고리즘과 공격자의 실행 시간을 $n$의 함수로 분석한다

처음에는 $n$을 키 길이와 비슷한 역할을 하는 값으로 이해할 수 있지만, 항상 실제 키 길이와 정확히 같은 것은 아니다

점근적 접근의 기준

대상	요구사항
공격자의 실행 시간	$n$에 대한 다항 시간으로 제한한다.
추가적인 구별 성공 확률	$n$에 대해 무시 가능한 함수로 제한한다.

보안 매개 변수가 커질수록 효율적인 공격자가 얻는 추가적인 구별 능력이 충분히 빠르게 작아져야 한다

3.6 다항 시간과 무시 가능한 함수

3.6.1 다항 시간

알고리즘의 실행 시간이 입력 크기 $n$의 다항식으로 제한되면 다항 시간(Polynomial Time) 알고리즘이라고 한다

예를 들면 다음과 같다

실행 시간	분류
$n$	다항 시간
$n^2$	다항 시간
$n^3$	다항 시간
$2^n$	지수 시간

확률적 다항 시간(Probabilistic Polynomial-Time, PPT) 알고리즘은 다항 시간 안에 실행되면서 내부적으로 무작위 선택을 사용할 수 있는 알고리즘이다. 암호학에서는 무작위 선택을 사용할 수 있는 다항 시간 알고리즘을 효율적인 알고리즘으로 취급한다

3.6.2 무시 가능한 함수

무시 가능한 함수(Negligible Function)

충분히 큰 $n$에서 모든 양의 다항식의 역수보다 작아지는 함수이다

함수 $\epsilon (n)$이 무시 가능하다는 것은 모든 양의 다항식 $p(n)$에 대해, 충분히 큰 $n$에서 다음이 성립한다는 뜻이다

$\epsilon (n)<\frac{1}{p(n)}$

함수	무시 가능 여부
$2^{-n}$	무시 가능
$n^3{2}^{-n}$	무시 가능
$\frac{1}{n}$	무시 불가능
$\frac{1}{n^{100}}$	무시 불가능
$2^{-60}$	$n$과 무관한 상수이므로 무시 불가능

$\frac{1}{n^{100}}$은 매우 빠르게 작아 보이지만, 예를 들어 $\frac{1}{n^{101}}$보다 작아지지는 않으므로 무시 가능한 함수가 아니다

작은 값과 무시 가능한 함수의 차이

“무시 가능”은 단순히 수치가 작다는 뜻이 아니다. 보안 매개변수 $n$이 증가할 때 감소하는 속도에 관한 성질이다. 따라서 아주 작은 상수 확률도 점근적 의미에서는 무시 가능하지 않다

3.6.3 이 기준을 사용하는 이유

다항 시간 연산의 결함

다항 시간 알고리즘이 다항 횟수만큼 다항 시간 하위 알고리즘을 호출해도 전체 실행 시간은 다항 시간이다

$\text{다항식}\times \text{다항식}=\text{다항식}$

무시 가능한 확률의 누적

실패 확률이 무시 가능한 작업을 다항 횟수만큼 수행해도, 전체 실패 확률은 여전히 무시 가능하 수준으로 제한할 수 있다

$\text{다항식}\times \text{무시 가능한 함수}=\text{무시 가능한 함수}$

이 성질은 여러 암호 기능을 결합하여 더 복잡한 방식을 구성할 때 유용하다

3.7 보안 매개변수를 포함한 비밀키 암호화

점근적 보안을 분석할 때는 키 생성 알고리즘에 보안 매개변수를 입력한다

알고리즘	입력	출력
키 생성 Gen	보안 매개변수 $1^n$	비밀키 $k$
암호화 Enc	키 $k$, 평문 $m\in \{0,1{\}}^{\ast }$	암호문 $c$
복호화 Dec	키 $k$, 암호문 $c$	평문 $m$ 또는 오류

$k\leftarrow Gen(1^n)$ $c\leftarrow {\mathrm{Enc}}_k(m)$ $m:={\mathrm{Dec}}_k(c)$

여기서 $1^n$은 숫자 1을 $n$번 나열한 단항 표기이다

예를 들어 다음과 같다

$1^4=1111$

입력 길이를 $n$으로 만들어 알고리즘의 실행 시간을 보안 매개변수 $n$에 대해 분석한다. 일반적인 메시지를 처리하는 암호화·복호화 시간은 메시지나 암호문의 길이도 함께 고려한다

3.8 계산적 구별 불가능성의 점근적 정의

3.8.1 구별 실험

보안 매개변수 $n$, 암호화 방식 $\Pi$, 공격자 $A$에 대해 실험 ${\mathrm{PrivK}}_{A,\Pi }(n)$을 정의한다

1. 공격자 $A$가 $1^n$을 입력받아 길이가 같은 두 평문 $m_0,m_1$을 출력한다
2. $k\leftarrow Gen(1^n)$으로 비밀키를 생성한다
3. $b\in 0,1$을 균등하게 무작위 선택한다
4. 선택된 평문을 암호화한다

$c\leftarrow {\mathrm{Enc}}_k(m_b)$

5. 공격자가 암호문 $c$를 보고 추측값 $b^{\prime }$를 출력한다
6. $b^{\prime }=b$이면 실험 결과를 1로 기록한다

두 평문의 길이를 같게 하는 이유는 암호문의 길이만으로 정답을 알아내는 경우를 제외하고, 평문의 내용이 구별되는지 평가하기 위해서이다

3.8.2 안전성 정의

모든 PPT 공격자 $A$에 대해 무시 가능한 함수 $\epsilon (n)$이 존재하여 다음을 만족하면, 암호화 방식 $\Pi$는 계산적 구별 불가능성을 만족한다

$\mathrm{Pr}[{\mathrm{PrivK}}_{A,\Pi }(n)=1]\le \frac{1}{2}+\epsilon (n)$

이 실험에서 정의한 안전성을 도청 공격에 대한 안전성(EAV Security)이라고도 한다

• 공격자는 효율적인 계산만 수행할 수 있다
• 암호문을 관찰하더라도 무작위 추측보다 유의미하게 더 잘 구별할 수 없어야 한다
• 성공 확률의 추가분은 무시 가능한 함수로 제한된다

도청 안전성의 보장 범위

이 실험은 하나의 도전 암호문을 관찰하는 상황을 다룬다. 이를 만족한다고 해서 같은 키로 여러 메시지를 암호화하는 경우나 선택 평문·선택 암호문 공격에 대한 안전성까지 자동으로 보장되지는 않는다

---

4. 암호학적 기본 요소의 구성

현대 암호학에서는 복잡한 보안 기능을 처음부터 개별적으로 설계하기보다, 더 단순한 기본 요소를 바탕으로 구성하고 안전성을 증명한다

암호학적 기본 요소

암호화, 인증, 무결성 검증 등 보안 기능을 구현하는 데 사용하는 기본적인 알고리즘이나 프로토콜이다

기본 요소	의미
일방향 함수(OWF, One-Way Function)	계산은 쉽지만 출력에서 역상을 찾기는 어렵게 한다
의사난수 생성기(PRG, Pseudorandom Generator)	짧은 무작위 시드로 더 긴 의사난수 문자열을 생성한다
의사난수 함수(PRF, Pseudorandom Function)	비밀키로 정해진 함수가 무작위 함수처럼 보이게 한다
의사난수 순열(PRP, Pseudorandom Permutation)	비밀키로 정해진 순열이 무작위 순열처럼 보이게 한다
해싱(Hashing)	메시지를 짧은 값으로 요약하며, 용도에 맞는 보안 성질을 제공한다
비밀키 암호화(Secret-Key Encryption)	송신자와 수신자가 공유하는 비밀키로 메시지를 암호화·복호화하는 방식
전자서명(Digital Signature)	메시지의 서명자를 확인하고 무단 변경을 검출하도록 한다
비트 커미트먼트(Bit Commitment)	비트값을 숨긴 채 미리 확정하고, 나중에 공개하는 프로토콜
영지식 증명(Zero-Knowledge Proof)	명제가 참임을 증명하면서, 그 사실 외의 추가 정보를 공개하지 않는 증명 방식

4.1 더 단순한 요소로부터 구성하기

암호학적 구성은 다음과 같은 방식으로 이루어진다

1. 기반이 되는 함수나 계산 문제를 정한다
2. 그 기반이 만족해야 하는 보안 성질이나 어려움에 관한 가정을 명시한다
3. 이를 이용하여 더 복잡한 보안 기능을 구성한다
4. 기반의 안전성을 이용하여 구성한 방식의 안전성을 증명한다

예를 들어, 일방향 함수로부터 의사난수 생성기를 구성하고, 이를 바탕으로 다른 암호 기능을 구성하는 방법을 연구할 수 있다

4.1.1 안전성 환원

안전성 환원

구성한 암호 방식을 효율적으로 공격할 수 있다면, 그 공격을 이용하여 기반이 되는 문제나 기본 요소의 안전성도 깨뜨릴 수 있음을 보이는 방법이다

안전성 환원의 논리는 다음과 같다

• 구상한 암호를 깨는 효율적인 공격자 $A$가 존재한다고 가정한다
• $A$를 이용하여 기반 문제를 푸는 효율적인 알고리즘 $B$를 만든다
• 기반 문제가 어렵다는 가정이 맞다면, 그러한 공격자$A$도 존재하기 어렵다고 결론 내린다

즉, 복잡한 암호 방식의 안전성 문제를 더 단순한 기반의 안전성 문제로 연결한다

4.2 암호학의 세계: Minicrypt와 Cryptomania

암호학에서는 어떤 기본 요소가 존재한다고 가정하는지에 따라 가능한 보안 기능을 구분한다

구분	핵심 가정과 기능
Minicrypt	일방향 함수의 존재를 바탕으로 의사난수 생성기, 의사난수 함수, 대칭키 암호화, 전자서명 등을 구성할 수 있는 범위
Cryptomania	공개키 암호화와 같은 더 강한 기능까지 가능한 범위

4.2.1 Minicrypt

일방향 함수가 존재하면 이를 바탕으로 여러 암호학적 기능을 구성할 수 있다

• 의사난수 생성기
• 의사난수 함수
• 의사난수 순열
• 안전한 대칭키 암호화
• 전자서명
• 비트 약정과 영지식 증명 등의 기능

이러한 구성에는 서로 다른 방식과 추가적인 정의가 필요하며, 모든 기능이 하나의 단순한 연산으로 바로 만들어지는 것은 아니다

4.2.2 Cryptomania

공개키 암호화에서는 송신자와 수신자가 동일한 비밀키를 미리 공유하지 않고도 기밀 통신을 수행할 수 있다

• 공개키: 다른 사람이 메시지를 암호화하는 데 사용한다
• 비밀키: 수신자가 암호문을 복호화하는 데 사용한다

이러한 기능을 구성하려면 일방향 함수의 존재만으로 알려진 것보다 더 강한 기반이 필요하다

일방향 함수와 공개키 암호화

일방향 함수가 존재한다는 사실만으로 공개키 암호화를 구성할 수 있는지는 알려져있지 않다. 또한 전자서명은 공개키로 검증하지만, 일방향 함수로부터 구성할 수 있다는 점에서 공개키 암호화와 구분해야 한다

4.3 주요 기본 요소의 역할

4.3.1 의사난수 생성기

짧은 무작위 시드에서 더 긴 문자열을 생성한다

• 같은 시드를 입력하면 같은 결과가 나온다
• 출력은 실제 무작위 문자열과 효율적으로 구별하기 어려워야 한다
• 단순히 복잡하거나 불규칙해 보이는 것만으로는 충분하지 않다

4.3.2 의사난수 함수

비밀키 $k$가 함수를 결정한다

$F_k(x)$

공격자가 여러 입력의 출력값을 확인하더라도, 비밀키를 모르면 이 함수와 진짜 무작위 함수를 효율적으로 구별하기 어려워야 한다

4.3.3 의사난수 순열

의사난수 순열은 입력과 출력 사이에 일대일 대응이 존재하는 의사난수 함수이다

• 정의역과 공역이 같다
• 각 출력에 대응하는 입력이 하나씩 존재한다
• 키를 알면 역방향 계산도 효율적으로 수해할 수 있다

블록 암호를 분석할 때 중요한 모델이다

4.3.4 해시, 전자서명, 약정, 영지식 증명

요소	역할
해시	입력을 짧은 값으로 요약한다. 역상 저항성·충돌 저항성 등 필요한 성질을 구분한다.
전자서명	비밀키로 서명하고 공개키로 검증하여 메시지의 출처와 무결성을 확인한다.
비트 약정(Bit Commitment)	선택한 값을 일단 숨겨 두고, 나중에 공개할 때 임의로 바꾸지 못하게 한다.
영지식 증명(Zero-Knowledge Proof)	어떤 주장이 참임을 증명하면서, 그 사실 외의 비밀 정보는 드러내지 않도록 한다.

4.4 일방향 함수

일방향 함수(One-Way Function, OWF)

입력에서 출력을 계산하는 것은 효율적이지만, 무작위 입력으로 생성한 출력이 주어졌을 때 그 출력의 역상을 찾기는 계산적으로 어려운 함수이다

4.4.1 순방향 계산과 역상 탐색

함수 $F$에 입력 $x$를 넣어 출력 $y$를 계산한다고 하자

$y=F(x)$

• 순방향 계산: $x$를 알고 $F(x)$를 계산한다
• 역상 탐색: $y$를 알고 $F(x^{\prime })=y$를 만족하는 입력 $x^{\prime }$를 찾는다

일방향 함수는 순방향 계산은 쉽지만 역상 탐색은 어렵다

원래 입력을 찾을 필요는 없다

공격자는 처음 사용된 입력 $x$와 정확히 같은 값을 찾을 필요가 없다. $F(x^{\prime })=F(x)$를 만족하는 어떤 역상 $x^{\prime }$라도 찾으면 성공이다

4.4.2 수학적 정의

함수족을 다음과 같이 나타내자

$F_n:\{0,1{\}}^n\to \{0,1{\}}^{\ell (n)}$

• $n$: 입력 길이이자 보안 매개변수
• $\ell (n)$: 출력 길이
• $F_n$: 효율적으로 계산할 수 있는 함수

다음 실험을 수행한다

1. 입력 $x\in {0,1}^n$을 균등하게 무작위 선택한다
2. $y=F_n(x)$를 계산한다
3. 공격자에게 $1^n$과 $y$를 제공한다
4. 공격자가 역상 후보 $x^{\prime }$를 출력한다
5. $x^{\prime }\in {0,1}^n$이고 $F_n(x^{\prime })=y$이면 성공으로 판단한다

모든 PPT 공격자 $A$에 대해 무시 가능한 함수 $\mu (n)$이 존재하여 다음이 성립해야 한다

$\mathrm{Pr}\left[F_n(A(1^n,F_n(x)))=F_n(x)\right]\le \mu (n)$

여기서 확률은 입력 $x$의 무작위 선택과 공격자의 내부 무작위성에 대해 계산한다. 공격자가 유효한 길이의 입력을 출력하지 않으면 실패로 처리한다

4.4.3 무제한 계산을 허용한 경우

계산 시간을 무제한으로 허용하면 모든 입력을 시험하여 역상을 찾을 수 있다. 따라서 일방향성은 역상 탐색이 수학적으로 불가능하다는 뜻이 아니다. 효율적인 공격자가 성공할 확률이 무시 가능해야 한다는 뜻이다

4.5 일방향 함수의 존재와 계산 복잡도

4.5.1 P와 NP의 관계

• P: 다항 시간 안에 답을 구할 수 있는 결정 문제들의 집합
• NP: 주어진 답이 맞는지 다항 시간 안에 검증할 수 있는 결정 문제들의 집합

일방향 함수의 존재와 다음 관계가 성립한다.

$P=NP\Rightarrow \text{일방향 함수는 존재하지 않는다}$

이를 대우로 표현하면 다음과 같다

$\text{일방향 함수가 존재한다}\Rightarrow P\ne NP$

그러나 그 역방향은 알려져 있지 않다

$P\ne NP$만으로는 충분하지 않다

$P\ne NP$이면 일방향 함수가 존재한다는 결론은 증명되지 않았다. $P\ne NP$는 최악의 경우의 어려움에 관한 구분이지만, 일방향 함수에는 무작위로 선택된 입력에 대해서도 역상 탐색이 어려워야 한다는 요구가 있다

4.5.2 의사난수 생성기와의 관계

의사난수 생성기와 일방향 함수의 존재는 동치이다

$\text{의사난수 생성기가 존재한다}⟺\text{일방향 함수가 존재한다}$

이는 한쪽이 존재하면 다른 쪽도 구성할 수 있다는 존재에 관한 결과이다. 두 개념이 같은 함수이거나, 실제 구현의 효율까지 같다는 뜻은 아니다

4.6 평균적인 경우에도 어려운 문제

암호학의 기반으로 사용할 문제는 일부 특별한 입력에서만 어려워서는 부족하다. 실제로 생성하는 입력의 분포에서 공격자가 높은 확률로 쉽게 풀 수 없어야 한다

구분	의미
최악의 경우의 어려움	문제의 입력 중 풀기 어려운 경우가 존재한다
평균적인 경우의 어려움	정해진 분포에서 생성되는 입력에 대해 문제를 해결하기 어렵다

4.6.1 NP-난해·NP-완전 문제의 활용 한계

대표적인 문제로 그래프 3색칠, 외판원 문제, 배낭 문제 등이 있다

그러나 이러한 문제의 일반적인 어려움만으로 암호의 안전성을 보장할 수는 없다

• 특정 입력들은 쉽게 해결될 수 있다
• 암호 방식이 생성하는 입력에 특별한 구조가 있을 수 있다
• 공격자가 그 구조를 이용하면 원래 문제 전체를 풀지 않고도 암호를 공격할 수 있다

따라서 문제의 이름이나 최악의 경우의 난도뿐 아니라, 입력 생성 방식과 실제 공격 문제를 함께 분석해야 한다

4.6.2 이산로그 문제

이산로그 문제(Discrete Logarithm Problem, DLP)

유한 순환군에서 생성원 $g$와 $h=g^x$가 주어졌을 때, 이를 만족하는 지수 $x$를 구하는 문제이다

순방향에서는 지수 $x$를 알고 다음을 계산한다

$h=g^x$

역방향에서는 $g$와 $h$를 알고 다음을 만족하는 $x$를 찾는다

$g^x=h$

모듈러 연산을 사용하는 간단한 예는 다음과 같다

$2^x\equiv 8(\mathrm{mod}11)$

이 경우 $x=3$이 한 해이다. 작은 예는 쉽게 풀 수 있지만, 적절한 군과 충분한 크기의 매개변수를 사용하는 경우의 어려움을 암호학적 가정으로 활용한다

4.6.3 소인수분해 문제

소인수분해 문제(Integer Factorization)

주어진 합성수를 소수들의 곱으로 분해하는 문제이다

예를 들어 다음과 같다

$N=pq$

• 순방향: 소수 $p,q$를 알고 곱 $N$을 계산한다
• 역방향: $N$을 알고 소인수 $p,q$를 찾는다

작은 수에서는 다음과 같이 쉽게 계산할 수 있다

$77=7\times 11$

암호학에서는 적절하게 생성한 큰 정수에 대한 소인수분해의 어려움을 활용한다

이산로그와 소인수분해 모두 모든 입력이 어렵다는 뜻은 아니다. 안전성은 사용하는 문제의 구체적인 형태, 입력 분포, 매개변수에 관한 가정을 바탕으로 판단한다