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=tR²；
4）计算n的montgomery_reduce值：r=nR^-1 mod l = (mR^-1)R²R^-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=<a,b<l, a-b mod l，实际的逻辑为：
1）若a>b，则a-b mod l = a-b;
2）若a<b, 则a-b mod l = a-b+l.

代码中的模减运算很巧妙，不需要做a>b的判断，直接通过borrow和carry位来实现。
注意Scalar52为[u64;5]数组，且采用little-endian方式排布，每个元素仅用其中的52个bit。

/// Compute `a - b` (mod l)pub fn sub(a: &Scalar52, b: &Scalar52) -> Scalar52 {let mut difference = Scalar52::zero();let mask = (1u64 << 52) - 1;// a - blet mut borrow: u64 = 0;for i in 0..5 {borrow = a[i].wrapping_sub(b[i] + (borrow >> 63)); // (a[i]-b[i]+borrow/2^63) mod 2^64difference[i] = borrow & mask; //直接取52位。}//当a>=b时，最高位的(borrow >> 63) 为0；否则(borrow >> 63) 为1// conditionally add l if the difference is negativelet underflow_mask = ((borrow >> 63) ^ 1).wrapping_sub(1); //当a>=b时，underflow_mask为0；否则为2^64-1let 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+Ldifference[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$，可能大于。如下例，当用$0-b,b>l时，0-(0-b)=b$。

3. add 模加运算

求0=<a,b<l, a+b mod l的思路为，直接求取sum=a+b，然后再调用上面的sub函数来求取sum mod l.

/// Compute `a + b` (mod l)pub fn add(a: &Scalar52, b: &Scalar52) -> Scalar52 {let mut sum = Scalar52::zero();let mask = (1u64 << 52) - 1;// a + blet mut carry: u64 = 0;for i in 0..5 {carry = a[i] + b[i] + (carry >> 52);sum[i] = carry & mask;}// subtract l if the sum is >= lScalar52::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

总结

以上是生活随笔为你收集整理的curve25519-dalek中的Scalar模运算mul/sub/add/div的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。