Euclidean algorithm, RSA

1. Euclidean Algorithm (유클리드 알고리즘)

목표: 주어지는 두 수 $I_0$과 $I_1$의 최대공약수(GCD)를 빠르고 효율적으로 찾기 위함입니다.

핵심 아이디어: "큰 수를 작은 수로 나눈 나머지를 구하는 과정을, 나머지가 0이 될 때까지 반복한다."수학적으로 표현하면 $gcd(I_0, I_1) = gcd(I_0 \bmod I_1, I_1)$이 성립한다는 원리를 이용합니다.

$gcd(973, 301)$ 구하기
나머지를 $I_2, I_3 \dots$ 순으로 정의하며 나눗셈을 반복합니다.

• $973 = 3 \cdot 301 + 70$ (여기서 나머지 $I_2 = 70$)
• $301 = 4 \cdot 70 + 21$ (여기서 나머지 $I_3 = 21$)
• $70 = 3 \cdot 21 + 7$ (여기서 나머지 $I_4 = 7$)
• $21 = 3 \cdot 7 + 0$ (나머지가 0이 됨)

결론: 나머지가 0이 되기 직전의 나머지인 $7$이 두 수의 최대공약수가 됩니다.

2. 확장 유클리드 알고리즘 (Extended Euclidean Algorithm)

목표: 방금 구한 최대공약수($7$)를, 처음 시작했던 두 수($973$과 $301$)의 선형 결합(곱셈과 덧셈) 형태로 표현하는 것입니다.우리가 최종적으로 도달해야 하는 수식의 형태는 다음과 같습니다.

$gcd(I_0, I_1) = s \cdot I_0 + t \cdot I_1$

여기서 우리가 찾아내야 하는 핵심 파라미터가 바로 계수 $s$와 $t$입니다. 앞서 계산한 나눗셈 식들을 나머지 기준으로 다시 정리한 뒤, 밑에서부터 위로 역추적(Backward Substitution)하며 대입해 올라갑니다.

[역추적 상세 단계]

Step 1: $I_2$ 식 정리
$70 = 1 \cdot 973 - 3 \cdot 301$

Step 2: $I_3$ 식 정리 및 대입
$21 = 301 - 4 \cdot 70$

이 식의 $70$ 자리에 Step 1의 결과를 통째로 대입합니다.
$21 = 301 - 4 \cdot (1 \cdot 973 - 3 \cdot 301)$
$21 = -4 \cdot 973 + 13 \cdot 301$

Step 3: $I_4$ 식 정리 및 대입
$7 = 70 - 3 \cdot 21$

이 식에 앞서 구한 $70$과 $21$의 식을 모두 대입합니다.
$7 = (1 \cdot 973 - 3 \cdot 301) - 3 \cdot (-4 \cdot 973 + 13 \cdot 301)$

괄호를 풀고 $973$과 $301$로 각각 묶어서 정리합니다.
$7 = 13 \cdot 973 + (-42) \cdot 301$
결론: 최종 형태를 맞추었으므로, 우리가 찾던 계수는 $s = 13$, $t = -42$가 됩니다.

3. 알고리즘 일반화 (재귀 공식 도출)

위와 같은 수작업 역추적은 컴퓨터가 수행하기엔 매우 비효율적입니다. 따라서 컴퓨터가 루프(Loop)를 돌며 쉽게 계산할 수 있도록, 이전 단계의 값들로 현재 값을 구하는 점화식(Recursive Formula)을 유도해야 합니다.

[점화식 유도 과정]1. 가정 설정: 특정 $i$ 단계 직전의 두 식을 다음과 같이 일반화할 수 있다고 가정합니다.
$I_{i-2} = s_{i-2} \cdot I_0 + t_{i-2} \cdot I_1$
$I_{i-1} = s_{i-1} \cdot I_0 + t_{i-1} \cdot I_1$

2. 나눗셈 식 정리: 일반 유클리드 알고리즘의 나눗셈 식을 나머지 $I_i$에 대해 정리합니다.
   $I_{i-2} = q_{i-1} \cdot I_{i-1} + I_i \implies I_i = I_{i-2} - q_{i-1} \cdot I_{i-1}$

