curve25519-dalek中的Scalar模运算mul/sub/add/div

https://github.com/dalek-cryptography/curve25519-dalek/blob/master/src/backend/serial/u64/scalar.rs 中

1. mul 模乘运算

求a*b mod l的算法依据为： 1）计算m=ab； 2）计算m的montgomery_reduce值：t=mR-1 mod l； 3）计算n=tR2； 4）计算n的montgomery_reduce值：r=nR-1 mod l = (mR-1)R2R-1 mod l = ab mod l。 由此最终获得的r值即为a*b mod l。

    /// Compute `a * b` (mod l)
    #[inline(never)]
    pub fn mul(a: &Scalar52, b: &Scalar52) -> Scalar52 {
        let ab = Scalar52::montgomery_reduce(&Scalar52::mul_internal(a, b));
        Scalar52::montgomery_reduce(&Scalar52::mul_internal(&ab, &constants::RR))
    }

2. sub 模减运算

求0= Scalar52 { let mut difference = Scalar52::zero(); let mask = (1u64 > 63)); // (a[i]-b[i]+borrow/2^63) mod 2^64 difference[i] = borrow & mask; //直接取52位。 } //当a>=b时，最高位的(borrow >> 63) 为0；否则(borrow >> 63) 为1 // conditionally add l if the difference is negative let underflow_mask = ((borrow >> 63) ^ 1).wrapping_sub(1); //当a>=b时，underflow_mask为0；否则为2^64-1 let mut carry: u64 = 0; for i in 0..5 { carry = (carry >> 52) + difference[i] + (constants::L[i] & underflow_mask); // 当a>=b时， a-b mod l = difference；否则 a-b mod l = difference+L difference[i] = carry & mask; //每个元素只存储52位，超过的通过carry>>52表示进位。 } difference }

在上述代码中增加调试信息，可由输出结果进行反向验证。

zyd a:Scalar52: [4503599627370495, 4503599627370495, 4503599627370495, 4503599627370495, 35184372088831], b:Scalar52: [3224898173688058, 3370928136179116, 1182880079308587, 1688835920473363, 14937922189349], mask:4503599627370495
zyd i:0, borrow:1278701453682437, borrow>>63:0, difference:Scalar52: [1278701453682437, 0, 0, 0, 0]
zyd i:1, borrow:1132671491191379, borrow>>63:0, difference:Scalar52: [1278701453682437, 1132671491191379, 0, 0, 0]
zyd i:2, borrow:3320719548061908, borrow>>63:0, difference:Scalar52: [1278701453682437, 1132671491191379, 3320719548061908, 0, 0]
zyd i:3, borrow:2814763706897132, borrow>>63:0, difference:Scalar52: [1278701453682437, 1132671491191379, 3320719548061908, 2814763706897132, 0]
zyd i:4, borrow:20246449899482, borrow>>63:0, difference:Scalar52: [1278701453682437, 1132671491191379, 3320719548061908, 2814763706897132, 20246449899482]
zyd underflow_mask:0
zyd i:0, carry:1278701453682437, carry>>52:0, difference:Scalar52: [1278701453682437, 1132671491191379, 3320719548061908, 2814763706897132, 20246449899482]
zyd i:1, carry:1132671491191379, carry>>52:0, difference:Scalar52: [1278701453682437, 1132671491191379, 3320719548061908, 2814763706897132, 20246449899482]
zyd i:2, carry:3320719548061908, carry>>52:0, difference:Scalar52: [1278701453682437, 1132671491191379, 3320719548061908, 2814763706897132, 20246449899482]
zyd i:3, carry:2814763706897132, carry>>52:0, difference:Scalar52: [1278701453682437, 1132671491191379, 3320719548061908, 2814763706897132, 20246449899482]
zyd i:4, carry:20246449899482, carry>>52:0, difference:Scalar52: [1278701453682437, 1132671491191379, 3320719548061908, 2814763706897132, 20246449899482]
zyd a:Scalar52: [3224898173688058, 3370928136179116, 1182880079308587, 1688835920473363, 14937922189349], b:Scalar52: [4503599627370495, 4503599627370495, 4503599627370495, 4503599627370495, 35184372088831], mask:4503599627370495
zyd i:0, borrow:18445465372255869179, borrow>>63:1, difference:Scalar52: [3224898173688059, 0, 0, 0, 0]
zyd i:1, borrow:18445611402218360236, borrow>>63:1, difference:Scalar52: [3224898173688059, 3370928136179116, 0, 0, 0]
zyd i:2, borrow:18443423354161489707, borrow>>63:1, difference:Scalar52: [3224898173688059, 3370928136179116, 1182880079308587, 0, 0]
zyd i:3, borrow:18443929310002654483, borrow>>63:1, difference:Scalar52: [3224898173688059, 3370928136179116, 1182880079308587, 1688835920473363, 0]
zyd i:4, borrow:18446723827259652133, borrow>>63:1, difference:Scalar52: [3224898173688059, 3370928136179116, 1182880079308587, 1688835920473363, 4483353177471013]
zyd underflow_mask:18446744073709551615
zyd i:0, carry:3896813007023336, carry>>52:0, difference:Scalar52: [3896813007023336, 3370928136179116, 1182880079308587, 1688835920473363, 4483353177471013]
zyd i:1, carry:7287592461284141, carry>>52:1, difference:Scalar52: [3896813007023336, 2783992833913645, 1182880079308587, 1688835920473363, 4483353177471013]
zyd i:2, carry:1182880080676389, carry>>52:0, difference:Scalar52: [3896813007023336, 2783992833913645, 1182880080676389, 1688835920473363, 4483353177471013]
zyd i:3, carry:1688835920473363, carry>>52:0, difference:Scalar52: [3896813007023336, 2783992833913645, 1182880080676389, 1688835920473363, 4483353177471013]
zyd i:4, carry:4500945363515429, carry>>52:0, difference:Scalar52: [3896813007023336, 2783992833913645, 1182880080676389, 1688835920473363, 4500945363515429]
res: Scalar52: [1278701453682437, 1132671491191379, 3320719548061908, 2814763706897132, 20246449899482], zyd:Scalar52: [3896813007023336, 2783992833913645, 1182880080676389, 1688835920473363, 4500945363515429]

注意，sub返回的值不一定小于 l l l，可能大于。如下例，当用 0 − b , b > l 时 ， 0 − ( 0 − b ) = b 0-b, b>l时，0-(0-b)=b 0−b,b>l时，0−(0−b)=b。

3. add 模加运算

求0= 52); sum[i] = carry & mask; } // subtract l if the sum is >= l Scalar52::sub(&sum, &constants::L) } 4. div 模除运算

div模除运算可转换位模倒数后的模乘运算（见 1. mul 模乘运算）。 模倒数的计算方法可参见curve25519-dalek中的Montgomery inversion算法。

参考资料： [1] https://blog.csdn.net/mutourend/article/details/95613967 [2] https://www.youtube.com/watch?v=2UmQDKcelBQ