跳转到内容

std.crypto.pcurves.common

标准库Zig 0.17.1官方原文
源码std/crypto/pcurves/common.zig

第 1 行

std.crypto.pcurves.common.crypto

别名

第 2 行

别名目标 std.crypto

std.crypto.pcurves.common.debug

别名

第 3 行

别名目标 std.debug

std.crypto.pcurves.common.Field

类型函数

第 19 行

域元素,内部存储于 Montgomery 域。

pub fn Field(comptime params: FieldParams) type

参数

params: FieldParams

字段

limbs: MontgomeryDomainFieldElement

std.crypto.pcurves.common.Field.add

函数

第 131 行

将域元素相加。

pub fn add(a: Fe, b: Fe) Fe

参数

a: Fe
b: Fe

std.crypto.pcurves.common.Field.cMov

函数

第 126 行

如果 c 为正,则有条件地将域元素替换为 a。

pub fn cMov(fe: *Fe, a: Fe, c: u1) void

参数

fe: *Fe
a: Fe
c: u1

std.crypto.pcurves.common.Field.dbl

函数

第 145 行

将域元素加倍。

pub fn dbl(a: Fe) Fe

参数

a: Fe

std.crypto.pcurves.common.Field.encoded_length

常量

第 39 行

编码一个元素所需的字节数。

std.crypto.pcurves.common.Field.equivalent

函数

第 115 行

如果两个域元素等价,则返回 true。

pub fn equivalent(a: Fe, b: Fe) bool

参数

a: Fe
b: Fe

std.crypto.pcurves.common.Field.Fe

别名

第 25 行

别名目标 std.crypto.pcurves.common.Field

std.crypto.pcurves.common.Field.field_bits

常量

第 33 行

表示全部元素集合所需的位数。

std.crypto.pcurves.common.Field.field_order

常量

第 30 行

域大小。

std.crypto.pcurves.common.Field.fromBytes

函数

第 72 行

解包域元素。

pub fn fromBytes(s_: [encoded_length]u8, endian: std.builtin.Endian) NonCanonicalError!Fe

参数

s_: [encoded_length]u8
endian: std.builtin.Endian

错误

NonCanonical NonCanonicalError

std.crypto.pcurves.common.Field.fromInt

函数

第 95 行

从整数创建域元素。

pub fn fromInt(comptime x: IntRepr) NonCanonicalError!Fe

参数

x: IntRepr

错误

NonCanonical NonCanonicalError

std.crypto.pcurves.common.Field.IntRepr

常量

第 92 行

元素的整数形式。

std.crypto.pcurves.common.Field.invert

函数

第 198 行

返回域元素的逆;a=0 时返回 0。

pub fn invert(a: Fe) Fe

参数

a: Fe

std.crypto.pcurves.common.Field.isOdd

函数

第 120 行

若元素为奇数,返回 true。

pub fn isOdd(fe: Fe) bool

参数

fe: Fe

std.crypto.pcurves.common.Field.isSquare

函数

第 248 行

若域元素为平方元,则返回 true。

pub fn isSquare(x2: Fe) bool

参数

x2: Fe

std.crypto.pcurves.common.Field.isZero

函数

第 108 行

若域元素为零,则返回 true。

pub fn isZero(fe: Fe) bool

参数

fe: Fe

std.crypto.pcurves.common.Field.mul

函数

第 152 行

将域元素相乘。

pub fn mul(a: Fe, b: Fe) Fe

参数

a: Fe
b: Fe

std.crypto.pcurves.common.Field.neg

函数

第 190 行

对域元素取负。

pub fn neg(a: Fe) Fe

参数

a: Fe

std.crypto.pcurves.common.Field.one

常量

第 45 行

一。

std.crypto.pcurves.common.Field.orderSwap

函数

第 65 行

交换已编码元素的字节序。

pub fn orderSwap(s: [encoded_length]u8) [encoded_length]u8

参数

std.crypto.pcurves.common.Field.pow

函数

第 176 行

计算 a^n。

