This is going to be the first in a series of write ups detailing some of the challenges I solved for picoCTF 2022. I'll detail some of the math and algorithms necessary to solve the challenges, most of which are cryptography related (since of the four categories that's the one I'm most well versed in).
In this write up we look at Very Smooth.
For this challenge we're given the following introductory text:
Forget safe primes... Here, we like to live life dangerously... >:)
As well as two files: gen.py and output.txt. The contents of output.txt are
n = c5261293c8f9c420bc5291ac0c14e103944b6621bb2595089f1641d85c4dae589f101e0962fe2b25fcf4186fb259cbd88154b75f327d990a76351a03ac0185af4e1a127b708348db59cd4625b40d4e161d17b8ead6944148e9582985bbc6a7eaf9916cb138706ce293232378ebd8f95c3f4db6c8a77a597974848d695d774efae5bd3b32c64c72bcf19d3b181c2046e194212696ec41f0671314f506c27a2ecfd48313e371b0ae731026d6951f6e39dc6592ebd1e60b845253f8cd6b0497f0139e8a16d9e5c446e4a33811f3e8a918c6cd917ca83408b323ce299d1ea9f7e7e1408e724679725688c92ca96b84b0c94ce717a54c470d035764bc0b92f404f1f5 c = 1f511af6dd19a480eb16415a54c122d7485de4d933e0aeee6e9b5598a8e338c2b29583aee80c241116bc949980e1310649216c4afa97c212fb3eba87d2b3a428c4cc145136eff7b902c508cb871dcd326332d75b6176a5a551840ba3c76cf4ad6e3fdbba0d031159ef60b59a1c6f4d87d90623e5fe140b9f56a2ebc4c87ee7b708f188742732ff2c09b175f4703960f2c29abccf428b3326d0bd3d737343e699a788398e1a623a8bd13828ef5483c82e19f31dca2a7effe5b1f8dc8a81a5ce873a082016b1f510f712ae2fa58ecdd49ab3a489c8a86e2bb088a85262d791af313b0383a56f14ddbb85cb89fb31f863923377771d3e73788560c9ced7b188ba97
Looking at gen.py it should become evident that this is an RSA problem. We are given the encoded message, as well as the product of the two primes used to produce the encoding base (and therefore also the order of the group, i.e. the modulus). In order to solve the problem we will need to recover the the base by finding the two primes used to construct .
Don't look at me... Go ask Mr. Pollard if you need a hint!
and the title of the challenge (Very Smooth) should key you in to the fact that for this RSA problem, the primes and are smooth, and therefore is theoretically easy to factor given the right algorithm.
The task then is easy. Factor to get and , at which point we can reproduce code directly from gen.py to decode the flag.
For this challenge it seems right to use Pollard's p-1 algorithm to factor . I've linked wikipedia but will provide a brief overview of the algorithm here anyway.
This section on the algorithm will not be mathematically rigorous, the point here is only for you to understand the principle behind the algorithm, in broad enough strokes to be satisfying.
Pollar's algorithm is based on Fermat's little theorem, which says
where is an integer coprime to , is a random integer, and is a prime. Coprime means that and are do not share any common factors except 1. You can derive this formula pretty easily if you start wih
Try it for yourself!
Let's take a brief aside into modulo arithmetic for a moment. For an arbitrary integer where and are prime and an arbitrary integer , all you need to know here is that
from which it follows that if
Be sure to note that Equation (5) is not in modulo arithmetic, and is an arbitrary integer.
We now have all the pieces we need to undestand what exactly Pollard's p-1 algorithm is trying to do. Assume we're factoring , where and are two "large" primes. The algorithm works specifically to find factors such that is powersmooth.  We search through the space to find a value such that Equation (4) is true. From there we can find the greatest common divisor between and which returns to us . You can check for yourself that the greatest common divisor between and , given that both and are multiples of must be , if is a large prime (the largest prime factor , at least) and . Importantly the value of (in this syntax) is completely irrelevant.
The key to Pollard's p-1 algorithm is the method by which it searches this space using Equation (1). If you can make the exponent a large enough number with enough prime factors, you should (hopefully) be able to find . Wikipedia outlines an algorithm, but for this challenge I found a slightly modified version to run quicker and more successfully.
In pseudocode, to factor :
a <- 2 j <- 2 B <- 1e9 (the maximum smoothness bound) while j <= B: a <- a^j mod n g <- gcd(a-1, n) if 1 < g < n: return g j <- j + 1 return fail
and the resultant python code I used to solve the problem:
a = 2 j = 2 B = 1e9 while j <= B: a = pow(a, j, n) g = gcd(a - 1, n) if 1 < g < m: break j += 1 print(g)
Once you have you have , and therefore can find :
p = g q = n // p
Once you have and you can recover the flag:
import binascii e = 0x10001 m = lcm(p - 1, q - 1) d = pow(e, -1, m) mess = pow(c, d, n) decrypt = hex(mess) print(binascii.unhexlify(decrypt[2:]))
Since the challenge is still solvable, I have redacted the actual flag, although the principles in this blog post can help you solve it.
Quite a fun little challenge!
|||In fact there is no necessity that nor be large, this algorithm works for small primes too.|
|||I won't explain what this means here, you can either take it as an ansatz or check wikipedia for a more detailed explanation.|
|||This is a simple reversal of RSA encoding, where the exponent is pulled from gen.py. Read up on RSA if this doesn't make sense.|