Commit 8e79b3cf23
Changed files (3)
lib
std
crypto
lib/std/crypto/25519/ed25519.zig
@@ -97,6 +97,7 @@ pub const Ed25519 = struct {
try Curve.rejectNonCanonical(public_key);
const a = try Curve.fromBytes(public_key);
try a.rejectIdentity();
+ try Curve.rejectNonCanonical(r.*);
const expected_r = try Curve.fromBytes(r.*);
var h = Sha512.init(.{});
@@ -113,6 +114,78 @@ pub const Ed25519 = struct {
return error.InvalidSignature;
} else |_| {}
}
+
+ /// A (signature, message, public_key) tuple for batch verification
+ pub const BatchElement = struct {
+ sig: [signature_length]u8,
+ msg: []const u8,
+ public_key: [public_length]u8,
+ };
+
+ /// Verify several signatures in a single operation, much faster than verifying signatures one-by-one
+ pub fn verifyBatch(comptime count: usize, signature_batch: [count]BatchElement) !void {
+ var r_batch: [count][32]u8 = undefined;
+ var s_batch: [count][32]u8 = undefined;
+ var a_batch: [count]Curve = undefined;
+ var expected_r_batch: [count]Curve = undefined;
+
+ for (signature_batch) |signature, i| {
+ const r = signature.sig[0..32];
+ const s = signature.sig[32..64];
+ try Curve.scalar.rejectNonCanonical(s.*);
+ try Curve.rejectNonCanonical(signature.public_key);
+ const a = try Curve.fromBytes(signature.public_key);
+ try a.rejectIdentity();
+ try Curve.rejectNonCanonical(r.*);
+ const expected_r = try Curve.fromBytes(r.*);
+ expected_r_batch[i] = expected_r;
+ r_batch[i] = r.*;
+ s_batch[i] = s.*;
+ a_batch[i] = a;
+ }
+
+ var hram_batch: [count]Curve.scalar.Scalar = undefined;
+ for (signature_batch) |signature, i| {
+ var h = Sha512.init(.{});
+ h.update(&r_batch[i]);
+ h.update(&signature.public_key);
+ h.update(signature.msg);
+ var hram64: [Sha512.digest_length]u8 = undefined;
+ h.final(&hram64);
+ hram_batch[i] = Curve.scalar.reduce64(hram64);
+ }
+
+ var z_batch: [count]Curve.scalar.Scalar = undefined;
+ for (z_batch) |*z| {
+ try std.crypto.randomBytes(z[0..16]);
+ mem.set(u8, z[16..], 0);
+ }
+
+ var zs_sum = Curve.scalar.zero;
+ for (z_batch) |z, i| {
+ const zs = Curve.scalar.mul(z, s_batch[i]);
+ zs_sum = Curve.scalar.add(zs_sum, zs);
+ }
+ zs_sum = Curve.scalar.mul8(zs_sum);
+
+ var zr = Curve.neutralElement;
+ for (z_batch) |z, i| {
+ zr = zr.add(try expected_r_batch[i].mul(z));
+ }
+ zr = zr.clearCofactor();
+
+ var zah = Curve.neutralElement;
+ for (z_batch) |z, i| {
+ const zh = Curve.scalar.mul(z, hram_batch[i]);
+ zah = zah.add(try a_batch[i].mul(zh));
+ }
+ zah = zah.clearCofactor();
+
+ const zsb = try Curve.basePoint.mul(zs_sum);
+ if (zr.add(zah).sub(zsb).rejectIdentity()) |_| {
+ return error.InvalidSignature;
+ } else |_| {}
+ }
};
test "ed25519 key pair creation" {
@@ -138,3 +211,132 @@ test "ed25519 signature" {
try Ed25519.verify(sig, "test", public_key);
std.testing.expectError(error.InvalidSignature, Ed25519.verify(sig, "TEST", public_key));
}
+
+test "ed25519 batch verification" {
+ var i: usize = 0;
+ while (i < 100) : (i += 1) {
+ var seed: [32]u8 = undefined;
+ try std.crypto.randomBytes(&seed);
+ const key_pair = try Ed25519.createKeyPair(seed);
+ var msg1: [32]u8 = undefined;
+ var msg2: [32]u8 = undefined;
+ try std.crypto.randomBytes(&msg1);
+ try std.crypto.randomBytes(&msg2);
+ const sig1 = try Ed25519.sign(&msg1, key_pair, null);
+ const sig2 = try Ed25519.sign(&msg2, key_pair, null);
+ const public_key = Ed25519.publicKey(key_pair);
+ var signature_batch = [_]Ed25519.BatchElement{
+ Ed25519.BatchElement{
+ .sig = sig1,
+ .msg = &msg1,
+ .public_key = public_key,
+ },
+ Ed25519.BatchElement{
+ .sig = sig2,
+ .msg = &msg2,
+ .public_key = public_key,
+ },
+ };
+ try Ed25519.verifyBatch(2, signature_batch);
+
+ signature_batch[1].sig = sig1;
+ std.testing.expectError(error.InvalidSignature, Ed25519.verifyBatch(signature_batch.len, signature_batch));
+ }
+}
+
+test "ed25519 test vectors" {
+ const Vec = struct {
+ msg_hex: *const [64:0]u8,
+ public_key_hex: *const [64:0]u8,
+ sig_hex: *const [128:0]u8,
+ expected: ?anyerror,
+ };
+
+ const entries = [_]Vec{
+ Vec{
+ .msg_hex = "8c93255d71dcab10e8f379c26200f3c7bd5f09d9bc3068d3ef4edeb4853022b6",
+ .public_key_hex = "c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa",
+ .sig_hex = "c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a0000000000000000000000000000000000000000000000000000000000000000",
+ .expected = error.WeakPublicKey, // 0
+ },
+ Vec{
+ .msg_hex = "9bd9f44f4dcc75bd531b56b2cd280b0bb38fc1cd6d1230e14861d861de092e79",
+ .public_key_hex = "c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa",
+ .sig_hex = "f7badec5b8abeaf699583992219b7b223f1df3fbbea919844e3f7c554a43dd43a5bb704786be79fc476f91d3f3f89b03984d8068dcf1bb7dfc6637b45450ac04",
+ .expected = error.WeakPublicKey, // 1
+ },
+ Vec{
+ .msg_hex = "aebf3f2601a0c8c5d39cc7d8911642f740b78168218da8471772b35f9d35b9ab",
+ .public_key_hex = "f7badec5b8abeaf699583992219b7b223f1df3fbbea919844e3f7c554a43dd43",
+ .sig_hex = "c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa8c4bd45aecaca5b24fb97bc10ac27ac8751a7dfe1baff8b953ec9f5833ca260e",
+ .expected = null, // 2 - small order R is acceptable
+ },
+ Vec{
+ .msg_hex = "9bd9f44f4dcc75bd531b56b2cd280b0bb38fc1cd6d1230e14861d861de092e79",
+ .public_key_hex = "cdb267ce40c5cd45306fa5d2f29731459387dbf9eb933b7bd5aed9a765b88d4d",
+ .sig_hex = "9046a64750444938de19f227bb80485e92b83fdb4b6506c160484c016cc1852f87909e14428a7a1d62e9f22f3d3ad7802db02eb2e688b6c52fcd6648a98bd009",
+ .expected = null, // 3 - mixed orders
+ },
+ Vec{
+ .msg_hex = "e47d62c63f830dc7a6851a0b1f33ae4bb2f507fb6cffec4011eaccd55b53f56c",
+ .public_key_hex = "cdb267ce40c5cd45306fa5d2f29731459387dbf9eb933b7bd5aed9a765b88d4d",
+ .sig_hex = "160a1cb0dc9c0258cd0a7d23e94d8fa878bcb1925f2c64246b2dee1796bed5125ec6bc982a269b723e0668e540911a9a6a58921d6925e434ab10aa7940551a09",
+ .expected = null, // 4 - cofactored verification
+ },
+ Vec{
+ .msg_hex = "e47d62c63f830dc7a6851a0b1f33ae4bb2f507fb6cffec4011eaccd55b53f56c",
+ .public_key_hex = "cdb267ce40c5cd45306fa5d2f29731459387dbf9eb933b7bd5aed9a765b88d4d",
+ .sig_hex = "21122a84e0b5fca4052f5b1235c80a537878b38f3142356b2c2384ebad4668b7e40bc836dac0f71076f9abe3a53f9c03c1ceeeddb658d0030494ace586687405",
+ .expected = null, // 5 - cofactored verification
+ },
+ Vec{
+ .msg_hex = "85e241a07d148b41e47d62c63f830dc7a6851a0b1f33ae4bb2f507fb6cffec40",
+ .public_key_hex = "442aad9f089ad9e14647b1ef9099a1ff4798d78589e66f28eca69c11f582a623",
+ .sig_hex = "e96f66be976d82e60150baecff9906684aebb1ef181f67a7189ac78ea23b6c0e547f7690a0e2ddcd04d87dbc3490dc19b3b3052f7ff0538cb68afb369ba3a514",
+ .expected = error.NonCanonical, // 6 - S > L
+ },
+ Vec{
+ .msg_hex = "85e241a07d148b41e47d62c63f830dc7a6851a0b1f33ae4bb2f507fb6cffec40",
+ .public_key_hex = "442aad9f089ad9e14647b1ef9099a1ff4798d78589e66f28eca69c11f582a623",
+ .sig_hex = "8ce5b96c8f26d0ab6c47958c9e68b937104cd36e13c33566acd2fe8d38aa19427e71f98a4734e74f2f13f06f97c20d58cc3f54b8bd0d272f42b695dd7e89a8c2",
+ .expected = error.NonCanonical, // 7 - S >> L
+ },
+ Vec{
+ .msg_hex = "9bedc267423725d473888631ebf45988bad3db83851ee85c85e241a07d148b41",
+ .public_key_hex = "f7badec5b8abeaf699583992219b7b223f1df3fbbea919844e3f7c554a43dd43",
+ .sig_hex = "ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff03be9678ac102edcd92b0210bb34d7428d12ffc5df5f37e359941266a4e35f0f",
+ .expected = error.InvalidSignature, // 8 - non-canonical R
+ },
+ Vec{
+ .msg_hex = "9bedc267423725d473888631ebf45988bad3db83851ee85c85e241a07d148b41",
+ .public_key_hex = "f7badec5b8abeaf699583992219b7b223f1df3fbbea919844e3f7c554a43dd43",
+ .sig_hex = "ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffca8c5b64cd208982aa38d4936621a4775aa233aa0505711d8fdcfdaa943d4908",
+ .expected = null, // 9 - non-canonical R
+ },
+ Vec{
+ .msg_hex = "e96b7021eb39c1a163b6da4e3093dcd3f21387da4cc4572be588fafae23c155b",
+ .public_key_hex = "ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
+ .sig_hex = "a9d55260f765261eb9b84e106f665e00b867287a761990d7135963ee0a7d59dca5bb704786be79fc476f91d3f3f89b03984d8068dcf1bb7dfc6637b45450ac04",
+ .expected = error.IdentityElement, // 10 - small-order A
+ },
+ Vec{
+ .msg_hex = "39a591f5321bbe07fd5a23dc2f39d025d74526615746727ceefd6e82ae65c06f",
+ .public_key_hex = "ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
+ .sig_hex = "a9d55260f765261eb9b84e106f665e00b867287a761990d7135963ee0a7d59dca5bb704786be79fc476f91d3f3f89b03984d8068dcf1bb7dfc6637b45450ac04",
+ .expected = error.IdentityElement, // 11 - small-order A
+ },
+ };
+ for (entries) |entry, i| {
+ var msg: [entry.msg_hex.len / 2]u8 = undefined;
+ try fmt.hexToBytes(&msg, entry.msg_hex);
+ var public_key: [32]u8 = undefined;
+ try fmt.hexToBytes(&public_key, entry.public_key_hex);
+ var sig: [64]u8 = undefined;
+ try fmt.hexToBytes(&sig, entry.sig_hex);
+ if (entry.expected) |error_type| {
+ std.testing.expectError(error_type, Ed25519.verify(sig, &msg, public_key));
+ } else {
+ try Ed25519.verify(sig, &msg, public_key);
+ }
+ }
+}
lib/std/crypto/25519/edwards25519.zig
@@ -64,6 +64,15 @@ pub const Edwards25519 = struct {
.is_base = true,
};
+ /// The edwards25519 neutral element.
+ pub const neutralElement = Edwards25519{
+ .x = Fe{ .limbs = .{ 2251799813685229, 2251799813685247, 2251799813685247, 2251799813685247, 2251799813685247 } },
+ .y = Fe{ .limbs = .{ 1507481815385608, 2223447444246085, 1083941587175919, 2059929906842505, 1581435440146976 } },
+ .z = Fe{ .limbs = .{ 1507481815385608, 2223447444246085, 1083941587175919, 2059929906842505, 1581435440146976 } },
+ .t = Fe{ .limbs = .{ 2251799813685229, 2251799813685247, 2251799813685247, 2251799813685247, 2251799813685247 } },
+ .is_base = false,
+ };
+
const identityElement = Edwards25519{ .x = Fe.zero, .y = Fe.one, .z = Fe.one, .t = Fe.zero };
/// Reject the neutral element.
lib/std/crypto/25519/scalar.zig
@@ -6,10 +6,18 @@
const std = @import("std");
const mem = std.mem;
-const field_size = [32]u8{
+/// A 32-byte representation of a scalar in 0 .. 2^252 + 27742317777372353535851937790883648493
+pub const Scalar = [32]u8;
+
+/// 2^252 + 27742317777372353535851937790883648493
+pub const field_size = [32]u8{
0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, // 2^252+27742317777372353535851937790883648493
};
+/// Zero
+pub const zero = [_]u8{0} ** 32;
+
+/// Double-word scalar representation
const ScalarExpanded = struct {
limbs: [64]i64 = [_]i64{0} ** 64,
@@ -62,6 +70,11 @@ const ScalarExpanded = struct {
inline while (j < 32) : (j += 1) {
limbs[j + 1] += limbs[j] >> 8;
}
+ j = 0;
+ inline while (j < 32) : (j += 1) {
+ limbs[j] &= 0xff;
+ }
+ limbs[32] = 0;
}
fn toBytes(e: *ScalarExpanded) [32]u8 {
@@ -150,11 +163,51 @@ pub inline fn clamp(s: *[32]u8) void {
s[31] = (s[31] & 127) | 64;
}
+/// Return a*b (mod L)
+pub fn mul(a: [32]u8, b: [32]u8) [32]u8 {
+ return ScalarExpanded.fromBytes(a).mul(ScalarExpanded.fromBytes(b)).toBytes();
+}
+
/// Return a*b+c (mod L)
pub fn mulAdd(a: [32]u8, b: [32]u8, c: [32]u8) [32]u8 {
return ScalarExpanded.fromBytes(a).mulAdd(ScalarExpanded.fromBytes(b), ScalarExpanded.fromBytes(c)).toBytes();
}
+/// Return a*8 (mod L)
+pub fn mul8(s: [32]u8) [32]u8 {
+ var x = ScalarExpanded.fromBytes(s);
+ x = x.add(x);
+ x = x.add(x);
+ x = x.add(x);
+ return x.toBytes();
+}
+
+/// Return a+b (mod L)
+pub fn add(a: [32]u8, b: [32]u8) [32]u8 {
+ return ScalarExpanded.fromBytes(a).add(ScalarExpanded.fromBytes(b)).toBytes();
+}
+
+/// Return -s (mod L)
+pub fn neg(s: [32]u8) [32]u8 {
+ const fs: [64]u8 = field_size ++ [_]u8{0} ** 32;
+ var sx: [64]u8 = undefined;
+ mem.copy(u8, sx[0..32], s[0..]);
+ mem.set(u8, sx[32..], 0);
+ var carry: u32 = 0;
+ var i: usize = 0;
+ while (i < 64) : (i += 1) {
+ carry = @as(u32, fs[i]) -% sx[i] -% @as(u32, carry);
+ sx[i] = @truncate(u8, carry);
+ carry = (carry >> 8) & 1;
+ }
+ return reduce64(sx);
+}
+
+/// Return (a-b) (mod L)
+pub fn sub(a: [32]u8, b: [32]u8) [32]u8 {
+ return add(a, neg(b));
+}
+
test "scalar25519" {
const bytes: [32]u8 = .{ 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 255 };
var x = ScalarExpanded.fromBytes(bytes);