nx_p256_point.nx source
↩ module page · 382 lines · 12252 B
1// nx_p256_point.nx -- NIST P-256 elliptic-curve point operations.
2//
3// Phase 0b §I.3 piece 2 of the ECDSA-P256 arc:
4// ✓ 0. u256 big-int (6ff89dd8)
5// ✓ 1. p256_field add/sub/neg (133f16a1)
6// ✓ 1b. u256 wide multiplication (ddb0994a)
7// ✓ 1c. p256_field mul + sq (d295c0a3)
8// ✓ 1d. p256_field inverse (48e8e69d)
9// ✓ 2. p256_point: struct + zero + set_affine + on_curve +
10// to_affine + double (THIS commit)
11// - 2b. p256_point_add (queued -- own commit, complex)
12// - 2c. p256_scalar_mul (queued)
13// - 3. p256_scalar mod n (queued)
14// - 4. ecdsa_p256 verify (queued)
15//
16// Curve (FIPS 186-5 §D.2.4):
17// y^2 = x^3 + a*x + b (mod p)
18// a = -3
19// b = 0x5AC635D8 AA3A93E7 B3EBBD55 769886BC
20// 651D06B0 CC53B0F6 3BCE3C3E 27D2604B
21// G = (Gx, Gy) -- base point of order n
22// p = NIST P-256 prime (see nx_p256_field)
23//
24// Internal representation: Jacobian projective coordinates.
25// Affine (x, y) <-> Jacobian (X, Y, Z) where x = X/Z^2, y = Y/Z^3
26// Point at infinity O: Z = 0 (canonical: X = Y = 1, Z = 0)
27//
28// Why Jacobian:
29// - point_double: 4 mults + 4 squares + ~10 add/sub
30// (vs affine: 2 mults + 2 squares + 1 INVERT which is ~30 mults
31// via Fermat; Jacobian skips the invert per doubling)
32// - point_add: 12 mults + 4 squares (still no invert)
33// - Invert deferred to once at the end via point_to_affine
34//
35// Public API (this commit):
36// P256Point struct {x: *i64, y: *i64, z: *i64}
37// p256_point_alloc() -- zero/infinity
38// p256_point_zero(p) -- set to infinity
39// p256_point_copy(dst, src)
40// p256_point_is_infinity(p) -> 0|1
41// p256_point_set_affine(p, x, y) -- Z = 1 in Jacobian
42// p256_point_load_b(out) -- the curve constant b
43// p256_point_load_g(out_g) -- the base point G
44// p256_point_on_curve(p) -> 0|1 -- affine on-curve check
45// p256_point_to_affine(p) -- in-place: Z != 0 -> Z = 1
46// p256_point_double(out, in) -- out = 2 * in
47// p256_point_eq(a, b) -> 0|1 -- equality (auto-affines)
48// nx_p256_point_verdict_is_valid(v)
49//
50// What is NOT shipped here (queued for follow-up commits):
51// - p256_point_add (Jacobian + Jacobian -> Jacobian)
52// - p256_scalar_mul (k * P via double-and-add)
53// - Constant-time guarantees (ECDSA verify is variable-time-safe)
54//
55// Per Cardinals 9 (single-responsibility -- this commit ships point
56// representation + doubling + on-curve + to-affine; addition is its
57// own complex primitive in its own commit) and 22 (composition --
58// every point op composes the shipped field arithmetic).
59//
60// license_tier: INDEPENDENT_REDERIVE
61// genealogy_id: international-research-sources/nist/fips_186_5 + sec_g/sec1_v2
62// lineage_id: nishi_p256_point_q10
63
64// nx_safety_envelope:
65// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
66// sil_target: SIL1
67// evidence: [bulk_applied_2026-05-19, p256-point-jacobian]
68// verdict: NOT_YET_EVALUATED
69
70import "nx_syscalls.nx"
71import "nx_u256.nx"
72import "nx_p256_field.nx"
73import "nx_p256_field_mul.nx"
74import "nx_p256_field_inv.nx"
75
76struct P256Point {
77 x: *i64,
78 y: *i64,
79 z: *i64,
80}
81
82const NX_P256_POINT_OK: i64 = 1
83const NX_P256_POINT_BAD: i64 = 2
84const NX_P256_POINT_VERDICT_N: i64 = 3
85
86func nx_p256_point_verdict_is_valid(v: i64) -> i64 {
87 if v < NX_P256_POINT_OK { return 0 }
88 if v >= NX_P256_POINT_VERDICT_N { return 0 }
89 return 1
90}
91
92// Allocate a new point, initialised to infinity (Z = 0).
93func p256_point_alloc() -> *P256Point {
94 let raw: *u8 = nx_scratch(24)
95 let p: *P256Point = raw as *P256Point
96 p.x = u256_alloc()
97 p.y = u256_alloc()
98 p.z = u256_alloc()
99 p256_field_one(p.x)
100 p256_field_one(p.y)
101 p256_field_zero(p.z)
102 return p
103}
104
105// Set the point to the canonical infinity representation (1, 1, 0).
106func p256_point_zero(p: *P256Point) -> i64 {
107 p256_field_one(p.x)
108 p256_field_one(p.y)
109 p256_field_zero(p.z)
110 return 0
111}
112
113// Returns 1 if Z == 0 (infinity), else 0.
114func p256_point_is_infinity(p: *P256Point) -> i64 {
115 return u256_is_zero(p.z)
116}
117
118// dst := src (component-wise copy).
119func p256_point_copy(dst: *P256Point, src: *P256Point) -> i64 {
120 u256_copy(dst.x, src.x)
121 u256_copy(dst.y, src.y)
122 u256_copy(dst.z, src.z)
123 return 0
124}
125
126// Set p to the affine (x, y) point: Jacobian (X = x, Y = y, Z = 1).
127func p256_point_set_affine(p: *P256Point, x: *i64, y: *i64) -> i64 {
128 u256_copy(p.x, x)
129 u256_copy(p.y, y)
130 p256_field_one(p.z)
131 return 0
132}
133
134// Write the curve constant b into out.
135// b = 0x5AC635D8 AA3A93E7 B3EBBD55 769886BC
136// 651D06B0 CC53B0F6 3BCE3C3E 27D2604B
137// LE limb layout (limb[0] = LSB):
138// limb[0] = 0x27D2604B
139// limb[1] = 0x3BCE3C3E
140// limb[2] = 0xCC53B0F6
141// limb[3] = 0x651D06B0
142// limb[4] = 0x769886BC
143// limb[5] = 0xB3EBBD55
144// limb[6] = 0xAA3A93E7
145// limb[7] = 0x5AC635D8
146func p256_point_load_b(out: *i64) -> i64 {
147 out[0] = 0x27D2604B
148 out[1] = 0x3BCE3C3E
149 out[2] = 0xCC53B0F6
150 out[3] = 0x651D06B0
151 out[4] = 0x769886BC
152 out[5] = 0xB3EBBD55
153 out[6] = 0xAA3A93E7
154 out[7] = 0x5AC635D8
155 return 0
156}
157
158// Write the base point G into out_g (with Z = 1).
159// Gx = 0x6B17D1F2 E12C4247 F8BCE6E5 63A440F2
160// 77037D81 2DEB33A0 F4A13945 D898C296
161// Gy = 0x4FE342E2 FE1A7F9B 8EE7EB4A 7C0F9E16
162// 2BCE3357 6B315ECE CBB64068 37BF51F5
163func p256_point_load_g(out_g: *P256Point) -> i64 {
164 out_g.x[0] = 0xD898C296
165 out_g.x[1] = 0xF4A13945
166 out_g.x[2] = 0x2DEB33A0
167 out_g.x[3] = 0x77037D81
168 out_g.x[4] = 0x63A440F2
169 out_g.x[5] = 0xF8BCE6E5
170 out_g.x[6] = 0xE12C4247
171 out_g.x[7] = 0x6B17D1F2
172
173 out_g.y[0] = 0x37BF51F5
174 out_g.y[1] = 0xCBB64068
175 out_g.y[2] = 0x6B315ECE
176 out_g.y[3] = 0x2BCE3357
177 out_g.y[4] = 0x7C0F9E16
178 out_g.y[5] = 0x8EE7EB4A
179 out_g.y[6] = 0xFE1A7F9B
180 out_g.y[7] = 0x4FE342E2
181
182 p256_field_one(out_g.z)
183 return 0
184}
185
186// Verify an AFFINE point (with Z = 1) satisfies y^2 = x^3 - 3x + b.
187// Returns 1 if on curve, 0 otherwise. Infinity is treated as
188// on-curve (returns 1).
189//
190// Caller MUST normalize to affine via p256_point_to_affine first
191// if the point came from Jacobian arithmetic; otherwise this check
192// is undefined.
193func p256_point_on_curve(p: *P256Point) -> i64 {
194 if p256_point_is_infinity(p) == 1 { return 1 }
195
196 let _fm: i64 = nx_scratch_save()
197 let x: *i64 = u256_alloc()
198 let y: *i64 = u256_alloc()
199 u256_copy(x, p.x)
200 u256_copy(y, p.y)
201
202 // LHS: y^2
203 let lhs: *i64 = u256_alloc()
204 p256_field_sq(lhs, y)
205
206 // RHS: x^3 - 3x + b
207 let x2: *i64 = u256_alloc()
208 let x3: *i64 = u256_alloc()
209 p256_field_sq(x2, x)
210 p256_field_mul(x3, x2, x)
211 // 3x = x + x + x
212 let three_x: *i64 = u256_alloc()
213 p256_field_add(three_x, x, x)
214 p256_field_add(three_x, three_x, x)
215 // rhs = x^3 - 3x + b
216 let b: *i64 = u256_alloc()
217 p256_point_load_b(b)
218 let rhs: *i64 = u256_alloc()
219 p256_field_sub(rhs, x3, three_x)
220 p256_field_add(rhs, rhs, b)
221
222 let _r: i64 = p256_field_eq(lhs, rhs)
223 nx_scratch_restore(_fm)
224 return _r
225}
226
227// Convert Jacobian (X, Y, Z) to canonical affine (x, y, 1) in place.
228// If Z == 0 (infinity): no-op (canonical infinity already (1,1,0))
229// Else:
230// z_inv = Z^(-1)
231// z_inv2 = z_inv^2
232// z_inv3 = z_inv2 * z_inv
233// x_new = X * z_inv2
234// y_new = Y * z_inv3
235// Z_new = 1
236func p256_point_to_affine(p: *P256Point) -> i64 {
237 if p256_point_is_infinity(p) == 1 { return 0 }
238
239 let _fm: i64 = nx_scratch_save()
240 let z_inv: *i64 = u256_alloc()
241 let z_inv2: *i64 = u256_alloc()
242 let z_inv3: *i64 = u256_alloc()
243 p256_field_inv(z_inv, p.z)
244 p256_field_sq(z_inv2, z_inv)
245 p256_field_mul(z_inv3, z_inv2, z_inv)
246
247 p256_field_mul(p.x, p.x, z_inv2)
248 p256_field_mul(p.y, p.y, z_inv3)
249 p256_field_one(p.z)
250 nx_scratch_restore(_fm)
251 return 0
252}
253
254// Equality test that auto-normalizes via clone-and-to-affine.
255// Inputs unchanged; comparison after both normalized.
256//
257// Edge cases:
258// - Both infinity: equal (1)
259// - One infinity, other not: not equal (0)
260// - Neither infinity: compare affine x and y after to_affine
261func p256_point_eq(a: *P256Point, b: *P256Point) -> i64 {
262 let a_inf: i64 = p256_point_is_infinity(a)
263 let b_inf: i64 = p256_point_is_infinity(b)
264 if a_inf == 1 {
265 if b_inf == 1 { return 1 }
266 return 0
267 }
268 if b_inf == 1 { return 0 }
269
270 let _fm: i64 = nx_scratch_save()
271 let ac: *P256Point = p256_point_alloc()
272 let bc: *P256Point = p256_point_alloc()
273 p256_point_copy(ac, a)
274 p256_point_copy(bc, b)
275 p256_point_to_affine(ac)
276 p256_point_to_affine(bc)
277 if p256_field_eq(ac.x, bc.x) != 1 {
278 nx_scratch_restore(_fm)
279 return 0
280 }
281 if p256_field_eq(ac.y, bc.y) != 1 {
282 nx_scratch_restore(_fm)
283 return 0
284 }
285 nx_scratch_restore(_fm)
286 return 1
287}
288
289// out = 2 * in. Jacobian doubling with a = -3 special form (SEC 1
290// v2.0 §2.2.1.3, optimized for the NIST P curves where a = -3
291// permits the M = 3*(X-Z^2)*(X+Z^2) factorization instead of the
292// generic 3*X^2 + a*Z^4).
293//
294// if Z1 == 0: return infinity
295// if Y1 == 0: return infinity (cannot double a 2-torsion point;
296// P-256 has no points of order 2 in
297// practice, but defensive)
298// delta = Z1^2
299// gamma = Y1^2
300// beta = X1 * gamma
301// alpha = 3 * (X1 - delta) * (X1 + delta)
302// X3 = alpha^2 - 8 * beta
303// Z3 = (Y1 + Z1)^2 - gamma - delta
304// Y3 = alpha * (4 * beta - X3) - 8 * gamma^2
305//
306// Aliasing-safe: out may equal in (we snapshot input into locals).
307func p256_point_double(out: *P256Point, in_pt: *P256Point) -> i64 {
308 if p256_point_is_infinity(in_pt) == 1 {
309 p256_point_zero(out)
310 return 0
311 }
312 if u256_is_zero(in_pt.y) == 1 {
313 p256_point_zero(out)
314 return 0
315 }
316
317 let _fm: i64 = nx_scratch_save()
318 let X1: *i64 = u256_alloc()
319 let Y1: *i64 = u256_alloc()
320 let Z1: *i64 = u256_alloc()
321 u256_copy(X1, in_pt.x)
322 u256_copy(Y1, in_pt.y)
323 u256_copy(Z1, in_pt.z)
324
325 let delta: *i64 = u256_alloc()
326 let gamma: *i64 = u256_alloc()
327 let beta: *i64 = u256_alloc()
328 let alpha: *i64 = u256_alloc()
329 let tmp1: *i64 = u256_alloc()
330 let tmp2: *i64 = u256_alloc()
331
332 p256_field_sq(delta, Z1) // delta = Z1^2
333 p256_field_sq(gamma, Y1) // gamma = Y1^2
334 p256_field_mul(beta, X1, gamma) // beta = X1 * gamma
335
336 // alpha = 3 * (X1 - delta) * (X1 + delta)
337 p256_field_sub(tmp1, X1, delta)
338 p256_field_add(tmp2, X1, delta)
339 p256_field_mul(alpha, tmp1, tmp2)
340 // alpha *= 3
341 p256_field_add(tmp1, alpha, alpha) // 2*alpha
342 p256_field_add(alpha, tmp1, alpha) // 3*alpha
343
344 // X3 = alpha^2 - 8 * beta
345 let X3: *i64 = u256_alloc()
346 p256_field_sq(X3, alpha)
347 p256_field_add(tmp1, beta, beta) // 2*beta
348 p256_field_add(tmp1, tmp1, tmp1) // 4*beta
349 p256_field_add(tmp2, tmp1, tmp1) // 8*beta
350 p256_field_sub(X3, X3, tmp2)
351
352 // Z3 = (Y1 + Z1)^2 - gamma - delta
353 let Z3: *i64 = u256_alloc()
354 p256_field_add(tmp1, Y1, Z1)
355 p256_field_sq(tmp2, tmp1)
356 p256_field_sub(tmp2, tmp2, gamma)
357 p256_field_sub(Z3, tmp2, delta)
358
359 // Y3 = alpha * (4*beta - X3) - 8 * gamma^2
360 let Y3: *i64 = u256_alloc()
361 p256_field_add(tmp1, beta, beta) // 2*beta
362 p256_field_add(tmp1, tmp1, tmp1) // 4*beta
363 p256_field_sub(tmp1, tmp1, X3) // 4*beta - X3
364 p256_field_mul(Y3, alpha, tmp1)
365 // tmp2 = 8 * gamma^2
366 p256_field_sq(tmp1, gamma)
367 p256_field_add(tmp2, tmp1, tmp1) // 2*gamma^2
368 p256_field_add(tmp2, tmp2, tmp2) // 4*gamma^2
369 p256_field_add(tmp2, tmp2, tmp2) // 8*gamma^2
370 p256_field_sub(Y3, Y3, tmp2)
371
372 u256_copy(out.x, X3)
373 u256_copy(out.y, Y3)
374 u256_copy(out.z, Z3)
375 nx_scratch_restore(_fm)
376 return 0
377}
378
379// Compile-only smoke. Real KAT in nx_p256_point_test.nx.
380func main() -> i64 {
381 return 0
382}