Challenge:

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')

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


Solve:

There are many approaches.

1

\[f(p) = c_1 \cdot p^{136} + c_2 \cdot p^{135} + c_3 \cdot p^{134} + ...\] \[w \equiv 2^{f(p)} \pmod n\] \[w \equiv 2^{c_1 \cdot p^{136} + c_2 \cdot p^{135} + c_3 \cdot p^{134} + ...} \pmod n\] \[w \equiv 2^{c_1 \cdot p^{136}} \cdot 2^{c_2 \cdot p^{135}} \cdot 2^{c_3 \cdot p^{134}} \cdot ... \pmod n\] \[w \equiv \left(2^{p^{136}}\right)^{c_1} \cdot \left(2^{p^{135}}\right)^{c_2} \cdot \left(2^{p^{134}}\right)^{c_3} \cdot ... \pmod n\]

Then if you work mod p, and apply fermat’s little theorem, every 2^(p^i) just becomes 2.


\[w \equiv 2^{c_1} \cdot 2^{c_2} \cdot 2^{c_3} \cdot ...\]


\[w \equiv 2^{c_1 + c_2 + c_3 + ...}\] 
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

s = sum(f.coefficients(sparse=False))
p = gcd(n, pow(2, s, n) - w)
print(bytes.fromhex(f'{pow(c, pow(e, -1, p-1), p):x}'))

2

What’s also funny is it’s solveable without the output f.

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

The sum is always going to be pretty small.

for s in range(-100, 100):
    p = gcd(n, pow(2, s, n) - w)
    if p != 1:
        break

3

The final coefficient of f is a - 2

\[f(n) = c_1 \cdot n^{136} + c_2 \cdot n^{135} + c_3 \cdot n^{134} + ... - 2\] \[f(n) + 2 = c_1 \cdot n^{136} + c_2 \cdot n^{135} + c_3 \cdot n^{134} + ...\] 


n = 151510886600487624888537926759375027338192556324330182365859112926770109752858284462159488504727238764120612593911292154858008775463001345641311051184326218974685701057787672193003745574697137968457609530135969033403360561333863943223407215732526198691453110628598401583407984162075630768455052482583101773637
e = 65537
c = 74468088842131664480394073891613024559473817230309311952320910922177130990996003196602702376336093457990873018154873841543712071422931358036924937335888815556064840522100618318507080665149514719351519909821468981883880543654015414713368018500970500498936910817336501949914675483148862843329341461828563728789
PR.<x> = PolynomialRing(ZZ)
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 = 13225714361729574520455202298375227094074406734919375136587843359624943332689824878374404352272325464764160629294291226430894442389258055341084446730877841
q = 11455780947372131061966087259393299886332168747401603467936030221981775933945653112148754911576958430762875142273435855265225533133629852360508022599728757
assert w == pow(2, f(p), n)

print(w % q == pow(2, f(n), q)) # True
print(w % p == pow(2, f(n), p)) # False


Can you see why mod q is true and mod p is false?

Then you can do

assert (w * 2**2) % n == 2**2 * pow(2, f(p), n) % n
assert 0 == (pow(2, f(n)+2, n) - 4*w) % q
assert q == gcd(n, pow(2, f(n)+2, n) - 4*w)


4

Split f(x) into k * (x-1) + r

where r can be calculated as f mod (x-1)

sub that in

\[w \equiv 2^{f(p)} \pmod n\] \[w \equiv 2^{k \cdot (p-1) + r} \pmod n\] \[w \equiv (2^{p-1})^k \cdot 2^r \pmod p\]

By fermat’s little theorem, 2^(p-1) mod p is 1

\[w \equiv (1)^k \cdot 2^r \pmod p\] \[w \equiv 2^r \pmod p\] 
r = f % (x-1)
assert p == gcd(n, pow(2, r, n) - w)




Bivariate

Challenge:

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,y> = PolynomialRing(ZZ)
x, y = P.gens()

terms = []
for i in range(16):
    terms += [(x**i)*(y**j) for j in range(16-i)]

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,q),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')

