bigint32 — 큰수 모듈러 산술(32 비트 조각)
u64 하나에 들어가지 않는 수를 모듈러 곱하고 거듭제곱한다. RSA 의 2048 비트 수 같은 것이다.
무엇을 약속하고 무엇을 하지 않나
s^e mod n)과 곡선 산술에 드는 것뿐이다. 큰수 나눗셈 · 음수 · GCD · 역원은 없다. 지수 e 는 u64 하나다 — RSA 의 공개 지수(보통 65537)를 담으려고 그렇게 좁혔다. 안 지은 것은 틀릴 수도 없다.같은 모듈이 셋 있다 — 조각 폭만 다르다. bigint16 · bigint32 · bigint64 는 op 의 이름과 입력이 모두 같고, 수를 몇 비트 조각으로 나눠 담는지만 다르다. 부르는 쪽은 use 한 줄만 바꿔 폭을 고른다. 넷째 bigint 는 같은 op 을 내놓되 폭을 기계가 고른다(대상의 조각 폭 · --limb-bits) — 표준 라이브러리의 rsa · p256 · p384 · ecdsa · ed25519 가 그것을 쓴다(2026-10-23 부터, RFC-0152). 2026-10-22 까지는 bigint 라는 이름의 한 모듈(16 비트 조각 → 같은 날 32 비트)이었다.
| 모듈 | 조각 | x86-64 | 쓸 자리 |
|---|---|---|---|
bigint16 | 16 비트 | 0.71 초 | 곱셈기가 좁은 기계(8 · 16 비트 CPU) — 그런 기계에서는 아직 재지 않았다 |
bigint32 | 32 비트 | 0.22 초 | 곱셈기가 32 비트인 기계(cortex_m · mips_be · cheriot 에서 bigint 가 고른다) |
bigint64 | 64 비트 | 0.12 초 | 64 비트 기계(bigint 가 고른다). 32 비트 빌드(x86 -m32)에서도 bigint32 보다 1.35 배 빨랐다 |
표 50.1 — 세 폭 — RSA-2048 거듭제곱 300 번, 네이티브 -O2(2026-10-22 잼)
크기는 바이트로 말한다. 모든 op 은 조각 수가 아니라 수의 바이트 수 nb 를 받는다(RSA-2048 은 256 · P-256 은 32 · P-384 는 48). 조각 수는 모듈 안에서만 안다 — limbs nb. 가 그 수다. 그래서 폭을 바꿔도 부르는 글이 깨지지 않는다. 수 하나는 limbs nb. 칸, 작업 공간 t 는 그보다 2 칸 더 든다. ⌈nb / 2⌉ + 2 칸을 잡아 두면 세 폭 어디에나 맞는다.
표현 — 조각 폭은 누산이 정한다. 수는 32 비트 조각(limb) 을 u64 에 담아 리틀엔디언 차례로 늘어놓는다. 몽고메리 곱은 곱 하나마다 바로 올림을 넘기므로 한 칸의 합은 (232−1) + (232−1)2 + (232−1) = 264 − 1 — u64 에 꼭 든다. 넘치면 add 가 멈추므로 셈이 틀렸다면 그 자리에서 드러난다.
| op | 하는 일 | 요구 · 비고 |
|---|---|---|
limbs | nb 바이트짜리 수의 조각 수 | ⌈nb / 조각 바이트⌉ |
zero | a 의 수를 0 으로 | a 는 limbs nb. 칸 이상 |
from_bytes · to_bytes | 빅엔디언 바이트 ↔ 조각 | RSA 의 인코딩 · 바이트 수는 nb 이하(모자란 위쪽은 0) · from_bytes 는 nb 를 돌려준다 |
from_bytes_le · to_bytes_le | 리틀엔디언 바이트 32 개 ↔ 조각 | 곡선 쪽 관례 · 32 를 돌려준다 |
ge_mod | a ≥ n 인가(0 · 1) | |
dbl_mod | a ← 2a mod n | R² 를 만드는 데 쓴다 |
mont_mul | out ← a·b·R⁻¹ mod n (CIOS) | t 는 작업 공간 · 몽고메리 상수는 n0inv 가 낸다 |
n0inv | −n⁻¹ mod 2^(조각 폭) — 몽고메리 상수 | n 은 홀수 |
mod_exp | out ← bse^e mod n | e 는 u64 · r2·acc·tmp·t 는 작업 공간 |
add_mod · sub_mod | o ← (a ± b) mod m | a, b 는 m 보다 작다 · o 는 a 나 b 와 같은 칸이어도 된다(2026-10-23) |
is_zero · equal | 0 인가 · 두 수가 같은가(0 · 1) | 2026-10-23 |
bit | 수의 i 번째 비트 | 0 이 가장 낮다 · 2026-10-23 |
표 50.2 — bigint16 · bigint32 · bigint64 의 op (셋이 같다)
폭을 고르는 타입 limb — 네 모듈이 저마다 트레이트 bigwidth.width 를 갖춘 타입 limb 을 낸다. 폭을 받는 라이브러리 op 에 bigint32.limb. 을 넘기면 그 한 번만 32 비트 조각으로 셈한다(rsa.verify_pss_by …).
bigint64 에는 하나가 더 있다 — 곱의 윗말 mul_hi.
왜 몽고메리인가 — 나눗셈을 짓지 않으려고. 보통의 모듈러 곱 a·b mod n 에서 mod 는 큰수 나눗셈이다. 몽고메리 곱은 대신 a·b·R⁻¹ mod n 을 내는데 R = 2^(32k) 이라 나누기가 시프트가 된다. 대가로 값을 몽고메리 영역으로 옮겼다 되돌려야 하고 R² mod n 이 필요한데, 그것도 나눗셈 없이 얻는다 — n 의 맨 윗 비트 자리의 수를 몇 번 배로 늘리고(dbl_mod, 넘칠 때마다 n 을 뺀다) 몽고메리 제곱을 몇 번 하면 된다(RSA-2048 에서 두 배 257 번 · 제곱 세 번 — 전엔 두 배 4,096 번). 이 모듈의 설계 전체가 이 한 줄이다: 나눗셈을 짓지 않으려고 곱을 바꿨다.
확인하는 것 — 세 폭이 파이썬 정수 산술과 바이트까지 같은지(크기 9 · 17 · 32 · 33 · 48 · 100 · 255 · 256 바이트, VM · 네이티브), RSA-PSS 검증이 끝까지 통하는지(rsa). 짓지 않은 것 — 상수 시간, 큰수 나눗셈, 음수, GCD, 모듈러 역원(곡선 쪽 역원은 p256 이 페르마 거듭제곱으로 한다), 아주 큰 e.