[Cryptography(암호학)] 5주차-Number Theory

본 포스팅은 Coursera | Cryptography - Jonathan Katz 강의를 수강하며 정리했습니다.

1-1 Number Theory One

Cryptography 5주차 강의정리를 시작하겠습니다. 이번 주차에서는 비대칭키 암호화를 위한 number Theory(정수론)에 대해 공부합니다. 먼저 특정 용어와 표기법을 정리하겠습니다.

1. Algorithmic number theory

암호학에서는 암호 알고리즘이 얼마나 효율적인지 알아보고자 복잡성을 측정합니다. Number Theory에서는 효율성에 대해 asymptotic efficiency를 측정하고, 보통 입력의 길이로 이를 판단합니다. 가령, 어떤 상수 $a$에 대한 크기 를 묻는다면, 그 자체로 숫자 값을 말하겠지만, 입력의 길이 는 비트로 환산한 $2^{|a|}$ 입니다.
뒤에서는 풀기 쉬운(easy) 문제와 어려운(hard) 문제를 나눌 것입니다. 여기서 말하는 풀기 쉬운(easy) 문제는 다항 시간 내에 효율적으로 해결이 가능한 문제로, 암호 알고리즘이 easy하다면 공격자에 의해 깨지기 쉬운 문제가 되겠죠.

2. Modular arithmetic

아래는 모듈러(Modular) 연산에 대한 표기와 설명입니다.

$[a\,\bmod\,N]$

• a를 N으로 나누었을 때 나머지
• $0 \le [a\,\bmod\,N] \le N-1$
• $a = b\,\bmod\,N \Leftrightarrow [a\,\bmod\,N] = [b\,\bmod\,N]$

말 그대로 a를 N으로 나눴을 때의 나머지를 말합니다. 나머지는 0과 N-1 사이의 정수가 될 것입니다. 익숙하지 않은 건 세 번째 표기일텐데요, 어떤 정수 $a$에 대하여 $a = b\,\bmod\,N$라는 것은 a를 N으로 나눈 나머지인 $[a\,\bmod\,N]$ 또한 a일 것이기 때문에 위 식이 성립합니다. 앞으로 우리는 특정 정수 집합 내에서의 모듈러(modular) 연산 표기를 하게 됩니다. 이때 요긴하게 사용될테니 잘 이해하고 넘어가시기 바랍니다.

| Algorithmic number theory

일반적인 표준 연산들을 살펴보면, 덧셈과 뺄셈은 효율적으로($O(n)$) 다항 시간 내에 풀 수 있습니다. 곱셈과 나눗셈도 조금 시간이 더 걸릴 뿐이지 이 또한 효율적 계산이 가능합니다($O(n^2)$). 마찬가지로 모듈러(modular) 연산의 산술도 동일합니다. 모듈러연산은 어떤 정수를 실제 값보다 축소하여 표현이 가능합니다. 축소된 두 정수를 덧셈, 뺄셈, 곱셈, 나눗셈하는 것 또한 그리 어렵지 않은 일이겠죠?

3. Exponentiation

앞서 모듈러(modular) 연산의 덧셈, 뺄셈, 곱셈, 나눗셈 산술은 다항 시간 내에 연산이 가능했습니다. 그럼 제곱 연산을 살펴봅시다. 어떤 상수 $a$에 대해 $b$ 제곱을 한다고 할 때, 결과값의 비트 크기는 $O(b*|a|)$ 입니다. 그럼 제곱 연산에 대한 실행 시간은 $b$ 만큼이 제곱으로 올라가기 때문에 매우 오래 걸리게 됩니다. 앞서 암호학에서는 특정 정수 집합 내에 있는 수만을 종종 다룬다고 했습니다. 고로 다행히도 우리가 할 제곱 연산은 연산이 진행될수록 무한대로 많아지는 것이 아니라 모듈러 연산 결과값을 다시 제곱하는 형태로 축소하여 진행합니다. 아래 코드를 살펴봅시다.

	exp (a, b, N) {
    	// assume b >= 0
    	ans = 1;
    	for (i=1, i <= b; i++)
    		ans = [ans * a mod N];
    	return ans;
    }

하지만 위처럼 제곱 연산을 진행한다고 해서 시간에 축소하는 것은 아닙니다. 모듈러(modular)에서 취하는 곱셈이더라도 어차피 b번 반복 진행하므로 시간 복잡도가 $O(b * n^2)$이 걸립니다. 만약 b의 값을 1024bit 정도 되는 수로 연산한다면, modular 곱셈 연산을 굉장히 많이하므로 매우 비효율적인 알고리즘이 되겠죠.

| Efficient exponentation