n = 98488948227534213135365379684862624429673068552821962383206603053375602239567322517902539151497074614991106864222481349938278930598229083057490442318255136829928469581554377192371866029487604479323565889518717446151982565992066276503827461143275322745847799672825450812329543611683563104108219738025321562523
e = 65537
c = 33689078336368731933599049868377598889513853827091255415228112692581639226201157033763841134090287166200344255205518269253856257850799105681895141225429744730522910522719711967250214161994104603730456295060918937791062152710510634082416634814375504799932491459723391812528758183583260665132261524658305233101
f = x^14*y + x^13*y^2 - x^12*y^3 - 3*x^10*y^5 - x^8*y^7 - x^6*y^9 + x^5*y^10 + x^4*y^11 - x^2*y^13 - 2*x*y^14 + y^15 - x^14 + 3*x^13*y + x^12*y^2 + 2*x^11*y^3 - x^9*y^5 + x^8*y^6 + x^7*y^7 - x^6*y^8 + x^5*y^9 - x^4*y^10 - 2*x^3*y^11 + 2*x^2*y^12 - 2*x*y^13 + x^11*y^2 - 3*x^10*y^3 - x^7*y^6 - x^6*y^7 + x^5*y^8 + 3*x^4*y^9 + 4*x^3*y^10 + 2*x^2*y^11 - 2*x*y^12 + y^13 + 2*x^12 + 2*x^11*y - 5*x^9*y^3 - 3*x^8*y^4 + 4*x^7*y^5 - 2*x^6*y^6 - x^5*y^7 - x^3*y^9 - x^2*y^10 + x*y^11 - y^12 - x^11 - x^10*y + 3*x^9*y^2 + 3*x^8*y^3 - 2*x^7*y^4 - 2*x^6*y^5 + 2*x^3*y^8 - 3*x^2*y^9 + y^11 + x^10 + x^8*y^2 - x^7*y^3 + 3*x^6*y^4 - 5*x^5*y^5 - x^4*y^6 + x^3*y^7 - x^2*y^8 - 2*y^10 - x^8*y - x^7*y^2 - x^5*y^4 - x^4*y^5 - x^2*y^7 - x*y^8 - 4*x^8 + 4*x^7*y - 2*x^6*y^2 - x^5*y^3 - 2*x^4*y^4 - x^3*y^5 - 3*x^2*y^6 + x*y^7 - 3*y^8 + 4*x^6*y + x^5*y^2 - 2*x^3*y^4 - 5*x^2*y^5 + x*y^6 + x^5*y + 2*x^4*y^2 - x^2*y^4 - x*y^5 - 2*y^6 + 3*x^5 + 4*x^4*y + 2*x^3*y^2 - y^5 - x^4 - 3*x^3*y - 3*x^2*y^2 + x*y^3 + 2*x^3 + x*y^2 + y^3 + x^2 - 4*x*y + y^2 + 2*x + y
w = 15989670860487110440149242708963326378222417402274922693109917884050744558426262015391394948248787707275063436118071762352120567031556081355002123446258001515700442370180130234425828020876205206138411646169530066935290884923582522784445410472996067725745321733529202293253140485085104533833013732203780391490


Solver:

n = 98488948227534213135365379684862624429673068552821962383206603053375602239567322517902539151497074614991106864222481349938278930598229083057490442318255136829928469581554377192371866029487604479323565889518717446151982565992066276503827461143275322745847799672825450812329543611683563104108219738025321562523
e = 65537
c = 33689078336368731933599049868377598889513853827091255415228112692581639226201157033763841134090287166200344255205518269253856257850799105681895141225429744730522910522719711967250214161994104603730456295060918937791062152710510634082416634814375504799932491459723391812528758183583260665132261524658305233101
var('x y')
f = x^14*y + x^13*y^2 - x^12*y^3 - 3*x^10*y^5 - x^8*y^7 - x^6*y^9 + x^5*y^10 + x^4*y^11 - x^2*y^13 - 2*x*y^14 + y^15 - x^14 + 3*x^13*y + x^12*y^2 + 2*x^11*y^3 - x^9*y^5 + x^8*y^6 + x^7*y^7 - x^6*y^8 + x^5*y^9 - x^4*y^10 - 2*x^3*y^11 + 2*x^2*y^12 - 2*x*y^13 + x^11*y^2 - 3*x^10*y^3 - x^7*y^6 - x^6*y^7 + x^5*y^8 + 3*x^4*y^9 + 4*x^3*y^10 + 2*x^2*y^11 - 2*x*y^12 + y^13 + 2*x^12 + 2*x^11*y - 5*x^9*y^3 - 3*x^8*y^4 + 4*x^7*y^5 - 2*x^6*y^6 - x^5*y^7 - x^3*y^9 - x^2*y^10 + x*y^11 - y^12 - x^11 - x^10*y + 3*x^9*y^2 + 3*x^8*y^3 - 2*x^7*y^4 - 2*x^6*y^5 + 2*x^3*y^8 - 3*x^2*y^9 + y^11 + x^10 + x^8*y^2 - x^7*y^3 + 3*x^6*y^4 - 5*x^5*y^5 - x^4*y^6 + x^3*y^7 - x^2*y^8 - 2*y^10 - x^8*y - x^7*y^2 - x^5*y^4 - x^4*y^5 - x^2*y^7 - x*y^8 - 4*x^8 + 4*x^7*y - 2*x^6*y^2 - x^5*y^3 - 2*x^4*y^4 - x^3*y^5 - 3*x^2*y^6 + x*y^7 - 3*y^8 + 4*x^6*y + x^5*y^2 - 2*x^3*y^4 - 5*x^2*y^5 + x*y^6 + x^5*y + 2*x^4*y^2 - x^2*y^4 - x*y^5 - 2*y^6 + 3*x^5 + 4*x^4*y + 2*x^3*y^2 - y^5 - x^4 - 3*x^3*y - 3*x^2*y^2 + x*y^3 + 2*x^3 + x*y^2 + y^3 + x^2 - 4*x*y + y^2 + 2*x + y
w = 15989670860487110440149242708963326378222417402274922693109917884050744558426262015391394948248787707275063436118071762352120567031556081355002123446258001515700442370180130234425828020876205206138411646169530066935290884923582522784445410472996067725745321733529202293253140485085104533833013732203780391490

kp = pow(2, f(y=n/x)(x=1), n) - w
p = gcd(kp, n)


print(bytes.fromhex(f'{pow(c, pow(e, -1, p-1), p):x}'))