 |
|
| Science Forum Index » Cryptography Forum » modular exponentiation with barrett reduction vs.... |
|
Page 1 of 1 |
|
| Author |
Message |
| yawnmoth... |
 Posted: Mon Nov 02, 2009 9:18 am |
|
|
|
Guest
|
The bnModPow function in <http://www-cs-students.stanford.edu/~tjw/
jsbn/jsbn2.js> claims to implement the modular exponentiation
algorithm described in HAC 14.85. Only problem is that it doesn't
look anything like HAC 14.85. I've tried modifying it to look more
similar and although it works with barrett reduction it doesn't work
with montgomery reduction.
First, here's what I'm using to test it:
http://pastebin.com/m53de665f
When using bnModPow's original implementation, I get the correct
answer.
Here's my rewritten bnModPow:
http://pastebin.com/m420d20a4
The problem occurs when I replace "z = new Barrett(m);" with "z = new
Montgomery(m);".
Here are debug versions of each implementation:
http://pastebin.com/m55e36527
http://pastebin.com/d1fe4fe32
The former (mine) and the latter (the original) have a matching g[31],
which suggests to me that montgomery reduction is being implemented
correctly. The windows are the same, as well, despite being
calculated differently. The only difference I see, for sure, is that
the number of times squaring takes place is different for each
implementation. In my implementation it takes place 504 times and in
the original implementation it takes place 476 times. That (and the
fact that the only function that was changed) makes me think that my
modular exponentiation routine is bad, but if that were the case, why
would I be getting the correct answer with barrett reduction?
Anyway, I'm at a loss. Any ideas would be appreciated - thanks! |
|
|
| Back to top |
|
|
|
| yawnmoth... |
| Posted: Mon Nov 02, 2009 1:49 pm |
|
|
|
Guest
|
On Nov 2, 1:18 pm, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
[quote]The bnModPow function in <http://www-cs-students.stanford.edu/~tjw/
jsbn/jsbn2.js> claims to implement the modular exponentiation
algorithm described in HAC 14.85. Only problem is that it doesn't
look anything like HAC 14.85. I've tried modifying it to look more
similar and although it works with barrett reduction it doesn't work
with montgomery reduction.
First, here's what I'm using to test it:
http://pastebin.com/m53de665f
When using bnModPow's original implementation, I get the correct
answer.
Here's my rewritten bnModPow:
http://pastebin.com/m420d20a4
The problem occurs when I replace "z = new Barrett(m);" with "z = new
Montgomery(m);".
Here are debug versions of each implementation:
http://pastebin.com/m55e36527http://pastebin.com/d1fe4fe32
The former (mine) and the latter (the original) have a matching g[31],
which suggests to me that montgomery reduction is being implemented
correctly. The windows are the same, as well, despite being
calculated differently. The only difference I see, for sure, is that
the number of times squaring takes place is different for each
implementation. In my implementation it takes place 504 times and in
the original implementation it takes place 476 times. That (and the
fact that the only function that was changed) makes me think that my
modular exponentiation routine is bad, but if that were the case, why
would I be getting the correct answer with barrett reduction?
Anyway, I'm at a loss. Any ideas would be appreciated - thanks!
[/quote]
Well, I've had one idea, but that doesn't seem to have helped. In
particular, I noticed that one can potentially be squared and reduced
several times. With barrett reduction this isn't a problem since if
you square and reduce one, you still get one. With montgomery
reduction, however, this is a problem. You square one, get one, and
then reduce one, and what you get won't be one. Do that again and
you'll that much further away from one than you were before.
To remedy this, I added a check before each squaring to see if the
number being squared is one. If it is, no squaring takes place.
Unfortunately, this still doesn't work. Here's the latest code:
http://pastebin.com/mee48c5c
Any ideas? |
|
|
| Back to top |
|
|
|
| Tom St Denis... |
| Posted: Mon Nov 02, 2009 2:01 pm |
|
|
|
Guest
|
On Nov 2, 6:49 pm, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
[quote]On Nov 2, 1:18 pm, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
The bnModPow function in <http://www-cs-students.stanford.edu/~tjw/
jsbn/jsbn2.js> claims to implement the modular exponentiation
algorithm described in HAC 14.85. Only problem is that it doesn't
look anything like HAC 14.85. I've tried modifying it to look more
similar and although it works with barrett reduction it doesn't work
with montgomery reduction.
First, here's what I'm using to test it:
http://pastebin.com/m53de665f
When using bnModPow's original implementation, I get the correct
answer.
Here's my rewritten bnModPow:
http://pastebin.com/m420d20a4
The problem occurs when I replace "z = new Barrett(m);" with "z = new
Montgomery(m);".
Here are debug versions of each implementation:
http://pastebin.com/m55e36527http://pastebin.com/d1fe4fe32
The former (mine) and the latter (the original) have a matching g[31],
which suggests to me that montgomery reduction is being implemented
correctly. The windows are the same, as well, despite being
calculated differently. The only difference I see, for sure, is that
the number of times squaring takes place is different for each
implementation. In my implementation it takes place 504 times and in
the original implementation it takes place 476 times. That (and the
fact that the only function that was changed) makes me think that my
modular exponentiation routine is bad, but if that were the case, why
would I be getting the correct answer with barrett reduction?
Anyway, I'm at a loss. Any ideas would be appreciated - thanks!
Well, I've had one idea, but that doesn't seem to have helped. In
particular, I noticed that one can potentially be squared and reduced
several times. With barrett reduction this isn't a problem since if
you square and reduce one, you still get one. With montgomery
reduction, however, this is a problem. You square one, get one, and
then reduce one, and what you get won't be one. Do that again and
you'll that much further away from one than you were before.
To remedy this, I added a check before each squaring to see if the
number being squared is one. If it is, no squaring takes place.
Unfortunately, this still doesn't work. Here's the latest code:
http://pastebin.com/mee48c5c
Any ideas?
[/quote]
Not reading your code [I have better things to do sorry...], but in
Montgomery you end up with 1R*1R == 1R^2 when reduced is 1R. So
really in montgomery space if you square "unity" you end up with
unity. If you're not then your montgomery code is broken.
Also, leaving aside single digit mults/squares your expmod function
should have the same # of bigint square/multiplies regardless of the
number system used [straight integers like Barett or Montgomery
space]. The only thing that changes the number of bigint operations
is the exponentiation algorithm.
I would first test your primitives outside an exptmod, then get back
to it.
Also if you're just going to model your stuff after another piece of
code so closely you might as well use it. If you're trying to learn
how to write bignum code it's not a good idea to look at other
libraries so closely. |
|
|
| Back to top |
|
|
|
| yawnmoth... |
| Posted: Mon Nov 02, 2009 5:25 pm |
|
|
|
Guest
|
On Nov 2, 6:01 pm, Tom St Denis <t... at (no spam) iahu.ca> wrote:
[quote]On Nov 2, 6:49 pm, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
On Nov 2, 1:18 pm, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
The bnModPow function in <http://www-cs-students.stanford.edu/~tjw/
jsbn/jsbn2.js> claims to implement the modular exponentiation
algorithm described in HAC 14.85. Only problem is that it doesn't
look anything like HAC 14.85. I've tried modifying it to look more
similar and although it works with barrett reduction it doesn't work
with montgomery reduction.
First, here's what I'm using to test it:
http://pastebin.com/m53de665f
When using bnModPow's original implementation, I get the correct
answer.
Here's my rewritten bnModPow:
http://pastebin.com/m420d20a4
The problem occurs when I replace "z = new Barrett(m);" with "z = new
Montgomery(m);".
Here are debug versions of each implementation:
http://pastebin.com/m55e36527http://pastebin.com/d1fe4fe32
The former (mine) and the latter (the original) have a matching g[31],
which suggests to me that montgomery reduction is being implemented
correctly. The windows are the same, as well, despite being
calculated differently. The only difference I see, for sure, is that
the number of times squaring takes place is different for each
implementation. In my implementation it takes place 504 times and in
the original implementation it takes place 476 times. That (and the
fact that the only function that was changed) makes me think that my
modular exponentiation routine is bad, but if that were the case, why
would I be getting the correct answer with barrett reduction?
Anyway, I'm at a loss. Any ideas would be appreciated - thanks!
Well, I've had one idea, but that doesn't seem to have helped. In
particular, I noticed that one can potentially be squared and reduced
several times. With barrett reduction this isn't a problem since if
you square and reduce one, you still get one. With montgomery
reduction, however, this is a problem. You square one, get one, and
then reduce one, and what you get won't be one. Do that again and
you'll that much further away from one than you were before.
To remedy this, I added a check before each squaring to see if the
number being squared is one. If it is, no squaring takes place.
Unfortunately, this still doesn't work. Here's the latest code:
http://pastebin.com/mee48c5c
Any ideas?
Not reading your code [I have better things to do sorry...], but in
Montgomery you end up with 1R*1R == 1R^2 when reduced is 1R. So
really in montgomery space if you square "unity" you end up with
unity. If you're not then your montgomery code is broken.
Also, leaving aside single digit mults/squares your expmod function
should have the same # of bigint square/multiplies regardless of the
number system used [straight integers like Barett or Montgomery
space]. The only thing that changes the number of bigint operations
is the exponentiation algorithm.
I would first test your primitives outside an exptmod, then get back
to it.
[/quote]
I actually figured it out... in the original description of sliding-
window exponentiation I was consulting, it says to assign 1 to A and g
to g[1]. Both have to have the preliminary montgomery step performed
on them and I was only doing it on one.
Thanks for the feedback! |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Sat Dec 05, 2009 9:24 pm
|
|