Elliptic Curve Digital Signature Algorithm (ECDSA).
pub fn Ecdsa(comptime Curve: type, comptime Hash: type) typepub fn Ecdsa(comptime Curve: type, comptime Hash: type) type {
const Prf = switch (Hash) {
sha3.Shake128 => sha3.KMac128,
sha3.Shake256 => sha3.KMac256,
else => crypto.auth.hmac.Hmac(Hash),
};
return struct {
/// Length (in bytes) of optional random bytes, for non-deterministic signatures.
pub const noise_length = Curve.scalar.encoded_length;
/// An ECDSA secret key.
pub const SecretKey = struct {
/// Length (in bytes) of a raw secret key.
pub const encoded_length = Curve.scalar.encoded_length;
bytes: Curve.scalar.CompressedScalar,
pub fn fromBytes(bytes: [encoded_length]u8) !SecretKey {
return SecretKey{ .bytes = bytes };
}
pub fn toBytes(sk: SecretKey) [encoded_length]u8 {
return sk.bytes;
}
};
/// An ECDSA public key.
pub const PublicKey = struct {
/// Length (in bytes) of a compressed sec1-encoded key.
pub const compressed_sec1_encoded_length = 1 + Curve.Fe.encoded_length;
/// Length (in bytes) of an uncompressed sec1-encoded key.
pub const uncompressed_sec1_encoded_length = 1 + 2 * Curve.Fe.encoded_length;
p: Curve,
/// Create a public key from a SEC-1 representation.
pub fn fromSec1(sec1: []const u8) !PublicKey {
return PublicKey{ .p = try Curve.fromSec1(sec1) };
}
/// Encode the public key using the compressed SEC-1 format.
pub fn toCompressedSec1(pk: PublicKey) [compressed_sec1_encoded_length]u8 {
return pk.p.toCompressedSec1();
}
/// Encoding the public key using the uncompressed SEC-1 format.
pub fn toUncompressedSec1(pk: PublicKey) [uncompressed_sec1_encoded_length]u8 {
return pk.p.toUncompressedSec1();
}
};
/// An ECDSA signature.
pub const Signature = struct {
/// Length (in bytes) of a raw signature.
pub const encoded_length = Curve.scalar.encoded_length * 2;
/// Maximum length (in bytes) of a DER-encoded signature.
pub const der_encoded_length_max = encoded_length + 2 + 2 * 3;
/// The R component of an ECDSA signature.
r: Curve.scalar.CompressedScalar,
/// The S component of an ECDSA signature.
s: Curve.scalar.CompressedScalar,
/// Create a Verifier for incremental verification of a signature.
pub fn verifier(sig: Signature, public_key: PublicKey) Verifier.InitError!Verifier {
return Verifier.init(sig, public_key);
}
pub const VerifyError = Verifier.InitError || Verifier.VerifyError;
/// Verify the signature against a message and public key.
/// Return IdentityElement or NonCanonical if the public key or signature are not in the expected range,
/// or SignatureVerificationError if the signature is invalid for the given message and key.
pub fn verify(sig: Signature, msg: []const u8, public_key: PublicKey) VerifyError!void {
var st = try sig.verifier(public_key);
st.update(msg);
try st.verify();
}
/// Verify the signature against a pre-hashed message and public key.
/// The message must have already been hashed using the scheme's hash function.
/// Returns SignatureVerificationError if the signature is invalid for the given message and key.
pub fn verifyPrehashed(sig: Signature, msg_hash: [Hash.digest_length]u8, public_key: PublicKey) VerifyError!void {
var st = try sig.verifier(public_key);
return st.verifyPrehashed(msg_hash);
}
/// Return the raw signature (r, s) in big-endian format.
pub fn toBytes(sig: Signature) [encoded_length]u8 {
var bytes: [encoded_length]u8 = undefined;
@memcpy(bytes[0 .. encoded_length / 2], &sig.r);
@memcpy(bytes[encoded_length / 2 ..], &sig.s);
return bytes;
}
/// Create a signature from a raw encoding of (r, s).
/// ECDSA always assumes big-endian.
pub fn fromBytes(bytes: [encoded_length]u8) Signature {
return Signature{
.r = bytes[0 .. encoded_length / 2].*,
.s = bytes[encoded_length / 2 ..].*,
};
}
/// Encode the signature using the DER format.
/// The maximum length of the DER encoding is der_encoded_length_max.
/// The function returns a slice, that can be shorter than der_encoded_length_max.
pub fn toDer(sig: Signature, buf: *[der_encoded_length_max]u8) []u8 {
var w: std.Io.Writer = .fixed(buf);
const sig_r = mem.trimStart(u8, &sig.r, &.{0});
const sig_s = mem.trimStart(u8, &sig.s, &.{0});
const r_len = @as(u8, @intCast(sig_r.len + (sig_r[0] >> 7)));
const s_len = @as(u8, @intCast(sig_s.len + (sig_s[0] >> 7)));
const seq_len = @as(u8, @intCast(2 + r_len + 2 + s_len));
w.writeAll(&[_]u8{ 0x30, seq_len }) catch unreachable;
w.writeAll(&[_]u8{ 0x02, r_len }) catch unreachable;
if (sig_r[0] >> 7 != 0) {
w.writeByte(0x00) catch unreachable;
}
w.writeAll(sig_r) catch unreachable;
w.writeAll(&[_]u8{ 0x02, s_len }) catch unreachable;
if (sig_s[0] >> 7 != 0) {
w.writeByte(0x00) catch unreachable;
}
w.writeAll(sig_s) catch unreachable;
return w.buffered();
}
// Read a DER-encoded integer.
fn readDerInt(out: []u8, reader: *std.Io.Reader) EncodingError!void {
const buf = reader.takeArray(2) catch return error.InvalidEncoding;
if (buf[0] != 0x02) return error.InvalidEncoding;
var expected_len: usize = buf[1];
if (expected_len == 0 or expected_len > 1 + out.len) return error.InvalidEncoding;
var has_top_bit = false;
if (expected_len == 1 + out.len) {
if ((reader.takeByte() catch return error.InvalidEncoding) != 0) return error.InvalidEncoding;
expected_len -= 1;
has_top_bit = true;
}
const out_slice = out[out.len - expected_len ..];
reader.readSliceAll(out_slice) catch return error.InvalidEncoding;
if (@intFromBool(has_top_bit) != out[0] >> 7) return error.InvalidEncoding;
}
/// Create a signature from a DER representation.
/// Returns InvalidEncoding if the DER encoding is invalid.
pub fn fromDer(der: []const u8) EncodingError!Signature {
var sig: Signature = mem.zeroInit(Signature, .{});
var reader: std.Io.Reader = .fixed(der);
const buf = reader.takeArray(2) catch return error.InvalidEncoding;
if (buf[0] != 0x30 or @as(usize, buf[1]) + 2 != der.len) {
return error.InvalidEncoding;
}
try readDerInt(&sig.r, &reader);
try readDerInt(&sig.s, &reader);
if (reader.seek != der.len) return error.InvalidEncoding;
return sig;
}
};
/// A Signer is used to incrementally compute a signature.
/// It can be obtained from a `KeyPair`, using the `signer()` function.
pub const Signer = struct {
h: Hash,
secret_key: SecretKey,
noise: ?[noise_length]u8,
fn init(secret_key: SecretKey, noise: ?[noise_length]u8) !Signer {
return Signer{
.h = Hash.init(.{}),
.secret_key = secret_key,
.noise = noise,
};
}
/// Add new data to the message being signed.
pub fn update(self: *Signer, data: []const u8) void {
self.h.update(data);
}
/// Compute a signature over a hash.
fn finalizePrehashed(self: *Signer, msg_hash: [Hash.digest_length]u8) (IdentityElementError || NonCanonicalError)!Signature {
const scalar_encoded_length = Curve.scalar.encoded_length;
const h_len = @max(Hash.digest_length, scalar_encoded_length);
var h: [h_len]u8 = @as([h_len - Hash.digest_length]u8, @splat(0)) ++ msg_hash;
std.debug.assert(h.len >= scalar_encoded_length);
const z = reduceToScalar(scalar_encoded_length, h[0..scalar_encoded_length].*);
const k = deterministicScalar(msg_hash, self.secret_key.bytes, self.noise);
const p = try Curve.basePoint.mul(k.toBytes(.big), .big);
const xs = p.affineCoordinates().x.toBytes(.big);
const r = reduceToScalar(Curve.Fe.encoded_length, xs);
if (r.isZero()) return error.IdentityElement;
const k_inv = k.invert();
const zrs = z.add(r.mul(try Curve.scalar.Scalar.fromBytes(self.secret_key.bytes, .big)));
const s = k_inv.mul(zrs);
if (s.isZero()) return error.IdentityElement;
return Signature{ .r = r.toBytes(.big), .s = s.toBytes(.big) };
}
/// Compute a signature over the entire message.
pub fn finalize(self: *Signer) (IdentityElementError || NonCanonicalError)!Signature {
var h_slice: [Hash.digest_length]u8 = undefined;
self.h.final(&h_slice);
return self.finalizePrehashed(h_slice);
}
};
/// A Verifier is used to incrementally verify a signature.
/// It can be obtained from a `Signature`, using the `verifier()` function.
pub const Verifier = struct {
h: Hash,
r: Curve.scalar.Scalar,
s: Curve.scalar.Scalar,
public_key: PublicKey,
pub const InitError = IdentityElementError || NonCanonicalError;
fn init(sig: Signature, public_key: PublicKey) InitError!Verifier {
const r = try Curve.scalar.Scalar.fromBytes(sig.r, .big);
const s = try Curve.scalar.Scalar.fromBytes(sig.s, .big);
if (r.isZero() or s.isZero()) return error.IdentityElement;
return Verifier{
.h = Hash.init(.{}),
.r = r,
.s = s,
.public_key = public_key,
};
}
/// Add new content to the message to be verified.
pub fn update(self: *Verifier, data: []const u8) void {
self.h.update(data);
}
pub const VerifyError = IdentityElementError || NonCanonicalError ||
SignatureVerificationError;
/// Verify that the signature is valid for the hash.
fn verifyPrehashed(self: *Verifier, msg_hash: [Hash.digest_length]u8) VerifyError!void {
const ht = Curve.scalar.encoded_length;
const h_len = @max(Hash.digest_length, ht);
var h: [h_len]u8 = @as([h_len - Hash.digest_length]u8, @splat(0)) ++ msg_hash;
const z = reduceToScalar(ht, h[0..ht].*);
if (z.isZero()) {
return error.SignatureVerificationFailed;
}
const s_inv = self.s.invert();
const v1 = z.mul(s_inv).toBytes(.little);
const v2 = self.r.mul(s_inv).toBytes(.little);
const v1g = try Curve.basePoint.mulPublic(v1, .little);
const v2pk = try self.public_key.p.mulPublic(v2, .little);
const vxs = v1g.add(v2pk).affineCoordinates().x.toBytes(.big);
const vr = reduceToScalar(Curve.Fe.encoded_length, vxs);
if (!self.r.equivalent(vr)) {
return error.SignatureVerificationFailed;
}
}
/// Verify that the signature is valid for the entire message.
pub fn verify(self: *Verifier) VerifyError!void {
var h_slice: [Hash.digest_length]u8 = undefined;
self.h.final(&h_slice);
return self.verifyPrehashed(h_slice);
}
};
/// An ECDSA key pair.
pub const KeyPair = struct {
/// Length (in bytes) of a seed required to create a key pair.
pub const seed_length = noise_length;
/// Public part.
public_key: PublicKey,
/// Secret scalar.
secret_key: SecretKey,
/// Deterministically derive a key pair from a cryptograpically secure secret seed.
///
/// Except in tests, applications should generally call `generate()` instead of this function.
pub fn generateDeterministic(seed: [seed_length]u8) IdentityElementError!KeyPair {
const h: [Hash.digest_length]u8 = @splat(0x00);
const k0: [SecretKey.encoded_length]u8 = @splat(0x01);
const secret_key = deterministicScalar(h, k0, seed).toBytes(.big);
return fromSecretKey(SecretKey{ .bytes = secret_key });
}
/// Generate a new, random key pair.
pub fn generate(io: std.Io) KeyPair {
var random_seed: [seed_length]u8 = undefined;
while (true) {
io.random(&random_seed);
return generateDeterministic(random_seed) catch {
@branchHint(.unlikely);
continue;
};
}
}
/// Return the public key corresponding to the secret key.
pub fn fromSecretKey(secret_key: SecretKey) IdentityElementError!KeyPair {
const public_key = try Curve.basePoint.mul(secret_key.bytes, .big);
return KeyPair{ .secret_key = secret_key, .public_key = PublicKey{ .p = public_key } };
}
/// Sign a message using the key pair.
/// The noise can be null in order to create deterministic signatures.
/// If deterministic signatures are not required, the noise should be randomly generated instead.
/// This helps defend against fault attacks.
pub fn sign(key_pair: KeyPair, msg: []const u8, noise: ?[noise_length]u8) (IdentityElementError || NonCanonicalError)!Signature {
var st = try key_pair.signer(noise);
st.update(msg);
return st.finalize();
}
/// Sign a pre-hashed message using the key pair.
/// The message must have already been hashed using the scheme's hash function.
/// The noise parameter can be null for deterministic signatures, or random bytes for enhanced security against fault attacks.
pub fn signPrehashed(key_pair: KeyPair, msg_hash: [Hash.digest_length]u8, noise: ?[noise_length]u8) (IdentityElementError || NonCanonicalError)!Signature {
var st = try key_pair.signer(noise);
return st.finalizePrehashed(msg_hash);
}
/// Create a Signer, that can be used for incremental signature verification.
pub fn signer(key_pair: KeyPair, noise: ?[noise_length]u8) !Signer {
return Signer.init(key_pair.secret_key, noise);
}
};
// Reduce the coordinate of a field element to the scalar field.
fn reduceToScalar(comptime unreduced_len: usize, s: [unreduced_len]u8) Curve.scalar.Scalar {
if (unreduced_len >= 48) {
var xs: [64]u8 = @splat(0);
@memcpy(xs[xs.len - s.len ..], s[0..]);
return Curve.scalar.Scalar.fromBytes64(xs, .big);
}
var xs: [48]u8 = @splat(0);
@memcpy(xs[xs.len - s.len ..], s[0..]);
return Curve.scalar.Scalar.fromBytes48(xs, .big);
}
// Create a deterministic scalar according to a secret key and optional noise.
// This uses the overly conservative scheme from the "Deterministic ECDSA and EdDSA Signatures with Additional Randomness" draft.
fn deterministicScalar(h: [Hash.digest_length]u8, secret_key: Curve.scalar.CompressedScalar, noise: ?[noise_length]u8) Curve.scalar.Scalar {
var k: [h.len]u8 = @splat(0);
var m: [h.len + 1 + noise_length + secret_key.len + h.len]u8 = @splat(0);
var t: [Curve.scalar.encoded_length]u8 = @splat(0);
const m_v = m[0..h.len];
const m_i = &m[m_v.len];
const m_z = m[m_v.len + 1 ..][0..noise_length];
const m_x = m[m_v.len + 1 + noise_length ..][0..secret_key.len];
const m_h = m[m.len - h.len ..];
@memset(m_v, 0x01);
m_i.* = 0x00;
if (noise) |n| @memcpy(m_z, &n);
@memcpy(m_x, &secret_key);
@memcpy(m_h, &h);
Prf.create(&k, &m, &k);
Prf.create(m_v, m_v, &k);
m_i.* = 0x01;
Prf.create(&k, &m, &k);
Prf.create(m_v, m_v, &k);
while (true) {
var t_off: usize = 0;
while (t_off < t.len) : (t_off += m_v.len) {
const t_end = @min(t_off + m_v.len, t.len);
Prf.create(m_v, m_v, &k);
@memcpy(t[t_off..t_end], m_v[0 .. t_end - t_off]);
}
if (Curve.scalar.Scalar.fromBytes(t, .big)) |s| return s else |_| {}
m_i.* = 0x00;
Prf.create(&k, m[0 .. m_v.len + 1], &k);
Prf.create(m_v, m_v, &k);
}
}
};
}