note [🌿 다듬는 중 · growing] [⏳ 시점에 민감 · date-sensitive]

같은 메시지에는 같은 서명 — Ed25519가 난수를 믿지 않는 이유

작성 2026-08-23 약 13분 · 각주 9분

목차 12

같은 키로 같은 메시지를 두 번 서명했다. 두 결과는 완전히 같은 64바이트였다.

암호에서 반복은 대개 사고의 냄새다. 초기화 벡터를 재사용하면 평문 사이의 차이가 드러나고, 소금 없이 해시한 비밀번호는 미리 만들어 둔 표로 뚫린다. 그리고 서명할 때 한 번만 쓰고 버려야 하는 비밀값, 곧 nonce를 두 번 쓰면 — 개인키가 그대로 나온다.

그런데 Ed25519에서는 이 반복이 결함이 아니라 설계다.

확인부터 하고 시작한다

Node.js 하나로 확인할 수 있다. 아래 시드는 RFC 8032가 규격 안에 실어 둔 공식 시험 벡터다.

import { createPrivateKey, sign } from 'node:crypto';

// RFC 8032 §7.1 TEST 2의 32바이트 시드를 PKCS#8 껍데기에 넣은 것
const pkcs8 = Buffer.from(
  '302e020100300506032b657004220420' +
  '4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb', 'hex');
const key = createPrivateKey({ key: pkcs8, format: 'der', type: 'pkcs8' });
const msg = Buffer.from('72', 'hex');

console.log(sign(null, msg, key).toString('hex'));
console.log(sign(null, msg, key).toString('hex'));

실행하면 이렇게 나온다.

92a009a9f0d4cab8720e820b5f642540a2b27b5416503f8fb3762223ebdb69da085ac1e43e15996e458f3613d0f11d8c387b2eaeb4302aeeb00d291612bb0c00
92a009a9f0d4cab8720e820b5f642540a2b27b5416503f8fb3762223ebdb69da085ac1e43e15996e458f3613d0f11d8c387b2eaeb4302aeeb00d291612bb0c00

두 줄이 같다. 그리고 이 값은 RFC 8032가 같은 시험 벡터 옆에 적어 둔 서명과 바이트 단위로 같다.¹

규격을 지킨 구현이라면 언어가 무엇이든, 기계가 무엇이든, 오늘이든 십 년 뒤든 같은 값이 나온다. 서명 과정이 기계의 난수 생성기를 전혀 쓰지 않기 때문이다.

Ed25519가 안전한 것은 더 좋은 난수를 만들어서가 아니다. 잘못된 난수를 넣을 입구를 없애서다.

이 글은 그 입구가 왜 그렇게 위험했는지, 그리고 그것을 막으려고 무엇을 포기하고 무엇을 고정했는지를 따라간다. 미리 말해 두면 결론은 알고리즘 자랑이 아니다.

좋은 암호는 더 어려운 문제를 고르는 데서 끝나지 않는다. 구현자가 치명적으로 틀릴 수 있는 선택지 자체를 줄인다.

nonce는 보조 재료가 아니라 두 번째 개인키다

nonce는 number used once, 말 그대로 한 번만 쓰는 수다. 이름이 조심스러운 데는 이유가 있다.

전통적인 ECDSA의 서명식은 이렇다.

s = k^{-1}(z + rd) \bmod n

$d$ 는 장기 개인키, $k$ 는 서명마다 새로 뽑는 비밀 정수, $z$ 는 메시지 해시, $n$ 은 기저점 $G$ 의 위수다. 서명은 $(r, s)$ 이고 $r$ 은 $kG$ 의 $x$ 좌표에서 온다.

$r$ 이 $k$ 만의 함수라는 데 함정이 있다. 같은 $k$ 로 서로 다른 두 메시지를 서명하면 두 서명의 $r$ 이 같아지고, 두 식을 빼면 $d$ 가 사라진다.

s_1 - s_2 = k^{-1}(z_1 - z_2)

k = \frac{z_1 - z_2}{s_1 - s_2}, \qquad d = \frac{s_1 k - z_1}{r}

두 줄이다. 나눗셈은 $\bmod n$ 위의 역원이고, 전부 눈 깜짝할 사이에 끝난다. 필요한 것은 공개된 서명 두 개와 그 메시지 두 개뿐이다.²

이것은 이론적 위험이 아니다. 2010년 12월 fail0verflow는 27C3에서 소니가 플레이스테이션 3의 코드 서명에 $k$ 를 상수로 박아 두었음을 보였다.³ 2013년 8월에는 안드로이드의 SecureRandom이 제대로 초기화되지 않는 결함이 드러났고, 그 위에서 돌던 비트코인 지갑들이 같은 $k$ 를 재사용해 개인키가 털렸다.⁴

