Univariate (ictf Round 54)

RSA Fermat's Little Theorem

Challenge overview

In this CTF challenge we are given the following encryption script:

from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

p = getPrime(512)
q = getPrime(512)
n = p*q

m = bytes_to_long(flag.encode())
e = 65537
c = pow(m,e,n)

P.<x> = PolynomialRing(ZZ)
x = P.gens()[0]

terms = [x**i for i in range(137)]

T = RealDistribution('gaussian', 2)
coefs = [round(T.get_random_element()) for _ in range(len(terms))]

f = sum([term*coef for term,coef in zip(terms,coefs)])
w = pow(2,f(p),n)

with open('out.txt', 'w') as file:
    file.write(f'{n = }\n')
    file.write(f'{e = }\n')
    file.write(f'{c = }\n')
    file.write(f'{f = }\n')
    file.write(f'{w = }\n')

as well as the output:

n = 151510886600487624888537926759375027338192556324330182365859112926770109752858284462159488504727238764120612593911292154858008775463001345641311051184326218974685701057787672193003745574697137968457609530135969033403360561333863943223407215732526198691453110628598401583407984162075630768455052482583101773637
e = 65537
c = 74468088842131664480394073891613024559473817230309311952320910922177130990996003196602702376336093457990873018154873841543712071422931358036924937335888815556064840522100618318507080665149514719351519909821468981883880543654015414713368018500970500498936910817336501949914675483148862843329341461828563728789
f = -x^136 + x^135 - 2*x^134 - 4*x^132 + 2*x^130 - x^128 - 3*x^127 + 4*x^126 + 3*x^125 + 3*x^124 + x^123 + x^122 - 5*x^121 - 3*x^120 - x^119 - x^118 + x^117 + x^116 - 4*x^114 - 2*x^112 + 2*x^110 + x^109 + 2*x^108 - 2*x^107 + 3*x^106 - x^104 + 2*x^103 - x^102 + x^101 - 2*x^100 + 3*x^99 - 2*x^98 - x^97 - x^96 - 3*x^95 - x^94 - 2*x^93 - 2*x^91 + 3*x^90 - 2*x^89 - 2*x^88 + x^86 + x^85 - 2*x^84 - 3*x^83 + 2*x^82 + 3*x^79 - x^76 + 2*x^75 - x^74 + x^71 - 5*x^70 - x^67 + x^66 + x^65 + x^63 - x^61 + x^59 - 2*x^58 + 6*x^56 + x^55 + 3*x^54 - x^53 + 2*x^52 + 3*x^51 + x^50 + 2*x^49 + 3*x^47 + 2*x^46 - 4*x^45 + 3*x^44 + 3*x^43 - x^42 - 2*x^40 - 5*x^39 + x^38 + x^37 + 2*x^36 + 2*x^35 + x^34 - x^33 + x^32 - 5*x^31 + x^30 + x^29 + 2*x^28 - 2*x^27 + 3*x^26 - x^25 - x^23 - x^22 - 3*x^21 + 2*x^20 - x^19 - x^17 + 2*x^16 - 2*x^15 - 2*x^14 - 2*x^13 - 2*x^12 + 2*x^11 - 2*x^9 + 3*x^8 - 4*x^7 + 2*x^6 - 2*x^5 - 5*x^4 - 3*x^3 + 5*x^2 - 2
w = 86258923706084556733053644452456806418792871483898871193707132372143291757396867798433017660985422614532352743658877188445517898648519256573663299464811234251773841741466280567326570167017786562044635756348763128567054349991798640926148221279889174229551074668002853442182664523748992260830782387602048836221

The encryption script uses RSA to encrypt the flag. However, we are given some hints about the prime factor $p$.

\[\large w = 2^{f(p)} \mod n\]

Recovering p

We utilize the polynomial identity:

\[\large f(x) - f(1) = (x-1)\cdot g(x)\]

for some polynomial $g(x)$. We can evaluate $f$ at $x=1$ in sagemath:

sage: f(1)
-12

So, for $f(p)$, we have:

