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; //仅取52bit
let top_mask = (1u64 << 48) - 1; //仅取48bit
let 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 skipped
let l = &constants::L;
// the first half computes the Montgomery adjustment factor n, and begins adding n*l to make limbs divisible by R
let (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 result
let (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 l
Scalar52::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
4503599627370496
sage: 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表示[通俗易懂]分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/88308.html