}
/*
- * Propagate carries. Since the operation above really is a
- * truncature, followed by the addition of nonnegative values,
- * the result will be positive. Moreover, the carry cannot
- * exceed 5 bits (we performed 20 additions with values smaller
- * than 256 bits).
+ * Propagate carries. This is a signed propagation, and the
+ * result may be negative. The loop above may enlarge values,
+ * but not two much: worst case is the chain involving t[i - 3],
+ * in which a value may be added to itself up to 7 times. Since
+ * starting values are 13-bit each, all words fit on 20 bits
+ * (21 to account for the sign bit).
*/
cc = norm13(t, t, 20);
/*
* Perform modular reduction again for the bits beyond 256 (the carry
- * and the bits 256..259). This time, we can simply inject full
- * word values.
+ * and the bits 256..259). Since the largest shift below is by 10
+ * bits, and the values fit on 21 bits, values fit in 32-bit words,
+ * thereby allowing injecting full word values.
*/
cc = (cc << 4) | (t[19] >> 9);
t[19] &= 0x01FF;
t[14] -= cc << 10;
t[7] -= cc << 5;
t[0] += cc;
+
+ /*
+ * If the carry is negative, then after carry propagation, we may
+ * end up with a value which is negative, and we don't want that.
+ * Thus, in that case, we add the modulus. Note that the subtraction
+ * result, when the carry is negative, is always smaller than the
+ * modulus, so the extra addition will not make the value exceed
+ * twice the modulus.
+ */
+ cc >>= 31;
+ t[0] -= cc;
+ t[7] += cc << 5;
+ t[14] += cc << 10;
+ t[17] -= cc << 3;
+ t[19] += cc << 9;
+
norm13(d, t, 20);
}
}
/*
- * Propagate carries. Since the operation above really is a
- * truncature, followed by the addition of nonnegative values,
- * the result will be positive. Moreover, the carry cannot
- * exceed 5 bits (we performed 20 additions with values smaller
- * than 256 bits).
+ * Propagate carries. This is a signed propagation, and the
+ * result may be negative. The loop above may enlarge values,
+ * but not two much: worst case is the chain involving t[i - 3],
+ * in which a value may be added to itself up to 7 times. Since
+ * starting values are 13-bit each, all words fit on 20 bits
+ * (21 to account for the sign bit).
*/
cc = norm13(t, t, 20);
/*
* Perform modular reduction again for the bits beyond 256 (the carry
- * and the bits 256..259). This time, we can simply inject full
- * word values.
+ * and the bits 256..259). Since the largest shift below is by 10
+ * bits, and the values fit on 21 bits, values fit in 32-bit words,
+ * thereby allowing injecting full word values.
*/
cc = (cc << 4) | (t[19] >> 9);
t[19] &= 0x01FF;
t[14] -= cc << 10;
t[7] -= cc << 5;
t[0] += cc;
+
+ /*
+ * If the carry is negative, then after carry propagation, we may
+ * end up with a value which is negative, and we don't want that.
+ * Thus, in that case, we add the modulus. Note that the subtraction
+ * result, when the carry is negative, is always smaller than the
+ * modulus, so the extra addition will not make the value exceed
+ * twice the modulus.
+ */
+ cc >>= 31;
+ t[0] -= cc;
+ t[7] += cc << 5;
+ t[14] += cc << 10;
+ t[17] -= cc << 3;
+ t[19] += cc << 9;
+
norm13(d, t, 20);
}
return P256_N;
}
+static size_t
+api_xoff(int curve, size_t *len)
+{
+ (void)curve;
+ *len = 32;
+ return 1;
+}
+
static uint32_t
api_mul(unsigned char *G, size_t Glen,
const unsigned char *x, size_t xlen, int curve)
(uint32_t)0x00800000,
&api_generator,
&api_order,
+ &api_xoff,
&api_mul,
&api_mulgen,
&api_muladd