RSA 원리

 

 

 

RSA(RSA cryptosystem)의 핵심 원리는:

곱하기는 쉬운데,
다시 소인수분해는 매우 어렵다

 

를 이용하는 것.

그리고 그 위에:

• 모듈러 연산(mod)
• 오일러 정리

를 조합해서:

공개키로 잠그고
개인키로만 풀 수 있는 구조

 

를 만든다.

---

RSA 전체 흐름 먼저

RSA는 크게 3단계다.

단계	내용
키 생성	공개키/개인키 생성
암호화	공개키 사용
복호화	개인키 사용

---

STEP 1 — 소수 2개 선택

아주 큰 소수 두 개를 고른다.

예제는 이해를 위해 작은 수로 설명.

p = 17
q = 23

 

---

STEP 2 — 두 수를 곱함

𝑛=𝑝×𝑞

즉:

17 × 23 = 391

 

여기서:

n = 391

 

이 공개된다.

---

왜 중요하냐?

곱하는 건 쉽다.

하지만:

391만 보고
17 × 23 찾기

 

는 훨씬 어렵다.

실제 RSA는 숫자가 엄청 커서 현실적으로 분해가 매우 어렵다.

---

STEP 3 — 오일러 파이 계산

φ(n)=(p−1)(q−1)

즉:

(17-1)(23-1)
=
16 × 22
=
352

 

---

STEP 4 — 공개 지수 e 선택

조건:

gcd(e,φ(n))=1

즉 서로소인 수 선택.

보통 실무에서는:

65537

 

엄청 많이 사용.

예제에서는:

e = 3

 

같은 작은 값 사용 가능.

---

STEP 5 — 개인키 d 계산

여기가 핵심이다.

조건:

d×e≡1(modφ(n))

즉:

d × 3 mod 352 = 1

 

되는 d를 찾는다.

결과:

d = 235

 

---

이제 키 완성

공개키

(e,n)=(3,391)

---

개인키

(d,n)=(235,391)

---

암호화

예:

평문 M = 5

 

암호화:

 

즉:

5^3 mod 391
=
125

 

암호문:

C = 125

 

---

복호화

복호화는:

즉:

125^235 mod 391

 

계산하면 다시:

5

 

가 나온다.

---

왜 다시 원복될까?

이게 RSA 핵심이다.

오일러 정리에 의해:

가 성립하게 d를 만든다.

즉:

암호화 후 복호화
=
원래 값

 

되도록 수학적으로 설계한 거다.

---

그런데 공격자는 왜 못 푸나?

공격자는 공개키:

(e,n)

 

만 안다.

---

문제는 d 계산하려면

φ(n)

이 필요하고,

φ(n)을 계산하려면:

p,q 알아야 함

 

---

결국 핵심 난제

n → p,q 분해

 

즉 소인수분해다.

---

실제 RSA는 엄청 큼

실무:

키 크기	의미
2048bit	일반적
3072bit	더 강함
4096bit	고보안

---

왜 RSA가 느리냐?

문제는:

이 계산이 매우 무겁다.

즉:

• 거대한 정수
• 거듭제곱
• mod 반복

연산이다.

---

그래서 HTTPS에서는

RSA는:

AES 세션키 교환만

 

하고,

실제 데이터는:

• Advanced Encryption Standard
• AES-GCM

사용한다.

---

RSA의 진짜 혁신

RSA 이전엔:

"키를 어떻게 전달?"

 

문제가 있었다.

RSA는:

공개키는 공개해도 안전

 

이라는 혁신을 만든 거다.

---

핵심 요약

RSA 원리는:

큰 수 곱셈은 쉽지만,
다시 소인수분해는 매우 어렵다는 성질을 이용해
공개키와 개인키를 만드는 것

 

이다.