Tags: crt rsa 

Rating: 1.0

c4ptur3th3crypt0 – Nov. 9, 2016, 9:24 a.m.

Can't really blame the author in this case, that's not at all how to use CRT, no wonder your code never finished.

Judging by the size of that mod and the small e, d is going to be similarly large. The whole point of using CRT with RSA is the reduce the size of the exponent used in decryption, and you can only do this given the factrs of n, which is available here. In your explanation you say that you calculate c^d mod p1 and so on, this doesn't help with anything if the exponent size is the same, so you're doing far more work than you need to. Given a factor p, CRT allows you to reduce d mod phi(p) during that step, so you instead calculate c^(d mod phi(p)) mod p, which is far less work, and then the steps are trivial to combine. A simple explanation of what I mean here with just pq as factors is here: http://www.di-mgt.com.au/crt_rsa.html . Since n was easy to factor here, I'd say this problem is very feasible, and probably wouldn't take long to calculate, but you seem to have missed the point.


mad_damon – Nov. 12, 2016, 3:42 p.m.

Oh, c'mon. You can't always blame the author and state "This was a very badly designed task" because you think you have rights to judge since you are one of the top ten teams. Please remember 'a very badly designed task' is not the same as 'a task that make me annoyed'.

Solution in https://ctftime.org/writeup/4696 just need 30 seconds.