Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 0 down vote favorite

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
i dont think so, only N and E like this: 10001 <...N1...> 10001 <...N2...> 10001 <...N3...> – lonelyis Dec 7 '12 at 11:23
3  
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
1  
For the deterministic algorithm, see $\:$ www.math.dartmouth.edu/~carlp/aks041411.pdf . $\hspace{.7 in}$ – Ricky Demer Dec 7 '12 at 22:38
1  
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
show 7 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.