같은 메시지에는 같은 서명 — Ed25519가 매번 주사위를 굴리지 않는 이유

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

고장일까? 암호에서 반복은 사고의 냄새가 날 때가 있다. ECDSA라는 전자서명 방식에서는 서로 다른 메시지에 같은 비밀 난수를 다시 쓰면 개인키를 들킬 수 있다. 그런데 Ed25519에서는 같은 메시지에 같은 서명이 나오는 것이 설계의 일부다.

차이는 무엇이 반복되느냐에 있다. 이 글은 그 차이를 따라간다.

직접 두 번 서명해 본다

전자서명은 공개키로 두 가지를 확인하게 해 준다. 개인키를 가진 사람이 서명했는지, 그리고 메시지가 바뀌지 않았는지다. 인감도장과 인감증명서에 빗대면 개인키는 도장이고, 공개키는 누구나 대조해 볼 수 있는 증명서다. 다만 도장은 어느 서류에 찍어도 같은 자국을 남기지만, 전자서명은 메시지 내용을 바탕으로 계산한 값이라 다른 문서에 옮겨 붙이면 검증을 통과하지 못한다. 메시지를 숨기는 암호화와도 역할이 다르다.

Node.js로 Ed25519 서명을 두 번 만들어 보자. 코드의 시드는 32바이트 비밀값으로, 서명에 필요한 비밀이 모두 여기서 나온다. 이 자리에는 규격 문서인 RFC 8032에 실린 공개 시험값을 넣었다.

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

// RFC 8032 §7.1 TEST 2의 공개 시험용 시드. 실제 키로 쓰지 않는다.
// PKCS#8은 Node.js에 개인키를 전달하기 위한 포장 형식이다.
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에 실린 정답과도 바이트 단위로 같다.¹ 이 글에서 다루는 기본 Ed25519의 서명 절차는 키와 메시지가 같으면 같은 결과를 내도록 정해져 있다. 이를 결정론적이라고 부른다. 주사위보다는 계산기에 가깝다.

Ed25519는 서명할 때마다 좋은 난수를 뽑아야 한다는 숙제를 없앴다.

그 숙제를 망치면 무슨 일이 생기는지부터 보자. 수식이 몇 개 나오지만 기호를 다 외울 필요는 없다. 같은 값이 두 식에 들어갔을 때 무엇이 드러나는지만 따라가면 된다.

nonce — 메시지마다 달라야 하는 비밀

nonce는 number used once, 한 번 쓰는 수라는 뜻이다. 용도에 따라 공개되는 nonce도 있지만, 여기서 다루는 서명용 nonce는 비밀이어야 한다.

난수로 nonce를 만드는 ECDSA의 서명식은 이렇다.

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

여기서 $d$는 오래 보관하는 개인키, $k$는 서명마다 새로 뽑는 비밀 정수, 곧 nonce다. $z$는 메시지를 해시해 얻은 정수다. 해시는 어떤 길이의 입력이든 일정한 길이의 값으로 바꾸는 함수로, 같은 입력에는 늘 같은 값을 낸다. $r$은 $k$로 곡선 위의 점을 계산해 얻는 값이며, $(r,s)$가 공개되는 서명이다.

모든 계산은 정해진 수 $n$으로 나눈 나머지 범위에서 한다. 시곗바늘이 12시간마다 같은 자리로 돌아오듯, 결과가 $n$에 닿으면 0부터 다시 센다.

서명 하나는 공격자에게 식 하나를 준다. 공개된 $r$에서 $k$를 거꾸로 구하기는 어렵다고 보면, 이 식에서 모르는 값은 $k$와 $d$ 둘이다. 식 하나로 미지수 둘을 풀 수는 없다. 서명마다 새 $k$를 뽑으면 식이 하나 늘 때 미지수도 하나 늘어난다. 문제는 $k$를 다시 쓸 때다.

같은 $k$로 해시가 다른 두 메시지를 서명했다고 하자. 두 서명의 $r$도 같아진다. 두 식을 빼면 개인키가 들어 있던 항이 사라진다.

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

이제 공개된 값만으로 $k$를 구하고, 원래 식에 넣어 개인키 $d$까지 구할 수 있다.

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

어려운 암호 문제를 풀 필요가 없다. 같은 미지수가 들어간 두 식을 연립해 풀면 된다.²

