Sum-O-Primes

Sum-O-Primes

Author

JOSHUA INSCOE

Description

We have so much faith in RSA we give you not just the product of the primes, but their sum as well!

• gen.py
• output.txt

Hint

1. I love squares :)

Approach

Looking at the code, we see that:

x = p + q
n = p * q

Since we know x and n, we can use the quadratic formula to find p and q.

q = x - p
n = p(x-p)
p^2 - px + n =0 
p = (p + sqrt(p^2 - 4n))/2

Using this website, we can calculate the value of p and q:

p = 159345915596463944529081131753971814012774772050551148399495974973230064137934032201667165677259168937053515829561017311027545566207271693690228836186236646253172692528842923841477807159018342662898044600149285073653457469902347646580582259244229740406914468116287983551968641638873594478429124383124661956247

q = 155868000505857419209946367754266186073076819993840772838936630023198614594161965925121384245003607287648726728938019179285989886255327887846950299862954841947205295029541250199019231520699925463895248134439966031615306349461409351339070301637536042916274176236307232503242861213248080124656331830391844435179

Next, I needed to find a way to reverse c = pow(FLAG, e, n). I searched up a solution and found code on Stack Overflow. I then modified the code with the values from the question:

b = 65537
c = int(("c4bf129f0b86c18115b8eabfc5399e366e75d703f191f993b56d433d86c2a7c85ff1304c9d9068893232ced732e769114873a6dfdc61949388a0bc8a1f4ef0332888e714c9deadb2439c532aa1c8210f8a90409f6e7776239eebf649149f02e005683c86e677ebf17506ed076eddf593696dbc58340dde1c3a7da443f0b27d3ba8e8f04e7139e199ef34cb88e26e3794b319a4018a6627203c479edd50cb9c5b2cdc8a8de14c6c0294e6ad13c95c98fe8e8f1b9587dc7f2ddbba1233a14ed831321323c1e68b525f8fb8a93bd7081e702606c7174d1534af66858c25c5b19304accde3a0659cd29c3c7cb411e015422b5a8fd0d403470553bc5f870b3506709d".encode()), 16)
y = int("7a374a38637bc444b13d346f33db53376c75d1776172e6ff1758d1daff37e51b620ec096bb6a1c8dc8c02e9501c0b87a22799490036f357ed9d4cdb698a9400121bad57d19e0c29316be010397dd2b2da64e4b4bcb81cb53043cf6032ee7b66253fbd34870c80cd006b715816eb90a1effc0b8e4f0a3b963bf3a09c2d95fc1b152d813e343fe35aad0f17a0575f6bbefa73f567f9531f211ecdbd1892e467df5029f0e3e29228f765df8c8e042f759ad468b4af7274c420b826f92370e4a07e4586d96d1e6b9b87487902f34dc96add01aa661384e90a6ba19e6ca194533afef7e6f254c59e5d684c850d23a64d4e9d10a35fd8fdc06899496c11310bd146565".encode(), 16)

p = 159345915596463944529081131753971814012774772050551148399495974973230064137934032201667165677259168937053515829561017311027545566207271693690228836186236646253172692528842923841477807159018342662898044600149285073653457469902347646580582259244229740406914468116287983551968641638873594478429124383124661956247

q = 155868000505857419209946367754266186073076819993840772838936630023198614594161965925121384245003607287648726728938019179285989886255327887846950299862954841947205295029541250199019231520699925463895248134439966031615306349461409351339070301637536042916274176236307232503242861213248080124656331830391844435179

lam = carmichael_lambda([(p,1), (q, 1)])
z = inverse(b, lam)
x = pow(y, z, c)
print(hex(x))

Running it gave me 0x7069636f4354467b66356561623139307d and converting it to a String, we get picoCTF{f5eab190}

Flag

picoCTF{f5eab190}