[curves] Torsion-safe representatives (was: Ed25519 "clamping" and its effect on hierarchical key derivation)
oleganza at gmail.com
Mon Mar 27 11:04:40 PDT 2017
Henry, the technique you showed is fantastic, I love it!
I have a lame question, though. You mention that `a*B = a'*B` holds for the base point. But is it also true for any point in the B's subgroup? The reason I ask is that I need to have not just regular EdDSA signatures, but also DLEQs (discrete log equality proofs) with random generator points.
> Hi all,
> this subject came up today at the Tor meeting in a discussion with Ian
> Goldberg, George Kadianakis, Isis Lovecruft, and myself.
> As Tony noted, using bit-twiddling to mask away the low bits of a scalar is
> problematic because the bit-twiddling is not well-defined `(mod l)`. (Here `l`
> is the order of the basepoint, so the full group has order `8*l`). This means
> that the "clamping" is not compatible with any arithmetic operations on
> We (Ian, George, Isis, and myself) have the following suggestion.
> Define a "torsion-safe representative" of `a \in Z` to be 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, so accidentally multiplying by a torsion point can't leak
> information. However, unlike "clamping", this operation is actually
> well-defined, and leaves the scalar unchanged, in the sense that scalar
> multiplication by `a` and by `a'` are the same on the prime-order subgroup.
> How do we compute such a representative? Since (using the CRT)
> k := 3l + 1 ≡ 1 (mod l)
> ≡ 0 (mod 8),
> `k*a mod 8l` is a torsion-safe representative of `a`. Computing `k*a mod 8l`
> directly is a problem because an implementation may only have arithmetic modulo
> `l`, not `8l`. However,
> k*a ≡ (3l+1)*a ≡ 3al + a (mod 8l),
> so it's sufficient to compute `3al (mod 8l)` and add it to `a`. Since
> 3a mod 8 = 3a + 8n,
> (3a mod 8)*l = 3al + 8ln ≡ 3al (mod 8l),
> so it's sufficient to compute `3a mod 8` and use a lookup table of
> [0, 1l, 2l, 3l, 4l, 5l, 6l, 7l]
> to get `3al (mod 8l)`. Arranging the lookup table as
> [0, 3l, 6l, 1l, 4l, 7l, 2l, 5l]
> means that `a mod 8` indexes `3al (mod 8l)`. Therefore, computing a
> torsion-safe representative for a scalar `a` just amounts to computing
> a + permuted_lookup_table[a & 7]
> in constant time. If the input `a` is reduced, so that `a < l`, then the
> torsion-safe representative is bounded by `8l < 2^256` and therefore fits in 32
> This ends up being slightly more work than just bit-twiddling, but not by much,
> and it's certainly insignificant compared to the cost of a scalar
> multiplication. There's a prototype implementation here  in case anyone is
> curious to see what it looks like.
> Henry de Valence
> : https://github.com/hdevalence/curve25519-dalek/commit/2ae0bdb6df26a74ef46d4332b635c9f6290126c7
> (subject to rebasing...)
> The permuted lookup table is, explicitly:
> sage: l = 2^252 + 27742317777372353535851937790883648493
> sage: lookup = [((3 * i) % 8)*l for i in range(8)]
> sage: lookup
> Curves mailing list
> Curves at moderncrypto.org
More information about the Curves