이 알고리즘을 더 수정해서 효율적으로 연산 가능하도록 만들어봅시다. Square and Multiply라는 아이디어를 하나 던져보겠습니다. 우리가 구하고자 하는 $a^b$를 전개하면, $a$를 $b$ 번 곱해 $(a*a*...*a)$를 계산해야 했습니다. 여기서 어떤 상수 $b$가 2의 거듭제곱인 $2^k$($k$는 상수)라고 가정합시다. 그럼 $a^b$를 다시 표현하면 $a^{2^k}$가 되므로, $(a*a*...*a)$가 아니라 $((a^2)^2)^2...)^2$로 표현이 가능합니다.
가정에서 $b=2^k$ 로 두었는데, 사실 우리는 모든 10진법의 수를 2진법으로 표현할 수 있습니다. 예를 들어 $13 = 1101_2$입니다. 이 13이 지수로 올라간다면, 2진법으로 표현했을 때 해당 자리수가 0인지 1인지에 따라 제곱 및 곱셈 여부를 결정하면 될 것같습니다. 아래 코드를 확인해봅시다.

    exp (a, b, N) {
    	// assume b >= 0
    	x = a, t = 1;
    	while (b > 0) {
    		if (b odd)
    			t = [t * x mod N], b = b-1;
    		x = [x^2 mod N], b = b/2;
    	}
    	return t;
    }

위 코드의 프로세스는 아래와 같습니다

1. $b$를 이진수로 변환한다.
2. $b$의 값에 따라 multiply를 진행한다.
   2-1. $b$의 현재 자리수가 홀수(1)이라면, multiply를 진행한다. $t = [t * x \;mod\; N]$
   2-2. $b$의 현재 자리수가 짝수(0)이라면, if 문을 벗어난다. (multiply 진행 x)
3. 공통적으로 square 연산을 진행한다. $x = [x^2 \;mod \;N]$

$a^{13}$으로 예를 들어보겠습니다. (이해를 위해 모듈러 연산은 진행하지 않았습니다.)

위 과정에서 정확하게 리턴값 t가 $a^{13}$이 나오는 것을 알 수 있습니다. 13은 총 이진수로 나타내면 총 네 자리수로, 이는 $log(13)$ 정도의 과정을 거치게 됩니다. 따라서 시간복잡도는 $O(log(b) * n^2)$ 로, 이전보다 효율적으로 제곱연산을 수행할 수 있습니다.

2-1 Number Theory Two

1. Groups

이번 강의에서는 group(군)의 개념을 도입해서 대수학의 정수론을 조금 더 살펴보겠습니다. 다양한 group 중 abelian group(아벨군)에 대해서 정의해보겠습니다.

$G$ : Abelian group $\;\;\;\;\circ$ : 이항 연산

• $e \circ g = g$ (for $g \in G)$ 를 만족하는 항등원(identity) $e \in G$ 가 존재한다.
  • 항등원 : 0 또는 1로 표현 가능
• 모든 $g\;(g \in G)$는 $h \circ g = e$를 만족하는 역원(inverse) $h \in G$ 를 가지고 있다.
  • 역원 : $-g$ 또는 $g^{-1}$로 표현 가능
• 결합법칙(Associativity): 모든 $f, g, h \in G$ 에 대하여 $f \circ (g \circ h) = (f \circ g) \circ h$
• 교환법칙(Commutativity): 모든 $g, h \in G$ 에 대하여 $g \circ h = h \circ g$
  $\; \\$
• order : 유한군(finite group) $G$의 원소의 개수 (집합의 크기)
• Group exponentiation : $m \cdot a\;$ or $\;a^m$ ($a \in G$)

위에서 말하는 이항연산은 두 개의 항이 필요한 연산을 말합니다. 가령, +, -, ×, ÷와 같은 사칙연산을 사용하기 위해서는 $a+b$ 이렇게 a와 b 두 개의 항이 필요하므로 이항연산입니다.
이항 연산에 대해 이해했으니 group(군)에 대해 더 자세하게 살펴봅시다. Group(군)이 되기 위해서는 몇 가지 조건을 만족해야 합니다. 먼저 결합법칙과 교환법칙이 성립해야 합니다. 그리고 이항 연산에 대하여 닫혀있어야 합니다. 닫혀있다는 것은 group에 속한 임의의 원소 두 개를 뽑아 연산한 결과가 다시 그 group 안에 있음을 말합니다. 가령, 자연수 집합은 덧셈에 대하여 닫혀있다고 말할 수 있습니다.
세 번째 조건은 각 원소의 항등원과 역원이 군에 포함되어야 한다는 것입니다. 임의의 원소 $g$에 대하여 $e$와 연산한 결과가 자기 자신($g$)라면 $e$는 $g$의 항등원(identity) 입니다. 역원(inverse)은 연산 결과가 항등원이 나오게 만드는 수를 말합니다.

2. Computations in groups

1-1 강의에서는 모듈러(modular) 연산을 위주로 한 효율성에 대해 살펴보았습니다. 모듈러 연산은 어떤 수를 축소하여 표현할 수 있으므로, group을 잘만 만든다면 모듈러 연산을 통해 위 조건을 모두 만족하는 Abelian group(아벨군)을 만들 수 있을겁니다. 암호학에선 group 연산에서도 그 효율성을 동일하게 가져간다고 가정합니다. 앞서 exponentiation을 square & multiply algorithm으로 효율적으로 계산한 것과 같이, group 내에서의 지수 연산을 포함한 원소들의 연산은 다항 시간 내에 효율적인 수행이 가능합니다. 그럼 group 내 연산에 대해 정의해봅시다.

