NCSC CTF 2023 - RSA

This is the solution of the challenge “RSA” given during the NCSC CTF challenge. Is is about RSA on floating point numbers.

Description

I was learning rsa but something is wrong.

RSA0x01.rar

Details

Points: 500

Category: Cryptography

Solution

The encryption is RSA 1024-bit but instead of computing modulo a prime $n = pq$, the computations are done modulo a float $n = q/p$. To keep floating point computations correct, the precision is set to 2048 decimal digit. We used sage and we set the precision almost to the same value as explained in the documenbtation

1
2

sage: import json
sage: R = RealField(512*4*3.33)

We have the resulting values given in the file output.txt:

1
2
3
4
5
6
7

sage: with open("output.txt") as f:
....:     d = json.load(f)
sage: c = R(d["ciphertext"])
sage: n = R(d["n"])
sage: p = int(d["p"])
sage: q = int(d["q"])
sage: e = 3

From RSA, we have the relation: $$ m^e = k \cdot n + c = \frac{k \cdot q}{p} + c$$ For some integer $k$. To come back to integer values, we compute $c \cdot p$ and obtain $m^e \cdot p \mod q$. Indeed doing the multiplication gives:

2.44062004837057700888316254676405133079143753777493883302389343336394224268193803653505640786665901860835460820766238834515971513692080336298919726429408700000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000070046848330144485238214684592089801403946109956026093765401725220509043978138288055653346613635367680285946673535429150140753877046405182067272041160466854298310590234447915284145035198827833354030141820875627949242944339083770119648410785170751924585040120537462433986960891475286435611510900232215923780245101888484968910116263688445505902666907844080641874651177691607665488856371751740638417803140829757369113e153

Which is an integer with a a very small floating point part after all the zeros corresponding to a floating point computation error. Thus we can extract the integer part:

1
2

sage: a = int(c*p); a
2440620048370577008883162546764051330791437537774938833023893433363942242681938036535056407866659018608354608207662388345159715136920803362989197264294087

Then we multiply by $p^{-1} \mod q$ and we obtained $m^e \mod q$:

1

sage: a = a*inverse_mod(p,q) % q

Now we need to compute the cubic root of the ciphertext. Luckly, $q = 2 \mod 3$, so there is a simple formula to computed the cubic root: $$m = a^{\frac{2q-1}{3}} \mod q$$

Then we can recover the flag:

1
2
3
4
5
6

sage: q % 3
2
sage: a = a*inverse_mod(p,q) % q
sage: a = pow(a, (2*q-1)/3, q)
sage: int(m).to_bytes(64,"big")
b'\x00\x00\x00\x00\x00\x00\x00Securinets{w3ll_My_N3w_rsa_15_as_vulNEr4b1e_As_plA1nTExt}'