#curve25519 #ristretto #curve-point #ristretto255 #crypto

no-std curve25519-dalek-ml

Rust语言实现的ristretto255和Curve25519群运算

6个稳定版本

4.2.2 2024年7月24日
4.2.1 2024年2月17日
4.1.1 2023年11月1日
4.0.0 2022年8月8日

#40 in 密码学

Download history 450/week @ 2024-05-04 397/week @ 2024-05-11 323/week @ 2024-05-18 239/week @ 2024-05-25 220/week @ 2024-06-01 323/week @ 2024-06-08 661/week @ 2024-06-15 312/week @ 2024-06-22 300/week @ 2024-06-29 347/week @ 2024-07-06 273/week @ 2024-07-13 264/week @ 2024-07-20 307/week @ 2024-07-27 239/week @ 2024-08-03 179/week @ 2024-08-10 251/week @ 2024-08-17

1,023 每月下载量
用于hd-keys-curves-wasm

BSD-3-Clause

1MB
26K SLoC

curve25519-dalek CI

dalek-cryptography logo: a dalek with edwards curves as sparkles coming out of its radar-schnozzley blaster thingies

Rust语言实现的Ristretto和Curve25519群运算。

curve25519-dalek 是一个库,提供对 Curve25519 的 Edwards 和 Montgomery 形式的群运算,以及对素数阶 Ristretto 群的群运算。

curve25519-dalek 并不旨在提供任何特定加密协议的实现。相反,这些协议(如 x25519-daleked25519-dalek)的实现应将 curve25519-dalek 作为库使用。

curve25519-dalek 旨在提供一个干净、安全的 中级别 API,用于实现各种基于 ECC 的加密协议,例如密钥协商、签名、匿名凭证、rangeproofs 和零知识证明系统。

特别是,curve25519-dalek 实现了 Ristretto,它从一个非素数阶的 Edwards 曲线构造了一个素数阶群。这提供了 Edwards 曲线算术的速度和安全性优势,而没有与系数相关的抽象不匹配的缺陷。

注意curve25519-dalek 相比,本crate的主要区别是增加了对 Edwards 曲线的 hash_to_curve。

使用

稳定

要导入 curve25519-dalek,请在项目 Cargo.toml 的依赖关系部分添加以下内容

curve25519-dalek = "4"

如果您选择使用 SemVer-exempted features,可以使用范围来限定测试兼容的版本范围,例如。

curve25519-dalek = ">= 4.0, < 4.2"

特性标志

特性 默认? 描述
alloc 启用Edwards和Ristretto多标量乘法、批量标量求逆和批量Ristretto双倍压缩。同时启用zeroize
zeroize 为所有标量和曲线点类型启用Zeroize
预计算表 包含预计算的基点乘法表。这可以将EdwardsPoint::mul_baseRistrettoPoint::mul_base的速度提高约4倍,但会增加约30KB的代码大小。
rand_core 启用Scalar::randomRistrettoPoint::random。这是一个可选依赖项,其版本不受SemVer约束。有关更多详细信息,请参阅下文
digest 启用RistrettoPoint::{from_hash, hash_from_bytes}Scalar::{from_hash, hash_from_bytes}。这是一个可选依赖项,其版本不受SemVer约束。有关更多详细信息,请参阅下文
serde 启用所有点和标量类型的serde序列化/反序列化。
遗留兼容性 启用Scalar::from_bits,允许用户构建未简化的标量,其算术是错误的。除非您知道自己在做什么,否则请勿使用此功能。
group 启用外部groupffcrate特性

当使用curve25519-dalek作为依赖项时禁用默认功能,请将default-features = false添加到您的Cargo.toml中的依赖项。要在运行cargo时禁用它,请添加--no-default-featuresCLI标志。

主要版本API更改

每个主要版本发布的破坏性更改可以在CHANGELOG.md中的“破坏性更改”子标题下找到。以下是一些高级破坏性更改

4.0.0中的破坏性更改

  • 将MSRV从1.41更新到1.60
  • 提供SemVer策略
  • digestrand_core作为可选功能
  • 删除stdnightly功能
  • 替换后端选择 - 请参阅CHANGELOG.md后端
  • 将方法Scalar::{zero, one}替换为常量Scalar::{ZERO, ONE}
  • Scalar::from_canonical_bytes现在返回CtOption
  • Scalar::is_canonical现在返回Choice
  • 删除 Scalar::from_bytes_clampedScalar::reduce
  • Scalar::from_bits 弃用,并在 legacy_compatibility 后启用功能门
  • 弃用 EdwardsPoint::hash_from_bytes 并将其重命名为 EdwardsPoint::nonspec_map_to_curve
  • 在使用 EdwardsBasepointTableRistrettoBasepointTable 时,必须包含一个新的特性,use curve25519_dalek::traits::BasepointTable

