RSA 알고리즘 계산

앞서 작성한 RSA 암호화 알고리즘에 대한 이론에 이어, 이 알고리즘은 두 개의 큰 소수를 기반으로 하여 안전한 데이터 전송을 가능하게 합니다. RSA는 주로 이메일 암호화, 디지털 서명, SSL/TLS와 같은 보안 통신 프로토콜에서 사용됩니다.

실제 숫자를 사용하여 키 생성 → 암호화 → 복호화의 과정을 거치며, 계산 과정을 살펴보겠습니다.

 

 

RSA 암호화 알고리즘 예제 (p = 61, q = 53)

RSA 알고리즘의 주요 과정(키 생성 → 암호화 → 복호화)을 실제 숫자로 계산해 보겠습니다.

---

1. 키 생성 (Key Generation)

(1) 두 개의 큰 소수 선택

RSA 알고리즘은 두 개의 큰 소수 p와 q를 선택하는 것으로 시작합니다.
예제에서는 작은 숫자를 사용하여 계산을 쉽게 하겠습니다.

• p=3, q=11

 

(2) 두 소수의 곱을 구하여 n 계산

n은 공개 키와 개인 키 모두에서 사용됩니다.

• n=p×q =3×11=33

 

(3) 오일러 피 함수 φ(n)계산

오일러 피 함수는 다음과 같이 계산됩니다.

• φ(n)=(p−1)×(q−1)
• φ(33)=(3−1)×(11−1)=2×10=20

 

(4) 공개 키 지수 e선택

e는 1<e<φ(n)이면서 gcd⁡(e,φ(n))=1을 만족해야 합니다.

• e=3을 선택합니다.
• gcd⁡(3,20)=1이므로 선택 가능합니다.

 

(5) 개인 키 지수 d계산

d는 다음 방정식을 만족하는 수를 찾는 과정입니다.

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

 즉,

        d×3≡1(mod20)

이를 만족하는 최소의 d는 7입니다. (역원 계산)

 

(6) 공개 키와 개인 키 설정

• 공개 키 (Public Key): (e,n)=(3,33)
• 개인 키 (Private Key): (d,n)=(7,33)

---

2. 암호화 (Encryption)

사용자가 보낼 메시지를 숫자로 변환해야 합니다.

• 예제에서 메시지 M=4를 암호화해 보겠습니다.

암호문 C는 다음 공식으로 계산됩니다.

 

따라서 암호문 C=31 입니다.

 

---

3. 복호화 (Decryption)

암호문 C=31을 복호화하는 과정입니다.

---

정리해보면

---

결론

이 과정을 통해 RSA 알고리즘이 어떻게 작동하는지 알 수 있습니다.

• 공개 키(e, n)로 암호화,
• 개인 키(d, n)로 복호화 하여 원래 메시지를 복원할 수 있습니다.
• 모듈러 연산을 활용하여 큰 숫자를 다룰 수 있도록 설계된 안전한 알고리즘입니다.