종이 위의 이야기만은 아니다. 2010년 fail0verflow의 PS3 분석에서는 코드 서명에 같은 $k$를 쓰는 문제가 드러났다.³ 2013년에는 안드로이드의 난수 생성기 초기화 결함이 비트코인 지갑 보안 사고로 이어졌다.⁴

nonce를 통째로 재사용해야만 위험한 것도 아니다. nonce의 일부 정보가 실행 시간 차이로 새어 나가는 것만으로 개인키를 복구한 연구도 있다.⁵ $k$는 쓰고 버리는 값이지만, 지켜야 할 비밀이라는 점에서는 개인키 못지않다.

주사위를 굴리는 대신 메시지에서 계산한다

그렇다면 주사위를 아예 치우면 어떨까. Ed25519는 nonce를 개인키와 메시지에서 계산한다. 먼저 32바이트 시드에서 서명에 쓸 비밀값 둘과 공개키를 만든다.

h      = SHA-512(seed)     # seed: 무작위로 만든 32바이트 비밀값
a      = clamp(h[0:32])    # 앞 절반을 조정한 비밀 정수
prefix = h[32:64]          # nonce 계산에 쓸 비밀값
A      = [a]B              # 공개키

타원곡선에는 곡선 위의 두 점을 ‘더해’ 또 다른 점을 얻는 규칙이 있다. [a]B는 기준점 $B$를 이 규칙으로 $a$번 더하는 연산이다. $a$가 아주 커도 두 배 하기와 더하기를 조합하면 금방 계산할 수 있다. 반대로 공개된 $A$만 보고 $a$를 알아내기는 어렵다고 여겨진다. 그래서 $A$를 공개키로 내놓을 수 있다.

clamp는 앞 절반의 일부 비트를 규격대로 고정하는 처리다. 그 결과 $a$는 일정 범위의 8의 배수가 된다. 이 처리는 비밀 정수의 형태를 맞춰 주지만, 검증이나 뒤에서 볼 부채널 방어까지 대신해 주지는 않는다.⁶

뒤 절반인 prefix도 버리지 않는다. 이 값과 지금 서명하는 메시지를 해시한 결과가 nonce다. 같은 입력이면 같은 값이 나오지만, 비밀 prefix를 모르는 사람은 nonce를 미리 계산하기 어렵다.

수식으로 옮기기 전에 주의할 점이 하나 있다. 앞의 ECDSA와는 기호의 쓰임이 다르다. 여기서는 $r$이 비밀 nonce이고, $k$는 공개된 정보로 계산하는 값이다. 나머지 기호도 정리해 두자. $H$는 SHA-512, $M$은 메시지, $L$은 기준점 $B$를 반복해서 더할 때 한 바퀴를 도는 주기다. $\Vert$는 바이트열을 이어 붙인다는 뜻이다.

$$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$$

첫 식에서는 prefix와 메시지로 nonce $r$을 만들고, $B$를 $r$번 더한 점 $R$을 구한다. 둘째 식의 $k$는 $R$, 공개키 $A$, 메시지로 계산하므로 검증자도 똑같이 구할 수 있다. 셋째 식에서는 $r$과 $k$, 그리고 시드에서 나온 비밀 정수 $a$로 $S$를 계산한다. 점 $R$과 정수 $S$를 각각 32바이트로 인코딩해 이어 붙인 것이 64바이트 서명이다.⁷

위험했던 것은 서로 다른 메시지에 같은 nonce를 쓰는 일이었다. Ed25519에서는 메시지가 바뀌면 해시 입력도 바뀐다. 예를 들어 ‘좋아’와 ‘좋다’처럼 한 글자만 달라도, 해시 결과는 조금 달라지는 게 아니라 서로 무관해 보이는 값이 된다. 우연히 같은 $r$이 나올 수는 있지만, 정상적인 조건에서 그 충돌 확률은 무시할 만큼 작다. 난수 생성기 상태가 꼬여 같은 값을 되풀이하는 사고를 이 단계에서 걱정할 필요가 없어진다.

반면 메시지가 같으면 nonce도 같고 서명도 같다. 공개된 서명만 보는 공격자는 이미 가진 서명을 한 장 더 받을 뿐이다. 같은 식이 두 번 적힌 셈이라, 개인키를 풀어낼 새로운 식은 생기지 않는다.

