author Thomas Pornin Fri, 23 Jun 2017 22:31:09 +0000 (00:31 +0200) committer Thomas Pornin Fri, 23 Jun 2017 22:31:09 +0000 (00:31 +0200)
 src/ec/ec_p256_m15.c patch | blob | history src/ec/ec_p256_m31.c patch | blob | history test/test_crypto.c patch | blob | history

index 06eee86..6ce57e0 100644 (file)
@@ -1122,6 +1122,22 @@ mul_f256(uint32_t *d, const uint32_t *a, const uint32_t *b)
t -= cc << 10;
t -= cc << 5;
t += 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 -= cc;
+       t += cc << 5;
+       t += cc << 10;
+       t -= cc << 3;
+       t += cc << 9;
+
norm13(d, t, 20);
}

@@ -1195,6 +1211,22 @@ square_f256(uint32_t *d, const uint32_t *a)
t -= cc << 10;
t -= cc << 5;
t += 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 -= cc;
+       t += cc << 5;
+       t += cc << 10;
+       t -= cc << 3;
+       t += cc << 9;
+
norm13(d, t, 20);
}

index 0631a13..0462c15 100644 (file)
@@ -394,7 +394,7 @@ mul_f256(uint32_t *d, const uint32_t *a, const uint32_t *b)
uint32_t t;
uint64_t s;
uint64_t cc, x;
-       uint32_t z;
+       uint32_t z, c;
int i;

mul9(t, a, b);
@@ -465,7 +465,15 @@ mul_f256(uint32_t *d, const uint32_t *a, const uint32_t *b)
d &= 0xFFFF;

/*
-        * Subtract cc*p.
+        * One extra round of reduction, for cc*2^256, which means
+        * adding cc*(2^224-2^192-2^96+1) to a 256-bit (nonnegative)
+        * value. If cc is negative, then it may happen (rarely, but
+        * not neglectibly so) that the result would be negative. In
+        * order to avoid that, if cc is negative, then we add the
+        * modulus once. Note that if cc is negative, then propagating
+        * that carry must yield a value lower than the modulus, so
+        * adding the modulus once will keep the final result under
+        * twice the modulus.
*/
z = (uint32_t)cc;
d -= z << 6;
@@ -473,6 +481,12 @@ mul_f256(uint32_t *d, const uint32_t *a, const uint32_t *b)
d -= ARSH(z, 18);
d += (z << 14) & 0x3FFFFFFF;
d += ARSH(z, 16);
+       c = z >> 31;
+       d -= c;
+       d += c << 6;
+       d += c << 12;
+       d -= c << 14;
+       d += c << 16;
for (i = 0; i < 9; i ++) {
uint32_t w;

@@ -492,7 +506,7 @@ square_f256(uint32_t *d, const uint32_t *a)
uint32_t t;
uint64_t s;
uint64_t cc, x;
-       uint32_t z;
+       uint32_t z, c;
int i;

square9(t, a);
@@ -563,7 +577,15 @@ square_f256(uint32_t *d, const uint32_t *a)
d &= 0xFFFF;

/*
-        * Subtract cc*p.
+        * One extra round of reduction, for cc*2^256, which means
+        * adding cc*(2^224-2^192-2^96+1) to a 256-bit (nonnegative)
+        * value. If cc is negative, then it may happen (rarely, but
+        * not neglectibly so) that the result would be negative. In
+        * order to avoid that, if cc is negative, then we add the
+        * modulus once. Note that if cc is negative, then propagating
+        * that carry must yield a value lower than the modulus, so
+        * adding the modulus once will keep the final result under
+        * twice the modulus.
*/
z = (uint32_t)cc;
d -= z << 6;
@@ -571,6 +593,12 @@ square_f256(uint32_t *d, const uint32_t *a)
d -= ARSH(z, 18);
d += (z << 14) & 0x3FFFFFFF;
d += ARSH(z, 16);
+       c = z >> 31;
+       d -= c;
+       d += c << 6;
+       d += c << 12;
+       d -= c << 14;
+       d += c << 16;
for (i = 0; i < 9; i ++) {
uint32_t w;

index fd0b396..ae0c712 100644 (file)
@@ -5062,6 +5062,39 @@ test_EC_inner(const char *sk, const char *sU,
fflush(stdout);
}

+static void
+test_EC_P256_carry_inner(const br_ec_impl *impl, const char *sP, const char *sQ)
+{
+       unsigned char P, Q[sizeof P], k;
+       size_t plen, qlen;
+
+       plen = hextobin(P, sP);
+       qlen = hextobin(Q, sQ);
+       if (plen != sizeof P || qlen != sizeof P) {
+               fprintf(stderr, "KAT is incorrect\n");
+               exit(EXIT_FAILURE);
+       }
+       k = 0x10;
+       if (impl->mul(P, plen, k, 1, BR_EC_secp256r1) != 1) {
+               fprintf(stderr, "P-256 multiplication failed\n");
+               exit(EXIT_FAILURE);
+       }
+       check_equals("P256_carry", P, Q, plen);
+       printf(".");
+       fflush(stdout);
+}
+
+static void
+test_EC_P256_carry(const br_ec_impl *impl)
+{
+       test_EC_P256_carry_inner(impl,
+               "0435BAA24B2B6E1B3C88E22A383BD88CC4B9A3166E7BCF94FF6591663AE066B33B821EBA1B4FC8EA609A87EB9A9C9A1CCD5C9F42FA1365306F64D7CAA718B8C978",
+               "0447752A76CA890328D34E675C4971EC629132D1FC4863EDB61219B72C4E58DC5E9D51E7B293488CFD913C3CF20E438BB65C2BA66A7D09EABB45B55E804260C5EB");
+       test_EC_P256_carry_inner(impl,
+               "048DAC7B0BE9B3206FCE8B24B6B4AEB122F2A67D13E536B390B6585CA193427E63F222388B5F51D744D6F5D47536D89EEEC89552BCB269E7828019C4410DFE980A");
+}
+
static void
test_EC_KAT(const char *name, const br_ec_impl *impl, uint32_t curve_mask)
{
@@ -5074,6 +5107,7 @@ test_EC_KAT(const char *name, const br_ec_impl *impl, uint32_t curve_mask)
"C9AFA9D845BA75166B5C215767B1D6934E50C3DB36E89B127B8A622B120F6721",
"0460FED4BA255A9D31C961EB74C6356D68C049B8923B61FA6CE669622E60F29FB67903FE1008B8BC99A41AE9E95628BC64F2F1B20C2D7E9F5177A3C294D4462299",
impl, BR_EC_secp256r1);
+               test_EC_P256_carry(impl);
}
if (curve_mask & ((uint32_t)1 << BR_EC_secp384r1)) {
test_EC_inner(