| Example (Addition)

$Z_N = \{0, ..., N-1\}$ 에서 addition(덧셈)을 아래와 같이 정의합니다.

Addition

• Identity(항등원) = 0
• Inverse(역원) of a = [-a mod N]
• Associativity(결합법칙), commutativity(교환법칙) 성립
• order(집합의 크기) = N
• $m \cdot a = a + ... + a\,\bmod\,N$ can be computed efficiently

간단하게 숫자를 대입해 보겠습니다. $N=5$일 때, $Z_5 = \{0, 1, 2, 3, 4\}$입니다.
위 식에서 0과는 어떤 수를 더하든 자기 자신이 나옵니다. 따라서 위 집합에서 항등원은 0입니다. 덧셈에서의 역원은 덧셈 연산을 하여 항등원, 즉 0이 되는 수를 말합니다. 예를 들어, $1 + e = 0$ 을 성립시키는 $e$는 $-1$이므로, $[-1\; mod\; 5]= 4$입니다. 위와 같이 계산했을때, $m \cdot a$ 또한 다항 시간 내에 효율적으로 계산이 가능합니다.

| Example? - Multiplication

그렇다면 multiplication(곱셈) 에 대한 모듈러 연산은 어떨까요? 위와 동일한 그룹 $Z_N = \{0, ..., N-1\}$에서는 multiplication(곱셈)에 대하여 정의되지 않습니다. Group이 되기 위한 조건에는 역원이 존재해야 하는데, 곱셈에 대해서는 0의 역원이 존재하지 않기 때문입니다. 0을 그룹에서 제외하더라도 문제는 해결되지 않습니다. 예를 들어, $N=4$일 때, $Z'_4 = \{1, 2, 3\}$이라고 한다면 이때는 2에 대한 $mod \; 4$에서의 역원이 존재하지 않습니다.

| Modular Inverses

곱셈을 정의하는 방법이 없는 것은 아닙니다. 곱셈 연산에 대해 정의하기 위해 새로운 그룹을 정의할텐데, 정의하기에 앞서 필요한 modular inverse에 대해 정의를 해보겠습니다.

• 만약 $b\cdot b^{-1} = 1 \; mod \; N$을 만족하는 $b^{-1}$가 존재한다면,
  $b$는 invertible modulo N (모듈러 역원) 이고,
  역원은 group 내에 유일하다.
• "division by $b$" = "multiplication by $b^{-1}$"

만약 $b$ 의 inverse(역원) $b^{-1}$ 이 있다고 가정할 때, $modulo \;N$ 연산에서 “$b$ 로 나눈다”는 표현을 “$b^{-1}$ 을 곱한다”고 표현합니다. 여기서 말하는 invertable은 역원이 존재한다는 것을 뜻합니다. 이 invertable은 아래와 같이 표현이 가능합니다.

$Theorem : b \; is \; invertible \; modulo \; N \Leftrightarrow iff \; gcd(b, N) = 1$

$b$가 $Z_N$에서 역원을 가진다면, $b$와 $N$의 gcd(최대공약수)가 1이라는 의미입니다. 이를 다르게 말하면 $b$와 $N$이 서로소 관계라는 것과 같습니다. 이는 매우 중요한 필요충분조건입니다.
이를 조금 더 응용해 봅시다. 만약 $N$이 소수 $p$ 라면, $N$에 대해 모든 원소와의 gcd(최대공약수)가 1이므로, $Z_p = \{1, 2, 3, ..., p-1\}$의 그룹 내 모든 원소는 역원을 갖는다고 볼 수 있습니다.
$N = pq$ ($p, \;q$는 서로 다른 두 소수)라면, $p$와 $q$의 배수가 아니라면 모두 $N$과의 최대공약수가 1이므로 역원을 갖습니다.

| We get a group ! $Z^*_N$

앞선 정의에 따라 곱셈 연산에 대하여 새로운 group $Z^*_N$를 정의합시다. $Z^*_N$는 multiplication(곱셈) 연산에서 역원이 존재하는 [1, N-1] 내의 원소들의 집합 $Z^*_N = \{1, ..., N-1\}$와 같이 정의합니다.

Multiplication

• Identity(항등원) = 1
• Inverse(역원) of a = [$a^{-1}$ mod N]
• Associativity(결합법칙), commutativity(교환법칙) 성립
• order(집합의 크기) = $\Phi(N)$
• $a^m = a \cdot ... \cdot a\,\bmod\,N$ can be computed efficiently

| $\Phi(N)$

위 곱셈에 대한 그룹 연산에서 group(집합)의 크기를 $\Phi(N)$이라고 정의했습니다. 이는 오일러의 피함수라고 하는데요, $\Phi(N)$ 은 modulo N에서 invertible한 원소들의 개수를 말합니다. 다시 말하면,

