PDF 서명을 위한 순수 Pascal NIST 곡선 연산

HotPDF는 순수 Object Pascal로 PDF를 위한 타원 곡선 키 합의와 서명 검증을 수행합니다. 경로 어디에도 OpenSSL 바인딩도, 플랫폼 암호화 provider도 없습니다. 다섯 곡선을 커버합니다. NIST 소수 계열의 P-256, P-384, P-521, 그리고 Montgomery 곡선 키 합의용 X25519와 X448입니다. 그 코드를 링크하지 않고 직접 쓰는 이유는 순수함이 아니라 배포입니다. 실행 파일 하나와 암호화 DLL 없이 배포되는 Delphi 또는 Free Pascal 애플리케이션에는 관리할 버전 불일치도, 플랫폼별로 탐지할 provider도, 고객이 시스템 라이브러리를 패치할 때 달라질 동작도 없습니다

대가는 이제 연산을 직접 소유한다는 것입니다. 큰 정수 모듈러 곱셈은 무자비한 코드입니다. 공개된 테스트 벡터에 대해 바이트 단위로 동일한 결과를 내거나 그럴듯해 보이는 쓰레기를 내거나 둘 중 하나이며, 그 두 상태 사이의 거리가 비교 하나일 수 있습니다. 이 글은 그 비교의 이야기입니다. 버그의 모양이 유한체 연산의 어떤 Pascal 포트에도 일반화되기 때문입니다

PDF 라이브러리가 곡선 연산을 애초에 왜 필요로 하는가

두 기능이 곡선 연산을 끌어들입니다. 첫째는 문서의 공개 키 암호화입니다. ISO 32000 수신자 목록 핸들러가 명명된 인증서를 위해 문서별 키를 래핑하는데, 수신자가 EC 키를 갖고 있으면 래핑은 RSA 키 전송이 아니라 키 합의를 통해 돌아갑니다. ECDH가 없으면 그런 문서를 열 방법이 없습니다. 둘째는 서명 검증입니다. /ByteRange 바이트에 대한 ECDSA 서명 검증은 서명자 곡선 위의 점 곱셈이 필요하고, P-384는 P-256이 목표가 아니라 바닥으로 여겨지는 정부 및 적격 서명 프로파일에서 흔합니다. HotPDF는 이 작업의 결과를 ECDSA 및 CMS 검증 경로와 플러그형 signature-provider 모델을 통해 노출합니다

HotPDF 순수 Pascal 곡선 연산이 쓰이는 곳의 도식: 수신자 목록 ECDH 암호화와 ByteRange에 대한 ECDSA 서명 검증 — 키 합의는 명명된 수신자를 위해 EC 암호화 문서를 열고, 서명 검증은 서명자 곡선 위의 점 곱셈을 필요로 합니다

CIOS, 그리고 마지막의 단 하나의 뺄셈

Montgomery 곱셈은 축약이 시프트가 되는 변환된 도메인에서 작동해 나눗셈을 피합니다. HotPDF가 쓰는 변형은 Coarsely Integrated Operand Scanning으로, 곱셈과 축약을 limb 단위로 섞어 중간값이 modulus 폭에 limb 하나를 더한 것을 넘어 자라지 않게 합니다. 루프 본문은 단순하고 테스트하기 쉽습니다. 꼬리는 그렇지 않습니다. 인터리브 패스가 끝난 뒤 누산기는 modulus의 두 배까지 어디에나 있을 수 있으므로, 알고리즘은 누산기가 소수와 같거나 클 때만 소수 한 복사본을 제거하는 조건부 뺄셈으로 끝납니다

두 다중 limb 수를 비교한다는 것은 borrow를 안고 최상위 limb부터 아래로 걷는 것입니다. 당연해 보이는 쓰법은 누산기 limb을 modulus limb에 들어오는 borrow를 더한 것과 비교하는 것입니다. 그 식은 틀리고, 대부분의 곡선이 숨겨 주는 방식으로 틀립니다

// 틀림: P[I]가 $FFFFFFFFFFFFFFFF일 때 P[I] + Borrow는 넘칠 수 있음
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// 맞음: limb에 절대 더하지 않고 비교합니다
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

borrow 넘침은 실제로 어떤 모습인가

프로덕션에서만 빼고 어디서나 동작하는 곡선처럼 보입니다. P-384와 P-521의 소수는 전부 일인 limb들을 담고 있으므로 P[I]는 $FFFFFFFFFFFFFFFF와 같습니다. 여기에 1의 들어오는 borrow를 더하면 64비트 부호 없는 수가 0으로 넘칩니다. 비교는 그다음 누산기 limb이 0보다 작은지를 묻고, 작지 않다고 판단해 borrow가 필요 없다고 결론 냅니다. 결과의 limb 하나가 1만큼 어긋납니다

HotPDF P-384 연산에서 잘못된 limb 비교와 올바른 borrow 전파를 대조한 Montgomery 축약 borrow 넘침 도식 — 모두 일인 limb에 borrow를 더하면 0으로 넘치므로, P-384와 P-521은 뺄셈을 놓치고 P-256은 결함을 숨깁니다

P-256은 limb 어느 것도 모두 일이 아니므로 벗어납니다. 덧셈이 넘치지 않고 버그 있는 식이 우연히 올바른 식과 일치합니다. 테스트 스위트에 최악의 결과입니다. 가장 많이 테스트된 곡선은 통과하고, 덜 테스트된 곡선들은 피연산자 값에 따라 간헐적으로 실패하며, 실패는 완전히 유효한 문서 위에 "잘못된 서명"이라는 검증 결과로 나타납니다. HotPDF는 정확히 이 이유로 P-384에 명시적 게이트를 달았습니다. 참조 벡터에 대해 연산이 증명될 때까지 틀린 답이 아니라 unavailable 상태를 돌려주었습니다

