Digital Signature — 전자 서명의 수학적 구조

RSA로 메시지를 암호화하면 기밀성은 확보된다. 하지만 Bob은 여전히 한 가지를 모른다. 이 메시지가 정말 Alice에게서 왔는가? 전자 서명은 그 질문에 답한다. 비밀키 없이는 위조할 수 없고, 공개키만으로 누구나 검증할 수 있는 수학적 사인이다.

이 포스트에서 다루는 내용

RSA 서명: $s = m^d \bmod n$ , 검증: $s^e = m$ . 정확성은 성립하지만 교과서 형태는 위조 가능
ElGamal 서명: $r = g^k \bmod p$ , $s = (m - ar)k^{-1} \bmod (p-1)$ (DLP 기반)
인증기관(CA): 공개키의 신뢰를 보증하는 신뢰 앵커
암호학적 해시: SHA로 $m \to h$ (고정 크기). 원상·제2원상·충돌 저항성이 각각 다른 공격을 막는다
역할 분담 뼈대: AES(기밀성) + RSA(키 전달·서명) + SHA(무결성), 그리고 실제 프로토콜이 여기에 더하는 것들

왜 서명이 필요한가

대칭키 시스템에서는 Alice와 Bob만이 키 $k$ 를 공유한다. Bob이 $k$ 로 암호문을 복호화했다면, 그 메시지는 $k$ 를 아는 Alice가 보냈다고 추론할 수 있다.

하지만 RSA 같은 공개키 시스템에서는 누구나 공개키 $(n, e)$ 로 암호화할 수 있다. Bob은 암호문을 복호화할 수 있지만, 누가 보냈는지는 알 수 없다.

전자 서명은 이 문제를 해결한다. 현실의 서명처럼 두 가지 조건을 만족해야 한다.

본인만 서명할 수 있다: 비밀키 없이는 위조할 수 없다
누구나 검증할 수 있다: 공개키로 누구나 확인한다

디지털 환경에서는 한 가지 조건이 추가된다. 종이 서명과 달리 비트열은 완벽히 복사되므로, 서명이 어느 문서에 묶여 있는지가 수식 안에 들어가 있어야 한다.

메시지 결속: 서명 $s$ 는 특정 $m$ 에만 유효해야 한다. $m$ 에 붙은 $s$ 를 떼어 $m'$ 에 붙이면 검증이 실패해야 한다.

이 두 조건을 하나로 묶은 표준 정의가 EUF-CMA(chosen-message attack 하의 존재적 위조 불가능성)다. 공격자가 자기가 고른 메시지들에 대한 서명을 얼마든지 얻어 낸 뒤에도, 한 번도 서명받지 않은 메시지에 대한 유효한 서명 하나를 새로 만들어 낼 수 없어야 한다는 요구다. 아래에서 서명 방식을 평가할 때 기준으로 삼는 것이 이 정의다.

RSA 서명

RSA의 암호화( $m^e$ )와 복호화( $m^d$ )는 서로 대칭이다. 즉 어느 방향으로 적용해도 원문이 복원된다.

(m^d)^e \equiv m^{de} \equiv m \pmod{n}

이 대칭성을 서명에 활용한다.

서명 생성 (Alice, 비밀키 $d$ 사용):

s = m^d \bmod n

서명 검증 (Bob, Alice의 공개키 $e$ 사용):

s^e \bmod n \stackrel{?}{=} m

RSA 전자 서명의 흐름. Alice가 비밀키 d로 평문 m에 서명해 (m, s)를 보내고, Bob은 Alice의 공개키 e로 s를 되돌려 m과 같은지 확인한다. 가로채더라도 d 없이는 유효한 s를 만들 수 없다

복호화 과정이 서명 생성, 암호화 과정이 서명 검증이 된다. 비밀키 $d$ 를 가진 Alice만이 유효한 $s$ 를 만들 수 있고, 공개키 $e$ 는 공개되어 있으므로 누구나 검증할 수 있다.