더 나쁜 소식은 완전한 재사용이 필요하지도 않다는 것이다. $k$ 의 상위 몇 비트만 새도 여러 서명을 모아 격자 문제로 바꾸면 개인키가 나온다. 그리고 이 문턱은 사반세기 넘게 계속 내려왔다 — 1999년에는 160비트 중 8비트가 필요했고, 2019년에는 $k$ 의 비트 길이만 새어도 서명 500~2,100개로 256비트 키가 복구됐다. 2020년에는 최상위 비트 하나조차 확률적으로만 아는 상태에서 깨는 결과가 나왔다.⁵

nonce는 서명의 부속품이 아니다. 매번 새로 만들어 즉시 버려야 하는 두 번째 개인키다. 그리고 이 두 번째 개인키는 서명하는 기계의 난수 생성기가 만든다 — 암호 설계자가 손댈 수 없는 자리다.

난수를 없앤 것이 아니라 메시지에 묶었다

Ed25519는 이 자리를 아예 들어낸다. 키를 만들 때부터 다르다.

h      = SHA-512(seed)     # seed: 32바이트. 유일한 진짜 비밀
a      = clamp(h[0:32])    # 비밀 스칼라
prefix = h[32:64]          # 밖으로 절대 나가지 않는 32바이트
A      = [a]B              # 공개키

시드 하나를 해시해 앞 절반은 스칼라로 쓰고, 뒤 절반은 쓰지 않고 보관한다. 이 뒤 절반이 나중에 nonce의 씨앗이 된다.

clamp는 몇 비트를 강제로 켜고 끄는 처리다. 하위 3비트를 0으로 만들어 $a$ 를 8의 배수로 맞추고, 최상위 비트를 0으로, 그 아래 비트를 1로 고정한다. 앞의 조작은 여인수 8에서 오는 소부분군 문제를 지우고, 뒤의 조작은 스칼라의 비트 길이를 고정해 곱셈 사다리의 회전 수가 키에 따라 달라지지 않게 한다.⁶

서명은 네 줄이다. $H$ 는 SHA-512, $L$ 은 기저점 $B$ 의 위수다.

r = H(\mathrm{prefix} \mathbin\Vert M) \bmod L, \qquad R = [r]B

k = H(R \mathbin\Vert A \mathbin\Vert M) \bmod L

S = (r + ka) \bmod L

\sigma = R \mathbin\Vert S

32바이트 $R$ 과 32바이트 $S$ 를 이어 붙인 64바이트가 서명이다.⁷

핵심은 첫 줄이다. $r$ 은 난수 생성기에서 오지 않는다. 밖으로 나가지 않는 비밀 prefix와 지금 서명하는 메시지, 이 둘만의 함수다.

그러면 앞 절의 사고가 왜 막히는지 보인다. 위험했던 것은 같은 nonce가 아니라 같은 nonce로 서명된 서로 다른 두 메시지였다. Ed25519에서는 메시지가 다르면 $r$ 이 다르므로 그 조합이 아예 만들어지지 않는다. 메시지가 같으면 $r$ 도 같지만, 그때 나오는 것은 이미 세상에 나간 서명과 똑같은 64바이트다 — 공격자가 새로 얻는 것이 없다.

난수가 사라진 것이 아니다. 서명할 때마다 필요하던 난수가 키를 만들 때 한 번으로 옮겨졌다. 매번 잘해야 하는 일이 한 번만 잘하면 되는 일로 바뀐 것이다.

검증은 한 줄이다

검증자가 확인하는 관계는 이것이다.

[S]B = R + [k]A

$k$ 는 서명의 $R$ , 공개키 $A$ , 메시지 $M$ 만으로 다시 계산되므로 검증자도 구할 수 있다. 그리고 등식은 그냥 풀린다.

[S]B = [r + ka]B = [r]B + [k]\left([a]B\right) = R + [k]A

개인키 $a$ 는 식 어디에도 남지 않는데, 서명자가 $a$ 를 써서 $S$ 를 만들었다는 사실만 확인된다. 서명이 하는 일이 정확히 이것이다.

RFC 8032가 적어 둔 검증식은 여기에 여인수 8이 곱해진 $[8][S]B = [8]R + [8][k]A$ 형태다. 그리고 바로 다음 문장에서, 8을 곱하지 않은 위의 식으로 확인해도 “충분하지만 필수는 아니다”라고 덧붙인다. 두 식을 나란히 둔 이 한 문장이 나중에 문제가 된다.⁸

25519는 마법의 숫자가 아니라 모양이다

