Here we can notice that the used encryption is RSA, but the modulus n3 uses 4 prime numbers instead of two. However the trick is using "next_prime" in the given sequence means that the 4 primes are all successive.
n1 --> n3 = n1 * n2
n1 = p1q1
n2 = p2q2
n1 * n2 = (p1q1) * (p2q2)
p1 --> random prime with 512 bit size
q1 --> next prime after p1
p2 --> next prime after q1
q2 --> next prime after p2
And we have the output given with the source code of the encryption.
note that n1 is n3 in the code, and n2 is n4 in the code.
Knowing that the 4 primes are successive we can work on factorizing them. First I tried Alberton and Factor.db but modulus (n1 from the output file) was too big.
So I worked on bruteforcing the factorization with an iterative method approach, meaning that I take the output of each iteration and use it as in input for the next iteration while decreasing the searching steps to increase the accuracy of searching. This way I decrease the complexity of bruteforcing the factorization and get a quicker result instead of waiting many hours using a simple for loop and incrementing the same small steps everytime.
.
.
Here's how I implemented this idea, through using a big value slightly smaller than the prime, and subtracting it from the prime at the end of each loop before getting the previous prime. The script adjusts the value that we subtract from the prime each iteration, such that as we move closer, we subtract smaller values, and get better accuracy.
Note: p1 = getPrime(512) --> means the smallest prime is a random prime with 512 bits size, so the primes are in the range of
[2pow(1) - 2pow(15)-1] this gives us around 10pow(154) possible primes which is why normal iteration would be too slow.
First I will run "initial_guessing_the_primes.py" so that I get a good initial guess for the prime p1, such that the product of 4 successive primes is greater than the modulus n.
so now we have the initial guess for prime1. I will go to "descending_primes.py" and initilize prime4 with this value of prime1 we got from the terminal.
now what this script does is it iterates over the primes in a descending order. since we are on the greater side of the target prime.
Next let's run "descending_primes.py", I recorded the time it took before yeilding a result, it took roughly 10 minutes.
and here's the results
I will take those results and put them into another script I wrote "getting_the_primes.py". In this script I will iterate in an ascending order, since it's on the side of primes whose product is less than the modulus.
The result comes back with all the values of the 4 primes
Finally we have the the 4 primes and we can get the two decryption keys d1 and d2 It's worth noting that the source code doesn't use the normal rsa encryption method however it multiplies the encrypted message with an integer to add padding and randomness. We need to remove it's effect before we can decrypt.
I use "rsa.py" to do these steps and to do the decryption as well, after running the script I finally got the flag!!!
