Cycling - GoogleCTF 2022

It is well known that any RSA encryption can be undone by just encrypting the ciphertext over and over again. If the RSA modulus has been chosen badly then the number of encryptions necessary to undo an encryption is small. However, if the modulus is well chosen then a cycle attack can take much longer. This property can be used for a timed release of a message. We have confirmed that it takes a whopping 2^1025-3 encryptions to decrypt the flag. Pack out your quantum computer and perform 2^1025-3 encryptions to solve this challenge. Good luck doing this in 48h.

e = 65537
n = ... # snip
ct = ... # snip
# Decryption via cycling:
pt = ct
for _ in range(2**1025 - 3):
  pt = pow(pt, e, n)
# Assert decryption worked:
assert ct == pow(pt, e, n)

# Print flag:
print(pt.to_bytes((pt.bit_length() + 7)//8, 'big').decode())

Solution

given that ${R = 2^{1025} - 3}$ and $pt^{e ^ R} = pt \implies pt^{e ^ {R-1}} = 1 mod \phi(n)$

since given ciphertext is already encrypted once so ${e^{R+1} \equiv 1 (mod \phi(n))}$ and From carmichael's lambda function ${\lambda(n) = lcm(p-1),(q-1)}$ It can also be ${e^{R+1} \equiv 1 (mod \phi(n))}$

from this statement we can se lambda function for $n=\lambda(n)$ is ${R+1}$ according to its definition. so ${R+1} | \lambda(\lambda(n))$

${R+1 = \lambda(\lambda(n)) = \lambda(lcm(p-1,q-1)) = \lambda(2*s1.s2.....sk)}$

${\implies lcm(s1-1,s2-1,....sk-1) = R+1}$

Now if know that eah si-1 devides R+1 and since R+1 is not esoteric so it can be factored using factotdb and add 1 to each factor and we will get the values of si.

factors = [2, 3, 5, 17, 257, 641, 65537, 274177, 2424833, 6700417, 67280421310721, 1238926361552897, 59649589127497217, 5704689200685129054721, 7455602825647884208337395736200454918783366342657, (2^256+1)//1238926361552897, (2^512+1)//18078591766524236008555392315198157702078226558764001281]
assert 2**1025-2 == prod(factors)

C = []
for ps in powerset(factors):
    v = prod(ps) + 1
    if is_prime(v):
        C.append(prod(ps) + 1)
Ξ = prod(C)

e = 65537
n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680

d = pow(e, -1, Ξ)
print(long_to_bytes(int(pow(ct, d, n))))

from Crypto.Util.number import *
from gmpy2 import *
from math import *
from itertools import *

e = 65537
n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680

factors = [2,3,5,17,257,641,65537,274177,2424833,6700417,67280421310721,1238926361552897,59649589127497217,5704689200685129054721,7455602825647884208337395736200454918783366342657,93461639715357977769163558199606896584051237541638188580280321,741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737]

res=2

for i in range(1, len(factors)):
    for comb in combinations(factors, i):
        pp = prod(comb)
        if isPrime(pp + 1):
            res = powmod(res, pp + 1, n)
            g = gcd(res - 1, n)
            if 1 < g < n:
                p = g
                q = n // p

phi = (p - 1) * (q - 1)
d = invert(e, phi)
pt = powmod(ct, d, n)
print(int(pt).to_bytes((int(pt).bit_length() + 7) // 8, "big"))

After running the above code we get the flag CTF{Recycling_Is_Great}