curve25519-dalek中field reduce原理分析

对于Curve25519，其Field域内的module Fp = 2255-19。 对于64位系统：

/// A `FieldElement51` represents an element of the field
/// \\( \mathbb Z / (2\^{255} - 19)\\).
///
/// In the 64-bit implementation, a `FieldElement` is represented in
/// radix \\(2\^{51}\\) as five `u64`s; the coefficients are allowed to
/// grow up to \\(2\^{54}\\) between reductions modulo \\(p\\).
///
/// # Note
///
/// The `curve25519_dalek::field` module provides a type alias
/// `curve25519_dalek::field::FieldElement` to either `FieldElement51`
/// or `FieldElement2625`.
///
/// The backend-specific type `FieldElement51` should not be used
/// outside of the `curve25519_dalek::field` module.
#[derive(Copy, Clone)]
pub struct FieldElement51(pub (crate) [u64; 5]);

src/backend/serial/u64/field.rs中的reduce函数，是将[u64;5] low-reduce成h, h ∈ [ 0 , 2 ∗ p ) , p = 2 255 − 19 h \in [0, 2*p), p=2^{255}-19 h∈[0,2∗p),p=2255−19。具体的原理如下：

1. field reduce原理分析

如要求某整数 u m o d ( 2 255 − 19 ) u\quad mod \quad (2^{255}-19) umod(2255−19)，可将u整数用多项式做如下表示： u = ∑ i u i 2 51 i x i ， 其 中 ， u i ∈ N u=\sum_{i}^{}u_i2^{51i}x^i，其中，u_i \in N u=∑i​ui​251ixi，其中，ui​∈N 设置x=1，通过对u多项式求值即可代表域Fp内的值。 如需求一个值： a ∈ [ 0 , 2 320 − 1 ] m o d ( 2 255 − 19 ) = ？ a\in [0, 2^{320}-1] \quad mod \quad(2^{255}-19)=？ a∈[0,2320−1]mod(2255−19)=？ 将 a ∈ [ 0 , 2 320 − 1 ] a\in [0, 2^{320}-1] a∈[0,2320−1]以上图表示，同时根据 a i a_i ai​分别取相应的 b i , c i b_i,c_i bi​,ci​: b i = a i & ( 2 < < 51 − 1 ) , c i = a i > > 51 ， 其 中 ， c i < = 2 13 b_i=a_i \& (2<<51 -1), c_i=a_i >> 51， 其中，c_i<= 2^{13} bi​=ai​&(251，其中，ci​> 51; let c4 = limbs[4] >> 51; limbs[0] &= LOW_51_BIT_MASK; limbs[1] &= LOW_51_BIT_MASK; limbs[2] &= LOW_51_BIT_MASK; limbs[3] &= LOW_51_BIT_MASK; limbs[4] &= LOW_51_BIT_MASK; limbs[0] += c4 * 19; limbs[1] += c0; limbs[2] += c1; limbs[3] += c2; limbs[4] += c3; FieldElement51(limbs) } 3. field reduce结果 ∈ [ 0 , 2 ∗ p ) , p = 2 255 − 19 \in [0, 2*p), p=2^{255}-19 ∈[0,2∗p),p=2255−19

src/backend/serial/u64/field.rs中的sub,neg等函数都只是调用了reduce函数，将最终的返回结果限定在了 ∈ [ 0 , 2 ∗ p ) , p = 2 255 − 19 \in [0, 2*p), p=2^{255}-19 ∈[0,2∗p),p=2255−19，只有调用to_bytes函数，才会将结果限定在 ∈ [ 0 , p ) , p = 2 255 − 19 \in [0, p), p=2^{255}-19 ∈[0,p),p=2255−19。

		// -1 + (2^255 - 19) = 2^255 - 20 = p-1
	    let a: [u8;32] = [0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f];
    
        let mut b = FieldElement::from_bytes(&a);
        println!("zyd-before negate b:{:?}", b);
        b.conditional_negate(Choice::from(1)); //求倒数，用的是reduce结果，对应结果为：-(p-1) mod p = p+1
        println!("zyd--b:{:?}", b);
        println!("zyd--b.to_bytes():{:?}", b.to_bytes()); //to_bytes()函数会对结果进行再次module，(p+1) mod p = 1.

对应输出为：

zyd-before negate b:FieldElement51([2251799813685228, 2251799813685247, 2251799813685247, 2251799813685247, 2251799813685247])
zyd--b:FieldElement51([2251799813685230, 2251799813685247, 2251799813685247, 2251799813685247, 2251799813685247])
zyd--b.to_bytes():[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

4. 一些常量值表示

1）-1对应modulo值为2255-19-1=57896044618658097711785492504343953926634992332820282019728792003956564819948，用FieldElement51表示为：

FieldElement51([2251799813685228, 2251799813685247, 2251799813685247, 2251799813685247, 2251799813685247])

sage: 2251799813685228+2251799813685247*(2^51)+2251799813685247*(2^102)+2251799813685247*(2^153)+2251799813685247*(2^204)==2^255-19-1
True

2）0值对应FieldElement51表示为：

FieldElement51([ 0, 0, 0, 0, 0 ])

3）1值对应FieldElement51表示为：

FieldElement51([ 1, 0, 0, 0, 0 ])

4）16*p值对应FieldElement51表示为：

FieldElement51([ 36028797018963664, 36028797018963952, 36028797018963952, 36028797018963952, 36028797018963952 ])

sage: p=2^255-19
sage: 36028797018963664+36028797018963952*(2^51)+36028797018963952*(2^102)+36028
....: 797018963952*(2^153)+36028797018963952*(2^204)==16*p
True
sage: