std.crypto.25519.edwards25519.crypto
别名
别名目标 std.crypto
std.crypto.25519.edwards25519.debug
别名
别名目标 std.debug
std.crypto.25519.edwards25519.Edwards25519
容器
Edwards25519 上的群运算。
字段
Fescalarencoded_lengthfromBytestoBytesrejectNonCanonicalbasePointidentityElementrejectIdentityrejectUnexpectedSubgroupclearCofactorrejectLowOrdernegdbladdsubshiftcMovpcSelectslidepcMulpcMul16precomputebasePointPcmulmulPublicmulDoubleBasePublicmulMulticlampedMulxmontToYmontmontToEdelligator2fromHashstringToPointsfromStringfromUniform
std.crypto.25519.edwards25519.Edwards25519.add
函数
将两个 Edwards25519 点相加。
pub fn add(p: Edwards25519, q: Edwards25519) Edwards25519
参数
p: Edwards25519
q: Edwards25519
std.crypto.25519.edwards25519.Edwards25519.basePoint
常量
edwards25519 基点。
std.crypto.25519.edwards25519.Edwards25519.basePointPc
常量
std.crypto.25519.edwards25519.Edwards25519.clampedMul
函数
先对标量进行“钳制”,再与 Edwards25519 点相乘。 钳制强制使标量成为余因子的倍数,以防止小子群攻击。 强烈建议在 DH 操作中这样做。 若结果点是单位元,返回 error.WeakPublicKey。
pub fn clampedMul(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519
参数
p: Edwards25519
s: [32]u8
std.crypto.25519.edwards25519.Edwards25519.clearCofactor
函数
将点乘以余因子
pub fn clearCofactor(p: Edwards25519) Edwards25519
参数
p: Edwards25519
std.crypto.25519.edwards25519.Edwards25519.cMov
函数
fn cMov(p: *Edwards25519, a: Edwards25519, c: u64) void
参数
std.crypto.25519.edwards25519.Edwards25519.dbl
函数
将 Edwards25519 点加倍。
pub fn dbl(p: Edwards25519) Edwards25519
参数
p: Edwards25519
std.crypto.25519.edwards25519.Edwards25519.elligator2
类型函数
Elligator2 映射:返回 Montgomery 仿射坐标
pub fn elligator2(r: Fe) struct { x: Fe, y: Fe, not_square: bool }
参数
r: Fe
std.crypto.25519.edwards25519.Edwards25519.encoded_length
常量
点的压缩表示的字节长度。
usize
std.crypto.25519.edwards25519.Edwards25519.Fe
别名
底层素数域。
std.crypto.25519.edwards25519.Edwards25519.fromBytes
函数
从压缩的(Y+sign)坐标解码 Edwards25519 点。
pub fn fromBytes(s: [encoded_length]u8) EncodingError!Edwards25519
参数
s: [encoded_length]u8
错误
- InvalidEncoding EncodingError
std.crypto.25519.edwards25519.Edwards25519.fromHash
函数
将 64 位哈希映射到 Edwards25519 曲线点
pub fn fromHash(h: [64]u8) Edwards25519
参数
h: [64]u8
std.crypto.25519.edwards25519.Edwards25519.fromString
函数
将上下文 ctx 和字符串 s 哈希为 Edwards25519 点。
此函数实现“Hashing to Elliptic Curves”标准文档中的 edwards25519_XMD:SHA-512_ELL2_RO_ 和 edwards25519_XMD:SHA-512_ELL2_NU_ 方法。
虽然标准未严格要求,但为兼容其他实现,建议避免在 上下文中使用 NUL 字符。
pub fn fromString(comptime random_oracle: bool, ctx: []const u8, s: []const u8) Edwards25519
参数
random_oracle: bool
ctx: []const u8
s: []const u8
std.crypto.25519.edwards25519.Edwards25519.fromUniform
函数
将 32 位均匀位串映射为 edwards25519 点。
pub fn fromUniform(r: [32]u8) Edwards25519
参数
r: [32]u8
std.crypto.25519.edwards25519.Edwards25519.identityElement
常量
std.crypto.25519.edwards25519.Edwards25519.montToEd
函数
fn montToEd(x: Fe, y: Fe) Edwards25519
参数
std.crypto.25519.edwards25519.Edwards25519.mul
函数
将 Edwards25519 点乘以未经钳位的标量。 若基点生成小阶群,返回 error.WeakPublicKey; 若结果是单位元,返回 error.IdentityElement。
pub fn mul(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519
参数
p: Edwards25519
s: [32]u8
std.crypto.25519.edwards25519.Edwards25519.mulDoubleBasePublic
函数
对公开参数执行双基点乘法:以可变时间计算 (p1s1)+(p2s2)。 可用于签名验证。
pub fn mulDoubleBasePublic(p1: Edwards25519, s1: [32]u8, p2: Edwards25519, s2: [32]u8) WeakPublicKeyError!Edwards25519
参数
错误
- WeakPublicKey WeakPublicKeyError
std.crypto.25519.edwards25519.Edwards25519.mulMulti
函数
针对公开数据,以可变时间执行多标量乘法。 计算 ps0ss0 + ps1ss1 + ps2*ss2...,比逐个执行这些操作更快。
pub fn mulMulti(comptime count: usize, ps: [count]Edwards25519, ss: [count][32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519
参数
std.crypto.25519.edwards25519.Edwards25519.mulPublic
函数
以可变时间将 Edwards25519 点乘以公开标量。 可用于签名验证。
pub fn mulPublic(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519
参数
p: Edwards25519
s: [32]u8
std.crypto.25519.edwards25519.Edwards25519.neg
函数
翻转 X 坐标的符号。
pub fn neg(p: Edwards25519) Edwards25519
参数
p: Edwards25519
std.crypto.25519.edwards25519.Edwards25519.pcMul
函数
fn pcMul(pc: *const [9]Edwards25519, s: [32]u8, comptime vartime: bool) IdentityElementError!Edwards25519
参数
错误
- IdentityElement IdentityElementError
std.crypto.25519.edwards25519.Edwards25519.pcMul16
函数
fn pcMul16(pc: *const [16]Edwards25519, s: [32]u8, comptime vartime: bool) IdentityElementError!Edwards25519
参数
错误
- IdentityElement IdentityElementError
std.crypto.25519.edwards25519.Edwards25519.pcSelect
函数
fn pcSelect(comptime n: usize, pc: *const [n]Edwards25519, b: u8) Edwards25519
参数
std.crypto.25519.edwards25519.Edwards25519.precompute
函数
fn precompute(p: Edwards25519, comptime count: usize) [1 + count]Edwards25519
参数
p: Edwards25519
count: usize
std.crypto.25519.edwards25519.Edwards25519.rejectIdentity
函数
拒绝单位元。
pub fn rejectIdentity(p: Edwards25519) IdentityElementError!void
参数
p: Edwards25519
错误
- IdentityElement IdentityElementError
std.crypto.25519.edwards25519.Edwards25519.rejectLowOrder
函数
检查该点是否生成低阶群。
如果是,则返回 WeakPublicKey 错误。
pub fn rejectLowOrder(p: Edwards25519) WeakPublicKeyError!void
参数
p: Edwards25519
错误
- WeakPublicKey WeakPublicKeyError
std.crypto.25519.edwards25519.Edwards25519.rejectNonCanonical
函数
检查点的编码是否规范。
pub fn rejectNonCanonical(s: [32]u8) NonCanonicalError!void
参数
s: [32]u8
错误
- NonCanonical NonCanonicalError
std.crypto.25519.edwards25519.Edwards25519.rejectUnexpectedSubgroup
函数
若点不在标准基点生成的素数阶子群中,则拒绝该点。
如果点不在主子群中:
- 若属于低阶子群,返回
WeakPublicKeyError。 - 否则返回
UnexpectedSubgroupError。
pub fn rejectUnexpectedSubgroup(p: Edwards25519) (WeakPublicKeyError || UnexpectedSubgroupError)!void
参数
p: Edwards25519
std.crypto.25519.edwards25519.Edwards25519.scalar
别名
模主子群阶的域算术。
std.crypto.25519.edwards25519.Edwards25519.shift
函数
对点连续执行 n 次倍点。
fn shift(p: Edwards25519, n: comptime_int) Edwards25519
参数
p: Edwards25519
n: comptime_int
std.crypto.25519.edwards25519.Edwards25519.slide
函数
fn slide(s: [32]u8) [2 * 32]i8
参数
s: [32]u8
std.crypto.25519.edwards25519.Edwards25519.stringToPoints
函数
fn stringToPoints(comptime n: usize, ctx: []const u8, s: []const u8) [n]Edwards25519
参数
n: usize
ctx: []const u8
s: []const u8
std.crypto.25519.edwards25519.Edwards25519.sub
函数
两个 Edwards25519 点相减。
pub fn sub(p: Edwards25519, q: Edwards25519) Edwards25519
参数
p: Edwards25519
q: Edwards25519
std.crypto.25519.edwards25519.Edwards25519.toBytes
函数
编码 Edwards25519 点。
pub fn toBytes(p: Edwards25519) [encoded_length]u8
参数
p: Edwards25519
std.crypto.25519.edwards25519.Edwards25519.xmontToYmont
函数
fn xmontToYmont(x: Fe) NotSquareError!Fe
参数
x: Fe
错误
- NotSquare NotSquareError
std.crypto.25519.edwards25519.EncodingError
别名
std.crypto.25519.edwards25519.fmt
别名
别名目标 std.fmt
std.crypto.25519.edwards25519.htest
常量
std.crypto.25519.edwards25519.IdentityElementError
别名
std.crypto.25519.edwards25519.mem
别名
别名目标 std.mem
std.crypto.25519.edwards25519.NonCanonicalError
别名
std.crypto.25519.edwards25519.NotSquareError
别名
std.crypto.25519.edwards25519.std
别名
别名目标 std
std.crypto.25519.edwards25519.UnexpectedSubgroupError
别名
std.crypto.25519.edwards25519.WeakPublicKeyError
别名
源码
std/crypto/25519/edwards25519.zig
const std = @import("std");
const crypto = std.crypto;
const debug = std.debug;
const fmt = std.fmt;
const mem = std.mem;
const EncodingError = crypto.errors.EncodingError;
const IdentityElementError = crypto.errors.IdentityElementError;
const NonCanonicalError = crypto.errors.NonCanonicalError;
const NotSquareError = crypto.errors.NotSquareError;
const WeakPublicKeyError = crypto.errors.WeakPublicKeyError;
const UnexpectedSubgroupError = crypto.errors.UnexpectedSubgroupError;
/// Edwards25519 上的群运算。
pub const Edwards25519 = struct {
/// 底层素数域。
pub const Fe = @import("field.zig").Fe;
/// 模主子群阶的域算术。
pub const scalar = @import("scalar.zig");
/// 点的压缩表示的字节长度。
pub const encoded_length: usize = 32;
x: Fe,
y: Fe,
z: Fe,
t: Fe,
is_base: bool = false,
/// 从压缩的(Y+sign)坐标解码 Edwards25519 点。
pub fn fromBytes(s: [encoded_length]u8) EncodingError!Edwards25519 {
const z = Fe.one;
const y = Fe.fromBytes(s);
var u = y.sq();
var v = u.mul(Fe.edwards25519d);
u = u.sub(z);
v = v.add(z);
var x = u.mul(v).pow2523().mul(u);
const vxx = x.sq().mul(v);
const has_m_root = vxx.sub(u).isZero();
const has_p_root = vxx.add(u).isZero();
if ((@intFromBool(has_m_root) | @intFromBool(has_p_root)) == 0) { // 尽量避免两个条件分支
return error.InvalidEncoding;
}
x.cMov(x.mul(Fe.sqrtm1), 1 - @intFromBool(has_m_root));
if (x.isZero() and (s[31] >> 7) != 0) {
return error.InvalidEncoding;
}
x.cMov(x.neg(), @intFromBool(x.isNegative()) ^ (s[31] >> 7));
const t = x.mul(y);
return Edwards25519{ .x = x, .y = y, .z = z, .t = t };
}
/// 编码 Edwards25519 点。
pub fn toBytes(p: Edwards25519) [encoded_length]u8 {
const zi = p.z.invert();
var s = p.y.mul(zi).toBytes();
s[31] ^= @as(u8, @intFromBool(p.x.mul(zi).isNegative())) << 7;
return s;
}
/// 检查点的编码是否规范。
pub fn rejectNonCanonical(s: [32]u8) NonCanonicalError!void {
return Fe.rejectNonCanonical(s, true);
}
/// edwards25519 基点。
pub const basePoint = Edwards25519{
.x = Fe{ .limbs = .{ 1738742601995546, 1146398526822698, 2070867633025821, 562264141797630, 587772402128613 } },
.y = Fe{ .limbs = .{ 1801439850948184, 1351079888211148, 450359962737049, 900719925474099, 1801439850948198 } },
.z = Fe.one,
.t = Fe{ .limbs = .{ 1841354044333475, 16398895984059, 755974180946558, 900171276175154, 1821297809914039 } },
.is_base = true,
};
pub const identityElement = Edwards25519{ .x = Fe.zero, .y = Fe.one, .z = Fe.one, .t = Fe.zero };
/// 拒绝单位元。
pub fn rejectIdentity(p: Edwards25519) IdentityElementError!void {
if (p.x.isZero()) {
return error.IdentityElement;
}
}
/// 若点不在标准基点生成的素数阶子群中,则拒绝该点。
///
/// 如果点不在主子群中:
///
/// - 若属于低阶子群,返回 `WeakPublicKeyError`。
/// - 否则返回 `UnexpectedSubgroupError`。
pub fn rejectUnexpectedSubgroup(p: Edwards25519) (WeakPublicKeyError || UnexpectedSubgroupError)!void {
try p.rejectLowOrder();
// 将 p 乘以子群的阶;这是一个素数阶群,因此结果应为单位元。
const _10 = p.dbl();
const _11 = p.add(_10);
const _100 = p.add(_11);
const _110 = _10.add(_100);
const _1000 = _10.add(_110);
const _1011 = _11.add(_1000);
const _10000 = _1000.dbl();
const _100000 = _10000.dbl();
const _100110 = _110.add(_100000);
const _1000000 = _100000.dbl();
const _1010000 = _10000.add(_1000000);
const _1010011 = _11.add(_1010000);
const _1100011 = _10000.add(_1010011);
const _1100111 = _100.add(_1100011);
const _1101011 = _100.add(_1100111);
const _10010011 = _1000000.add(_1010011);
const _10010111 = _100.add(_10010011);
const _10111101 = _100110.add(_10010111);
const _11010011 = _1000000.add(_10010011);
const _11100111 = _1010000.add(_10010111);
const _11101101 = _110.add(_11100111);
const _11110101 = _1000.add(_11101101);
const q = ((_11110101.add(((((_1101011.add(((((_10.add(((_1011.add(_11110101)).shift(126)
.add(_1010011)).shift(9).add(_11110101))).shift(7).add(_1100111)).shift(9).add(_11110101).shift(11)
.add(_10111101)).shift(8).add(_11100111)).shift(9))).shift(6).add(_1011)).shift(14).add(_10010011).shift(10)
.add(_1100011)).shift(9).add(_10010111)).shift(10))).shift(8).add(_11010011)).shift(8).add(_11101101);
if (q.x.isZero() and q.y.equivalent(q.z)) return;
return error.UnexpectedSubgroup;
}
/// 将点乘以余因子
pub fn clearCofactor(p: Edwards25519) Edwards25519 {
return p.dbl().dbl().dbl();
}
/// 检查该点是否生成低阶群。
/// 如果是,则返回 `WeakPublicKey` 错误。
pub fn rejectLowOrder(p: Edwards25519) WeakPublicKeyError!void {
const y_sqrtm1 = Fe.sqrtm1.mul(p.y);
if (p.x.isZero() or p.y.isZero() or p.z.isZero() or
y_sqrtm1.sub(p.x).isZero() or y_sqrtm1.add(p.x).isZero())
{
return error.WeakPublicKey;
}
}
/// 翻转 X 坐标的符号。
pub fn neg(p: Edwards25519) Edwards25519 {
return .{ .x = p.x.neg(), .y = p.y, .z = p.z, .t = p.t.neg() };
}
/// 将 Edwards25519 点加倍。
pub fn dbl(p: Edwards25519) Edwards25519 {
const t0 = p.x.add(p.y).sq();
var x = p.x.sq();
var z = p.y.sq();
const y = z.add(x);
z = z.sub(x);
x = t0.sub(y);
const t = p.z.sq2().sub(z);
return .{
.x = x.mul(t),
.y = y.mul(z),
.z = z.mul(t),
.t = x.mul(y),
};
}
/// 将两个 Edwards25519 点相加。
pub fn add(p: Edwards25519, q: Edwards25519) Edwards25519 {
const a = p.y.sub(p.x).mul(q.y.sub(q.x));
const b = p.x.add(p.y).mul(q.x.add(q.y));
const c = p.t.mul(q.t).mul(Fe.edwards25519d2);
var d = p.z.mul(q.z);
d = d.add(d);
const x = b.sub(a);
const y = b.add(a);
const z = d.add(c);
const t = d.sub(c);
return .{
.x = x.mul(t),
.y = y.mul(z),
.z = z.mul(t),
.t = x.mul(y),
};
}
/// 两个 Edwards25519 点相减。
pub fn sub(p: Edwards25519, q: Edwards25519) Edwards25519 {
return p.add(q.neg());
}
/// 对点连续执行 `n` 次倍点。
fn shift(p: Edwards25519, n: comptime_int) Edwards25519 {
var q = p;
for (0..n) |_| q = q.dbl();
return q;
}
fn cMov(p: *Edwards25519, a: Edwards25519, c: u64) void {
p.x.cMov(a.x, c);
p.y.cMov(a.y, c);
p.z.cMov(a.z, c);
p.t.cMov(a.t, c);
}
fn pcSelect(comptime n: usize, pc: *const [n]Edwards25519, b: u8) Edwards25519 {
var t = Edwards25519.identityElement;
comptime var i: u8 = 1;
inline while (i < pc.len) : (i += 1) {
t.cMov(pc[i], ((@as(usize, b ^ i) -% 1) >> 8) & 1);
}
return t;
}
fn slide(s: [32]u8) [2 * 32]i8 {
const reduced = if ((s[s.len - 1] & 0x80) == 0) s else scalar.reduce(s);
var e: [2 * 32]i8 = undefined;
for (reduced, 0..) |x, i| {
e[i * 2 + 0] = @as(i8, @as(u4, @truncate(x)));
e[i * 2 + 1] = @as(i8, @as(u4, @truncate(x >> 4)));
}
// 此时 e[0..63] 位于 0 到 15 之间,e[63] 位于 0 到 7 之间
var carry: i8 = 0;
for (e[0..63]) |*x| {
x.* += carry;
carry = (x.* + 8) >> 4;
x.* -= carry * 16;
}
e[63] += carry;
// 现在,包含 e[63] 在内,e[*] 均位于 -8 到 8 之间
return e;
}
// 采用 4 位窗口和前 8 个倍数进行标量乘法。
// 要求将标量转换为非相邻形式。
// 根据实际基准测试,仅将此方法用于多标量乘法。
// NAF 可将预计算表大小减半,但我们有意
// 避免这些表,以保持标准库轻量。
fn pcMul(pc: *const [9]Edwards25519, s: [32]u8, comptime vartime: bool) IdentityElementError!Edwards25519 {
std.debug.assert(vartime);
const e = slide(s);
var q = Edwards25519.identityElement;
var pos: usize = 2 * 32 - 1;
while (true) : (pos -= 1) {
const slot = e[pos];
if (slot > 0) {
q = q.add(pc[@as(usize, @intCast(slot))]);
} else if (slot < 0) {
q = q.sub(pc[@as(usize, @intCast(-slot))]);
}
if (pos == 0) break;
q = q.dbl().dbl().dbl().dbl();
}
try q.rejectIdentity();
return q;
}
// 使用 4 位窗口和前 15 个倍点进行标量乘法。
fn pcMul16(pc: *const [16]Edwards25519, s: [32]u8, comptime vartime: bool) IdentityElementError!Edwards25519 {
var q = Edwards25519.identityElement;
var pos: usize = 252;
while (true) : (pos -= 4) {
const slot: u4 = @truncate((s[pos >> 3] >> @as(u3, @truncate(pos))));
if (vartime) {
if (slot != 0) {
q = q.add(pc[slot]);
}
} else {
q = q.add(pcSelect(16, pc, slot));
}
if (pos == 0) break;
q = q.dbl().dbl().dbl().dbl();
}
try q.rejectIdentity();
return q;
}
fn precompute(p: Edwards25519, comptime count: usize) [1 + count]Edwards25519 {
var pc: [1 + count]Edwards25519 = undefined;
pc[0] = Edwards25519.identityElement;
pc[1] = p;
var i: usize = 2;
while (i <= count) : (i += 1) {
pc[i] = if (i % 2 == 0) pc[i / 2].dbl() else pc[i - 1].add(p);
}
return pc;
}
const basePointPc = pc: {
@setEvalBranchQuota(10000);
break :pc precompute(Edwards25519.basePoint, 15);
};
/// 将 Edwards25519 点乘以未经钳位的标量。
/// 若基点生成小阶群,返回 error.WeakPublicKey;
/// 若结果是单位元,返回 error.IdentityElement。
pub fn mul(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
const pc = if (p.is_base) basePointPc else pc: {
const xpc = precompute(p, 15);
xpc[4].rejectIdentity() catch return error.WeakPublicKey;
break :pc xpc;
};
return pcMul16(&pc, s, false);
}
/// 以可变时间将 Edwards25519 点乘以公开标量。
/// 可用于签名验证。
pub fn mulPublic(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
if (p.is_base) {
return pcMul16(&basePointPc, s, true);
} else {
const pc = precompute(p, 8);
pc[4].rejectIdentity() catch return error.WeakPublicKey;
return pcMul(&pc, s, true);
}
}
/// 对公开参数执行双基点乘法:*以可变时间*计算 (p1*s1)+(p2*s2)。
/// 可用于签名验证。
pub fn mulDoubleBasePublic(p1: Edwards25519, s1: [32]u8, p2: Edwards25519, s2: [32]u8) WeakPublicKeyError!Edwards25519 {
var pc1_array: [9]Edwards25519 = undefined;
const pc1 = if (p1.is_base) basePointPc[0..9] else pc: {
pc1_array = precompute(p1, 8);
pc1_array[4].rejectIdentity() catch return error.WeakPublicKey;
break :pc &pc1_array;
};
var pc2_array: [9]Edwards25519 = undefined;
const pc2 = if (p2.is_base) basePointPc[0..9] else pc: {
pc2_array = precompute(p2, 8);
pc2_array[4].rejectIdentity() catch return error.WeakPublicKey;
break :pc &pc2_array;
};
const e1 = slide(s1);
const e2 = slide(s2);
var q = Edwards25519.identityElement;
var pos: usize = 2 * 32 - 1;
while (true) : (pos -= 1) {
const slot1 = e1[pos];
if (slot1 > 0) {
q = q.add(pc1[@as(usize, @intCast(slot1))]);
} else if (slot1 < 0) {
q = q.sub(pc1[@as(usize, @intCast(-slot1))]);
}
const slot2 = e2[pos];
if (slot2 > 0) {
q = q.add(pc2[@as(usize, @intCast(slot2))]);
} else if (slot2 < 0) {
q = q.sub(pc2[@as(usize, @intCast(-slot2))]);
}
if (pos == 0) break;
q = q.dbl().dbl().dbl().dbl();
}
return q;
}
/// 针对公开数据,以*可变时间*执行多标量乘法。
/// 计算 ps0*ss0 + ps1*ss1 + ps2*ss2...,比逐个执行这些操作更快。
pub fn mulMulti(comptime count: usize, ps: [count]Edwards25519, ss: [count][32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
var pcs: [count][9]Edwards25519 = undefined;
var bpc: [9]Edwards25519 = undefined;
@memcpy(&bpc, basePointPc[0..bpc.len]);
for (ps, 0..) |p, i| {
if (p.is_base) {
pcs[i] = bpc;
} else {
pcs[i] = precompute(p, 8);
pcs[i][4].rejectIdentity() catch return error.WeakPublicKey;
}
}
var es: [count][2 * 32]i8 = undefined;
for (ss, 0..) |s, i| {
es[i] = slide(s);
}
var q = Edwards25519.identityElement;
var pos: usize = 2 * 32 - 1;
while (true) : (pos -= 1) {
for (es, 0..) |e, i| {
const slot = e[pos];
if (slot > 0) {
q = q.add(pcs[i][@as(usize, @intCast(slot))]);
} else if (slot < 0) {
q = q.sub(pcs[i][@as(usize, @intCast(-slot))]);
}
}
if (pos == 0) break;
q = q.dbl().dbl().dbl().dbl();
}
try q.rejectIdentity();
return q;
}
/// 先对标量进行“钳制”,再与 Edwards25519 点相乘。
/// 钳制强制使标量成为余因子的倍数,以防止小子群攻击。
/// 强烈建议在 DH 操作中这样做。
/// 若结果点是单位元,返回 error.WeakPublicKey。
///
///
pub fn clampedMul(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
var t: [32]u8 = s;
scalar.clamp(&t);
return mul(p, t);
}
// Montgomery 形式——恢复 y = sqrt(x^3 + A*x^2 + x)
fn xmontToYmont(x: Fe) NotSquareError!Fe {
var x2 = x.sq();
const x3 = x.mul(x2);
x2 = x2.mul32(Fe.edwards25519a_32);
return x.add(x2).add(x3).sqrt();
}
// 从 Montgomery 仿射坐标转换为 Edwards 扩展坐标
fn montToEd(x: Fe, y: Fe) Edwards25519 {
const x_plus_one = x.add(Fe.one);
const x_minus_one = x.sub(Fe.one);
const x_plus_one_y_inv = x_plus_one.mul(y).invert(); // 1/((x+1)*y)
// xed = sqrt(-A-2)*x/y
const xed = x.mul(Fe.edwards25519sqrtam2).mul(x_plus_one_y_inv).mul(x_plus_one);
// yed = (x-1)/(x+1),若分母为 0 则为 1。
var yed = x_plus_one_y_inv.mul(y).mul(x_minus_one);
yed.cMov(Fe.one, @intFromBool(x_plus_one_y_inv.isZero()));
return Edwards25519{
.x = xed,
.y = yed,
.z = Fe.one,
.t = xed.mul(yed),
};
}
/// Elligator2 映射:返回 Montgomery 仿射坐标
pub fn elligator2(r: Fe) struct { x: Fe, y: Fe, not_square: bool } {
const rr2 = r.sq2().add(Fe.one).invert();
var x = rr2.mul32(Fe.edwards25519a_32).neg(); // x=x1
var x2 = x.sq();
const x3 = x2.mul(x);
x2 = x2.mul32(Fe.edwards25519a_32); // x2 = A*x1^2
const gx1 = x3.add(x).add(x2); // gx1 = x1^3 + A*x1^2 + x1
const not_square = !gx1.isSquare();
// gx1 不是平方元 => x = -x1-A
x.cMov(x.neg(), @intFromBool(not_square));
x2 = Fe.zero;
x2.cMov(Fe.edwards25519a, @intFromBool(not_square));
x = x.sub(x2);
// 已有 y = sqrt(gx1) 或 sqrt(gx2),其中 gx2 = gx1*(A+x1)/(-x1),
// 但直接从曲线方程重新计算 y,速度也基本相同。
const y = xmontToYmont(x) catch unreachable;
return .{ .x = x, .y = y, .not_square = not_square };
}
/// 将 64 位哈希映射到 Edwards25519 曲线点
pub fn fromHash(h: [64]u8) Edwards25519 {
const fe_f = Fe.fromBytes64(h);
var elr = elligator2(fe_f);
const y_sign = !elr.not_square;
const y_neg = elr.y.neg();
elr.y.cMov(y_neg, @intFromBool(elr.y.isNegative()) ^ @intFromBool(y_sign));
return montToEd(elr.x, elr.y).clearCofactor();
}
fn stringToPoints(comptime n: usize, ctx: []const u8, s: []const u8) [n]Edwards25519 {
debug.assert(n <= 2);
const H = crypto.hash.sha2.Sha512;
const h_l: usize = 48;
var xctx = ctx;
var hctx: [H.digest_length]u8 = undefined;
if (ctx.len > 0xff) {
var st = H.init(.{});
st.update("H2C-OVERSIZE-DST-");
st.update(ctx);
st.final(&hctx);
xctx = hctx[0..];
}
const empty_block: [H.block_length]u8 = @splat(0);
var t = [3]u8{ 0, n * h_l, 0 };
var xctx_len_u8 = [1]u8{@as(u8, @intCast(xctx.len))};
var st = H.init(.{});
st.update(empty_block[0..]);
st.update(s);
st.update(t[0..]);
st.update(xctx);
st.update(xctx_len_u8[0..]);
var u_0: [H.digest_length]u8 = undefined;
st.final(&u_0);
var u: [n * H.digest_length]u8 = undefined;
var i: usize = 0;
while (i < n * H.digest_length) : (i += H.digest_length) {
u[i..][0..H.digest_length].* = u_0;
var j: usize = 0;
while (i > 0 and j < H.digest_length) : (j += 1) {
u[i + j] ^= u[i + j - H.digest_length];
}
t[2] += 1;
st = H.init(.{});
st.update(u[i..][0..H.digest_length]);
st.update(t[2..3]);
st.update(xctx);
st.update(xctx_len_u8[0..]);
st.final(u[i..][0..H.digest_length]);
}
var px: [n]Edwards25519 = undefined;
i = 0;
while (i < n) : (i += 1) {
@memset(u_0[0 .. H.digest_length - h_l], 0);
u_0[H.digest_length - h_l ..][0..h_l].* = u[i * h_l ..][0..h_l].*;
px[i] = fromHash(u_0);
}
return px;
}
/// 将上下文 `ctx` 和字符串 `s` 哈希为 Edwards25519 点。
///
/// 此函数实现“Hashing to Elliptic Curves”标准文档中的 edwards25519_XMD:SHA-512_ELL2_RO_
/// 和 edwards25519_XMD:SHA-512_ELL2_NU_ 方法。
///
/// 虽然标准未严格要求,但为兼容其他实现,建议避免在
/// 上下文中使用 NUL 字符。
pub fn fromString(comptime random_oracle: bool, ctx: []const u8, s: []const u8) Edwards25519 {
if (random_oracle) {
const px = stringToPoints(2, ctx, s);
return px[0].add(px[1]);
} else {
return stringToPoints(1, ctx, s)[0];
}
}
/// 将 32 位均匀位串映射为 edwards25519 点。
pub fn fromUniform(r: [32]u8) Edwards25519 {
var s = r;
const x_sign = s[31] >> 7;
s[31] &= 0x7f;
const elr = elligator2(Fe.fromBytes(s));
var p = montToEd(elr.x, elr.y);
const p_neg = p.neg();
p.cMov(p_neg, @intFromBool(p.x.isNegative()) ^ x_sign);
return p.clearCofactor();
}
};
const htest = @import("../test.zig");
test "packing/unpacking" {
const s = [1]u8{170} ++ @as([31]u8, @splat(0));
var b = Edwards25519.basePoint;
const pk = try b.mul(s);
var buf: [128]u8 = undefined;
try std.testing.expectEqualStrings(try std.mem.print(&buf, "{X}", .{&pk.toBytes()}), "074BC7E0FCBD587FDBC0969444245FADC562809C8F6E97E949AF62484B5B81A6");
const small_order_ss: [7][32]u8 = .{
.{
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 0(阶为 4)
},
.{
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 1(阶为 1)
},
.{
0x26, 0xe8, 0x95, 0x8f, 0xc2, 0xb2, 0x27, 0xb0, 0x45, 0xc3, 0xf4, 0x89, 0xf2, 0xef, 0x98, 0xf0, 0xd5, 0xdf, 0xac, 0x05, 0xd3, 0xc6, 0x33, 0x39, 0xb1, 0x38, 0x02, 0x88, 0x6d, 0x53, 0xfc, 0x05, // 270738550114484064931822528722565878893680426757531351946374360975030340202(阶为 8)
},
.{
0xc7, 0x17, 0x6a, 0x70, 0x3d, 0x4d, 0xd8, 0x4f, 0xba, 0x3c, 0x0b, 0x76, 0x0d, 0x10, 0x67, 0x0f, 0x2a, 0x20, 0x53, 0xfa, 0x2c, 0x39, 0xcc, 0xc6, 0x4e, 0xc7, 0xfd, 0x77, 0x92, 0xac, 0x03, 0x7a, // 55188659117513257062467267217118295137698188065244968500265048394206261417927(阶为 8)
},
.{
0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f, // p-1(阶为 2)
},
.{
0xed, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f, // p(=0,阶为 4)
},
.{
0xee, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f, // p+1(=1,阶为 1)
},
};
for (small_order_ss) |small_order_s| {
const small_p = try Edwards25519.fromBytes(small_order_s);
try std.testing.expectError(error.WeakPublicKey, small_p.mul(s));
}
}
test "point addition/subtraction" {
const io = std.testing.io;
var s1: [32]u8 = undefined;
var s2: [32]u8 = undefined;
io.random(&s1);
io.random(&s2);
const p = try Edwards25519.basePoint.clampedMul(s1);
const q = try Edwards25519.basePoint.clampedMul(s2);
const r = p.add(q).add(q).sub(q).sub(q);
try r.rejectIdentity();
try std.testing.expectError(error.IdentityElement, r.sub(p).rejectIdentity());
try std.testing.expectError(error.IdentityElement, p.sub(p).rejectIdentity());
try std.testing.expectError(error.IdentityElement, p.sub(q).add(q).sub(p).rejectIdentity());
}
test "uniform-to-point" {
var r = [32]u8{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 };
var p = Edwards25519.fromUniform(r);
try htest.assertEqual("0691eee3cf70a0056df6bfa03120635636581b5c4ea571dfc680f78c7e0b4137", p.toBytes()[0..]);
r[31] = 0xff;
p = Edwards25519.fromUniform(r);
try htest.assertEqual("f70718e68ef42d90ca1d936bb2d7e159be6c01d8095d39bd70487c82fe5c973a", p.toBytes()[0..]);
}
// 测试向量来自 draft-irtf-cfrg-hash-to-curve-12
test "hash-to-curve operation" {
var p = Edwards25519.fromString(true, "QUUX-V01-CS02-with-edwards25519_XMD:SHA-512_ELL2_RO_", "abc");
try htest.assertEqual("31558a26887f23fb8218f143e69d5f0af2e7831130bd5b432ef23883b895839a", p.toBytes()[0..]);
p = Edwards25519.fromString(false, "QUUX-V01-CS02-with-edwards25519_XMD:SHA-512_ELL2_NU_", "abc");
try htest.assertEqual("42fa27c8f5a1ae0aa38bb59d5938e5145622ba5dedd11d11736fa2f9502d7367", p.toBytes()[0..]);
}
test "implicit reduction of invalid scalars" {
const s = @as([31]u8, @splat(0)) ++ [1]u8{255};
const p1 = try Edwards25519.basePoint.mulPublic(s);
const p2 = try Edwards25519.basePoint.mul(s);
const p3 = try p1.mulPublic(s);
const p4 = try p1.mul(s);
try std.testing.expectEqualSlices(u8, p1.toBytes()[0..], p2.toBytes()[0..]);
try std.testing.expectEqualSlices(u8, p3.toBytes()[0..], p4.toBytes()[0..]);
try htest.assertEqual("339f189ecc5fbebe9895345c72dc07bda6e615f8a40e768441b6f529cd6c671a", p1.toBytes()[0..]);
try htest.assertEqual("a501e4c595a3686d8bee7058c7e6af7fd237f945c47546910e37e0e79b1bafb0", p3.toBytes()[0..]);
}
test "subgroup check" {
const io = std.testing.io;
for (0..100) |_| {
var p = Edwards25519.basePoint;
const s = Edwards25519.scalar.random(io);
p = try p.mulPublic(s);
try p.rejectUnexpectedSubgroup();
}
var bogus: [Edwards25519.encoded_length]u8 = undefined;
_ = try std.fmt.hexToBytes(&bogus, "4dc95e3c28d78c48a60531525e6327e259b7ba0d2f5c81b694052c766a14b625");
const p = try Edwards25519.fromBytes(bogus);
try std.testing.expectError(error.UnexpectedSubgroup, p.rejectUnexpectedSubgroup());
var torsion2L: [Edwards25519.encoded_length]u8 = undefined;
_ = try std.fmt.hexToBytes(&torsion2L, "9599999999999999999999999999999999999999999999999999999999999999");
const p2L = try Edwards25519.fromBytes(torsion2L);
try std.testing.expectError(error.UnexpectedSubgroup, p2L.rejectUnexpectedSubgroup());
}