This year, the GPN included a CTF organized by squareroots. This post is about the service Espionage including an alternative solution.

The Service

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.