We had a telnet decryption service and a screenshot indicating we would have to deal with RSA. The screenshot also included an encrypted version of a flag.txt, 31319528277563551791166984607206341790, so this was our target.
The Way It Was Meant To Be
Well, we had the decryption service, so why not try that one?
>> Go ahead: give me your encrypted number: 31319528277563551791166984607206341790 The truth? You can't handle the truth!
Looks like they installed a check for that special number preventing us from decrypting flag.txt. So how can we bypass that check? The easiest way would be by adding a leading zero:
>> Go ahead: give me your encrypted number: 031319528277563551791166984607206341790 Congratulations! Hash this number 3133734221 for the flag.
So we’re done here.
The Hard Way
That was a bit too easy, right? Well, actually, I just didn’t had the idea to try it with the leading zero. So let’s use more math!
As one can read on Wikipedia, if we have a message m, its encrypted form c and a number r and we decrypt c*r^e, we get m*r. Using algorithms for fast exponentiation
def eExpo(x,y,n): # returns x**y % n r=1 b=x ys= while y!=0: ys.append( y % 2 ) y = y // 2 for i in ys: if i == 1: r=r*b % n b=b*b % n return r
and inverting (modulo N)
def inverseElem(x, n): # returns x^(-1) in n (d, x, y) = extEukl(x,n) return x % n def extEukl(a,b): # returns (d, x, y) d gcd, ax+by=d if b == 0: return (a, 1, 0) x2=1 x1=0 y2=0 y1=1 while b>0: q=a // b r=a % b x=x2-q*x1 y=y2-q*y1 a=b b=r x2=x1 x1=x y2=y1 y1=y return (a, x2, y2)
we can get m (I set r to 2). As above, the result is 3133734221.
A third way is to factorize N into p and q and using them to get the secret key. sage mathematics needs less than 2 seconds to find them.