\[\large f(p) + 12 = (p-1)\cdot g(x)\]

This means $f(p)+12$ is a multiple of $p-1$!

We can then utilize fermat’s little theorem:

\[\large 2^{p-1} \equiv 1 \mod (p)\]

Any exponent that is a multiple of $p-1$ will also be congruent to $1 \mod p$.

\[\large \begin{align} \nonumber 2^{f(p)+12} \equiv 1 \mod p \\ \nonumber 2^{f(p)}\cdot 2^{12} \equiv 1 \mod p \\ \nonumber w \cdot 2^{12} - 1 \equiv 0 \mod p \end{align}\]

From here, we can use $gcd$ with $N$ to recover $p$ and $q$:

sage: p = gcd(w*2^12-1,n)
sage: q = n/p
sage: assert p*q == n

With the prime factors recovered, the decryption is trivial:

phi = (p-1)*(q-1)
d = pow(e,-1,phi)
pt = bytes.fromhex(f"{int(pow(c,d,n)):x}")
print(pt)
# ictf{p-1_g0es_aB$olU7eLy_w1lD!!!}

solve.py

P.<x> = PolynomialRing(ZZ)
x = P.gens()[0]

n = 151510886600487624888537926759375027338192556324330182365859112926770109752858284462159488504727238764120612593911292154858008775463001345641311051184326218974685701057787672193003745574697137968457609530135969033403360561333863943223407215732526198691453110628598401583407984162075630768455052482583101773637
e = 65537
c = 74468088842131664480394073891613024559473817230309311952320910922177130990996003196602702376336093457990873018154873841543712071422931358036924937335888815556064840522100618318507080665149514719351519909821468981883880543654015414713368018500970500498936910817336501949914675483148862843329341461828563728789
f = -x^136 + x^135 - 2*x^134 - 4*x^132 + 2*x^130 - x^128 - 3*x^127 + 4*x^126 + 3*x^125 + 3*x^124 + x^123 + x^122 - 5*x^121 - 3*x^120 - x^119 - x^118 + x^117 + x^116 - 4*x^114 - 2*x^112 + 2*x^110 + x^109 + 2*x^108 - 2*x^107 + 3*x^106 - x^104 + 2*x^103 - x^102 + x^101 - 2*x^100 + 3*x^99 - 2*x^98 - x^97 - x^96 - 3*x^95 - x^94 - 2*x^93 - 2*x^91 + 3*x^90 - 2*x^89 - 2*x^88 + x^86 + x^85 - 2*x^84 - 3*x^83 + 2*x^82 + 3*x^79 - x^76 + 2*x^75 - x^74 + x^71 - 5*x^70 - x^67 + x^66 + x^65 + x^63 - x^61 + x^59 - 2*x^58 + 6*x^56 + x^55 + 3*x^54 - x^53 + 2*x^52 + 3*x^51 + x^50 + 2*x^49 + 3*x^47 + 2*x^46 - 4*x^45 + 3*x^44 + 3*x^43 - x^42 - 2*x^40 - 5*x^39 + x^38 + x^37 + 2*x^36 + 2*x^35 + x^34 - x^33 + x^32 - 5*x^31 + x^30 + x^29 + 2*x^28 - 2*x^27 + 3*x^26 - x^25 - x^23 - x^22 - 3*x^21 + 2*x^20 - x^19 - x^17 + 2*x^16 - 2*x^15 - 2*x^14 - 2*x^13 - 2*x^12 + 2*x^11 - 2*x^9 + 3*x^8 - 4*x^7 + 2*x^6 - 2*x^5 - 5*x^4 - 3*x^3 + 5*x^2 - 2
w = 86258923706084556733053644452456806418792871483898871193707132372143291757396867798433017660985422614532352743658877188445517898648519256573663299464811234251773841741466280567326570167017786562044635756348763128567054349991798640926148221279889174229551074668002853442182664523748992260830782387602048836221

p = gcd(w*2^12-1,n)
q = n/p
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
pt = bytes.fromhex(f"{int(pow(c,d,n)):x}")
print(pt)