On Wed, May 11, 2011 at 08:01:28PM -0400, Nick Mathewson wrote:
> On Wed, May 11, 2011 at 6:10 PM, Ian Goldberg <[email protected]> wrote:
> [...]
> > Remember also that if you have non-black-box access to the
> > exponentiation routine, the server can compute X^y and X^b
> > simultaneously. That will make a bigger difference in time, but is not
> > really relevant from a spec-level standpoint.
>
> Can you expand on how this would work? I didn't ask the first time
> you told me this, on the theory that I could figure it out if I
> thought about it for long enough, but several days later I still don't
> have it. All the ways I can think of are inefficient,
> non-constant-time, or both.
Use right-to-left exponentiation. This is totally off the top of my
head.
def exp(base,expon):
a = base
mask = 1
res = 1
# Invariant: a = base^mask
do:
# Be a little cleverer about the if if you
# care about constant-time; just save the output
# somewhere useless
if (expon & mask): # bitwise and
res = res*a
a *= a
mask <<= 1
until (mask is larger than the maximum possible expon)
return res
Then exp2(base, expon1, expon2) will be:
def exp2(base,expon1, expon2):
a = base
mask = 1
res1 = 1
res2 = 1
# Invariant: a = base^mask
do:
# Be a little cleverer about the if if you
# care about constant-time; just save the output
# somewhere useless
if (expon1 & mask): # bitwise and
res1 = res1*a
if (expon2 & mask): # bitwise and
res2 = res2*a
a *= a
mask <<= 1
until (mask is larger than the maximum possible expon)
return (res1, res2)
The idea is that the squarings are common between the exps, and just the
multiplications have to be done separately.
- Ian
_______________________________________________
tor-dev mailing list
[email protected]
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
