Any thoughts anyone?
Facts:
- d is much much smaller than e.
- Can't factorize N with any factorization algorithm.
- N and e given.
How do I do?
I have an assignment to factor a 160 digit number on the form p*q, where p and q are primes. The number is N in RSA. I also got e, which is also about 160 digits, and the fact that d is much much smaller than e. I assume the latter information was given because we need to use it to factor N in reasonable time, but I can't figure out how to do this.
All I know is that e*d = 1 mod (p-1)(q-1). Can't seem to find a way to calculate neither d nor p or q, since there's too many unknown in the equation.
Any help would be very appreciated.
I think that there is a conjecture to the effect that any method of beating RSA is equivalent to factoring N? Thus making your assignment impossible. Unless you have the required computer power to factorise N.
Perhaps this paper might be interesting.
Breaking RSA may not be equivalent to factoring
I have not read it.
If your tutor has given you an answer, then please post it.