3. 대입 및 계수 추출: 앞서 가정한 식들을 방금 정리한 $I_i$ 식에 대입합니다.
   $I_i = (s_{i-2} \cdot I_0 + t_{i-2} \cdot I_1) - q_{i-1} \cdot (s_{i-1} \cdot I_0 + t_{i-1} \cdot I_1)$
   이를 $I_0$과 $I_1$로 묶어냅니다.

$I_i = (s_{i-2} - q_{i-1} \cdot s_{i-1}) \cdot I_0 + (t_{i-2} - q_{i-1} \cdot t_{i-1}) \cdot I_1$

4. 최종 점화식 완성: 괄호 안의 식들이 곧 새로운 $s_i$와 $t_i$가 됩니다.
   $s_i = s_{i-2} - q_{i-1} \cdot s_{i-1}$
   $t_i = t_{i-2} - q_{i-1} \cdot t_{i-1}$

5. 초기값 (Base Cases): 이 루프를 시작하기 위한 초기 세팅입니다.
   $s_0 = 1, t_0 = 0$ (초기식 $I_0 = 1 \cdot I_0 + 0 \cdot I_1$ 을 만족하기 위해)
   $s_1 = 0, t_1 = 1$ (초기식 $I_1 = 0 \cdot I_0 + 1 \cdot I_1$ 을 만족하기 위해)

