博客
关于我
daelk-cryptography curve25519-dalek源码解析——之Field表示
阅读量:274 次
发布时间:2019-03-01

本文共 2544 字,大约阅读时间需要 8 分钟。

1. Scalar结构

在这种情况下,我们需要定义一个Scalar结构,该结构代表一个小于2^255的整数,并用于表示一个域域中的元素。对于Curve25519曲线,其域域p值为2^255 - 19。

#[derive(Copy, Clone)]
pub struct Scalar {
/// `bytes`是小端序编码的整数表示一个域域中的元素。
///
/// #Invariant
/// - `bytes`的整数值必须小于2^255,或者
/// - `bytes[31]`的高位必须为零。这确保在计算NAF表示时有进位空间。
pub(crate) bytes: [u8; 32],
}

Scalar类型中的bytes成员被标记为pub(crate),这意味着该成员在本crate内可见,但对其他crate外的代码不可见。

2. UnpackedScalar结构

程序默认使用u64_backend特性,UnpackedScalar用于表示GF(l)域,其中l = 2^252 + 27742317777372353535851937790883648493。

#[cfg(feature = "u64_backend")]
type UnpackedScalar = backend::serial::u64::scalar::Scalar52;
#[cfg(feature = "u32_backend")]
type UnpackedScalar = backend::serial::u32::scalar::Scalar29;

3. Scalar与UnpackedScalar转换

3.1 Scalar转换为UnpackedScalar

Scalar转换为UnpackedScalar的实现如下:

/// 将32字节的Scalar值转换为5个52位的UnpackedScalar 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; // 52位掩码
let top_mask = (1u64 << 48) - 1; // 48位掩码
let mut s = Scalar52::zero();
// 存储有效的256位值
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()方法将结果转换回Scalar值。
  • 4. 常量值验证

    constant.rs中定义了一些常量值。L表示基点的阶,即2^252 + 27742317777372353535851937790883648493。

    pub(crate) const L: Scalar52 = Scalar52([
    0x0002631a5cf5d3ed,
    0x000dea2f79cd6581,
    0x000000000014def9,
    0x0000000000000000,
    0x0000100000000000,
    ]);
    // `L` * `LFACTOR` = -1 (mod 2^52)
    pub(crate) const LFACTOR: u64 = 0x51da312547e1b;
    // `R` = R % L,其中 R = 2^260
    pub(crate) const R: Scalar52 = Scalar52([
    0x000f48bd6721e6ed,
    0x0003bab5ac67e45a,
    0x000fffffeb35e51b,
    0x000fffffffffffff,
    0x00000fffffffffff,
    ]);
    // `RR` = (R^2) % L,其中 R = 2^260
    pub(crate) const RR: Scalar52 = Scalar52([
    0x0009d265e952d13b,
    0x000d63c715bea69f,
    0x0005be65cb687604,
    0x0003dceec73d217f,
    0x000009411b7c309a,
    ]);

    通过Sage验证:

    • L = 2^252 + 27742317777372353535851937790883648493
    • LFACTOR = 0x51da312547e1b
    • R = 2^260
    • RR = (R^2) % L
    • LR满足Montgomery减少的条件。

    5. 生成程序帮助文档

    使用/////!格式的注释会生成以cargo doc命令运行的HTML帮助文档。

    转载地址:http://tfqx.baihongyu.com/

    你可能感兴趣的文章
    Objective-C实现Julia集算法(附完整源码)
    查看>>
    Objective-C实现jump search跳转搜索算法(附完整源码)
    查看>>
    Objective-C实现k nearest neighbours k最近邻分类算法(附完整源码)
    查看>>
    Objective-C实现k-means clustering均值聚类算法(附完整源码)
    查看>>
    Objective-C实现k-Means算法(附完整源码)
    查看>>
    Objective-C实现k-nearest算法(附完整源码)
    查看>>
    Objective-C实现KadaneAlgo计算给定数组的最大连续子数组和算法(附完整源码)
    查看>>
    Objective-C实现kahns algorithm卡恩算法(附完整源码)
    查看>>
    Objective-C实现karatsuba大数相乘算法(附完整源码)
    查看>>
    Objective-C实现karger算法(附完整源码)
    查看>>
    Objective-C实现KMP搜索算法(附完整源码)
    查看>>
    Objective-C实现Knapsack problem背包问题算法(附完整源码)
    查看>>
    Objective-C实现knapsack背包问题算法(附完整源码)
    查看>>
    Objective-C实现knapsack背包问题算法(附完整源码)
    查看>>
    Objective-C实现knight tour骑士之旅算法(附完整源码)
    查看>>
    Objective-C实现knight Tour骑士之旅算法(附完整源码)
    查看>>
    Objective-C实现KNN算法(附完整源码)
    查看>>
    Objective-C实现KNN算法(附完整源码)
    查看>>
    Objective-C实现KNN算法(附完整源码)
    查看>>
    Objective-C实现knuth morris pratt(KMP)算法(附完整源码)
    查看>>