앞선 modular inverse의 성질에 의해, $N$이 소수라면 $\Phi(N)$ = N - 1입니다. 그렇다면 $N$이 두 소수 $p$와 $q$의 곱일 땐 어떨까요? $\Phi(N)$ = $(p - 1)(q - 1)$입니다. 위 식을 전개하면 $N - p - q + 1$가 되는데, 이는 $N$에서 $p$의 배수와 $q$의 배수를 각각 뺀 뒤, 두 번 뺀 $pq=N$을 다시 더한 결과값입니다.

3. Fermat's little Theorem

Group theory에서 매우 중요하게 다루는 정리 중 하나가 Fermat's little Theorem(페르마의 소정리) 입니다. Fermat's little Theorem(페르마의 소정리)는 Euler Theorem(오일러의 정리)와 밀접한 관련이 있습니다.

| Fermat's little Theorem

Fermat's little Theorem
finate group $G$에서 $N$이 소수 $p$일 때, $g \in G$에 대하여 $g^{p-1} \equiv 1\,(\bmod\,N \; )$ 을 만족한다.

| Euler Theorem

페르마 소정리를 일반화하여, 모듈러 $N$이 소수일 필요가 없는 경우를 정의한 것이 Euler Theorem(오일러의 정리)입니다.

Euler Theorem (오일러의 정리)
finate group $G$에서 order가 $m$일 때, $g \in G$에 대하여 $N$과 $g$가 $gcd(N,g)=1$을 만족한다면
$g^m \equiv 1 \;(\;\bmod \; N\;)$을 만족한다.

| Example

위 Euler Theorem(오일러의 정리)에서 정의한 그룹은 $Z^*_N$이므로, $m$은 오일러 피함수 $\Phi(N)$으로 표현 가능합니다. 이때 $N=pq$ ($p$와 $q$는 서로 다른 두 소수)라고 하면, 아래와 같이 응용할 수 있습니다.

• In $\;Z_N\;$
  모든 $a \in Z_N$에 대하여, $N \cdot a = 0 \bmod N$
  $\Rightarrow$ 어떤 수와 $N$을 곱한 수를 $N$으로 나눈 나머지는 0입니다.

• In $\;Z^*_N\;$
  모든 $a \in Z^*_N$에 대하여, $a^{\Phi(N)}=1 \bmod N$ ($\Leftarrow$ 오일러의 정리)
  $N$ prime : 모든 $a \in Z^*_N$에 대하여, $a^{N-1}=1 \bmod N$ ($\Leftarrow$ 페르마의 소정리)

4. Corollary (따름정리)

위에서 페르마의 소정리와 오일러의 정리를 살펴보았습니다. 두 이론에서 파생된 그룹에 대한 따름 정리들을 살펴봅시다.

| Theorem 1

Order가 $m$인 finate group $G$일 때, $g \in G$와 상수 $x$에 대하여
$g^x = g^{[x\,\bmod\,m]}$ 를 만족한다.

| Proof 1

위에서 정의한 상수 $x$에 대하여 $m$에 대한 몫과 나머지를 $x = q*m + r$로 정의해 봅시다.

위 식에서 우항은 modular $m$에 의해 $g^{mq}$ 는 자연스럽게 사라지고 $g^r$ 만 남습니다.

여기서 $r$은 나머지로, $[x \bmod m]$ 이므로 위 식이 성립합니다.

| Theorem 2

Order가 $m$인 finate group $G$에 대하여, 함수 $f_e(g) = g^e$라고 하자.
만약 $gcd(e,m) = 1$ 이라면, $f_e$는 permutation이다.
그리고 만약 $d = e^{-1} \bmod m$이라면, $f_d$는 $f_e$의 inverse(역함수)이다.

| Proof 2

위 정리는 두 함수 $f_d$와 $f_e$에 대하여 $gcd(e,m) = 1$이므로 $1=[ed \bmod m]$라는 성질에 의해 증명할 수 있습니다.

3-1 Number Theory Three

지금까지 다항시간 내에 효율적으로 풀 수 있는 계산에 대해 논의해왔습니다. 이런 문제들을 easy problem이라고 부릅니다. 한편, 암호 알고리즘을 만들 때에는 암호화를 하기는 쉽지만, 복호화를 하기에는 어려워야 합니다. 누군가가 쉽게 풀 수 없게끔 만들어야 하여, 다항 시간 내에 풀 수 없는 문제를 hard problem이라고 부릅니다. 이번 강의에서는 암호 알고리즘을 만들기 적합한 hard problem 에 대해 다뤄보겠습니다.

1. Factoring

가장 대표적인 hard problem은 factoring입니다. Factoring은 쉽게 말해 인수분해입니다. 앞서, 우리는 주어진 두 수 $x, y$를 곱해서 $x \cdot y$를 구하는 일은 쉬운 문제라고 배웠습니다. 하지만 반대로 $x \cdot y$이 주어졌을 때 어떤 두 수 $x$와 $y$를 곱하여 생긴 것인지 도출하는 것은 어려운 문제입니다. 예를 들어, 매우 큰 두 정수를 곱해보겠습니다.

$10101023 \\ 29100257 \\ 293942365262911$

