BCTF – Hyper RSA (partial write-up)

Note: this is only a partial solution of the challenge. We did not mange to find the final exponents (which seemingly consisted of brute force search). Since there is no public write-up on this challenge, I decided to reveal the steps we managed to solve.

In the challenge, the attacker faces a server which holds two public primes $n_1$ and $n_2$ . We are free to choose two public exponents, and then encrypt as many plaintexts we like and finally be provided with the ciphertexts. We are also given an encrypted ciphertext under some unknown pair of public and private exponents:

$c_{\text{flag}} = 3612783941217721669487918278209911521323696929552012175100130528144953435277957012327876297909487756767163399469731122537754642368918321895211682844060051902226307200945658526452184995263241224610748656158064831467711457662659609765597325107742484418555573571733455873166185394833773943367518472411975358177757721075900099526140241289604501293079211412322023186020382617546224962628798465635111775435684570876736680218992899063074934853328180993221927800114698375815660980849891750946707282694641977171200300901905249566807230865872745785916874656741470951342227797544099362706484433003094851882722308369118455538479$

First, we query the encryption oracle with $(e_1,e_2) = (3,3)$ for a set of $d_1$ and $d_2$ . From this we can obtain

$d_1 = \texttt{10432559840486091238407986988472970520548832706289214947811849537927274948127663170306003428074405328552190367462729448141199308081302292059426995808484058284071726178321093769010253718635839112005598229388426825846608726434009363031976522406362773877053508711261328048542330881490837019555160214885435900875140669728809603050591350491117516599843469193722625022900563322480961807909105162387955052982225929319214174195609467519911561107503276945625754503885658048229977674962768991890696657322679981046140557032473316966471408929891217819462873933997980207367060467826058538352787319965471115525606873525765956022755}$

$d_2 = \texttt{ 18434291248706602507692139489870142858237122452654977603780588325060940957761677692894130895254390322366008636030808286525456605529069636514428545405098930492285798039797914286961244360346191682249253213739197170737252020204823515088071850372035821706421887399346542193406844426895832785144423616572944530524268278367294169788563195945948875146318991132270424085837162202880313881956605092548244978325581097532125959221844304821670216895431833284145715755370858066969707806628244776295492128956752714968008625297831663040413012626460918795704942599285181769039738245083073355598802651145370178899779306002326153284931}$

Now, we can compute the totient function:

$\phi(n_i) = (e_i\cdot d_i - 1)/2, i \in \{1,2\}.$

Then, we can compute $(p_i,q_i) , i \in \{1,2\}$ using

$(n_i + 1 - \phi(n_i)) \pm \sqrt{(n_i+1-\phi(n_i))^2-4 \cdot n_i}.$

Ok, so we factored the two 2048-bit safe primes. Amazing! Now, the exponents we obtain are obviously not the ones used in decrypting the data in the image. So, we don’t know $e_1$ and $e_2$ . The encryption is a function $g(f(m,e_1),e_2) = c$ . By inverting $g$ , we find that
$f(m,e_1) = g^{-1}(c,e_2)$ .

$\textbf{for}~ e_2 \in E_2$

$\quad \text{compute inverse of } e_2 \mod (p_2-1)(q_2-1) = d_2$
$\quad H[g^{-1}(c,d_2)] \leftarrow e_2$

$\textbf{for}~ e_1 \in E_1:$

$\quad \textbf{if} \text{ there is a } H[f(m,e_1)] \textbf{then} \text{ output }(e_1,H[f(m,e_1)])$

This is the part I did not solve. Ideally, this gives us $(e_1,e_2)$ . Now, we compute $(d_1,d_2)$ and call $\textsf{dec}(c_{\text{flag}},d_1,d_2) = (c^d_2 \bmod n_2)^d_1 \bmod n_1$ .

grocid.net

scribbles from past, present and possibly future

BCTF – Hyper RSA (partial write-up)

Leave a Reply Cancel reply

Menu

grocid.net

scribbles from past, present and possibly future

Share this:

Like this:

Leave a Reply Cancel reply

Menu