RSA 암호화와 모듈러 연산 개념 정리

 

1. RSA 암호화 알고리즘 기초

1.1 RSA란?

• 공개 키(Public Key)와 개인 키(Private Key)를 사용하는 비대칭 암호화 알고리즘이다.
• 소인수 분해가 어려운 수학적 성질을 이용하여 보안을 확보한다.

1.2 키 생성 과정

1. 두 개의 작은 소수 $p = 3$, $q = 11$ 선택
2. $n = p \times q = 3 \times 11 = 33$
3. 오일러 함수: $\varphi(n) = (p - 1)(q - 1) = 2 \times 10 = 20$
4. 공개 키 지수 $e = 7$ 선택 (조건: $\gcd(7, 20) = 1$)
5. 개인 키 지수 $d$ 계산: $$ ed \equiv 1 \mod{20} \Rightarrow 7 \cdot d \equiv 1 \mod{20} $$ → $d = 3$ (왜냐하면 $7 \cdot 3 = 21 \mod 20 = 1$)

공개 키: $(e, n) = (7, 33)$
개인 키: $(d, n) = (3, 33)$

1.3 암호화 / 복호화 과정 (예시 포함)

• 평문 메시지: $M = 4$
• 암호화: $$ C = M^e \mod n = 4^7 \mod 33 $$ 계산:
  • $4^2 = 16$
  • $4^3 = 64$
  • $4^4 = 256$
  • $4^5 = 1024$
  • $4^6 = 4096$
  • $4^7 = 16384$
  • $16384 \mod 33 = 16$ → 암호문 $C = 16$
• 복호화: $$ M = C^d \mod n = 16^3 \mod 33 $$ 계산:
  • $16^2 = 256$
  • $16^3 = 256 \cdot 16 = 4096$
  • $4096 \mod 33 = 4$ → 복호화 결과: $M = 4$

---

2. 모듈러 연산 (Modular Arithmetic)

2.1 정의

$a \mod m$은 $a$를 $m$으로 나눈 나머지를 의미한다.

예:

13 \mod 4 = 1 \\
9 \mod 4 = 1 \\
\Rightarrow 13 \equiv 9 \mod 4

2.2 합동(Congruence)

• $a \equiv b \mod m$은 $a$와 $b$가 $m$으로 나눈 나머지가 같음을 의미한다.

2.3 음수에 대한 모듈러

• 음수도 모듈러 연산 가능

-2 \mod 3 = 1

---

3. 모듈러 연산의 항등원과 역원

3.1 항등원 (Identity)

• 덧셈의 항등원: $0$ (예: $a + 0 = a$)
• 곱셈의 항등원: $1$ (예: $a \cdot 1 = a$)

3.2 역원 (Inverse)

• 어떤 연산의 결과가 항등원이 되게 만드는 수
• 덧셈의 역원: $-a$ → $a + (-a) = 0$
• 곱셈의 역원: $a^{-1}$ → $a \cdot a^{-1} = 1$

---

4. 모듈러 곱셈 역원 (Multiplicative Inverse)

4.1 정의

어떤 수 $a$에 대해 다음을 만족하는 $x$가 존재할 때:

a \cdot x \equiv 1 \mod m

4.2 예시

3 \cdot x \equiv 1 \mod 7 \\
\text{답: } x = 5 \Rightarrow 3 \cdot 5 = 15 \mod 7 = 1

---

5. 분수의 모듈러 연산

분수 $\frac{a}{b} \mod m$을 계산하려면 다음과 같이 한다:

\frac{a}{b} \mod m = (a \cdot b^{-1}) \mod m

5.1 예시: $\frac{3}{4} \mod 7$

1. $4^{-1} \mod 7 = 2$ (왜냐하면 $4 \cdot 2 = 8 \mod 7 = 1$)
2. 따라서: $$ \frac{3}{4} \mod 7 = 3 \cdot 2 \mod 7 = 6 $$

---

6. 모듈러 역원 구하기: 확장 유클리드 알고리즘

6.1 확장 유클리드 알고리즘의 역할

• 다음 식을 만족하는 정수 $x, y$를 찾는다: $$ a \cdot x + m \cdot y = \gcd(a, m) $$
• 만약 $\gcd(a, m) = 1$이라면, $x$가 $a$의 모듈러 역원이 된다.

6.2 예시: $3^{-1} \mod 7$

• $7 = 2 \cdot 3 + 1$
• $1 = 7 - 2 \cdot 3 = (-2) \cdot 3 + 1 \cdot 7$
• 따라서 $x = -2$, 즉 $3^{-1} \equiv -2 \equiv 5 \mod 7$

6.3 파이썬 코드 예시

# 확장 유클리드 알고리즘

def extended_gcd(a, b):
    if b == 0:
        return (1, 0, a)
    else:
        x1, y1, d = extended_gcd(b, a % b)
        x, y = y1, x1 - (a // b) * y1
        return (x, y, d)

def mod_inverse(a, m):
    x, y, g = extended_gcd(a, m)
    if g != 1:
        return None
    else:
        return x % m

print(mod_inverse(3, 7))  # 출력: 5