1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Did they publish an exponent pair (e,d)? $\endgroup$ – CodesInChaos Dec 7 '12 at 11:21
  • 3
    $\begingroup$ There is no solution to the problem as you describe it. Perhaps some of the moduli were badly created and contain common factors. $\endgroup$ – CodesInChaos Dec 7 '12 at 11:26
  • 1
    $\begingroup$ @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. $\endgroup$ – Paŭlo Ebermann Dec 7 '12 at 13:08
  • 1
    $\begingroup$ For the deterministic algorithm, see $\:$ www.math.dartmouth.edu/~carlp/aks041411.pdf . $\hspace{.7 in}$ $\endgroup$ – user991 Dec 7 '12 at 22:38
  • 1
    $\begingroup$ 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. $\endgroup$ – Antimony Dec 10 '12 at 7:09
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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