kyber_rs/group/edwards25519/
scalar.rs

1use crate::encoding::{BinaryMarshaler, BinaryUnmarshaler, Marshaling, MarshallingError};
2use crate::group::internal::marshalling;
3use crate::group::{self, integer_field, ScalarCanCheckCanonical};
4use crate::util::random;
5use num_bigint::BigInt;
6use num_bigint_dig as num_bigint;
7use serde::{Deserialize, Serialize};
8
9use crate::cipher::stream::Stream;
10use crate::group::edwards25519::constants;
11use crate::group::edwards25519::constants::PRIME_ORDER;
12use crate::group::edwards25519::fe::{load3, load4};
13use crate::group::integer_field::integer::ByteOrder::LittleEndian;
14use crate::group::integer_field::integer::Int;
15use subtle::ConstantTimeEq;
16
17use core::fmt::{Debug, Display, Formatter};
18
19use super::constants::{FULL_ORDER, L_MINUS2};
20
21const MARSHAL_SCALAR_ID: [u8; 8] = [b'e', b'd', b'.', b's', b'c', b'a', b'l', b'a'];
22
23#[derive(Copy, Clone, Eq, Ord, PartialOrd, Debug, Default, Serialize, Deserialize)]
24pub struct Scalar {
25    pub v: [u8; 32],
26}
27
28impl Scalar {
29    pub fn new() -> Self {
30        Self::default()
31    }
32
33    fn as_int(&self) -> Int {
34        Int::new_int_bytes(&self.v, &PRIME_ORDER, LittleEndian)
35    }
36
37    fn set_int(mut self, i: &mut Int) -> Self {
38        let b = i
39            .little_endian(32, 32)
40            .unwrap_or_else(|_| Self::default().v.to_vec());
41        self.v.as_mut_slice()[0..b.len()].copy_from_slice(b.as_ref());
42        self
43    }
44}
45
46impl ScalarCanCheckCanonical for Scalar {
47    /// [`is_canonical()`] checks whether the [`Scalar`] in sb is in the range `0<=s<L` as required by `RFC8032`, Section 5.1.7.
48    /// Also provides Strong Unforgeability under Chosen Message Attacks (SUF-CMA)
49    /// See paper <https://eprint.iacr.org/2020/823.pdf> for definitions and theorems
50    /// See <https://github.com/jedisct1/libsodium/blob/4744636721d2e420f8bbe2d563f31b1f5e682229/src/libsodium/crypto_core/ed25519/ref10/ed25519_ref10.c#L2568>
51    /// for a reference.
52    /// The method accepts a buffer instead of calling [`marshal_binary()`] on the receiver since that
53    /// always returns values modulo [`PRIME_ORDER`].
54    fn is_canonical(&self, sb: &[u8]) -> bool {
55        if sb.len() != 32 {
56            return false;
57        }
58
59        if (sb[31] & 0xf0) == 0 {
60            return true;
61        }
62
63        let l = PRIME_ORDER.to_bytes_le().1;
64
65        let mut c = 0u8;
66        let mut n = 1u8;
67        for i in (0..=31).rev() {
68            // subtraction might lead to an underflow which needs
69            // to be accounted for in the right shift
70            c |= (((sb[i] as u16) - (l[i] as u16)) >> 8) as u8 & n;
71            n &= ((((sb[i] as u16) ^ (l[i] as u16)) - 1) >> 8) as u8;
72        }
73
74        c != 0
75    }
76}
77
78impl PartialEq for Scalar {
79    /// [`eq()`] is an equality test for two [`scalars`](Scalar) on the same [`Group`]
80    fn eq(&self, other: &Self) -> bool {
81        bool::from(self.v.ct_eq(other.v.as_ref()))
82    }
83}
84
85impl Display for Scalar {
86    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
87        write!(f, "Ed25519Scalar({self:#x})")
88    }
89}
90
91impl BinaryMarshaler for Scalar {
92    fn marshal_binary(&self) -> Result<Vec<u8>, MarshallingError> {
93        let mut b = self.as_int().marshal_binary()?;
94        b.resize(32, 0);
95
96        //TODO: should not self.v.to_vec() be enough?
97
98        Ok(b)
99    }
100}
101
102impl BinaryUnmarshaler for Scalar {
103    fn unmarshal_binary(&mut self, data: &[u8]) -> Result<(), MarshallingError> {
104        if data.len() != 32 {
105            return Err(MarshallingError::InvalidInput(
106                "wrong size buffer".to_owned(),
107            ));
108        }
109        self.v.copy_from_slice(data);
110        Ok(())
111    }
112}
113
114impl LowerHex for Scalar {
115    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
116        let prefix = if f.alternate() { "0x" } else { "" };
117        let encoded = hex::encode(self.v);
118        write!(f, "{prefix}{encoded}")
119    }
120}
121
122impl UpperHex for Scalar {
123    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
124        let prefix = if f.alternate() { "0X" } else { "" };
125        let encoded = hex::encode_upper(self.v);
126        write!(f, "{prefix}{encoded}")
127    }
128}
129
130use core::fmt::{LowerHex, UpperHex};
131use core::ops;
132impl_op_ex!(*|a: &Scalar, b: &Scalar| -> Scalar {
133    let mut v = [0_u8; 32];
134    sc_mul(&mut v, &a.v, &b.v);
135    Scalar { v }
136});
137
138impl_op_ex!(+|a: &Scalar, b: &Scalar| -> Scalar {
139        let mut v = [0u8; 32];
140        sc_add(&mut v, &a.v, &b.v);
141        Scalar { v }
142});
143
144impl group::Scalar for Scalar {
145    /// [`set()`] sets [`self`] equal to another [`Scalar`] `a`
146    fn set(mut self, a: &Self) -> Self {
147        self.v = a.v;
148        self
149    }
150
151    /// [`set_int64()`] sets [`self`] the [`Scalar`] to a small integer value.
152    fn set_int64(self, v: i64) -> Self {
153        self.set_int(&mut Int::new_int64(v, constants::PRIME_ORDER.clone()))
154    }
155
156    fn zero(mut self) -> Self {
157        self.v = [0; 32];
158        self
159    }
160
161    /// [`sub()`] sets [`self`] to the modular difference `a - b`
162    fn sub(mut self, a: &Self, b: &Self) -> Self {
163        sc_sub(&mut self.v, &a.v, &b.v);
164        self
165    }
166
167    fn pick(self, rand: &mut impl Stream) -> Self {
168        let mut i = integer_field::integer::Int::new_int(
169            random::random_int(&PRIME_ORDER, rand),
170            PRIME_ORDER.clone(),
171        );
172        self.set_int(&mut i)
173    }
174
175    fn set_bytes(self, bytes: &[u8]) -> Self {
176        self.set_int(&mut Int::new_int_bytes(bytes, &PRIME_ORDER, LittleEndian))
177    }
178
179    fn one(mut self) -> Self {
180        self.v = [0u8; 32];
181        self.v[0] = 1;
182        self
183    }
184
185    fn div(mut self, a: &Self, b: &Self) -> Self {
186        let mut i = Scalar::default();
187        i = i.inv(b);
188        sc_mul(&mut self.v, &a.v, &i.v);
189        self
190    }
191
192    fn inv(mut self, ac: &Self) -> Self {
193        let mut res = Scalar::default();
194        res = res.one();
195        // Modular inversion in a multiplicative group is a^(phi(m)-1) = a^-1 mod m
196        // Since m is prime, phi(m) = m - 1 => a^(m-2) = a^-1 mod m.
197        // The inverse is computed using the exponentation-and-square algorithm.
198        // Implementation is constant time regarding the value a, it only depends on
199        // the modulo.
200        let bit_vec = get_bits(&L_MINUS2.to_bytes_le().1);
201        for i in (0..=255).rev() {
202            let bit_is_set = bit_vec[i];
203            // square step
204            let res_v_clone = res.v;
205            sc_mul(&mut res.v, &res_v_clone, &res_v_clone);
206            if bit_is_set {
207                // multiply step
208                let res_v_clone = res.v;
209                sc_mul(&mut res.v, &res_v_clone, &ac.v);
210            }
211        }
212        self.v = res.v;
213        self
214    }
215
216    fn neg(mut self, a: &Self) -> Self {
217        let mut z = Scalar::default();
218        z = z.zero();
219        sc_sub(&mut self.v, &z.v, &a.v);
220        self
221    }
222}
223
224impl Marshaling for Scalar {
225    fn marshal_to(&self, w: &mut impl std::io::Write) -> Result<(), MarshallingError> {
226        marshalling::scalar_marshal_to(self, w)
227    }
228
229    fn marshal_size(&self) -> usize {
230        32
231    }
232
233    fn unmarshal_from(&mut self, r: &mut impl std::io::Read) -> Result<(), MarshallingError> {
234        marshalling::scalar_unmarshal_from(self, r)
235    }
236
237    fn unmarshal_from_random(&mut self, r: &mut (impl std::io::Read + Stream)) {
238        marshalling::scalar_unmarshal_from_random(self, r);
239    }
240
241    fn marshal_id(&self) -> [u8; 8] {
242        MARSHAL_SCALAR_ID
243    }
244}
245
246fn get_bits(bytes: &[u8]) -> Vec<bool> {
247    let mut bit_vec = Vec::new();
248    let masks = vec![
249        0b00000001u8,
250        0b00000010u8,
251        0b00000100u8,
252        0b00001000u8,
253        0b00010000u8,
254        0b00100000u8,
255        0b01000000u8,
256        0b10000000u8,
257    ];
258    for byte in bytes {
259        for mask in masks.clone() {
260            bit_vec.push(byte & mask != 0)
261        }
262    }
263    bit_vec
264}
265
266/// Input:
267///
268///   `a[0]+256*a[1]+...+256^31*a[31] = a`
269///
270///   `b[0]+256*b[1]+...+256^31*b[31] = b`
271///
272///   `c[0]+256*c[1]+...+256^31*c[31] = c`
273///
274/// Output:
275///
276///   `s[0]+256*s[1]+...+256^31*s[31] = (ab+c) mod l`
277///
278///   where `l = 2^252 + 27742317777372353535851937790883648493`.
279pub fn sc_mul_add(s: &mut [u8; 32], a: &[u8; 32], b: &[u8; 32], c: &[u8; 32]) {
280    let a0 = 2097151 & load3(&a[..]);
281    let a1 = 2097151 & (load4(&a[2..]) >> 5);
282    let a2 = 2097151 & (load3(&a[5..]) >> 2);
283    let a3 = 2097151 & (load4(&a[7..]) >> 7);
284    let a4 = 2097151 & (load4(&a[10..]) >> 4);
285    let a5 = 2097151 & (load3(&a[13..]) >> 1);
286    let a6 = 2097151 & (load4(&a[15..]) >> 6);
287    let a7 = 2097151 & (load3(&a[18..]) >> 3);
288    let a8 = 2097151 & load3(&a[21..]);
289    let a9 = 2097151 & (load4(&a[23..]) >> 5);
290    let a10 = 2097151 & (load3(&a[26..]) >> 2);
291    let a11 = load4(&a[28..]) >> 7;
292    let b0 = 2097151 & load3(&b[..]);
293    let b1 = 2097151 & (load4(&b[2..]) >> 5);
294    let b2 = 2097151 & (load3(&b[5..]) >> 2);
295    let b3 = 2097151 & (load4(&b[7..]) >> 7);
296    let b4 = 2097151 & (load4(&b[10..]) >> 4);
297    let b5 = 2097151 & (load3(&b[13..]) >> 1);
298    let b6 = 2097151 & (load4(&b[15..]) >> 6);
299    let b7 = 2097151 & (load3(&b[18..]) >> 3);
300    let b8 = 2097151 & load3(&b[21..]);
301    let b9 = 2097151 & (load4(&b[23..]) >> 5);
302    let b10 = 2097151 & (load3(&b[26..]) >> 2);
303    let b11 = load4(&b[28..]) >> 7;
304    let c0 = 2097151 & load3(&c[..]);
305    let c1 = 2097151 & (load4(&c[2..]) >> 5);
306    let c2 = 2097151 & (load3(&c[5..]) >> 2);
307    let c3 = 2097151 & (load4(&c[7..]) >> 7);
308    let c4 = 2097151 & (load4(&c[10..]) >> 4);
309    let c5 = 2097151 & (load3(&c[13..]) >> 1);
310    let c6 = 2097151 & (load4(&c[15..]) >> 6);
311    let c7 = 2097151 & (load3(&c[18..]) >> 3);
312    let c8 = 2097151 & load3(&c[21..]);
313    let c9 = 2097151 & (load4(&c[23..]) >> 5);
314    let c10 = 2097151 & (load3(&c[26..]) >> 2);
315    let c11 = load4(&c[28..]) >> 7;
316    let mut carry = [0_i64; 23];
317
318    let mut s0 = c0 + a0 * b0;
319    let mut s1 = c1 + a0 * b1 + a1 * b0;
320    let mut s2 = c2 + a0 * b2 + a1 * b1 + a2 * b0;
321    let mut s3 = c3 + a0 * b3 + a1 * b2 + a2 * b1 + a3 * b0;
322    let mut s4 = c4 + a0 * b4 + a1 * b3 + a2 * b2 + a3 * b1 + a4 * b0;
323    let mut s5 = c5 + a0 * b5 + a1 * b4 + a2 * b3 + a3 * b2 + a4 * b1 + a5 * b0;
324    let mut s6 = c6 + a0 * b6 + a1 * b5 + a2 * b4 + a3 * b3 + a4 * b2 + a5 * b1 + a6 * b0;
325    let mut s7 = c7 + a0 * b7 + a1 * b6 + a2 * b5 + a3 * b4 + a4 * b3 + a5 * b2 + a6 * b1 + a7 * b0;
326    let mut s8 = c8
327        + a0 * b8
328        + a1 * b7
329        + a2 * b6
330        + a3 * b5
331        + a4 * b4
332        + a5 * b3
333        + a6 * b2
334        + a7 * b1
335        + a8 * b0;
336    let mut s9 = c9
337        + a0 * b9
338        + a1 * b8
339        + a2 * b7
340        + a3 * b6
341        + a4 * b5
342        + a5 * b4
343        + a6 * b3
344        + a7 * b2
345        + a8 * b1
346        + a9 * b0;
347    let mut s10 = c10
348        + a0 * b10
349        + a1 * b9
350        + a2 * b8
351        + a3 * b7
352        + a4 * b6
353        + a5 * b5
354        + a6 * b4
355        + a7 * b3
356        + a8 * b2
357        + a9 * b1
358        + a10 * b0;
359    let mut s11 = c11
360        + a0 * b11
361        + a1 * b10
362        + a2 * b9
363        + a3 * b8
364        + a4 * b7
365        + a5 * b6
366        + a6 * b5
367        + a7 * b4
368        + a8 * b3
369        + a9 * b2
370        + a10 * b1
371        + a11 * b0;
372    let mut s12 = a1 * b11
373        + a2 * b10
374        + a3 * b9
375        + a4 * b8
376        + a5 * b7
377        + a6 * b6
378        + a7 * b5
379        + a8 * b4
380        + a9 * b3
381        + a10 * b2
382        + a11 * b1;
383    let mut s13 = a2 * b11
384        + a3 * b10
385        + a4 * b9
386        + a5 * b8
387        + a6 * b7
388        + a7 * b6
389        + a8 * b5
390        + a9 * b4
391        + a10 * b3
392        + a11 * b2;
393    let mut s14 =
394        a3 * b11 + a4 * b10 + a5 * b9 + a6 * b8 + a7 * b7 + a8 * b6 + a9 * b5 + a10 * b4 + a11 * b3;
395    let mut s15 = a4 * b11 + a5 * b10 + a6 * b9 + a7 * b8 + a8 * b7 + a9 * b6 + a10 * b5 + a11 * b4;
396    let mut s16 = a5 * b11 + a6 * b10 + a7 * b9 + a8 * b8 + a9 * b7 + a10 * b6 + a11 * b5;
397    let mut s17 = a6 * b11 + a7 * b10 + a8 * b9 + a9 * b8 + a10 * b7 + a11 * b6;
398    let mut s18 = a7 * b11 + a8 * b10 + a9 * b9 + a10 * b8 + a11 * b7;
399    let mut s19 = a8 * b11 + a9 * b10 + a10 * b9 + a11 * b8;
400    let mut s20 = a9 * b11 + a10 * b10 + a11 * b9;
401    let mut s21 = a10 * b11 + a11 * b10;
402    let mut s22 = a11 * b11;
403    let mut s23 = 0_i64;
404
405    carry[0] = (s0 + (1 << 20)) >> 21;
406    s1 += carry[0];
407    s0 -= carry[0] << 21;
408    carry[2] = (s2 + (1 << 20)) >> 21;
409    s3 += carry[2];
410    s2 -= carry[2] << 21;
411    carry[4] = (s4 + (1 << 20)) >> 21;
412    s5 += carry[4];
413    s4 -= carry[4] << 21;
414    carry[6] = (s6 + (1 << 20)) >> 21;
415    s7 += carry[6];
416    s6 -= carry[6] << 21;
417    carry[8] = (s8 + (1 << 20)) >> 21;
418    s9 += carry[8];
419    s8 -= carry[8] << 21;
420    carry[10] = (s10 + (1 << 20)) >> 21;
421    s11 += carry[10];
422    s10 -= carry[10] << 21;
423    carry[12] = (s12 + (1 << 20)) >> 21;
424    s13 += carry[12];
425    s12 -= carry[12] << 21;
426    carry[14] = (s14 + (1 << 20)) >> 21;
427    s15 += carry[14];
428    s14 -= carry[14] << 21;
429    carry[16] = (s16 + (1 << 20)) >> 21;
430    s17 += carry[16];
431    s16 -= carry[16] << 21;
432    carry[18] = (s18 + (1 << 20)) >> 21;
433    s19 += carry[18];
434    s18 -= carry[18] << 21;
435    carry[20] = (s20 + (1 << 20)) >> 21;
436    s21 += carry[20];
437    s20 -= carry[20] << 21;
438    carry[22] = (s22 + (1 << 20)) >> 21;
439    s23 += carry[22];
440    s22 -= carry[22] << 21;
441    carry[1] = (s1 + (1 << 20)) >> 21;
442    s2 += carry[1];
443    s1 -= carry[1] << 21;
444    carry[3] = (s3 + (1 << 20)) >> 21;
445    s4 += carry[3];
446    s3 -= carry[3] << 21;
447    carry[5] = (s5 + (1 << 20)) >> 21;
448    s6 += carry[5];
449    s5 -= carry[5] << 21;
450    carry[7] = (s7 + (1 << 20)) >> 21;
451    s8 += carry[7];
452    s7 -= carry[7] << 21;
453    carry[9] = (s9 + (1 << 20)) >> 21;
454    s10 += carry[9];
455    s9 -= carry[9] << 21;
456    carry[11] = (s11 + (1 << 20)) >> 21;
457    s12 += carry[11];
458    s11 -= carry[11] << 21;
459    carry[13] = (s13 + (1 << 20)) >> 21;
460    s14 += carry[13];
461    s13 -= carry[13] << 21;
462    carry[15] = (s15 + (1 << 20)) >> 21;
463    s16 += carry[15];
464    s15 -= carry[15] << 21;
465    carry[17] = (s17 + (1 << 20)) >> 21;
466    s18 += carry[17];
467    s17 -= carry[17] << 21;
468    carry[19] = (s19 + (1 << 20)) >> 21;
469    s20 += carry[19];
470    s19 -= carry[19] << 21;
471    carry[21] = (s21 + (1 << 20)) >> 21;
472    s22 += carry[21];
473    s21 -= carry[21] << 21;
474    s11 += s23 * 666643;
475    s12 += s23 * 470296;
476    s13 += s23 * 654183;
477    s14 -= s23 * 997805;
478    s15 += s23 * 136657;
479    s16 -= s23 * 683901;
480    // s23 = 0;
481    s10 += s22 * 666643;
482    s11 += s22 * 470296;
483    s12 += s22 * 654183;
484    s13 -= s22 * 997805;
485    s14 += s22 * 136657;
486    s15 -= s22 * 683901;
487    // s22 = 0;
488    s9 += s21 * 666643;
489    s10 += s21 * 470296;
490    s11 += s21 * 654183;
491    s12 -= s21 * 997805;
492    s13 += s21 * 136657;
493    s14 -= s21 * 683901;
494    // s21 = 0;
495    s8 += s20 * 666643;
496    s9 += s20 * 470296;
497    s10 += s20 * 654183;
498    s11 -= s20 * 997805;
499    s12 += s20 * 136657;
500    s13 -= s20 * 683901;
501    // s20 = 0;
502    s7 += s19 * 666643;
503    s8 += s19 * 470296;
504    s9 += s19 * 654183;
505    s10 -= s19 * 997805;
506    s11 += s19 * 136657;
507    s12 -= s19 * 683901;
508    // s19 = 0;
509    s6 += s18 * 666643;
510    s7 += s18 * 470296;
511    s8 += s18 * 654183;
512    s9 -= s18 * 997805;
513    s10 += s18 * 136657;
514    s11 -= s18 * 683901;
515    // s18 = 0;
516    carry[6] = (s6 + (1 << 20)) >> 21;
517    s7 += carry[6];
518    s6 -= carry[6] << 21;
519    carry[8] = (s8 + (1 << 20)) >> 21;
520    s9 += carry[8];
521    s8 -= carry[8] << 21;
522    carry[10] = (s10 + (1 << 20)) >> 21;
523    s11 += carry[10];
524    s10 -= carry[10] << 21;
525    carry[12] = (s12 + (1 << 20)) >> 21;
526    s13 += carry[12];
527    s12 -= carry[12] << 21;
528    carry[14] = (s14 + (1 << 20)) >> 21;
529    s15 += carry[14];
530    s14 -= carry[14] << 21;
531    carry[16] = (s16 + (1 << 20)) >> 21;
532    s17 += carry[16];
533    s16 -= carry[16] << 21;
534    carry[7] = (s7 + (1 << 20)) >> 21;
535    s8 += carry[7];
536    s7 -= carry[7] << 21;
537    carry[9] = (s9 + (1 << 20)) >> 21;
538    s10 += carry[9];
539    s9 -= carry[9] << 21;
540    carry[11] = (s11 + (1 << 20)) >> 21;
541    s12 += carry[11];
542    s11 -= carry[11] << 21;
543    carry[13] = (s13 + (1 << 20)) >> 21;
544    s14 += carry[13];
545    s13 -= carry[13] << 21;
546    carry[15] = (s15 + (1 << 20)) >> 21;
547    s16 += carry[15];
548    s15 -= carry[15] << 21;
549    s5 += s17 * 666643;
550    s6 += s17 * 470296;
551    s7 += s17 * 654183;
552    s8 -= s17 * 997805;
553    s9 += s17 * 136657;
554    s10 -= s17 * 683901;
555    // s17 = 0;
556    s4 += s16 * 666643;
557    s5 += s16 * 470296;
558    s6 += s16 * 654183;
559    s7 -= s16 * 997805;
560    s8 += s16 * 136657;
561    s9 -= s16 * 683901;
562    // s16 = 0;
563    s3 += s15 * 666643;
564    s4 += s15 * 470296;
565    s5 += s15 * 654183;
566    s6 -= s15 * 997805;
567    s7 += s15 * 136657;
568    s8 -= s15 * 683901;
569    // s15 = 0;
570    s2 += s14 * 666643;
571    s3 += s14 * 470296;
572    s4 += s14 * 654183;
573    s5 -= s14 * 997805;
574    s6 += s14 * 136657;
575    s7 -= s14 * 683901;
576    // s14 = 0;
577    s1 += s13 * 666643;
578    s2 += s13 * 470296;
579    s3 += s13 * 654183;
580    s4 -= s13 * 997805;
581    s5 += s13 * 136657;
582    s6 -= s13 * 683901;
583    // s13 = 0;
584    s0 += s12 * 666643;
585    s1 += s12 * 470296;
586    s2 += s12 * 654183;
587    s3 -= s12 * 997805;
588    s4 += s12 * 136657;
589    s5 -= s12 * 683901;
590    s12 = 0;
591    carry[0] = (s0 + (1 << 20)) >> 21;
592    s1 += carry[0];
593    s0 -= carry[0] << 21;
594    carry[2] = (s2 + (1 << 20)) >> 21;
595    s3 += carry[2];
596    s2 -= carry[2] << 21;
597    carry[4] = (s4 + (1 << 20)) >> 21;
598    s5 += carry[4];
599    s4 -= carry[4] << 21;
600    carry[6] = (s6 + (1 << 20)) >> 21;
601    s7 += carry[6];
602    s6 -= carry[6] << 21;
603    carry[8] = (s8 + (1 << 20)) >> 21;
604    s9 += carry[8];
605    s8 -= carry[8] << 21;
606    carry[10] = (s10 + (1 << 20)) >> 21;
607    s11 += carry[10];
608    s10 -= carry[10] << 21;
609    carry[1] = (s1 + (1 << 20)) >> 21;
610    s2 += carry[1];
611    s1 -= carry[1] << 21;
612    carry[3] = (s3 + (1 << 20)) >> 21;
613    s4 += carry[3];
614    s3 -= carry[3] << 21;
615    carry[5] = (s5 + (1 << 20)) >> 21;
616    s6 += carry[5];
617    s5 -= carry[5] << 21;
618    carry[7] = (s7 + (1 << 20)) >> 21;
619    s8 += carry[7];
620    s7 -= carry[7] << 21;
621    carry[9] = (s9 + (1 << 20)) >> 21;
622    s10 += carry[9];
623    s9 -= carry[9] << 21;
624    carry[11] = (s11 + (1 << 20)) >> 21;
625    s12 += carry[11];
626    s11 -= carry[11] << 21;
627    s0 += s12 * 666643;
628    s1 += s12 * 470296;
629    s2 += s12 * 654183;
630    s3 -= s12 * 997805;
631    s4 += s12 * 136657;
632    s5 -= s12 * 683901;
633    s12 = 0;
634    carry[0] = s0 >> 21;
635    s1 += carry[0];
636    s0 -= carry[0] << 21;
637    carry[1] = s1 >> 21;
638    s2 += carry[1];
639    s1 -= carry[1] << 21;
640    carry[2] = s2 >> 21;
641    s3 += carry[2];
642    s2 -= carry[2] << 21;
643    carry[3] = s3 >> 21;
644    s4 += carry[3];
645    s3 -= carry[3] << 21;
646    carry[4] = s4 >> 21;
647    s5 += carry[4];
648    s4 -= carry[4] << 21;
649    carry[5] = s5 >> 21;
650    s6 += carry[5];
651    s5 -= carry[5] << 21;
652    carry[6] = s6 >> 21;
653    s7 += carry[6];
654    s6 -= carry[6] << 21;
655    carry[7] = s7 >> 21;
656    s8 += carry[7];
657    s7 -= carry[7] << 21;
658    carry[8] = s8 >> 21;
659    s9 += carry[8];
660    s8 -= carry[8] << 21;
661    carry[9] = s9 >> 21;
662    s10 += carry[9];
663    s9 -= carry[9] << 21;
664    carry[10] = s10 >> 21;
665    s11 += carry[10];
666    s10 -= carry[10] << 21;
667    carry[11] = s11 >> 21;
668    s12 += carry[11];
669    s11 -= carry[11] << 21;
670    s0 += s12 * 666643;
671    s1 += s12 * 470296;
672    s2 += s12 * 654183;
673    s3 -= s12 * 997805;
674    s4 += s12 * 136657;
675    s5 -= s12 * 683901;
676    // s12 = 0;
677    carry[0] = s0 >> 21;
678    s1 += carry[0];
679    s0 -= carry[0] << 21;
680    carry[1] = s1 >> 21;
681    s2 += carry[1];
682    s1 -= carry[1] << 21;
683    carry[2] = s2 >> 21;
684    s3 += carry[2];
685    s2 -= carry[2] << 21;
686    carry[3] = s3 >> 21;
687    s4 += carry[3];
688    s3 -= carry[3] << 21;
689    carry[4] = s4 >> 21;
690    s5 += carry[4];
691    s4 -= carry[4] << 21;
692    carry[5] = s5 >> 21;
693    s6 += carry[5];
694    s5 -= carry[5] << 21;
695    carry[6] = s6 >> 21;
696    s7 += carry[6];
697    s6 -= carry[6] << 21;
698    carry[7] = s7 >> 21;
699    s8 += carry[7];
700    s7 -= carry[7] << 21;
701    carry[8] = s8 >> 21;
702    s9 += carry[8];
703    s8 -= carry[8] << 21;
704    carry[9] = s9 >> 21;
705    s10 += carry[9];
706    s9 -= carry[9] << 21;
707    carry[10] = s10 >> 21;
708    s11 += carry[10];
709    s10 -= carry[10] << 21;
710    //s[0] = (s0 >> 0) as u8;
711    s[0] = s0 as u8;
712    s[1] = (s0 >> 8) as u8;
713    s[2] = ((s0 >> 16) | (s1 << 5)) as u8;
714    s[3] = (s1 >> 3) as u8;
715    s[4] = (s1 >> 11) as u8;
716    s[5] = ((s1 >> 19) | (s2 << 2)) as u8;
717    s[6] = (s2 >> 6) as u8;
718    s[7] = ((s2 >> 14) | (s3 << 7)) as u8;
719    s[8] = (s3 >> 1) as u8;
720    s[9] = (s3 >> 9) as u8;
721    s[10] = ((s3 >> 17) | (s4 << 4)) as u8;
722    s[11] = (s4 >> 4) as u8;
723    s[12] = (s4 >> 12) as u8;
724    s[13] = ((s4 >> 20) | (s5 << 1)) as u8;
725    s[14] = (s5 >> 7) as u8;
726    s[15] = ((s5 >> 15) | (s6 << 6)) as u8;
727    s[16] = (s6 >> 2) as u8;
728    s[17] = (s6 >> 10) as u8;
729    s[18] = ((s6 >> 18) | (s7 << 3)) as u8;
730    s[19] = (s7 >> 5) as u8;
731    s[20] = (s7 >> 13) as u8;
732    //s[21] = (s8 >> 0) as u8;
733    s[21] = s8 as u8;
734    s[22] = (s8 >> 8) as u8;
735    s[23] = ((s8 >> 16) | (s9 << 5)) as u8;
736    s[24] = (s9 >> 3) as u8;
737    s[25] = (s9 >> 11) as u8;
738    s[26] = ((s9 >> 19) | (s10 << 2)) as u8;
739    s[27] = (s10 >> 6) as u8;
740    s[28] = ((s10 >> 14) | (s11 << 7)) as u8;
741    s[29] = (s11 >> 1) as u8;
742    s[30] = (s11 >> 9) as u8;
743    s[31] = (s11 >> 17) as u8;
744}
745
746/// Hacky [`sc_add()`] cobbled together rather sub-optimally from [`sc_mul_add()`].
747///
748/// Input:
749///
750///   `a[0]+256*a[1]+...+256^31*a[31] = a`
751///
752///   `c[0]+256*c[1]+...+256^31*c[31] = c`
753///
754/// Output:
755///
756///   `s[0]+256*s[1]+...+256^31*s[31] = (a+c) mod l`
757///
758///   where `l = 2^252 + 27742317777372353535851937790883648493`.
759fn sc_add(s: &mut [u8; 32], a: &[u8; 32], c: &[u8; 32]) {
760    let a0 = 2097151 & load3(&a[..]);
761    let a1 = 2097151 & (load4(&a[2..]) >> 5);
762    let a2 = 2097151 & (load3(&a[5..]) >> 2);
763    let a3 = 2097151 & (load4(&a[7..]) >> 7);
764    let a4 = 2097151 & (load4(&a[10..]) >> 4);
765    let a5 = 2097151 & (load3(&a[13..]) >> 1);
766    let a6 = 2097151 & (load4(&a[15..]) >> 6);
767    let a7 = 2097151 & (load3(&a[18..]) >> 3);
768    let a8 = 2097151 & load3(&a[21..]);
769    let a9 = 2097151 & (load4(&a[23..]) >> 5);
770    let a10 = 2097151 & (load3(&a[26..]) >> 2);
771    let a11 = load4(&a[28..]) >> 7;
772    let c0 = 2097151 & load3(&c[..]);
773    let c1 = 2097151 & (load4(&c[2..]) >> 5);
774    let c2 = 2097151 & (load3(&c[5..]) >> 2);
775    let c3 = 2097151 & (load4(&c[7..]) >> 7);
776    let c4 = 2097151 & (load4(&c[10..]) >> 4);
777    let c5 = 2097151 & (load3(&c[13..]) >> 1);
778    let c6 = 2097151 & (load4(&c[15..]) >> 6);
779    let c7 = 2097151 & (load3(&c[18..]) >> 3);
780    let c8 = 2097151 & load3(&c[21..]);
781    let c9 = 2097151 & (load4(&c[23..]) >> 5);
782    let c10 = 2097151 & (load3(&c[26..]) >> 2);
783    let c11 = load4(&c[28..]) >> 7;
784    let mut carry: [i64; 23] = [0; 23];
785
786    let mut s0 = c0 + a0;
787    let mut s1 = c1 + a1;
788    let mut s2 = c2 + a2;
789    let mut s3 = c3 + a3;
790    let mut s4 = c4 + a4;
791    let mut s5 = c5 + a5;
792    let mut s6 = c6 + a6;
793    let mut s7 = c7 + a7;
794    let mut s8 = c8 + a8;
795    let mut s9 = c9 + a9;
796    let mut s10 = c10 + a10;
797    let mut s11 = c11 + a11;
798    let mut s12 = 0;
799    let mut s13 = 0;
800    let mut s14 = 0;
801    let mut s15 = 0;
802    let mut s16 = 0;
803    let mut s17 = 0;
804    let mut s18 = 0;
805    let mut s19 = 0;
806    let mut s20 = 0;
807    let mut s21 = 0;
808    let mut s22 = 0;
809    let mut s23 = 0;
810
811    carry[0] = (s0 + (1 << 20)) >> 21;
812    s1 += carry[0];
813    s0 -= carry[0] << 21;
814    carry[2] = (s2 + (1 << 20)) >> 21;
815    s3 += carry[2];
816    s2 -= carry[2] << 21;
817    carry[4] = (s4 + (1 << 20)) >> 21;
818    s5 += carry[4];
819    s4 -= carry[4] << 21;
820    carry[6] = (s6 + (1 << 20)) >> 21;
821    s7 += carry[6];
822    s6 -= carry[6] << 21;
823    carry[8] = (s8 + (1 << 20)) >> 21;
824    s9 += carry[8];
825    s8 -= carry[8] << 21;
826    carry[10] = (s10 + (1 << 20)) >> 21;
827    s11 += carry[10];
828    s10 -= carry[10] << 21;
829    carry[12] = (s12 + (1 << 20)) >> 21;
830    s13 += carry[12];
831    s12 -= carry[12] << 21;
832    carry[14] = (s14 + (1 << 20)) >> 21;
833    s15 += carry[14];
834    s14 -= carry[14] << 21;
835    carry[16] = (s16 + (1 << 20)) >> 21;
836    s17 += carry[16];
837    s16 -= carry[16] << 21;
838    carry[18] = (s18 + (1 << 20)) >> 21;
839    s19 += carry[18];
840    s18 -= carry[18] << 21;
841    carry[20] = (s20 + (1 << 20)) >> 21;
842    s21 += carry[20];
843    s20 -= carry[20] << 21;
844    carry[22] = (s22 + (1 << 20)) >> 21;
845    s23 += carry[22];
846    s22 -= carry[22] << 21;
847
848    carry[1] = (s1 + (1 << 20)) >> 21;
849    s2 += carry[1];
850    s1 -= carry[1] << 21;
851    carry[3] = (s3 + (1 << 20)) >> 21;
852    s4 += carry[3];
853    s3 -= carry[3] << 21;
854    carry[5] = (s5 + (1 << 20)) >> 21;
855    s6 += carry[5];
856    s5 -= carry[5] << 21;
857    carry[7] = (s7 + (1 << 20)) >> 21;
858    s8 += carry[7];
859    s7 -= carry[7] << 21;
860    carry[9] = (s9 + (1 << 20)) >> 21;
861    s10 += carry[9];
862    s9 -= carry[9] << 21;
863    carry[11] = (s11 + (1 << 20)) >> 21;
864    s12 += carry[11];
865    s11 -= carry[11] << 21;
866    carry[13] = (s13 + (1 << 20)) >> 21;
867    s14 += carry[13];
868    s13 -= carry[13] << 21;
869    carry[15] = (s15 + (1 << 20)) >> 21;
870    s16 += carry[15];
871    s15 -= carry[15] << 21;
872    carry[17] = (s17 + (1 << 20)) >> 21;
873    s18 += carry[17];
874    s17 -= carry[17] << 21;
875    carry[19] = (s19 + (1 << 20)) >> 21;
876    s20 += carry[19];
877    s19 -= carry[19] << 21;
878    carry[21] = (s21 + (1 << 20)) >> 21;
879    s22 += carry[21];
880    s21 -= carry[21] << 21;
881
882    s11 += s23 * 666643;
883    s12 += s23 * 470296;
884    s13 += s23 * 654183;
885    s14 -= s23 * 997805;
886    s15 += s23 * 136657;
887    s16 -= s23 * 683901;
888    // s23 = 0;
889
890    s10 += s22 * 666643;
891    s11 += s22 * 470296;
892    s12 += s22 * 654183;
893    s13 -= s22 * 997805;
894    s14 += s22 * 136657;
895    s15 -= s22 * 683901;
896    // s22 = 0;
897
898    s9 += s21 * 666643;
899    s10 += s21 * 470296;
900    s11 += s21 * 654183;
901    s12 -= s21 * 997805;
902    s13 += s21 * 136657;
903    s14 -= s21 * 683901;
904    // s21 = 0;
905
906    s8 += s20 * 666643;
907    s9 += s20 * 470296;
908    s10 += s20 * 654183;
909    s11 -= s20 * 997805;
910    s12 += s20 * 136657;
911    s13 -= s20 * 683901;
912    // s20 = 0;
913
914    s7 += s19 * 666643;
915    s8 += s19 * 470296;
916    s9 += s19 * 654183;
917    s10 -= s19 * 997805;
918    s11 += s19 * 136657;
919    s12 -= s19 * 683901;
920    // s19 = 0;
921
922    s6 += s18 * 666643;
923    s7 += s18 * 470296;
924    s8 += s18 * 654183;
925    s9 -= s18 * 997805;
926    s10 += s18 * 136657;
927    s11 -= s18 * 683901;
928    // s18 = 0;
929
930    carry[6] = (s6 + (1 << 20)) >> 21;
931    s7 += carry[6];
932    s6 -= carry[6] << 21;
933    carry[8] = (s8 + (1 << 20)) >> 21;
934    s9 += carry[8];
935    s8 -= carry[8] << 21;
936    carry[10] = (s10 + (1 << 20)) >> 21;
937    s11 += carry[10];
938    s10 -= carry[10] << 21;
939    carry[12] = (s12 + (1 << 20)) >> 21;
940    s13 += carry[12];
941    s12 -= carry[12] << 21;
942    carry[14] = (s14 + (1 << 20)) >> 21;
943    s15 += carry[14];
944    s14 -= carry[14] << 21;
945    carry[16] = (s16 + (1 << 20)) >> 21;
946    s17 += carry[16];
947    s16 -= carry[16] << 21;
948
949    carry[7] = (s7 + (1 << 20)) >> 21;
950    s8 += carry[7];
951    s7 -= carry[7] << 21;
952    carry[9] = (s9 + (1 << 20)) >> 21;
953    s10 += carry[9];
954    s9 -= carry[9] << 21;
955    carry[11] = (s11 + (1 << 20)) >> 21;
956    s12 += carry[11];
957    s11 -= carry[11] << 21;
958    carry[13] = (s13 + (1 << 20)) >> 21;
959    s14 += carry[13];
960    s13 -= carry[13] << 21;
961    carry[15] = (s15 + (1 << 20)) >> 21;
962    s16 += carry[15];
963    s15 -= carry[15] << 21;
964
965    s5 += s17 * 666643;
966    s6 += s17 * 470296;
967    s7 += s17 * 654183;
968    s8 -= s17 * 997805;
969    s9 += s17 * 136657;
970    s10 -= s17 * 683901;
971    // s17 = 0;
972
973    s4 += s16 * 666643;
974    s5 += s16 * 470296;
975    s6 += s16 * 654183;
976    s7 -= s16 * 997805;
977    s8 += s16 * 136657;
978    s9 -= s16 * 683901;
979    // s16 = 0;
980
981    s3 += s15 * 666643;
982    s4 += s15 * 470296;
983    s5 += s15 * 654183;
984    s6 -= s15 * 997805;
985    s7 += s15 * 136657;
986    s8 -= s15 * 683901;
987    // s15 = 0;
988
989    s2 += s14 * 666643;
990    s3 += s14 * 470296;
991    s4 += s14 * 654183;
992    s5 -= s14 * 997805;
993    s6 += s14 * 136657;
994    s7 -= s14 * 683901;
995    // s14 = 0;
996
997    s1 += s13 * 666643;
998    s2 += s13 * 470296;
999    s3 += s13 * 654183;
1000    s4 -= s13 * 997805;
1001    s5 += s13 * 136657;
1002    s6 -= s13 * 683901;
1003    // s13 = 0;
1004
1005    s0 += s12 * 666643;
1006    s1 += s12 * 470296;
1007    s2 += s12 * 654183;
1008    s3 -= s12 * 997805;
1009    s4 += s12 * 136657;
1010    s5 -= s12 * 683901;
1011    s12 = 0;
1012
1013    carry[0] = (s0 + (1 << 20)) >> 21;
1014    s1 += carry[0];
1015    s0 -= carry[0] << 21;
1016    carry[2] = (s2 + (1 << 20)) >> 21;
1017    s3 += carry[2];
1018    s2 -= carry[2] << 21;
1019    carry[4] = (s4 + (1 << 20)) >> 21;
1020    s5 += carry[4];
1021    s4 -= carry[4] << 21;
1022    carry[6] = (s6 + (1 << 20)) >> 21;
1023    s7 += carry[6];
1024    s6 -= carry[6] << 21;
1025    carry[8] = (s8 + (1 << 20)) >> 21;
1026    s9 += carry[8];
1027    s8 -= carry[8] << 21;
1028    carry[10] = (s10 + (1 << 20)) >> 21;
1029    s11 += carry[10];
1030    s10 -= carry[10] << 21;
1031
1032    carry[1] = (s1 + (1 << 20)) >> 21;
1033    s2 += carry[1];
1034    s1 -= carry[1] << 21;
1035    carry[3] = (s3 + (1 << 20)) >> 21;
1036    s4 += carry[3];
1037    s3 -= carry[3] << 21;
1038    carry[5] = (s5 + (1 << 20)) >> 21;
1039    s6 += carry[5];
1040    s5 -= carry[5] << 21;
1041    carry[7] = (s7 + (1 << 20)) >> 21;
1042    s8 += carry[7];
1043    s7 -= carry[7] << 21;
1044    carry[9] = (s9 + (1 << 20)) >> 21;
1045    s10 += carry[9];
1046    s9 -= carry[9] << 21;
1047    carry[11] = (s11 + (1 << 20)) >> 21;
1048    s12 += carry[11];
1049    s11 -= carry[11] << 21;
1050
1051    s0 += s12 * 666643;
1052    s1 += s12 * 470296;
1053    s2 += s12 * 654183;
1054    s3 -= s12 * 997805;
1055    s4 += s12 * 136657;
1056    s5 -= s12 * 683901;
1057    s12 = 0;
1058
1059    carry[0] = s0 >> 21;
1060    s1 += carry[0];
1061    s0 -= carry[0] << 21;
1062    carry[1] = s1 >> 21;
1063    s2 += carry[1];
1064    s1 -= carry[1] << 21;
1065    carry[2] = s2 >> 21;
1066    s3 += carry[2];
1067    s2 -= carry[2] << 21;
1068    carry[3] = s3 >> 21;
1069    s4 += carry[3];
1070    s3 -= carry[3] << 21;
1071    carry[4] = s4 >> 21;
1072    s5 += carry[4];
1073    s4 -= carry[4] << 21;
1074    carry[5] = s5 >> 21;
1075    s6 += carry[5];
1076    s5 -= carry[5] << 21;
1077    carry[6] = s6 >> 21;
1078    s7 += carry[6];
1079    s6 -= carry[6] << 21;
1080    carry[7] = s7 >> 21;
1081    s8 += carry[7];
1082    s7 -= carry[7] << 21;
1083    carry[8] = s8 >> 21;
1084    s9 += carry[8];
1085    s8 -= carry[8] << 21;
1086    carry[9] = s9 >> 21;
1087    s10 += carry[9];
1088    s9 -= carry[9] << 21;
1089    carry[10] = s10 >> 21;
1090    s11 += carry[10];
1091    s10 -= carry[10] << 21;
1092    carry[11] = s11 >> 21;
1093    s12 += carry[11];
1094    s11 -= carry[11] << 21;
1095
1096    s0 += s12 * 666643;
1097    s1 += s12 * 470296;
1098    s2 += s12 * 654183;
1099    s3 -= s12 * 997805;
1100    s4 += s12 * 136657;
1101    s5 -= s12 * 683901;
1102    // s12 = 0;
1103
1104    carry[0] = s0 >> 21;
1105    s1 += carry[0];
1106    s0 -= carry[0] << 21;
1107    carry[1] = s1 >> 21;
1108    s2 += carry[1];
1109    s1 -= carry[1] << 21;
1110    carry[2] = s2 >> 21;
1111    s3 += carry[2];
1112    s2 -= carry[2] << 21;
1113    carry[3] = s3 >> 21;
1114    s4 += carry[3];
1115    s3 -= carry[3] << 21;
1116    carry[4] = s4 >> 21;
1117    s5 += carry[4];
1118    s4 -= carry[4] << 21;
1119    carry[5] = s5 >> 21;
1120    s6 += carry[5];
1121    s5 -= carry[5] << 21;
1122    carry[6] = s6 >> 21;
1123    s7 += carry[6];
1124    s6 -= carry[6] << 21;
1125    carry[7] = s7 >> 21;
1126    s8 += carry[7];
1127    s7 -= carry[7] << 21;
1128    carry[8] = s8 >> 21;
1129    s9 += carry[8];
1130    s8 -= carry[8] << 21;
1131    carry[9] = s9 >> 21;
1132    s10 += carry[9];
1133    s9 -= carry[9] << 21;
1134    carry[10] = s10 >> 21;
1135    s11 += carry[10];
1136    s10 -= carry[10] << 21;
1137
1138    //s[0] = (s0 >> 0) as u8;
1139    s[0] = s0 as u8;
1140    s[1] = (s0 >> 8) as u8;
1141    s[2] = ((s0 >> 16) | (s1 << 5)) as u8;
1142    s[3] = (s1 >> 3) as u8;
1143    s[4] = (s1 >> 11) as u8;
1144    s[5] = ((s1 >> 19) | (s2 << 2)) as u8;
1145    s[6] = (s2 >> 6) as u8;
1146    s[7] = ((s2 >> 14) | (s3 << 7)) as u8;
1147    s[8] = (s3 >> 1) as u8;
1148    s[9] = (s3 >> 9) as u8;
1149    s[10] = ((s3 >> 17) | (s4 << 4)) as u8;
1150    s[11] = (s4 >> 4) as u8;
1151    s[12] = (s4 >> 12) as u8;
1152    s[13] = ((s4 >> 20) | (s5 << 1)) as u8;
1153    s[14] = (s5 >> 7) as u8;
1154    s[15] = ((s5 >> 15) | (s6 << 6)) as u8;
1155    s[16] = (s6 >> 2) as u8;
1156    s[17] = (s6 >> 10) as u8;
1157    s[18] = ((s6 >> 18) | (s7 << 3)) as u8;
1158    s[19] = (s7 >> 5) as u8;
1159    s[20] = (s7 >> 13) as u8;
1160    //s[21] = (s8 >> 0) as u8;
1161    s[21] = s8 as u8;
1162    s[22] = (s8 >> 8) as u8;
1163    s[23] = ((s8 >> 16) | (s9 << 5)) as u8;
1164    s[24] = (s9 >> 3) as u8;
1165    s[25] = (s9 >> 11) as u8;
1166    s[26] = ((s9 >> 19) | (s10 << 2)) as u8;
1167    s[27] = (s10 >> 6) as u8;
1168    s[28] = ((s10 >> 14) | (s11 << 7)) as u8;
1169    s[29] = (s11 >> 1) as u8;
1170    s[30] = (s11 >> 9) as u8;
1171    s[31] = (s11 >> 17) as u8;
1172}
1173
1174/// Hacky [`sc_sub()`] cobbled together rather sub-optimally from [`sc_mul_add()`].
1175///
1176/// Input:
1177///
1178///   `a[0]+256*a[1]+...+256^31*a[31] = a`
1179///
1180///   `c[0]+256*c[1]+...+256^31*c[31] = c`
1181///
1182/// Output:
1183///
1184///   `s[0]+256*s[1]+...+256^31*s[31] = (a-c) mod l`
1185///
1186///   where `l = 2^252 + 27742317777372353535851937790883648493`.
1187fn sc_sub(s: &mut [u8; 32], a: &[u8; 32], c: &[u8; 32]) {
1188    let a0 = 2097151 & load3(&a[..]);
1189    let a1 = 2097151 & (load4(&a[2..]) >> 5);
1190    let a2 = 2097151 & (load3(&a[5..]) >> 2);
1191    let a3 = 2097151 & (load4(&a[7..]) >> 7);
1192    let a4 = 2097151 & (load4(&a[10..]) >> 4);
1193    let a5 = 2097151 & (load3(&a[13..]) >> 1);
1194    let a6 = 2097151 & (load4(&a[15..]) >> 6);
1195    let a7 = 2097151 & (load3(&a[18..]) >> 3);
1196    let a8 = 2097151 & load3(&a[21..]);
1197    let a9 = 2097151 & (load4(&a[23..]) >> 5);
1198    let a10 = 2097151 & (load3(&a[26..]) >> 2);
1199    let a11 = load4(&a[28..]) >> 7;
1200    let c0 = 2097151 & load3(&c[..]);
1201    let c1 = 2097151 & (load4(&c[2..]) >> 5);
1202    let c2 = 2097151 & (load3(&c[5..]) >> 2);
1203    let c3 = 2097151 & (load4(&c[7..]) >> 7);
1204    let c4 = 2097151 & (load4(&c[10..]) >> 4);
1205    let c5 = 2097151 & (load3(&c[13..]) >> 1);
1206    let c6 = 2097151 & (load4(&c[15..]) >> 6);
1207    let c7 = 2097151 & (load3(&c[18..]) >> 3);
1208    let c8 = 2097151 & load3(&c[21..]);
1209    let c9 = 2097151 & (load4(&c[23..]) >> 5);
1210    let c10 = 2097151 & (load3(&c[26..]) >> 2);
1211    let c11 = load4(&c[28..]) >> 7;
1212    let mut carry = [0_i64; 23]; // [23]int64;
1213
1214    let mut s0 = 1916624 - c0 + a0;
1215    let mut s1 = 863866 - c1 + a1;
1216    let mut s2 = 18828 - c2 + a2;
1217    let mut s3 = 1284811 - c3 + a3;
1218    let mut s4 = 2007799 - c4 + a4;
1219    let mut s5 = 456654 - c5 + a5;
1220    let mut s6 = 5 - c6 + a6;
1221    let mut s7 = 0 - c7 + a7;
1222    let mut s8 = 0 - c8 + a8;
1223    let mut s9 = 0 - c9 + a9;
1224    let mut s10 = 0 - c10 + a10;
1225    let mut s11 = 0 - c11 + a11;
1226    let mut s12 = 16;
1227    let mut s13 = 0;
1228    let mut s14 = 0;
1229    let mut s15 = 0;
1230    let mut s16 = 0;
1231    let mut s17 = 0;
1232    let mut s18 = 0;
1233    let mut s19 = 0;
1234    let mut s20 = 0;
1235    let mut s21 = 0;
1236    let mut s22 = 0;
1237    let mut s23 = 0;
1238
1239    carry[0] = (s0 + (1 << 20)) >> 21;
1240    s1 += carry[0];
1241    s0 -= carry[0] << 21;
1242    carry[2] = (s2 + (1 << 20)) >> 21;
1243    s3 += carry[2];
1244    s2 -= carry[2] << 21;
1245    carry[4] = (s4 + (1 << 20)) >> 21;
1246    s5 += carry[4];
1247    s4 -= carry[4] << 21;
1248    carry[6] = (s6 + (1 << 20)) >> 21;
1249    s7 += carry[6];
1250    s6 -= carry[6] << 21;
1251    carry[8] = (s8 + (1 << 20)) >> 21;
1252    s9 += carry[8];
1253    s8 -= carry[8] << 21;
1254    carry[10] = (s10 + (1 << 20)) >> 21;
1255    s11 += carry[10];
1256    s10 -= carry[10] << 21;
1257    carry[12] = (s12 + (1 << 20)) >> 21;
1258    s13 += carry[12];
1259    s12 -= carry[12] << 21;
1260    carry[14] = (s14 + (1 << 20)) >> 21;
1261    s15 += carry[14];
1262    s14 -= carry[14] << 21;
1263    carry[16] = (s16 + (1 << 20)) >> 21;
1264    s17 += carry[16];
1265    s16 -= carry[16] << 21;
1266    carry[18] = (s18 + (1 << 20)) >> 21;
1267    s19 += carry[18];
1268    s18 -= carry[18] << 21;
1269    carry[20] = (s20 + (1 << 20)) >> 21;
1270    s21 += carry[20];
1271    s20 -= carry[20] << 21;
1272    carry[22] = (s22 + (1 << 20)) >> 21;
1273    s23 += carry[22];
1274    s22 -= carry[22] << 21;
1275
1276    carry[1] = (s1 + (1 << 20)) >> 21;
1277    s2 += carry[1];
1278    s1 -= carry[1] << 21;
1279    carry[3] = (s3 + (1 << 20)) >> 21;
1280    s4 += carry[3];
1281    s3 -= carry[3] << 21;
1282    carry[5] = (s5 + (1 << 20)) >> 21;
1283    s6 += carry[5];
1284    s5 -= carry[5] << 21;
1285    carry[7] = (s7 + (1 << 20)) >> 21;
1286    s8 += carry[7];
1287    s7 -= carry[7] << 21;
1288    carry[9] = (s9 + (1 << 20)) >> 21;
1289    s10 += carry[9];
1290    s9 -= carry[9] << 21;
1291    carry[11] = (s11 + (1 << 20)) >> 21;
1292    s12 += carry[11];
1293    s11 -= carry[11] << 21;
1294    carry[13] = (s13 + (1 << 20)) >> 21;
1295    s14 += carry[13];
1296    s13 -= carry[13] << 21;
1297    carry[15] = (s15 + (1 << 20)) >> 21;
1298    s16 += carry[15];
1299    s15 -= carry[15] << 21;
1300    carry[17] = (s17 + (1 << 20)) >> 21;
1301    s18 += carry[17];
1302    s17 -= carry[17] << 21;
1303    carry[19] = (s19 + (1 << 20)) >> 21;
1304    s20 += carry[19];
1305    s19 -= carry[19] << 21;
1306    carry[21] = (s21 + (1 << 20)) >> 21;
1307    s22 += carry[21];
1308    s21 -= carry[21] << 21;
1309
1310    s11 += s23 * 666643;
1311    s12 += s23 * 470296;
1312    s13 += s23 * 654183;
1313    s14 -= s23 * 997805;
1314    s15 += s23 * 136657;
1315    s16 -= s23 * 683901;
1316    // s23 = 0;
1317
1318    s10 += s22 * 666643;
1319    s11 += s22 * 470296;
1320    s12 += s22 * 654183;
1321    s13 -= s22 * 997805;
1322    s14 += s22 * 136657;
1323    s15 -= s22 * 683901;
1324    // s22 = 0;
1325    s9 += s21 * 666643;
1326    s10 += s21 * 470296;
1327    s11 += s21 * 654183;
1328    s12 -= s21 * 997805;
1329    s13 += s21 * 136657;
1330    s14 -= s21 * 683901;
1331    // s21 = 0;
1332    s8 += s20 * 666643;
1333    s9 += s20 * 470296;
1334    s10 += s20 * 654183;
1335    s11 -= s20 * 997805;
1336    s12 += s20 * 136657;
1337    s13 -= s20 * 683901;
1338    // s20 = 0;
1339    s7 += s19 * 666643;
1340    s8 += s19 * 470296;
1341    s9 += s19 * 654183;
1342    s10 -= s19 * 997805;
1343    s11 += s19 * 136657;
1344    s12 -= s19 * 683901;
1345    // s19 = 0;
1346    s6 += s18 * 666643;
1347    s7 += s18 * 470296;
1348    s8 += s18 * 654183;
1349    s9 -= s18 * 997805;
1350    s10 += s18 * 136657;
1351    s11 -= s18 * 683901;
1352    // s18 = 0;
1353    carry[6] = (s6 + (1 << 20)) >> 21;
1354    s7 += carry[6];
1355    s6 -= carry[6] << 21;
1356    carry[8] = (s8 + (1 << 20)) >> 21;
1357    s9 += carry[8];
1358    s8 -= carry[8] << 21;
1359    carry[10] = (s10 + (1 << 20)) >> 21;
1360    s11 += carry[10];
1361    s10 -= carry[10] << 21;
1362    carry[12] = (s12 + (1 << 20)) >> 21;
1363    s13 += carry[12];
1364    s12 -= carry[12] << 21;
1365    carry[14] = (s14 + (1 << 20)) >> 21;
1366    s15 += carry[14];
1367    s14 -= carry[14] << 21;
1368    carry[16] = (s16 + (1 << 20)) >> 21;
1369    s17 += carry[16];
1370    s16 -= carry[16] << 21;
1371    carry[7] = (s7 + (1 << 20)) >> 21;
1372    s8 += carry[7];
1373    s7 -= carry[7] << 21;
1374    carry[9] = (s9 + (1 << 20)) >> 21;
1375    s10 += carry[9];
1376    s9 -= carry[9] << 21;
1377    carry[11] = (s11 + (1 << 20)) >> 21;
1378    s12 += carry[11];
1379    s11 -= carry[11] << 21;
1380    carry[13] = (s13 + (1 << 20)) >> 21;
1381    s14 += carry[13];
1382    s13 -= carry[13] << 21;
1383    carry[15] = (s15 + (1 << 20)) >> 21;
1384    s16 += carry[15];
1385    s15 -= carry[15] << 21;
1386    s5 += s17 * 666643;
1387    s6 += s17 * 470296;
1388    s7 += s17 * 654183;
1389    s8 -= s17 * 997805;
1390    s9 += s17 * 136657;
1391    s10 -= s17 * 683901;
1392    // s17 = 0;
1393    s4 += s16 * 666643;
1394    s5 += s16 * 470296;
1395    s6 += s16 * 654183;
1396    s7 -= s16 * 997805;
1397    s8 += s16 * 136657;
1398    s9 -= s16 * 683901;
1399    // s16 = 0;
1400    s3 += s15 * 666643;
1401    s4 += s15 * 470296;
1402    s5 += s15 * 654183;
1403    s6 -= s15 * 997805;
1404    s7 += s15 * 136657;
1405    s8 -= s15 * 683901;
1406    // s15 = 0;
1407    s2 += s14 * 666643;
1408    s3 += s14 * 470296;
1409    s4 += s14 * 654183;
1410    s5 -= s14 * 997805;
1411    s6 += s14 * 136657;
1412    s7 -= s14 * 683901;
1413    // s14 = 0;
1414    s1 += s13 * 666643;
1415    s2 += s13 * 470296;
1416    s3 += s13 * 654183;
1417    s4 -= s13 * 997805;
1418    s5 += s13 * 136657;
1419    s6 -= s13 * 683901;
1420    // s13 = 0;
1421    s0 += s12 * 666643;
1422    s1 += s12 * 470296;
1423    s2 += s12 * 654183;
1424    s3 -= s12 * 997805;
1425    s4 += s12 * 136657;
1426    s5 -= s12 * 683901;
1427    s12 = 0;
1428    carry[0] = (s0 + (1 << 20)) >> 21;
1429    s1 += carry[0];
1430    s0 -= carry[0] << 21;
1431    carry[2] = (s2 + (1 << 20)) >> 21;
1432    s3 += carry[2];
1433    s2 -= carry[2] << 21;
1434    carry[4] = (s4 + (1 << 20)) >> 21;
1435    s5 += carry[4];
1436    s4 -= carry[4] << 21;
1437    carry[6] = (s6 + (1 << 20)) >> 21;
1438    s7 += carry[6];
1439    s6 -= carry[6] << 21;
1440    carry[8] = (s8 + (1 << 20)) >> 21;
1441    s9 += carry[8];
1442    s8 -= carry[8] << 21;
1443    carry[10] = (s10 + (1 << 20)) >> 21;
1444    s11 += carry[10];
1445    s10 -= carry[10] << 21;
1446    carry[1] = (s1 + (1 << 20)) >> 21;
1447    s2 += carry[1];
1448    s1 -= carry[1] << 21;
1449    carry[3] = (s3 + (1 << 20)) >> 21;
1450    s4 += carry[3];
1451    s3 -= carry[3] << 21;
1452    carry[5] = (s5 + (1 << 20)) >> 21;
1453    s6 += carry[5];
1454    s5 -= carry[5] << 21;
1455    carry[7] = (s7 + (1 << 20)) >> 21;
1456    s8 += carry[7];
1457    s7 -= carry[7] << 21;
1458    carry[9] = (s9 + (1 << 20)) >> 21;
1459    s10 += carry[9];
1460    s9 -= carry[9] << 21;
1461    carry[11] = (s11 + (1 << 20)) >> 21;
1462    s12 += carry[11];
1463    s11 -= carry[11] << 21;
1464    s0 += s12 * 666643;
1465    s1 += s12 * 470296;
1466    s2 += s12 * 654183;
1467    s3 -= s12 * 997805;
1468    s4 += s12 * 136657;
1469    s5 -= s12 * 683901;
1470    s12 = 0;
1471    carry[0] = s0 >> 21;
1472    s1 += carry[0];
1473    s0 -= carry[0] << 21;
1474    carry[1] = s1 >> 21;
1475    s2 += carry[1];
1476    s1 -= carry[1] << 21;
1477    carry[2] = s2 >> 21;
1478    s3 += carry[2];
1479    s2 -= carry[2] << 21;
1480    carry[3] = s3 >> 21;
1481    s4 += carry[3];
1482    s3 -= carry[3] << 21;
1483    carry[4] = s4 >> 21;
1484    s5 += carry[4];
1485    s4 -= carry[4] << 21;
1486    carry[5] = s5 >> 21;
1487    s6 += carry[5];
1488    s5 -= carry[5] << 21;
1489    carry[6] = s6 >> 21;
1490    s7 += carry[6];
1491    s6 -= carry[6] << 21;
1492    carry[7] = s7 >> 21;
1493    s8 += carry[7];
1494    s7 -= carry[7] << 21;
1495    carry[8] = s8 >> 21;
1496    s9 += carry[8];
1497    s8 -= carry[8] << 21;
1498    carry[9] = s9 >> 21;
1499    s10 += carry[9];
1500    s9 -= carry[9] << 21;
1501    carry[10] = s10 >> 21;
1502    s11 += carry[10];
1503    s10 -= carry[10] << 21;
1504    carry[11] = s11 >> 21;
1505    s12 += carry[11];
1506    s11 -= carry[11] << 21;
1507    s0 += s12 * 666643;
1508    s1 += s12 * 470296;
1509    s2 += s12 * 654183;
1510    s3 -= s12 * 997805;
1511    s4 += s12 * 136657;
1512    s5 -= s12 * 683901;
1513    // s12 = 0;
1514    carry[0] = s0 >> 21;
1515    s1 += carry[0];
1516    s0 -= carry[0] << 21;
1517    carry[1] = s1 >> 21;
1518    s2 += carry[1];
1519    s1 -= carry[1] << 21;
1520    carry[2] = s2 >> 21;
1521    s3 += carry[2];
1522    s2 -= carry[2] << 21;
1523    carry[3] = s3 >> 21;
1524    s4 += carry[3];
1525    s3 -= carry[3] << 21;
1526    carry[4] = s4 >> 21;
1527    s5 += carry[4];
1528    s4 -= carry[4] << 21;
1529    carry[5] = s5 >> 21;
1530    s6 += carry[5];
1531    s5 -= carry[5] << 21;
1532    carry[6] = s6 >> 21;
1533    s7 += carry[6];
1534    s6 -= carry[6] << 21;
1535    carry[7] = s7 >> 21;
1536    s8 += carry[7];
1537    s7 -= carry[7] << 21;
1538    carry[8] = s8 >> 21;
1539    s9 += carry[8];
1540    s8 -= carry[8] << 21;
1541    carry[9] = s9 >> 21;
1542    s10 += carry[9];
1543    s9 -= carry[9] << 21;
1544    carry[10] = s10 >> 21;
1545    s11 += carry[10];
1546    s10 -= carry[10] << 21;
1547    //s[0] = (s0 >> 0) as u8;
1548    s[0] = s0 as u8;
1549    s[1] = (s0 >> 8) as u8;
1550    s[2] = ((s0 >> 16) | (s1 << 5)) as u8;
1551    s[3] = (s1 >> 3) as u8;
1552    s[4] = (s1 >> 11) as u8;
1553    s[5] = ((s1 >> 19) | (s2 << 2)) as u8;
1554    s[6] = (s2 >> 6) as u8;
1555    s[7] = ((s2 >> 14) | (s3 << 7)) as u8;
1556    s[8] = (s3 >> 1) as u8;
1557    s[9] = (s3 >> 9) as u8;
1558    s[10] = ((s3 >> 17) | (s4 << 4)) as u8;
1559    s[11] = (s4 >> 4) as u8;
1560    s[12] = (s4 >> 12) as u8;
1561    s[13] = ((s4 >> 20) | (s5 << 1)) as u8;
1562    s[14] = (s5 >> 7) as u8;
1563    s[15] = ((s5 >> 15) | (s6 << 6)) as u8;
1564    s[16] = (s6 >> 2) as u8;
1565    s[17] = (s6 >> 10) as u8;
1566    s[18] = ((s6 >> 18) | (s7 << 3)) as u8;
1567    s[19] = (s7 >> 5) as u8;
1568    s[20] = (s7 >> 13) as u8;
1569    //s[21] = (s8 >> 0) as u8;
1570    s[21] = s8 as u8;
1571    s[22] = (s8 >> 8) as u8;
1572    s[23] = ((s8 >> 16) | (s9 << 5)) as u8;
1573    s[24] = (s9 >> 3) as u8;
1574    s[25] = (s9 >> 11) as u8;
1575    s[26] = ((s9 >> 19) | (s10 << 2)) as u8;
1576    s[27] = (s10 >> 6) as u8;
1577    s[28] = ((s10 >> 14) | (s11 << 7)) as u8;
1578    s[29] = (s11 >> 1) as u8;
1579    s[30] = (s11 >> 9) as u8;
1580    s[31] = (s11 >> 17) as u8;
1581}
1582
1583/// Hacky [`sc_mul()`] cobbled together rather sub-optimally from [`sc_mul_add()`].
1584///
1585/// Input:
1586///
1587///   `a[0]+256*a[1]+...+256^31*a[31] = a`
1588///
1589///   `b[0]+256*b[1]+...+256^31*b[31] = b`
1590///
1591/// Output:
1592///
1593///   `s[0]+256*s[1]+...+256^31*s[31] = (ab) mod l`
1594///
1595///   where `l = 2^252 + 27742317777372353535851937790883648493`.
1596fn sc_mul(s: &mut [u8; 32], a: &[u8; 32], b: &[u8; 32]) {
1597    let a0 = 2097151 & load3(&a[..]);
1598    let a1 = 2097151 & (load4(&a[2..]) >> 5);
1599    let a2 = 2097151 & (load3(&a[5..]) >> 2);
1600    let a3 = 2097151 & (load4(&a[7..]) >> 7);
1601    let a4 = 2097151 & (load4(&a[10..]) >> 4);
1602    let a5 = 2097151 & (load3(&a[13..]) >> 1);
1603    let a6 = 2097151 & (load4(&a[15..]) >> 6);
1604    let a7 = 2097151 & (load3(&a[18..]) >> 3);
1605    let a8 = 2097151 & load3(&a[21..]);
1606    let a9 = 2097151 & (load4(&a[23..]) >> 5);
1607    let a10 = 2097151 & (load3(&a[26..]) >> 2);
1608    let a11 = load4(&a[28..]) >> 7;
1609    let b0 = 2097151 & load3(&b[..]);
1610    let b1 = 2097151 & (load4(&b[2..]) >> 5);
1611    let b2 = 2097151 & (load3(&b[5..]) >> 2);
1612    let b3 = 2097151 & (load4(&b[7..]) >> 7);
1613    let b4 = 2097151 & (load4(&b[10..]) >> 4);
1614    let b5 = 2097151 & (load3(&b[13..]) >> 1);
1615    let b6 = 2097151 & (load4(&b[15..]) >> 6);
1616    let b7 = 2097151 & (load3(&b[18..]) >> 3);
1617    let b8 = 2097151 & load3(&b[21..]);
1618    let b9 = 2097151 & (load4(&b[23..]) >> 5);
1619    let b10 = 2097151 & (load3(&b[26..]) >> 2);
1620    let b11 = load4(&b[28..]) >> 7;
1621    let c0 = 0;
1622    let c1 = 0;
1623    let c2 = 0;
1624    let c3 = 0;
1625    let c4 = 0;
1626    let c5 = 0;
1627    let c6 = 0;
1628    let c7 = 0;
1629    let c8 = 0;
1630    let c9 = 0;
1631    let c10 = 0;
1632    let c11 = 0;
1633    let mut carry: [i64; 23] = [0; 23];
1634
1635    let mut s0 = c0 + a0 * b0;
1636    let mut s1 = c1 + a0 * b1 + a1 * b0;
1637    let mut s2 = c2 + a0 * b2 + a1 * b1 + a2 * b0;
1638    let mut s3 = c3 + a0 * b3 + a1 * b2 + a2 * b1 + a3 * b0;
1639    let mut s4 = c4 + a0 * b4 + a1 * b3 + a2 * b2 + a3 * b1 + a4 * b0;
1640    let mut s5 = c5 + a0 * b5 + a1 * b4 + a2 * b3 + a3 * b2 + a4 * b1 + a5 * b0;
1641    let mut s6 = c6 + a0 * b6 + a1 * b5 + a2 * b4 + a3 * b3 + a4 * b2 + a5 * b1 + a6 * b0;
1642    let mut s7 = c7 + a0 * b7 + a1 * b6 + a2 * b5 + a3 * b4 + a4 * b3 + a5 * b2 + a6 * b1 + a7 * b0;
1643    let mut s8 = c8
1644        + a0 * b8
1645        + a1 * b7
1646        + a2 * b6
1647        + a3 * b5
1648        + a4 * b4
1649        + a5 * b3
1650        + a6 * b2
1651        + a7 * b1
1652        + a8 * b0;
1653    let mut s9 = c9
1654        + a0 * b9
1655        + a1 * b8
1656        + a2 * b7
1657        + a3 * b6
1658        + a4 * b5
1659        + a5 * b4
1660        + a6 * b3
1661        + a7 * b2
1662        + a8 * b1
1663        + a9 * b0;
1664    let mut s10 = c10
1665        + a0 * b10
1666        + a1 * b9
1667        + a2 * b8
1668        + a3 * b7
1669        + a4 * b6
1670        + a5 * b5
1671        + a6 * b4
1672        + a7 * b3
1673        + a8 * b2
1674        + a9 * b1
1675        + a10 * b0;
1676    let mut s11 = c11
1677        + a0 * b11
1678        + a1 * b10
1679        + a2 * b9
1680        + a3 * b8
1681        + a4 * b7
1682        + a5 * b6
1683        + a6 * b5
1684        + a7 * b4
1685        + a8 * b3
1686        + a9 * b2
1687        + a10 * b1
1688        + a11 * b0;
1689    let mut s12 = a1 * b11
1690        + a2 * b10
1691        + a3 * b9
1692        + a4 * b8
1693        + a5 * b7
1694        + a6 * b6
1695        + a7 * b5
1696        + a8 * b4
1697        + a9 * b3
1698        + a10 * b2
1699        + a11 * b1;
1700    let mut s13 = a2 * b11
1701        + a3 * b10
1702        + a4 * b9
1703        + a5 * b8
1704        + a6 * b7
1705        + a7 * b6
1706        + a8 * b5
1707        + a9 * b4
1708        + a10 * b3
1709        + a11 * b2;
1710    let mut s14 =
1711        a3 * b11 + a4 * b10 + a5 * b9 + a6 * b8 + a7 * b7 + a8 * b6 + a9 * b5 + a10 * b4 + a11 * b3;
1712    let mut s15 = a4 * b11 + a5 * b10 + a6 * b9 + a7 * b8 + a8 * b7 + a9 * b6 + a10 * b5 + a11 * b4;
1713    let mut s16 = a5 * b11 + a6 * b10 + a7 * b9 + a8 * b8 + a9 * b7 + a10 * b6 + a11 * b5;
1714    let mut s17 = a6 * b11 + a7 * b10 + a8 * b9 + a9 * b8 + a10 * b7 + a11 * b6;
1715    let mut s18 = a7 * b11 + a8 * b10 + a9 * b9 + a10 * b8 + a11 * b7;
1716    let mut s19 = a8 * b11 + a9 * b10 + a10 * b9 + a11 * b8;
1717    let mut s20 = a9 * b11 + a10 * b10 + a11 * b9;
1718    let mut s21 = a10 * b11 + a11 * b10;
1719    let mut s22 = a11 * b11;
1720    let mut s23 = 0;
1721
1722    carry[0] = (s0 + (1 << 20)) >> 21;
1723    s1 += carry[0];
1724    s0 -= carry[0] << 21;
1725    carry[2] = (s2 + (1 << 20)) >> 21;
1726    s3 += carry[2];
1727    s2 -= carry[2] << 21;
1728    carry[4] = (s4 + (1 << 20)) >> 21;
1729    s5 += carry[4];
1730    s4 -= carry[4] << 21;
1731    carry[6] = (s6 + (1 << 20)) >> 21;
1732    s7 += carry[6];
1733    s6 -= carry[6] << 21;
1734    carry[8] = (s8 + (1 << 20)) >> 21;
1735    s9 += carry[8];
1736    s8 -= carry[8] << 21;
1737    carry[10] = (s10 + (1 << 20)) >> 21;
1738    s11 += carry[10];
1739    s10 -= carry[10] << 21;
1740    carry[12] = (s12 + (1 << 20)) >> 21;
1741    s13 += carry[12];
1742    s12 -= carry[12] << 21;
1743    carry[14] = (s14 + (1 << 20)) >> 21;
1744    s15 += carry[14];
1745    s14 -= carry[14] << 21;
1746    carry[16] = (s16 + (1 << 20)) >> 21;
1747    s17 += carry[16];
1748    s16 -= carry[16] << 21;
1749    carry[18] = (s18 + (1 << 20)) >> 21;
1750    s19 += carry[18];
1751    s18 -= carry[18] << 21;
1752    carry[20] = (s20 + (1 << 20)) >> 21;
1753    s21 += carry[20];
1754    s20 -= carry[20] << 21;
1755    carry[22] = (s22 + (1 << 20)) >> 21;
1756    s23 += carry[22];
1757    s22 -= carry[22] << 21;
1758
1759    carry[1] = (s1 + (1 << 20)) >> 21;
1760    s2 += carry[1];
1761    s1 -= carry[1] << 21;
1762    carry[3] = (s3 + (1 << 20)) >> 21;
1763    s4 += carry[3];
1764    s3 -= carry[3] << 21;
1765    carry[5] = (s5 + (1 << 20)) >> 21;
1766    s6 += carry[5];
1767    s5 -= carry[5] << 21;
1768    carry[7] = (s7 + (1 << 20)) >> 21;
1769    s8 += carry[7];
1770    s7 -= carry[7] << 21;
1771    carry[9] = (s9 + (1 << 20)) >> 21;
1772    s10 += carry[9];
1773    s9 -= carry[9] << 21;
1774    carry[11] = (s11 + (1 << 20)) >> 21;
1775    s12 += carry[11];
1776    s11 -= carry[11] << 21;
1777    carry[13] = (s13 + (1 << 20)) >> 21;
1778    s14 += carry[13];
1779    s13 -= carry[13] << 21;
1780    carry[15] = (s15 + (1 << 20)) >> 21;
1781    s16 += carry[15];
1782    s15 -= carry[15] << 21;
1783    carry[17] = (s17 + (1 << 20)) >> 21;
1784    s18 += carry[17];
1785    s17 -= carry[17] << 21;
1786    carry[19] = (s19 + (1 << 20)) >> 21;
1787    s20 += carry[19];
1788    s19 -= carry[19] << 21;
1789    carry[21] = (s21 + (1 << 20)) >> 21;
1790    s22 += carry[21];
1791    s21 -= carry[21] << 21;
1792
1793    s11 += s23 * 666643;
1794    s12 += s23 * 470296;
1795    s13 += s23 * 654183;
1796    s14 -= s23 * 997805;
1797    s15 += s23 * 136657;
1798    s16 -= s23 * 683901;
1799    // s23 = 0;
1800
1801    s10 += s22 * 666643;
1802    s11 += s22 * 470296;
1803    s12 += s22 * 654183;
1804    s13 -= s22 * 997805;
1805    s14 += s22 * 136657;
1806    s15 -= s22 * 683901;
1807    // s22 = 0;
1808
1809    s9 += s21 * 666643;
1810    s10 += s21 * 470296;
1811    s11 += s21 * 654183;
1812    s12 -= s21 * 997805;
1813    s13 += s21 * 136657;
1814    s14 -= s21 * 683901;
1815    // s21 = 0;
1816
1817    s8 += s20 * 666643;
1818    s9 += s20 * 470296;
1819    s10 += s20 * 654183;
1820    s11 -= s20 * 997805;
1821    s12 += s20 * 136657;
1822    s13 -= s20 * 683901;
1823    // s20 = 0;
1824
1825    s7 += s19 * 666643;
1826    s8 += s19 * 470296;
1827    s9 += s19 * 654183;
1828    s10 -= s19 * 997805;
1829    s11 += s19 * 136657;
1830    s12 -= s19 * 683901;
1831    // s19 = 0;
1832
1833    s6 += s18 * 666643;
1834    s7 += s18 * 470296;
1835    s8 += s18 * 654183;
1836    s9 -= s18 * 997805;
1837    s10 += s18 * 136657;
1838    s11 -= s18 * 683901;
1839    // s18 = 0;
1840
1841    carry[6] = (s6 + (1 << 20)) >> 21;
1842    s7 += carry[6];
1843    s6 -= carry[6] << 21;
1844    carry[8] = (s8 + (1 << 20)) >> 21;
1845    s9 += carry[8];
1846    s8 -= carry[8] << 21;
1847    carry[10] = (s10 + (1 << 20)) >> 21;
1848    s11 += carry[10];
1849    s10 -= carry[10] << 21;
1850    carry[12] = (s12 + (1 << 20)) >> 21;
1851    s13 += carry[12];
1852    s12 -= carry[12] << 21;
1853    carry[14] = (s14 + (1 << 20)) >> 21;
1854    s15 += carry[14];
1855    s14 -= carry[14] << 21;
1856    carry[16] = (s16 + (1 << 20)) >> 21;
1857    s17 += carry[16];
1858    s16 -= carry[16] << 21;
1859
1860    carry[7] = (s7 + (1 << 20)) >> 21;
1861    s8 += carry[7];
1862    s7 -= carry[7] << 21;
1863    carry[9] = (s9 + (1 << 20)) >> 21;
1864    s10 += carry[9];
1865    s9 -= carry[9] << 21;
1866    carry[11] = (s11 + (1 << 20)) >> 21;
1867    s12 += carry[11];
1868    s11 -= carry[11] << 21;
1869    carry[13] = (s13 + (1 << 20)) >> 21;
1870    s14 += carry[13];
1871    s13 -= carry[13] << 21;
1872    carry[15] = (s15 + (1 << 20)) >> 21;
1873    s16 += carry[15];
1874    s15 -= carry[15] << 21;
1875
1876    s5 += s17 * 666643;
1877    s6 += s17 * 470296;
1878    s7 += s17 * 654183;
1879    s8 -= s17 * 997805;
1880    s9 += s17 * 136657;
1881    s10 -= s17 * 683901;
1882    // s17 = 0;
1883
1884    s4 += s16 * 666643;
1885    s5 += s16 * 470296;
1886    s6 += s16 * 654183;
1887    s7 -= s16 * 997805;
1888    s8 += s16 * 136657;
1889    s9 -= s16 * 683901;
1890    // s16 = 0;
1891
1892    s3 += s15 * 666643;
1893    s4 += s15 * 470296;
1894    s5 += s15 * 654183;
1895    s6 -= s15 * 997805;
1896    s7 += s15 * 136657;
1897    s8 -= s15 * 683901;
1898    // s15 = 0;
1899
1900    s2 += s14 * 666643;
1901    s3 += s14 * 470296;
1902    s4 += s14 * 654183;
1903    s5 -= s14 * 997805;
1904    s6 += s14 * 136657;
1905    s7 -= s14 * 683901;
1906    // s14 = 0;
1907
1908    s1 += s13 * 666643;
1909    s2 += s13 * 470296;
1910    s3 += s13 * 654183;
1911    s4 -= s13 * 997805;
1912    s5 += s13 * 136657;
1913    s6 -= s13 * 683901;
1914    // s13 = 0;
1915
1916    s0 += s12 * 666643;
1917    s1 += s12 * 470296;
1918    s2 += s12 * 654183;
1919    s3 -= s12 * 997805;
1920    s4 += s12 * 136657;
1921    s5 -= s12 * 683901;
1922    s12 = 0;
1923
1924    carry[0] = (s0 + (1 << 20)) >> 21;
1925    s1 += carry[0];
1926    s0 -= carry[0] << 21;
1927    carry[2] = (s2 + (1 << 20)) >> 21;
1928    s3 += carry[2];
1929    s2 -= carry[2] << 21;
1930    carry[4] = (s4 + (1 << 20)) >> 21;
1931    s5 += carry[4];
1932    s4 -= carry[4] << 21;
1933    carry[6] = (s6 + (1 << 20)) >> 21;
1934    s7 += carry[6];
1935    s6 -= carry[6] << 21;
1936    carry[8] = (s8 + (1 << 20)) >> 21;
1937    s9 += carry[8];
1938    s8 -= carry[8] << 21;
1939    carry[10] = (s10 + (1 << 20)) >> 21;
1940    s11 += carry[10];
1941    s10 -= carry[10] << 21;
1942
1943    carry[1] = (s1 + (1 << 20)) >> 21;
1944    s2 += carry[1];
1945    s1 -= carry[1] << 21;
1946    carry[3] = (s3 + (1 << 20)) >> 21;
1947    s4 += carry[3];
1948    s3 -= carry[3] << 21;
1949    carry[5] = (s5 + (1 << 20)) >> 21;
1950    s6 += carry[5];
1951    s5 -= carry[5] << 21;
1952    carry[7] = (s7 + (1 << 20)) >> 21;
1953    s8 += carry[7];
1954    s7 -= carry[7] << 21;
1955    carry[9] = (s9 + (1 << 20)) >> 21;
1956    s10 += carry[9];
1957    s9 -= carry[9] << 21;
1958    carry[11] = (s11 + (1 << 20)) >> 21;
1959    s12 += carry[11];
1960    s11 -= carry[11] << 21;
1961
1962    s0 += s12 * 666643;
1963    s1 += s12 * 470296;
1964    s2 += s12 * 654183;
1965    s3 -= s12 * 997805;
1966    s4 += s12 * 136657;
1967    s5 -= s12 * 683901;
1968    s12 = 0;
1969
1970    carry[0] = s0 >> 21;
1971    s1 += carry[0];
1972    s0 -= carry[0] << 21;
1973    carry[1] = s1 >> 21;
1974    s2 += carry[1];
1975    s1 -= carry[1] << 21;
1976    carry[2] = s2 >> 21;
1977    s3 += carry[2];
1978    s2 -= carry[2] << 21;
1979    carry[3] = s3 >> 21;
1980    s4 += carry[3];
1981    s3 -= carry[3] << 21;
1982    carry[4] = s4 >> 21;
1983    s5 += carry[4];
1984    s4 -= carry[4] << 21;
1985    carry[5] = s5 >> 21;
1986    s6 += carry[5];
1987    s5 -= carry[5] << 21;
1988    carry[6] = s6 >> 21;
1989    s7 += carry[6];
1990    s6 -= carry[6] << 21;
1991    carry[7] = s7 >> 21;
1992    s8 += carry[7];
1993    s7 -= carry[7] << 21;
1994    carry[8] = s8 >> 21;
1995    s9 += carry[8];
1996    s8 -= carry[8] << 21;
1997    carry[9] = s9 >> 21;
1998    s10 += carry[9];
1999    s9 -= carry[9] << 21;
2000    carry[10] = s10 >> 21;
2001    s11 += carry[10];
2002    s10 -= carry[10] << 21;
2003    carry[11] = s11 >> 21;
2004    s12 += carry[11];
2005    s11 -= carry[11] << 21;
2006
2007    s0 += s12 * 666643;
2008    s1 += s12 * 470296;
2009    s2 += s12 * 654183;
2010    s3 -= s12 * 997805;
2011    s4 += s12 * 136657;
2012    s5 -= s12 * 683901;
2013    // s12 = 0;
2014
2015    carry[0] = s0 >> 21;
2016    s1 += carry[0];
2017    s0 -= carry[0] << 21;
2018    carry[1] = s1 >> 21;
2019    s2 += carry[1];
2020    s1 -= carry[1] << 21;
2021    carry[2] = s2 >> 21;
2022    s3 += carry[2];
2023    s2 -= carry[2] << 21;
2024    carry[3] = s3 >> 21;
2025    s4 += carry[3];
2026    s3 -= carry[3] << 21;
2027    carry[4] = s4 >> 21;
2028    s5 += carry[4];
2029    s4 -= carry[4] << 21;
2030    carry[5] = s5 >> 21;
2031    s6 += carry[5];
2032    s5 -= carry[5] << 21;
2033    carry[6] = s6 >> 21;
2034    s7 += carry[6];
2035    s6 -= carry[6] << 21;
2036    carry[7] = s7 >> 21;
2037    s8 += carry[7];
2038    s7 -= carry[7] << 21;
2039    carry[8] = s8 >> 21;
2040    s9 += carry[8];
2041    s8 -= carry[8] << 21;
2042    carry[9] = s9 >> 21;
2043    s10 += carry[9];
2044    s9 -= carry[9] << 21;
2045    carry[10] = s10 >> 21;
2046    s11 += carry[10];
2047    s10 -= carry[10] << 21;
2048
2049    //s[0] = (s0 >> 0) as u8;
2050    s[0] = s0 as u8;
2051    s[1] = (s0 >> 8) as u8;
2052    s[2] = ((s0 >> 16) | (s1 << 5)) as u8;
2053    s[3] = (s1 >> 3) as u8;
2054    s[4] = (s1 >> 11) as u8;
2055    s[5] = ((s1 >> 19) | (s2 << 2)) as u8;
2056    s[6] = (s2 >> 6) as u8;
2057    s[7] = ((s2 >> 14) | (s3 << 7)) as u8;
2058    s[8] = (s3 >> 1) as u8;
2059    s[9] = (s3 >> 9) as u8;
2060    s[10] = ((s3 >> 17) | (s4 << 4)) as u8;
2061    s[11] = (s4 >> 4) as u8;
2062    s[12] = (s4 >> 12) as u8;
2063    s[13] = ((s4 >> 20) | (s5 << 1)) as u8;
2064    s[14] = (s5 >> 7) as u8;
2065    s[15] = ((s5 >> 15) | (s6 << 6)) as u8;
2066    s[16] = (s6 >> 2) as u8;
2067    s[17] = (s6 >> 10) as u8;
2068    s[18] = ((s6 >> 18) | (s7 << 3)) as u8;
2069    s[19] = (s7 >> 5) as u8;
2070    s[20] = (s7 >> 13) as u8;
2071    //s[21] = (s8 >> 0) as u8;
2072    s[21] = s8 as u8;
2073    s[22] = (s8 >> 8) as u8;
2074    s[23] = ((s8 >> 16) | (s9 << 5)) as u8;
2075    s[24] = (s9 >> 3) as u8;
2076    s[25] = (s9 >> 11) as u8;
2077    s[26] = ((s9 >> 19) | (s10 << 2)) as u8;
2078    s[27] = (s10 >> 6) as u8;
2079    s[28] = ((s10 >> 14) | (s11 << 7)) as u8;
2080    s[29] = (s11 >> 1) as u8;
2081    s[30] = (s11 >> 9) as u8;
2082    s[31] = (s11 >> 17) as u8;
2083}
2084
2085pub(crate) fn new_scalar_int(i: BigInt) -> Scalar {
2086    let s = Scalar::default();
2087    s.set_int(&mut Int::new_int(i, FULL_ORDER.clone()))
2088}
kyber_rs/group/edwards25519/scalar.rs

kyber_rs/group/edwards25519/
scalar.rs
