question about multi-prime rsa
- From: yawnmoth <terra1024@xxxxxxxxx>
- Date: Wed, 11 Nov 2009 12:26:16 -0800 (PST)
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)
.
- Follow-Ups:
- Re: question about multi-prime rsa
- From: Arturo Magidin
- Re: question about multi-prime rsa
- Prev by Date: test
- Next by Date: Re: question about multi-prime rsa
- Previous by thread: test
- Next by thread: Re: question about multi-prime rsa
- Index(es):