bigint — 큰수 모듈러 산술
u64 하나에 들어가지 않는 수를 모듈러 곱하고 거듭제곱한다. RSA 의 2048 비트 수 같은 것이다.
무엇을 약속하고 무엇을 하지 않나
상수 시간을 약속하지 않고 감사받지 않았다. 필요한 만큼만 지었다 — RSA 검증(
s^e mod n)과 곡선 산술에 드는 것뿐이다. 큰수 나눗셈 · 음수 · GCD · 역원은 없다. 지수 e 는 u64 하나다 — RSA 의 공개 지수(보통 65537)를 담으려고 그렇게 좁혔다. 안 지은 것은 틀릴 수도 없다.표현 — 조각 폭은 누산이 정한다. 수는 16 비트 조각(limb) 을 u64 에 담아 리틀엔디언 차례로 늘어놓는다. 곱이 16×16 = 32 비트이고 128 조각을 더해도 239 라 u64 안에서 안전하다. 32 비트 조각을 쓰면 곱이 264 에 닿아 누산이 넘친다. “레지스터가 64 비트니 조각도 64 비트” 는 자연스러워 보이지만 틀린다 — 조각 폭을 정하는 것은 곱이 아니라 누산이다.
| op | 하는 일 | 요구 · 비고 |
|---|---|---|
zero | a 의 앞 k 조각을 0 으로 | a ≥ k |
from_bytes · to_bytes | 빅엔디언 바이트 ↔ 조각 | RSA 의 인코딩 |
from_bytes_le · to_bytes_le | 리틀엔디언 바이트 ↔ 조각 | 곡선 쪽 관례 |
ge_mod | a ≥ n 인가(0 · 1) | k 조각 비교 |
dbl_mod | a ← 2a mod n | R² 를 만드는 데 쓴다 |
mont_mul | out ← a·b·R⁻¹ mod n (CIOS) | t 는 작업 공간 |
n0inv16 | −n⁻¹ mod 2^16 — 몽고메리 상수 | n 의 맨 아래 조각만 받는다 |
mod_exp | out ← bse^e mod n | e 는 u64 · r2·acc·tmp·t 는 작업 공간 |
표 50.1 — bigint 의 op
왜 몽고메리인가 — 나눗셈을 짓지 않으려고. 보통의 모듈러 곱 a·b mod n 에서 mod 는 큰수 나눗셈이다. 몽고메리 곱은 대신 a·b·R⁻¹ mod n 을 내는데 R = 2^(16k) 이라 나누기가 시프트가 된다. 대가로 값을 몽고메리 영역으로 옮겼다 되돌려야 하고 R² mod n 이 필요한데, 그것도 나눗셈 없이 얻는다 — 1 을 2·16k 번 배로 늘리면서(dbl_mod) 넘칠 때마다 n 을 뺀다. 이 모듈의 설계 전체가 이 한 줄이다: 나눗셈을 짓지 않으려고 곱을 바꿨다.
확인하는 것 — 파이썬 정수 산술과의 바이트 대조, RSA-PSS 검증이 끝까지 통하는지(rsa), VM·네이티브 일치. 짓지 않은 것 — 상수 시간, 큰수 나눗셈, 음수, GCD, 모듈러 역원(곡선 쪽 역원은 p256 이 페르마 거듭제곱으로 한다), 아주 큰 e.