매번 새 난수를 잘 뽑아야 하던 일이, 키를 만들 때 좋은 시드를 한 번 뽑는 일로 줄었다.

비밀을 모르고 확인하는 법

검증자는 $r$도 $a$도 모른다. 그런데 $S$가 제대로 만들어졌는지 어떻게 알 수 있을까. 비결은 두 비밀이 곡선 위의 점으로 모습을 바꿔 이미 공개돼 있다는 데 있다. 서명 속 $R$은 $B$를 $r$번 더한 점이고, 공개키 $A$는 $B$를 $a$번 더한 점이다. 점만 보고 몇 번 더했는지 알아내기는 어렵다고 여겨지지만, 점끼리 더하는 계산은 누구나 할 수 있다. 검증의 핵심 관계는 이것이다.

$$[S]B = R + [k]A$$

검증자는 공개키 $A$, 서명의 $R$, 메시지 $M$으로 $k$를 다시 계산한다. 올바른 서명이 이 관계를 만족하는 이유는 식을 풀면 보인다.

$$[S]B = [r + ka]B = [r]B + [k]([a]B) = R + [k]A$$

가운데 단계에는 비밀이 들어 있지만, 검증자가 실제로 맞춰 보는 양 끝에는 비밀값이 없다. 키와 검증 절차가 적절하고 암호학적 가정이 성립한다면, 개인키 없이 이 관계에 맞는 새 서명을 만들기는 어렵다.

실제 검증에는 인코딩과 숫자 범위 검사도 필요하다. RFC 8032는 위 식의 양쪽에 8을 곱한 형태를 제시하면서, 8을 곱하지 않은 식으로 검사해도 된다고 한다. 이 8은 곡선의 여인수다. 곡선 위 점의 전체 개수가 기준점의 주기 $L$의 8배라는 데서 나온다. 두 검증식은 정상적으로 만든 서명에서는 모두 성립하지만, 특수한 입력을 받아들이는 범위는 달라질 수 있다.⁸

이 차이는 뒤에서 다시 나온다. 서명을 만드는 방법을 고정했다고 해서, 어떤 서명을 받아들일지까지 완전히 같아지지는 않는다.

25519 — 나머지 계산을 쉽게 만드는 숫자

Ed25519의 25519는 어디서 온 숫자일까. 좌표 계산에 쓰는 아래 소수에서 255와 19를 따왔다.

$$p = 2^{255} - 19$$

이 수로 나눈 나머지만 남기며 계산한다. 눈여겨볼 것은 19라는 숫자보다 $2^{255}$에 바짝 붙은 모양이다. 이 모양 덕분에 큰 나눗셈을 자리 옮김과 작은 수의 곱셈·덧셈으로 바꿀 수 있다.⁹

십진법으로 옮겨 보면 감이 온다. 예를 들어 1000보다 3 작은 997로 나눈 나머지를 구한다고 하자. 나머지만 따지면 1000은 3과 같다. 그래서 12345를 12×1000 + 345로 쪼개면, 나머지는 12×3 + 345 = 381이다. 긴 나눗셈이 필요 없다. $p$도 $2^{255}$보다 19 작다. 그래서 $p$로 나눈 나머지만 따지면 $2^{255}$는 19와 같고, 이진법에서 같은 요령이 통한다.

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

큰 수를 $x = x_0 + 2^{255}x_1$로 쪼개어 쓰면,

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

가 된다. 높은 자릿값을 잘라 19배한 뒤 아래쪽에 더하면 큰 나눗셈을 피할 수 있다. 실제 구현에서는 이 접기를 반복하고 올림과 마지막 뺄셈을 처리한다. 19를 한 번 곱해 더하는 것으로 나머지 계산이 다 끝나지는 않는다.

이런 구조는 빠른 계산뿐 아니라, 비밀값에 따라 실행 경로가 달라지지 않는 구현을 만드는 데도 도움이 된다.

예외가 적으면 실수할 자리도 줄어든다

