🔐 [클래식] A Method for Obtaining Digital Signatures and Public-Key Cryptosystems — '공개해도 안전한 열쇠'를 처음 구현한 RSA

논문 정보

한 줄 요약 — '자물쇠는 모두에게 나눠주고, 열쇠만 숨긴다'

1976년 Diffie와 Hellman은 "공개키 암호"라는 개념을 세상에 던졌지만, 정작 그것을 실제로 만들 방법은 제시하지 못했다(그들은 개념만 있고 실물 구현은 없다고 스스로 밝혔다). 1년 뒤 MIT의 Rivest·Shamir·Adleman이 그 개념을 처음으로 동작하는 실물로 구현한 것이 바로 이 논문이다. 아이디어는 이렇게 요약된다 — 메시지를 숫자 M으로 바꾼 뒤, 공개된 지수 e로 거듭제곱하고, 공개된 합성수 n으로 나눈 나머지를 취하면 암호문이 된다. 복호화는 비밀 지수 d로 같은 연산을 한 번 더 하면 된다. 안전성은 "공개된 n을 소인수분해하기 어렵다"는 사실에 기대는데, 논문이 제시한 200자리 n에 대해 저자들이 계산한 분해 시간은 약 3.8×10⁹년이었다. 이 하나의 방법이 오늘날 HTTPS·SSH·전자서명·코드 서명의 밑바탕이 되었다.

"보안 체계가 안전하다는 것을 증명할 방법은 없다. 유일하게 가능한 시험은, 누군가 그것을 깨뜨릴 방법을 생각해낼 수 있는지 지켜보는 것이다." — 이 논문 IX장, 그리고 "독자에게 도전한다, 이 방법을 깨뜨려 보라."

배경 — '키 배포 문제'라는 벽

• 모든 고전 암호의 공통 약점: 논문은 "모든 고전적 암호 기법(당시 NBS의 DES 표준 포함)은 키 배포 문제(key distribution problem)로 고통받는다"고 못 박는다. 비밀 통신을 시작하기 전에, 송신자와 수신자에게 암호·복호 키를 각각 전달하는 또 다른 비밀 거래가 필요하다는 뜻이다.
• 전령(courier)의 한계: 전통적으로는 사람이 직접 키를 나르는 수밖에 없었지만, "빠르고 값싼 전자 우편(electronic mail) 시스템"을 만들려면 그런 물리적 전달은 불가능하다.
• Diffie–Hellman의 개념, 남겨진 숙제: 1976년 Diffie와 Hellman이 "공개키 암호"라는 개념과 "트랩도어 단방향 함수" 아이디어를 제시했지만, 구체적인 예시는 하나도 없었다. 이 논문이 그 숙제를 푼다.
• 두 가지 요구: 전자 우편이 종이 우편을 대체하려면 (a) 메시지는 사적(private)이어야 하고, (b) 메시지에 서명(signed)할 수 있어야 한다. 이 논문은 이 둘을 동시에 해결한다.

핵심 1 — 공개키 암호체계의 네 가지 성질과 '트랩도어 단방향 함수'

• 공개 파일(public file) 개념: 각 사용자는 자신의 암호화 절차 E를 공개 파일에 올려두고, 대응하는 복호화 절차 D의 세부는 비밀로 유지한다. 이 프로토콜이 성립하려면 네 가지 성질이 필요하다.
• 네 가지 성질: (a) D(E(M)) = M — 복호화하면 원문이 돌아온다. (b) E와 D는 계산이 쉬워야 한다. (c) E를 공개해도 D를 계산하는 쉬운 방법이 드러나지 않아야 한다. (d) E(D(M)) = M — 순서를 뒤집어도 성립해야 하며, 이 성질(d)은 오직 서명(signature)을 구현하기 위해 필요하다.
• 정의 — 트랩도어 단방향 함수: (a)~(c)를 만족하는 함수 E를 "트랩도어 단방향 함수"라 부르고, (d)까지 만족하면 "트랩도어 단방향 치환(permutation)"이라 부른다. 한 방향은 쉽지만 역방향은 (겉보기에) 매우 어렵고, 특정한 비밀 정보("트랩도어")를 알면 역방향도 쉬워진다.
• 왜 새로웠나: 논문은 "우리의 암호화 함수는 저자들이 아는 유일한 트랩도어 단방향 치환의 후보"라고 적는다 — 즉 당시 유일한 실물 예시였다. 그래서 논문은 다른 예시를 찾아야 할 필요성까지 언급한다.

