PDA

View Full Version : RSA - More than 2 primes


jandis
August 20th, 2004, 00:51
I searched the forums and google but nothing seemed to turn up, except that yes there is a possibility of there being 3-4 primes. Here is the problem:

x = x^d mod n

Known
-----
N = 968b80866737a48f5d6798ae96f16f93f19f, base 16
D = 1024

When trying to use N to find p&q I get 4 prime factors:
3, 1D, 5AEE72489D, 4DF055177D4679B

So the problem is p & q are needed in order to find e in the equation e = d^(-1) mod ((p-1)(q-1)). Any help would be appreciated and please excuse my crypto ignorance.

mike
August 20th, 2004, 02:53
What you need to do is compute d^-1 mod (p-1)(q-1)(r-1)(s-1). Which is impossible, since p-1=3-1=2, and 1024 doesn't have an inverse modulo an even number. So your numbers can't be right.