 |
|
| Science Forum Index » Cryptography Forum » question about multi-prime rsa... |
|
Page 1 of 1 |
|
| Author |
Message |
| yawnmoth... |
 Posted: Wed Nov 11, 2009 10:26 am |
|
|
|
Guest
|
From <http://tools.ietf.org/html/rfc3447#page-8>:
-----------------------
Each CRT coefficient t_i (i = 3, ..., u) is a positive integer less
than r_i satisfying
R_i * t_i == 1 (mod r_i) ,
where R_i = r_1 * r_2 * ... * r_(i-1).
-----------------------
So t_3 satisfies the following:
R_i * t_i == 1 (mod r_3)
Where R_i = r_1 * r_2
And t_2, the following:
R_i * t_i == 1 (mod r_2)
Where R_i = r_1
ie. r_1 * t_i == 1 (mod r_2)
Problem is, this seems to contract this (from the previous page on the
RFC):
-----------------------
In a valid RSA private key with the second representation, the two
factors p and q are the first two prime factors of the RSA modulus
n
(i.e., r_1 and r_2)
....
and the CRT coefficient qInv is a positive integer less than p
satisfying
q * qInv == 1 (mod p).
-----------------------
Replacing p with r_1 and q with r_2 gets us this:
r_2 * qInv == 1 (mod r_1)
....but aren't qInv and t_2 essentially supposed to be the same thing?
As is, they're not:
qInv == r_2 ** -1 (mod r_1)
t_2 == r_1 ** -1 (mod r_2) |
|
|
| Back to top |
|
|
|
| Arturo Magidin... |
| Posted: Wed Nov 11, 2009 11:13 am |
|
|
|
Guest
|
On Nov 11, 2:26 pm, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
[quote]From <http://tools.ietf.org/html/rfc3447#page-8>:
-----------------------
Each CRT coefficient t_i (i = 3, ..., u) is a positive integer less
than r_i satisfying
R_i * t_i == 1 (mod r_i) ,
where R_i = r_1 * r_2 * ... * r_(i-1).
-----------------------
So t_3 satisfies the following:
R_i * t_i == 1 (mod r_3)
[/quote]
You mean R_3 * t_3 == 1 (mod r_3)
[quote]
Where R_i = r_1 * r_2
[/quote]
R_3 = r_1 * r_2.
[quote]And t_2, the following:
R_i * t_i == 1 (mod r_2)
Where R_i = r_1
[/quote]
Ehr... the definition above is for t_i, i=3,...,u. It does not specify
how to define t_1 or t_2. Could that be the source of the problem?
--
Arturo Magidin |
|
|
| Back to top |
|
|
|
| yawnmoth... |
| Posted: Wed Nov 11, 2009 11:45 am |
|
|
|
Guest
|
On Nov 11, 3:13 pm, Arturo Magidin <magi... at (no spam) member.ams.org> wrote:
[quote]On Nov 11, 2:26 pm, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
From <http://tools.ietf.org/html/rfc3447#page-8>:
-----------------------
Each CRT coefficient t_i (i = 3, ..., u) is a positive integer less
than r_i satisfying
R_i * t_i == 1 (mod r_i) ,
where R_i = r_1 * r_2 * ... * r_(i-1).
-----------------------
So t_3 satisfies the following:
R_i * t_i == 1 (mod r_3)
You mean R_3 * t_3 == 1 (mod r_3)
[/quote]
Yup - that is indeed what I meant.
[quote]Where R_i = r_1 * r_2
R_3 = r_1 * r_2.
And t_2, the following:
R_i * t_i == 1 (mod r_2)
Where R_i = r_1
Ehr... the definition above is for t_i, i=3,...,u. It does not specify
how to define t_1 or t_2. Could that be the source of the problem?
[/quote]
I think the problem is more like... it seems to me like the
hypothetical t_2 ought to be the same as qInv. As is, it's like t_2
(or rather, it's equivalent, qInv) is being defined differently from
t_i, i > 2. Also, t_1 can't exist because then R_i would be equal to
the non-existent r_0.
Also, imho, qInv being defined differently from t_i, i > 2 just isn't
as elegant. If t_2 == qInv, you could use the same code to generate
all t_i, i > 1, but as is, you have to have separate code to calculate
qInv and t_i, i > 2. |
|
|
| Back to top |
|
|
|
| Arturo Magidin... |
| Posted: Wed Nov 11, 2009 11:55 am |
|
|
|
Guest
|
On Nov 11, 3:45 pm, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
[quote]On Nov 11, 3:13 pm, Arturo Magidin <magi... at (no spam) member.ams.org> wrote:
On Nov 11, 2:26 pm, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
From <http://tools.ietf.org/html/rfc3447#page-8>:
-----------------------
Each CRT coefficient t_i (i = 3, ..., u) is a positive integer less
than r_i satisfying
R_i * t_i == 1 (mod r_i) ,
where R_i = r_1 * r_2 * ... * r_(i-1).
-----------------------
So t_3 satisfies the following:
R_i * t_i == 1 (mod r_3)
You mean R_3 * t_3 == 1 (mod r_3)
Yup - that is indeed what I meant.
Where R_i = r_1 * r_2
R_3 = r_1 * r_2.
And t_2, the following:
R_i * t_i == 1 (mod r_2)
Where R_i = r_1
Ehr... the definition above is for t_i, i=3,...,u. It does not specify
how to define t_1 or t_2. Could that be the source of the problem?
I think the problem is more like... it seems to me like the
hypothetical t_2 ought to be the same as qInv.
[/quote]
And as far as I can tell, it *is*: they define t_1 and t_2 in the case
of two primes, then explain how to expand it if there are more primes:
start the same way, and once you have the first two, you continue
"this way". So they only need to define t_3, t_4, ... etc.
[quote] As is, it's like t_2
(or rather, it's equivalent, qInv) is being defined differently from
t_i, i > 2. Also, t_1 can't exist because then R_i would be equal to
the non-existent r_0.
[/quote]
"t_1 can't exist" only if you insist on taking a definition that is
being given *explicitly as not applying to t_1 and t_2* and apply it
to t_1 and t_2 regardless of the instructions. Yes: t_1 and t_2 are
being defined differently: they are defined the way they are when the
RSA modulus is just a product of two primes.
[quote]Also, imho, qInv being defined differently from t_i, i > 2 just isn't
as elegant.
[/quote]
That would be a problem of elegance, yes, but not with the system.
In a regular CRT application, you would pick t_i so that
R_i*t_i == a_i (mod r_i),
but the R_i would be equal to R_i = r_1*r_2 *...*r_{i-1}*r_{i+1}
*...*r_u. Possibly what is happening is that you have a *better*
algorithm by doing things differently.
[quote] If t_2 == qInv, you could use the same code to generate
all t_i, i > 1, but as is, you have to have separate code to calculate
qInv and t_i, i > 2.
[/quote]
And maybe that speeds it up? The usual proof of the CRT gives you an
algorithm for computing the solution, but a "successive solution"
process gives you a solution that is computationally easier (at least
by hand): instead of computing R_i as I defined them above for each i,
then solving each R_i * t_i == a_i (mod r_i), and then setting x
=R_1*t_1+...+R_u*t_u, a method which is easier on the hand is to start
with x=a_1 (mod r_1), which gives x=a_1 + x_1*r_1. Substitute that
into x==a_2 (mod r_2), and solve for x_1. Then substitute that back
into x, and into x==a_3 (mod r_3), and so on. While this process is
not symmetric on the congruences and is, perhaps, less elegant, it
works and is faster for most people doing it by hand than the elegant
and symmetric method of the CRT proof.
--
Arturo Magidin
-- |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Mon Mar 22, 2010 9:08 am
|
|