이름에 붙은 숫자는 유한체의 크기다.

p = 2^{255} - 19

19가 신비한 것이 아니라 모양이 중요하다. 이 모양 덕분에 나머지 연산이 나눗셈 없이, 자리 옮김과 작은 상수 한 번의 곱셈으로 끝난다.⁹

깊이 보기 — 나눗셈 없이 나머지를 구하는 계산

두 개의 255비트 수를 곱하면 약 510비트가 나오는데, 이것을 $x = x_0 + 2^{255}x_1$ 로 쪼개면 $2^{255} \equiv 19 \pmod p$ 이므로

x \equiv x_0 + 19\,x_1 \pmod p

가 된다. 일반적인 나눗셈 대신 자리 옮김과 5비트짜리 상수 한 번의 곱셈으로 나머지 연산이 끝난다. 19가 하필 19인 이유도 여기 있다 — $2^{255} - s$ 가 소수가 되는 가장 작은 $s$ 가 19다.⁹

빠른 것보다 중요한 것이 하나 더 있다. 이 나머지 연산은 입력값을 보고 갈라지는 분기 없이 짤 수 있다. 이 성질이 다음 절의 주제로 이어진다.

예외가 없는 공식은 보안 기능이다

타원곡선에서 두 점을 더할 때, 바이어슈트라스 표현에서는 경우를 나눠야 한다.

P와 Q가 같은 점인가?      → 배가 공식으로
P가 Q의 역원인가?         → 결과는 항등원
둘 중 하나가 항등원인가?
분모가 0이 되는가?

문제는 스칼라 곱셈에서 이 분기가 비밀 스칼라의 비트에 따라 갈린다는 것이다. 갈라진 가지마다 명령 수와 메모리 접근 패턴이 다르면, 실행 시간이나 캐시 상태가 그 비트를 흘린다.

트위스티드 에드워즈 곡선은 여기가 다르다. 매개변수 $d$ 가 유한체에서 제곱수가 아니면 덧셈 공식이 완전(complete)해진다 — 곡선 위의 어떤 두 점을 넣어도, 같은 점이든 서로의 역원이든 항등원이든, 하나의 공식이 예외 없이 옳은 답을 준다. edwards25519가 쓰는 $d = -121665/121666$ 이 그 조건을 만족한다.¹⁰

경우를 나눌 일이 없으니 분기가 없고, 분기가 없으니 흘릴 것도 없다.

다만 여기서 한 칸 이상 나가면 안 된다. 완전 공식이 자동으로 constant-time을 뜻하지는 않는다. RFC 8032는 자기 예제 코드가 side-channel silent하지 않다고 명시해 둔다.¹¹ 완전 공식이 주는 것은 분기 없이 짜기 쉬운 바닥이지, 짜 준 결과가 아니다. Ed25519 논문이 스스로 내건 조건도 두 개다 — 비밀키에서 배열 첨자로 가는 데이터 흐름이 없을 것, 그리고 비밀키에서 분기 조건으로 가는 데이터 흐름이 없을 것. 완전성은 뒤쪽 조건을 덧셈 공식 안에서 거들 뿐이고, 테이블 조회와 조건부 교환은 따로 손대야 한다.

비슷한 이름 넷은 서로 다른 것이다

앞 절에서 edwards25519라는 이름이 슬쩍 지나갔다. 이 동네의 이름들은 자주 뒤섞이니, 한 번 정리해 두면 나머지가 편하다.

이름	무엇인가	곡선 표현
curve25519	$v^2 = u^3 + 486662u^2 + u$ 라는 곡선	몽고메리
edwards25519	그 곡선의 다른 모델¹²	트위스티드 에드워즈
X25519	키 합의(Diffie–Hellman)에 쓰는 함수¹³	몽고메리 $u$ 좌표
Ed25519	edwards25519와 SHA-512로 고정한 서명 방식	트위스티드 에드워즈

깊이 보기 — 두 곡선 이름은 왜 이렇게 헷갈리는가

앞의 둘은 쌍유리 동치다. 유리식 좌표변환으로 서로 오갈 수 있고, 그래서 이산로그 문제의 난이도가 같다. 다만 “같은 곡선”이라고 뭉뚱그리면 조금 나간다 — 방정식이 다르고, 아핀 좌표의 점 집합도 다르고, 변환식에는 예외점이 있다. 안전한 표현은 같은 곡선의 두 모델이다.¹²

