RSA - 보안 알고리즘에 대해 이해

AWS에서 키페어 만들다가 궁금해서 찾아봤습니다.

일단 잘모르는 내용이기 때문에 물어보고 이해해보겠습니다.

 

https://sejin-technology.tistory.com/45

AWS - EC2 - Ubuntu 서버 설치하기 - Setting

 

궁금하면 보세요..

이해

 

일단 잘모르는 내용이기 때문에 ChatGpt에 예시를 들어 설명해달라고 했습니다.

 

아래는 아주 간단한 숫자를 사용한 RSA 개념 예시입니다. 실제 RSA에서는 수백~수천 비트 크기의 매우 큰 소수를 사용하지만, 여기서는 이해를 돕기 위해 작은 수를 사용하겠습니다. (실제 보안에는 전혀 쓰일 수 없음을 유의하세요.)

---

개념 상황

• 두 명, **송신자(민수)**와 **수신자(지영)**가 있습니다.
• 지영이 민수로부터 비밀 메시지를 안전하게 받고 싶다고 가정해 봅시다.
• 지영은 자신의 공개 키를 민수에게 알려주고, 민수는 그 공개 키로 메시지를 암호화한 뒤 지영에게 보냅니다.
• 지영은 자신의 비밀 키로 그 암호문을 복호화합니다.

---

키 생성 예시 (지영 측)

1. 두 개의 소수 선택하기
2. \[ p = 5, \quad q = 11 \]
3. 모듈러스 \( n \) 계산
4. \[ n = p \times q = 5 \times 11 = 55 \]
5. \(\phi(n)\) 계산
6. \[ \phi(n) = (p - 1)(q - 1) = (5 - 1)(11 - 1) = 4 \times 10 = 40 \]
7. 공개 지수 \( e \) 선택
8. \(\phi(n)=40\)과 서로소인 수 \(e=3\)을 선택합니다. (3과 40은 최대공약수가 1이므로 서로소)
9. 비밀 지수 \( d \) 계산\(d\)를 만족시키는 수를 찾습니다.따라서 \( d = 27 \).
10. 3 × 27 = 81이고, 81을 40으로 나눈 나머지는 1입니다.
11. \[ d \times e \equiv 1 \pmod{\phi(n)} \quad \Rightarrow \quad d \times 3 \equiv 1 \pmod{40} \]
12. 공개 키와 비밀 키 완성
    • 공개 키: \((n, e) = (55, 3)\)
    • 비밀 키: \((n, d) = (55, 27)\)

지영은 \((55, 3)\)를 공개 키로 민수에게 전송합니다.

---

암호화 (민수 측)

민수가 지영에게 보내고 싶은 평문 메시지를 숫자로 변환한다고 합시다.

예를 들어 "HI" 라는 메시지를 단순히 숫자 8로 표현한다고 가정합니다.

• 평문 \( M = 8 \)
• 지영의 공개 키 \((n,e)=(55,3)\) 사용

암호문 \( C \)는 다음과 같이 계산합니다.

\[ C = M^{e} \mod n = 8^{3} \mod 55 \]

\[ 8^{3} = 512 \]

이제 512를 55로 나눈 나머지를 구합니다.

55 × 9 = 495,

512 - 495 = 17,

따라서 \( 512 \mod 55 = 17 \).

암호문 \( C = 17 \).

민수는 이 암호문 17을 지영에게 전송합니다.

---

복호화 (지영 측)

지영은 자신의 비밀 키 \((n,d)=(55,27)\)를 사용하여 암호문 17을 복호화합니다.

\[ M = C^{d} \mod n = 17^{27} \mod 55 \]

실제 계산을 생략하면 RSA 구조 특성상 이 결과는 원문 \( M = 8 \)를 되찾게 됩니다.

원문 숫자 8이 우리가 약속한 "HI"를 의미하므로 지영은 메시지를 복원할 수 있습니다.

---

정리

1. 키 생성 (지영): 두 소수 \( p, q \)로부터 \( n \)과 \(\phi(n)\), 그리고 \( d \)를 구하고, \( e \)를 선택하여 공개 키 \((n,e)\)와 비밀 키 \((n,d)\)를 만든 뒤, 공개 키만 세상에 알립니다.
2. 암호화 (민수): 평문 \( M \)에 지영의 공개 키 \((n,e)\)를 적용해 \( C = M^{e} \mod n \)을 구하고, 이 \( C \)를 지영에게 보냅니다.
3. 복호화 (지영): 받은 암호문 \( C \)에 비밀 키 \((n,d)\)를 적용해 \( M = C^{d} \mod n \)을 구해 원래 평문을 복원합니다.

이와 같은 과정을 통해 RSA는 소인수분해의 어려움을 기반으로 공개 키를 알려도 안전한 통신을 가능하게 합니다.

 

 

 

내가한 정리

일단 RSA 라는 것은 소인수 분해를 활용하는 알고리즘이고, 비밀키가 없을때 공개키를 공격해도 어렵게 한다는 의미인 것을 이해할 수 있습니다.

 

 

 

다른 사이트에서 찾은 건데 훨씬 이해하기 쉬운 것 같습니다.

 

결국 평문을 공개키로 보안하고 , 공개키와 비밀키를 가지고 있는 Recipient가 쉽게 해독할 수 있게끔 한다는 것을

이해해 볼 수 있습니다.