curve25519之torsion points

1. Torsion points定义

在书《Elliptic Curves Number Theory And Cryptography 2n》中有定义： 满足上述定义，具有相同 n n n值的point，组成了n-torsion group。

2. curve25519的

对于Curve25519，其Montgomery form为： v 2 = u 3 + 486662 u 2 + u , q = 2 255 − 19 v^2=u^3+486662u^2+u, q=2^{255}-19 v2=u3+486662u2+u,q=2255−19 curve25519 co-factor为8 sage脚本验证：

sage: q=2^255-19
sage: E=EllipticCurve(GF(q),[0,486662,0,1,0])
sage: n=E.cardinality()
sage: n
57896044618658097711785492504343953926856930875039260848015607506283634007912
sage: factor(n)
2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989
sage: r=2^252+27742317777372353535851937790883648493
sage: n/r
8

对应的magma脚本为：

clear;
E := EllipticCurve([GF(2^255-19) | 0,486662,0,1,0]);
Order(E);
FactoredOrder(E);

57896044618658097711785492504343953926856930875039260848015607506283634007912
[ ,  ]

n = h r , h = 8 , r = 2 252 + 27742317777372353535851937790883648493 ( r 为 素 数 ) n=hr,h=8,r=2^{252}+27742317777372353535851937790883648493(r为素数) n=hr,h=8,r=2252+27742317777372353535851937790883648493(r为素数) 由此可知，curve25519具有两组torsion subgroup，分别为：h-torsion subgroup 和 r-torsion subgroup。

实际使用时，为了保证elliptic curve的安全性，应尽量使所使用的point在r-torsion subgroup，而不是在h-torsion subgroup。具体原因参加之前的博客ristretto对cofactor>1的椭圆曲线(如Curve25519等)的兼容（含Curve25519 cofactor的sage验证）。

curve25519-dalek中通过is_torsion_free和is_small_order来分别point区分是在r-torsion subgroup还是在h-torsion subgroup:

    /// Determine if this point is of small order.
    ///
    /// # Return
    ///
    /// * `true` if `self` is in the torsion subgroup \\( \mathcal E[8] \\);
    /// * `false` if `self` is not in the torsion subgroup \\( \mathcal E[8] \\).
    ///
    /// # Example
    ///
    /// ```
    /// use curve25519_dalek::constants;
    ///
    /// // Generator of the prime-order subgroup
    /// let P = constants::ED25519_BASEPOINT_POINT;
    /// // Generator of the torsion subgroup
    /// let Q = constants::EIGHT_TORSION[1];
    ///
    /// // P has large order
    /// assert_eq!(P.is_small_order(), false);
    ///
    /// // Q has small order
    /// assert_eq!(Q.is_small_order(), true);
    /// ```
    pub fn is_small_order(&self) -> bool {
        self.mul_by_cofactor().is_identity()
    }

    /// Determine if this point is “torsion-free”, i.e., is contained in
    /// the prime-order subgroup.
    ///
    /// # Return
    ///
    /// * `true` if `self` has zero torsion component and is in the
    /// prime-order subgroup;
    /// * `false` if `self` has a nonzero torsion component and is not
    /// in the prime-order subgroup.
    ///
    /// # Example
    ///
    /// ```
    /// use curve25519_dalek::constants;
    ///
    /// // Generator of the prime-order subgroup
    /// let P = constants::ED25519_BASEPOINT_POINT;
    /// // Generator of the torsion subgroup
    /// let Q = constants::EIGHT_TORSION[1];
    ///
    /// // P is torsion-free
    /// assert_eq!(P.is_torsion_free(), true);
    ///
    /// // P + Q is not torsion-free
    /// assert_eq!((P+Q).is_torsion_free(), false);
    /// ```
    pub fn is_torsion_free(&self) -> bool {
        (self * &constants::BASEPOINT_ORDER).is_identity()
    }
}

代码中有：

/// The 8-torsion subgroup \\(\mathcal E [8]\\).
///
/// In the case of Curve25519, it is cyclic; the \\(i\\)-th element of
/// the array is \\([i]P\\), where \\(P\\) is a point of order \\(8\\)
/// generating \\(\mathcal E[8]\\).
///
/// Thus \\(\mathcal E[4]\\) is the points indexed by `0,2,4,6`, and
/// \\(\mathcal E[2]\\) is the points indexed by `0,4`.
pub const EIGHT_TORSION: [EdwardsPoint; 8] = EIGHT_TORSION_INNER_DOC_HIDDEN;

