ECDSA 서명

P-256 타원 곡선에서 ECDH와 ECDSA의 개념을 다뤘다. 이 포스트는 ECDSA 서명의 실무적인 부분을 다룬다. 서명 바이트가 매번 길이가 다른 이유, nonce를 한 번이라도 재사용하면 비밀키가 유출되는 이유, mbedTLS에서 서명을 만들고 검증하는 실제 코드를 정리한다.

서명 생성

입력: 비밀키 d, 메시지 m, 곡선 차수 n, 생성점 G

1. z = SHA-256(m)                         해시 (곡선 비트 길이로 truncate)
2. k = random ∈ [1, n-1]                  nonce (한 번만 사용해야 한다)
3. R = k × G = (x_R, y_R)                곡선 위의 점
4. r = x_R mod n                          서명의 첫 번째 값
5. s = k⁻¹ × (z + r × d) mod n           서명의 두 번째 값
6. 서명 = (r, s)

r이 0이면 k를 다시 뽑는다. s가 0이어도 다시 뽑는다.

핵심은 5단계의 s = k⁻¹(z + rd) mod n이다. nonce k가 비밀키 d를 감추는 역할을 한다. k를 모르면 d를 역산할 수 없다.

서명 검증

입력: 공개키 Q, 메시지 m, 서명 (r, s)

1. z = SHA-256(m)
2. w = s⁻¹ mod n
3. u₁ = z × w mod n
4. u₂ = r × w mod n
5. P = u₁ × G + u₂ × Q
6. P의 x좌표 mod n이 r과 같으면 유효

왜 성립하는가

서명 생성에서:

s = k⁻¹(z + rd)  →  k = s⁻¹(z + rd) = s⁻¹z + s⁻¹rd = u₁ + u₂d

따라서:

R = k × G = (u₁ + u₂d) × G = u₁G + u₂(dG) = u₁G + u₂Q

검증 5단계에서 계산하는 P = u₁G + u₂Q가 원래의 R과 같으므로, x좌표가 r과 일치한다.

검증에는 비밀키 d가 필요 없다. 공개키 Q = dG만으로 충분하다.

DER 인코딩

왜 서명 길이가 매번 다른가

mbedTLS, OpenSSL 등 대부분의 라이브러리는 ECDSA 서명을 ASN.1 DER 포맷으로 출력한다. P-256 서명의 raw 크기는 64바이트(r 32 + s 32)로 고정이지만, DER 인코딩 후에는 70~73바이트로 변한다.

바이트 구조

0x30 [전체길이] 0x02 [r길이] [r바이트] 0x02 [s길이] [s바이트]
│                │                      │
SEQUENCE 태그    INTEGER 태그 (r)       INTEGER 태그 (s)

길이가 변하는 이유

DER의 INTEGER는 부호 있는 값이다. r과 s는 항상 양수인데, 최상위 비트가 1이면 음수로 해석된다. 이를 방지하기 위해 0x00을 앞에 패딩한다.

r = 0x8A3F...  → DER: 0x02 0x21 0x00 0x8A 0x3F ...  (33바이트)
r = 0x2B7C...  → DER: 0x02 0x20 0x2B 0x7C ...        (32바이트)

최상위 바이트가 0x80 이상이면 패딩이 붙는다. 확률적으로 약 50%다.

P-256 DER 서명 크기 분포

r 패딩	s 패딩	DER 크기	확률
없음	없음	70바이트	~25%
있음	없음 또는 반대	71바이트	~50%
있음	있음	72바이트	~25%

프레이밍 오버헤드: SEQUENCE 태그(1) + 전체길이(1) + INTEGER 태그(1) + r길이(1) + INTEGER 태그(1) + s길이(1) = 6바이트.

DER vs Raw 포맷

포맷	크기	사용처
DER (ASN.1)	70~73바이트	TLS, X.509, mbedTLS, OpenSSL
Raw (r \|\| s)	64바이트 고정	JWT/JWS, WebAuthn, BLE GATT

BLE 같은 대역폭이 좁은 환경에서는 raw 포맷이 유리하다. mbedTLS가 출력하는 DER을 직접 파싱해서 r, s를 추출하거나, raw 서명을 DER로 감싸서 mbedTLS에 넘겨야 하는 상황이 자주 생긴다.

Nonce 재사용 공격

같은 k로 두 메시지에 서명하면

메시지 m₁, m₂에 같은 nonce k를 사용하면 두 서명 (r, s₁), (r, s₂)가 나온다. r이 같은 이유는 R = kG가 동일하기 때문이다.

s₁ = k⁻¹(z₁ + rd)
s₂ = k⁻¹(z₂ + rd)

빼면:

s₁ - s₂ = k⁻¹(z₁ - z₂)

k 복원:

k = (z₁ - z₂) / (s₁ - s₂) mod n

k가 나오면 비밀키 d도 바로 나온다:

d = (s₁k - z₁) / r mod n

한 번의 nonce 재사용으로 비밀키가 완전히 유출된다.

Sony PS3 사례 (2010)

Sony는 PS3 펌웨어 서명에 ECDSA를 사용했는데, nonce k를 상수로 고정했다. 2010년 27C3 컨퍼런스에서 fail0verflow 팀이 이를 발견하고, 위 공식으로 Sony의 비밀키를 역산했다. 이후 누구나 자체 서명한 소프트웨어를 PS3에서 실행할 수 있게 됐다.

nonce가 “충분히 랜덤”이 아니라 완전한 랜덤이어야 하는 이유다. 부분적 nonce 노출(몇 비트만 유출)도 lattice attack으로 비밀키를 복원할 수 있다.

RFC 6979 — 결정적 Nonce

RNG(난수 생성기)에 의존하지 않고 nonce를 만드는 방법이다. 비밀키와 메시지 해시를 HMAC-DRBG에 넣어서 결정적으로 k를 생성한다.

동작 원리

입력: 비밀키 x, 메시지 해시 h

1. V = 0x01 × hlen          (1로 초기화)
2. K = 0x00 × hlen          (0으로 초기화)
3. K = HMAC_K(V || 0x00 || x || h)
4. V = HMAC_K(V)
5. K = HMAC_K(V || 0x01 || x || h)
6. V = HMAC_K(V)
7. k후보 = HMAC_K(V)에서 비트 추출
8. k가 [1, n-1] 범위이고 유효한 r을 생성하면 사용
   아니면 K = HMAC_K(V || 0x00), V = HMAC_K(V) 후 7로 돌아감

특성

같은 키 + 같은 메시지 → 항상 같은 서명. 재현 가능하고 테스트 가능하다
RNG가 필요 없다. 하드웨어 TRNG가 없는 환경에서도 안전하다
기존 검증 코드와 완전히 호환된다. 검증 측은 k가 어떻게 생성되었는지 모른다

주의: Fault Injection

결정적 nonce는 같은 입력에 항상 같은 중간 값을 생성한다. 전압 글리치 같은 fault injection 공격에 노출된 환경(임베디드 디바이스)에서는 공격자가 차이를 분석할 수 있다.

Hedged signature가 이를 보완한다: k = RFC6979(x, h, random_noise). 결정적 생성에 랜덤 노이즈를 섞어서, RNG가 깨져도 RFC 6979의 안전성은 유지하면서 fault attack에도 대응한다.

서명 가변성 (Malleability)

유효한 서명 (r, s)가 있을 때, (r, n - s)도 수학적으로 유효하다. 서명 방정식에서 s와 -s mod n이 모두 검증을 통과하기 때문이다.

왜 문제인가

서명의 바이트 표현이 달라지므로 해시가 변한다. 서명을 포함한 데이터의 해시로 식별하는 시스템(예: Bitcoin 트랜잭션 ID)에서 같은 트랜잭션이 다른 ID를 가질 수 있다. Bitcoin에서 실제로 거래소 출금 공격에 악용되었다 (Transaction Malleability, 2014).

Low-S 정규화

해결: s > n/2이면 s = n - s로 대체한다. 항상 작은 쪽의 s를 사용하면 정규 형태가 하나로 고정된다.

/* s가 n/2보다 크면 정규화 */
if (mbedtls_mpi_cmp_mpi(&s, &half_n) > 0) {
    mbedtls_mpi_sub_mpi(&s, &n, &s);
}

Bitcoin(BIP 62/146)에서는 low-S가 합의 규칙이다. 일반 ECDSA에서는 선택사항이지만, 프로토콜에서 서명 바이트의 유일성이 필요하면 적용해야 한다.

mbedTLS 코드 패턴

서명 생성

#include "mbedtls/ecdsa.h"
#include "mbedtls/sha256.h"

mbedtls_ecdsa_context ctx;
mbedtls_ecdsa_init(&ctx);

/* 키 로드 (P-256) */
mbedtls_ecp_group_load(&ctx.grp, MBEDTLS_ECP_DP_SECP256R1);
mbedtls_mpi_read_binary(&ctx.d, privkey_bytes, 32);

/* 해시 */
uint8_t hash[32];
mbedtls_sha256(message, msg_len, hash, 0);

/* 서명 (DER 출력) */
uint8_t sig[MBEDTLS_ECDSA_MAX_LEN];  /* 최대 ~73바이트 */
size_t sig_len;
mbedtls_ecdsa_write_signature(&ctx, MBEDTLS_MD_SHA256,
    hash, 32, sig, sizeof(sig), &sig_len,
    mbedtls_ctr_drbg_random, &ctr_drbg);