핵심 2 — 알고리즘: RSA의 실제 수식

• 키 생성: 큰 "임의의" 소수 p, q를 골라 n = p · q를 만든다. (p−1)·(q−1)과 서로소인 큰 임의 정수 d를 고르고, e는 e · d ≡ 1 (mod (p−1)·(q−1))를 만족하는 d의 곱셈 역원으로 계산한다. 공개키는 (e, n), 비밀키는 (d, n).
• 암호화·복호화: C ≡ E(M) ≡ Me (mod n)이고 D(C) ≡ Cd (mod n)이다. 흥미로운 대칭성 — 암호화와 복호화가 완전히 같은 연산이고 지수만 다르다. 암호화는 메시지 크기를 늘리지 않는다(둘 다 0~n−1 범위).
• 왜 동작하나(VI장, 수학): 오일러·페르마의 항등식 Mφ(n) ≡ 1 (mod n)가 토대다. 여기서 φ(n) = (p−1)(q−1) = n − (p+q) + 1. e·d ≡ 1 (mod φ(n))이므로 Me·d ≡ Mk·φ(n)+1 ≡ M (mod n)이 성립해 E와 D가 서로 역치환이 된다.
• 효율성(VII장): "반복 제곱과 곱셈(exponentiation by repeated squaring)"으로 Me (mod n)를 최대 2·log2(e)번의 곱셈과 나눗셈으로 계산한다. 고속 컴퓨터는 200자리 메시지를 몇 초 안에 암호화하며, 블록당 암호화 시간은 n의 자릿수의 세제곱보다 빠르게 늘지 않는다.
• 구체적 파라미터: 100자리 소수 p, q를 권장 → n은 200자리. 소수 정리에 따르면 100자리 소수를 찾으려면 평균 약 115개를 검사하면 된다. 소수 판정은 Solovay–Strassen 확률적 알고리즘으로, 100개의 무작위 a에 대해 통과하면 합성수일 확률이 2⁻¹⁰⁰ 수준이다.
• 논문 속 장난 — VIII장 '작은 예제': p=47, q=59 → n=2773, d=157, φ=2668, e=17. "ITS ALL GREEK TO ME"를 두 글자씩 숫자로 바꾼 뒤 첫 블록 M=920은 92017 ≡ 948 (mod 2773)로 암호화된다. 전체 암호문은 0948 2342 1084 1444 2663 2390 0778 0774 0219 1655.

핵심 3 — 디지털 서명: '부인할 수 없음'을 수학으로

• 인증과 서명의 차이: 논문은 "인증(authentication)"은 수신자가 메시지가 송신자에게서 왔다고 스스로 만족하는 것이고, "서명(signature)"은 수신자가 제3자(판사)에게까지 그 사실을 입증할 수 있어야 한다고 구분한다.
• 서명이 메시지에 묶여야 하는 이유: 서명이 서명자 의존적일 뿐 아니라 메시지 의존적이어야 한다. 그렇지 않으면 수신자가 서명을 다른 메시지에 잘라 붙이거나("cutting and pasting") 메시지를 바꿔치기해도 탐지할 수 없다.
• 서명 절차: Bob이 S = DB(M)으로 메시지를 자기 비밀키로 복호화해 서명을 만들고, 이를 Alice의 공개키로 다시 암호화해 EA(S)를 보낸다. Alice는 DA로 S를 얻고, 공개 파일의 EB로 M = EB(S)를 복원한다. Bob은 다른 누구도 DB를 만들 수 없으므로 나중에 서명 사실을 부인할 수 없다.
• 왜 치환(permutation)이 필요한가: 서명은 암호화되지 않은 메시지에 복호화 함수를 적용하므로, 모든 메시지가 어떤 메시지의 암호문이 되는 "치환" 성질(d)이 반드시 필요하다.
• 당시의 응용 상상: 논문은 전자 수표(electronic check) 시스템, 서명된 이메일, 심지어 "통화의 모든 단어를 서명해 보내는" 미래까지 그린다 — 오늘날의 전자서명·공인인증·코드 서명이 여기서 출발한다.

