[공개 키 암호] RSA

1. RSA

• 공개 키 암호 알고리즘 중 하나
• 공개 키 암호와 디지털 서명에 사용가능

 

---

2. RSA에 의한 암호화

• RSA에서는 평문, 키, 암호문이 숫자임

• e와 n이라는 한 쌍의 수를 알면 누구라도 암호화 가능 -> e와 n이 RSA에서 사용하는 암호화 키 -> e와 n으로 이루어진 쌍이 공개 키

• e와 n이라는 2개의 수는 키 쌍(공개 키와 개인 키)이 아님 -> e와 n 두 수를 1조로 한 것이 하나의 공개 키
• 공개 키 = (e,n)

---

3. RSA에 의한 복호화

• d와 n 쌍인 (d, n)이 개인 키에 해당
• d와 n 모두를 알고 있는 사람만이 이 암호문을 복호화할 수 있음

---

4. 키 쌍의 생성

• e와 n이 공개 키, d와 n이 개인 키이므로 e, d, n 3개의 수를 구하는 것은 키 쌍을 생성하는 것과 다름없음
• RSA의 키 쌍 생성 순서
  • N을 구함
    • N = p x q (p, q는 소수)
  • L을 구함 (L : 키 쌍을 생성할 때만 등장하는 수)
    • L = lcm(p-1, q-1)     (L은 p-1과 q-1의 최소 공배수)
  • E를 구함
    • 1 < E < L
    • gcd(E, L) = 1          (E와 L의 최대 공약수는 1(E와 L은 서로 소))
  • D를 구함
    • 1< D < L
    • E x D mod L = 1