Tags: multi-prime crypto rsa
Rating:
Challenge Prompt:
Normal RSA uses two primes - that’s too few in my opinion, so I’ve added some more.
Files
You are given a Python snippet and a ciphertext output generated by it.
from sympy import nextprime, randprime
from sympy.core.random import seed
from math import prod, gcd
from Crypto.Util.number import bytes_to_long
p = randprime(2**127, 2**128)
N = 1
while N < 2**2048:
N *= p
p = nextprime(p)
assert gcd(phi_N, 65537) == 1
pt = bytes_to_long(FLAG)
ct = pow(pt, 65537, N)
print("N = ", N)
print("ct = ", ct)
# N = 34546497157207880069779144631831207265231460152307441189118439470134817451040294541962595051467936974790601780839436065863454184794926578999811185968827621504669046850175311261350438632559611677118618395111752688984295293397503841637367784035822653287838715174342087466343269494566788538464938933299114092019991832564114273938460700654437085781899023664719672163757553413657400329448277666114244272477880443449956274432819386599220473627937756892769036756739782458027074917177880632030971535617166334834428052274726261358463237730801653954955468059535321422372540832976374412080012294606011959366354423175476529937084540290714443009720519542526593306377
# ct = 32130352215164271133656346574994403191937804418876038099987899285740425918388836116548661879290345302496993945260385667068119439335225069147290926613613587179935141225832632053477195949276266017803704033127818390923119631817988517430076207710598936487746774260037498876812355794218544860496013734298330171440331211616461602762715807324092281416443801588831683678783343566735253424635251726943301306358608040892601269751843002396424155187122218294625157913902839943220894690617817051114073999655942113004066418001260441287880247349603218620539692362737971711719433735307458772641705989685797383263412327068222383880346012169152962953918108171850055943194
Task is to decrypt the ciphertext ct and recover the flag.
Solution:
Import modules:
prod computes the product of primes.
inverse finds the modular inverse for RSA decryption.
long_to_bytes converts decrypted number into a readable string.
re is used to search for the flag format.
2. Set up known values:
Prime list p from FactorDB.
Public exponent e.
Ciphertext ct.
3. Rebuild RSA internals:
Compute modulus N by multiplying all primes.
Compute totient phi_N as the product of (p_i - 1).
4. Decrypt:
Calculate d, the private exponent.
Decrypt ct to get plaintext integer.
Convert integer to bytes.
5. Extract the flag:
Search the decrypted bytes for uiuctf{...} pattern.