pub fn pow(a: Fe, comptime T: type, comptime n: T) Fe

参数

a: Fe
T: type
n: T

std.crypto.pcurves.common.Field.rejectNonCanonical

函数

第 52 行

拒绝元素的非规范编码。

pub fn rejectNonCanonical(s_: [encoded_length]u8, endian: std.builtin.Endian) NonCanonicalError!void

参数

s_: [encoded_length]u8
endian: std.builtin.Endian

错误

NonCanonical NonCanonicalError

std.crypto.pcurves.common.Field.saturated_bits

常量

第 36 行

可在不溢出的情况下饱和的位数。

std.crypto.pcurves.common.Field.sq

函数

第 159 行

将域元素平方。

pub fn sq(a: Fe) Fe

参数

a: Fe

std.crypto.pcurves.common.Field.sqn

函数

第 166 行

将域元素平方 n 次。

fn sqn(a: Fe, comptime n: comptime_int) Fe

参数

a: Fe
n: comptime_int

std.crypto.pcurves.common.Field.sqrt

函数

第 314 行

计算 x2 的平方根;若 x2 不是平方数,返回 error.NotSquare。

pub fn sqrt(x2: Fe) NotSquareError!Fe

参数

x2: Fe

错误

NotSquare NotSquareError

std.crypto.pcurves.common.Field.sub

函数

第 138 行

减去域元素。

pub fn sub(a: Fe, b: Fe) Fe

参数

a: Fe
b: Fe

std.crypto.pcurves.common.Field.toBytes

函数

第 83 行

打包域元素。

pub fn toBytes(fe: Fe, endian: std.builtin.Endian) [encoded_length]u8

参数

fe: Fe
endian: std.builtin.Endian

std.crypto.pcurves.common.Field.toInt

函数

第 102 行

将域元素作为整数返回。

pub fn toInt(fe: Fe) IntRepr

参数

fe: Fe

std.crypto.pcurves.common.Field.uncheckedSqrt

函数

第 278 行

fn uncheckedSqrt(x2: Fe) Fe

参数

x2: Fe

std.crypto.pcurves.common.Field.zero

常量

第 42 行

零。

Fe

std.crypto.pcurves.common.FieldParams

容器

第 10 行

创建有限域类型的参数。

字段

fiat: type
field_order: comptime_int
field_bits: comptime_int
saturated_bits: comptime_int
encoded_length: comptime_int

std.crypto.pcurves.common.mem

别名

第 4 行

别名目标 std.mem

std.crypto.pcurves.common.NonCanonicalError

别名

第 6 行

别名目标 std.crypto.errors.NonCanonicalError

std.crypto.pcurves.common.NotSquareError

别名

第 7 行

别名目标 std.crypto.errors.NotSquareError

std.crypto.pcurves.common.std

别名

第 1 行

别名目标 std

源码

std/crypto/pcurves/common.zig

const std = @import("std");
const crypto = std.crypto;
const debug = std.debug;
const mem = std.mem;

const NonCanonicalError = crypto.errors.NonCanonicalError;
const NotSquareError = crypto.errors.NotSquareError;

/// 创建有限域类型的参数。
pub const FieldParams = struct {
    fiat: type,
    field_order: comptime_int,
    field_bits: comptime_int,
    saturated_bits: comptime_int,
    encoded_length: comptime_int,
};

