# Factorize RSA knowing several N and E

I did a CRT challenge yesterday and theres one problem I was unable to solve, probably due to my lack of understanding advanced crypto math.

Its about RSA. There are ten given pairs of N and E (modulo and exponent). E is always the standard exponent 10001 (hex). N is a 2048 bit number.

Well, I tried everything known to me (CRT, Wiener, p-1), no luck. Now it occurred to me that maybe 10 pairs aren't given to keep you busy but that maybe the vulnerability is located there?

Any ideas?

no, I don't have the data anymore. :)

-
Did they publish an exponent pair (e,d)? – CodesInChaos Dec 7 '12 at 11:21
There is no solution to the problem as you describe it. Perhaps some of the moduli were badly created and contain common factors. – CodesInChaos Dec 7 '12 at 11:26
@Ionelysis: The gcd of two integers is always a factor of those. So if it is not 1 (and the integers are not identical), you got a factor, and can now calculate other factors. This will only work if those numbers were generated by a bad RNG, though. – Paŭlo Ebermann Dec 7 '12 at 13:08
For the deterministic algorithm, see $\:$ www.math.dartmouth.edu/~carlp/aks041411.pdf . $\hspace{.7 in}$ – Ricky Demer Dec 7 '12 at 22:38
Why do you care if the factors are prime? RSA is always done using a product of two (probable) primes, so any nontrivial factor will be prime. – Antimony Dec 10 '12 at 7:09

Now as you're given RSA moduli, which are always constructed as $n=pq$, you can be sure that if you find $gcd(n_1,n_2)=R>1$, than either $R=p$ or $R=q$ must hold.
As you pointed out in the comments you indeed found such an $R_1$ for $n_1,n_2$. Now you reconstruct $P_1=n/R_1$ and check if $P_1*R_1=n$ holds, which is the case.
In the next step you check wether $P_1$ or $R_1$ divide any of the other moduli.
If it does, you reconstruct the other prime of these moduli via $n/R_1$. You repeat this procedure for all factors you're given.