Lib.rs

› 密码学
#elliptic-curve #ristretto #scalar-field #ecc #doppio-curve

zerocaf

Doppio-curve上的椭圆曲线操作纯Rust实现

作者：Carlos Pérez，Luke，以及4位贡献者

3个不稳定版本

0.2.0 2019年7月26日
0.1.1 2019年7月4日
0.1.0 2019年7月3日

#1611 in 密码学

MIT许可证

380KB
2.5K SLoC

Dusk-Zerocaf 构建状态 codecov GitHub已关闭问题 Crates.io

警告：工作中的仓库。

快速、高效且抗弹性的加密操作。

此仓库包含对Ristretto标量场的Doppio曲线的实现：由Dusk团队设计的纯Rust实现。

特别感谢Isis Agora Lovecruft和Henry de Valence对Curve25519-dalek库的实现，这对于获得一些基本算术运算和库的结构非常有用。

Ristretto曲线

Ristretto是一种构建具有不可变编码的素数阶椭圆曲线群的技术。

Ristretto协议作为Mike Hamburg的Decaf方法的扩展而出现，该方法用于消除共因子，适用于共因子为4的曲线，而Ristretto是为共因子为8或4的非素数阶曲线设计的。Ristretto是由dalek-cryprography团队设计的，特别是Henry de Valence和Isis Agora Lovecruft，我们对他们的工作和奉献表示深深的感激。

Ristretto标量场和Bulletproofs。

最初设计用于将非素数阶曲线抽象为素数阶标量域，这种Ristretto抽象对于Bulletproofs零知识证明来说效率过于低下，难以实现。因此，使用了Ristretto标量域来解决使用Ristretto曲线的陪因子等于8的所有负面影响。策略是使用一个Ristretto嵌入曲线（也称为Doppio Curve），因为zerocaf中的初始操作是在其中进行的。zerocaf为Dusk Network协议内部零知识证明的使用打开了新的机遇，同时也使得Bulletproof整合的环签名替代品成为可能，与最快的环签名实现相比，性能提升了几个数量级。

在这个库中，通过在标量域上定义曲线，并仅使用一个薄抽象层，使得构建具有所需属性的曲线成为可能，从而允许使用签名的系统安全地扩展到零知识协议。这些零知识协议的使用不需要额外的加密假设，并且在代码中几乎没有变化。Ristretto标量域对Bulletproof友好，这使得可以同时使用这两种加密协议，因为它们都与椭圆曲线运算的现代应用密切相关。

特别感谢@ebfull通过以下推文激发了这项工作

这是一个在ristretto255标量域上的“嵌入”曲线

-x² + y² = 1 - (86649/86650)x²y²

它是Ristretto兼容的，并且与以下双有理等价

y² = x³ + 346598x² + x（并且它的自旋是安全的）

还有其他建议吗？

— Sean Bowe (@ebfull) 2019年1月22日

详细信息

曲线参数

变量 值 解释
方程 Edwards -x²+y²=1-$\frac{86649}}{86650}$x²y² -
a -1 -
d $\frac{86649}}}$ -
B $\frac{8}}}$ Edwards X > 0时的基准点Y坐标

Montgomery y²=x³+346598*x²+x
u(P) 17
A 346598

Weierstrass y²=x³+ax+b
a 2412335192444087404657728854347664746952372119793302535333983646055108025796
b 1340186218024493002587627141304258192751317844329612519629993998710484804961
x 2412335192444087404657728854347664746952372119793302535333983646095151532546
y 6222320563903764848551041754877036140234555813488015858364752483591799173948
变量 值 解释
G 2²⁵² - 121160309657751286123858757838224683208 曲线阶数
p 2²⁵² + 27742317777372353535851937790883648493 域素数
r 2²⁴⁹ - 15145038707218910765482344729778085401 子群素数

编码/解码工具

为了处理曲线上的点或任何非平凡的运算，例如那些具有复杂符号的运算 - 已经创建了一系列工具和示例，以简化编码/解码过程。这些可以在：tools/src/main.rs找到

示例