이름의 혼란에는 출처가 있다. 번스타인의 2006년 논문에서 Curve25519는 곡선이 아니라 함수의 이름이었다 — $x$ 좌표만 쓰는 Diffie–Hellman 연산 그 자체. 2014년에 그가 직접 CFRG 메일링 리스트에서 용어를 정리하자고 제안했고, 그때 함수 쪽에 X25519라는 새 이름이 붙고 Curve25519는 곡선을 가리키는 말이 됐다. RFC 7748이 그 정리를 따른다. 2014년 이전 문헌에서 Curve25519를 만나면 대개 함수 쪽을 가리킨다.¹³

그러니 넷을 역할로 갈라 두는 편이 낫다. X25519는 비밀을 합의하는 함수고, Ed25519는 메시지를 서명하는 방식이고, 두 곡선 이름은 그 둘이 계산하는 무대다. 곡선이 같으니 키를 겹쳐 써도 되지 않느냐는 물음은 별도의 분석이 필요한 물음이지, 이 표에서 바로 나오는 답이 아니다.

“ECDSA는 난수가 필요하다”는 이제 틀린 말이다

여기까지만 읽으면 결정론이 Ed25519만의 발명처럼 보인다. 그렇지 않다.

2013년에 나온 RFC 6979가 ECDSA용 결정론적 nonce를 이미 적어 두었다. 개인키와 메시지 해시를 HMAC 기반 결정론적 난수 생성기에 넣어 $k$ 를 뽑는 방식이다. 핵심은 검증하는 쪽이 아무것도 몰라도 된다는 것이다 — $r$ 과 $s$ 의 계산도, 키 생성도 그대로라서 기존 검증기가 그냥 받아들인다.¹⁴ NIST도 2023년 FIPS 186-5에서 결정론적 ECDSA와 EdDSA를 함께 승인 목록에 올렸다.¹⁵

그러니 정확한 대비는 “난수 대 결정론”이 아니다. 차이는 무엇이 스펙에 못 박혀 있는가다.

고를 수 있는 칸	ECDSA	Ed25519
곡선	고른다	edwards25519로 고정
해시	고른다	SHA-512로 고정
nonce 생성 규칙	구현 재량 — RFC 6979는 선택지	스펙의 일부
서명 인코딩	DER 등, 길이 가변	64바이트 고정
공개키 인코딩	압축/비압축 선택	32바이트 고정

ECDSA는 조립품이고 Ed25519는 완제품이다. 조립품에는 잘못 끼울 수 있는 칸이 있고, nonce는 그중 가장 비싼 칸이었다. 결정론적 ECDSA는 그 칸 하나를 고쳐 끼우는 부품이고, Ed25519는 애초에 그 칸을 만들지 않은 물건이다.

이 차이가 이 글의 명제다. 두 방식의 수학적 난이도는 비슷하다. 다른 것은 구현자에게 남겨 둔 자유의 양이다.

줄인 것과 없앤 것은 다르다

여기서 멈추면 찬양문이 된다. 결정론이 지우지 못한 것들이 있고, 몇 개는 결정론 때문에 생긴 것이다.

키 생성에는 여전히 좋은 난수가 필요하다. 없어진 것은 서명마다 필요하던 난수뿐이다. 32바이트 시드가 예측 가능하면 나머지 설계는 아무 의미가 없다. 다만 RFC 8032는 이 지점에서 한 가지를 덧붙인다 — 개인키는 쓰이기 전에 해시되므로, 엔트로피가 몇 비트 모자란 것만으로 재앙이 되지는 않는다고.¹⁶

메시지를 두 번 읽어야 한다. 이건 결정론이 직접 청구하는 값이다. $r$ 을 구하려면 메시지 전체가 필요하고, $k$ 를 구하려면 그 메시지가 또 필요하다. 그래서 Ed25519는 스트리밍으로 서명하지 못한다 — RFC의 표현으로 “PureEdDSA requires two passes over the input”이다. 큰 파일을 한 번만 훑고 서명하려면 미리 해시해서 넣는 변형(Ed25519ph)을 써야 하는데, 같은 문서가 그 변형은 쓰지 말라고 권고한다. 해시 함수의 약점에 훨씬 취약해지기 때문이다.¹⁷

그 두 번 읽는 자리가 공격면이 된다. 메시지를 두 번 읽는다는 것은, 두 읽기 사이에 끼어들 틈이 있다는 뜻이다. 첫 번째 읽기로 $r$ 이 정해진 뒤 메시지를 $M'$ 으로 바꿔치기하면, $r$ 은 $M$ 의 것인데 서명되는 것은 $M'$ 이 된다. 그러면 같은 $r$ 아래 서로 다른 두 서명이 생기고, 그것은 정확히 앞에서 본 nonce 재사용이다. 개인키 스칼라는 나눗셈 한 번으로 나온다.

a = \frac{S - S'}{k - k'} \bmod L

