daelk-cryptography curve25519-dalek源码解析——之Field表示

2023-10-24 15:30
文章标签 源码 解析 表示 field cryptography daelk curve25519 dalek

本文主要是介绍daelk-cryptography curve25519-dalek源码解析——之Field表示，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://github.com/dalek-cryptography/curve25519-dalek

1. Scalar结构

针对p<2255的域filed，采用scalar以little-endian的数组形式来表示：【对于Curve25519，其p值为 2255 - 19】

/// The `Scalar` struct holds an integer \\(s < 2\^{255} \\) which
/// represents an element of \\(\mathbb Z / \ell\\).
#[derive(Copy, Clone)]
pub struct Scalar {/// `bytes` is a little-endian byte encoding of an integer representing a scalar modulo the/// group order.////// # Invariant////// The integer representing this scalar must be bounded above by \\(2\^{255}\\), or/// equivalently the high bit of `bytes[31]` must be zero.////// This ensures that there is room for a carry bit when computing a NAF representation.//// XXX This is pub(crate) so we can write literal constants.  If const fns were stable, we could//     make the Scalar constructors const fns and use those instead.pub(crate) bytes: [u8; 32], 
}

Scalar类型中的bytes成员定义为pub(crate)，表示该成员可在本crate内public可见，但对除本crate外的其它crates中不可见。

因此，对于：
x = 2238329342913194256032495932344128051776374960164957527413114840482143558222

sage: hex(2238329342913194256032495932344128051776374960164957527413114840482143
....: 558222)
'4f2d979a8f449d44442cc1b1085a552527dc21b64b413598408475d34b45a4e'
sage: len('4f2d979a8f449d44442cc1b1085a552527dc21b64b413598408475d34b45a4e'
....: )
63  //对应的 the high bit of `bytes[31]` must be zero.

/// // x = 2238329342913194256032495932344128051776374960164957527413114840482143558222/// let X: Scalar = Scalar::from_bytes_mod_order([///         0x4e, 0x5a, 0xb4, 0x34, 0x5d, 0x47, 0x08, 0x84,///         0x59, 0x13, 0xb4, 0x64, 0x1b, 0xc2, 0x7d, 0x52,///         0x52, 0xa5, 0x85, 0x10, 0x1b, 0xcc, 0x42, 0x44,///         0xd4, 0x49, 0xf4, 0xa8, 0x79, 0xd9, 0xf2, 0x04,///     ]);

2. UnpackedScalar结构

程序中默认采用的是u64_backend feature
UnpackedScalar用于代表GF(l)域，其中l=2^252 + 27742317777372353535851937790883648493

/// An `UnpackedScalar` represents an element of the field GF(l), optimized for speed.
///
/// This is a type alias for one of the scalar types in the `backend`
/// module.
#[cfg(feature = "u64_backend")]
type UnpackedScalar = backend::serial::u64::scalar::Scalar52;/// An `UnpackedScalar` represents an element of the field GF(l), optimized for speed.
///
/// This is a type alias for one of the scalar types in the `backend`
/// module.
#[cfg(feature = "u32_backend")]
type UnpackedScalar = backend::serial::u32::scalar::Scalar29;

参照libsnark中的格式const mp_size_t alt_bn128_r_limbs = (alt_bn128_r_bitcount+GMP_NUMB_BITS-1)/GMP_NUMB_BITS;，即bitcount=255：

  • 对于64位系统，数组大小的计算公式为n=roundup[(bitcount+64-1)/64]=5，为了减少计算复杂度（无需考虑所有64位，仅需关注libm位的计算操作），libm仅需用满足libm*n略大于等于bitcount，此时libm本可以取值51（51*5=255），但考虑到Montgomery multiplication reduce的需要，libm取值52。
  • 对于32位系统，数组大小的计算公式为n=roundup[(bitcount+32-1)/32]=9，同理此时libm取值29。
/// The `Scalar52` struct represents an element in
/// \\(\mathbb Z / \ell \mathbb Z\\) as 5 \\(52\\)-bit limbs.
#[derive(Copy,Clone)]
pub struct Scalar52(pub [u64; 5]);

3. Scalar与UnpackedScalar转换

	/// let inv_X: Scalar = X.invert();/// assert!(XINV == inv_X);/// let should_be_one: Scalar = &inv_X * &X;/// assert!(should_be_one == Scalar::one());/// ```pub fn invert(&self) -> Scalar {self.unpack().invert().pack()}/// Unpack this `Scalar` to an `UnpackedScalar` for faster arithmetic.pub(crate) fn unpack(&self) -> UnpackedScalar {UnpackedScalar::from_bytes(&self.bytes)}

