Rotating Secret Assembler

3 minutes to read

We are given a host to connect to. It shows the source code used to encrypt the flag:

$ nc puzzler7.imaginaryctf.org 3000
================================================================================

#!/usr/bin/env python3

from Crypto.Util.number import *

class Rotator:
    QUEUE_LENGTH = 10

    def __init__(self):
        self.e = 65537
        self.m = bytes_to_long(open('flag.txt', 'rb').read())
        self.queue = [getPrime(512) for i in range(self.QUEUE_LENGTH)]  

    def get_new_primes(self):
        ret = self.queue[-2:]
        self.queue.pop()
        while(len(self.queue) < self.QUEUE_LENGTH):
            self.queue = [getPrime(512)] + self.queue
        return tuple(ret)

    def enc_flag(self):
        p, q = self.get_new_primes()
        n = p*q
        print(f"Public key: {(n, self.e)}")
        print(f"Your encrypted flag: {pow(self.m, self.e, n)}")

rot = Rotator()

print('='*80)
print(open(__file__).read())
print('='*80)

while True:
    inp = input("Would you like an encrypted flag (y/n)? ")
    if 'y' in inp.lower():
        rot.enc_flag()
        print()
    else:
        break

================================================================================  
Would you like an encrypted flag (y/n)? ^C

The encryption type is RSA, but the implementation is wrong. The way to obtain the two prime numbers $p$ and $q$ is using a list of 10 prime numbers. The problem is that it uses primes #9 and #10, removes the last prime number from the list and adds a new one at the start.

Hence, if we encrypt the flag again, the current primes #9 and #10 are the old #8 and #9. As a result, the two modulus $n_1$ and $n_2$ have a common prime factor, so we can find it using the Greatest Common Divisor (GCD):

$ nc puzzler7.imaginaryctf.org 3000
================================================================================
...
================================================================================
Would you like an encrypted flag (y/n)? y
Public key: (96703909946448187810080059928860289847334838421345682013476154093401516765135280790240748288018738898773300957888698818329609720254183468520955600410824182661260651475354846583794678409061342257380126990919258631778574644009046899146628324485287628710454832937953442848153274308105256237934059406671514368669, 65537)  
Your encrypted flag: 59178952773280983701929213365655160414345333604813929581573406427317973306869828507777582501496996849288063597376183280909545034065032431890181707370065107503683394760116243008932175061294230315842811989143511271380367848125619781509436529057342192685755008501371415788491821709728063365374407957399759308403

Would you like an encrypted flag (y/n)? y
Public key: (67521112267846681759399501276451660075611114138321414686289669627378193951857898222612601048796706669289048949898237532495727093603797701087528981834411985551974275328675230434122883600996218065032476293749234911283805641424141314863236316629221906963122154907092242556815579427166899630607780645315510611627, 65537)
Your encrypted flag: 17472971162377108034479702090513254186993682961319105294905663470809265628036722391463644486154580853360833837492388701203988503690522100670413712708369683451190130374033333827066594624190360243317258296768874842826927768445323829689267057977209895049163051260509473831629782589375685789931957272431150099185

Would you like an encrypted flag (y/n)? ^C

$ python3 -q
>>> import math
>>> math.gcd(
...     96703909946448187810080059928860289847334838421345682013476154093401516765135280790240748288018738898773300957888698818329609720254183468520955600410824182661260651475354846583794678409061342257380126990919258631778574644009046899146628324485287628710454832937953442848153274308105256237934059406671514368669,  
...     67521112267846681759399501276451660075611114138321414686289669627378193951857898222612601048796706669289048949898237532495727093603797701087528981834411985551974275328675230434122883600996218065032476293749234911283805641424141314863236316629221906963122154907092242556815579427166899630607780645315510611627
... )
9363717537480322078371747028261742962030931062610359488017319347844327325330269179209776316998302502579512167515356510999614768902498349936434046242471613

There it is. Now that we have one prime number, we can find the other one using integer division on $n_1$ and decrypt the RSA encryption in the conventional way. This is the solution script in Python:

#!/usr/bin/env python3

from math import gcd
from pwn import remote


def main():
    r = remote('puzzler7.imaginaryctf.org', 3000)

    r.sendlineafter(b'Would you like an encrypted flag (y/n)? ', b'y')  
    r.recvuntil(b'Public key: ')
    n1, e = eval(r.recvline().decode())
    r.recvuntil(b'Your encrypted flag: ')
    c = int(r.recvline().decode())

    r.sendlineafter(b'Would you like an encrypted flag (y/n)? ', b'y')
    r.recvuntil(b'Public key: ')
    n2, _ = eval(r.recvline().decode())
    r.close()

    p = gcd(n1, n2)
    q = n1 // p

    phi_n = (p - 1) * (q - 1)
    d = pow(e, -1, phi_n)
    m = pow(c, d, n1)

    print(bytes.fromhex(hex(m)[2:]).decode())


if __name__ == '__main__':
    main()

And we obtain the flag:

$ python3 solve.py
[+] Opening connection to puzzler7.imaginaryctf.org on port 3000: Done  
[*] Closed connection to puzzler7.imaginaryctf.org port 3000
ictf{why_would_I_throw_away_perfectly_good_primes?}

The full script can be found in here: solve.py.