ristretto对cofactor>1的椭圆曲线(如Curve25519等)的兼容（含Curve25519 cofactor的sage验证）

1. 引言

基于椭圆曲线的加密系统，通常会由类似“G为具有prime-order q的group”的定义。

但是有些椭圆曲线具有的order n满足n=h*q，其中q为最大的素数，h称为cofactor。对于MNT4/6，BLS-BN128等曲线，其h为1。但是也存在cofactor不为1的曲线，如Hessian curves的cofactor通常为3，而Edwards curves的cofactor通常为4，Curve25519的cofactor为8.

Curve25519的cofactor为8的sage验证如下：

sage: p=2^255-19
sage: E=EllipticCurve(GF(p),[0, 486662, 0, 1, 0])
sage: E
Elliptic Curve defined by y^2 = x^3 + 486662*x^2 + x over Finite Field of size 57896044618658097711785492504343953926634992332820282019728792003956564819949
sage: n=E.cardinality()
sage: n
57896044618658097711785492504343953926856930875039260848015607506283634007912
sage: factor(n) //8*q，即cofactor为8。
2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989

Non-prime-order curves have significant advantages, such as complete addition laws and faster and simpler formulas. However, these advantages come at a cost: the order is not a prime q, but h·q for some small cofactor h.

当h>1时，曲线点由h-torsion和l-torsion点共同组成，其中h-torsion点将引起各种密码学缺陷。

“Let G be a group of prime order q.” This defines the requirements for the main group in many cryptographic systems, most often with the intention that G will be the group of points on an elliptic curve.

2. cofactor>1的缺陷

当曲线的cofactor>1时，存在以下缺陷：

1. Small-subgroup attacks：即所选择的点具有的order为h的倍数时，存在被攻击缺陷。
2. Non-injective behavior：当所选择的scalar相对于group order为素数时，与scalar的乘法通常为一对一满射函数。当cofactor>1时，random scalar无法保证。
3. Covert channels：非满射行为，导致存在数据泄露的可能。
4. Implementation-defined behavior：以Ed25519为例，对于h-torsion的非零值输入无明确的行为表现，如单个Ed25519签名验证和批量Ed25519签名验证可不同，或可依赖于不同的代码实现。
5. Nontrivial modifications：对于已有的已证明安全的基于prime-order group的密码学系统，当需要切换cofactor h>1的曲线时，需要对系统进行修改。通常修改比较简单，仅需要将现有的outputs乘以h即可。但是，密码学证明的过程很复杂，通常仅有专家才能明确指出具体哪些位置需要做调整。

3. ristretto的作用

ristretto用于做cofactor>1曲线的抽象层，尽可能减少底层代码的修改，ristretto对外表现为将non-prime-order的曲线抽象为a prime-order group.

目前支持cofactor为4或8的曲线。

实现的基本理论依据为Mike Hamburg的论文《Decaf: Eliminating cofactors through point compression》，该论文中时基于cofactor为4的情况设计的，restretto将其扩展为支持Curve25519（cofactor为8），支持用Ed25519签名的复杂零知识证明协议。

以Monero门罗币中实用的Ed25519签名为例，Ed25519签名具有可加工性的特点，将导致双花的可能（Ed25519的cofactor h=8，技术上来说，为8花）。 在Tor(洋葱)，Ed25519公钥的可加工性意味着每个V3 onion service可以有8个不同的地址，将导致匹配异常的可能。为了解决该异常，需要昂贵的运行时检查：a full scalar multiplcation, point compresssion以及equality check。而且该运行时检查需在多处被调用，以保证没有在onion service’s key中没有包含small torsion component.

详细的设计及设计细节可参看参考资料的[3]和[4]。

参考资料： [1] https://eprint.iacr.org/2015/673.pdf [2] https://tools.ietf.org/pdf/draft-hdevalence-cfrg-ristretto-01.pdf [3] https://ristretto.group/ristretto.html [4] https://github.com/dalek-cryptography/curve25519-dalek