여기까지는 정확성일 뿐, 안전한 서명 방식이 아니다

위 식이 보인 것은 정확성뿐이다. 정직하게 만든 서명이 검증을 통과한다는 것. 앞에서 세운 EUF-CMA 기준으로 보면 이 형태(교과서 RSA, raw RSA)는 두 가지 방식으로 뚫린다.

서명을 먼저 고르고 메시지를 나중에 만든다. 아무 $s$ 나 하나 집어 $m = s^e \bmod n$ 을 계산하면 $(m, s)$ 는 검증을 통과한다. 서명을 한 번도 요청하지 않고 만들어 낸 유효한 쌍이다. $m$ 이 알아볼 수 없는 값이라 실제 피해가 없어 보이지만, EUF-CMA는 의미 있는 메시지를 요구하지 않으므로 이것으로 정의가 깨진다.

곱셈이 그대로 통과한다. RSA는 $(m_1 m_2)^d \equiv m_1^d \cdot m_2^d \pmod n$ 을 만족한다. $m_1$ 과 $m_2$ 의 서명을 얻어 두면 곱하기만 해도 $m_1 m_2 \bmod n$ 의 서명이 나온다. 서명받은 적 없는 메시지에 대한 위조다.

두 공격 모두 $m$ 을 그대로 지수에 넣는다는 점을 파고든다. 아래에서 도입할 해시가 이 통로를 막는다. 다만 해시를 붙인 것만으로 안전성이 증명되지는 않아, 실제 표준은 난수를 섞은 인코딩을 함께 쓰는 RSA-PSS다. 이 글의 식들은 구조를 보이기 위한 형태이며 그대로 구현하면 안 된다.

인증기관 (Certificate Authority)

RSA 서명에는 한 가지 취약점이 있다. Bob이 사용하는 공개키 $e$ 가 정말 Alice의 것인가?

공격자 Eve가 자신의 공개키 $e'$ 를 Alice의 것인 척 배포하면, Bob은 Eve의 서명을 Alice의 서명으로 착각할 수 있다.

이를 해결하는 것이 인증기관(CA, Certificate Authority) 이다.

Alice가 자신의 공개키와 신원 정보를 CA에 제출한다.
CA는 이를 검토한 뒤 (공개키 + 신원 정보)에 CA 자신의 서명을 붙인다. 이것이 인증서(Certificate) 다.
Bob은 CA의 서명을 검증해 Alice의 공개키가 진짜임을 확인한다.

CA는 “누구나 신뢰하는 기관”이라는 전제 위에 작동한다. 공인인증서와 HTTPS 인증서가 이 구조로 동작한다.

ElGamal 서명

RSA가 소인수분해 어려움에 기반한다면, ElGamal 서명은 이산 대수 문제(DLP)에 기반한다.

설정: 공개 파라미터 $p$ , $g$ . Alice의 비밀키 $a$ , 공개키 $y = g^a \bmod p$ .

서명 생성 (Alice, 비밀키 $a$ 사용):

임의의 $k$ 를 선택한다 ( $\gcd(k, p-1) = 1$ )
$r = g^k \bmod p$
$s = (m - ar) \cdot k^{-1} \bmod (p-1)$

서명: $(r, s)$

서명 검증 (Bob, Alice의 공개키 $y$ 사용):

g^m \equiv y^r \cdot r^s \pmod{p}

검증이 성립하는 이유:

y^r \cdot r^s = (g^a)^r \cdot (g^k)^s = g^{ar} \cdot g^{k \cdot (m-ar)k^{-1}} = g^{ar} \cdot g^{m-ar} = g^m \pmod{p}

$k$ 와 $k^{-1}$ 이 상쇄되고, $a$ 는 공개키 $y = g^a$ 형태로만 검증에 사용된다. 비밀키 $a$ 없이는 서명을 생성할 수 없고, 공개키 $y$ 만으로 검증할 수 있다.

쉽게 말하면

