<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=""><br class=""></div><div><blockquote type="cite" class=""><div class="">On Jan 30, 2017, at 12:41 PM, Antonio Sanso <<a href="mailto:asanso@adobe.com" class="">asanso@adobe.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252" class="">
<div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
Thanks a lot Trevor,
<div class=""><br class="">
</div>
<div class="">this was a great write up.</div>
<div class="">One more question</div>
<div class=""><br class="">
<div class="">
<div class="">On Nov 7, 2016, at 12:51 AM, Trevor Perrin <<a href="mailto:trevp@trevp.net" class="">trevp@trevp.net</a>> wrote:</div>
<br class="Apple-interchange-newline">
<blockquote type="cite" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">However,
cofactor>1 can still have subtle and unexpected effects, e.g.</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">see
security considerations about "equivalent" public keys in RFC</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">7748,
which is relevant to the cofactor multiplication "cV" in</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">VXEdDSA,
or including DH public keys into "AD" in Signal's (recently</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">published)
X3DH [3].</span></blockquote>
<br class="">
</div>
<div class="">may you shed some more light about this?</div>
<div class="">What is the algorithm to find and “equivalent” public key?</div>
<div class=""><br class="">
</div>
<div class="">regards</div>
<div class=""><br class="">
</div>
<div class="">antonio</div></div></div></div></blockquote></div><br class=""><div class="">There are two degrees of freedom in making X25519 public keys equivalent.</div><div class=""><br class=""></div><div class="">First, the standard specifies that public keys must be treated the same as if they were reduced modulo p = 2^255-19. That means that if x is a public key computed by the standard algorithm, then x+p is an equivalent public key, and x+2p is too if that fits in 32 bytes. The same is true for p=2^448-2^224-1, except that for this prime, x+p is too large to write down in 56 bytes for almost every x.</div><div class=""><br class=""></div><div class="">Second, two x’s are equivalent if they differ by a c-torsion point. This is because the X25519 Diffie-Hellman key exchange algorithm is computing c*secret*P, which is the same as c*secret*(P+T) for points T such that c*T is the identity. Another way to describe these equivalent keys is that they’re the x-coordinates of points Q such that c*Q = c*P. Such keys can be found in SAGE by computing</div><div class=""><br class=""></div><div class="">[P.xy()[0] for P in (c*E.lift_x(x)).division_points(c)]</div><div class=""><br class=""></div><div class="">where the cofactor c is 8 for X25519 and 4 for X448. One of these points will always be 1/x modulo p. There are surely somewhat-less-nice formulas for the rest of them.</div><div class=""><br class=""></div><div class="">Of course, these two classes can be combined, so that P.xy()[0] + p is also an equivalent public key.</div><div class=""><br class=""></div><div class="">Cheers,</div><div class="">— Mike</div></body></html>