Add a function to give a 'torsion-safe' representative of a scalar

hdevalence · hdevalence · commit 2ae0bdb6df26 · 2017-03-25T10:25:20.000-07:00
diff --git a/src/constants.rs b/src/constants.rs
@@ -165,6 +165,31 @@ pub const lminus1: Scalar = Scalar([ 0xec, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0
                                      0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
                                      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                                      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10 ]);
+
+/// A table of small multiples of l, arranged so that the `i`-th entry
+/// of the table contains `l * ((3*i) % 8) mod 8l`.
+///
+/// Used for clamping since we do not have an implementation of
+/// multiplication mod 8l, only mod l.
+pub const permuted_multiples_of_l: [Scalar; 8] = [
+    Scalar([0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00]),
+    Scalar([0xc7, 0x7b, 0xe1, 0x16, 0x4f, 0x29, 0x37, 0x08, 0x83, 0xd6, 0xe6, 0xe8, 0x9b, 0xed, 0x9c, 0x3e,
+     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x30]),
+    Scalar([0x8e, 0xf7, 0xc2, 0x2d, 0x9e, 0x52, 0x6e, 0x10, 0x06, 0xad, 0xcd, 0xd1, 0x37, 0xdb, 0x39, 0x7d,
+     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x60]),
+    Scalar([0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
+     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10]),
+    Scalar([0xb4, 0x4f, 0xd7, 0x73, 0x69, 0x8c, 0x49, 0x60, 0x59, 0x73, 0xde, 0x8b, 0x7a, 0xe7, 0x7b, 0x53,
+     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40]),
+    Scalar([0x7b, 0xcb, 0xb8, 0x8a, 0xb8, 0xb5, 0x80, 0x68, 0xdc, 0x49, 0xc5, 0x74, 0x16, 0xd5, 0x18, 0x92,
+     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x70]),
+    Scalar([0xda, 0xa7, 0xeb, 0xb9, 0x34, 0xc6, 0x24, 0xb0, 0xac, 0x39, 0xef, 0x45, 0xbd, 0xf3, 0xbd, 0x29,
+     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x20]),
+    Scalar([0xa1, 0x23, 0xcd, 0xd0, 0x83, 0xef, 0x5b, 0xb8, 0x2f, 0x10, 0xd6, 0x2e, 0x59, 0xe1, 0x5a, 0x68,
+     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x50]),
+];
+
 /// The 8-torsion subgroup Ɛ[8].
 ///
 /// In the case of Curve25519, it is cyclic; the `i`th element of the
diff --git a/src/curve.rs b/src/curve.rs
@@ -1419,6 +1419,23 @@ mod test {
             P = P.scalar_mult(&A_SCALAR);
         }
     }
+
+    /// Test that torsion-safe scalars really are torsion-safe.
+    #[test]
+    fn torsion_safe_scalars_are_torsion_safe() {
+        let a_safe = A_SCALAR.to_torsion_safe_representative();
+
+        // a_safe should kill all torsion points...
+        for i in 0..8 {
+            assert!(constants::EIGHT_TORSION[i]
+                    .scalar_mult(&a_safe)
+                    .is_identity());
+        }
+
+        // but give the same result as a in the prime-order subgroup
+        assert_eq!(ExtendedPoint::basepoint_mult(&a_safe).compress_edwards(),
+                   ExtendedPoint::basepoint_mult(&A_SCALAR).compress_edwards());
+    }
 }
 
 // ------------------------------------------------------------------------
diff --git a/src/scalar.rs b/src/scalar.rs
@@ -44,6 +44,7 @@ use utils::{load3, load4};
 use subtle::CTAssignable;
 use subtle::CTEq;
 use subtle::arrays_equal_ct;
+use subtle;
 
 /// The `Scalar` struct represents an element in ℤ/lℤ, where
 ///
@@ -325,6 +326,50 @@ impl Scalar {
         output
     }
 
+    /// Compute a "torsion-safe" representative of this scalar, in
+    /// constant time.
+    ///
+    /// A torsion-safe representative of an integer `a \in Z/lZ` is an
+    /// integer `a' \in Z` such that `a ≡ a' (mod l)` and `a' ≡ 0 (mod 8)`.
+    ///
+    /// This means that `a B = a' B` for the basepoint `B`, but
+    /// `a' T = id` for `T` a torsion point.
+    ///
+    /// Using a torsion-safe representative ensures that accidentally
+    /// multiplying by a point of low order does not leak any
+    /// information about the scalar.  However, unlike simply clamping
+    /// the low bits of an integer to 0, it is well-defined `(mod l)`,
+    /// so that it is compatible with arithmetic operations on
+    /// scalars.
+    pub fn to_torsion_safe_representative(&self) -> Scalar {
+        let a = self;
+        // Note that k = 3l + 1 is ≡ 1 (mod l), ≡ 0 (mod 8).
+        //
+        // Therefore k*a (mod 8l) is a torsion-safe representative of a.
+        //
+        // We want to compute k*a ≡ (3l+1)*a ≡ 3al + a (mod 8l).
+        //
+        // Since 3a mod 8 = 3a + 8n, (3a mod 8)*l = 3al + 8ln ≡ 3al (mod 8l).
+        let a_mod_8 = a[0] & 0b111;
+        let mut t = Scalar::zero();
+        for i in 0..8 {
+            // The i-th entry of the table contains `l * ((3*i) mod 8)`.
+            t.conditional_assign(&constants::permuted_multiples_of_l[i as usize],
+                                 subtle::bytes_equal_ct(i, a_mod_8));
+        }
+
+        // Now t ≡ 3al (mod 8l), so add a to it.
+        let mut carry = 0u8;
+        for i in 0..32 {
+            let sum = (a.0[i] as u16) + (t[i] as u16) + (carry as u16);
+            t[i] = (sum & 0xff) as u8;
+            carry = (sum >> 8) as u8;
+        }
+        debug_assert!(carry == 0);
+
+        t
+    }
+
     /// Compute `ab+c (mod l)`.
     /// XXX should this exist, or should we just have Mul, Add etc impls
     /// that unpack and then call UnpackedScalar::multiply_add ?