此版本还对依赖项进行了大量更新和放宽,以解决上游构建问题。

后端

曲线算术由以下后端之一实现和使用

后端 选择 实现 位 / 字大小
serial 自动 一个优化、非并行实现 3264
fiat 手动 来自 fiat-crypto 的形式化验证域算术 3264
simd 自动 Intel AVX2 / AVX512 IFMA 加速后端 64

在运行时,curve25519-dalek 从其编译支持的集合中选择一个算术后端。对于 Intel x86-64 目标,除非指定其他,否则它将使用 simd 支持构建自身,如果检测到适当的 CPU 功能,则在运行时默认使用 serial。有关更多详细信息,请参阅 SIMD 后端

将来,simd 后端可能扩展以覆盖更多指令集。此更改将不会破坏性,因为这被视为实现细节。

手动后端覆盖

您可以强制包使用特定的后端支持编译,例如,对于 x86-64 目标使用 serial 以节省代码大小,或使用 fiat 以强制运行时使用已验证的代码。为此,设置环境变量

RUSTFLAGS='--cfg curve25519_dalek_backend="BACKEND"'

相当于,您可以写入 ~/.cargo/config

[build]
rustflags = ['--cfg=curve25519_dalek_backend="BACKEND"']

更多信息 在此处

注意:贡献者:目标后端并非完全相互独立。SIMD 后端直接依赖于串行后端的部分才能运行。

位 / 字大小

curve25519-dalek 将根据构建目标自动选择 fiatserial 后端的大小。例如,当选择 serialfiat 后端时,构建 64 位机器将自动选择默认的 64 位字大小。

在某些目标中,可能需要覆盖字大小以获得更好的性能。可以通过设置环境变量覆盖 serialfiat 的后端字大小

RUSTFLAGS='--cfg curve25519_dalek_bits="SIZE"'

SIZE3264。如上所述,这也可以放在 ~/.cargo/config 中。

注意:SIMD后端需要64位字长。尝试设置bits=32和backend=simd将导致编译错误。

交叉编译

由于后端选择是通过目标来完成的,交叉编译将自动选择正确的字长。例如,如果x86-64 Linux机器运行以下命令,curve25519-dalek将使用32位的serial后端进行编译。

$ sudo apt install gcc-multilib # (or whatever package manager you use)
$ rustup target add i686-unknown-linux-gnu
$ cargo build --target i686-unknown-linux-gnu

SIMD后端

具体的SIMD后端(AVX512 / AVX2 / serial默认)将根据当前可用的CPU功能和是否使用Rust nightly进行编译自动选择。具体条件如下所述。

对于给定的CPU功能,您还可以指定适当的-C target_feature来构建假设所需的SIMD指令始终可用的二进制文件。如果没有充分的理由,请不要这样做。

后端 RUSTFLAGS 需要nightly吗?
avx2 -C target_feature=+avx2 no
avx512 -C target_feature=+avx512ifma,+avx512vl yes

如果使用非nightly编译器编译,curve25519-dalek将不包括AVX512代码,因此在运行时永远不会选择它。

文档

semver-stable、面向公众的curve25519-dalek API在此进行了文档说明。

本地构建文档

curve25519-dalek文档需要自定义HTML头,以包含用于数学支持的KaTeX。遗憾的是,当前cargo doc不支持此功能,但可以使用以下方法构建文档:

make doc

用于常规文档的,以及

make doc-internal

用于包含私有项目的文档。

维护策略

此库的所有默认功能都受语义版本控制(SemVer)的保护。以下列出了MSRV和公共API的SemVer例外情况。

最低支持的Rust版本

发布 MSRV
4.x 1.60.0
3.x 1.41.0

从4.x开始,MSRV更改将伴随着次要版本的提升。

公共API SemVer例外

影响公共API的SemVer豁免组件的破坏性更改将伴随某些版本提升。以下列出了具体的策略

发布 公共API组件 策略
4.x 依赖项groupdigestrand_core 次要SemVer提升

安全性

