<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""> </div><div><blockquote type="cite" class=""><div class="">On Mar 27, 2017, at 11:04 AM, Oleg Andreev <<a href="mailto:oleganza@gmail.com" class="">oleganza@gmail.com</a>> wrote:</div> <div class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">Henry, the technique you showed is fantastic, I love it!<br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">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?</div></blockquote><div> </div><div>Yes.</div> <blockquote type="cite" class=""><div class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""> 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.<br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">Thank you!<br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class=""> 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]: <a href="https://github.com/hdevalence/curve25519-dalek/commit/2ae0bdb6df26a74ef46d4332b635c9f6290126c7" class="">https://github.com/hdevalence/curve25519-dalek/commit/2ae0bdb6df26a74ef46d4332b635c9f6290126c7</a> (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 <a href="mailto:Curves@moderncrypto.org" class="">Curves@moderncrypto.org</a> https://moderncrypto.org/mailman/listinfo/curves </blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">_______________________________________________<br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">Curves mailing list<br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><a href="mailto:Curves@moderncrypto.org" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">Curves@moderncrypto.org</a><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><a href="https://moderncrypto.org/mailman/listinfo/curves" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">https://moderncrypto.org/mailman/listinfo/curves</a></div></blockquote></div> </body></html>