/// 域元素,内部存储于 Montgomery 域。
pub fn Field(comptime params: FieldParams) type {
    const fiat = params.fiat;
    const MontgomeryDomainFieldElement = fiat.MontgomeryDomainFieldElement;
    const NonMontgomeryDomainFieldElement = fiat.NonMontgomeryDomainFieldElement;

    return struct {
        const Fe = @This();

        limbs: MontgomeryDomainFieldElement,

        /// 域大小。
        pub const field_order = params.field_order;

        /// 表示全部元素集合所需的位数。
        pub const field_bits = params.field_bits;

        /// 可在不溢出的情况下饱和的位数。
        pub const saturated_bits = params.saturated_bits;

        /// 编码一个元素所需的字节数。
        pub const encoded_length = params.encoded_length;

        /// 零。
        pub const zero: Fe = Fe{ .limbs = mem.zeroes(MontgomeryDomainFieldElement) };

        /// 一。
        pub const one = one: {
            var fe: Fe = undefined;
            fiat.setOne(&fe.limbs);
            break :one fe;
        };

        /// 拒绝元素的非规范编码。
        pub fn rejectNonCanonical(s_: [encoded_length]u8, endian: std.builtin.Endian) NonCanonicalError!void {
            var s = if (endian == .little) s_ else orderSwap(s_);
            const field_order_s = comptime fos: {
                var fos: [encoded_length]u8 = undefined;
                mem.writeInt(@Int(.unsigned, encoded_length * 8), &fos, field_order, .little);
                break :fos fos;
            };
            if (crypto.timing_safe.compare(u8, &s, &field_order_s, .little) != .lt) {
                return error.NonCanonical;
            }
        }

        /// 交换已编码元素的字节序。
        pub fn orderSwap(s: [encoded_length]u8) [encoded_length]u8 {
            var t = s;
            for (s, 0..) |x, i| t[t.len - 1 - i] = x;
            return t;
        }

        /// 解包域元素。
        pub fn fromBytes(s_: [encoded_length]u8, endian: std.builtin.Endian) NonCanonicalError!Fe {
            const s = if (endian == .little) s_ else orderSwap(s_);
            try rejectNonCanonical(s, .little);
            var limbs_z: NonMontgomeryDomainFieldElement = undefined;
            fiat.fromBytes(&limbs_z, s);
            var limbs: MontgomeryDomainFieldElement = undefined;
            fiat.toMontgomery(&limbs, limbs_z);
            return Fe{ .limbs = limbs };
        }

        /// 打包域元素。
        pub fn toBytes(fe: Fe, endian: std.builtin.Endian) [encoded_length]u8 {
            var limbs_z: NonMontgomeryDomainFieldElement = undefined;
            fiat.fromMontgomery(&limbs_z, fe.limbs);
            var s: [encoded_length]u8 = undefined;
            fiat.toBytes(&s, limbs_z);
            return if (endian == .little) s else orderSwap(s);
        }

        /// 元素的整数形式。
        pub const IntRepr = @Int(.unsigned, params.field_bits);

        /// 从整数创建域元素。
        pub fn fromInt(comptime x: IntRepr) NonCanonicalError!Fe {
            var s: [encoded_length]u8 = undefined;
            mem.writeInt(IntRepr, &s, x, .little);
            return fromBytes(s, .little);
        }

        /// 将域元素作为整数返回。
        pub fn toInt(fe: Fe) IntRepr {
            const s = fe.toBytes(.little);
            return mem.readInt(IntRepr, &s, .little);
        }

        /// 若域元素为零,则返回 true。
        pub fn isZero(fe: Fe) bool {
            var z: @TypeOf(fe.limbs[0]) = undefined;
            fiat.nonzero(&z, fe.limbs);
            return z == 0;
        }

        /// 如果两个域元素等价,则返回 true。
        pub fn equivalent(a: Fe, b: Fe) bool {
            return a.sub(b).isZero();
        }

        /// 若元素为奇数,返回 true。
        pub fn isOdd(fe: Fe) bool {
            const s = fe.toBytes(.little);
            return @as(u1, @truncate(s[0])) != 0;
        }

        /// 如果 `c` 为正,则有条件地将域元素替换为 `a`。
        pub fn cMov(fe: *Fe, a: Fe, c: u1) void {
            fiat.selectznz(&fe.limbs, c, fe.limbs, a.limbs);
        }

        /// 将域元素相加。
        pub fn add(a: Fe, b: Fe) Fe {
            var fe: Fe = undefined;
            fiat.add(&fe.limbs, a.limbs, b.limbs);
            return fe;
        }

        /// 减去域元素。
        pub fn sub(a: Fe, b: Fe) Fe {
            var fe: Fe = undefined;
            fiat.sub(&fe.limbs, a.limbs, b.limbs);
            return fe;
        }

        /// 将域元素加倍。
        pub fn dbl(a: Fe) Fe {
            var fe: Fe = undefined;
            fiat.add(&fe.limbs, a.limbs, a.limbs);
            return fe;
        }

        /// 将域元素相乘。
        pub fn mul(a: Fe, b: Fe) Fe {
            var fe: Fe = undefined;
            fiat.mul(&fe.limbs, a.limbs, b.limbs);
            return fe;
        }

        /// 将域元素平方。
        pub fn sq(a: Fe) Fe {
            var fe: Fe = undefined;
            fiat.square(&fe.limbs, a.limbs);
            return fe;
        }

        /// 将域元素平方 n 次。
        fn sqn(a: Fe, comptime n: comptime_int) Fe {
            var i: usize = 0;
            var fe = a;
            while (i < n) : (i += 1) {
                fe = fe.sq();
            }
            return fe;
        }

        /// 计算 a^n。
        pub fn pow(a: Fe, comptime T: type, comptime n: T) Fe {
            var fe = one;
            var x: T = n;
            var t = a;
            while (true) {
                if (@as(u1, @truncate(x)) != 0) fe = fe.mul(t);
                x >>= 1;
                if (x == 0) break;
                t = t.sq();
            }
            return fe;
        }

        /// 对域元素取负。
        pub fn neg(a: Fe) Fe {
            var fe: Fe = undefined;
            fiat.opp(&fe.limbs, a.limbs);
            return fe;
        }

        /// 返回域元素的逆;a=0 时返回 0。
        // 域求逆算法来自 https://eprint.iacr.org/2021/549.pdf
        pub fn invert(a: Fe) Fe {
            const iterations = (49 * field_bits + if (field_bits < 46) 80 else 57) / 17;
            const Limbs = @TypeOf(a.limbs);
            const Word = @TypeOf(a.limbs[0]);
            const XLimbs = [a.limbs.len + 1]Word;

            var d: Word = 1;
            var f = comptime blk: {
                var f: XLimbs = undefined;
                fiat.msat(&f);
                break :blk f;
            };
            var g: XLimbs = undefined;
            fiat.fromMontgomery(g[0..a.limbs.len], a.limbs);
            g[g.len - 1] = 0;

            var r = Fe.one.limbs;
            var v = Fe.zero.limbs;

            var out1: Word = undefined;
            var out2: XLimbs = undefined;
            var out3: XLimbs = undefined;
            var out4: Limbs = undefined;
            var out5: Limbs = undefined;

            var i: usize = 0;
            while (i < iterations - iterations % 2) : (i += 2) {
                fiat.divstep(&out1, &out2, &out3, &out4, &out5, d, f, g, v, r);
                fiat.divstep(&d, &f, &g, &v, &r, out1, out2, out3, out4, out5);
            }
            if (iterations % 2 != 0) {
                fiat.divstep(&out1, &out2, &out3, &out4, &out5, d, f, g, v, r);
                v = out4;
                f = out2;
            }
            var v_opp: Limbs = undefined;
            fiat.opp(&v_opp, v);
            fiat.selectznz(&v, @as(u1, @truncate(f[f.len - 1] >> (@bitSizeOf(Word) - 1))), v, v_opp);

            const precomp = blk: {
                var precomp: Limbs = undefined;
                fiat.divstepPrecomp(&precomp);
                break :blk precomp;
            };
            var fe: Fe = undefined;
            fiat.mul(&fe.limbs, v, precomp);
            return fe;
        }

        /// 若域元素为平方元,则返回 true。
        pub fn isSquare(x2: Fe) bool {
            if (field_order == 115792089210356248762697446949407573530086143415290314195533631308867097853951) {
                const t110 = x2.mul(x2.sq()).sq();
                const t111 = x2.mul(t110);
                const t111111 = t111.mul(x2.mul(t110).sqn(3));
                const x15 = t111111.sqn(6).mul(t111111).sqn(3).mul(t111);
                const x16 = x15.sq().mul(x2);
                const x53 = x16.sqn(16).mul(x16).sqn(15);
                const x47 = x15.mul(x53);
                const ls = x47.mul(((x53.sqn(17).mul(x2)).sqn(143).mul(x47)).sqn(47)).sq().mul(x2);
                return ls.equivalent(Fe.one);
            } else if (field_order == 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319) {
                const t111 = x2.mul(x2.mul(x2.sq()).sq());
                const t111111 = t111.mul(t111.sqn(3));
                const t1111110 = t111111.sq();
                const t1111111 = x2.mul(t1111110);
                const x12 = t1111110.sqn(5).mul(t111111);
                const x31 = x12.sqn(12).mul(x12).sqn(7).mul(t1111111);
                const x32 = x31.sq().mul(x2);
                const x63 = x32.sqn(31).mul(x31);
                const x126 = x63.sqn(63).mul(x63);
                const ls = x126.sqn(126).mul(x126).sqn(3).mul(t111).sqn(33).mul(x32).sqn(95).mul(x31);
                return ls.equivalent(Fe.one);
            } else {
                const ls = x2.pow(@Int(.unsigned, field_bits), (field_order - 1) / 2); // 勒让德符号
                return ls.equivalent(Fe.one);
            }
        }

        // x=x2^((field_order+1)/4),其中 field_order=3 (mod 4)。
        fn uncheckedSqrt(x2: Fe) Fe {
            if (field_order % 4 != 3) @compileError("unimplemented");
            if (field_order == 115792089210356248762697446949407573530086143415290314195533631308867097853951) {
                const t11 = x2.mul(x2.sq());
                const t1111 = t11.mul(t11.sqn(2));
                const t11111111 = t1111.mul(t1111.sqn(4));
                const x16 = t11111111.sqn(8).mul(t11111111);
                return x16.sqn(16).mul(x16).sqn(32).mul(x2).sqn(96).mul(x2).sqn(94);
            } else if (field_order == 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319) {
                const t111 = x2.mul(x2.mul(x2.sq()).sq());
                const t111111 = t111.mul(t111.sqn(3));
                const t1111110 = t111111.sq();
                const t1111111 = x2.mul(t1111110);
                const x12 = t1111110.sqn(5).mul(t111111);
                const x31 = x12.sqn(12).mul(x12).sqn(7).mul(t1111111);
                const x32 = x31.sq().mul(x2);
                const x63 = x32.sqn(31).mul(x31);
                const x126 = x63.sqn(63).mul(x63);
                return x126.sqn(126).mul(x126).sqn(3).mul(t111).sqn(33).mul(x32).sqn(64).mul(x2).sqn(30);
            } else if (field_order == 115792089237316195423570985008687907853269984665640564039457584007908834671663) {
                const t11 = x2.mul(x2.sq());
                const t1111 = t11.mul(t11.sqn(2));
                const t11111 = x2.mul(t1111.sq());
                const t1111111 = t11.mul(t11111.sqn(2));
                const x11 = t1111111.sqn(4).mul(t1111);
                const x22 = x11.sqn(11).mul(x11);
                const x27 = x22.sqn(5).mul(t11111);
                const x54 = x27.sqn(27).mul(x27);
                const x108 = x54.sqn(54).mul(x54);
                return x108.sqn(108).mul(x108).sqn(7).mul(t1111111).sqn(23).mul(x22).sqn(6).mul(t11).sqn(2);
            } else {
                return x2.pow(@Int(.unsigned, field_bits), (field_order + 1) / 4);
            }
        }

        /// 计算 `x2` 的平方根;若 `x2` 不是平方数,返回 `error.NotSquare`。
        pub fn sqrt(x2: Fe) NotSquareError!Fe {
            const x = x2.uncheckedSqrt();
            if (x.sq().equivalent(x2)) {
                return x;
            }
            return error.NotSquare;
        }
    };
}