num_from_bytes_le(&[76, 250, 187, 243, 105, 92, 117, 70, 234, 124, 126, 180, 87, 149, 62, 249, 16, 149, 138, 56, 26, 87, 14, 76, 251, 39, 168, 74, 176, 202, 26, 84]);
// Prints: 38041616210253564751207933125345413214423929536328854382158537130491690875468
    
let res = to_field_elem_51(&"1201935917638644956968126114584555454358623906841733991436515590915937358637");
println!("{:?}", res);
// Gives us: [939392471225133, 1174884015108736, 2226020409917912, 1948943783348399, 46747909865470]

hex_bytes_le("120193591763864495696812611458455545435862390684173399143651559091593735863735685683568356835683");
// Prints: Encoding result -> [63, 41, b7, c, b, 79, 94, 7b, 21, d2, fe, 7b, c8, 89, c9, 7f, 76, c8, 9b, a3, 58, 18, 39, a, f2, d2, 7c, 17, ed, 7f, 6, c4, 9d, 44, f3, 7c, 85, c2, 67, e]
// Put the 0x by yourseleves and if there's any value alone like `c` padd it with a 0 on the left like: `0x0c`

from_radix_to_radix_10("1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab", 16u32);
// Prints: 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787

在执行大数值运算时，例如：2²⁵² - 121160309657751286123858757838224683208，建议通过SageMath进行计算，因为用户界面符合这类函数。从SageMath，可以将它们转换为一致格式并轻松编译成Rust。

路线图

注意：重构关系以缩进来表示

  • 构建标量算术和标量结构定义。
    • 为 FieldElement 找到合适的基数值。
    • 添加所需的计算常数。
      • 实现加法。
      • 实现减法。
      • 实现字节编码/解码。
      • 实现 uint 原生类型的 From。
      • 实现 Ord、PartialOrd、Eq & PartialEq。
      • 在 u64 后端上实现乘法，使用 u128。
      • 实现平方。
      • 实现偶数的 Half。
      • 实现模否定。
      • 实现 Montgomery_reduction。
      • 定义 Montgomery_reduction 算法。
  • 创建 FieldElement 结构并实现我们在 u64 后端上需要的操作。
    • 为 FieldElement 找到合适的基数值。
    • 添加基本和所需的常数。
    • 实现 Reduce 函数，使 FieldElements 适合 5 个 u64 位肢体。
      • 实现加法。
      • 实现减法。
      • 实现字节编码/解码。
      • 实现 uint 原生类型的 From。
      • 实现 Ord、PartialOrd、Eq & PartialEq。
      • 在 u64 后端上实现乘法，使用 u128。
      • 实现平方。
      • 实现偶数的 Half。
      • 实现模否定。
      • 实现 Montgomery_reduction。
      • 定义 Montgomery_reduction 算法。
      • 实现模逆。
      • 研究加法链逆方法。
    • 为每个函数添加适当的测试。
  • 实现 Edwards 点。
    • 实现扭曲 Edwards 扩展坐标。
      • 实现点加法。
      • 实现点减法。
      • 实现点双倍。
      • 实现标量乘法。
      • 实现 from_bytes 转换。
      • 实现 to_byte 转换。
      • 实现压缩 Edwards 点 Y 坐标。
    • 实现扭曲 Edwards 投影坐标。
      • 实现点加法。
      • 实现点减法。
      • 实现点双倍。
      • 实现标量乘法。
      • 实现 from_bytes 转换。
      • 实现 to_byte 转换。
      • 实现压缩 Edwards 点 Y 坐标。
    • 使用包装函数（研究）将 Edwards 点表示为 Ristretto 点。
    • Cargo doc 测试和改进。
    • 决定各种 Edwards 坐标类型（压缩、标准、扩展、投影）的最佳用途。
    • 基准测试不同的实现和算法。
    • 研究关于 Niels 和 ProjectiveNiels 坐标的使用。
    • 实现 Ristretto 映射。
    • 构建并测试扭结点。
    • 测试 Edwards 点的所有点操作。
  • 实现 Montgomery 和 Edwards 操作 & 函数。

建议在 SageMath 中进行大数操作，从中可以将其转换为与 rust 连续的格式，并在每次计算后轻松编译。

依赖关系

~3MB
~60K SLoC