<div dir="ltr"><span style="font-size:12.8px">Have a look at the references in </span><a href="http://www.google.com/patents/US9148282" target="_blank" style="font-size:12.8px">http://www.google.com/patents/US9148282</a><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Particularly Siguna Mueller's Lucas-function based method..</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Not sure about the cost..</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Mike</div><div style="font-size:12.8px"><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jan 21, 2016 at 11:30 PM, Mike Hamburg <span dir="ltr"><<a href="mailto:mike@shiftleft.org" target="_blank">mike@shiftleft.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word">Hello Curves,<div><br></div><div>I was porting an embedded EC library to work with other curves, and I was wondering if anyone knew a compact, fast, deterministic algorithm for square roots mod NIST p224 (or other annoying primes)? I’m not worried about constant-time operation, since I probably have to blind anyway to reduce other side channels, but a deterministic algorithm is preferable because of possible real-time constraints.</div><div><br></div><div>OpenSSL’s implementation takes something like 4700 multiplications on average, which is more than a point*scalar multiply.</div><div><br></div><div>Dan’s paper [1] gives a variant of the Tonelli-Shanks algorithm which is fast and deterministic, requiring only 364 multiplies. But it’s very heavy, with 1024 precomputed elements. Reducing the table size makes the algorithm considerably slower.</div><div><br></div><div>I’ve tried to combine Dan’s Tonelli-Shanks variant with Sutherland’s algorithm, below. A variant with 4 precomputed points, a 64-element discrete log table (not as big as it sounds) and 10 or so field elements in memory takes 900 multiplies worst-case (~760 average-case).</div><div><br></div><div>Cipolla’s algorithm is nondeterministic.</div><div><br></div><div>Is Pocklington the way to go? It’s technically nondeterministic as well, but if I read [1] correctly the failure probability is 2^-96. A straightforward implementation probably takes more than 900 multiplies, but hopefully it’s simpler and uses less memory, right?</div><div><br></div><div>Is there some other algorithm I’m missing?</div><div><br></div><div>Thanks,</div><div>— Mike</div><div><br></div><div>[1] <a href="http://cr.yp.to/papers/sqroot.pdf" target="_blank">http://cr.yp.to/papers/sqroot.pdf</a></div><div><br></div><div>####################################################</div><div><br></div><div><div>p = 2^224 - 2^96 + 1</div><div>F = GF(p)</div><div>qnr = F(11)^(2^128-1)</div><div><br></div><div># 3-element precomputed table with roots of unity</div><div>precmp = dict((</div><div> (3*2^i, qnr^2^(96-3*2^i))</div><div> for i in [2,3,4]</div><div>))</div><div><br></div><div># 64-element discrete log table</div><div>tbits = 6</div><div>tlogger = qnr^2^(96-tbits)</div><div>dlog_table = dict((</div><div> (tlogger^i,2^tbits-i) for i in xrange(2^tbits)</div><div>))</div><div><br></div><div>def isqrt(x):</div><div> # inverse square root of x, assuming x is a QR</div><div> # First, DJB’s addition chain</div><div> s = x^3</div><div> s = s^2 * x # 2^3 - 1</div><div> u = s^2^3 * s # 2^6 - 1</div><div> s = u^2^6 * u # 2^12 - 1</div><div> t = s^2^12 * s # 2^24 - 1</div><div> s = t^2^24 * t # 2^48 - 1</div><div> s = s^2^48 * s # 2^96 - 1</div><div> s = s^2^24 * t # 2^120 - 1</div><div> s = s^2^6 * u # 2^126 - 1</div><div> s = s^2 * x</div><div> # here s == x^(2^127-1)</div><div> </div><div> ret = [s,s^2*x] # working powers of return value</div><div> rou = [qnr,qnr^2] # working roots of unity</div> stack = [95]<div> </div><div> def leaf(n):</div><div> dlog = dlog_table[ret.pop()]>>(tbits-n)</div><div> for i in xrange(len(rou)):</div><div> for j in xrange(n):</div><div> if dlog & (1<<j): ret[i] = ret[i] * rou[i]</div><div> rou[i] = rou[i]^2</div><div> </div><div> # max stack depth is 4, so 5+5 field elements in ret+rou</div><div> while len(stack):</div><div> n = stack.pop()</div><div> ret.append(ret[-1]^2^floor(n/2))</div><div> </div><div> if n <= 2*tbits:</div><div> leaf(ceil(n/2))</div><div> rou.pop()</div><div> leaf(floor(n/2))</div><div> else:</div><div> rou.append(precmp[ceil(n/2)])</div><div> stack.append(floor(n/2))</div><div> stack.append(ceil(n/2))</div><div> </div><div> return ret[0]</div></div></div><br>_______________________________________________<br>
Curves mailing list<br>
<a href="mailto:Curves@moderncrypto.org">Curves@moderncrypto.org</a><br>
<a href="https://moderncrypto.org/mailman/listinfo/curves" rel="noreferrer" target="_blank">https://moderncrypto.org/mailman/listinfo/curves</a><br>
<br></blockquote></div><br></div>