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

  1. \textbf{for}~ e_2 \in E_2
    1. \quad \text{compute inverse of } e_2 \mod (p_2-1)(q_2-1) = d_2
    2. \quad H[g^{-1}(c,d_2)] \leftarrow e_2
  2. \textbf{for}~ e_1 \in E_1:
    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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s