From 95b19cd50a30aac9cbd3cc810a4c4153f20af13d Mon Sep 17 00:00:00 2001 From: Loup Vaillant Date: Mon, 14 Oct 2019 10:55:12 +0200 Subject: [PATCH] Start sliding windows at bit 252 When performing the double scalar multiplication, bit 253, 254, and 255 are guaranteed to be zero. No need to check them, we can start from 252. Also added a comment warning about a possible off-by-one error. --- src/monocypher.c | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-) diff --git a/src/monocypher.c b/src/monocypher.c index bce3138..0bca1e8 100644 --- a/src/monocypher.c +++ b/src/monocypher.c @@ -1668,7 +1668,17 @@ typedef struct { void slide_init(slide_ctx *ctx, const u8 scalar[32]) { - int i = 255; + // scalar is guaranteed to be below L, either because we checked (s), + // or because we reduced it modulo L (h_ram). L is under 2^253, so + // so bits 253 to 255 are guaranteed to be zero. No need to test them. + // + // Note however that L is very close to 2^252, so bit 252 is almost + // always zero. If we were to start at bit 251, the tests wouldn't + // catch the off-by-one error (constructing one that does would be + // prohibitively expensive). + // + // We should still check bit 252, though. + int i = 252; while (i > 0 && scalar_bit(scalar, i) == 0) { i--; } -- 2.47.3