3.1 Scalar转换为UnpackedScalar

Scalar转换为UnpackedScalar的代码细节为：

	/// Unpack a 32 byte / 256 bit scalar into 5 52-bit limbs.pub fn from_bytes(bytes: &[u8; 32]) -> Scalar52 {let mut words = [0u64; 4];for i in 0..4 {for j in 0..8 {words[i] |= (bytes[(i * 8) + j] as u64) << (j * 8);}}let mask = (1u64 << 52) - 1; //仅取52bitlet top_mask = (1u64 << 48) - 1; //仅取48bitlet mut s = Scalar52::zero();// 一共仅保留256bit，words数组中是将scalar值按64bit为单位分别存储// 以下是要以52bit单位分别存储到s数组中，需要对words中的内容进行移位及mask处理，s数组内一共存储256bit有效位数。s[ 0] =   words[0]                            & mask; s[ 1] = ((words[0] >> 52) | (words[1] << 12)) & mask;s[ 2] = ((words[1] >> 40) | (words[2] << 24)) & mask;s[ 3] = ((words[2] >> 28) | (words[3] << 36)) & mask;s[ 4] =  (words[3] >> 16)                     & top_mask;s}

3.2 invert()操作

有限域内的乘法具有以下特征：

x(p-2) * x = x(p-1) = 1 (mod p)

由此可推测出，求有限域的x值的倒数可转换为求x(p-2)的值。

程序中，对Scalar值求倒数，是先通过unpack()函数将Scalar转换为UnpackedScalar，然后对UnpackedScalar求倒数，最后通过pack()函数将UnpackedScalar转换为Scalar值。

impl Scalar {/// let inv_X: Scalar = X.invert();/// assert!(XINV == inv_X);/// let should_be_one: Scalar = &inv_X * &X;/// assert!(should_be_one == Scalar::one());/// ```pub fn invert(&self) -> Scalar {self.unpack().invert().pack()}/// Unpack this `Scalar` to an `UnpackedScalar` for faster arithmetic.pub(crate) fn unpack(&self) -> UnpackedScalar {UnpackedScalar::from_bytes(&self.bytes)}
}impl UnpackedScalar {/// Inverts an UnpackedScalar not in Montgomery form.pub fn invert(&self) -> UnpackedScalar {self.to_montgomery().montgomery_invert().from_montgomery()}/// Pack the limbs of this `UnpackedScalar` into a `Scalar`.fn pack(&self) -> Scalar {Scalar{ bytes: self.to_bytes() }}
}

对于u64_backend feature, 有 type UnpackedScalar = backend::serial::u64::scalar::Scalar52;，所以对于
to_montgomery()的具体实现如下：

