Utilize values of n, p-q, and (p^3-q^3) to find the value of p or phi through solving a series of algebraic equations.
Analysis
We can see that we have very little code to work with, and the values provided are for the ones showed in output.txt.
Recall that we need d to decrypt the ct, where pt = pow(ct,d,n).
This site provides a recap on how to obtain d for decrypting RSA, where I quote:
Generate two large random primes, p and q, of approximately equal size such that their product n=pq is of the required bit length, e.g. 1024 bits. [See note 1].
Choose an integer e, 1<e<ϕ, such that gcd(e,ϕ)=1. [See note 2].
Compute the secret exponent d, 1<d<ϕ, such that ed≡1modϕ. [See note 3].
The public key is (n,e) and the private key (d,p,q). Keep all the values d, p, q and ϕ secret. [Sometimes the private key is written as (n,d) because you need the value of n when using d. Other times we might write the key pair as ((N,e),d).]
Our d also has to be derived from e and phi, where phi would be (p-1)(q-1) (refer to the info box above).
Using multiple expansions and substitutions with the values we are given, we can solve for p or phi.
Solving for Phi
We can reference this table if there is a need to recap the algebra rules:
Basic rules of algebra
Focusing on values of n, p-q, and (p^3-q^3):
Equations to get phi
Now we got phi using the values that we have, we can just get d using the Euclidean Algorithm and decrypt the ciphertext!
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, getRandomInteger, bytes_to_long
import math
from secret import flag
p,q = [getPrime(512) for _ in range(2)]
n = p*q
e = 65537
a = getRandomInteger(128)
m = bytes_to_long(flag)
ct = pow(m,e,n)
print(f"{p-q=}")
print(f"{pow(p,3)-pow(q,3)=}")
print(f"{n=}")
print(f"{ct=}")
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, getRandomInteger, bytes_to_long, long_to_bytes
import math
from decimal import Decimal
def isqrt(x):
"""Return the integer part of the square root of x, even for very
large integer values."""
if x < 0:
raise ValueError('square root not defined for negative numbers')
if x < _1_50:
return int(math.sqrt(x)) # use math's sqrt() for small parameters
n = int(x)
if n <= 1:
return n # handle sqrt(0)==0, sqrt(1)==1
# Make a high initial estimate of the result (a little lower is slower!!!)
r = 1 << ((n.bit_length() + 1) >> 1)
while True:
newr = (r + n // r) >> 1 # next estimate by Newton-Raphson
if newr >= r:
return r
r = newr
def egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q, r = b//a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
gcd = b
return gcd, x, y
_1_50 = 1 << 50 # 2**50 == 1,125,899,906,842,624
pminq=-1305235648860840853683949458831305072763230973669829177960178482866452800364412721111763583069321978987148627466498224410781024187725838888479326409184744
cubepq=-465514652595610856880453636545438331400010973790168791066069161352239209188533132121982942661849199245018660968880021999471046367873763759524854675286821508038418401864765726491449185192253500864628518550804809046508686959255535195714941766727484090297166583454871187745735758463441767587210583432967693381451227261083381147367649535205516682361917227931630894904749876510765825586785760034509104564737258991404912289408762611694496702482996518688138500642819128
n=118316055600083929089071669812439032539191357668051889677911602916721340636167359556934591671598570703259986990715914276095866429868571322432308962619799310816435693053230854913872753733501348441234715512020861405241513403795045428404496593692411330352525309662619935495570018411169134102570106958094779439217
ct=64880869410692063175906103028969957878271889970688259195068268235741104167117130794136851712307899764163566653527660540303926093374874865621497088649195483963877573321808998916766978276663044270028514646216644963284229260389738926787740160186040707610308628316701038087132926246223087221028661729121666185863
e = 65537
aplusbsqr = (cubepq // pminq) + n
pplusq = isqrt(aplusbsqr)
phi = n - (pplusq) + 1
gcd, a, b = egcd(e, phi)
d = a
print(d)
pt = pow(ct, d, n)
print(long_to_bytes(pt))