매우 큰 세 수가 있습니다. 10101023과 29100257를 곱하는 일은 적어도 다항 시간 내에서는 충분히 가능해 보입니다. 계산기로 쉽게 계산하면, 293942365262911가 나옵니다. 하지만 반대로, 293942365262911가 주어졌을 때 이를 인수분해하여 두 정수를 찾기란 매우 어려워 보입니다.

여기서 주의할 점이 있습니다. 위 예시에서는 분명 factoring이 어려웠지만, 모든 수에 대해서 어려운 문제인 것은 아닙니다. 사실 중학교 때 인수분해를 배우며, 처음에는 어려울 수 있어도 원리를 알면 곧장 쉽게 답을 도출할 수 있었죠. 확률적으로 봐도 그렇습니다. 예를 들어 어떤 수의 집합에서 절반은 짝수고 나머지는 홀수일텐데, 이 경우 $1/2$의 확률로 짝수가 나온다면 2로 나눠보며 비교적 쉽게 인수분해 접근이 가능할 것입니다.

그럼 어떤 수를 사용하면 factoring을 어렵게 만들 수 있을까요? 바로 길이가 같은 두 소수의 곱입니다. 이를 활용한 암호 알고리즘인 RSA 알고리즘에 대해 살펴보겠습니다. (RSA 알고리즘이 완전히 factoring과 동일하게 짜여진 것은 아닙니다.)

2. The RSA problem

RSA 알고리즘은 공개키 암호화 알고리즘입니다. 여담으로 얘기하자면, Ron Rivest, Adi Shamir, Leonard Adleman 세 사람이 함께 이 알고리즘을 만들어서, 이들의 이름을 따 RSA라고 합니다. 원래는 알파벳 순서대로 ARS로 하려고 했답니다. 보통 혁신적인 알고리즘을 만들면 너도나도 본인의 이름이 가장 앞에 오길 선호할텐데, RSA의 경우는 반대였다고 합니다. A에 해당되시는 Leonard Adleman께선 본인의 기여도가 적다하시며 이름을 가장 뒤에 붙여달라고 하셔서 지금의 RSA라는 이름으로 널리 알려지게 되었습니다. 암튼 저희 교수님께서 말씀해주신 여담이었습니다. ^_^

| Setting

RSA 알고리즘에서 암호화 복호화가 진행되기 앞서 key를 생성하는 과정입니다.

Setting for RSA
1. 홀수인 두 소수 $p$와 $q$ ($p \neq q$)를 뽑아 $N = p*q$를 설정한다.
2. $N$에 대한 multiplication modulo 연산 그룹 $Z_N^*$ 을 정의한다.
$\;\;\;$ $Z_N^*$ 의 order $\; \Phi(N)=(p-1)(q-1)$
3. gcd(e, $\Phi(N)$) = 1을 만족하는 $e$를 뽑는다.
$\;\;\;$이때 $\Phi(N)$ 와 $e$가 서로소이므로, $e$는 modulo $\Phi(N)$ 에 대하여 역원 $d$를 갖는다.
4. public key = $(N, e)$, secret key = $(N, d)$ 로 각각 설정한다.

| Encryption & Decryption

RSA 알고리즘에서의 $Enc\; \& \;Dec$ 알고리즘은 아래와 같습니다.

Encryption and Decryption for RSA
For message : $x$ $\;\;\;$ ciphertext : $c$
$Enc:$ $c \Leftarrow x^e\,\bmod\,N$
$Dec :$ $x \Leftarrow c^d = (x^e)^d = x^{ed} = x\,\bmod\,N$

| Proof & more informations

위 RSA 알고리즘의 Setting과 encryption, decryption 알고리즘에서 핵심이 되는 이론은 앞서 Fermat's little Theorem(페르마의 소정리)에서 공부한 따름정리 두 번째입니다. 이를 다시 상기해봅시다.

Order가 $m$인 finate group $G$에 대하여, 함수 $f_e(g) = g^e$라고 하자.
만약 $gcd(e,m) = 1$ 이라면, $f_e$는 permutation이다.
그리고 만약 $d = e^{-1} \bmod m$이라면, $f_d$는 $f_e$의 inverse(역함수)이다.

• setting
  위 정리의 핵심은 $gcd(e,m) = 1$ 라는 조건이었습니다. $gcd(e,m) = 1$인 것은 $e$와 $m$이 서로 역원을 가진다는 것과 필요충분조건이고, Setting의 3번 에서는 이를 활용하여 공개키와 비밀키를 뽑습니다.

• enc & dec
  $d = e^{-1} \bmod m$이라면, $f_d$는 $f_e$의 inverse(역함수) $d$의 역원이 $e$라면 $ed \; = \; 1\,\bmod\,\Phi(N)$을 만족할 것입니다. 더불어 오일러의 정리에 의해 $(x^{\Phi(N)})^q\,\bmod\,N = 1$이므로, 서로 역원 관계인 두 수에 대하여 제곱을 올렸을 때 아래 식이 성립합니다.

  $x^{ed} = x^{[ed \; = \; 1\,\bmod\,\Phi(N)]} = x^{q*\Phi(N) + 1} = (x^{\Phi(N)})^q \cdot x^1 = x\,\bmod\,N$

