Comparing Signature Schemes — ECDSA, EdDSA, Schnorr, BLS, and Forgery Pitfalls TODO

Algorithms · Day 85 / 100 · F. Cryptography & ZK (Day 82-96)

Concept

ECDSA is an elliptic-curve signature scheme that requires a secret random nonce per signature; if that nonce is reused or biased, the private key can be recovered from just two signatures. It also has signature malleability — both (r, s) and (r, -s mod n) are valid — so Ethereum constrains s to the lower half of the range; in exchange, the property that lets you recover the public key from a signature is what makes the ecrecover pattern possible. EdDSA, a Schnorr-family scheme, derives the nonce deterministically from the private key and the message hash, structurally eliminating nonce-reuse incidents — but implementations vary in cofactor handling and encoding-normalization checks, creating a consensus risk where one library accepts a signature that another rejects. Schnorr signatures' linear structure lets multiple keys and signatures be aggregated into one; BLS uses pairings to make signatures short and lets an unlimited number of them aggregate, which suits collecting a validator set's signatures, though verification is comparatively heavy. A common trap across aggregate schemes is the rogue-key attack, where an attacker crafts their own key relative to someone else's public key — defending against it needs proof of possession or a MuSig-style commitment procedure.

Subtle differences in signature-verification code translate directly into stolen funds or a consensus split between nodes, and nonce handling, malleability, and rogue-key attacks have each caused real incidents repeatedly. Choosing a scheme is choosing which pitfall you're taking on.

Code & Formula

# 서명 스킴 비교 — ECDSA의 nonce 재사용이 개인키를 복원시키는 함정을 토이 곡선 위에서 재현한다.
# 실제 secp256k1 대신 작은 소수 곡선으로 개념만 시연 (교육용, 프로덕션 서명엔 검증된 라이브러리 사용).

# 아주 작은 유한체 위의 "장난감" 타원곡선 대신, ECDSA 서명 수식만 정수 mod n 산술로 재현한다.
# 서명 공식: s = k^-1 * (h + r * priv_key) mod n  (r 은 nonce k 로부터 유도된 값이라고 가정)

n = 1000000007  # 그룹 위수 역할을 하는 소수 (토이 값)
priv_key = 123456789 % n

def sign(h, k, r):
    """h: 메시지 해시, k: nonce, r: nonce로부터 나온 값(실제론 k*G의 x좌표)"""
    k_inv = pow(k, -1, n)
    s = (k_inv * (h + r * priv_key)) % n
    return s

def recover_priv_key_from_nonce_reuse(h1, s1, h2, s2, r):
    """같은 nonce r로 서명한 서명 두 개만으로 개인키를 복원한다."""
    # s1 - s2 = k^-1 * (h1 - h2)  =>  k = (h1 - h2) / (s1 - s2)
    k = ((h1 - h2) * pow((s1 - s2) % n, -1, n)) % n
    # s1 = k^-1 * (h1 + r * priv) => priv = (s1 * k - h1) / r
    recovered = ((s1 * k - h1) * pow(r, -1, n)) % n
    return recovered

reused_nonce_k = 999999937
r = (reused_nonce_k * 7) % n  # r 은 k 로부터 결정론적으로 유도된다고 가정 (토이 모델)

h1, h2 = 42, 4242  # 서로 다른 두 메시지의 해시
s1 = sign(h1, reused_nonce_k, r)
s2 = sign(h2, reused_nonce_k, r)  # 실수로 같은 nonce 재사용

recovered_priv = recover_priv_key_from_nonce_reuse(h1, s1, h2, s2, r)
print("actual private key:", priv_key)
print("recovered from two signatures sharing a nonce:", recovered_priv)
print("nonce reuse breaks ECDSA:", recovered_priv == priv_key)

print()
print("EdDSA fixes this by deriving nonce deterministically as hash(priv_key || message),")
print("so the same key+message always reuses the SAME nonce safely (no accidental reuse across msgs).")

docs/code/algorithms/algorithms-85.py

Exercise

Produce two ECDSA signatures over different messages using the same nonce, then actually solve the resulting pair of equations to recover the private key.

Practical Connection

If Verex takes signed off-chain orders and verifies them on-chain, how you handle signature malleability, nonce reuse prevention, and domain separation (EIP-712) is exactly the defense line against order forgery and replay attacks.

Where it lands in Jayverse

• Verex: pick the aggregation scheme explicitly and defend against rogue keys. If the CLOB ever batches many market-maker signatures, BLS pairing-based aggregation suits an open, validator-like set while Schnorr/MuSig fits a small fixed multisig — document which is used and require proof of possession so an attacker can't craft a key relative to someone else's.
• Wallet: test that EIP-712 signature verification rejects the malleable counterpart, not just the canonical one. Since ecrecover relies on ECDSA's public-key-recovery property, add a test that a Wallet-signed payload's (r, -s mod n) variant is rejected, not silently accepted as a second valid signature.

If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.

한국어

서명 스킴 비교 TODO

Algorithms · Day 85 / 100 · F. 암호학·ZK (Day 82–96)

ECDSA·EdDSA·Schnorr·BLS와 위조 함정

개념