/* MBEDTLS_ECDSA_DETERMINISTIC 정의 시 RFC 6979 사용, RNG 무시 */

mbedtls_ecdsa_write_signature는 해시 → 서명 → DER 인코딩을 한 번에 처리한다. MBEDTLS_ECDSA_DETERMINISTIC이 정의되어 있으면 내부적으로 RFC 6979를 사용하고, RNG 콜백은 hedging용으로만 사용된다.

서명 검증

mbedtls_ecdsa_context ctx;
mbedtls_ecdsa_init(&ctx);
mbedtls_ecp_group_load(&ctx.grp, MBEDTLS_ECP_DP_SECP256R1);

/* 공개키 로드 (비압축: 0x04 || x || y) */
mbedtls_ecp_point_read_binary(&ctx.grp, &ctx.Q, pubkey_65, 65);

uint8_t hash[32];
mbedtls_sha256(message, msg_len, hash, 0);

/* 검증 (DER 서명 입력) */
int ret = mbedtls_ecdsa_read_signature(&ctx,
    hash, 32, sig_der, sig_der_len);
/* ret == 0이면 유효 */

DER ↔ Raw 변환

BLE GATT처럼 raw 포맷(64바이트)을 사용하는 경우, DER과 변환해야 한다.

/* Raw(64) → DER: r, s를 MPI로 읽어서 DER 작성 */
int raw_to_der(const uint8_t raw[64], uint8_t *der, size_t *der_len)
{
    mbedtls_mpi r, s;
    mbedtls_mpi_init(&r);
    mbedtls_mpi_init(&s);
    mbedtls_mpi_read_binary(&r, raw, 32);
    mbedtls_mpi_read_binary(&s, raw + 32, 32);

    int ret = mbedtls_ecdsa_signature_to_asn1(&r, &s, der, der_len);
    mbedtls_mpi_free(&r);
    mbedtls_mpi_free(&s);
    return ret;
}

/* DER → Raw(64): DER 파싱 후 r, s를 고정 32바이트로 출력 */
int der_to_raw(const uint8_t *der, size_t der_len, uint8_t raw[64])
{
    mbedtls_mpi r, s;
    mbedtls_mpi_init(&r);
    mbedtls_mpi_init(&s);

    /* DER 파싱 */
    unsigned char *p = (unsigned char *)der;
    const unsigned char *end = der + der_len;
    size_t len;
    mbedtls_asn1_get_tag(&p, end, &len,
        MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE);
    mbedtls_asn1_get_mpi(&p, end, &r);
    mbedtls_asn1_get_mpi(&p, end, &s);

    /* 고정 32바이트로 출력 (좌측 0 패딩) */
    memset(raw, 0, 64);
    mbedtls_mpi_write_binary(&r, raw, 32);
    mbedtls_mpi_write_binary(&s, raw + 32, 32);

    mbedtls_mpi_free(&r);
    mbedtls_mpi_free(&s);
    return 0;
}

메모

ECDSA vs EdDSA: EdDSA(Ed25519)는 nonce를 비밀키+메시지에서 결정적으로 생성하므로 nonce 재사용 문제가 구조적으로 없다. 새 프로토콜이면 EdDSA가 더 안전하다. BLE, TLS, CCC Digital Key 등 P-256이 스펙에 고정된 환경에서는 ECDSA를 써야 한다
P-256 vs secp256k1: P-256은 NIST/FIPS 환경(TLS, 정부, 자동차). secp256k1은 y² = x³ + 7로 방정식이 단순하고, 파라미터 생성이 투명해서 Bitcoin/Ethereum이 채택했다. 보안 강도는 동일(128비트)
서명에 메시지 자체가 아니라 해시를 넣는 이유: 곡선 연산은 느리다. 긴 메시지를 직접 처리하면 비용이 메시지 길이에 비례한다. SHA-256으로 32바이트로 압축하면 곡선 연산은 항상 고정 비용이다
해시 truncation: 해시 출력이 곡선 차수 n보다 길면 왼쪽(상위) 비트만 잘라 쓴다. P-256에서 SHA-256은 출력이 256비트이고 n도 256비트이므로 truncation이 필요 없다. SHA-384나 SHA-512을 쓸 때만 해당된다
mbedTLS의 restartable 연산: mbedtls_ecdsa_read_signature_restartable()로 검증을 여러 타임슬라이스에 나눠 실행할 수 있다. BLE 같은 실시간 시스템에서 수백 ms 블로킹을 피할 때 유용하다