위 과정에서, 만약 $\Phi(N)$이 잘 알려진 두 소수의 곱이라면 $N$을 찾기 쉽기 때문에 이로 파생되는 $\Phi(N)$과 $d$, 그리고 message $x$가 될 제곱근까지 모두 쉽게 구할 수 있을 것입니다. 반대로 잘 알려지지 않은 두 소수를 사용했다면 $\Phi(N)$을 구하기 매우 어려울 것입니다. 실제로 RSA 알고리즘은 이를 위해 두 소수 $p$와 $q$를 1024 비트 이상의 매우 큰 수로 사용합니다.

3. The RSA assumption

$N$과 $e$를 주어졌을 때, $d$를 구하는 것은 매우 어렵습니다. 그 이유를 RSA에 대하여 factoring = hard problem이라고 가정한 바를 바탕으로 설명하겠습니다. 만약 $\Phi(N)$ 을 구할 수 있다면, 확장된 유클리드 알고리즘에 의해 d(secret key)를 알아내는 것은 쉽습니다. 하지만 $\Phi(N)$ 을 구하기 위해선 $N$을 이루는 두 소수 $p$와 $q$를 알아야 하는데, 이 두 소수를 알아내는 방법은 앞서 말한 우리가 hard problem이라고 가정한 factoring 문제입니다. Factoring을 hard problem이라고 가정했기 때문에, $N$과 $e$만을 가지고 $d$를 알아내는 것은 어렵습니다.

이에 대한 공격 모델은 formal하게 정의하면 아래와 같습니다.

• $GenRSA(1^n) = (N, e, d)$
• Experiment $RSA-inv_{A, GenRSA}(n)$ :
  ① Compute $(N, e, d)$ ← $GenRSA(1^n)$
  ② Choose uniform $y \in Z^*_N$
  ③ Run $A(N, e, y)$ to get $x$
  ④ Experiment evaluates to 1 if $x^e=y \bmod N$

위 알고리즘은 공격자가 uniform하게 뽑은 $y$에 대하여, (N, e, y)를 통해 $x^e = y\,\bmod\,N$을 만족하는 x를 얻어낸다면 1을 반환하는 알고리즘입니다. 확률 상, 각 key의 길이가 1024 bit라고 할 때, 공격자가 적절한 $y$를 뽑을 확률은 $1/2^{1024}$이므로 무시할만한 확률입니다. 위 공격 모델에서의 확률은 아래와 같습니다.

4. Implementing GenRSA

이제 RSA를 현실에서 만드는 방법을 살펴봅시다. 알고리즘은 앞서 설명한 것과 유사하지만, 다시 한 번 정의하겠습니다.

impliment GenRSA
1. Generate uniform n-bit primes $p$, $q$
2. Set $N:=pq$
3. Choose arbitrary $e$ with $gcd(e, \Phi(N))=1$
4. Compute $d:=[e^{-1} \; \bmod \;\Phi(N)]$
5. Output $(N, e, d)$

위 과정 3번에서 임의의 $e$는 공개키로, 이미 모두에게 알려진 수입니다. 따라서 RSA 알고리즘의 hard 정도에 큰 영향을 미치지 않는다고 합니다. 두 키 $e$와 $d$는 지수승으로 올라가기 때문에, 지수승에 적합한 수로 선정하는 것이 암호를 만든는 사람 입장에서는 좋습니다. 제곱에 대한 계산은 앞서 Square & multiply 알고리즘을 사용했습니다. Multiply를 조금만 하도록 연산을 줄이기 위해, 주로 $e$를 $3(11_2)$ 혹은 $2^{16}+1(100...001_2)$로 설정하는 것이 일반적입니다.

4-1 Number Theory Four

1. Cyclic groups

2-1에서는 오일러의 정리와 페르마의 소정리를 정의하기 위한 abelian group에 대해 살펴봤다면, 이번에는 새로운 정리를 위해 cyclic groups(순환군) 에 대해 공부하겠습니다. Cyclic groups(순환군)은 아래와 같이 정의합니다.

Cyclic groups (순환군)
finit group $G$에 대하여 $G$의 원소를 $g$라고 하자.
집합 {$g^0, g^1, ...$}에서 order $\leq m$에 대하여 $g^m = 1 = g^0$이라면,
$G$는 cyclic group, $\;g$는 $G$의 generator

| Example

$Z_N=\{0,1,2,...,N-1\}$ 입니다. Addition(덧셈)에 대한 Abelian group(아벨군) $Z_N$은 모든 $N$에 대하여 cyclic하다는 성질을 가집니다. 왜냐하면 원소 1은 어떤 경우에도 generator이기 때문입니다.
숫자로 예시를 들겠습니다. $Z_8$ 에서 3이 생성하는 그룹은 $\{0, 3, 6, 1, 4, 7, 2, 5\}$ 로, 결국 해당 집합 내에 있는 원소값으로 형성됩니다. 이 그룹은 cyclic group이고, 이때 3은 generator인 것이죠. 한편, 2는 {0, 2, 4, 6}만 값으로 나오므로 generator가 될 수 없습니다. 여기서 중요한 이론 두 가지를 확인할 수 있습니다.