버그를 실제로 어떻게 찾아냈는가

코드를 읽어서가 아닙니다. 성과를 낸 절차는 기계적이고 재사용 가능합니다. 첫째, 상수를 배제합니다. p, R, R^2의 모든 limb을 독립적으로 재생성해 limb 단위로 비교했고, 이것이 곡선 버그의 단연 가장 흔한 원천을 배제합니다. 둘째, API가 아니라 연산을 계측합니다. 임시 dump procedure가 알려진 점에 대해 R^2, x^3, y^2의 Montgomery 곱셈 중간값을 출력하게 해 독립적으로 계산된 진리와 대조할 수 있게 했습니다

그 비교가 범인을 곧장 가리켰습니다. x 사슬은 처음부터 끝까지 올바른 반면 y^2는 정확히 한 limb에서 정확히 1만큼 달랐습니다. limb 하나의 1 차이는 곱셈 버그도, 캐리 전파 버그도, 상수 버그도 아닙니다. borrow 사슬 버그이며, 루틴 안의 유일한 borrow 사슬은 마지막 조건부 뺄셈입니다. 한 세부가 이것을 거의 탈선시킬 뻔했습니다. dump에 쓴 참조 상수가 첫 시도에서 자체적으로 잘못된 바이트 순서로 작성되어 y 값에 불일치를 만들었고, 잠시 존재하지 않는 두 번째 결함이 있는 것처럼 보였습니다. 진실(ground truth)이 여러분의 코드를 고발하게 하기 전에 그 엔디언을 먼저 검증하십시오

상수를 재생성하고 Montgomery 중간값을 덤프해 미러 진리와 diff하는 방식으로 HotPDF 곡선 버그의 위치를 찾은 흐름도 — 정확히 1인 limb 하나의 차이가 루틴의 유일한 borrow 사슬을 곧장 가렸고, 바이트 스왑된 참조는 하마터면 추적을 잘못 이끌 뻔했습니다

같은 루틴 안의 인접 함정들

그 비교의 몇 줄 안에는 실패 양상이 세 가지 더 살며, 셋 모두 개발 중 어느 시점에는 실제로 살아 있었습니다

// 1. 누산기는 modulus 폭 위에 limb 하나를 더 갖습니다. 하위 L개
//    limb만 비교하면 T가 정확히 p + 2^(64*L)인 경우를 놓치는데,
//    2p가 P-256에서는 2^256을, P-384에서는 2^384를 넘으므로
//    무작위 입력 중 의미 있는 비율에서 일어납니다
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. 일반 다중 limb 뺄셈에도 같은 넘침 위험이 있습니다. Y[I]가
//    $FFFFFFFFFFFFFFFF이면 Y[I] + Borrow는 0으로 넘치고 borrow는
//    지워지는 대신 다음 limb으로 살아남아야 합니다
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

셋째는 코드가 아니라 출처(provenance)입니다. P-521의 소수는 처음에 131개가 아니라 130개의 16진 자릿수로 옮겨 적혀 F 하나가 모자랐고, Montgomery 상수는 그 잘못된 소수에서 계산되었습니다. 상수들은 자기 일관적이면서 함께 틀렸습니다. 곡선 파라미터는 반드시 유도해야 하고 타이핑해서는 안 됩니다. 실제로 쓰는 소수에서 R을 (1 shl (64 * L)) mod p로 계산한 뒤, R * R mod p를 R^2 상수가 주장하는 값과 교차 검증하십시오. 서로 일치하는 상수 쌍은 어느 쪽에 대해서도 아무것도 증명하지 못합니다

한 곡선을 넘어 확장되는 검증 전략

X25519와 X448을 다룰 수 있게 만든 기법은 무한 정수 언어로 미러 구현을 작성하고 Pascal 제어 흐름을 한 줄씩 옮겨 적는 것이었습니다. 미러가 올바른 답을 내고 Pascal이 그렇지 않다면 결함은 전사 실수이며, 양쪽 구현에서 같은 중간값을 찔러 보면 몇 초 안에 찾습니다. RFC 7748 사다리의 세 가지 고전적 실수가 모두 이 방식으로 잡혔습니다. 두 번째 줄이 이미 스왑된 값을 재사용한 상수 시간 스왑, X에 곱하는 대신 z를 마이너스 일 제곱으로 돌려준 마지막 역원, 비트 or로 하프워드 곱을 조립해 캐리를 잃어버린 작은 상수 곱셈입니다

테스트 자료는 텍스트가 아니라 바이트로 받습니다. 텍스트 패턴으로 개인 키를 추출하는 것이, 추출 단계에 전적으로 사는 1바이트 어긋남 오류로 올바른 구현이 고발당하는 경로입니다. DER 인코딩에서 알려진 오프셋으로 16진을 잘라 바이트 배열을 비교하십시오

borrow 사슬이 바로잡힌 뒤 다섯 곡선 모두 공개된 참조 벡터와 바이트 단위로 일치하며, HotPDF는 더 이상 어느 것에도 게이트를 두지 않습니다. 인증서 기반 서명이나 수신자 목록 암호화를 통합하고 있다면 실무적 교훈은 곡선 선택이 이제 능력의 문제가 아니라 정책의 결정이라는 것입니다. 서명 쪽의 프로파일과 바이트 순서 함정은 PAdES 서명 워크스루에서 다룹니다. 컴포넌트 세부와 지원 알고리즘 매트릭스는 HotPDF Delphi PDF component 제품 페이지에 있습니다