# [curves] Torsion-safe representatives (was: Ed25519 "clamping" and its effect on hierarchical key derivation)

Mike Hamburg mike at shiftleft.org
Mon Mar 27 11:06:56 PDT 2017

> On Mar 27, 2017, at 11:04 AM, Oleg Andreev <oleganza at gmail.com> wrote:
>
> 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?

Yes.

> 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.
>
> Thank you!
>
>>
>> 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
>> scalars.
>>
>> 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
>> bytes.
>>
>> 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 [0] in case anyone is
>> curious to see what it looks like.
>>
>> Cheers,
>> Henry de Valence
>>
>> [0]: 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
>> [0,
>> 21711016731996786641919559689128982722571349078139722818005852814856362752967,
>> 43422033463993573283839119378257965445142698156279445636011705629712725505934,
>> 7237005577332262213973186563042994240857116359379907606001950938285454250989,
>> 28948022309329048855892746252171976963428465437519630424007803753141817003956,
>> 50659039041325835497812305941300959685999814515659353242013656567998179756923,
>> 14474011154664524427946373126085988481714232718759815212003901876570908501978,
>> 36185027886661311069865932815214971204285581796899538030009754691427271254945]
>> _______________________________________________
>> Curves mailing list
>> Curves at moderncrypto.org
>> https://moderncrypto.org/mailman/listinfo/curves
>
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org <mailto:Curves at moderncrypto.org>
> https://moderncrypto.org/mailman/listinfo/curves <https://moderncrypto.org/mailman/listinfo/curves>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170327/7bcee7bd/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3571 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170327/7bcee7bd/attachment.bin>