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

1. mul 模乘運算

求a*b mod l的算法依據(jù)為：
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位來實現(xiàn)。
注意Scalar52為[u64;5]數(shù)組，且采用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位。}//當(dāng)a>=b時，最高位的(borrow >> 63) 為0；否則(borrow >> 63) 為1// conditionally add l if the difference is negativelet underflow_mask = ((borrow >> 63) ^ 1).wrapping_sub(1); //當(dāng)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); // 當(dāng)a>=b時， a-b mod l = difference；否則 a-b mod l = difference+Ldifference[i] = carry & mask; //每個元素只存儲52位，超過的通過carry>>52表示進(jìn)位。}difference}

在上述代碼中增加調(diào)試信息，可由輸出結(jié)果進(jìn)行反向驗證。

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$，可能大于。如下例，當(dāng)用$0?b,b>l時，0?(0?b)=b$。

3. add 模加運算

求0=<a,b<l, a+b mod l的思路為，直接求取sum=a+b，然后再調(diào)用上面的sub函數(shù)來求取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模除運算可轉(zhuǎn)換位模倒數(shù)后的模乘運算（見 1. mul 模乘運算）。
模倒數(shù)的計算方法可參見curve25519-dalek中的Montgomery inversion算法。

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

總結(jié)

以上是生活随笔為你收集整理的curve25519-dalek中的Scalar模运算mul/sub/add/div的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。