배경지식

• Chinese Remainder Theorem - 알면 좋음

1. 개요

RSA(Rivest–Shamir–Adleman)는 대표적인 비대칭키 암호 알고리즘이다.

두 개의 서로 다른 키를 사용한다.

• 공개키: 공개해도 되는 키. 보통 “암호화” 또는 “서명 검증”에 사용한다.
• 개인키: 절대 노출되면 안 되는 키. 보통 “복호화” 또는 “서명 생성”에 사용한다.

1.1.2 RSA가 해결하는 문제

대칭키만으로는 처음 만난 두 주체가 안전하게 비밀키를 공유하기가 어렵다

RSA 같은 공개키 암호는 사전 공유 비밀 없이도 다음을 가능하게 한다.

1. 비밀 정보를 안전하게 전달(대표적으로는 세션용 대칭키)
2. 서명 기반 인증/무결성 보장(발신자 확인, 변조 방지)

1.1.3 RSA의 수학적 뼈대

• RSA는 보통 다음 형태의 모듈러 거듭제곱을 이용한다.
  • 암호화: $C \equiv M^e \pmod N$
  • 복호화: $M \equiv C^d \pmod N$
• 여기서 $N$ 은 보통 두 큰 소수 $p,q$ 의 곱 $N=pq$ 로 만든다.
• 핵심 가정은 $N$ 만 알고 $p,q$ 를 찾는 소인수분해가 매우 어렵다는 점이다.
  • 즉 “공개된 $N$ 으로부터 개인키에 필요한 정보를 역산하기 어렵다”가 RSA 보안의 출발점이다.

1.1.4 RSA는 언제 쓰나? (암호화 vs 서명)

• 암호화
  • 공개키로 암호화, 개인키로 복호화.
  • 실제로는 “메시지 전체”를 RSA로 직접 암호화하기보다, 대칭키를 안전하게 전달하는 용도로 많이 사용한다.
• 전자서명
  • 개인키로 서명 생성, 공개키로 서명 검증.
  • “이 메시지가 키 소유자에게서 왔다”와 “전송 중 변조되지 않았다”를 제공한다.

2. 수학적 배경

• 모듈러 연산

  <aside> 💡

  모듈러 연산

  모듈러 연산은 정수를 특정 수로 나눈 나머지가 같을 때 두 정수를 동일하게 취급하는 연산이다. 나누는 수를 모듈러라고 하며, $a \equiv b \pmod n$으로 표기하고 합동식이라고 한다.

  </aside>

• 오일러 피 함수

  <aside> 💡

  오일러 피 함수

  $\phi(x)$라고 쓰며 phi라고 읽는다.

  $\phi(x)$는 x와 서로소이며 0≤k<x인 숫자의 집합 개수이다 이를 수식적으로 나타내면 다음과 같다.

  $$ \phi(x) = \|\{k \in \mathbb{Z^+} : k < x\ and\ gcd (x,k) = 1\}\| $$

  • $\mathbb{Z^+}$ : 양의 정수 범위
  • ||집합|| : 집합의 개수
  • $a\in b$ : a는 b 집합의 포함 관계
  • gcd(x,k) = n : x,k의 최대공약수가 n

  한마디로 이 오일러의 피 함수를 이용하여 x의 서로소 개수를 구하는 것이다

  • $\phi(4) = 1,2,3\ 중\ 4와\ 서로소는\ 1,3 = 2$
  • $\phi(7) = 1,2,3,4,5,6은\ 7과\ 모두\ 서로소이기에 = 6$ </aside>

• 오일러의 정리

  <aside> 💡

  페르마의 소정리/오일러 정리

  gcd(a,n)=1인 양의 정수 a,n에 대하여

  $$ a^{\phi(n)}\equiv1\pmod{n} $$

  여기서 φ(n)은 오일러 피 함수 이다.

  </aside>

• 확장 유클리드 알고리즘

  <aside> 💡

  Euclidean algorithm

  확장 유클리드 알고리즘은 두 정수 a와 b의 최대공약수(gcd)를 구할 뿐만 아니라 베주 항등식을 만족하는 정수 x와 y를 찾는 알고리즘이다.

  </aside>