학교자율교육과정(수업량유연화) : RSA암호학의 이해

2024.7.10
학교에서 수업량유연화 기간에 [RSA암호학의 이해] 프로그램을 준비하며 만들었습니다. 예전에 수학대회 준비했던 것을 이용했는데, 지금은 그때와 달리 학생들의 동기부여가 적기 때문에 최대한 단순화 했습니다.

오랜만에 학생들과 정말 즐겁게 활동했습니다^^

한 번 도전해보세요
https://docs.google.com/forms/d/e/1FAIpQLScODGBOk7wMBQqTMo_0GBoR5cmEID_ihbewzv2GYQjm78Vbag/viewform?usp=sf_link

아래는 chat gpt 가 작성해준 내용입니다.
RSA 암호학이란?
현대의 디지털 보안 시스템에서 중요한 역할을 하는 암호화 방법입니다. RSA는 Ron Rivest, Adi Shamir, Leonard Adleman이라는 세 과학자의 이름에서 따온 것입니다.

1. 키 만들기

RSA 암호화에서 가장 중요한 첫 단계는 키를 만드는 것입니다. 키는 두 가지로 나뉩니다: 공개 키와 비밀 키. 공개 키는 누구와도 공유할 수 있지만, 비밀 키는 오직 소유자만 알아야 합니다.
단계 1: 두 개의 큰 소수(p와 q) 선택하기

• 먼저, 두 개의 큰 소수 ppp와 qqq를 선택합니다.
• 예를 들어, p=61p = 61p=61과 q=53q = 53q=53을 선택할 수 있습니다.

단계 2: n 계산하기

• nnn은 ppp와 qqq를 곱한 값입니다.
• n=p×q=61×53=3233n = p \times q = 61 \times 53 = 3233n=p×q=61×53=3233

단계 3: 오일러의 피 함수 φ(n) 계산하기

• φ(n)=(p−1)×(q−1)φ(n) = (p-1) \times (q-1)φ(n)=(p−1)×(q−1)
• φ(3233)=(61−1)×(53−1)=60×52=3120φ(3233) = (61-1) \times (53-1) = 60 \times 52 = 3120φ(3233)=(61−1)×(53−1)=60×52=3120

단계 4: 공개 키 지수 eee 선택하기

• eee는 1과 φ(n)φ(n)φ(n) 사이의 숫자로, eee와 φ(n)φ(n)φ(n)는 서로소(즉, 공약수가 1인 상태)여야 합니다.
• 일반적으로 e=65537e = 65537e=65537을 많이 사용합니다. 이 값은 계산을 단순화하고, 충분한 보안을 제공합니다.

단계 5: 비밀 키 지수 ddd 계산하기

• ddd는 다음 식을 만족하는 값입니다: d×e≡1 (mod φ(n))d \times e \equiv 1 \ (\text{mod} \ φ(n))d×e≡1 (mod φ(n))
• 쉽게 말해, d×ed \times ed×e를 φ(n)φ(n)φ(n)으로 나눈 나머지가 1이 되도록 하는 ddd를 찾는 것입니다.
• d=2753d = 2753d=2753 (계산 과정을 단순화하기 위해 결과만 표시합니다)

이제 공개 키 (e,n)=(65537,3233)(e, n) = (65537, 3233)(e,n)=(65537,3233)과 비밀 키 (d,n)=(2753,3233)(d, n) = (2753, 3233)(d,n)=(2753,3233)이 생성되었습니다.

2. 암호화 및 해독

이제 생성된 키를 사용하여 메시지를 암호화하고 해독하는 과정을 살펴보겠습니다.
암호화 과정

• 암호화는 공개 키 (e,n)(e, n)(e,n)을 사용하여 이루어집니다.
• 평문 메시지 MMM을 암호화된 메시지 CCC로 변환합니다.
• C=Me (mod n)C = M^e \ (\text{mod} \ n)C=Me (mod n)
• 예를 들어, 평문 메시지 M=65M = 65M=65일 경우:
  • C=6565537 (mod 3233)C = 65^{65537} \ (\text{mod} \ 3233)C=6565537 (mod 3233)
  • C=2790C = 2790C=2790 (계산 과정을 단순화하기 위해 결과만 표시합니다)

해독 과정

• 해독은 비밀 키 (d,n)(d, n)(d,n)을 사용하여 이루어집니다.
• 암호화된 메시지 CCC를 다시 평문 메시지 MMM로 변환합니다.
• M=Cd (mod n)M = C^d \ (\text{mod} \ n)M=Cd (mod n)
• 예를 들어, 암호화된 메시지 C=2790C = 2790C=2790일 경우:
  • M=27902753 (mod 3233)M = 2790^{2753} \ (\text{mod} \ 3233)M=27902753 (mod 3233)
  • M=65M = 65M=65 (계산 과정을 단순화하기 위해 결과만 표시합니다)

이렇게 해서 원래의 평문 메시지 M=65M = 65M=65를 다시 얻을 수 있습니다.