타원곡선의 점 덧셈에도 “이 경우에는 다른 공식을 써라”라는 예외가 있다. 예를 들어 바이어슈트라스 형태의 곡선에서 점을 평범한 $(x, y)$ 좌표(아핀 좌표)로 더하는 일반적인 공식은 두 점이 같을 때와 다를 때를 구분한다. 서로 다른 두 점은 둘을 잇는 직선의 기울기로 더하는데, 두 점의 $x$좌표가 같으면 그 기울기의 분모가 0이 되기 때문이다. 두 점이 같을 때는 접선을 쓰는 별도 공식이 필요하고, 서로 반대인 두 점도 따로 처리해야 한다.

비밀값에 따라 서로 다른 코드를 실행하면, 걸리는 시간이나 메모리 접근 흔적에서 정보가 샐 수 있다. 이를 부채널 누출이라고 한다. 비밀번호를 직접 보여 주지 않아도, 맞는 글자 수에 따라 응답 시간이 달라지면 단서가 되는 것과 비슷하다.

Ed25519가 쓰는 곡선에는 모든 점 쌍에 적용되는 완전한 덧셈 공식이 있다. 같은 점을 더하든, 서로 반대인 점을 더하든 하나의 공식으로 처리한다.¹⁰ 점의 관계에 따라 예외 분기를 만들 이유가 줄어든다.

그래도 완전한 공식이 곧 정보가 새지 않는 코드는 아니다. $[a]B$를 계산할 때 두 배 하기와 더하기를 어떤 순서로 거듭하는지, 미리 계산한 표의 어디를 읽는지도 중요하다. 비밀값에 따라 실행 시간과 메모리 접근이 달라지지 않게 짜는 일을 보통 constant-time 구현이라고 부른다. RFC도 문서에 실린 교육용 예제는 이런 방어를 목표로 하지 않는다고 밝힌다.¹¹

공식은 안전하게 짜기 쉬운 조건을 마련해 줄 뿐이다. 실제 코드가 그 조건을 살리는지는 따로 확인해야 한다.

닮은 이름 네 개를 구별해 두자

앞의 두 곡선 모델은 적절한 좌표변환으로 연결된다.¹² 같은 땅을 서로 다른 도법으로 그린 두 지도처럼, 바탕은 같고 좌표를 적는 방식이 다르다. 그래서 이름이 닮았다. 하지만 뒤의 두 도구는 하는 일이 다르다. X25519는 비밀을 합의하고, Ed25519는 메시지에 서명한다. 같은 수학을 쓴다고 해서 두 용도의 키를 그대로 바꿔 써도 된다는 뜻은 아니다.

ECDSA도 주사위를 안 굴릴 수 있다

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

RFC 6979는 ECDSA에서도 개인키와 메시지 해시로 nonce를 계산하는 방법을 정한다. 이렇게 만든 서명은 기존 ECDSA 검증기로 확인할 수 있다. 검증기는 nonce를 어떻게 골랐는지 따지지 않기 때문이다. NIST의 FIPS 186-5도 결정론적 ECDSA와 EdDSA를 다룬다.¹³

그러니 둘의 차이는 난수를 쓰느냐에만 있지 않다. 기본 규격이 무엇을 미리 정해 두었는가에도 있다.

식당에 빗대면 ECDSA는 재료를 하나씩 골라 주문하는 방식이고, Ed25519는 구성의 상당 부분을 미리 정해 둔 정식에 가깝다. ECDSA를 사용하는 프로토콜도 허용하는 조합을 좁힐 수 있다. 다만 Ed25519는 이름 하나에 표의 네 항목이 함께 묶여 나온다.

고를 수 있는 항목이 줄면 잘못 조합할 자리도 줄어든다. 이 글이 주목하는 설계상의 이점이 바로 이것이다.

그래도 남는 숙제

주사위 하나를 치웠다고 숙제가 모두 끝나지는 않는다.

키를 만들 때는 좋은 난수가 필요하다

32바이트 시드를 공격자가 예측할 수 있다면 나머지 설계가 아무리 좋아도 소용없다. 줄어든 것은 서명마다 난수를 뽑는 부담이다. 개인키 생성과 보관은 여전히 중요하다.¹⁴

기본 Ed25519는 메시지를 두 번 읽는다

