1use core::cmp::min;
2use core::ops::{Add, Sub};
3
4use super::error::*;
5use super::field25519::*;
6
7#[derive(Clone, Copy)]
8pub struct GeP2 {
9 x: Fe,
10 y: Fe,
11 z: Fe,
12}
13
14#[derive(Clone, Copy)]
15pub struct GeP3 {
16 x: Fe,
17 y: Fe,
18 z: Fe,
19 t: Fe,
20}
21
22#[derive(Clone, Copy, Default)]
23pub struct GeP1P1 {
24 x: Fe,
25 y: Fe,
26 z: Fe,
27 t: Fe,
28}
29
30#[derive(Clone, Copy)]
31pub struct GePrecomp {
32 y_plus_x: Fe,
33 y_minus_x: Fe,
34 xy2d: Fe,
35}
36
37#[derive(Clone, Copy, Default)]
38pub struct GeCached {
39 y_plus_x: Fe,
40 y_minus_x: Fe,
41 z: Fe,
42 t2d: Fe,
43}
44
45impl GeCached {
46 pub fn maybe_set(&mut self, other: &GeCached, do_swap: u8) {
47 self.y_plus_x.maybe_set(&other.y_plus_x, do_swap);
48 self.y_minus_x.maybe_set(&other.y_minus_x, do_swap);
49 self.z.maybe_set(&other.z, do_swap);
50 self.t2d.maybe_set(&other.t2d, do_swap);
51 }
52}
53
54impl GeP1P1 {
55 fn to_p2(&self) -> GeP2 {
56 GeP2 {
57 x: self.x * self.t,
58 y: self.y * self.z,
59 z: self.z * self.t,
60 }
61 }
62
63 fn to_p3(&self) -> GeP3 {
64 GeP3 {
65 x: self.x * self.t,
66 y: self.y * self.z,
67 z: self.z * self.t,
68 t: self.x * self.y,
69 }
70 }
71}
72
73impl From<GeP2> for GeP3 {
74 fn from(p: GeP2) -> GeP3 {
75 GeP3 {
76 x: p.x,
77 y: p.y,
78 z: p.z,
79 t: p.x * p.y,
80 }
81 }
82}
83
84impl GeP2 {
85 fn zero() -> GeP2 {
86 GeP2 {
87 x: FE_ZERO,
88 y: FE_ONE,
89 z: FE_ONE,
90 }
91 }
92
93 fn dbl(&self) -> GeP1P1 {
94 let xx = self.x.square();
95 let yy = self.y.square();
96 let b = self.z.square_and_double();
97 let a = self.x + self.y;
98 let aa = a.square();
99 let y3 = yy + xx;
100 let z3 = yy - xx;
101 let x3 = aa - y3;
102 let t3 = b - z3;
103
104 GeP1P1 {
105 x: x3,
106 y: y3,
107 z: z3,
108 t: t3,
109 }
110 }
111
112 fn slide(a: &[u8]) -> [i8; 256] {
113 let mut r = [0i8; 256];
114 for i in 0..256 {
115 r[i] = (1 & (a[i >> 3] >> (i & 7))) as i8;
116 }
117 for i in 0..256 {
118 if r[i] != 0 {
119 for b in 1..min(7, 256 - i) {
120 if r[i + b] != 0 {
121 if r[i] + (r[i + b] << b) <= 15 {
122 r[i] += r[i + b] << b;
123 r[i + b] = 0;
124 } else if r[i] - (r[i + b] << b) >= -15 {
125 r[i] -= r[i + b] << b;
126 for k in i + b..256 {
127 if r[k] == 0 {
128 r[k] = 1;
129 break;
130 }
131 r[k] = 0;
132 }
133 } else {
134 break;
135 }
136 }
137 }
138 }
139 }
140
141 r
142 }
143
144 #[allow(clippy::comparison_chain)]
145 pub fn double_scalarmult_vartime(a_scalar: &[u8], a_point: GeP3, b_scalar: &[u8]) -> GeP2 {
146 let aslide = GeP2::slide(a_scalar);
147 let bslide = GeP2::slide(b_scalar);
148
149 let mut ai = [GeCached {
150 y_plus_x: FE_ZERO,
151 y_minus_x: FE_ZERO,
152 z: FE_ZERO,
153 t2d: FE_ZERO,
154 }; 8]; ai[0] = a_point.to_cached();
156 let a2 = a_point.dbl().to_p3();
157 ai[1] = (a2 + ai[0]).to_p3().to_cached();
158 ai[2] = (a2 + ai[1]).to_p3().to_cached();
159 ai[3] = (a2 + ai[2]).to_p3().to_cached();
160 ai[4] = (a2 + ai[3]).to_p3().to_cached();
161 ai[5] = (a2 + ai[4]).to_p3().to_cached();
162 ai[6] = (a2 + ai[5]).to_p3().to_cached();
163 ai[7] = (a2 + ai[6]).to_p3().to_cached();
164
165 let mut r = GeP2::zero();
166
167 let mut i: usize = 255;
168 loop {
169 if aslide[i] != 0 || bslide[i] != 0 {
170 break;
171 }
172 if i == 0 {
173 return r;
174 }
175 i -= 1;
176 }
177
178 loop {
179 let mut t = r.dbl();
180 if aslide[i] > 0 {
181 t = t.to_p3() + ai[(aslide[i] / 2) as usize];
182 } else if aslide[i] < 0 {
183 t = t.to_p3() - ai[(-aslide[i] / 2) as usize];
184 }
185
186 if bslide[i] > 0 {
187 t = t.to_p3() + BI[(bslide[i] / 2) as usize];
188 } else if bslide[i] < 0 {
189 t = t.to_p3() - BI[(-bslide[i] / 2) as usize];
190 }
191
192 r = t.to_p2();
193
194 if i == 0 {
195 return r;
196 }
197 i -= 1;
198 }
199 }
200}
201
202impl GeP3 {
203 pub fn from_bytes_negate_vartime(s: &[u8; 32]) -> Option<GeP3> {
204 let y = Fe::from_bytes(s);
205 let z = FE_ONE;
206 let y_squared = y.square();
207 let u = y_squared - FE_ONE;
208 let v = (y_squared * FE_D) + FE_ONE;
209 let mut x = (u * v).pow25523() * u;
210
211 let vxx = x.square() * v;
212 let check = vxx - u;
213 if !check.is_zero() {
214 let check2 = vxx + u;
215 if !check2.is_zero() {
216 return None;
217 }
218 x = x * FE_SQRTM1;
219 }
220
221 if x.is_negative() == ((s[31] >> 7) != 0) {
222 x = x.neg();
223 }
224
225 let t = x * y;
226
227 Some(GeP3 { x, y, z, t })
228 }
229
230 pub fn from_bytes_vartime(s: &[u8; 32]) -> Option<GeP3> {
231 Self::from_bytes_negate_vartime(s).map(|p| GeP3 {
232 x: p.x.neg(),
233 y: p.y,
234 z: p.z,
235 t: p.t.neg(),
236 })
237 }
238
239 fn to_p2(&self) -> GeP2 {
240 GeP2 {
241 x: self.x,
242 y: self.y,
243 z: self.z,
244 }
245 }
246
247 fn to_cached(&self) -> GeCached {
248 GeCached {
249 y_plus_x: self.y + self.x,
250 y_minus_x: self.y - self.x,
251 z: self.z,
252 t2d: self.t * FE_D2,
253 }
254 }
255
256 fn zero() -> GeP3 {
257 GeP3 {
258 x: FE_ZERO,
259 y: FE_ONE,
260 z: FE_ONE,
261 t: FE_ZERO,
262 }
263 }
264
265 fn dbl(&self) -> GeP1P1 {
266 self.to_p2().dbl()
267 }
268
269 pub fn to_bytes(&self) -> [u8; 32] {
270 let recip = self.z.invert();
271 let x = self.x * recip;
272 let y = self.y * recip;
273 let mut bs = y.to_bytes();
274 bs[31] ^= (if x.is_negative() { 1 } else { 0 }) << 7;
275 bs
276 }
277
278 pub fn has_small_order(&self) -> bool {
279 let recip = self.z.invert();
280 let x = self.x * recip;
281 let y = self.y * recip;
282 let x_neg = x.neg();
283 let y_sqrtm1 = y * FE_SQRTM1;
284 x.is_zero() | y.is_zero() | (y_sqrtm1 == x) | (y_sqrtm1 == x_neg)
285 }
286}
287
288impl Add<GeP3> for GeP3 {
289 type Output = GeP3;
290
291 fn add(self, other: GeP3) -> GeP3 {
292 (self + other.to_cached()).to_p3()
293 }
294}
295
296impl Sub<GeP3> for GeP3 {
297 type Output = GeP3;
298
299 fn sub(self, other: GeP3) -> GeP3 {
300 (self - other.to_cached()).to_p3()
301 }
302}
303
304impl Add<GeCached> for GeP3 {
305 type Output = GeP1P1;
306
307 fn add(self, _rhs: GeCached) -> GeP1P1 {
308 let y1_plus_x1 = self.y + self.x;
309 let y1_minus_x1 = self.y - self.x;
310 let a = y1_plus_x1 * _rhs.y_plus_x;
311 let b = y1_minus_x1 * _rhs.y_minus_x;
312 let c = _rhs.t2d * self.t;
313 let zz = self.z * _rhs.z;
314 let d = zz + zz;
315 let x3 = a - b;
316 let y3 = a + b;
317 let z3 = d + c;
318 let t3 = d - c;
319
320 GeP1P1 {
321 x: x3,
322 y: y3,
323 z: z3,
324 t: t3,
325 }
326 }
327}
328
329impl Add<GePrecomp> for GeP3 {
330 type Output = GeP1P1;
331
332 fn add(self, _rhs: GePrecomp) -> GeP1P1 {
333 let y1_plus_x1 = self.y + self.x;
334 let y1_minus_x1 = self.y - self.x;
335 let a = y1_plus_x1 * _rhs.y_plus_x;
336 let b = y1_minus_x1 * _rhs.y_minus_x;
337 let c = _rhs.xy2d * self.t;
338 let d = self.z + self.z;
339 let x3 = a - b;
340 let y3 = a + b;
341 let z3 = d + c;
342 let t3 = d - c;
343
344 GeP1P1 {
345 x: x3,
346 y: y3,
347 z: z3,
348 t: t3,
349 }
350 }
351}
352
353impl Sub<GeCached> for GeP3 {
354 type Output = GeP1P1;
355
356 fn sub(self, _rhs: GeCached) -> GeP1P1 {
357 let y1_plus_x1 = self.y + self.x;
358 let y1_minus_x1 = self.y - self.x;
359 let a = y1_plus_x1 * _rhs.y_minus_x;
360 let b = y1_minus_x1 * _rhs.y_plus_x;
361 let c = _rhs.t2d * self.t;
362 let zz = self.z * _rhs.z;
363 let d = zz + zz;
364 let x3 = a - b;
365 let y3 = a + b;
366 let z3 = d - c;
367 let t3 = d + c;
368
369 GeP1P1 {
370 x: x3,
371 y: y3,
372 z: z3,
373 t: t3,
374 }
375 }
376}
377
378impl Sub<GePrecomp> for GeP3 {
379 type Output = GeP1P1;
380
381 fn sub(self, _rhs: GePrecomp) -> GeP1P1 {
382 let y1_plus_x1 = self.y + self.x;
383 let y1_minus_x1 = self.y - self.x;
384 let a = y1_plus_x1 * _rhs.y_minus_x;
385 let b = y1_minus_x1 * _rhs.y_plus_x;
386 let c = _rhs.xy2d * self.t;
387 let d = self.z + self.z;
388 let x3 = a - b;
389 let y3 = a + b;
390 let z3 = d - c;
391 let t3 = d + c;
392
393 GeP1P1 {
394 x: x3,
395 y: y3,
396 z: z3,
397 t: t3,
398 }
399 }
400}
401
402fn ge_precompute(base: &GeP3) -> [GeCached; 16] {
403 let base_cached = base.to_cached();
404 let mut pc = [GeP3::zero(); 16];
405 pc[1] = *base;
406 for i in 2..16 {
407 pc[i] = if i % 2 == 0 {
408 pc[i / 2].dbl().to_p3()
409 } else {
410 pc[i - 1].add(base_cached).to_p3()
411 }
412 }
413 let mut pc_cached: [GeCached; 16] = Default::default();
414 for i in 0..16 {
415 pc_cached[i] = pc[i].to_cached();
416 }
417 pc_cached
418}
419
420pub fn ge_scalarmult(scalar: &[u8], base: &GeP3) -> GeP3 {
421 let pc = ge_precompute(base);
422 let mut q = GeP3::zero();
423 let mut pos = 252;
424 loop {
425 let slot = ((scalar[pos >> 3] >> (pos & 7)) & 15) as usize;
426 let mut t = pc[0];
427 for i in 1..16 {
428 t.maybe_set(&pc[i], (((slot ^ i).wrapping_sub(1)) >> 8) as u8 & 1);
429 }
430 q = q.add(t).to_p3();
431 if pos == 0 {
432 break;
433 }
434 q = q.dbl().to_p3().dbl().to_p3().dbl().to_p3().dbl().to_p3();
435 pos -= 4;
436 }
437 q
438}
439
440pub fn ge_scalarmult_base(scalar: &[u8]) -> GeP3 {
441 const BXP: [u8; 32] = [
442 0x1a, 0xd5, 0x25, 0x8f, 0x60, 0x2d, 0x56, 0xc9, 0xb2, 0xa7, 0x25, 0x95, 0x60, 0xc7, 0x2c,
443 0x69, 0x5c, 0xdc, 0xd6, 0xfd, 0x31, 0xe2, 0xa4, 0xc0, 0xfe, 0x53, 0x6e, 0xcd, 0xd3, 0x36,
444 0x69, 0x21,
445 ];
446 const BYP: [u8; 32] = [
447 0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
448 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
449 0x66, 0x66,
450 ];
451 let bx = Fe::from_bytes(&BXP);
452 let by = Fe::from_bytes(&BYP);
453 let base = GeP3 {
454 x: bx,
455 y: by,
456 z: FE_ONE,
457 t: bx * by,
458 };
459 ge_scalarmult(scalar, &base)
460}
461
462#[cfg(feature = "x25519")]
463pub fn ge_to_x25519_vartime(s: &[u8; 32]) -> Option<[u8; 32]> {
464 let p = GeP3::from_bytes_vartime(s)?;
465 let yed = p.y;
466 let x_mont = (FE_ONE + yed) * ((FE_ONE - yed).invert());
467 Some(x_mont.to_bytes())
468}
469
470pub fn sc_reduce32(s: &mut [u8; 32]) {
471 let mut t = [0u8; 64];
472 t[0..32].copy_from_slice(s);
473 sc_reduce(&mut t);
474 s.copy_from_slice(&t[0..32]);
475}
476
477pub fn sc_reduce(s: &mut [u8]) {
478 let mut s0: i64 = 2097151 & load_3i(s);
479 let mut s1: i64 = 2097151 & (load_4i(&s[2..6]) >> 5);
480 let mut s2: i64 = 2097151 & (load_3i(&s[5..8]) >> 2);
481 let mut s3: i64 = 2097151 & (load_4i(&s[7..11]) >> 7);
482 let mut s4: i64 = 2097151 & (load_4i(&s[10..14]) >> 4);
483 let mut s5: i64 = 2097151 & (load_3i(&s[13..16]) >> 1);
484 let mut s6: i64 = 2097151 & (load_4i(&s[15..19]) >> 6);
485 let mut s7: i64 = 2097151 & (load_3i(&s[18..21]) >> 3);
486 let mut s8: i64 = 2097151 & load_3i(&s[21..24]);
487 let mut s9: i64 = 2097151 & (load_4i(&s[23..27]) >> 5);
488 let mut s10: i64 = 2097151 & (load_3i(&s[26..29]) >> 2);
489 let mut s11: i64 = 2097151 & (load_4i(&s[28..32]) >> 7);
490 let mut s12: i64 = 2097151 & (load_4i(&s[31..35]) >> 4);
491 let mut s13: i64 = 2097151 & (load_3i(&s[34..37]) >> 1);
492 let mut s14: i64 = 2097151 & (load_4i(&s[36..40]) >> 6);
493 let mut s15: i64 = 2097151 & (load_3i(&s[39..42]) >> 3);
494 let mut s16: i64 = 2097151 & load_3i(&s[42..45]);
495 let mut s17: i64 = 2097151 & (load_4i(&s[44..48]) >> 5);
496 let s18: i64 = 2097151 & (load_3i(&s[47..50]) >> 2);
497 let s19: i64 = 2097151 & (load_4i(&s[49..53]) >> 7);
498 let s20: i64 = 2097151 & (load_4i(&s[52..56]) >> 4);
499 let s21: i64 = 2097151 & (load_3i(&s[55..58]) >> 1);
500 let s22: i64 = 2097151 & (load_4i(&s[57..61]) >> 6);
501 let s23: i64 = load_4i(&s[60..64]) >> 3;
502
503 s11 += s23 * 666643;
504 s12 += s23 * 470296;
505 s13 += s23 * 654183;
506 s14 -= s23 * 997805;
507 s15 += s23 * 136657;
508 s16 -= s23 * 683901;
509
510 s10 += s22 * 666643;
511 s11 += s22 * 470296;
512 s12 += s22 * 654183;
513 s13 -= s22 * 997805;
514 s14 += s22 * 136657;
515 s15 -= s22 * 683901;
516
517 s9 += s21 * 666643;
518 s10 += s21 * 470296;
519 s11 += s21 * 654183;
520 s12 -= s21 * 997805;
521 s13 += s21 * 136657;
522 s14 -= s21 * 683901;
523
524 s8 += s20 * 666643;
525 s9 += s20 * 470296;
526 s10 += s20 * 654183;
527 s11 -= s20 * 997805;
528 s12 += s20 * 136657;
529 s13 -= s20 * 683901;
530
531 s7 += s19 * 666643;
532 s8 += s19 * 470296;
533 s9 += s19 * 654183;
534 s10 -= s19 * 997805;
535 s11 += s19 * 136657;
536 s12 -= s19 * 683901;
537
538 s6 += s18 * 666643;
539 s7 += s18 * 470296;
540 s8 += s18 * 654183;
541 s9 -= s18 * 997805;
542 s10 += s18 * 136657;
543 s11 -= s18 * 683901;
544
545 let mut carry6: i64 = (s6 + (1 << 20)) >> 21;
546 s7 += carry6;
547 s6 -= carry6 << 21;
548 let mut carry8: i64 = (s8 + (1 << 20)) >> 21;
549 s9 += carry8;
550 s8 -= carry8 << 21;
551 let mut carry10: i64 = (s10 + (1 << 20)) >> 21;
552 s11 += carry10;
553 s10 -= carry10 << 21;
554 let carry12: i64 = (s12 + (1 << 20)) >> 21;
555 s13 += carry12;
556 s12 -= carry12 << 21;
557 let carry14: i64 = (s14 + (1 << 20)) >> 21;
558 s15 += carry14;
559 s14 -= carry14 << 21;
560 let carry16: i64 = (s16 + (1 << 20)) >> 21;
561 s17 += carry16;
562 s16 -= carry16 << 21;
563
564 let mut carry7: i64 = (s7 + (1 << 20)) >> 21;
565 s8 += carry7;
566 s7 -= carry7 << 21;
567 let mut carry9: i64 = (s9 + (1 << 20)) >> 21;
568 s10 += carry9;
569 s9 -= carry9 << 21;
570 let mut carry11: i64 = (s11 + (1 << 20)) >> 21;
571 s12 += carry11;
572 s11 -= carry11 << 21;
573 let carry13: i64 = (s13 + (1 << 20)) >> 21;
574 s14 += carry13;
575 s13 -= carry13 << 21;
576 let carry15: i64 = (s15 + (1 << 20)) >> 21;
577 s16 += carry15;
578 s15 -= carry15 << 21;
579
580 s5 += s17 * 666643;
581 s6 += s17 * 470296;
582 s7 += s17 * 654183;
583 s8 -= s17 * 997805;
584 s9 += s17 * 136657;
585 s10 -= s17 * 683901;
586
587 s4 += s16 * 666643;
588 s5 += s16 * 470296;
589 s6 += s16 * 654183;
590 s7 -= s16 * 997805;
591 s8 += s16 * 136657;
592 s9 -= s16 * 683901;
593
594 s3 += s15 * 666643;
595 s4 += s15 * 470296;
596 s5 += s15 * 654183;
597 s6 -= s15 * 997805;
598 s7 += s15 * 136657;
599 s8 -= s15 * 683901;
600
601 s2 += s14 * 666643;
602 s3 += s14 * 470296;
603 s4 += s14 * 654183;
604 s5 -= s14 * 997805;
605 s6 += s14 * 136657;
606 s7 -= s14 * 683901;
607
608 s1 += s13 * 666643;
609 s2 += s13 * 470296;
610 s3 += s13 * 654183;
611 s4 -= s13 * 997805;
612 s5 += s13 * 136657;
613 s6 -= s13 * 683901;
614
615 s0 += s12 * 666643;
616 s1 += s12 * 470296;
617 s2 += s12 * 654183;
618 s3 -= s12 * 997805;
619 s4 += s12 * 136657;
620 s5 -= s12 * 683901;
621 s12 = 0;
622
623 let mut carry0: i64 = (s0 + (1 << 20)) >> 21;
624 s1 += carry0;
625 s0 -= carry0 << 21;
626 let mut carry2: i64 = (s2 + (1 << 20)) >> 21;
627 s3 += carry2;
628 s2 -= carry2 << 21;
629 let mut carry4: i64 = (s4 + (1 << 20)) >> 21;
630 s5 += carry4;
631 s4 -= carry4 << 21;
632 carry6 = (s6 + (1 << 20)) >> 21;
633 s7 += carry6;
634 s6 -= carry6 << 21;
635 carry8 = (s8 + (1 << 20)) >> 21;
636 s9 += carry8;
637 s8 -= carry8 << 21;
638 carry10 = (s10 + (1 << 20)) >> 21;
639 s11 += carry10;
640 s10 -= carry10 << 21;
641
642 let mut carry1: i64 = (s1 + (1 << 20)) >> 21;
643 s2 += carry1;
644 s1 -= carry1 << 21;
645 let mut carry3: i64 = (s3 + (1 << 20)) >> 21;
646 s4 += carry3;
647 s3 -= carry3 << 21;
648 let mut carry5: i64 = (s5 + (1 << 20)) >> 21;
649 s6 += carry5;
650 s5 -= carry5 << 21;
651 carry7 = (s7 + (1 << 20)) >> 21;
652 s8 += carry7;
653 s7 -= carry7 << 21;
654 carry9 = (s9 + (1 << 20)) >> 21;
655 s10 += carry9;
656 s9 -= carry9 << 21;
657 carry11 = (s11 + (1 << 20)) >> 21;
658 s12 += carry11;
659 s11 -= carry11 << 21;
660
661 s0 += s12 * 666643;
662 s1 += s12 * 470296;
663 s2 += s12 * 654183;
664 s3 -= s12 * 997805;
665 s4 += s12 * 136657;
666 s5 -= s12 * 683901;
667 s12 = 0;
668
669 carry0 = s0 >> 21;
670 s1 += carry0;
671 s0 -= carry0 << 21;
672 carry1 = s1 >> 21;
673 s2 += carry1;
674 s1 -= carry1 << 21;
675 carry2 = s2 >> 21;
676 s3 += carry2;
677 s2 -= carry2 << 21;
678 carry3 = s3 >> 21;
679 s4 += carry3;
680 s3 -= carry3 << 21;
681 carry4 = s4 >> 21;
682 s5 += carry4;
683 s4 -= carry4 << 21;
684 carry5 = s5 >> 21;
685 s6 += carry5;
686 s5 -= carry5 << 21;
687 carry6 = s6 >> 21;
688 s7 += carry6;
689 s6 -= carry6 << 21;
690 carry7 = s7 >> 21;
691 s8 += carry7;
692 s7 -= carry7 << 21;
693 carry8 = s8 >> 21;
694 s9 += carry8;
695 s8 -= carry8 << 21;
696 carry9 = s9 >> 21;
697 s10 += carry9;
698 s9 -= carry9 << 21;
699 carry10 = s10 >> 21;
700 s11 += carry10;
701 s10 -= carry10 << 21;
702 carry11 = s11 >> 21;
703 s12 += carry11;
704 s11 -= carry11 << 21;
705
706 s0 += s12 * 666643;
707 s1 += s12 * 470296;
708 s2 += s12 * 654183;
709 s3 -= s12 * 997805;
710 s4 += s12 * 136657;
711 s5 -= s12 * 683901;
712
713 carry0 = s0 >> 21;
714 s1 += carry0;
715 s0 -= carry0 << 21;
716 carry1 = s1 >> 21;
717 s2 += carry1;
718 s1 -= carry1 << 21;
719 carry2 = s2 >> 21;
720 s3 += carry2;
721 s2 -= carry2 << 21;
722 carry3 = s3 >> 21;
723 s4 += carry3;
724 s3 -= carry3 << 21;
725 carry4 = s4 >> 21;
726 s5 += carry4;
727 s4 -= carry4 << 21;
728 carry5 = s5 >> 21;
729 s6 += carry5;
730 s5 -= carry5 << 21;
731 carry6 = s6 >> 21;
732 s7 += carry6;
733 s6 -= carry6 << 21;
734 carry7 = s7 >> 21;
735 s8 += carry7;
736 s7 -= carry7 << 21;
737 carry8 = s8 >> 21;
738 s9 += carry8;
739 s8 -= carry8 << 21;
740 carry9 = s9 >> 21;
741 s10 += carry9;
742 s9 -= carry9 << 21;
743 carry10 = s10 >> 21;
744 s11 += carry10;
745 s10 -= carry10 << 21;
746
747 s[0] = (s0 >> 0) as u8;
748 s[1] = (s0 >> 8) as u8;
749 s[2] = ((s0 >> 16) | (s1 << 5)) as u8;
750 s[3] = (s1 >> 3) as u8;
751 s[4] = (s1 >> 11) as u8;
752 s[5] = ((s1 >> 19) | (s2 << 2)) as u8;
753 s[6] = (s2 >> 6) as u8;
754 s[7] = ((s2 >> 14) | (s3 << 7)) as u8;
755 s[8] = (s3 >> 1) as u8;
756 s[9] = (s3 >> 9) as u8;
757 s[10] = ((s3 >> 17) | (s4 << 4)) as u8;
758 s[11] = (s4 >> 4) as u8;
759 s[12] = (s4 >> 12) as u8;
760 s[13] = ((s4 >> 20) | (s5 << 1)) as u8;
761 s[14] = (s5 >> 7) as u8;
762 s[15] = ((s5 >> 15) | (s6 << 6)) as u8;
763 s[16] = (s6 >> 2) as u8;
764 s[17] = (s6 >> 10) as u8;
765 s[18] = ((s6 >> 18) | (s7 << 3)) as u8;
766 s[19] = (s7 >> 5) as u8;
767 s[20] = (s7 >> 13) as u8;
768 s[21] = (s8 >> 0) as u8;
769 s[22] = (s8 >> 8) as u8;
770 s[23] = ((s8 >> 16) | (s9 << 5)) as u8;
771 s[24] = (s9 >> 3) as u8;
772 s[25] = (s9 >> 11) as u8;
773 s[26] = ((s9 >> 19) | (s10 << 2)) as u8;
774 s[27] = (s10 >> 6) as u8;
775 s[28] = ((s10 >> 14) | (s11 << 7)) as u8;
776 s[29] = (s11 >> 1) as u8;
777 s[30] = (s11 >> 9) as u8;
778 s[31] = (s11 >> 17) as u8;
779}
780
781#[cfg(feature = "blind-keys")]
782pub fn sc_mul(a: &[u8], b: &[u8]) -> [u8; 32] {
783 let mut s = [0u8; 32];
784 sc_muladd(&mut s, a, b, &[0; 32]);
785 s
786}
787
788#[cfg(feature = "blind-keys")]
789pub fn sc_sq(s: &[u8]) -> [u8; 32] {
790 sc_mul(s, s)
791}
792
793#[cfg(feature = "blind-keys")]
794pub fn sc_sqmul(s: &[u8], n: usize, a: &[u8]) -> [u8; 32] {
795 let mut t = [0u8; 32];
796 t.copy_from_slice(s);
797 for _ in 0..n {
798 t = sc_sq(&t);
799 }
800 sc_mul(&t, a)
801}
802
803#[cfg(feature = "blind-keys")]
804pub fn sc_invert(s: &[u8; 32]) -> [u8; 32] {
805 let _10 = sc_sq(s);
806 let _11 = sc_mul(s, &_10);
807 let _100 = sc_mul(s, &_11);
808 let _1000 = sc_sq(&_100);
809 let _1010 = sc_mul(&_10, &_1000);
810 let _1011 = sc_mul(s, &_1010);
811 let _10000 = sc_sq(&_1000);
812 let _10110 = sc_sq(&_1011);
813 let _100000 = sc_mul(&_1010, &_10110);
814 let _100110 = sc_mul(&_10000, &_10110);
815 let _1000000 = sc_sq(&_100000);
816 let _1010000 = sc_mul(&_10000, &_1000000);
817 let _1010011 = sc_mul(&_11, &_1010000);
818 let _1100011 = sc_mul(&_10000, &_1010011);
819 let _1100111 = sc_mul(&_100, &_1100011);
820 let _1101011 = sc_mul(&_100, &_1100111);
821 let _10010011 = sc_mul(&_1000000, &_1010011);
822 let _10010111 = sc_mul(&_100, &_10010011);
823 let _10111101 = sc_mul(&_100110, &_10010111);
824 let _11010011 = sc_mul(&_10110, &_10111101);
825 let _11100111 = sc_mul(&_1010000, &_10010111);
826 let _11101011 = sc_mul(&_100, &_11100111);
827 let _11110101 = sc_mul(&_1010, &_11101011);
828
829 let mut recip = sc_mul(&_1011, &_11110101);
830 recip = sc_sqmul(&recip, 126, &_1010011);
831 recip = sc_sqmul(&recip, 9, &_10);
832 recip = sc_mul(&recip, &_11110101);
833 recip = sc_sqmul(&recip, 7, &_1100111);
834 recip = sc_sqmul(&recip, 9, &_11110101);
835 recip = sc_sqmul(&recip, 11, &_10111101);
836 recip = sc_sqmul(&recip, 8, &_11100111);
837 recip = sc_sqmul(&recip, 9, &_1101011);
838 recip = sc_sqmul(&recip, 6, &_1011);
839 recip = sc_sqmul(&recip, 14, &_10010011);
840 recip = sc_sqmul(&recip, 10, &_1100011);
841 recip = sc_sqmul(&recip, 9, &_10010111);
842 recip = sc_sqmul(&recip, 10, &_11110101);
843 recip = sc_sqmul(&recip, 8, &_11010011);
844 recip = sc_sqmul(&recip, 8, &_11101011);
845 recip
846}
847
848pub fn sc_muladd(s: &mut [u8], a: &[u8], b: &[u8], c: &[u8]) {
849 let a0 = 2097151 & load_3i(&a[0..3]);
850 let a1 = 2097151 & (load_4i(&a[2..6]) >> 5);
851 let a2 = 2097151 & (load_3i(&a[5..8]) >> 2);
852 let a3 = 2097151 & (load_4i(&a[7..11]) >> 7);
853 let a4 = 2097151 & (load_4i(&a[10..14]) >> 4);
854 let a5 = 2097151 & (load_3i(&a[13..16]) >> 1);
855 let a6 = 2097151 & (load_4i(&a[15..19]) >> 6);
856 let a7 = 2097151 & (load_3i(&a[18..21]) >> 3);
857 let a8 = 2097151 & load_3i(&a[21..24]);
858 let a9 = 2097151 & (load_4i(&a[23..27]) >> 5);
859 let a10 = 2097151 & (load_3i(&a[26..29]) >> 2);
860 let a11 = load_4i(&a[28..32]) >> 7;
861 let b0 = 2097151 & load_3i(&b[0..3]);
862 let b1 = 2097151 & (load_4i(&b[2..6]) >> 5);
863 let b2 = 2097151 & (load_3i(&b[5..8]) >> 2);
864 let b3 = 2097151 & (load_4i(&b[7..11]) >> 7);
865 let b4 = 2097151 & (load_4i(&b[10..14]) >> 4);
866 let b5 = 2097151 & (load_3i(&b[13..16]) >> 1);
867 let b6 = 2097151 & (load_4i(&b[15..19]) >> 6);
868 let b7 = 2097151 & (load_3i(&b[18..21]) >> 3);
869 let b8 = 2097151 & load_3i(&b[21..24]);
870 let b9 = 2097151 & (load_4i(&b[23..27]) >> 5);
871 let b10 = 2097151 & (load_3i(&b[26..29]) >> 2);
872 let b11 = load_4i(&b[28..32]) >> 7;
873 let c0 = 2097151 & load_3i(&c[0..3]);
874 let c1 = 2097151 & (load_4i(&c[2..6]) >> 5);
875 let c2 = 2097151 & (load_3i(&c[5..8]) >> 2);
876 let c3 = 2097151 & (load_4i(&c[7..11]) >> 7);
877 let c4 = 2097151 & (load_4i(&c[10..14]) >> 4);
878 let c5 = 2097151 & (load_3i(&c[13..16]) >> 1);
879 let c6 = 2097151 & (load_4i(&c[15..19]) >> 6);
880 let c7 = 2097151 & (load_3i(&c[18..21]) >> 3);
881 let c8 = 2097151 & load_3i(&c[21..24]);
882 let c9 = 2097151 & (load_4i(&c[23..27]) >> 5);
883 let c10 = 2097151 & (load_3i(&c[26..29]) >> 2);
884 let c11 = load_4i(&c[28..32]) >> 7;
885
886 let mut s0: i64 = c0 + a0 * b0;
887 let mut s1: i64 = c1 + a0 * b1 + a1 * b0;
888 let mut s2: i64 = c2 + a0 * b2 + a1 * b1 + a2 * b0;
889 let mut s3: i64 = c3 + a0 * b3 + a1 * b2 + a2 * b1 + a3 * b0;
890 let mut s4: i64 = c4 + a0 * b4 + a1 * b3 + a2 * b2 + a3 * b1 + a4 * b0;
891 let mut s5: i64 = c5 + a0 * b5 + a1 * b4 + a2 * b3 + a3 * b2 + a4 * b1 + a5 * b0;
892 let mut s6: i64 = c6 + a0 * b6 + a1 * b5 + a2 * b4 + a3 * b3 + a4 * b2 + a5 * b1 + a6 * b0;
893 let mut s7: i64 =
894 c7 + a0 * b7 + a1 * b6 + a2 * b5 + a3 * b4 + a4 * b3 + a5 * b2 + a6 * b1 + a7 * b0;
895 let mut s8: i64 = c8
896 + a0 * b8
897 + a1 * b7
898 + a2 * b6
899 + a3 * b5
900 + a4 * b4
901 + a5 * b3
902 + a6 * b2
903 + a7 * b1
904 + a8 * b0;
905 let mut s9: i64 = c9
906 + a0 * b9
907 + a1 * b8
908 + a2 * b7
909 + a3 * b6
910 + a4 * b5
911 + a5 * b4
912 + a6 * b3
913 + a7 * b2
914 + a8 * b1
915 + a9 * b0;
916 let mut s10: i64 = c10
917 + a0 * b10
918 + a1 * b9
919 + a2 * b8
920 + a3 * b7
921 + a4 * b6
922 + a5 * b5
923 + a6 * b4
924 + a7 * b3
925 + a8 * b2
926 + a9 * b1
927 + a10 * b0;
928 let mut s11: i64 = c11
929 + a0 * b11
930 + a1 * b10
931 + a2 * b9
932 + a3 * b8
933 + a4 * b7
934 + a5 * b6
935 + a6 * b5
936 + a7 * b4
937 + a8 * b3
938 + a9 * b2
939 + a10 * b1
940 + a11 * b0;
941 let mut s12: i64 = a1 * b11
942 + a2 * b10
943 + a3 * b9
944 + a4 * b8
945 + a5 * b7
946 + a6 * b6
947 + a7 * b5
948 + a8 * b4
949 + a9 * b3
950 + a10 * b2
951 + a11 * b1;
952 let mut s13: i64 = a2 * b11
953 + a3 * b10
954 + a4 * b9
955 + a5 * b8
956 + a6 * b7
957 + a7 * b6
958 + a8 * b5
959 + a9 * b4
960 + a10 * b3
961 + a11 * b2;
962 let mut s14: i64 =
963 a3 * b11 + a4 * b10 + a5 * b9 + a6 * b8 + a7 * b7 + a8 * b6 + a9 * b5 + a10 * b4 + a11 * b3;
964 let mut s15: i64 =
965 a4 * b11 + a5 * b10 + a6 * b9 + a7 * b8 + a8 * b7 + a9 * b6 + a10 * b5 + a11 * b4;
966 let mut s16: i64 = a5 * b11 + a6 * b10 + a7 * b9 + a8 * b8 + a9 * b7 + a10 * b6 + a11 * b5;
967 let mut s17: i64 = a6 * b11 + a7 * b10 + a8 * b9 + a9 * b8 + a10 * b7 + a11 * b6;
968 let mut s18: i64 = a7 * b11 + a8 * b10 + a9 * b9 + a10 * b8 + a11 * b7;
969 let mut s19: i64 = a8 * b11 + a9 * b10 + a10 * b9 + a11 * b8;
970 let mut s20: i64 = a9 * b11 + a10 * b10 + a11 * b9;
971 let mut s21: i64 = a10 * b11 + a11 * b10;
972 let mut s22: i64 = a11 * b11;
973 let mut s23: i64 = 0;
974
975 let mut carry0: i64 = (s0 + (1 << 20)) >> 21;
976 s1 += carry0;
977 s0 -= carry0 << 21;
978 let mut carry2: i64 = (s2 + (1 << 20)) >> 21;
979 s3 += carry2;
980 s2 -= carry2 << 21;
981 let mut carry4: i64 = (s4 + (1 << 20)) >> 21;
982 s5 += carry4;
983 s4 -= carry4 << 21;
984 let mut carry6: i64 = (s6 + (1 << 20)) >> 21;
985 s7 += carry6;
986 s6 -= carry6 << 21;
987 let mut carry8: i64 = (s8 + (1 << 20)) >> 21;
988 s9 += carry8;
989 s8 -= carry8 << 21;
990 let mut carry10: i64 = (s10 + (1 << 20)) >> 21;
991 s11 += carry10;
992 s10 -= carry10 << 21;
993 let mut carry12: i64 = (s12 + (1 << 20)) >> 21;
994 s13 += carry12;
995 s12 -= carry12 << 21;
996 let mut carry14: i64 = (s14 + (1 << 20)) >> 21;
997 s15 += carry14;
998 s14 -= carry14 << 21;
999 let mut carry16: i64 = (s16 + (1 << 20)) >> 21;
1000 s17 += carry16;
1001 s16 -= carry16 << 21;
1002 let carry18: i64 = (s18 + (1 << 20)) >> 21;
1003 s19 += carry18;
1004 s18 -= carry18 << 21;
1005 let carry20: i64 = (s20 + (1 << 20)) >> 21;
1006 s21 += carry20;
1007 s20 -= carry20 << 21;
1008 let carry22: i64 = (s22 + (1 << 20)) >> 21;
1009 s23 += carry22;
1010 s22 -= carry22 << 21;
1011
1012 let mut carry1: i64 = (s1 + (1 << 20)) >> 21;
1013 s2 += carry1;
1014 s1 -= carry1 << 21;
1015 let mut carry3: i64 = (s3 + (1 << 20)) >> 21;
1016 s4 += carry3;
1017 s3 -= carry3 << 21;
1018 let mut carry5: i64 = (s5 + (1 << 20)) >> 21;
1019 s6 += carry5;
1020 s5 -= carry5 << 21;
1021 let mut carry7: i64 = (s7 + (1 << 20)) >> 21;
1022 s8 += carry7;
1023 s7 -= carry7 << 21;
1024 let mut carry9: i64 = (s9 + (1 << 20)) >> 21;
1025 s10 += carry9;
1026 s9 -= carry9 << 21;
1027 let mut carry11: i64 = (s11 + (1 << 20)) >> 21;
1028 s12 += carry11;
1029 s11 -= carry11 << 21;
1030 let mut carry13: i64 = (s13 + (1 << 20)) >> 21;
1031 s14 += carry13;
1032 s13 -= carry13 << 21;
1033 let mut carry15: i64 = (s15 + (1 << 20)) >> 21;
1034 s16 += carry15;
1035 s15 -= carry15 << 21;
1036 let carry17: i64 = (s17 + (1 << 20)) >> 21;
1037 s18 += carry17;
1038 s17 -= carry17 << 21;
1039 let carry19: i64 = (s19 + (1 << 20)) >> 21;
1040 s20 += carry19;
1041 s19 -= carry19 << 21;
1042 let carry21: i64 = (s21 + (1 << 20)) >> 21;
1043 s22 += carry21;
1044 s21 -= carry21 << 21;
1045
1046 s11 += s23 * 666643;
1047 s12 += s23 * 470296;
1048 s13 += s23 * 654183;
1049 s14 -= s23 * 997805;
1050 s15 += s23 * 136657;
1051 s16 -= s23 * 683901;
1052
1053 s10 += s22 * 666643;
1054 s11 += s22 * 470296;
1055 s12 += s22 * 654183;
1056 s13 -= s22 * 997805;
1057 s14 += s22 * 136657;
1058 s15 -= s22 * 683901;
1059
1060 s9 += s21 * 666643;
1061 s10 += s21 * 470296;
1062 s11 += s21 * 654183;
1063 s12 -= s21 * 997805;
1064 s13 += s21 * 136657;
1065 s14 -= s21 * 683901;
1066
1067 s8 += s20 * 666643;
1068 s9 += s20 * 470296;
1069 s10 += s20 * 654183;
1070 s11 -= s20 * 997805;
1071 s12 += s20 * 136657;
1072 s13 -= s20 * 683901;
1073
1074 s7 += s19 * 666643;
1075 s8 += s19 * 470296;
1076 s9 += s19 * 654183;
1077 s10 -= s19 * 997805;
1078 s11 += s19 * 136657;
1079 s12 -= s19 * 683901;
1080
1081 s6 += s18 * 666643;
1082 s7 += s18 * 470296;
1083 s8 += s18 * 654183;
1084 s9 -= s18 * 997805;
1085 s10 += s18 * 136657;
1086 s11 -= s18 * 683901;
1087
1088 carry6 = (s6 + (1 << 20)) >> 21;
1089 s7 += carry6;
1090 s6 -= carry6 << 21;
1091 carry8 = (s8 + (1 << 20)) >> 21;
1092 s9 += carry8;
1093 s8 -= carry8 << 21;
1094 carry10 = (s10 + (1 << 20)) >> 21;
1095 s11 += carry10;
1096 s10 -= carry10 << 21;
1097 carry12 = (s12 + (1 << 20)) >> 21;
1098 s13 += carry12;
1099 s12 -= carry12 << 21;
1100 carry14 = (s14 + (1 << 20)) >> 21;
1101 s15 += carry14;
1102 s14 -= carry14 << 21;
1103 carry16 = (s16 + (1 << 20)) >> 21;
1104 s17 += carry16;
1105 s16 -= carry16 << 21;
1106
1107 carry7 = (s7 + (1 << 20)) >> 21;
1108 s8 += carry7;
1109 s7 -= carry7 << 21;
1110 carry9 = (s9 + (1 << 20)) >> 21;
1111 s10 += carry9;
1112 s9 -= carry9 << 21;
1113 carry11 = (s11 + (1 << 20)) >> 21;
1114 s12 += carry11;
1115 s11 -= carry11 << 21;
1116 carry13 = (s13 + (1 << 20)) >> 21;
1117 s14 += carry13;
1118 s13 -= carry13 << 21;
1119 carry15 = (s15 + (1 << 20)) >> 21;
1120 s16 += carry15;
1121 s15 -= carry15 << 21;
1122
1123 s5 += s17 * 666643;
1124 s6 += s17 * 470296;
1125 s7 += s17 * 654183;
1126 s8 -= s17 * 997805;
1127 s9 += s17 * 136657;
1128 s10 -= s17 * 683901;
1129
1130 s4 += s16 * 666643;
1131 s5 += s16 * 470296;
1132 s6 += s16 * 654183;
1133 s7 -= s16 * 997805;
1134 s8 += s16 * 136657;
1135 s9 -= s16 * 683901;
1136
1137 s3 += s15 * 666643;
1138 s4 += s15 * 470296;
1139 s5 += s15 * 654183;
1140 s6 -= s15 * 997805;
1141 s7 += s15 * 136657;
1142 s8 -= s15 * 683901;
1143
1144 s2 += s14 * 666643;
1145 s3 += s14 * 470296;
1146 s4 += s14 * 654183;
1147 s5 -= s14 * 997805;
1148 s6 += s14 * 136657;
1149 s7 -= s14 * 683901;
1150
1151 s1 += s13 * 666643;
1152 s2 += s13 * 470296;
1153 s3 += s13 * 654183;
1154 s4 -= s13 * 997805;
1155 s5 += s13 * 136657;
1156 s6 -= s13 * 683901;
1157
1158 s0 += s12 * 666643;
1159 s1 += s12 * 470296;
1160 s2 += s12 * 654183;
1161 s3 -= s12 * 997805;
1162 s4 += s12 * 136657;
1163 s5 -= s12 * 683901;
1164 s12 = 0;
1165
1166 carry0 = (s0 + (1 << 20)) >> 21;
1167 s1 += carry0;
1168 s0 -= carry0 << 21;
1169 carry2 = (s2 + (1 << 20)) >> 21;
1170 s3 += carry2;
1171 s2 -= carry2 << 21;
1172 carry4 = (s4 + (1 << 20)) >> 21;
1173 s5 += carry4;
1174 s4 -= carry4 << 21;
1175 carry6 = (s6 + (1 << 20)) >> 21;
1176 s7 += carry6;
1177 s6 -= carry6 << 21;
1178 carry8 = (s8 + (1 << 20)) >> 21;
1179 s9 += carry8;
1180 s8 -= carry8 << 21;
1181 carry10 = (s10 + (1 << 20)) >> 21;
1182 s11 += carry10;
1183 s10 -= carry10 << 21;
1184
1185 carry1 = (s1 + (1 << 20)) >> 21;
1186 s2 += carry1;
1187 s1 -= carry1 << 21;
1188 carry3 = (s3 + (1 << 20)) >> 21;
1189 s4 += carry3;
1190 s3 -= carry3 << 21;
1191 carry5 = (s5 + (1 << 20)) >> 21;
1192 s6 += carry5;
1193 s5 -= carry5 << 21;
1194 carry7 = (s7 + (1 << 20)) >> 21;
1195 s8 += carry7;
1196 s7 -= carry7 << 21;
1197 carry9 = (s9 + (1 << 20)) >> 21;
1198 s10 += carry9;
1199 s9 -= carry9 << 21;
1200 carry11 = (s11 + (1 << 20)) >> 21;
1201 s12 += carry11;
1202 s11 -= carry11 << 21;
1203
1204 s0 += s12 * 666643;
1205 s1 += s12 * 470296;
1206 s2 += s12 * 654183;
1207 s3 -= s12 * 997805;
1208 s4 += s12 * 136657;
1209 s5 -= s12 * 683901;
1210 s12 = 0;
1211
1212 carry0 = s0 >> 21;
1213 s1 += carry0;
1214 s0 -= carry0 << 21;
1215 carry1 = s1 >> 21;
1216 s2 += carry1;
1217 s1 -= carry1 << 21;
1218 carry2 = s2 >> 21;
1219 s3 += carry2;
1220 s2 -= carry2 << 21;
1221 carry3 = s3 >> 21;
1222 s4 += carry3;
1223 s3 -= carry3 << 21;
1224 carry4 = s4 >> 21;
1225 s5 += carry4;
1226 s4 -= carry4 << 21;
1227 carry5 = s5 >> 21;
1228 s6 += carry5;
1229 s5 -= carry5 << 21;
1230 carry6 = s6 >> 21;
1231 s7 += carry6;
1232 s6 -= carry6 << 21;
1233 carry7 = s7 >> 21;
1234 s8 += carry7;
1235 s7 -= carry7 << 21;
1236 carry8 = s8 >> 21;
1237 s9 += carry8;
1238 s8 -= carry8 << 21;
1239 carry9 = s9 >> 21;
1240 s10 += carry9;
1241 s9 -= carry9 << 21;
1242 carry10 = s10 >> 21;
1243 s11 += carry10;
1244 s10 -= carry10 << 21;
1245 carry11 = s11 >> 21;
1246 s12 += carry11;
1247 s11 -= carry11 << 21;
1248
1249 s0 += s12 * 666643;
1250 s1 += s12 * 470296;
1251 s2 += s12 * 654183;
1252 s3 -= s12 * 997805;
1253 s4 += s12 * 136657;
1254 s5 -= s12 * 683901;
1255
1256 carry0 = s0 >> 21;
1257 s1 += carry0;
1258 s0 -= carry0 << 21;
1259 carry1 = s1 >> 21;
1260 s2 += carry1;
1261 s1 -= carry1 << 21;
1262 carry2 = s2 >> 21;
1263 s3 += carry2;
1264 s2 -= carry2 << 21;
1265 carry3 = s3 >> 21;
1266 s4 += carry3;
1267 s3 -= carry3 << 21;
1268 carry4 = s4 >> 21;
1269 s5 += carry4;
1270 s4 -= carry4 << 21;
1271 carry5 = s5 >> 21;
1272 s6 += carry5;
1273 s5 -= carry5 << 21;
1274 carry6 = s6 >> 21;
1275 s7 += carry6;
1276 s6 -= carry6 << 21;
1277 carry7 = s7 >> 21;
1278 s8 += carry7;
1279 s7 -= carry7 << 21;
1280 carry8 = s8 >> 21;
1281 s9 += carry8;
1282 s8 -= carry8 << 21;
1283 carry9 = s9 >> 21;
1284 s10 += carry9;
1285 s9 -= carry9 << 21;
1286 carry10 = s10 >> 21;
1287 s11 += carry10;
1288 s10 -= carry10 << 21;
1289
1290 s[0] = (s0 >> 0) as u8;
1291 s[1] = (s0 >> 8) as u8;
1292 s[2] = ((s0 >> 16) | (s1 << 5)) as u8;
1293 s[3] = (s1 >> 3) as u8;
1294 s[4] = (s1 >> 11) as u8;
1295 s[5] = ((s1 >> 19) | (s2 << 2)) as u8;
1296 s[6] = (s2 >> 6) as u8;
1297 s[7] = ((s2 >> 14) | (s3 << 7)) as u8;
1298 s[8] = (s3 >> 1) as u8;
1299 s[9] = (s3 >> 9) as u8;
1300 s[10] = ((s3 >> 17) | (s4 << 4)) as u8;
1301 s[11] = (s4 >> 4) as u8;
1302 s[12] = (s4 >> 12) as u8;
1303 s[13] = ((s4 >> 20) | (s5 << 1)) as u8;
1304 s[14] = (s5 >> 7) as u8;
1305 s[15] = ((s5 >> 15) | (s6 << 6)) as u8;
1306 s[16] = (s6 >> 2) as u8;
1307 s[17] = (s6 >> 10) as u8;
1308 s[18] = ((s6 >> 18) | (s7 << 3)) as u8;
1309 s[19] = (s7 >> 5) as u8;
1310 s[20] = (s7 >> 13) as u8;
1311 s[21] = (s8 >> 0) as u8;
1312 s[22] = (s8 >> 8) as u8;
1313 s[23] = ((s8 >> 16) | (s9 << 5)) as u8;
1314 s[24] = (s9 >> 3) as u8;
1315 s[25] = (s9 >> 11) as u8;
1316 s[26] = ((s9 >> 19) | (s10 << 2)) as u8;
1317 s[27] = (s10 >> 6) as u8;
1318 s[28] = ((s10 >> 14) | (s11 << 7)) as u8;
1319 s[29] = (s11 >> 1) as u8;
1320 s[30] = (s11 >> 9) as u8;
1321 s[31] = (s11 >> 17) as u8;
1322}
1323
1324pub fn sc_reject_noncanonical(s: &[u8]) -> Result<(), Error> {
1325 static L: [u8; 32] = [
1326 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde,
1327 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1328 0x00, 0x10,
1329 ];
1330 if s.len() != 32 {
1331 panic!("Invalid compressed length")
1332 }
1333 let mut c: u8 = 0;
1334 let mut n: u8 = 1;
1335
1336 let mut i = 31;
1337 loop {
1338 c |= ((((s[i] as i32) - (L[i] as i32)) >> 8) as u8) & n;
1339 n &= ((((s[i] ^ L[i]) as i32) - 1) >> 8) as u8;
1340 if i == 0 {
1341 break;
1342 }
1343 i -= 1;
1344 }
1345 if c != 0 {
1346 Ok(())
1347 } else {
1348 Err(Error::NonCanonical)
1349 }
1350}
1351
1352pub fn is_identity(s: &[u8; 32]) -> bool {
1353 let mut c = s[0] ^ 0x01;
1354 for i in 1..31 {
1355 c |= s[i];
1356 }
1357 c |= s[31] & 0x7f;
1358 c == 0
1359}
1360
1361static BI: [GePrecomp; 8] = [
1362 GePrecomp {
1363 y_plus_x: Fe([
1364 1288382639258501,
1365 245678601348599,
1366 269427782077623,
1367 1462984067271730,
1368 137412439391563,
1369 ]),
1370 y_minus_x: Fe([
1371 62697248952638,
1372 204681361388450,
1373 631292143396476,
1374 338455783676468,
1375 1213667448819585,
1376 ]),
1377 xy2d: Fe([
1378 301289933810280,
1379 1259582250014073,
1380 1422107436869536,
1381 796239922652654,
1382 1953934009299142,
1383 ]),
1384 },
1385 GePrecomp {
1386 y_plus_x: Fe([
1387 1601611775252272,
1388 1720807796594148,
1389 1132070835939856,
1390 1260455018889551,
1391 2147779492816911,
1392 ]),
1393 y_minus_x: Fe([
1394 316559037616741,
1395 2177824224946892,
1396 1459442586438991,
1397 1461528397712656,
1398 751590696113597,
1399 ]),
1400 xy2d: Fe([
1401 1850748884277385,
1402 1200145853858453,
1403 1068094770532492,
1404 672251375690438,
1405 1586055907191707,
1406 ]),
1407 },
1408 GePrecomp {
1409 y_plus_x: Fe([
1410 769950342298419,
1411 132954430919746,
1412 844085933195555,
1413 974092374476333,
1414 726076285546016,
1415 ]),
1416 y_minus_x: Fe([
1417 425251763115706,
1418 608463272472562,
1419 442562545713235,
1420 837766094556764,
1421 374555092627893,
1422 ]),
1423 xy2d: Fe([
1424 1086255230780037,
1425 274979815921559,
1426 1960002765731872,
1427 929474102396301,
1428 1190409889297339,
1429 ]),
1430 },
1431 GePrecomp {
1432 y_plus_x: Fe([
1433 665000864555967,
1434 2065379846933859,
1435 370231110385876,
1436 350988370788628,
1437 1233371373142985,
1438 ]),
1439 y_minus_x: Fe([
1440 2019367628972465,
1441 676711900706637,
1442 110710997811333,
1443 1108646842542025,
1444 517791959672113,
1445 ]),
1446 xy2d: Fe([
1447 965130719900578,
1448 247011430587952,
1449 526356006571389,
1450 91986625355052,
1451 2157223321444601,
1452 ]),
1453 },
1454 GePrecomp {
1455 y_plus_x: Fe([
1456 1802695059465007,
1457 1664899123557221,
1458 593559490740857,
1459 2160434469266659,
1460 927570450755031,
1461 ]),
1462 y_minus_x: Fe([
1463 1725674970513508,
1464 1933645953859181,
1465 1542344539275782,
1466 1767788773573747,
1467 1297447965928905,
1468 ]),
1469 xy2d: Fe([
1470 1381809363726107,
1471 1430341051343062,
1472 2061843536018959,
1473 1551778050872521,
1474 2036394857967624,
1475 ]),
1476 },
1477 GePrecomp {
1478 y_plus_x: Fe([
1479 1970894096313054,
1480 528066325833207,
1481 1619374932191227,
1482 2207306624415883,
1483 1169170329061080,
1484 ]),
1485 y_minus_x: Fe([
1486 2070390218572616,
1487 1458919061857835,
1488 624171843017421,
1489 1055332792707765,
1490 433987520732508,
1491 ]),
1492 xy2d: Fe([
1493 893653801273833,
1494 1168026499324677,
1495 1242553501121234,
1496 1306366254304474,
1497 1086752658510815,
1498 ]),
1499 },
1500 GePrecomp {
1501 y_plus_x: Fe([
1502 213454002618221,
1503 939771523987438,
1504 1159882208056014,
1505 317388369627517,
1506 621213314200687,
1507 ]),
1508 y_minus_x: Fe([
1509 1971678598905747,
1510 338026507889165,
1511 762398079972271,
1512 655096486107477,
1513 42299032696322,
1514 ]),
1515 xy2d: Fe([
1516 177130678690680,
1517 1754759263300204,
1518 1864311296286618,
1519 1180675631479880,
1520 1292726903152791,
1521 ]),
1522 },
1523 GePrecomp {
1524 y_plus_x: Fe([
1525 1913163449625248,
1526 460779200291993,
1527 2193883288642314,
1528 1008900146920800,
1529 1721983679009502,
1530 ]),
1531 y_minus_x: Fe([
1532 1070401523076875,
1533 1272492007800961,
1534 1910153608563310,
1535 2075579521696771,
1536 1191169788841221,
1537 ]),
1538 xy2d: Fe([
1539 692896803108118,
1540 500174642072499,
1541 2068223309439677,
1542 1162190621851337,
1543 1426986007309901,
1544 ]),
1545 },
1546];