핵심 4 — 보안 근거: '깨는 것 = 인수분해만큼 어렵다'

• 공개된 도전: 논문은 "우리 방법을 깨뜨릴 방법을 찾아보라"고 독자에게 공개적으로 도전하면서, 명백한 공격 경로들이 모두 적어도 n을 인수분해하는 것만큼 어렵다는 것을 보인다. 특히 φ(n)을 알아내도, 비밀 지수 d를 알아내도 n을 쉽게 인수분해할 수 있으므로 우회로가 없다.
• 인수분해 자체의 난이도: "ln n · ln ln n의 제곱근" 규모(당시 저자들이 아는 가장 빠른 Schroeppel 알고리즘)와 Pollard의 O(n1/4) 알고리즘을 든다. 인수분해는 300년 넘게 천재 수학자들이 파고든 문제이고, "200자리 수를 합리적 시간에 인수분해하는 알고리즘은 아직 없다."
• Table 1 — 자릿수별 예상 분해 비용(연산 1회 = 1마이크로초 기준):

• 권장값: "n을 약 200자리로 하라" — 80자리는 현재 기술로 중간 수준, 200자리는 미래 발전에 대한 안전 여유를 준다. 키 길이를 골라 보안 수준을 조절할 수 있다는 유연성 자체가 기존 NBS(DES) 방식에는 없는 특징이었다.
• 정직한 미해결 문제: 논문은 "우리 방법을 깨는 모든 일반적인 방법이 효율적 인수분해 알고리즘을 낳는다는 것을 증명하지 못했다"고 인정한다. 이는 곧 RSA가 인수분해만큼 어렵다는 증명되지 않은 추측(conjecture)에 기대고 있음을 뜻한다 — 40여 년 뒤 양자 컴퓨터(Shor 알고리즘)가 이 가정을 위협하는 지점이기도 하다.

한계 · 유의점

• 안전성은 '추측' 위에: 인수분해가 어렵다는 가정에 의존하며, 논문 스스로 그 함의를 증명하지 못했음을 밝힌다. 또 "RSA를 깨는 것 = 인수분해"라는 등가성도 이 논문에서는 미증명이었다.
• 당시엔 교과서 RSA(패딩 없음): 이 원논문의 방식은 결정적(deterministic)·곱셈적 구조라, 훗날 선택 암호문 공격과 작은 지수·공통 모듈러스 문제가 드러났다. 실무 구현은 OAEP 등 확률적 패딩과 상수시간 구현으로 이를 보완한다.
• 패러다임 전환: 2015년 Logjam, 2018년 ROBOT 같은 공격은 키 교환/서명 구현의 결함을 드러냈고, 2013년 이후 전방향 안전성(forward secrecy)을 위해 RSA 키 교환은 ECDHE로 대체되는 흐름이 이어졌다 — RSA는 주로 서명과 신뢰 루트 쪽에 남았다.
• 그래도 사라지지 않는다: TLS 인증서, 코드 서명, SSH, PGP, 그리고 오늘날의 하드웨어 신뢰 루트까지 — "공개키를 나눠주고도 안전하다"는 이 논문의 기본 발상은 여전히 모든 인터넷 보안의 출발점이다.

출처

• 논문 (CACM, MIT 공개 PDF): people.csail.mit.edu/rivest/Rsapaper.pdf
• 아카이브 사본: Internet Archive — Rsapaper.pdf · DOI(등록): 10.1145/359340.359342
• 서지: Communications of the ACM, Vol. 21, No. 2 (1978.02), pp. 120–126 · 최초 유통은 MIT/LCS/TM-82(1977)
• 함께 읽기 — 공개키·암호학 계보: 2026-09-30 New Directions in Cryptography (Diffie–Hellman, 1976) — 이 논문이 구현한 '개념'의 출처 · 2026-09-21 On the Security of Public Key Protocols (Dolev–Yao, 1983) — 공개키 위 공격자 모델 · 2026-09-16 How to Break MD5 (2005) · 2026-09-04 Differential Cryptanalysis of DES-like Cryptosystems (1990) · 2026-08-31 Timing Attacks (Kocher, 1996)