ECDSA는 타원곡선 위의 서명 스킴으로 서명마다 비밀 난수 nonce가 필요하고, 이 nonce가 재사용되거나 편향되면 서명 두 개만으로 개인키가 복원된다. 또 (r, s)와 (r, -s mod n)이 모두 유효해 서명 가변성(malleability)이 생기므로 이더리움은 s를 낮은 절반으로 제한하는 규칙을 두었고, 대신 서명에서 공개키를 복원할 수 있다는 특성 덕에 ecrecover 패턴이 가능하다. EdDSA는 Schnorr 계열로 nonce를 비밀키와 메시지의 해시로 결정론적으로 만들어 nonce 재사용 사고를 구조적으로 없앴지만, 구현마다 cofactor 처리나 인코딩 정규성 검사 기준이 달라 같은 서명을 어떤 라이브러리는 받고 어떤 라이브러리는 거부하는 합의 위험이 있다. Schnorr 서명은 선형 구조 덕분에 여러 키와 서명을 하나로 집계할 수 있고, BLS는 페어링을 이용해 서명이 짧고 다수 서명을 무제한 집계할 수 있어 검증자 집합 서명 취합에 적합하지만 검증 연산이 상대적으로 무겁다. 집계형 스킴의 공통 함정은 rogue-key 공격으로, 공격자가 남의 공개키를 반영해 자신의 키를 고르는 것을 막기 위해 소유 증명(proof of possession)이나 MuSig류의 커밋 절차가 필요하다.

서명 검증 코드의 미묘한 차이가 자금 도난이나 노드 간 합의 분기로 직결되고, nonce·malleability·rogue-key는 실제로 반복해서 사고를 낸 지점이다. 스킴을 고르는 일은 곧 어떤 함정을 떠안을지 고르는 일이다.

코드 · 수식

# 서명 스킴 비교 — ECDSA의 nonce 재사용이 개인키를 복원시키는 함정을 토이 곡선 위에서 재현한다.
# 실제 secp256k1 대신 작은 소수 곡선으로 개념만 시연 (교육용, 프로덕션 서명엔 검증된 라이브러리 사용).

# 아주 작은 유한체 위의 "장난감" 타원곡선 대신, ECDSA 서명 수식만 정수 mod n 산술로 재현한다.
# 서명 공식: s = k^-1 * (h + r * priv_key) mod n  (r 은 nonce k 로부터 유도된 값이라고 가정)

n = 1000000007  # 그룹 위수 역할을 하는 소수 (토이 값)
priv_key = 123456789 % n

def sign(h, k, r):
    """h: 메시지 해시, k: nonce, r: nonce로부터 나온 값(실제론 k*G의 x좌표)"""
    k_inv = pow(k, -1, n)
    s = (k_inv * (h + r * priv_key)) % n
    return s

def recover_priv_key_from_nonce_reuse(h1, s1, h2, s2, r):
    """같은 nonce r로 서명한 서명 두 개만으로 개인키를 복원한다."""
    # s1 - s2 = k^-1 * (h1 - h2)  =>  k = (h1 - h2) / (s1 - s2)
    k = ((h1 - h2) * pow((s1 - s2) % n, -1, n)) % n
    # s1 = k^-1 * (h1 + r * priv) => priv = (s1 * k - h1) / r
    recovered = ((s1 * k - h1) * pow(r, -1, n)) % n
    return recovered

reused_nonce_k = 999999937
r = (reused_nonce_k * 7) % n  # r 은 k 로부터 결정론적으로 유도된다고 가정 (토이 모델)

h1, h2 = 42, 4242  # 서로 다른 두 메시지의 해시
s1 = sign(h1, reused_nonce_k, r)
s2 = sign(h2, reused_nonce_k, r)  # 실수로 같은 nonce 재사용

recovered_priv = recover_priv_key_from_nonce_reuse(h1, s1, h2, s2, r)
print("actual private key:", priv_key)
print("recovered from two signatures sharing a nonce:", recovered_priv)
print("nonce reuse breaks ECDSA:", recovered_priv == priv_key)

print()
print("EdDSA fixes this by deriving nonce deterministically as hash(priv_key || message),")
print("so the same key+message always reuses the SAME nonce safely (no accidental reuse across msgs).")

docs/code/algorithms/algorithms-85.py

연습

동일한 nonce로 서로 다른 메시지에 ECDSA 서명 두 개를 만든 뒤 두 서명식을 연립해 개인키를 실제로 복원하는 스크립트를 작성해 보라.

실무 · Verex 연결

Verex에서 오프체인 주문에 서명을 받아 온체인에서 검증한다면 서명 가변성, 재사용 방지 nonce, 도메인 분리(EIP-712)를 어떻게 잡느냐가 곧 주문 위조·재생 공격의 방어선이다.

Jayverse에서의 위치

• Verex: 집계 스킴을 명시적으로 고르고 rogue-key 공격을 방어한다. CLOB이 여러 마켓메이커 서명을 배치로 묶는다면, 페어링 기반 BLS 집계는 개방적이고 검증자 집합 같은 상황에 맞고 Schnorr/MuSig는 소규모 고정 멀티시그에 맞는다. 어느 쪽을 쓰는지 문서화하고, 공격자가 남의 공개키에 상대적으로 키를 조작하지 못하도록 소유 증명을 요구한다.
• Wallet: EIP-712 서명 검증이 정규 형태뿐 아니라 malleable한 변형도 거부하는지 테스트한다. ecrecover는 ECDSA의 공개키 복구 속성에 의존하므로, Wallet이 서명한 페이로드의 (r, -s mod n) 변형이 두 번째 유효 서명으로 조용히 받아들여지지 않고 거부되는지 테스트를 추가한다.

공부한 날 원본 커리큘럼(docs/knowledge/dev-100-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.