Skip to content

std.crypto.25519.edwards25519

Standard libraryZig 0.17.1Official documentation
Sourcestd/crypto/25519/edwards25519.zig

Source line 1

std.crypto.25519.edwards25519.crypto

alias

Source line 2

Alias of std.crypto

std.crypto.25519.edwards25519.debug

alias

Source line 3

Alias of std.debug

std.crypto.25519.edwards25519.Edwards25519

container

Source line 15

Group operations over Edwards25519.

Fields

x: Fe
y: Fe
z: Fe
t: Fe
is_base: bool = false

std.crypto.25519.edwards25519.Edwards25519.add

function

Source line 164

Add two Edwards25519 points.

pub fn add(p: Edwards25519, q: Edwards25519) Edwards25519

Parameters

std.crypto.25519.edwards25519.Edwards25519.basePoint

constant

Source line 68

The edwards25519 base point.

std.crypto.25519.edwards25519.Edwards25519.basePointPc

constant

Source line 284

std.crypto.25519.edwards25519.Edwards25519.clampedMul

function

Source line 395

Multiply an Edwards25519 point by a scalar after "clamping" it. Clamping forces the scalar to be a multiple of the cofactor in order to prevent small subgroups attacks. This is strongly recommended for DH operations. Return error.WeakPublicKey if the resulting point is the identity element.