이 공격은 실험실 이야기가 아니다. 2017년에는 아두이노 나노에 전압 글리치를 넣어 SHA-512 계산을 한 번 고장 내는 것만으로 스칼라를 복구했고,¹⁸ 2018년에는 물리적 접근 없이 다른 가상머신에서 Rowhammer로 메시지 바이트를 뒤집어 같은 결과를 얻었다.¹⁹

그리고 이 대목에 이 글에서 가장 얄궂은 문장이 있다. 같은 공격은 옛날식 무작위 ECDSA에는 통하지 않는다. 매번 $k$ 가 새로 뽑히므로 두 식의 미지수가 셋이 되어 풀리지 않기 때문이다. 결정론은 난수 사고 하나를 지웠고, 그 자리에 고장 주입이라는 다른 문 하나를 열었다. FIPS 186-5도 결정론적 서명을 승인하는 바로 그 문서에서 이 위험을 함께 적어 둔다.¹⁵

다만 이 문이 아무 데서나 열리는 것은 아니다. 공격에는 조건이 붙는다 — 같은 메시지를 반복해서 서명시킬 수 있어야 하고, 서명 과정에 공격자가 통제할 수 없는 난수가 섞여 있지 않아야 한다. TLS 1.3, SSH, IKEv2는 이 조건을 만족하지 않는다. 세 프로토콜 모두 서버가 새로 뽑은 난수를 서명 대상 안에 이미 섞어 넣기 때문이다.¹⁹

대책은 결정론적 nonce에 신선한 난수를 조금 섞는 것 — 이른바 hedged 서명이다. 검증자에게는 아무것도 달라지지 않고, 난수가 나빠지거나 반복되더라도 최악의 경우가 완전 결정론과 같은 수준으로 떨어질 뿐이다. 시그널의 XEdDSA는 오래전부터 이렇게 하고 있고, NIST의 양자내성 서명 표준 ML-DSA는 아예 hedged를 기본값으로 삼았다. 다만 ECDSA·EdDSA용 hedged 규격을 세우려던 IETF 초안은 아직 RFC가 되지 못한 채 만료됐다.²⁰

남겨 둔 칸에서는 여전히 갈라진다. Ed25519 서명 하나를 두고 라이브러리마다 유효·무효 판정이 달라질 수 있다. 여인수 8을 곱한 검증식을 쓰는지, 소위수 점을 거부하는지, 비정규 인코딩을 받아 주는지, $S \ge L$ 인 서명을 막는지 — 네 칸이 서로 독립적으로 갈린다.

2020년에 이 문제를 정면으로 잰 연구가 있다. 열여섯 개 라이브러리에 경계 사례 시험 벡터 열두 개를 먹여 본 결과, 여인수를 곱한 검증식을 쓴 것은 하나뿐이었고, 소위수 점을 제대로 거부한 것도 하나뿐이었으며, 다섯 개는 $S < L$ 검사를 온전히 하지 않았다.²¹ 마지막 칸이 특히 잘 보인다. $S$ 는 해시 입력에 들어가지 않으므로, 검사를 빠뜨리면 $S$ 에 $L$ 을 더한 다른 64바이트가 같은 메시지·같은 키에 대해 그대로 통과한다. RFC 8032가 $S < L$ 검사 하나로 서명 가변성(malleability)을 막는다고 적어 둔 자리가 여기다.²²

이게 이 글의 명제를 배신하는 것은 아니다. 오히려 명제를 정확하게 만든다 — 선택지를 줄인 설계에서도, 남겨 둔 칸에서는 갈라진다. 줄인 만큼만 안전해지는 것이다. 그리고 저 연구 이후 실제로 칸이 더 줄었다. libsodium은 2022년 말에 검증을 여인수를 곱하는 쪽으로 바꿨다.²³

양자내성이 아니다. 이건 RFC 8032가 스스로 적어 둔 한계다 — 충분히 큰 양자컴퓨터는 Ed25519도 Ed448도 깬다고. 대체재는 NIST가 2024년 8월에 확정한 격자·해시 기반 서명 표준 쪽에 있다.²⁴

마지막 한 칸

문제는 풀리지 않는다, 옮겨질 뿐에서 RSA를 두고 이렇게 적었다 — 진짜 누설은 수식이 아니라 번역의 마지막 한 칸, 그러니까 수학을 현실의 하드웨어와 코드로 다시 옮기는 자리에서 일어난다고. Ed25519는 그 문장에 대한 하나의 응답으로 읽힌다.

