Ronkathon：从第一性原理学习密码学
原文：https://pluto.xyz/blog/ronkathon-learn-cryptography-from-first-principles
作者：Waylon，Colin
译者：Kurt Pan
Ronkathon 是受 Plonkathon 启发的一系列密码学原语的 Rust 实现。该技术库旨在展示应用密码学的理论性质以及是用适合密码学的编程语言写成的具体应用。
https://github.com/pluto/ronkathon
Ronkathon 是根据第一性原理构建的，因此不存在关于外部库的假设知识或冗杂的依赖关系（ rand 和 itertools 除外）。这里的大部分代码都没有进行优化以试图达到数学透明性和简易性。
该工作作为密码学原语的玩具实现，用以帮助培养对实现细节的理解——因此，大部分代码无优化，不安全，也不适用商业用途。我们首先实现构造 KZG 证明的原语，然后继续构造其他原语。下面列出了该技术库的概要。
域及其扩张
多项式
椭圆曲线
椭圆曲线配对
KZG
非对称原语
哈希
结论
域及其扩张
https://github.com/pluto/ronkathon/blob/main/src/field/README.md 有限域是密码学中广泛使用的核心原语。该库有一个有限域模块。我们使用它来定义素数阶的域 ，将其用作 KZG 构造中的基域。这个素数来自Plonk by hand，具有一些很好的性质，例如：
https://research.metastate.dev/plonk-by-hand-part-1/ 第一个曲线群是在这个基域上定义的。该库还支持域扩张 。我们使用扩张次数 （我们将在稍后的椭圆曲线部分解释这个的基本原理）来构造 KZG。通常将域扩张上的曲线群表示为 。为了构建一般的扩张，我们需要一个多项式模块。
多项式
https://github.com/pluto/ronkathon/blob/main/src/polynomial/mod.rs
多项式是一种普遍存在的结构，有许多应用。我们将多项式模块用于扩张域、Reed-Solomon 编码和多项式承诺方案。多项式承诺方案是另一个核心密码学原语，允许证明者以某种方式承诺多项式，使其在任何点的求值都可以被其他人高效地验证，从而确保多项式的完整性。这稍后会在 KZG 多项式承诺方案中使用。
椭圆曲线
https://github.com/pluto/ronkathon/blob/main/src/curve/README.md
椭圆曲线是一个美丽的原语，用于非对称密码学以及零知识证明。在非对称密码学中，椭圆曲线以相对较小的密钥大小提供了高等级的安全性，使其比 RSA 等传统方法更高效、更快速。我们还在基于配对的密码学中使用椭圆曲线和 KZG 证明。我们有一个手工制作的曲线库，支持有限域上椭圆曲线点的点加。我们在 KZG 承诺中使用 形式的配对友好曲线。我们称最大的椭圆曲线群中的点的数量为椭圆曲线的标量域。
对于我们的 KZG 构造来说，基域是 ，曲线群的标量域的阶是 17 。
椭圆曲线配对
配对被正式描述为一个接受两个参数的双线性映射：
第一条曲线循环子群中的一个点 第二个循环子群的一个点
并将它们映射到第三个群，使得配对为：
曲线循环子群 和 都是相同阶的（即, 它们具有相同的标量域, 从而是同构的）。配对是这些不同子群之间的映射。如果这里一下子不是很清楚，那也没关系--给它一些时间。我们也会讨论更多细节。
现在我们对配对的抽象结构有了一个粗略的了解，让我们来看看如何构造配对友好的曲线群。
为了构建配对友好曲线，我们首先要找到第一个曲线群的标量域。曲线的标量域是曲线的阶，或者说是由生成元生成的循环群中的点的数量。对于我们的曲线群 , 标量域是 以及我们选择的生成元是 。现在我们有了曲线的标量域，就可以找到曲线的嵌入度。
嵌入度定义为使曲线阶（标量域的大小） 整除 的最小数字 。
我们可以看到，对于 不会整除 。但是对于 确实整除 , 所以我们的第一个曲线群的嵌入度 。
然后, 我们使用这个新的嵌入度和该扩张域上的第二个曲线群构建扩张域 。所有 17 阶椭圆曲线点都可以使用 中的坐标找到, 因此可以方便地处理 。我们已在库中详细记录了配对的细节。
https://github.com/pluto/ronkathon/blob/main/src/curve/README.md
KZG
https://github.com/pluto/ronkathon/blob/main/src/kzg/README.md
在 KZG 中，我们需要结构化参考串 (SRS) 形式的可信设置。我们用两个同构的曲线群 和 的生成元生成 SRS。SRS 是两条曲线上的点的列表。 中的 SRS 中的点数大于等于我们要证明的约束数量（要证明的多项式的次数）, 而第二个曲线群 的SRS中的点的数量大于等于我们的掩除数多项式的次数。然后，我们在曲线标量域中选择一个随机数 ，并将 SRS 构造为：
类似地:
其中 是多项式中的门数和系数数量。一旦我们有了 SRS，我们就可以做出对多项式既绑定又隐藏的承诺了（假设可信设置已正确创建）。我们首先承诺想要证明的多项式，方法是将多项式的系数与 SRS 中的点相乘, 然后将它们加在一起以获得第一个曲线群中的一个点。
其中 是多项式的次数, 是多项式的第个 系数。然后，我们选择一个值来求 处的多项式的值以及求值结果。注意，我们的多项式与曲线有相同的阶数17 。然后我们对求值承诺并将结果称为
然后, 配对获取这些输入并检查这两个配对是否相等, 同时利用配对的双线性性来实现乘法, 同时保留隐藏性。
非对称原语
我们还实现了一些非对称密码学原语（链接如下），其中使用与解密信息的密钥不同的密钥来加密信息。这些原语构成了大量的公钥基础设施，对于区块链账户和钱包至关重要。
我们有 Rivest、Shair、Alderman (RSA) 和椭圆曲线数字签名算法 (ECDSA) 的简单实现：
https://github.com/pluto/ronkathon/tree/main/src/rsa https://github.com/pluto/ronkathon/blob/main/src/ecdsa.rs
哈希
https://github.com/pluto/ronkathon/blob/main/src/hashes/README.md 我们支持 Sha256 和 Poseidon 的实现（感谢我们的开源贡献者 Sambhav！）。哈希函数对于确保计算中的数据完整性至关重要，它们将输入数据转换为唯一表示原始数据的固定大小的字符串。可用于数据存储、数字签名和口令管理等各种应用，提供高效、安全的数据验证方式，而无需存储原始数据。Poseidon 的独特之处在于它属于一个新的哈希函数家族：代数哈希函数，具有在构造零知识证明时所需的性质。
https://github.com/pluto/ronkathon/blob/main/src/hashes/README.md
https://autoparallel.github.io/poseidon/index.html
结论
我们会继续向存储库中添加原语，请继续关注。如有任何问题，请随时通过 tg 联系。我们正在积极探索 MPC 原语。