pub fn clampedMul(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519

Parameters

p: Edwards25519
s: [32]u8

std.crypto.25519.edwards25519.Edwards25519.clearCofactor

function

Source line 126

Multiply a point by the cofactor

pub fn clearCofactor(p: Edwards25519) Edwards25519

Parameters

std.crypto.25519.edwards25519.Edwards25519.cMov

function

Source line 194

fn cMov(p: *Edwards25519, a: Edwards25519, c: u64) void

Parameters

p: *Edwards25519
a: Edwards25519
c: u64

std.crypto.25519.edwards25519.Edwards25519.dbl

function

Source line 147

Double an Edwards25519 point.

pub fn dbl(p: Edwards25519) Edwards25519

Parameters

std.crypto.25519.edwards25519.Edwards25519.elligator2

type-function

Source line 431

Elligator2 map - Returns Montgomery affine coordinates

pub fn elligator2(r: Fe) struct { x: Fe, y: Fe, not_square: bool }

Parameters

r: Fe

std.crypto.25519.edwards25519.Edwards25519.encoded_length

constant

Source line 21

Length in bytes of a compressed representation of a point.

usize

std.crypto.25519.edwards25519.Edwards25519.Fe

alias

Source line 17

The underlying prime field.

Alias of std.crypto.25519.field.Fe

std.crypto.25519.edwards25519.Edwards25519.fromBytes

function

Source line 31

Decode an Edwards25519 point from its compressed (Y+sign) coordinates.

pub fn fromBytes(s: [encoded_length]u8) EncodingError!Edwards25519

Parameters

Errors

InvalidEncoding EncodingError

std.crypto.25519.edwards25519.Edwards25519.fromHash

function

Source line 453

Map a 64-bit hash into an Edwards25519 point

pub fn fromHash(h: [64]u8) Edwards25519

Parameters

h: [64]u8

std.crypto.25519.edwards25519.Edwards25519.fromString

function

Source line 520

Hash a context ctx and a string s into an Edwards25519 point

This function implements the edwards25519_XMD:SHA-512_ELL2_RO_ and edwards25519_XMD:SHA-512_ELL2_NU_ methods from the "Hashing to Elliptic Curves" standard document.

Although not strictly required by the standard, it is recommended to avoid NUL characters in the context in order to be compatible with other implementations.

pub fn fromString(comptime random_oracle: bool, ctx: []const u8, s: []const u8) Edwards25519

Parameters

random_oracle: bool
ctx: []const u8
s: []const u8

std.crypto.25519.edwards25519.Edwards25519.fromUniform

function

Source line 530

Map a 32 bit uniform bit string into an edwards25519 point

pub fn fromUniform(r: [32]u8) Edwards25519

Parameters

r: [32]u8

std.crypto.25519.edwards25519.Edwards25519.identityElement

constant

Source line 76

std.crypto.25519.edwards25519.Edwards25519.montToEd

function

Source line 410

fn montToEd(x: Fe, y: Fe) Edwards25519

Parameters

x: Fe
y: Fe

std.crypto.25519.edwards25519.Edwards25519.mul

function

Source line 292

Multiply an Edwards25519 point by a scalar without clamping it. Return error.WeakPublicKey if the base generates a small-order group, and error.IdentityElement if the result is the identity element.

pub fn mul(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519

Parameters

p: Edwards25519
s: [32]u8

std.crypto.25519.edwards25519.Edwards25519.mulDoubleBasePublic

function

Source line 315

Double-base multiplication of public parameters - Compute (p1s1)+(p2s2) IN VARIABLE TIME This can be used for signature verification.

pub fn mulDoubleBasePublic(p1: Edwards25519, s1: [32]u8, p2: Edwards25519, s2: [32]u8) WeakPublicKeyError!Edwards25519

Parameters

p1: Edwards25519
s1: [32]u8
p2: Edwards25519
s2: [32]u8

Errors

WeakPublicKey WeakPublicKeyError

std.crypto.25519.edwards25519.Edwards25519.mulMulti

function

Source line 353

Multiscalar multiplication IN VARIABLE TIME for public data Computes ps0ss0 + ps1ss1 + ps2*ss2... faster than doing many of these operations individually

pub fn mulMulti(comptime count: usize, ps: [count]Edwards25519, ss: [count][32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519

Parameters

count: usize
ps: [count]Edwards25519
ss: [count][32]u8

std.crypto.25519.edwards25519.Edwards25519.mulPublic

function

Source line 303

Multiply an Edwards25519 point by a PUBLIC scalar IN VARIABLE TIME This can be used for signature verification.

pub fn mulPublic(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519

Parameters

p: Edwards25519
s: [32]u8

std.crypto.25519.edwards25519.Edwards25519.neg

function

Source line 142

Flip the sign of the X coordinate.

pub fn neg(p: Edwards25519) Edwards25519

Parameters

std.crypto.25519.edwards25519.Edwards25519.pcMul

function

Source line 234

fn pcMul(pc: *const [9]Edwards25519, s: [32]u8, comptime vartime: bool) IdentityElementError!Edwards25519

Parameters

pc: *const [9]Edwards25519
s: [32]u8
vartime: bool

Errors

IdentityElement IdentityElementError

std.crypto.25519.edwards25519.Edwards25519.pcMul16

function

Source line 254

fn pcMul16(pc: *const [16]Edwards25519, s: [32]u8, comptime vartime: bool) IdentityElementError!Edwards25519

Parameters

pc: *const [16]Edwards25519
s: [32]u8
vartime: bool

Errors

IdentityElement IdentityElementError

std.crypto.25519.edwards25519.Edwards25519.pcSelect

function

Source line 201

fn pcSelect(comptime n: usize, pc: *const [n]Edwards25519, b: u8) Edwards25519

Parameters

n: usize
pc: *const [n]Edwards25519
b: u8

std.crypto.25519.edwards25519.Edwards25519.precompute

function

Source line 273

fn precompute(p: Edwards25519, comptime count: usize) [1 + count]Edwards25519

Parameters

p: Edwards25519
count: usize

std.crypto.25519.edwards25519.Edwards25519.rejectIdentity

function

Source line 79

Reject the neutral element.

pub fn rejectIdentity(p: Edwards25519) IdentityElementError!void

Parameters

Errors

IdentityElement IdentityElementError

std.crypto.25519.edwards25519.Edwards25519.rejectLowOrder

function

Source line 132

Check that the point does not generate a low-order group. Return a WeakPublicKey error if it does.

pub fn rejectLowOrder(p: Edwards25519) WeakPublicKeyError!void

Parameters

Errors

WeakPublicKey WeakPublicKeyError

std.crypto.25519.edwards25519.Edwards25519.rejectNonCanonical

function

Source line 63

Check that the encoding of a point is canonical.

pub fn rejectNonCanonical(s: [32]u8) NonCanonicalError!void

Parameters

s: [32]u8

Errors

NonCanonical NonCanonicalError

std.crypto.25519.edwards25519.Edwards25519.rejectUnexpectedSubgroup

function

Source line 91

Reject a point if it is not in the prime order subgroup generated by the standard base point.

If the point is not in the main subgroup:

  • WeakPublicKeyError is returned if the point belongs to a low-order subgroup.
  • UnexpectedSubgroupError is returned otherwise.
pub fn rejectUnexpectedSubgroup(p: Edwards25519) (WeakPublicKeyError || UnexpectedSubgroupError)!void

Parameters

std.crypto.25519.edwards25519.Edwards25519.scalar

alias

Source line 19

Field arithmetic mod the order of the main subgroup.

Alias of std.crypto.25519.scalar

std.crypto.25519.edwards25519.Edwards25519.shift

function

Source line 188

Double a point n times.

fn shift(p: Edwards25519, n: comptime_int) Edwards25519

Parameters

p: Edwards25519
n: comptime_int

std.crypto.25519.edwards25519.Edwards25519.slide

function

Source line 210

fn slide(s: [32]u8) [2 * 32]i8

Parameters

s: [32]u8

std.crypto.25519.edwards25519.Edwards25519.stringToPoints

function

Source line 463

fn stringToPoints(comptime n: usize, ctx: []const u8, s: []const u8) [n]Edwards25519

Parameters

n: usize
ctx: []const u8
s: []const u8

std.crypto.25519.edwards25519.Edwards25519.sub

function

Source line 183

Subtract two Edwards25519 points.

pub fn sub(p: Edwards25519, q: Edwards25519) Edwards25519

Parameters

std.crypto.25519.edwards25519.Edwards25519.toBytes

function

Source line 55

Encode an Edwards25519 point.

pub fn toBytes(p: Edwards25519) [encoded_length]u8

Parameters

std.crypto.25519.edwards25519.Edwards25519.xmontToYmont

function

Source line 402

fn xmontToYmont(x: Fe) NotSquareError!Fe

Parameters

x: Fe

Errors

NotSquare NotSquareError

std.crypto.25519.edwards25519.EncodingError

alias

Source line 7

Alias of std.crypto.errors.EncodingError

std.crypto.25519.edwards25519.fmt

alias

Source line 4

Alias of std.fmt

std.crypto.25519.edwards25519.htest

constant

Source line 542

std.crypto.25519.edwards25519.IdentityElementError

alias

Source line 8

Alias of std.crypto.errors.IdentityElementError

std.crypto.25519.edwards25519.mem

alias

Source line 5

Alias of std.mem

std.crypto.25519.edwards25519.NonCanonicalError

alias

Source line 9

Alias of std.crypto.errors.NonCanonicalError

std.crypto.25519.edwards25519.NotSquareError

alias

Source line 10

Alias of std.crypto.errors.NotSquareError

std.crypto.25519.edwards25519.std

alias

Source line 1

Alias of std

std.crypto.25519.edwards25519.UnexpectedSubgroupError

alias

Source line 12

Alias of std.crypto.errors.UnexpectedSubgroupError

std.crypto.25519.edwards25519.WeakPublicKeyError

alias

Source line 11

Alias of std.crypto.errors.WeakPublicKeyError

Source code

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;

/// Group operations over Edwards25519.
pub const Edwards25519 = struct {
    /// The underlying prime field.
    pub const Fe = @import("field.zig").Fe;
    /// Field arithmetic mod the order of the main subgroup.
    pub const scalar = @import("scalar.zig");
    /// Length in bytes of a compressed representation of a point.
    pub const encoded_length: usize = 32;

    x: Fe,
    y: Fe,
    z: Fe,
    t: Fe,

    is_base: bool = false,

    /// Decode an Edwards25519 point from its compressed (Y+sign) coordinates.
    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) { // best-effort to avoid two conditional branches
            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 };
    }

    /// Encode an Edwards25519 point.
    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;
    }

    /// Check that the encoding of a point is canonical.
    pub fn rejectNonCanonical(s: [32]u8) NonCanonicalError!void {
        return Fe.rejectNonCanonical(s, true);
    }

    /// The edwards25519 base point.
    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 };

    /// Reject the neutral element.
    pub fn rejectIdentity(p: Edwards25519) IdentityElementError!void {
        if (p.x.isZero()) {
            return error.IdentityElement;
        }
    }

    /// Reject a point if it is not in the prime order subgroup generated by the standard base point.
    ///
    /// If the point is not in the main subgroup:
    ///
    /// - `WeakPublicKeyError` is returned if the point belongs to a low-order subgroup.
    /// - `UnexpectedSubgroupError` is returned otherwise.
    pub fn rejectUnexpectedSubgroup(p: Edwards25519) (WeakPublicKeyError || UnexpectedSubgroupError)!void {
        try p.rejectLowOrder();

        // Multiply p by the order of subgroup - This is a prime order group, so the result should be the neutral element.
        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;
    }

    /// Multiply a point by the cofactor
    pub fn clearCofactor(p: Edwards25519) Edwards25519 {
        return p.dbl().dbl().dbl();
    }

    /// Check that the point does not generate a low-order group.
    /// Return a `WeakPublicKey` error if it does.
    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;
        }
    }

    /// Flip the sign of the X coordinate.
    pub fn neg(p: Edwards25519) Edwards25519 {
        return .{ .x = p.x.neg(), .y = p.y, .z = p.z, .t = p.t.neg() };
    }

    /// Double an Edwards25519 point.
    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),
        };
    }

    /// Add two Edwards25519 points.
    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),
        };
    }

    /// Subtract two Edwards25519 points.
    pub fn sub(p: Edwards25519, q: Edwards25519) Edwards25519 {
        return p.add(q.neg());
    }

    /// Double a point `n` times.
    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)));
        }
        // Now, e[0..63] is between 0 and 15, e[63] is between 0 and 7
        var carry: i8 = 0;
        for (e[0..63]) |*x| {
            x.* += carry;
            carry = (x.* + 8) >> 4;
            x.* -= carry * 16;
        }
        e[63] += carry;
        // Now, e[*] is between -8 and 8, including e[63]
        return e;
    }

    // Scalar multiplication with a 4-bit window and the first 8 multiples.
    // This requires the scalar to be converted to non-adjacent form.
    // Based on real-world benchmarks, we only use this for multi-scalar multiplication.
    // NAF could be useful to half the size of precomputation tables, but we intentionally
    // avoid these to keep the standard library lightweight.
    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;
    }

    // Scalar multiplication with a 4-bit window and the first 15 multiples.
    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);
    };

    /// Multiply an Edwards25519 point by a scalar without clamping it.
    /// Return error.WeakPublicKey if the base generates a small-order group,
    /// and error.IdentityElement if the result is the identity element.
    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);
    }

    /// Multiply an Edwards25519 point by a *PUBLIC* scalar *IN VARIABLE TIME*
    /// This can be used for signature verification.
    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);
        }
    }

    /// Double-base multiplication of public parameters - Compute (p1*s1)+(p2*s2) *IN VARIABLE TIME*
    /// This can be used for signature verification.
    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;
    }

    /// Multiscalar multiplication *IN VARIABLE TIME* for public data
    /// Computes ps0*ss0 + ps1*ss1 + ps2*ss2... faster than doing many of these operations individually
    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;
    }

    /// Multiply an Edwards25519 point by a scalar after "clamping" it.
    /// Clamping forces the scalar to be a multiple of the cofactor in
    /// order to prevent small subgroups attacks.
    /// This is strongly recommended for DH operations.
    /// Return error.WeakPublicKey if the resulting point is
    /// the identity element.
    pub fn clampedMul(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
        var t: [32]u8 = s;
        scalar.clamp(&t);
        return mul(p, t);
    }

    // montgomery -- recover 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 affine coordinates to edwards extended coordinates
    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) or 1 if the denominator is 0
        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 map - Returns Montgomery affine coordinates
    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 not a square => x = -x1-A
        x.cMov(x.neg(), @intFromBool(not_square));
        x2 = Fe.zero;
        x2.cMov(Fe.edwards25519a, @intFromBool(not_square));
        x = x.sub(x2);

        // We have y = sqrt(gx1) or sqrt(gx2) with gx2 = gx1*(A+x1)/(-x1)
        // but it is about as fast to just recompute y from the curve equation.
        const y = xmontToYmont(x) catch unreachable;
        return .{ .x = x, .y = y, .not_square = not_square };
    }

    /// Map a 64-bit hash into an Edwards25519 point
    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;
    }

    /// Hash a context `ctx` and a string `s` into an Edwards25519 point
    ///
    /// This function implements the edwards25519_XMD:SHA-512_ELL2_RO_ and edwards25519_XMD:SHA-512_ELL2_NU_
    /// methods from the "Hashing to Elliptic Curves" standard document.
    ///
    /// Although not strictly required by the standard, it is recommended to avoid NUL characters in
    /// the context in order to be compatible with other implementations.
    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];
        }
    }

    /// Map a 32 bit uniform bit string into an edwards25519 point
    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 (order 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 (order 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(order 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 (order 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 (order 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, order 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, order 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..]);
}

// Test vectors from 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());
}