curve25519-dalek类型设计为使非法状态不可表示。例如,任何EdwardsPoint实例都将保证在Edwards曲线上持有点,任何RistrettoPoint实例都将保证在Ristretto群中持有有效点。

所有操作都使用恒等时逻辑(没有依赖于秘密的分支,没有依赖于秘密的内存访问)实现,除非明确标记为可变时序代码。我们相信,我们的恒等时逻辑至少在x86_64目标上被降低到恒等时汇编。

作为对未来编译器优化可能的额外防护,subtle crate在每个条件移动或赋值之前放置了一个优化屏障。更多详细信息可以在subtle crate的文档中找到。

某些功能(例如,多标量乘法或批量求逆)需要堆分配临时缓冲区。在释放之前,所有可能包含秘密数据的堆分配缓冲区都将显式地置零。

然而,我们并没有尝试将栈数据清零,原因有两个。首先,这样做是无法正确完成的:我们没有控制栈分配,因此无法知道要擦除多少数据。其次,因为 curve25519-dalek 提供了一个中级API,因此开始清零栈数据可能不是在 curve25519-dalek 函数的入口点,而是在其他crate中函数的入口点。

实现是内存安全的,并且不包含任何显著的 unsafe 代码。SIMD后端在内部使用 unsafe 来调用SIMD内嵌函数。这些函数被标记为 unsafe 只是因为在不适当的CPU上调用它们会导致 SIGILL,但整个后端仅在检测到适当的CPU特性时或在程序整体编译时使用适当的 target_feature 才会被调用。

性能

基准测试使用 criterion.rs 运行。

cargo bench --features "rand_core"
export RUSTFLAGS='-C target_cpu=native'
cargo +nightly bench --features "rand_core"

性能是正确性、安全和清晰之后的次要目标,但我们的目标是与其他实现具有竞争力。

FFI

遗憾的是,我们目前没有计划直接将FFI添加到 curve25519-dalek。原因是,我们使用Rust功能来提供一个API,该API维护安全不变性,这不可能在FFI边界上维护。例如,如上文中 安全 部分所述,无法构造无效点,如果我们在FFI上公开点操作,则情况并非如此。

然而,curve25519-dalek 被设计为一个 中级 API,旨在实现其他,更高级的原始函数。而不是在中级提供FFI,我们的建议是在Rust中实现高级原始函数(签名、PAKE、ZKP等),使用 curve25519-dalek 作为依赖项,并让该crate为该原始函数提供最小、面向字节的FFI。

贡献

请参阅 CONTRIBUTING.md

关于

剧透警告: 第十二任博士与 Daleks 的第一次遭遇发生在他的第二集完整剧集 "Into the Dalek"。联合银河抵抗军的困顿飞船发现了一个损坏的 Dalek,它变成了 "善良" 的,渴望杀死所有其他 Daleks。博士、克拉拉和一支士兵队伍被微型化并进入 Dalek,博士将其命名为 Rusty。他们修复了损坏,但意外地将其恢复到原始状态,导致它开始狂暴并警告 Dalek 舰队叛逆飞船的位置。然而,博士通过将自己的意识与 Dalek 相连接,设法将 Rusty 恢复到之前的状态:Rusty 分享着博士对宇宙之美的看法,但也与他深恶痛绝的 Daleks 相同。Rusty 摧毁其他 Daleks 并离开飞船,决心追踪并结束 Dalek 族的命运。

curve25519-dalek 由 Isis Agora Lovecruft 和 Henry de Valence 撰写。

此库的部分内容最初是 Adam Langley 的 Golang ed25519 库的移植,该库反过来又是参考 ref10 实现的移植。此后,包括32位字段算术在内的大部分代码都已重写。

快速 u32u64 矢量算术是由 Andrew Moon 实现的,而标量求逆的加法链是由 Brian Smith 提供的。优化的批量求逆是由 Sean Bowe 和 Daira Hopwood 贡献的。

no_stdzeroize 支持是由 Tony Arcieri 贡献的。

经过形式验证的 fiat_backend 集成了由 Fiat Crypto 项目 生成的 Rust 代码,并由 François Garillot 贡献。

还要感谢 Ashley Hauck、Lucas Salibian、Manish Goregaokar、Jack Grigg、Pratyush Mishra、Michael Rosenberg、@pinkforest 以及众多其他人为他们的贡献。

依赖项

~0.2–1.7MB
~35K SLoC