impl Scalar52 {/// Puts a Scalar52 in to Montgomery form, i.e. computes `a*R (mod l)`#[inline(never)]pub fn to_montgomery(&self) -> Scalar52 {Scalar52::montgomery_mul(self, &constants::RR) //将数组中52*5=260，260bit所有位数都用上。pub struct Scalar52(pub [u64; 5]);}/// Compute `(a * b) / R` (mod l), where R is the Montgomery modulus 2^260#[inline(never)]pub fn montgomery_mul(a: &Scalar52, b: &Scalar52) -> Scalar52 {Scalar52::montgomery_reduce(&Scalar52::mul_internal(a, b))}/// Compute `a * b`#[inline(always)]pub (crate) fn mul_internal(a: &Scalar52, b: &Scalar52) -> [u128; 9] {let mut z = [0u128; 9];z[0] = m(a[0],b[0]);z[1] = m(a[0],b[1]) + m(a[1],b[0]);z[2] = m(a[0],b[2]) + m(a[1],b[1]) + m(a[2],b[0]);z[3] = m(a[0],b[3]) + m(a[1],b[2]) + m(a[2],b[1]) + m(a[3],b[0]);z[4] = m(a[0],b[4]) + m(a[1],b[3]) + m(a[2],b[2]) + m(a[3],b[1]) + m(a[4],b[0]);z[5] =                m(a[1],b[4]) + m(a[2],b[3]) + m(a[3],b[2]) + m(a[4],b[1]);z[6] =                               m(a[2],b[4]) + m(a[3],b[3]) + m(a[4],b[2]);z[7] =                                              m(a[3],b[4]) + m(a[4],b[3]);z[8] =                                                             m(a[4],b[4]);z}/// u64 * u64 = u128 multiply helper#[inline(always)]fn m(x: u64, y: u64) -> u128 {(x as u128) * (y as u128)}/// Compute `limbs/R` (mod l), where R is the Montgomery modulus 2^260#[inline(always)]pub (crate) fn montgomery_reduce(limbs: &[u128; 9]) -> Scalar52 {#[inline(always)]fn part1(sum: u128) -> (u128, u64) {let p = (sum as u64).wrapping_mul(constants::LFACTOR) & ((1u64 << 52) - 1);((sum + m(p,constants::L[0])) >> 52, p)}#[inline(always)]fn part2(sum: u128) -> (u128, u64) {let w = (sum as u64) & ((1u64 << 52) - 1);(sum >> 52, w)}// note: l3 is zero, so its multiplies can be skippedlet l = &constants::L;// the first half computes the Montgomery adjustment factor n, and begins adding n*l to make limbs divisible by Rlet (carry, n0) = part1(        limbs[0]);let (carry, n1) = part1(carry + limbs[1] + m(n0,l[1]));let (carry, n2) = part1(carry + limbs[2] + m(n0,l[2]) + m(n1,l[1]));let (carry, n3) = part1(carry + limbs[3]              + m(n1,l[2]) + m(n2,l[1]));let (carry, n4) = part1(carry + limbs[4] + m(n0,l[4])              + m(n2,l[2]) + m(n3,l[1]));// limbs is divisible by R now, so we can divide by R by simply storing the upper half as the resultlet (carry, r0) = part2(carry + limbs[5]              + m(n1,l[4])              + m(n3,l[2]) + m(n4,l[1]));let (carry, r1) = part2(carry + limbs[6]                           + m(n2,l[4])              + m(n4,l[2]));let (carry, r2) = part2(carry + limbs[7]                                        + m(n3,l[4])             );let (carry, r3) = part2(carry + limbs[8]                                                     + m(n4,l[4]));let         r4 = carry as u64;// result may be >= l, so attempt to subtract lScalar52::sub(&Scalar52([r0,r1,r2,r3,r4]), l)}
}

4. constant.rs中常量值sage验证

/// constant.rs中有记录一些常量值。
/// `L` is the order of base point, i.e. 2^252 + 27742317777372353535851937790883648493
pub(crate) const L: Scalar52 = Scalar52([ 0x0002631a5cf5d3ed, 0x000dea2f79cd6581, 0x000000000014def9, 0x0000000000000000, 0x0000100000000000 ]);/// 其实即为L[0]*LFACTOR = -1 (mod 2^52) = 2^52-1 (mod 2^52)
/// (L[i]<<52)*LFACTOR = 0 (mod 2^52) 其中 1 =< i <= 4
/// `L` * `LFACTOR` = -1 (mod 2^52)
pub(crate) const LFACTOR: u64 = 0x51da312547e1b;/// `R` = R % L where R = 2^260
pub(crate) const R: Scalar52 = Scalar52([ 0x000f48bd6721e6ed, 0x0003bab5ac67e45a, 0x000fffffeb35e51b, 0x000fffffffffffff, 0x00000fffffffffff ]);/// `RR` = (R^2) % L where R = 2^260
pub(crate) const RR: Scalar52 = Scalar52([ 0x0009d265e952d13b, 0x000d63c715bea69f, 0x0005be65cb687604, 0x0003dceec73d217f, 0x000009411b7c309a ]);

对应的sage验证为：