그 응답의 방식이 이 글의 요점이다. 마지막 한 칸을 더 조심해서 채우라고 요구하는 대신, 채울 칸의 수를 줄였다. 난수 생성기를 고를 자리, 곡선을 고를 자리, 해시를 고를 자리, 인코딩을 고를 자리, 점 덧셈의 예외를 처리할 자리 — 하나씩 스펙 안으로 끌고 들어와 못을 박았다. 남은 자유가 적을수록 틀릴 수 있는 방법도 적어진다.

이것은 암호에만 있는 이야기는 아니다. 어떤 규칙이 지켜지지 않을 때, 더 잘 지키라고 요구하는 길과 지키지 않을 방법을 없애는 길이 있다. 앞의 길은 사람의 판단을 믿고, 뒤의 길은 판단에 의존하지 않는다. 전체 점검은 전체를 보지 않는다에서 문서와 필수 검사를 갈라 놓은 것과 같은 구분이다 — 문서는 판단을 돕고, 검사는 판단에만 의존하지 않게 한다. Ed25519는 nonce 규칙을 문서에서 검사로, 정확히는 스펙 안으로 옮긴 쪽이다.

암호학은 공격자가 풀기 어려운 문제를 만드는 학문이다. 그런데 실제 암호 시스템은 개발자가 틀리기 어려운 형태까지 만들어야 완성된다.

같은 메시지에 같은 서명이 나오는 것은, 그러니까 이상한 일이 아니다. 그 자리에 아무것도 고를 것이 남아 있지 않다는 뜻이다.

더 들어가려면

규격 본문: RFC 8032 — Edwards-Curve Digital Signature Algorithm (EdDSA)
곡선 쪽: RFC 7748 — Elliptic Curves for Security
결정론적 ECDSA: RFC 6979
구현 간 판정이 갈리는 지점들: Taming the Many EdDSAs

