Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

It`s 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.

The task: factorize all N.

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. :)

share|improve this question
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 $\:$ . $\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

If the moduli share no commonness / weak properties, it's impossible to solve the problem as given at hand. (As CodesInChaos pointed out)

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.
As soon as you've done this step and still have unfactored moduli left, you try to apply the GCD on all pairs of unfactored moduli and use the resulting factors to obtain the remaing factors and factor the remaining moduli.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.