ElGamal 서명의 검증 수식 $g^m = y^r \cdot r^s$ 가 성립하는 이유는, 서명 과정에서 임시 키 $k$ 와 비밀키 $a$ 를 교묘하게 섞어 넣었기 때문이다. 검증 시 이들이 정확히 상쇄되어 $g^m$ 이 복원된다. 비밀키 $a$ 를 모르면 이 상쇄가 일어나는 서명 $(r, s)$ 를 만들 수 없다.

이 방식에서 갈라져 나온 표준이 DSS(Digital Signature Standard) 의 DSA다. 다만 위 식을 그대로 표준화한 것은 아니고, ElGamal 계열의 변형에 가깝다. 세 군데가 다르다.

$p-1$ 전체가 아니라 그 소수 위수 부분군 $q$ 위에서 계산한다( $q \mid p-1$ ). 그래서 서명이 $2\lvert p \rvert$ 가 아니라 $2\lvert q \rvert$ 비트로 짧다.
$r = (g^k \bmod p) \bmod q$ 처럼 두 번 줄인다.
서명식이 $s = k^{-1}\bigl(H(m) + ar\bigr) \bmod q$ 로, 부호가 뺄셈이 아닌 덧셈이고 $m$ 자리에 해시 $H(m)$ 이 들어간다.

서명 크기 문제: 암호학적 해시

$s = m^d \bmod n$ 은 $n$ 으로 나눈 나머지이므로 언제나 모듈러스보다 작다. 2048비트 RSA라면 서명 하나는 늘 256바이트다. 그러니 “메시지가 크면 서명도 커진다”는 말은 틀렸다. 진짜 문제는 다른 데 있다.

$m$ 을 지수에 넣으려면 $m$ 이 $0$ 부터 $n-1$ 까지의 수 하나여야 한다. $m$ 이 100MB라면 $n$ 보다 한참 크므로 애초에 한 덩어리로 넣을 수가 없다. 방법은 $m$ 을 $\lfloor \log_2 n \rfloor$ 비트짜리 블록으로 쪼개 각각 서명하는 것인데, 그러면 두 가지가 한꺼번에 무너진다.

서명 총량이 메시지에 비례한다. 블록이 수십만 개면 서명도 수십만 개다.
블록마다 서명이 따로 유효하다. 공격자가 블록 순서를 바꾸거나 일부를 지우거나 복제해도 각 서명은 그대로 검증을 통과한다. 문서 전체에 대한 결속이 사라진다.

여기에 블록마다 모듈러 지수연산을 한 번씩 돌아야 하는 속도 문제까지 겹친다.

해결책은 암호학적 해시 함수(Cryptographic Hash Function) 다.

h = \text{SHA}(m)

SHA는 임의 길이의 메시지 $m$ 을 고정 크기(SHA-256이면 256비트)의 해시값 $h$ 로 변환한다. 서명은 $m$ 대신 $h$ 에 생성한다.

s = h^d \bmod n = \text{SHA}(m)^d \bmod n

해시를 거친 서명. Alice는 수 MB짜리 평문 m을 SHA로 256비트 해시 h로 줄인 뒤 비밀키로 서명하고, Bob은 받은 m을 같은 함수로 해시해 공개키로 복원한 값과 비교한다. 메시지 길이와 무관하게 지수에 들어가는 값이 하나로 고정되고, 서명이 h를 통해 m에 묶인다

여기서 해시에 요구되는 성질은 셋이고, 막는 공격이 각각 다르다. 하나로 뭉뚱그리면 어느 성질이 어느 위협을 담당하는지 잃는다.