RFC 8032 §7.1의 두 번째 시험 벡터(1바이트 메시지 0x72)다. 본문 코드의 PKCS#8 접두사 302e020100300506032b657004220420은 32바이트 Ed25519 시드를 감싸는 고정 껍데기이고, 그 뒤가 RFC의 시드 값이다. ↩
$r$ 이 $k$ 에만 의존하므로 같은 $k$ 를 쓴 두 서명은 같은 $r$ 을 갖는다. $s_1 = k^{-1}(z_1 + rd)$ 와 $s_2 = k^{-1}(z_2 + rd)$ 를 빼면 $rd$ 항이 소거되어 $s_1 - s_2 = k^{-1}(z_1 - z_2)$ 가 되고, 여기서 $k$ 를 얻은 뒤 $d = r^{-1}(s_1 k - z_1)$ 로 개인키가 나온다. 모든 연산은 위수 $n$ 을 법으로 한다. ↩
fail0verflow, Console Hacking 2010: PS3 Epic Fail, 27C3, 2010년 12월 29일. 난수 생성기가 우연히 충돌한 사고가 아니었다 — 소니의 서명 코드는 $k$ 를 상수로 두었다. 발표는 그 자리를 xkcd 221번의 return 4; // chosen by fair dice roll 패널 한 장으로 대신했다. 깨진 것은 SELF(Signed ELF) 코드 서명 체인이다. ↩
bitcoin.org의 경고문은 2013년 8월 11일자, 구글 안드로이드 보안팀의 원인 분석은 8월 14일자다. 결함은 둘이었다 — Apache Harmony SHA1PRNG의 오프셋 오류(CVE-2013-7372)와, 안드로이드 4.4 이전에서 OpenSSL PRNG가 제대로 시드되지 않는 문제(CVE-2013-7373). 경고문은 이것을 키 생성의 약점으로 서술했지만, 실제로 관측된 도난은 nonce 재사용 경로였다. ↩
개인키 복원은 hidden number problem, 곧 격자 문제로 환원된다. 문턱이 내려온 경로는 이렇다. Howgrave-Graham & Smart(1999)는 160비트 위수에서 8비트가 알려질 때 서명 30개로 풀었고 4비트는 불가능하다고 적었다. Minerva(TCHES 2020)는 여러 라이브러리와 인증받은 스마트카드 칩에서 $k$ 의 비트 길이가 새는 것을 찾아 256비트 키를 서명 500~2,100개로 복구했다. LadderLeak(ePrint 2020/615)의 “1비트 미만”은 비유가 아니다 — 최상위 비트를 확률 1 미만으로 알려 주는 잡음 섞인 오라클을 뜻하고, 그만큼 서명이 많이 필요하다 — 잡음 있는 오라클로 NIST P-192는 $2^{35}$ 개, sect163r1은 $2^{24}$ 개를 썼다. 덧붙여 $k$ 가 재사용된 것이 아니라 아예 예측 가능하면 서명 하나로 끝난다 — $d = (sk - z)r^{-1} \bmod n$ . ↩
RFC 8032 §5.1.5의 2단계. 규격의 말은 “prune the buffer”이고, 바이트로 옮기면 h[0] &= 248, h[31] &= 127, h[31] |= 64다. 이유는 §3의 매개변수 5·6에 있다 — 비밀 스칼라는 $2^c$ 의 배수여야 하고( $c=3$ ), 정확히 $n+1$ 비트여야 하며 $2^n$ 자리가 항상 켜져 있어야 한다( $n = 254$ ). 결과적으로 $2^{254} \le a < 2^{255}$ 이고 $a \equiv 0 \pmod 8$ 이다. ↩
RFC 8032 §5.1.6. 본문의 $\mathbin\Vert$ 는 바이트열 이어붙이기다. 규격은 $r$ 과 $k$ 를 SHA-512 출력 64바이트를 리틀엔디언 정수로 읽은 값으로 정의하고 $\bmod\ L$ 은 “효율을 위해” 먼저 줄이라고 적는데, 부록의 참조 구현은 본문처럼 바로 줄인다. Ed25519ctx·Ed25519ph에서는 해시 입력 앞에 dom2 접두사가 붙는다. ↩
RFC 8032 §5.1.7의 3단계 원문은 “Check the group equation [8][S]B = [8]R + [8][k]A’. It’s sufficient, but not required, to instead check [S]B = R + [k]A’.”다. §8.8은 여인수를 곱하는 것이 “보안상 꼭 필요하지는 않지만”, 어떤 응용에서는 구현들이 유효한 서명의 집합을 두고 서로 다르게 판단하는 것 자체가 바람직하지 않다고 적는다 — 예로 fingerprinting 공격을 든다. 실제로 이 두 문장이 뒤의 절에서 볼 구현 간 불일치의 출처다. ↩
RFC 7748 §4.1의 말은 “Few primes of the form 2^c-s with s small exist between 2^250 and 2^521, and other choices of coefficient are not as competitive in performance”다. 문헌은 이런 꼴을 유사 메르센(pseudo-Mersenne) 소수라 부르지만 RFC 7748과 RFC 8032 어디에도 그 표현은 없다. 메르센 소수 $2^n - 1$ 과는 다른 것이다. ↩ ↩²
트위스티드 에드워즈 곡선 $ax^2 + y^2 = 1 + dx^2y^2$ 에서 $a$ 가 $\mathrm{GF}(p)$ 의 제곱수이고 $d$ 가 제곱수가 아니면 덧셈 공식이 모든 점 쌍에 대해 성립한다. edwards25519는 $a = -1$ 이고 $p \equiv 1 \pmod 4$ 라 $-1$ 이 제곱수이며, $d$ 는 제곱수가 아니다. 한 가지 더 — 완전성은 곡선이 아니라 공식의 성질이다. 같은 곡선 위에도 완전하지 않은 덧셈 공식이 있고, Ed25519 논문은 더 빠른 그런 공식을 이 이유로 쓰지 않았다고 적는다. ↩
RFC 8032 §8.1 마지막 문장 — “Note that the example implementations in this document do not attempt to be side-channel silent.” 같은 절은 $\bmod\ p$ 산술에 데이터 의존 분기가 없어야 하고, 점 덧셈은 통합 공식 덕분에 어렵지 않지만 스칼라 곱셈은 별도의 노력이 필요하다고 덧붙인다. ↩
RFC 7748 §4.1 — “This curve is birationally equivalent to a twisted Edwards curve -x^2 + y^2 = 1 + dx^2y^2, called “edwards25519"". 같은 절이 양방향 변환식을 함께 준다. 참고로 curve25519↔edwards25519는 쌍유리 동치지만 curve448↔edwards448은 4-아이소제니다 — 한쪽 이야기를 다른 쪽에 옮기면 안 된다. ↩ ↩²
번스타인의 2006년 논문 서론은 “The Curve25519 function is F_p-restricted x-coordinate scalar multiplication on E(F_p2)“라고 정의한다 — 곡선이 아니라 함수다. 2014년 8월 CFRG 메일링 리스트 글에서 그는 X25519를 몽고메리 $x$ 좌표 DH 함수, Ed25519를 에드워즈 좌표 서명 방식, Curve25519를 그 바탕 타원곡선으로 쓰자고 제안했고 RFC 7748이 이를 따랐다. ↩ ↩²
RFC 6979, Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA), 2013년 8월. 토마 포르냉 개인 명의의 Independent Submission이고 분류는 Informational이다 — IETF 표준화 트랙 문서가 아닌데도 사실상의 기준이 되어 지금은 FIPS 186-5가 참조로 인용한다. ↩
NIST FIPS 186-5, Digital Signature Standard (DSS), 2023년 2월 3일 발효. §6.3.2가 결정론적 ECDSA를, §7.1이 EdDSA를 다루고, §6.4의 입력 목록에는 “An approved random bit generator (not needed for deterministic ECDSA)“라고 적혀 있다. 같은 문서가 반대편도 적어 둔다 — §6과 §7.1은 결정론적 서명이 고장 주입에 취약해질 수 있다고 경고하며 관련 논문들을 인용한다. ↩ ↩²
RFC 8032 §8.2 — “Obviously, private key generation requires randomness, but due to the fact that the private key is hashed before use, a few missing bits of entropy doesn’t constitute a disaster.” 같은 절은 검증도 결정론적이지만 여러 서명을 한꺼번에 확인하는 일괄 검증(batch verification)에는 난수가 필요하다고 덧붙인다. ↩
RFC 8032 §4 — “PureEdDSA requires two passes over the input.” 그 절은 이것을 충돌 내성과 단일 패스 인터페이스 사이의 선택으로 제시한다. Ed25519ph에 대한 권고는 §8.5에 있다 — “These variants SHOULD NOT be used.” ↩
Romailler & Pelissier, Practical fault attack against the Ed25519 and EdDSA signature schemes, FDTC 2017. 해시 출력에 한 바이트 고장을 넣어 같은 $r$ 에 서로 다른 $k$ 를 만든다. 이 공격으로 복구되는 것은 비밀 스칼라 $a$ 뿐이고 시드와 prefix는 남는데, 임의의 $r$ 을 골라 서명해도 검증식이 성립하므로 $a$ 만으로 어떤 메시지든 위조할 수 있다. ↩
Poddebniak, Somorovsky, Schinzel, Lochter, Rösler, Attacking Deterministic Signature Schemes Using Fault Attacks, EuroS&P 2018, ePrint 2017/1014. 핵심 관찰이 본문의 그것이다 — “We now observe that M is read twice during the signature process.” 무작위 ECDSA에 통하지 않는 이유(미지수가 셋이 되어 유일해가 없다)와 TLS 1.3·SSH·IKEv2가 왜 조건에 해당하지 않는지도 같은 논문의 분석이다. ↩ ↩²
IETF 초안은 draft-irtf-cfrg-det-sigs-with-noise, Hedged ECDSA and EdDSA Signatures. 2022년 CFRG 문서로 채택됐지만 -05(2025년 3월)를 끝으로 만료됐다. 구성은 간단하다 — $r$ 을 구하기 전에 SHA-512(prefix || Z)로 prefix를 한 번 더 섞는다( $Z$ 는 32바이트 난수). 시그널의 XEdDSA는 64바이트 난수를 nonce 해시에 섞는다. ↩
Chalkias, Garillot, Nikolaenko, Taming the many EdDSAs, SSR 2020, ePrint 2020/1244. 여인수를 곱한 검증식을 쓴 것은 ed25519-zebra뿐, 소위수 성분을 검사한 것은 libsodium뿐이었다. $S < L$ 을 온전히 검사하지 않은 다섯 중 ed25519-donna와 ref10은 최상위 세 비트만 보는 빠른 검사(sig[63] & 224)를 하는데, 이것은 $S \ge 2^{253}$ 만 걸러 내므로, $S + L$ 이 떨어지는 $[L,\, 2^{253})$ 구간의 비정규 값이 통과한다. ↩
RFC 8032 §8.4 — “Ed25519 and Ed448 signatures are not malleable due to the verification check that decoded S is smaller than l.” 이유는 단순하다. 해시 입력은 $R \mathbin\Vert A \mathbin\Vert M$ 이라 $S$ 가 들어가지 않고, $B$ 의 위수가 $L$ 이므로 $[S+L]B = [S]B$ 다. ↩
libsodium 1.0.18은 계산한 $R$ 과 서명의 $R$ 을 바이트로 비교했다(여인수를 곱하지 않는 방식). 현재 master는 $R - ([S]B - [k]A)$ 가 소위수인지를 보는데, 이는 $[8][S]B = [8]R + [8][k]A$ 와 같다. 바뀐 커밋은 2022년 11월 26일자다. ↩
RFC 8032 §1 — “A sufficiently large quantum computer would be able to break both.” §8.5는 더 짧게 적는다 — “Both are demolished by quantum computers just about the same.” 대체 표준은 NIST가 2024년 8월에 확정한 FIPS 204(ML-DSA)와 FIPS 205(SLH-DSA)다. ↩