# Bro do you even Lift - Teaser CONFidence CTF 2019

tl;dr

1. Find roots in a polynomial ring over $mod;p$
2. Use Hensel’s Lifting lemma to find roots over $mod;p^k$

Challenge Points: 85
Challenge Solves:
Solved by: v4d3r, s0rc3r3r, v3ct0r, 4lph4

## Preliminary Analysis

This challenge was based on a 4th degree Univariate Polynomial Ring. We are provided with lift.sage and
outputs.txt. In lift.sage we have:

Contents of outputs.txt are:

35671

12172655049735206766902704703038559858384636896299329359049381021748*x^4 + 11349632906292428218038992315252727065628405382223597973250830870345*x^3 + 9188725924715231519926481580171897766710554662167067944757835186451*x^2 + 8640134917502441100824547249422817926745071806483482930174015978801*x + 170423096151399242531943631075016082117474571389010646663163733960337669863762406085472678450206495375341400002076986312777537466715254543510453341546006440265217992449199424909061809647640636052570307868161063402607743165324091856116789213643943407874991700761651741114881108492638404942954408505222152223605412516092742190317989684590782541294253512675164049148557663016927886803673382663921583479090048005883115303905133335418178354255826423404513286728

It is clear from the above snippet that the flag is a root of the following polynomial:
$ax^4 + bx^3 + cx^2 + dx + e = 0;(mod;N)$
where $N = p^{100}$; $p = 35671$

Thus, the challenge was to find the root of this polynomial!

To solve this challenge, we can first find a solution for the given polynomial over $mod;p$ and then use
Hensel’s lifting lemma to find a solution for the given polynomial over $mod;p^k = mod; N$. Hensel’s lifting
lemma states that:

If a polynomial equation has a simple root modulo a prime number p, then this root corresponds to a unique root of the same equation modulo any higher power of p, which can be found by iteratively “lifting” the solution modulo successive powers of p.

## Step-1: Finding roots over $mod;p$

Cool! This python/sagemath script returned the base solutions as [27020, 25020]

## Step-2: Use Hensel’s lifting to find roots over $mod;N$

We primarily used p4’s Hensel’s lifting implementation in their library crypto-commons. v4d3r tweaked it to
make it compatible with sagemath.

Running the above script gave the flag as:
p4{Th4t5_50m3_h34vy_l1ft1n9}