The challenge describes the following cryptosystem:
$h\equiv g^x\ mod\ p$
$s\equiv h^y\ mod\ p$
$c1\equiv gy\ mod\ p$
$c2\equiv ms\ mod\ p$
p, g, h are released as part of the public key and (c1, c2) form the ciphertext. To recover $m$, we can multiply equation (4) with $s^{-1}$ (remember that division is not defined modulo p!), so $m=c2\cdot s^{-1}\ mod\ p$. From equation (2), we can calculate $s$ if we have $y$, since we already have $h$. It turns out that we can recover $y$ by multiplying $g^{-1}$ to both sides of equation (3)! So $y\equiv c1\cdot g^{-1}\ mod\ p$. $g^{-1}$ and $s^{-1}$ can be calculated using Fermat’s Little Theorem, which states that $a^{p-1}\equiv 1\ mod\ p$ if $p$ is prime (which it is in this challenge) from which we obtain that $a^{-1}\equiv a^{p-2}\ mod\ p$.
p = 163096280281091423983210248406915712517889481034858950909290409636473708049935881617682030048346215988640991054059665720267702269812372029514413149200077540372286640767440712609200928109053348791072129620291461211782445376287196340880230151621619967077864403170491990385250500736122995129377670743204192511487
g = 90013867415033815546788865683138787340981114779795027049849106735163065530238112558925433950669257882773719245540328122774485318132233380232659378189294454934415433502907419484904868579770055146403383222584313613545633012035801235443658074554570316320175379613006002500159040573384221472749392328180810282909
h = 36126929766421201592898598390796462047092189488294899467611358820068759559145016809953567417997852926385712060056759236355651329519671229503584054092862591820977252929713375230785797177168714290835111838057125364932429350418633983021165325131930984126892231131770259051468531005183584452954169653119524751729
(c1, c2) = (159888401067473505158228981260048538206997685715926404215585294103028971525122709370069002987651820789915955483297339998284909198539884370216675928669717336010990834572641551913464452325312178797916891874885912285079465823124506696494765212303264868663818171793272450116611177713890102083844049242593904824396, 119922107693874734193003422004373653093552019951764644568950336416836757753914623024010126542723403161511430245803749782677240741425557896253881748212849840746908130439957915793292025688133503007044034712413879714604088691748282035315237472061427142978538459398404960344186573668737856258157623070654311038584)
y = c1 * pow(g, p - 2, p) % p # pow(g, -1, p) can be used too for Python >= 3.8
s = pow(h, y, p)
m = c2 * pow(s, p - 2, p) % p
# This is a manual implementation of Crypto.Util.number.long_to_bytes()
res = ""
while m:
res = chr(m % 256) + res
m //= 256
print(res)
Flag: HTB{b3_c4r3ful_wh3n_1mpl3m3n71n6_cryp705y573m5_1n_7h3_mul71pl1c471v3_6r0up}
The challenge simply wants you to find a strong pseudoprime for the prime bases up to 300 for a Miller-Rabin Primality Test. It is commonly known that Carmichael numbers pass the primality test for all bases coprime to them, but Carmichael numbers are hard to find! An explanation on the Miller-Rabin Primality Test and Carmichael numbers can be found here.
The challenge also requires your number to be between 600 to 1500 bits, which makes it very very hard to find on your own. Thankfully, Arnault found one such number that is ~1300 bits long, which took me a while to Google but hey whatever works right?
Flag: HTB{c42m1ch431_num8325_423_fun_p53ud0p21m35}
The challenge describes the following cryptosystem
$N=pq$
$c_1\equiv p^{e_1}+FLAG\ mod\ N$
$c_2\equiv p^{e_2}+FLAG\ mod\ N$
$N$, $c_1$, $e_1$, $c_2$, $e_2$ are given. Then, we can do a little algebra to extract out $p$.
$c_2-c_1\equiv p^{e_2}-p^{e_1}\ mod\ N$