sage: 2^252 + 27742317777372353535851937790883648493
7237005577332262213973186563042994240857116359379907606001950938285454250989
sage: is_prime(72370055773322622139731865630429942408571163593799076060019509382
....: 85454250989)
True
sage: hex(7237005577332262213973186563042994240857116359379907606001950938285454
....: 250989)
'1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed'  //即pub(crate) const L: Scalar52为数组内每个元素只截取13个数字（52bit），按little-endian方式存储。sage: L=2^252 + 27742317777372353535851937790883648493
sage: LFACTOR=0x51da312547e1b
sage: LFACTOR
1439961107955227
sage: mod(L*LFACTOR, 2^52)  //即`L` * `LFACTOR` = -1 (mod 2^52)
4503599627370495
sage: 2^52
4503599627370496sage: R=2^260
sage: mod(R,L)
7237005577332262213973186563042994233755083008372585100823854863819240236781
sage: hex(7237005577332262213973186563042994233755083008372585100823854863819240
....: 236781)
'fffffffffffffffffffffffffffffeb35e51b3bab5ac67e45af48bd6721e6ed' //即pub(crate) const R: Scalar52为数组内每个元素只截取13个数字（52bit），按little-endian方式存储。sage: mod(R^2, L)
4185850391763183796333492317919282507600454137915443218209456916606550724923
sage: hex(4185850391763183796333492317919282507600454137915443218209456916606550
....: 724923)
'9411b7c309a3dceec73d217f5be65cb687604d63c715bea69f9d265e952d13b'
sage:sage: gcd(L,R) //符合Montgomery reduction定义的条件。可参见https://blog.csdn.net/mutourend/article/details/95613967 第2.4.1节内容
1

5. 生成程序帮助文档

以///或//!格式表示的注释，在以cargo doc命令运行会在target/doc目录下生成相应的.html帮助文档。
在这里插入图片描述

参考资料：
[1] https://stackoverflow.com/questions/41666235/how-do-i-make-an-rust-item-public-within-a-crate-but-private-outside-it

这篇关于daelk-cryptography curve25519-dalek源码解析——之Field表示的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/276094。

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
Java ArrayList扩容机制 （源码解读）

Java ArrayList扩容机制 （源码解读）

结论：初始长度为10，若所需长度小于1.5倍原长度，则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1：数组默认长度         2:这是一个共享的空数组实例，用于明确创建长度为0时的ArrayList ，比如通过 new ArrayList<>(0)，ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL
阅读更多...
如何在Visual Studio中调试.NET源码

如何在Visual Studio中调试.NET源码

今天偶然在看别人代码时，发现在他的代码里使用了Any判断List<T>是否为空。 我一般的做法是先判断是否为null，再判断Count。 看了一下Count的源码如下： 1 [__DynamicallyInvokable]2 public int Count3 {4 [__DynamicallyInvokable]5 get
阅读更多...
工厂ERP管理系统实现源码（JAVA）

工厂ERP管理系统实现源码（JAVA）

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本，并实时掌握各环节的运营状况。 在采购管理方面，系统能够处理采购订单、供应商管理和采购入库等流程，确保采购过程的透明和高效。仓库管理方面，实现库存的精准管理，包括入库、出库、盘点等操作，确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、
阅读更多...
OWASP十大安全漏洞解析

OWASP十大安全漏洞解析

OWASP（开放式Web应用程序安全项目）发布的“十大安全漏洞”列表是Web应用程序安全领域的权威指南，它总结了Web应用程序中最常见、最危险的安全隐患。以下是对OWASP十大安全漏洞的详细解析： 1. 注入漏洞（Injection） 描述：攻击者通过在应用程序的输入数据中插入恶意代码，从而控制应用程序的行为。常见的注入类型包括SQL注入、OS命令注入、LDAP注入等。 影响：可能导致数据泄
阅读更多...
从状态管理到性能优化：全面解析 Android Compose

从状态管理到性能优化：全面解析 Android Compose

文章目录 引言一、Android Compose基本概念1.1 什么是Android Compose?1.2 Compose的优势1.3 如何在项目中使用Compose 二、Compose中的状态管理2.1 状态管理的重要性2.2 Compose中的状态和数据流2.3 使用State和MutableState处理状态2.4 通过ViewModel进行状态管理 三、Compose中的列表和滚动
阅读更多...
Spring 源码解读：自定义实现Bean定义的注册与解析

Spring 源码解读：自定义实现Bean定义的注册与解析

引言 在Spring框架中，Bean的注册与解析是整个依赖注入流程的核心步骤。通过Bean定义，Spring容器知道如何创建、配置和管理每个Bean实例。本篇文章将通过实现一个简化版的Bean定义注册与解析机制，帮助你理解Spring框架背后的设计逻辑。我们还将对比Spring中的BeanDefinition和BeanDefinitionRegistry，以全面掌握Bean注册和解析的核心原理。
阅读更多...
CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 （最大值之和）给定整数序列 a0,⋯,an−1，求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr（其中0≤l≤r<n0≤l≤r<n）表示，对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同，当且仅当下标不同。 例如，当原序列为 [1,2,1,2] 时，要计算子序列 [
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2