RSA CRT key?
massimo piccinetti
can you tell me where i can find
the documentation of the algorithm ([Mil76])
to convert a RSAPrivateKey (modulus + private exponent only)
to a RSAPrivateCRTKey (modulus, exponent, p, q etc..)
thanks
Doug Stell
<massimo.p...@etaisdn.inet.it> wrote:
>Hello,
>can you tell me where i can find
>the documentation of the algorithm ([Mil76])
>to convert a RSAPrivateKey (modulus + private exponent only)
>to a RSAPrivateCRTKey (modulus, exponent, p, q etc..)
Instead of discarding the primes, P and Q, and using only the
private exponent, D, the primes are retained and two related key
components are computed. These are the multiplicative inverses
of P and Q, P1 and Q1, using Euclid's Theorem, such that
(P*P1) (mod Q) = 1 and (Q*Q1) (mod P) = 1.
P1 = inverse of P: P1 = (P)^(Q-2) (mod Q)
Q1 = inverse of Q: Q1 = (Q)^(P-2) (mod P)
The private exponents (mod P-1) and (mod Q-1) are also computed.
Private Exponent D = 107: = 7 (mod 10) = 11 (mod 16)
The CRT method private key is:
[N, P, Q, P1, Q1, D (mod P-1), D (mod Q-1)]
Mark Wooding
> can you tell me where i can find the documentation of the algorithm
> ([Mil76]) to convert a RSAPrivateKey (modulus + private exponent only)
> to a RSAPrivateCRTKey (modulus, exponent, p, q etc..)
You need the modulus n and both the private exponent d and the public
one e. If you don't have the public exponent, you can try guessing that
it's one of the common ones (3, 17 or 65537 = 2^{16} + 1) until the
algorithm works.
The initial objective is to factor the modulus. The following algorithm
will do this.
Compute z = e d - 1. Since e d = 1 (mod \lambda(n)), we know that x^z =
1 (mod n) for all x. Also, since \lambda(n) is even (since p - 1 is
even, and \lambda(n) = \lcm(p - 1, q - 1)), we can write z = 2^s t,
where s > 0 and t is odd.
Invent some x at random, and compute x_0 = x^t. If x_0 = 1 (mod n) then
choose another x and try again. Now let x_{i+i} = x_i^2 for 0 <= i < s.
We know that x_s = 1 (mod n). Find x_j such that x_j != 1 but x_{j+1} =
1 (both mod n). If x_j = -1 (mod n) then we lose, so try again with a
different x. Otherwise, x_j is a nontrivial square root of 1 (mod n),
so \gcd(x_j - 1, n) is a nontrivial factor of n. Call it p and find q =
n/p.
(Why does this work? In order for y do be a square root of 1 (mod p q),
it must be a square root of 1 mod each of p and q -- the Chinese
Remainder Theorem makes this obvious. The only square roots of 1 mod p
are 1 and -1, and similarly for q. When we find a square root y of 1,
then, we have four cases:
1. y = 1 (mod p); y = 1 (mod q)
2. y = -1 (mod p); y = -1 (mod q)
3. y = 1 (mod p); y = -1 (mod q)
4. y = -1 (mod p); y = 1 (mod q)
Cases 1 and 2 are trivial and unhelpful. In these cases, we just have
to try again. Let's assume we're in case 3, then (case 4 is symmetric
anyway). We have y - 1 = 0 (mod p) and y - 1 = -2 (mod q). Assuming
that q > 2, then, y is a multiple of p (so it has a large common factor
with n) and is not a multiple of q. Hence \gcd(y - 1, n) is an
interesting factor of n.)
Now you're home and dry. All you need to do is compute d mod (p - 1), d
mod (q - 1) and q mod p.
-- [mdw]
Bryan Olson
>Hello,
>can you tell me where i can find
>the documentation of the algorithm ([Mil76])
>to convert a RSAPrivateKey (modulus + private exponent only)
>to a RSAPrivateCRTKey (modulus, exponent, p, q etc..)
You need the public exponent too, (which is also in the
RSAPrivateKey).
While raising a random base to e*d-1, see if you get a
non-trivial square root of 1 along the way. If so, take the
gcd(n, square_root1 + 1) and that's a factor. If not,
repeat.
Below is Python code (which I posted once before).
--Bryan
|
| # Python code for factoring RSA modulus n using e and d
|
| def gcd(x, y):
| """Return the GCD of x and y."""
| while x>0:
| x, y = y%x, x
| return y
|
| def split_using_e_and_d(n, e, d):
| """Given a composite n and e, d such that
| e*d mod lambda(n) == 1, return a non-trival factor of n.
| Loops out or asserts false on bad inputs.
| """
| s = e * d - 1
| # Remove factors of 2 from exponent s
| while s & 1 == 0:
| s = s >> 1
| # Try bases until we find a factor
| for base in xrange(1, 999, 2):
| # Realy we should set base randomly
| a = pow(long(base), s, n)
| if a == 1:
| # Darn, we got to 1 without finding a square root
| continue
| # Keep squaring until we hit 1.
| while a != 1 and a != n-1:
| b = a
| a = a * a % n
| if a == 1:
| # Got it
| return gcd(n, b + 1)
| # Darn, the square root we found was -1.
| assert(0), "Something is very wrong."
|
massimo piccinetti
now i'm going to programm my JavaRing.