3. 오일러 파이 함수 (Euler's Phi Function, Phi(m))

• 정의: 어떤 수 M이 주어졌을 때, M보다 작으면서 M과 서로소(최대공약수가 1)인 양의 정수의 개수를 의미합니다.

• 예시 1: M = 6일 때, 6과 서로소인 수는 1과 5 두 개이므로 Phi(6) = 2 입니다.

• 예시 2 (큰 수의 계산법): RSA 암호화에 쓰이는 매우 큰 수들은 일일이 셀 수 없으므로 소인수분해 공식을 사용합니다.
  공식: M을 소인수분해한 결과가 P1^E1 P2^E2 ... 라면,
  Phi(M) = (P1^E1 - P1^(E1 - 1)) (P2^E2 - P2^(E2 - 1)) ... 와 같이 계산합니다.

• 계산 예시: M = 240
  240을 소인수분해하면 2^4 3^1 5^1 입니다.
  공식에 대입하면 (2^4 - 2^3) (3^1 - 3^0) (5^1 - 5^0) = 8 2 4 = 64가 됩니다.
  

페르마의 소정리 (Fermat's Little Theorem)

필기 상단에 적힌 이 정리는 소수(Prime Number)의 아주 특별한 성질을 보여줍니다.어떤 정수 $a$와 소수 $P$가 있을 때, 다음과 같은 공식이 항상 성립합니다.

$a^P \equiv a \pmod P$
이 공식의 양변을 $a$로 나누어 주면(단, $a$가 $P$의 배수가 아닐 때) 다음과 같이 표현할 수 있습니다.
$a^{P-1} \equiv 1 \pmod P$
여기서 이전 시간에 배웠던 오일러 파이 함수($\Phi$)를 떠올려 봅시다. 소수 $P$에 대한 파이 함수 값은 자신보다 작은 모든 수와 서로소이므로 $\Phi(P) = P - 1$이 됩니다.
이 사실을 위의 공식에 대입하면 다음과 같은 최종 형태가 도출됩니다.

$a^{\Phi(P)} \equiv 1 \pmod P$

오일러의 정리 (Euler's Theorem)

필기 중간의 오일러의 정리는 페르마의 소정리를 한 단계 더 확장한 것입니다. 페르마의 정리는 모듈러 값이 반드시 '소수($P$)'일 때만 성립했지만, 오일러는 이를 '어떤 수($m$)'에 대해서도 성립하도록 일반화했습니다.

조건은 단 하나, 밑이 되는 수 $a$와 모듈러가 되는 수 $m$이 서로소($gcd(a, m) = 1$)여야 한다는 것입니다. 이 조건만 만족하면 다음 공식이 무조건 성립합니다.

오일러의 정리 검증 예시 (Ex)
필기 하단은 이 마법 같은 오일러의 정리가 진짜로 성립하는지 구체적인 숫자를 넣어 증명해보는 과정입니다.

[가정] $a = 5$, $m = 12$ 라고 해봅시다. $5$와 $12$는 최대공약수가 $1$인 서로소이므로 오일러의 정리를 적용할 수 있습니다.

Step 1:

$\Phi(12)$ 계산하기
$12$를 소인수분해하면 $3 \cdot 4 = 3^1 \cdot 2^2$ 입니다.
파이 함수 공식에 넣으면:

$\Phi(12) = (2^2 - 2^1) \cdot (3^1 - 3^0)$
$= (4 - 2) \cdot (3 - 1) = 2 \cdot 2 = 4$

즉, $\Phi(12) = 4$ 입니다.

Step 2:

오일러 공식에 대입하기
오일러의 정리에 따르면 $5^{\Phi(12)} \equiv 1 \pmod{12}$ 가 성립해야 하므로, 결국 $5^4 \pmod{12}$ 의 결과가 $1$이 나오는지 확인하면 됩니다.

Step 3:

모듈러 연산 풀이
$5^4$을 한 번에 계산하면 $625$로 너무 크니까, 필기에서는 연산을 쪼개는 팁(Equivalent Class 활용)을 썼습니다.

$5^4 \equiv 5^2 \cdot 5^2 \pmod{12}$
$5^2 = 25$
$\equiv 25 \cdot 25 \pmod{12}$

여기서 $25$를 $12$로 나누면 몫이 $2$($24$)이고 나머지가 $1$이 됩니다. 따라서 $25 \pmod{12} \equiv 1$ 로 바꿀 수 있습니다.

$\equiv 1 \cdot 1 \pmod{12}$
$\equiv 1 \pmod{12}$

결론: 수작업으로 계산해 본 결과도 정확히 $1$이 나옴으로써, 오일러의 정리($a^{\Phi(m)} \equiv 1 \pmod m$)가 완벽하게 증명되었습니다!

이 두 정리가 훗날 RSA에서 $X^{E \cdot D} \equiv X \pmod N$ (암호화했다가 복호화하면 원래 평문이 나온다)을 증명하는 데 핵심 키로 사용됩니다.

---

2. 대칭키(비밀키) 암호화 vs 공개키(비대칭키) 암호화

대칭키(Symmetric Key)의 문제점:
Alice와 Bob이 동일한 키($K$)로 암복호화를 하려면, 사전에 안전한 채널(Secure Channel)을 통해 이 키를 주고받아야 합니다(Key Distribution). 하지만 인터넷처럼 개방된 네트워크에서 안전한 채널을 구축하는 것은 현실적으로 불가능에 가깝습니다.

공개키(Asymmetric Key)의 해결책:
수신자인 Bob이 사전에 두 개의 열쇠 꾸러미(키 쌍)를 만듭니다

• 누구나 볼 수 있게 공개하는 열쇠 ($K_{pub}$): 암호화 전용
• 자기 자신만 꽁꽁 숨겨두는 열쇠 ($K_{pr}$): 복호화 전용이제 Alice는 Bob의 공개키로 데이터를 암호화($y = e_{K_{pub}}(x)$)해서 보내면 됩니다. 해커가 중간에 데이터를 가로채도, 복호화 키는 오직 Bob만 가지고 있으므로 안전하게 통신할 수 있습니다!

3. RSA Algorithm

[1단계: 키 생성 (Key Generation)] - 모듈러 Phi(n) 사용

1. 아주 큰 두 소수 $p$와 $q$를 고릅니다. (보통 $512$비트 이상의 거대한 수)
2. 두 소수를 곱해서 모듈러 $n$을 만듭니다: $n = p \cdot q$
3. 오일러 파이 함수를 이용해 $\Phi(n)$을 계산합니다: $\Phi(n) = (p-1) \cdot (q-1)$
4. 공개키 $e$를 선택합니다. (단, $e$는 $\Phi(n)$과 서로소여야 함, 즉 $gcd(e, \Phi(n)) = 1$)
5. 비밀키 $d$를 계산합니다. 앞서 배운 확장 유클리드 알고리즘(EEA)을 이용해 $e$의 모듈러 역원을 구합니다
   $d \cdot e \equiv 1 \pmod{\Phi(n)}$

결론: 이렇게 만들어진 $(e, n)$ 묶음은 공개키가 되어 널리 배포되고, $d$는 개인키가 되어 수신자만 안전하게 보관합니다.

3. RSA의 실제 연산과 계산 예제
   세 번째 장은 방금 만든 키로 어떻게 암호화/복호화를 하는지 공식과 예제를 보여줍니다.

[암호화 / 복호화 공식]

• 암호화 (Alice): 평문 $x$를 Bob의 공개키 $e$와 $n$을 이용해 암호화합니다.
  $y = x^e \bmod n$
• 복호화 (Bob): 암호문 $y$를 자신의 개인키 $d$와 $n$을 이용해 복호화합니다.
  $x = y^d \bmod n$

[손으로 풀어보는 RSA 예제]
수업 시간에 진행한 예제 수치를 그대로 따라가 보겠습니다.

• 평문 (Alice): $x = 4$
  키 생성 (Bob):

1. $p = 3, q = 11$ 선택
2. $n = 3 \cdot 11 = 33$
3. $\Phi(n) = 2 \cdot 10 = 20$
4. 공개키 $e = 3$ 선택 (임의로 작은 수 선택)
5. 개인키 $d$ 계산: $3 \cdot d \equiv 1 \pmod{20}$ 이므로, $d = 7$(공개키: $(33, 3)$ / 개인키: $7$)

암호화 (Alice):
$y = 4^3 \bmod 33$
$= 64 \bmod 33 = 31$
(Alice는 암호문 $31$을 전송합니다.)

복호화 (Bob):
$x = 31^7 \bmod 33$
이 계산을 쉽게 하기 위해 Equivalent Class를 사용합니다. $31 \equiv -2 \pmod{33}$ 이므로,
$= (-2)^7 \bmod 33$
$= -128 \bmod 33$
$-128$은 $-4 \cdot 33 + 4$ 이므로, 최종 평문은 원래 Alice가 보냈던 $4$가 튀어나옵니다!

왜 $e=3$ 같이 작은 숫자를 공개키로 쓰면 안 될까?
필기 맨 아래 빨간 글씨로 적힌 'Trudy'의 해킹 시나리오가 그 답을 줍니다.
만약 암호문 $y = x^3 \bmod 77$ 처럼, $x^3$ 값이 모듈러 $n$($77$)을 넘지 못하는 상황(예: $x=4$일 때 $4^3 = 64$)이 발생하면 모듈러 연산이 사실상 무력화됩니다. 해커(Trudy)는 그냥 암호문에 세제곱근($\sqrt[3]{64}$)을 씌워버리는 것만으로 평문($4$)을 쉽게 알아낼 수 있습니다. 따라서 실제 구현에서는 $e$ 값을 최소한 $17$이나 $65537$($2^{16} + 1$) 같은 큰 소수로 설정해야만 안전합니다.

4. RSA의 응용 및 최적화 이슈

1. RSA 알고리즘은 왜 안전할까? (보안의 핵심)

• 해커가 개인키를 알아내려면 $\Phi(n)$ 값을 반드시 계산해야 합니다.
• 하지만 $\Phi(n)$을 구하려면 거대한 수 $n$을 두 소수 $p$와 $q$로 소인수분해(Factorize)해야만 합니다.
• $n$이 $2^{800}$ 이상으로 매우 큰 수일 경우, 이를 소인수분해하는 것은 현재의 컴퓨팅 파워로는 "매우 어렵다(very difficult)" 혹은 사실상 불가능합니다. 이것이 RSA가 안전한 이유입니다.

이전 수업에서 언급했듯이 해커(Trudy)가 가로채는 정보는 공개키 $e$와 모듈러 $n$입니다. 해커가 비밀키 $d$를 구하려면 $d \cdot e \equiv 1 \pmod{\Phi(n)}$ 공식을 풀어야 하므로 $\Phi(n)$의 값을 반드시 알아야 합니다.

• $\Phi(n) = (p-1) \cdot (q-1)$ 이므로, $\Phi(n)$을 알기 위해서는 거대한 수 $n$을 소수 $p$와 $q$로 소인수분해(Factorization)해야 합니다.
• 현대 수학 및 컴퓨터 공학 관점에서 볼 때, $n$이 $1024$비트나 $2048$비트 단위의 엄청나게 큰 수일 경우 이를 소인수분해하는 것은 우주의 나이만큼이나 오랜 시간이 걸리는 'NP 난제'에 속합니다.
• 결론적으로 RSA의 안전성은 "큰 수의 소인수분해는 현실적으로 불가능에 가깝다"는 수학적 한계에 철저히 기반을 두고 있습니다.

2. RSA의 응용: 동형 암호화 (Homomorphic Encryption)

RSA는 단순히 데이터를 숨기는 것을 넘어, 암호화된 상태(Ciphertext) 그대로 유의미한 연산을 수행할 수 있는 놀라운 성질을 가지고 있습니다. 이를 동형 곱셈(Homomorphic Multiplication)이라고 부릅니다.

• 개념: 두 평문 $m_1$과 $m_2$를 각각 암호화한 상태에서 서로 곱한 결과는, 애초에 두 평문을 곱한 뒤 한 번에 암호화한 결과와 완벽하게 일치합니다.
  $E(m_1) \cdot E(m_2) = E(m_1 \cdot m_2)$

• 수학적 증명: (동일한 공개키 $e$와 $n$을 사용한다고 가정)
  $m_1^e \pmod n \cdot m_2^e \pmod n \equiv (m_1 \cdot m_2)^e \pmod n$

숫자 예제 검증: $m_1 = 4, m_2 = 3, e = 3, n = 33$ 일 때

1. 따로 암호화해서 곱하기:
   $e(m_1) = 4^3 \bmod 33 = 31$
   $e(m_2) = 3^3 \bmod 33 = 27$
   $31 \cdot 27 \bmod 33 \equiv (-2) \cdot (-6) \bmod 33 = 12 \bmod 33$

2. 곱한 뒤 암호화하기:
   $e(4 \cdot 3) = 12^3 \bmod 33$
   이것은 $(4 \cdot 3)^3 \bmod 33 = 4^3 \cdot 3^3 \bmod 33 = 31 \cdot 27 \bmod 33$ 이 되어 결국 위와 똑같이 $12 \bmod 33$ 이 나옵니다!

참고 (Homomorphic ADD): RSA는 동형 곱셈만 지원하지만, 'Paillier(파이에)' 알고리즘 같은 것을 사용하면 암호문끼리 곱했을 때 평문끼리의 '덧셈' 결과를 얻어낼 수도 있습니다.

• 활용: 이 성질을 이용하면 클라우드 서버나 데이터베이스 관리자가 사용자의 실제 데이터(평문)를 전혀 들여다보지 않고도 암호문 상태로 데이터 연산을 수행할 수 있습니다.

3. RSA 연산 최적화: 고속 거듭제곱 (Fast Exponentiation)

RSA의 암/복호화 과정에는 $x^{1024}$처럼 지수(Exponent)가 엄청나게 큰 모듈러 거듭제곱 연산이 필수적으로 수반됩니다. 이를 컴퓨터로 어떻게 효율적으로 계산할지가 핵심 문제입니다.

[비교 1] $x^4$ 계산하기

• Naive (단순 반복): $x \cdot x \cdot x \cdot x$ $\rightarrow$ 곱셈 3번 필요
• Better (제곱 활용): $x^2 \cdot x^2 = x^4$ $\rightarrow$ 곱셈 2번 필요

[비교 2] $x^8$ 계산하기

• Naive: 곱셈 7번 필요
• Better: $x^4 \cdot x^4 = x^8$ $\rightarrow$ 곱셈 3번 필요 ($x \rightarrow x^2 \rightarrow x^4 \rightarrow x^8$)

나이브 접근법 (Naive Approach):
$x^4$를 구할 때 $x \cdot x \cdot x \cdot x$처럼 하나씩 차례대로 곱하는 방식입니다.지수가 $2^{1024}$일 경우 총 $2^{1024} - 1$번이라는 천문학적인 횟수의 곱셈(선형 복잡도, $O(n)$)을 수행해야 하므로 사실상 계산이 불가능합니다.

효율적인 접근법 (Better Approach):
$x \rightarrow x^2 \rightarrow x^4 \rightarrow x^8$ 처럼 앞서 계산한 결과값을 통째로 제곱(Square)해 나가는 방식입니다.
이렇게 하면 지수가 $2^{1024}$일 때 겨우 $1024$번의 곱셈(로그 복잡도, $O(\log n)$)만으로 결과를 얻어낼 수 있습니다.

Q. 지수가 홀수이거나 2의 거듭제곱 꼴이 아닐 때는 어떻게 하나요?
이때 사용하는 범용적인 알고리즘이 바로 'Square-and-Multiply Algorithm'입니다. 자세한 동작 방식은 다음 수업 시간에 이어서 다루게 될 예정입니다.