crypto: P224::Contract could produce a non-minimal representation.

I missed an overflow in Contract because I suspected that the prime elimination
would take care of it. It didn't, and I forgot to get back to the overflow.
Because of this, Contract may have produced a non-minimal representation,
causing flakey failures ~0.02% of the time.

BUG=110972
TEST=crypto_unittests


Review URL: http://codereview.chromium.org/9104013

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@119775 0039d316-1c4b-4281-b951-d872f2087c98

1 files changed, 35 insertions, 2 deletions

diff --git a/crypto/p224.cc b/crypto/p224.cc
index 31a19bc..a7cc66b 100644
--- a/crypto/p224.cc
+++ b/crypto/p224.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -247,7 +247,7 @@ void Invert(FieldElement* out, const FieldElement& in) {
 
 // Contract converts a FieldElement to its minimal, distinguished form.
 //
-// On entry, in[i] < 2**32
+// On entry, in[i] < 2**29
 // On exit, in[i] < 2**28
 void Contract(FieldElement* inout) {
   FieldElement& out = *inout;
@@ -273,6 +273,39 @@ void Contract(FieldElement* inout) {
     out[i+1] -= 1 & mask;
   }
 
+  // We might have pushed out[3] over 2**28 so we perform another, partial
+  // carry chain.
+  for (int i = 3; i < 7; i++) {
+    out[i+1] += out[i] >> 28;
+    out[i] &= kBottom28Bits;
+  }
+  top = out[7] >> 28;
+  out[7] &= kBottom28Bits;
+
+  // Eliminate top while maintaining the same value mod p.
+  out[0] -= top;
+  out[3] += top << 12;
+
+  // There are two cases to consider for out[3]:
+  //   1) The first time that we eliminated top, we didn't push out[3] over
+  //      2**28. In this case, the partial carry chain didn't change any values
+  //      and top is zero.
+  //   2) We did push out[3] over 2**28 the first time that we eliminated top.
+  //      The first value of top was in [0..16), therefore, prior to eliminating
+  //      the first top, 0xfff1000 <= out[3] <= 0xfffffff. Therefore, after
+  //      overflowing and being reduced by the second carry chain, out[3] <=
+  //      0xf000. Thus it cannot have overflowed when we eliminated top for the
+  //      second time.
+
+  // Again, we may just have made out[0] negative, so do the same carry down.
+  // As before, if we made out[0] negative then we know that out[3] is
+  // sufficiently positive.
+  for (int i = 0; i < 3; i++) {
+    uint32 mask = static_cast<uint32>(static_cast<int32>(out[i]) >> 31);
+    out[i] += (1 << 28) & mask;
+    out[i+1] -= 1 & mask;
+  }
+
   // The value is < 2**224, but maybe greater than p. In order to reduce to a
   // unique, minimal value we see if the value is >= p and, if so, subtract p.