성질	요구	막는 공격
원상 저항성	$h$ 가 주어졌을 때 $H(m) = h$ 인 $m$ 을 찾을 수 없다	위에서 본 “서명을 먼저 고르기”. $s$ 를 아무거나 잡아 $h = s^e$ 를 얻어도, 그 $h$ 로 가는 $m$ 을 만들 수 없다
제2원상 저항성	$m_1$ 이 주어졌을 때 $H(m_2) = H(m_1)$ 인 $m_2 \neq m_1$ 을 찾을 수 없다	메시지 결속. 이미 서명된 $m_1$ 의 서명을 떼어 다른 문서에 옮겨 붙이는 것
충돌 저항성	$H(m_1) = H(m_2)$ 인 아무 쌍이나 찾을 수 없다	서명자를 속여 $m_1$ 에 서명받은 뒤 그 서명을 $m_2$ 의 것이라 주장하는 것. 공격자가 두 메시지를 모두 고를 수 있다는 점이 위와 다르다

메시지 결속을 직접 담당하는 것은 제2원상 저항성이다. 충돌 저항성은 그보다 강한 요구이고, 서명자 자신이 속는 상황을 막는다. 뒤에서 볼 생일 역설이 깎아내리는 것도 이 세 번째다.

Birthday Paradox와 해시 길이

해시가 $n$ 비트라면, 특정 해시값 $h$ 와 충돌하는 메시지를 찾으려면 평균 $2^n$ 번의 시도가 필요하다.

그런데 특정 값이 아닌 임의의 충돌 쌍 $m_1, m_2$ 를 찾는 것은 훨씬 쉽다. 생일 역설(Birthday Paradox)에 의해 약 $2^{n/2}$ 번이면 충분하다.

365일 중 생일이 같은 두 사람을 찾으려면 23명이면 충분하다 ( $\approx \sqrt{365}$ ). 특정인과 생일이 같으려면 253명이 필요하다.

따라서 SHA-256(256비트)의 충돌 저항성은 사실상 $2^{128}$ 이다. 이를 감안해 SHA-256 이상을 사용하는 것이 현재 권장 기준이다.

역할을 나눠 조합하기: AES + RSA + SHA

보안 통신은 한 알고리즘으로 끝나지 않고 기밀성·인증·무결성을 각각 맡는 조각을 조합한다. 그 역할 분담을 보이기 위한 뼈대를 아래에 세운다.

이 절은 교육용 뼈대다

아래 패킷은 세 알고리즘이 각자 무엇을 담당하는지 드러내는 것이 목적이고, 그대로 쓰면 안전하지 않다. 실제 프로토콜이 여기에 더하는 것들을 미리 적어 둔다.

AEAD. AES를 그냥 쓰면 암호문을 고쳐도 티가 나지 않는다. 실무는 GCM 같은 인증 암호 모드로 논스와 인증 태그를 함께 쓴다.
패딩. $k^{e_b}$ 처럼 raw RSA로 키를 실어 보내면 여러 공격에 열린다. RSA는 OAEP, 서명은 PSS 인코딩을 쓴다.
트랜스크립트 결속. 아래 서명은 $m$ 만 덮는다. $C$ 나 $k'$ 를 바꿔치기해도 서명은 그대로 통과한다. 실제 프로토콜은 주고받은 내용 전체에 서명한다.
신원 확인. 공개키가 상대의 것인지는 인증서 검증으로 확인해야 한다. 앞 절의 CA가 그 자리다.
다운그레이드 방어. 약한 알고리즘으로 끌어내리려는 시도를 막는 장치가 따로 필요하다.

더해서 오늘날 TLS 1.3은 RSA 키 전송을 아예 없앴다. 키 교환은 (EC)DHE로 하고 RSA는 인증서 서명 쪽에 남는다. 세션 키가 장기 키에서 독립해야 나중에 장기 키가 털려도 과거 통신이 열리지 않기 때문이다.

설정:

Alice: RSA 키쌍 $(e_a, d_a)$ , 모듈러스 $n_A$
Bob: RSA 키쌍 $(e_b, d_b)$ , 모듈러스 $n_B$
대칭키 $k$ : Alice가 임의 생성

AES와 RSA와 SHA의 역할 분담 뼈대. Alice는 평문을 AES로 암호화하고 대칭키를 Bob의 공개키로 감싸고 해시에 자기 비밀키로 서명해 세 조각을 보내며, Bob은 키를 풀고 평문을 복원한 뒤 해시를 비교한다. 기밀성은 AES, 키 전달과 인증은 RSA, 무결성은 SHA가 맡는다. 교육용 뼈대이며 실제 프로토콜은 아니다