nonce $r$을 계산할 때 한 번, 공개값 $k$를 계산할 때 다시 한 번 메시지가 필요하다. 둘째 해시의 입력은 $R$로 시작하는데, $R$은 첫 해시가 메시지를 끝까지 읽어야 나온다. 그래서 메시지를 보관하거나 다시 읽을 수 있어야 한다. 예를 들어 큰 파일을 네트워크로 받으면서 바로 서명하려면, 첫 해시가 끝난 뒤 둘째 해시에 다시 넣을 수 있도록 파일 전체를 어딘가에 저장해 두어야 한다. 한 번 지나간 데이터를 저장하지 않는 단일 패스 인터페이스와는 맞지 않는다.

미리 해시하는 Ed25519ph 변형은 입력을 한 번만 훑으면 되지만 보안 특성이 달라진다. 해시값을 문서의 지문에 빗대면, 이 변형은 계약서 원문 대신 그 지문에 서명하는 셈이다. 서로 다른 두 계약서에서 똑같은 지문이 나온다면, 한쪽에서 받은 서명을 다른 쪽에도 그대로 쓸 수 있다. 이렇게 서로 다른 입력이 같은 해시값을 내는 일을 해시 충돌이라고 한다. 그래서 미리 해시한 메시지에 서명하면 안전성이 그 사전 해시의 충돌 저항성, 곧 충돌을 찾기 어려운 성질에 달려 있다. 기본 Ed25519도 안에서 메시지를 해시하지만 해시하는 방식이 달라서, 해시 충돌을 이용한 공격을 막는 성질이 한 겹 더 있다. RFC는 이 차이 때문에 기본 변형을 권한다.¹⁵

두 번 읽는 것은 결정론적 서명 전체의 필수 조건이 아니라, 이 서명 구성에서 생기는 비용이다.

계산 중간을 고장 내면 다른 문제가 생긴다

같은 입력에 같은 nonce가 나온다는 성질을 공격자가 거꾸로 이용할 수는 없을까.

공격자가 정상적인 서명을 하나 얻은 뒤, 같은 메시지를 다시 서명시키면서 계산 중간을 교란할 수 있다고 하자. 메시지가 같으니 nonce $r$은 두 번 다 똑같이 나온다. 그런데 nonce를 계산한 직후 다음 해시에 들어갈 메시지를 공격자가 아는 $M'$으로 바꾸면, 같은 $r$에 서로 다른 $k$와 $k'$이 붙는다. 공격자는 공개된 $R$, $A$와 두 메시지로 이 값들을 계산할 수 있다. 정상 서명의 $S$에서 교란된 서명의 $S'$을 빼면 공통의 $r$이 사라진다. 다시 연립방정식이다.

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

실제로 Rowhammer로 메모리 비트를 뒤집는 방식 등을 분석한 연구가 있다.¹⁶ Rowhammer는 메모리의 한 줄에 빠르게 거듭 접근해 이웃한 줄의 비트를 바꾸는 기법이다. 다만 이 고장 공격은 서명 두 개를 수집하는 것만으로는 성립하지 않는다. 같은 입력을 반복해 서명시키고 특정 계산이나 데이터를 교란할 수 있어야 한다. 그 연구에 따르면, 분석 대상이 된 TLS·SSH·IPsec의 사용 방식은 이 공격 조건에 해당하지 않는다.

nonce를 매번 독립적으로 새로 뽑으면 이처럼 두 식을 빼서 nonce를 소거하는 방법은 통하지 않는다. 그렇다고 무작위 서명이 모든 고장 공격에 안전하다는 뜻은 아니다. 결정론적 서명은 한 종류의 사고를 줄인다. 다만 다른 공격 조건에서는 같은 계산을 반복한다는 점이 공격의 단서가 될 수 있다.

대응 방향 중 하나는 개인키와 메시지로 정한 nonce에 추가 난수를 섞는 hedged 서명이다. 이름의 hedge는 내기에서 한쪽에만 걸지 않는다는 뜻이다. 난수가 나빠져도 결정론적 계산에 기대고, 난수가 좋으면 반복을 이용하는 공격에 대비하려는 설계다. 적절한 구성과 구현이 전제된다. 시그널의 XEdDSA가 이런 방식을 쓰며, ECDSA·EdDSA용 IETF 초안도 있다. 이 초안은 2026년 9월 확인 기준 만료 상태이며 RFC가 아니다.¹⁷

검증 구현도 맞춰 봐야 한다