• Theorem 1 : Group의 order(그룹의 크기)가 소수인 그룹이 cyclic하다면, 항등원을 제외한 모든 원소에 대하여 generator이다.
• Theorem 2 : $p$가 prime이면, $Z_p^*$ 는 cyclic group 이다. (order = $p-1$)

위 두 이론이 중요한 이유는 generator를 uniform한 확률로 쉽게 뽑고 싶기 입니다. 어떤 cyclic group 내에서 모든 원소가 generator라면, 그 그룹의 order 만큼의 경우의 수가 있을 겁니다. 따라서 위 두 이론 중 하나에 만족하는 cyclic group인 경우, 다른 조건을 거치지 않고 해당 그룹 내 원소 중 아무거나 뽑더라도 generator를 뽑을 수 있으므로 이점을 지닙니다.

2. Discrete-logarithm problem

지금까지 cyclic group과 generator를 뽑은 이유를 설명드리겠습니다. 우리는 이전 강의에서 hard problem 중 하나인 factoring에 대해 살펴봤고, 이를 응용한 RSA 암호화 알고리즘을 알아보기 위해 group에 대해 정의하고 살펴봤습니다. cyclic group 또한 지금 소개할 hard problem과 관련된 개념입니다. 바로 discrete-logarithm problem입니다.
Order가 $m$인 cyclic group G의 어떤 generator $g$에 대하여, $\{g^0, g^1,...,g^{m-1}\}=G$입니다. 이때 $h\in G$는 $g^x=h$ $(x\in Z_m)$으로 표현 가능합니다. 여기서 $log_gh=x$를 구하는 문제를 Dlog(discrete logarithm) problem이라고 합니다.

Dlog problem in $G$ : g와 h를 주어졌을 때, $log_gh$를 구하는 것
Dlog assumption in $G$ : $G$ 내에서 discrete log problem 계산하기는 어려움

일반적인 log 연산은 그리 어렵지 않을 수 있습니다. 하지만 우리는 modular 그룹 내에서 연산을 진행하기 때문에, 0 부터 m-1 사이의 값을 가지는 x를 찾기는 시간이 매우 오래 걸릴 수밖에 없을 것입니다.

이 문제에 대한 공격 모델을 정의하면 아래와 같습니다.

• $\mathcal{G}$ : group-generation algorithm
  $G$ : cyclic group $\;\;$ $q$ : order $\;\;$ $g$ : generator
• For algorithm $A$, $Dlog_{A,\mathcal{G}}(n)$ :
  ① compute $(G, q, g)$ ← $\mathcal{G}(1^n)$
  ② Choose uniform $h \in G$
  ③ Run $A(G, q, g, h)$ to get $x$
  ④ Experiment evaluates to 1 if $g^x=h$

위 알고리즘 $Dlog_{A, \mathcal{G}}(n)$ 은 공격자가 그룹 $G$에서 uniform 하게 원소 $h$를 뽑고, 주어진 $(G, q, g, h)$ 만으로 $g^x = h$ 를 만족하는 $x$를 얻으면 1을 반환하는 알고리즘입니다. 위 공격 모델에서의 확률은 아래와 같습니다.

3. Diffie-Hellman problems

Dlog 문제를 착안하여 만들어진 key 교환 알고리즘입니다. Diffie-Hellman problems를 살펴봅시다. 그룹 $G$와 generator $g$에 대하여 함수 $DH_g(h_1,h_2) = DH(g^x,g^y) = g^{xy}$와 같이 정의합니다. 이때 Diffie-Hellman problems는 두 가지 종류가 있습니다.

| Computational Diffie-Hellman (CDH)

Cyclic group $G$에 대하여 $g$와 $h_1$, $h_2$가 주어졌을 때, $DH_g(h_1,h_2) = g^{xy}$ 를 계산하는 것은 어렵다.

• $g^x \cdot g^y = g^{x+y} \ne g^{xy}$

CDH는 $DH_g(h_1,h_2)$ 계산 자체가 어려움을 말합니다. 두 수를 곱한다고 할지라도 $g^xy$와 $g^{x+y}$는 다르기 때문에 주어진 조건만을 가지고 문제를 풀기는 어렵습니다.

| Decisional Diffie-Hellman (DDH)

Cyclic group $G$에 대하여 $g$와 $h_1$, $h_2$가 주어졌을 때, $DH_g(h_1,h_2) = g^{xy}$ 값을 그룹 $G$ 내의 uniform element $g^z$ 와 구별하는 것은 어럽다.

DDH는 $g^{xy}$와 그렇지 않은 두 수를 구분(결정)하는 문제입니다. 만약 $h_1$과 $h_2$가 매우 큰 두 수라면, 그 결과값은 더욱 큰 수가 될 것입니다.

DDH에 대한 공격 모델에 대해 정의하면 다음과 같습니다.

| Relating the Diffie-Hellman problems

