홍라이프 계산기RSA 키 계산 쉽게 이해하기 — 개념과 원리
RSA는 전자서명과 키 교환에 널리 쓰이는 공개키 암호입니다. 이 계산기는 아주 작은 소수로 교과서식 RSA를 실행해, 모듈러스를 만들고 개인 지수를 구한 뒤 숫자를 암호화하고 다시 복호화하는 과정을 단계별로 보여 줍니다. RSA가 왜 성립하는지 직접 확인하고 싶은 학생과 개발자를 위한 도구입니다.
계산 방법
- 두 소수 p, q를 골라 n = p × q를 만듭니다.
- 오일러 피 함수 φ(n) = (p − 1)(q − 1)을 구합니다.
- gcd(e, φ(n)) = 1인 공개 지수 e를 고릅니다. p나 q가 소수가 아니거나 e가 φ(n)과 서로소가 아니면 계산을 멈춥니다.
- e × d ≡ 1 (mod φ(n))을 만족하는 개인 지수 d = e⁻¹ mod φ(n)을 확장 유클리드 호제법으로 구합니다.
- 0 ≤ m < n인 메시지 m을 c = mᵉ mod n으로 암호화하고, m = cᵈ mod n으로 복호화합니다. 거듭제곱은 큰 정수로 정확하게 계산합니다.
원리
오일러 정리에 따르면 m과 n이 서로소일 때 m^φ(n) ≡ 1 (mod n)입니다. e × d = 1 + t × φ(n)이므로 c = mᵉ를 d제곱하면 m^(1 + tφ(n)) = m × (m^φ(n))^t ≡ m이 됩니다. 중국인의 나머지 정리를 쓰면 n보다 작은 모든 m에서 성립함을 보일 수 있습니다. n과 e는 공개되지만 d를 구하려면 φ(n)이 필요하고, 이는 n을 소인수분해하는 것만큼 어렵습니다. 3,233은 바로 분해되지만 2,048비트 수는 현재 컴퓨터로 분해할 수 없습니다.
예제 풀이
- 입력값은 p = 61, q = 53, e = 17, m = 65입니다.
- n = 61 × 53 = 3,233입니다.
- φ(n) = 60 × 52 = 3,120이고, gcd(17, 3,120) = 1이므로 e를 쓸 수 있습니다.
- 17 × 2,753 = 46,801 = 15 × 3,120 + 1이므로 d = 2,753입니다.
- 암호문은 c = 65¹⁷ mod 3,233 = 2,790입니다.
- 2,790^2,753 mod 3,233 = 65로 원래 메시지가 돌아옵니다.
결과 해석
복호화 결과가 처음의 m과 같으면 키 쌍이 올바르게 만들어진 것입니다. 다른 값이 나오면 대개 m이 n 이상이라 하나로 표현되지 않은 경우입니다. 실제로는 e로 65,537을 많이 쓰고, n은 2,048비트 이상을 씁니다.
흔한 실수
- 메시지 숫자를 n과 같거나 크게 넣습니다.
- φ(n)과 공약수가 있는 e를 골라 d가 존재하지 않습니다.
- 교과서식 RSA를 그대로 써도 된다고 생각합니다. 패딩이 없으면 같은 m은 항상 같은 c가 되어 안전하지 않습니다.
자주 묻는 질문
왜 e = 65,537을 많이 씁니까?
소수이면서 이진수로 1인 비트가 두 개뿐이라 암호화와 서명 검증이 빠르고, 패딩과 함께 쓰면 작은 지수 공격도 피할 수 있기 때문입니다.
φ(n) 대신 λ(n)을 써도 됩니까?
됩니다. 많은 라이브러리가 λ(n) = lcm(p − 1, q − 1)로 d를 구하며, 더 작지만 똑같이 유효한 d가 나옵니다.
요즘 RSA 키는 얼마나 길어야 합니까?
일반 용도는 2,048비트를 최소로 보고, 장기 보호에는 3,072비트가 권고됩니다.
출처: R. L. Rivest, A. Shamir, L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM 21(2), 1978 · IETF RFC 8017, PKCS #1: RSA Cryptography Specifications Version 2.2 · NIST SP 800-57 Part 1, Recommendation for Key Management