RSA

RSA

RSA란

  • SSL / TLS에 가장 많이 사용되는 공개키 암호화 알고리즘.
  • 공개키와 개인키를 사용하며, 암호화는 공개키를 통해, 복호화는 개인키를 통해 수행.

준비 사항

  1. 매우 큰 두 소수 p, q를 준비.
  2. p - 1, q - 1과 서로소인 e를 찾음.
  3. ed ≡ 1 (mod (p - 1)(q - 1))인 d를 찾음.
  4. p와 q를 곱한 값을 N이라고 하고, N과 e를 공개함. 이들이 공개키가 됨.
  5. d는 공개하지 않고, 해독하는 사람이 가지고 있음. 이것이 개인키가 됨.

암호화

  1. 암호문을 받는 사람이 공개키를 제공.
  2. 암호문을 보내는 사람이 평서문 a를 이용해 다음 x 값을 계산. 이 때 a는 무조건 N보다 작아야 함.
    • x = a ^ e % N
  3. x가 암호문이 되고, 이를 전송.

복호화

  1. 암호문을 보낸 사람에게서 암호문 x를 받음.
  2. 다음과 같은 방법을 통해 y값 계산
    • y = x ^ d % N
  3. y는 평서문 a와 동일하기 때문에, 복호화가 완료됨.

원리

  • 오일러 정리에 의해, a ^ (p - 1)(q - 1) ≡ 1 (mod N)임.
  • 따라서, y ≡ x ^ d ≡ a ^ (ed) ≡ a ^ (k _ (p - 1)(q - 1) + 1) ≡ 1^k _ a ≡ a (mod N) 임.
  • y, a 둘 다 N보다 작으므로 y = a가 됨.

References

  1. https://namu.wiki/w/RSA%20%EC%95%94%ED%98%B8%ED%99%94