같은 답안지를 채점자 두 명이 보면, 분명한 정답과 오답에는 같은 점수를 주다가도 애매한 답에서 판정이 갈릴 수 있다. 채점 기준 하나를 빠뜨린 채점자가 있을 때도 그렇다. 서명 검증도 비슷하다. 서명 생성법을 고정해도 검증기가 경계 사례를 다르게 처리할 수 있다. 앞서 본 여인수 처리, 허용하는 점과 인코딩, 정수 범위 검사 등이 차이를 만든다. 2020년의 Taming the many EdDSAs는 실제 라이브러리에서 이런 불일치를 조사했다.¹⁸

그중 이해하기 쉬운 예는 $S$의 범위다. 검증기가 $S < L$을 검사하지 않으면, $S$에 $L$을 더해도 곡선 계산 결과는 같아질 수 있다. $B$는 $L$번 더하면 한 바퀴를 돌아오기 때문이다. 시계에서 3시와 15시가 같은 자리를 가리키는 것과 같다. $S+L$이 인코딩 범위에 들어가면, 원본과 다른 서명 바이트가 검증을 통과할 수 있다.¹⁹

여러 시스템이 같은 입력에 같은 판정을 내려야 한다면 이런 검증 기준도 맞춰야 한다. 결정론적 생성과 구현 간 검증의 일치는 서로 다른 문제다.

끝으로, Ed25519는 양자내성 서명도 아니다. 충분히 큰 양자컴퓨터에는 취약하며, NIST의 ML-DSA·SLH-DSA 같은 양자내성 서명은 별도의 방식이다.²⁰

마지막 한 칸

문제를 옮겨 푼다에서는 문제의 표현을 바꾸면 다루기 쉬워지는 순간을 따라갔다. Ed25519에서도 비슷한 선택이 보인다. “서명할 때마다 좋은 난수를 뽑아라”라는 요구를 “좋은 시드에서 정해진 방법으로 계산하라”로 바꾼다.

물론 규격에 적었다고 구현이 저절로 정확해지지는 않는다. 키를 지키고, 부채널을 막고, 검증 규칙을 맞추는 일은 남는다. 그래도 서명할 때마다 제대로 해내야 하던 일 하나가 사라졌다는 차이는 크다.

전체 점검은 전체를 보지 않는다에서 다룬 검사 절차도 비슷한 질문에서 출발한다. 매번 주의를 기울여야 하는 일 중, 정해진 절차에 맡길 수 있는 것은 무엇인가.

같은 메시지에 같은 서명이 나왔다. 이번에는 주사위를 잘못 굴린 게 아니다. 그 단계에는 주사위가 없었다.

더 들어가려면

• 서명 규격과 시험값: RFC 8032
• 곡선과 키 합의: RFC 7748
• 결정론적 ECDSA: RFC 6979
• 검증 결과가 갈리는 사례: Taming the many EdDSAs

주석

1. RFC 8032 §7.1의 두 번째 시험 벡터. 메시지는 1바이트 0x72다. 코드의 PKCS#8 접두사는 32바이트 시드를 개인키 형식으로 감싼다. ↩

2. 모든 연산은 기준점의 위수 $n$을 법으로 한다. $z_1 \not\equiv z_2 \pmod n$이고 유효한 ECDSA 서명이라면 본문의 분모에 역원이 존재한다. 같은 메시지의 같은 서명 두 개로는 이렇게 소거해도 새 정보를 얻을 수 없다. ↩

3. fail0verflow, Console Hacking 2010: PS3 Epic Fail, 27C3, 2010년 12월 29일. 발표 자료는 서명용 난수를 매번 바꾸지 않은 문제와 개인키 복구식을 보여 준다. ↩

4. 안드로이드 보안팀의 Some SecureRandom Thoughts, 2013년 8월 14일. 비트코인 거래 사고를 계기로 조사한 PRNG 초기화 문제와 키 생성·서명·난수 생성에 미치는 영향을 설명한다. ↩

5. Minerva 연구팀의 공개 설명. 일부 ECDSA 구현에서 nonce의 비트 길이에 따른 실행 시간 차이를 이용해 개인키를 복구했다. 필요한 관측 수는 장치와 잡음 조건에 따라 다르므로 서로 다른 공격의 수치를 하나의 발전 속도처럼 비교하기는 어렵다. ↩