Alice → Bob 전송:

임의의 대칭키 $k$ 생성
$C = \text{AES}_k(m)$ : 평문을 AES로 암호화 (속도)
$k' = k^{e_b} \bmod n_B$ : 대칭키를 Bob의 공개키로 암호화
$h = \text{SHA}(m)$ , $s = h^{d_a} \bmod n_A$ : 해시에 Alice의 서명 생성
전송 패킷: $(C,\ k',\ s)$

Bob의 복호화 및 검증:

$k = k'^{d_b} \bmod n_B$ : RSA로 대칭키 복원
$m = \text{AES}_k^{-1}(C)$ : AES로 평문 복원
$h = s^{e_a} \bmod n_A$ : Alice의 공개키로 서명 복원
$h' = \text{SHA}(m)$ , $h' \stackrel{?}{=} h$ : 직접 해시와 비교

각 구성 요소의 역할:

알고리즘	역할	이유
AES	메시지 암호화	빠르고 대용량 처리 가능
RSA	키 전달 + 서명	AES 키를 안전하게 공유, 신원 인증
SHA	해시	지수에 들어갈 값을 하나로 고정, 메시지 결속

TLS·PGP 같은 실제 프로토콜도 이 역할 분담을 공유한다. 빠른 대칭 암호가 본문을 맡고, 공개키가 키 합의와 신원을 맡고, 해시가 무결성을 맡는다. 다만 위 상자에 적은 것들이 모두 채워져야 그 자리에 설 수 있다.

핵심 정리

RSA 서명은 복호화 키( $d$ )로 서명하고 암호화 키( $e$ )로 검증한다. $ed \equiv 1 \pmod{\varphi(n)}$ 에서 $m^{ed} = m$ 이 성립하기 때문이다. 다만 이것은 정확성일 뿐이다. 교과서 RSA는 서명을 먼저 고르는 방식과 곱셈 성질로 위조되므로, 실제 표준은 난수 인코딩을 붙인 RSA-PSS다.
ElGamal 서명은 DLP에 기반하며, $g^m \equiv y^r \cdot r^s \pmod{p}$ 로 검증한다. 비밀키 $a$ 없이는 유효한 $(r, s)$ 를 만들 수 없다. 표준인 DSA는 이 계열의 변형으로, 소수 위수 부분군 $q$ 위에서 계산하고 서명식의 부호와 해시 사용이 다르다.
서명 $s = m^d \bmod n$ 은 언제나 모듈러스 크기다. 해시가 푸는 문제는 서명 길이가 아니라, $m$ 이 $n$ 보다 크면 한 덩어리로 넣을 수 없어 블록으로 쪼개야 하고 그러면 블록 재배열에 열린다는 점이다. 메시지 결속을 직접 담당하는 성질은 제2원상 저항성이다.
Birthday Paradox에 의해 $n$ 비트 해시의 실질적 충돌 저항성은 $2^{n/2}$ 이다. SHA-256의 실질 안전성은 $2^{128}$ 이다.
보안 통신은 AES(기밀성) + 공개키(키 합의·인증) + SHA(무결성)로 역할을 나눈다. 이 글의 패킷은 그 분담을 보이는 뼈대이며, 실제 프로토콜은 AEAD·패딩·트랜스크립트 결속·인증서 검증·다운그레이드 방어를 더한다. TLS 1.3은 RSA 키 전송을 아예 없애고 (EC)DHE로 키를 합의한다.

다음 포스트

Cryptographic Hashing, 암호학적 해시 함수. SHA의 내부 구조(Merkle-Damgård), 일방향성·충돌 저항성의 수학, Birthday Paradox가 해시 길이에 미치는 영향, 그리고 MD5/SHA-1이 왜 더 이상 안전하지 않은지까지 다룬다.