/// Inner item used to hide limb constants from cargo doc output.
#[doc(hidden)]
pub const EIGHT_TORSION_INNER_DOC_HIDDEN: [EdwardsPoint; 8] = [
    EdwardsPoint {
        X: FieldElement51([0, 0, 0, 0, 0]),
        Y: FieldElement51([1, 0, 0, 0, 0]),
        Z: FieldElement51([1, 0, 0, 0, 0]),
        T: FieldElement51([0, 0, 0, 0, 0]),
    }
    ,
    EdwardsPoint {
        X: FieldElement51([358744748052810, 1691584618240980, 977650209285361, 1429865912637724, 560044844278676]),
        Y: FieldElement51([84926274344903, 473620666599931, 365590438845504, 1028470286882429, 2146499180330972]),
        Z: FieldElement51([1, 0, 0, 0, 0]),
        T: FieldElement51([1448326834587521, 1857896831960481, 1093722731865333, 1677408490711241, 1915505153018406]),
    }
    ,
    EdwardsPoint {
        X: FieldElement51([533094393274173, 2016890930128738, 18285341111199, 134597186663265, 1486323764102114]),
        Y: FieldElement51([0, 0, 0, 0, 0]),
        Z: FieldElement51([1, 0, 0, 0, 0]),
        T: FieldElement51([0, 0, 0, 0, 0]),
    }
    ,
    EdwardsPoint {
        X: FieldElement51([358744748052810, 1691584618240980, 977650209285361, 1429865912637724, 560044844278676]),
        Y: FieldElement51([2166873539340326, 1778179147085316, 1886209374839743, 1223329526802818, 105300633354275]),
        Z: FieldElement51([1, 0, 0, 0, 0]),
        T: FieldElement51([803472979097708, 393902981724766, 1158077081819914, 574391322974006, 336294660666841]),
    }
    ,
    EdwardsPoint {
        X: FieldElement51([0, 0, 0, 0, 0]),
        Y: FieldElement51([2251799813685228, 2251799813685247, 2251799813685247, 2251799813685247, 2251799813685247]),
        Z: FieldElement51([1, 0, 0, 0, 0]),
        T: FieldElement51([0, 0, 0, 0, 0]),
    }
    ,
    EdwardsPoint {
        X: FieldElement51([1893055065632419, 560215195444267, 1274149604399886, 821933901047523, 1691754969406571]),
        Y: FieldElement51([2166873539340326, 1778179147085316, 1886209374839743, 1223329526802818, 105300633354275]),
        Z: FieldElement51([1, 0, 0, 0, 0]),
        T: FieldElement51([1448326834587521, 1857896831960481, 1093722731865333, 1677408490711241, 1915505153018406]),
    }
    ,
    EdwardsPoint {
        X: FieldElement51([1718705420411056, 234908883556509, 2233514472574048, 2117202627021982, 765476049583133]),
        Y: FieldElement51([0, 0, 0, 0, 0]),
        Z: FieldElement51([1, 0, 0, 0, 0]),
        T: FieldElement51([0, 0, 0, 0, 0]),
    }
    ,
    EdwardsPoint {
        X: FieldElement51([1893055065632419, 560215195444267, 1274149604399886, 821933901047523, 1691754969406571]),
        Y: FieldElement51([84926274344903, 473620666599931, 365590438845504, 1028470286882429, 2146499180330972]),
        Z: FieldElement51([1, 0, 0, 0, 0]),
        T: FieldElement51([803472979097708, 393902981724766, 1158077081819914, 574391322974006, 336294660666841]),
    }
];

    #[test]
    fn test_eight_torsion() {
        for i in 0..8 {
            let Q = constants::EIGHT_TORSION[i].mul_by_pow_2(3);
            assert!(Q.is_valid());
            assert!(Q.is_identity());
        }
    }

    #[test]
    fn test_four_torsion() {
        for i in (0..8).filter(|i| i % 2 == 0) {
            let Q = constants::EIGHT_TORSION[i].mul_by_pow_2(2);
            assert!(Q.is_valid());
            assert!(Q.is_identity());
        }
    }

    #[test]
    fn test_two_torsion() {
        for i in (0..8).filter(|i| i % 4 == 0) {
            let Q = constants::EIGHT_TORSION[i].mul_by_pow_2(1);
            assert!(Q.is_valid());
            assert!(Q.is_identity());
        }
    }

参考资料： [1] 书《Elliptic Curves Number Theory And Cryptography 2n》 [2] Extended twisted Edwards curve坐标系 [3] ristretto对cofactor>1的椭圆曲线(如Curve25519等)的兼容（含Curve25519 cofactor的sage验证）