6. RFC 8032 §5.1.5. 리틀엔디언 바이트열에 h[0] &= 248, h[31] &= 127, h[31] |= 64를 적용하면 $2^{254} \le a < 2^{255}$이고 $a \equiv 0 \pmod 8$이다. a와 prefix도 시드에서 파생된 비밀값으로 보호해야 한다. ↩

7. RFC 8032 §5.1.6. 수식의 해시 입력에 들어가는 $R$과 $A$는 점의 인코딩이다. 해시 출력은 리틀엔디언 정수로 읽는다. 본문은 기본 Ed25519를 다루며, Ed25519ctx·Ed25519ph는 해시 입력 구성이 다르다. ↩

8. RFC 8032 §5.1.7, §8.8. 여인수를 곱한 검증식은 $[8][S]B = [8]R + [8][k]A$다. 규격이 허용하는 선택 차이와 규격상 필수 검사를 빠뜨리는 구현 오류는 구별해야 한다. ↩

9. RFC 7748 §4.1. 체의 크기는 $2^{255}-19$이며, 곡선 위 점의 개수나 서명에서 쓰는 위수 $L$과는 다른 수다. 본문의 합동식은 이 소수 정의에서 바로 나온다. ↩

10. RFC 8032 §3. 트위스티드 에드워즈 식 $ax^2+y^2=1+dx^2y^2$에서는 $a$가 0이 아닌 제곱수이고 $d$는 제곱수가 아니라는 조건을 쓴다. edwards25519가 이 조건을 만족한다. 여기서 곡선 계수 $a$와 본문의 비밀 스칼라 $a$는 같은 기호를 쓰지만 서로 다른 값이다. 다른 곡선 표현에서도 적절한 공식과 구현으로 예외 분기나 부채널을 줄일 수 있다. ↩

11. RFC 8032 §8.1. 비밀에 의존하는 분기와 메모리 접근을 피해야 하며, 문서의 예제 구현은 부채널 누출 방어를 목표로 하지 않는다. ↩

12. RFC 7748 §4.1의 쌍유리 동치와 좌표변환. 모든 아핀 좌표에 같은 식을 그대로 적용할 수 있는 것은 아니며 예외점 처리가 필요하다. ↩

13. RFC 6979와 NIST FIPS 186-5. 결정론적 ECDSA는 검증기와의 호환성을 유지하면서 nonce 생성 방법을 바꾼다. ↩

14. RFC 8032 §8.2. 개인키 생성에는 난수가 필요하다. 여러 서명을 한꺼번에 검증하는 일괄 검증에도 난수가 필요하므로, Ed25519를 쓰는 모든 과정이 난수와 무관한 것은 아니다. ↩

15. RFC 8032 §4, §8.5. 충돌에 대한 추가 방어 성질과 단일 패스 인터페이스의 선택을 설명한다. Ed25519ph는 단순히 Ed25519(SHA-512(M))를 계산하는 것과도 다르다. ↩

16. Poddebniak 외, Attacking Deterministic Signature Schemes Using Fault Attacks, EuroS&P 2018. 고장 주입으로 결정론적 ECDSA·EdDSA를 공격할 수 있는 조건을 분석한다. 비밀 스칼라를 얻으면 원래 시드나 prefix를 복구하지 않아도 서명을 위조할 수 있다. ↩

17. Signal의 XEdDSA 규격과 Hedged ECDSA and EdDSA Signatures 초안. XEdDSA는 nonce 계산에 추가 난수를 넣는다. hedged 변형은 검증식과 호환되더라도 서명 바이트가 매번 같을 필요는 없으므로, 기본 Ed25519의 결정론적 생성과 구분해야 한다. ↩

18. Chalkias, Garillot, Nikolaenko, Taming the many EdDSAs, SSR 2020. 경계 사례의 검증 결과와 일괄·개별 검증의 호환성을 조사한다. 당시 라이브러리의 조사 결과이며 현재 버전 전체의 상태를 뜻하지 않는다. ↩

19. RFC 8032 §8.4. 해시 입력에는 $S$가 없고 $[S+L]B=[S]B$다. 따라서 디코딩한 $S$가 $L$보다 작은지 검사해야 한다. ↩

20. NIST의 FIPS 204 — ML-DSA, FIPS 205 — SLH-DSA, 2024년 8월. 양자컴퓨터 앞에서 Ed25519가 지니는 한계는 RFC 8032 §1에도 명시돼 있다. ↩