diff options
Diffstat (limited to 'lib/std')
| -rw-r--r-- | lib/std/crypto/25519/ed25519.zig | 13 | ||||
| -rw-r--r-- | lib/std/crypto/25519/edwards25519.zig | 29 |
2 files changed, 33 insertions, 9 deletions
diff --git a/lib/std/crypto/25519/ed25519.zig b/lib/std/crypto/25519/ed25519.zig index 1a739de5c6..abbba22f11 100644 --- a/lib/std/crypto/25519/ed25519.zig +++ b/lib/std/crypto/25519/ed25519.zig @@ -168,18 +168,13 @@ pub const Ed25519 = struct { } zs_sum = Curve.scalar.mul8(zs_sum); - var zr = Curve.neutralElement; + var zhs: [count]Curve.scalar.CompressedScalar = undefined; for (z_batch) |z, i| { - zr = zr.add(try expected_r_batch[i].mulPublic(z)); + zhs[i] = Curve.scalar.mul(z, hram_batch[i]); } - 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].mulPublic(zh)); - } - zah = zah.clearCofactor(); + const zr = (try Curve.mulMulti(count, expected_r_batch, z_batch)).clearCofactor(); + const zah = (try Curve.mulMulti(count, a_batch, zhs)).clearCofactor(); const zsb = try Curve.basePoint.mulPublic(zs_sum); if (zr.add(zah).sub(zsb).rejectIdentity()) |_| { diff --git a/lib/std/crypto/25519/edwards25519.zig b/lib/std/crypto/25519/edwards25519.zig index a8991ac518..74ea89a952 100644 --- a/lib/std/crypto/25519/edwards25519.zig +++ b/lib/std/crypto/25519/edwards25519.zig @@ -208,6 +208,35 @@ pub const Edwards25519 = struct { return pcMul(pc, s, true); } + /// 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) !Edwards25519 { + var pcs: [count][16]Edwards25519 = undefined; + for (ps) |p, i| { + if (p.is_base) { + @setEvalBranchQuota(10000); + pcs[i] = comptime precompute(Edwards25519.basePoint); + } else { + pcs[i] = precompute(p); + pcs[i][4].rejectIdentity() catch |_| return error.WeakPublicKey; + } + } + var q = Edwards25519.identityElement; + var pos: usize = 252; + while (true) : (pos -= 4) { + q = q.dbl().dbl().dbl().dbl(); + for (ss) |s, i| { + const bit = (s[pos >> 3] >> @truncate(u3, pos)) & 0xf; + if (bit != 0) { + q = q.add(pcs[i][bit]); + } + } + if (pos == 0) break; + } + 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. |