[curves] Compact square root algorithm for annoying primes
Mike Hamburg
mike at shiftleft.org
Fri Jan 22 13:56:35 PST 2016
> On Jan 22, 2016, at 4:20 AM, Michael Scott <mike.scott at miracl.com> wrote:
>
> Have a look at the references in http://www.google.com/patents/US9148282 <http://www.google.com/patents/US9148282>
>
> Particularly Siguna Mueller's Lucas-function based method..
Thanks! To your knowledge, is the Mueller method itself patented? I’ll check it out when I can get the right login.
> Not sure about the cost..
The abstract claims “expected cost = 1.33 * the number of multiplications for a square and multiply”, which would be 468 in this case.
I’ve also improved the splitting in my code, pasted below, which improves its worst-case time to 718 multiplies, with 7 elements in RAM and 2 in ROM plus still that pesky dlog table. A little tuning can save another few multiplies, but I went with simplicity instead. So it’s still presumably worse than the Mueller method, except perhaps in that it is deterministic.
> Mike
Thanks again,
— also Mike
>
>
> On Thu, Jan 21, 2016 at 11:30 PM, Mike Hamburg <mike at shiftleft.org <mailto:mike at shiftleft.org>> wrote:
> Hello Curves,
>
> 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.
>
> OpenSSL’s implementation takes something like 4700 multiplications on average, which is more than a point*scalar multiply.
>
> 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.
>
> 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).
>
> Cipolla’s algorithm is nondeterministic.
>
> 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?
>
> Is there some other algorithm I’m missing?
>
> Thanks,
> — Mike
>
> [1] http://cr.yp.to/papers/sqroot.pdf <http://cr.yp.to/papers/sqroot.pdf>
>
p = 2^224 - 2^96 + 1
F = GF(p)
qnr = 11^(2^128-1)
dlog_table = dict((
(qnr^(2^90*i),2^6-i) for i in xrange(2^6)
))
precmp = [qnr^2^66,qnr^2^84]
def isqrt(x):
s = x^3
s = s^2 * x # 2^3 - 1
u = s^2^3 * s # 2^6 - 1
s = u^2^6 * u # 2^12 - 1
t = s^2^12 * s # 2^24 - 1
s = t^2^24 * t # 2^48 - 1
s = s^2^48 * s # 2^96 - 1
s = s^2^24 * t # 2^120 - 1
s = s^2^6 * u # 2^126 - 1
s = s^2 * x
# here s == x^(2^127-1)
ret = [s]
rou = [qnr]
def leaf(r,n=6):
dlog = dlog_table[r]>>(tbits-n)
for i in xrange(len(ret)):
for j in xrange(n):
if dlog & (1<<j): ret[i] = ret[i] * rou[i]
rou[i] = rou[i]^2
def stage(m):
if len(ret) > 1:
return ret[-1]^2^(6*m)
else:
return (ret[-1]^2*x)^2^(6*m-1)
def descent(n):
for i in xrange(n-1,0,-1):
leaf(stage(i),6)
if len(ret) > 1:
rou.pop()
leaf(ret.pop(),6)
else:
leaf(ret[0]^2*x,5)
# Have to apply leaf() 96/6 = 16 times
# Split it as 11+5, 11=6+5, 6=4+2, 5=3+2
# Precomputed roots of unity for 2^(6*5) and 2^(6*2)
ret.append(stage(11)); rou.append(precmp[0])
ret.append(stage(3)); rou.append(precmp[1])
descent(2)
descent(3)
ret.append(stage(6)); rou.append(precmp[0])
ret.append(stage(3)); rou.append(precmp[1])
descent(2)
descent(3)
ret.append(stage(4)); rou.append(precmp[1])
descent(2)
descent(4)
return ret[0]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20160122/ab1bb4b1/attachment.html>
More information about the Curves
mailing list