Ed25519 Deep Dive

Original presentation by Jinwoo Lee on Dec 3, 2025

타원곡선 (Elliptic Curve)

더 자세한 내용은 Threshold Signature Scheme 초반부를 참고.

위수(Order)

1. 전체 그룹 위수 ($n$): 곡선 존재하는 모든 점들의 총 개수

   $$n = 8 \cdot q$$
   • 여기서 $8$은 cofactor라고 부름.

2. 순환 부분군 위수 ($q$): 실제 서명 및 키 파생 연산에 사용되는 부분군(subgroup)의 위수

   $$q = 2^{252} + 27742317777372353535851937790883648493$$

유한체 (Finite Field)

25519의 의미

Ed25519라는 이름은 유한체를 정의하는 소수 $p$에서 유래함.

공개키 압축

$x$좌표값이 255비트보다 살짝 작은 값이기 때문에 Public Key 압축에 있어 이점을 가짐.

HD Wallet in Solana

솔라나의 BIP-44 표준 Path

• 501 coin type을 사용하고 있음. 다른 SVM(Solana Virtual Machine) 체인의 경우 달라질 수 있으므로 리서치 필요.

비밀키 활용 (Secret Key Usage)

서명 시 secp256k1 / secp256r1 (NIST-256)과 많은 차이점이 존재함.

1. 초기 시드 (Initial Seed)

• 무작위의 32바이트 난수를 사용함.
• secp256k1과 달리 curve order보다 작게 설정해야 하는 제약이 없음.

2. Expanded Secret Key

초기 시드의 SHA-512 해시값을 Expanded Secret Key로 사용함.

• 총 64바이트
• 상위 32bytes와 하위 32bytes의 용도가 다름.

2-1. 상위 32bytes ($H_{high}$)

디지털 서명에 필요한 nonce ($r$) 값을 만들 때 사용됨.

2-2. 하위 32bytes ($H_{low}$) = 비밀키 스칼라 $x$

• 공개키를 만들기 위한 Private Key로 사용됨.
• Curve order보다 작게 만들기 위해, 그리고 보안상의 이유(Timing Attack 방어 등)로 비트 조작(Bit Clamping) 과정이 들어감:
  • Cofactor(8) Clearing: 마지막 비트 3개를 0으로 만듦 $\rightarrow$ 8의 배수로 만들어 메인 subgroup에 위치시킴.
  • Range Clamping: 최상위 비트를 0으로, 두 번째 상위 비트를 1로 설정.

EdDSA - Schnorr 서명 기반

1. 서명 생성 ($\sigma = (\text{R} \Vert s)$)

1-1. 임시 비밀값 $r$ 및 점 $R$ 계산 (Nonce Generation)

임시 비밀값 $r$은 $H_{high}$와 메시지 해시 $M$으로부터 결정론적(Deterministic)으로 생성됨. (RFC-6979와 유사)

• $r$ 계산 (mod $q$):

  $$r = \text{SHA-512}(H_{high} \Vert M) \pmod q$$

• $R$ 계산 (곡선 위의 점):

  $$R = r \cdot G$$

  (점 $R$의 인코딩 값 $\text{R}$은 서명의 첫 32바이트가 됨.)

1-2. Challenge 값 $k$ 계산

$\text{R}$, 공개키 $P$, 메시지 $M$을 모두 해시하여 도전 값 $k$를 계산함.

• $k$ 계산 (mod $q$): $$k = \text{SHA-512}(\text{R} \Vert P \Vert M) \pmod q$$

1-3. 최종 서명 스칼라 $s$ 계산

$r$, $k$, $x$ (비밀키 $H_{low}$)를 사용하여 최종 서명 스칼라 $s$를 계산함. 이는 사실상 Schnorr Signature 구조임.

• $s$ 계산 (mod $q$): $$s = (r + k \cdot x) \pmod q$$

1-4. 최종 서명 $\sigma$

서명 $\sigma$는 $\text{R}$ (32bytes)과 $s$ (32bytes)를 순서대로 연결한 64바이트임.

2. 서명 검증 (Verification)

검증자는 서명 $\sigma = (\text{R} \Vert s)$, 메시지 $M$, 그리고 공개키 $P$를 사용함.

2-1. Challenge 값 $k$ 재계산

서명 생성 시 사용된 것과 동일한 방식으로 $k$를 재계산함.

2-2. 검증 공식 확인

다음 타원 곡선 방정식이 성립하는지 확인함.

• 항목 설명:
  • $s \cdot G$: 서명 스칼라 $s$에 기준점 $G$를 곱한 값
  • $R$: 서명에서 추출한 임시 비밀점
  • $k \cdot P$: 재계산한 도전 값 $k$에 공개키 $P$를 곱한 값

Note: secp256k1 / secp256r1과 달리(e.g., Ethereum’s ecrecover), Ed25519 표준은 일반적으로 Public Key Recovery 인터페이스를 지원하지 않고, “성공/실패” 검증 방식임.

Public Key 압축 및 서명 R값 압축

• 기본적으로 Public Key와 서명 $R$ 모두 타원곡선 위의 점이므로 $(x, y)$ 좌표가 필요하여 64bytes ($32+32$)여야 함.
• 하지만 타원곡선 방정식은 $y^2 = x^3 + ax + b$ 형태의 $x$축 대칭성을 가지므로, $x$좌표와 $y$좌표의 부호(Parity)만 있으면 점을 완벽히 특정할 수 있음.
• secp256k1의 경우:
  • $y$좌표의 부호(Parity)를 나타내는 1바이트 prefix(0x02 or 0x03)를 붙여 33bytes를 Compressed Public Key로 사용함.
• Ed25519의 경우:
  • $y$좌표를 기본으로 저장함.
  • $x$좌표는 항상 양수이며, $x$의 범위가 $2^{255}-19$ (255비트)보다 작기 때문에, 마지막 남는 1비트(MSB)에 $x$좌표의 짝수/홀수 여부(Parity)를 저장할 수 있음.
  • 따라서 32바이트 안에 점 정보를 완벽히 압축할 수 있음.

Ed25519 vs X25519

• Ed25519: 디지털 서명(Signing) 생성 및 검증에 사용됨. (Edwards Curve)
• X25519: 키 교환(Key Exchange, ECDH)을 위해 사용됨. (Montgomery Curve)
  • Ed25519 키를 수학적으로 변환(Birational Equivalence)하여 X25519 키로 사용할 수 있음.
  • 몽고메리 좌표계(Montgomery Ladder)를 사용하여 $x$좌표만으로 효율적인 연산이 가능하며, Timing Attack 등 Side Channel Attack에 강력한 저항성을 가짐.