PDA

View Full Version : RSA - More than 2 primes


jandis
08-20-2004, 01:51 AM
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
08-20-2004, 03:53 AM
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.