nx_p256_scalar_mul_wnaf.nx source
↩ module page · 110 lines · 4614 B
1// nx_p256_scalar_mul_wnaf.nx -- variable-base scalar mult via width-4 wNAF (signed non-adjacent form).
2// For the ECDSA verify's u2*Q (Q varies -> no fixed-base comb). Fewer point additions than the plain
3// binary double-and-add: ~256/(4+1) ~= 51 adds instead of ~128. Precomputes the odd multiples
4// {1,3,5,7}*Q (+ their negatives), recodes the scalar to signed digits, one double + conditional
5// signed add per step. Variable-time is safe for verify (public scalars). Proven bit-identical to
6// p256_scalar_mul by nx_p256_wnaf_difftest over many random scalars. license_tier: ORIGINAL
7import "nx_syscalls.nx"
8import "nx_u256.nx"
9import "nx_p256_field.nx"
10import "nx_p256_point.nx"
11import "nx_p256_point_add.nx"
12
13// out = -p (Jacobian negation: (x, p-y, z)). y in [0,p) -> p-y = -y mod p.
14func p256_point_neg(out: *P256Point, p: *P256Point) -> i64 {
15 let _fm: i64 = nx_scratch_save()
16 p256_point_copy(out, p)
17 let pp: *i64 = u256_alloc()
18 p256_field_load_p(pp)
19 p256_field_sub(out.y, pp, out.y)
20 nx_scratch_restore(_fm)
21 return 0
22}
23
24func p256_scalar_mul_wnaf(out: *P256Point, k_8: *i64, p: *P256Point) -> i64 {
25 let _fm: i64 = nx_scratch_save()
26 let base: *P256Point = p256_point_alloc()
27 p256_point_copy(base, p)
28
29 // odd-multiple table 1,3,5,7 * base and their negatives
30 let twoP: *P256Point = p256_point_alloc()
31 p256_point_double(twoP, base)
32 let T0: *P256Point = p256_point_alloc(); p256_point_copy(T0, base) // 1P
33 let T1: *P256Point = p256_point_alloc(); p256_point_add(T1, twoP, T0) // 3P
34 let T2: *P256Point = p256_point_alloc(); p256_point_add(T2, T1, twoP) // 5P
35 let T3: *P256Point = p256_point_alloc(); p256_point_add(T3, T2, twoP) // 7P
36 let N0: *P256Point = p256_point_alloc(); p256_point_neg(N0, T0)
37 let N1: *P256Point = p256_point_alloc(); p256_point_neg(N1, T1)
38 let N2: *P256Point = p256_point_alloc(); p256_point_neg(N2, T2)
39 let N3: *P256Point = p256_point_alloc(); p256_point_neg(N3, T3)
40
41 // 9-limb mutable copy of the scalar (limb 8 absorbs any k += |d| overflow past 2^256).
42 let kk: *i64 = (sys_mmap(9 * 8)) as *i64
43 var c0: i64 = 0
44 while c0 < 8 { kk[c0] = k_8[c0] & 0xffffffff; c0 = c0 + 1 }
45 kk[8] = 0
46
47 let dig: *i64 = (sys_mmap(264 * 8)) as *i64
48 var nd: i64 = 0
49 // recode: while kk != 0 { if odd: d = signed(kk mod 16); kk -= d; dig=d; kk >>= 1 }
50 var nz: i64 = 1
51 while nz == 1 {
52 nz = 0
53 var z: i64 = 0
54 while z < 9 { if (kk[z] & 0xffffffff) != 0 { nz = 1 } z = z + 1 }
55 if nz == 1 {
56 var d: i64 = 0
57 if (kk[0] & 1) == 1 {
58 d = kk[0] & 15
59 if d >= 8 { d = d - 16 }
60 var c: i64 = 0 - d // add (-d): two's-complement carry/borrow chain
61 var i: i64 = 0
62 while i < 9 {
63 let v: i64 = (kk[i] & 0xffffffff) + c
64 kk[i] = v & 0xffffffff
65 c = v >> 32 // arithmetic >> : -1 = borrow, +1 = carry
66 i = i + 1
67 }
68 }
69 dig[nd] = d
70 nd = nd + 1
71 var carry: i64 = 0 // kk >>= 1 (9 limbs)
72 var j: i64 = 8
73 while j >= 0 {
74 let v: i64 = kk[j] & 0xffffffff
75 let ncar: i64 = v & 1
76 kk[j] = ((v >> 1) | (carry << 31)) & 0xffffffff
77 carry = ncar
78 j = j - 1
79 }
80 }
81 }
82
83 let result: *P256Point = p256_point_alloc()
84 p256_point_zero(result)
85 var i: i64 = nd - 1
86 while i >= 0 {
87 p256_point_double(result, result)
88 let d: i64 = dig[i]
89 if d != 0 {
90 var ad: i64 = d
91 if ad < 0 { ad = 0 - ad }
92 let idx: i64 = (ad - 1) / 2 // 1->0, 3->1, 5->2, 7->3
93 if d > 0 {
94 if idx == 0 { p256_point_add(result, result, T0) }
95 if idx == 1 { p256_point_add(result, result, T1) }
96 if idx == 2 { p256_point_add(result, result, T2) }
97 if idx == 3 { p256_point_add(result, result, T3) }
98 } else {
99 if idx == 0 { p256_point_add(result, result, N0) }
100 if idx == 1 { p256_point_add(result, result, N1) }
101 if idx == 2 { p256_point_add(result, result, N2) }
102 if idx == 3 { p256_point_add(result, result, N3) }
103 }
104 }
105 i = i - 1
106 }
107 p256_point_copy(out, result)
108 nx_scratch_restore(_fm)
109 return 0
110}