각 문제들의 상관관계에 대해 살펴봅시다. DDH는 CDH보다 강한 assumption을 지니고 있습니다. 한편 CDH는 Dlog보다 강한 assumption으로, 난이도에 순서는 DLog > CDH > DDH 입니다.
다른 말로 표현하면, DLog 문제를 풀 수 있다면 CDH와 DDH를 풀 수 있습니다. 한편 CDH를 풀 수 있다면 DDH를 풀 수 있습니다.

4. Group selection

암호학에 적용할 때 prime-order group을 가장 많이 사용합니다. 앞서 말한 것처럼, generator를 고르기 위해서는 모든 원소가 generator인 경우가 가장 좋은데, 이 경우는 order가 prime인 group이 해당하기 때문입니다. Prime-order group의 subgroup으로 다음과 같은 두 그룹이 존재합니다.

1. Prime-order subgroup of $Z_p^*$ ($p$는 소수)

• E.g., $p=tq+1$ ($q$는 소수)
• Take the subgroup $t^{th}$ powers,
  $G = \{[x^t \; \bmod \;p] \; | \; x \in Z^*_p\}$
  order : $(p-1)/t = q$
  $q$가 소수이므로, 이 그룹은 cyclic

오일러 법칙에 따르면, $x^{p-1} = 1 \; \bmod \; p$ 입니다. 이때 $t$ 만큼의 거듭제곱 $x^t$에 대하여, $(x^t)^k = 1 \; \bmod \; p$인 $k$를 구하면 되는데, 위 식을 가장 잘 만족시키는 $k$는 $t*k = order$이 되게 하는 수입니다. 따라서 order = $(p-1)/t$가 됩니다.

2. Elliptic curve group
   Elliptic curve group에 대한 자세한 설명은 생략하겠습니다.
   
   

5-1 Number Theory Five

앞서, hard problem에 대해 살펴봤습니다. 첫 번째로 본 hard problem은 factoring에 대한 문제로, RSA algorithm은 이를 응용하여 만든 공개키 암호화입니다. 두 번째로 본 hard problem은 DLog에 대한 문제로, 이에 착안한 Diffie-Hellman problems을 살펴봤습니다. 하지만 hard problem이라는 이유로 모두 암호화에 바로 사용할 수 있는 것은 아닙니다. 암호화에 필요한 key size 등 적절한 파라메터 값이 들어가고, 이에 대한 안전성이 확보되어야만 합니다. 이번 강의에서는 지금까지 대칭키 암호화에서 본 내용을 바탕으로 hard problem을 암호화에 적용하기 위한 방안을 검토해보겠습니다.

1. Security

앞서 block cipher를 살펴봤습니다. Block cipher는 입출력, 그리고 key의 길이가 고정된 암호 알고리즘입니다. Block cipher의 key size를 n-bit 로 설정하면 $2^n$ 정도의 시간이 걸립니다. 한편, hash function은 n-bit output으로 설정하면 birthday attack에 의해 $2^{n/2}$ 정도의 시간으로 공격이 가능합니다. Block cipher보다 더 공격 노출 확률이 높은 것이죠.

그렇다면 적어도 우리가 정의한 hard problem인 factoring과 DLog에 대하여 살펴봅시다. Factoring은 modular 계산을 해야하는데, 이때 modulus가 n-bit라면 $2^n$ 정도의 시간이 걸리는지 확인해야 합니다. Dlog는 group 내에서 generator를 하나씩 검토해야 할텐데, 해당 그룹 안에 $2^n$ 만큼의 원소가 있다면 실제 이에 대한 탐색 시간도 $2^n$이 소요되는지 확인해봅시다.

2. Algorithms for factoring

인수분해(factoring)의 경우, 우리가 이야기 한 $2^n$ 시간 보다 더 적게 걸리는 알고리즘이 존재합니다. $2^{O(log(N))}$ 정도의 시간이 걸리며, 베스트 알고리즘 (asymptotically) 또한 $2^{O(||N||^{1/3}log||N||^{2/3)}}$ 정도의 시간이 걸립니다.

3. Algorithms for Dlog

Dlog의 경우 가장 자주 쓰이는 두 가지 알고리즘 클래스가 있습니다. 하나는 임의의 generic 그룹에 대해 확인하는 알고리즘이고, 다른 하나는 특정 그룹에 대해 원소를 확인하는 알고리즘입니다. 보통 $2^{n/2} \approx 2^n$ 정도의 시간이 걸리며, 베스트 알고리즘 (asymptotically) 또한 $2^n$개의 원소에 대하여 $2^{O(||N||^{1/3}log||N||^{2/3)}}$ 정도의 시간이 걸린다고 합니다.

심지어 타원곡선 그룹에서는 현재 generic 알고리즘보다 더 좋은 알고리즘은 없다고 합니다. 이처럼 아직까지 어려운 문제로 평가되는 문제를 이용해 암호 알고리즘으로 응용할 수 있습니다 이들을 security 알고리즘에 사용하기 위해선 적절한 파라미터를 선정하여 넣을 필요가 있습니다.