Mathematics of Cryptography
Easy
150
Description
The Defenders heard that there are some Math legends among us and have reached out for assistance in breaking one of the Uprisers' security defenses.
Solution
TL;DR
Utilize values of
n
,p-q
, and(p^3-q^3)
to find the value ofp
orphi
through solving a series of algebraic equations.
Analysis
#!/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=}")
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)
.
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:

Focusing on values of n
, p-q
, and (p^3-q^3)
:

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, 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))
Last updated
Was this helpful?