tl;dr Coppersmith’s Attack to recover RSA primes

**Challenge Points**: 200**Challenge Solves**:**Solved by**: s0rc3r3r, v4d3r, nsg99, 4lph4

The challenge is based on RSA and we are given the following script:

1 | def bytes_to_long(data): |

We are given ciphertext of two plaintext messages $ m_1 $ “You can’t factor the modulus” and $ m_2 $ “If you

don’t know the modulus!”, and encrypted text of the flag in `output.txt`

:

1 | msg1 = 4249729541274832324831915101850978041491970958978013333892918723306168770472089196478720527554982764987079625218029445015042835412969986610407794962546486526768377464483162272541733624521350257458334912357961557141551376502679112069746250223130120067678503609054343306910481618502449487751467838568736395758064426403381068760701434585433915614901796040740316824283643177505677105619002929103619338876322183416750542848507631412106633630984867562243228659040403724671325236096319784525457674398019860558530212905126133378508676777200538275088387251038714220361173376355185449239483472545370043145325106307606431828449482078191 |

Some observations:

- We are not given the public modulus in this challenge.
- Factors of the modulus
`n`

are derived and there exists a relation between them

Based on the above observations, one can say that the challenge can be solved in two steps:

- Recover the public modulus using the ciphertext-plaintext pairs
- Since there exists a relation between factors of
`n`

, recover factors based on this and decrypt the ciphertext of the flag.

## Recovering the modulus

Let the ciphertext of message $ m_1 $ be $ c_1 $ and ciphertext of message $ m_2 $ be $ c_2 $. We can write:

$ m_1^e \equiv c_1\mod n $

$ m_2^e \equiv c_2\mod n $

This implies:

$ m_1^e - c_1 = k_1*n $

$ m_2^e - c_2 = k_2*n $

where $ k_1, k_2 \in \mathbb{Z}^+ $

Hence,

$ GCD(m_1^e - c_1, m_2^e - c_2) = GCD(k_1*n, k_2*n) = k’*n $

With the above equation we can recover a multiple of `n`

, where `k'`

is a small number and can be detected

simply by brute force. We wrote the following code using sagemath (python took longer time on our laptops

to calculate since the messages are quite large) to recover `n`

1 | from Crypto.Util.number import * |

Coincidentally, GCD gave us the exact value of `n`

. We can verify this by simply encrypting the given messages $ m_1 $ and $ m_2 $ with our recovered modulus value and given exponent `e`

, and check if they match with their corresponding given ciphertexts $ c_1 $ and $ c_2 $.

Running the above code gives the value of `n`

as:

1 | N = 34825223743402829383680359547814183240817664070909938698674658390374124787235739502688056639022131897715513587903467527066065545399622834534513631867145432553730850980331789931667370903396032758515681278057031496814054828419443822343986117760958186984521716807347123949922837482460532728350223473430713058522361175980521908817215812291272284241848086260180382693014713901303747444753828636575351349026883294939561001468099252543181336195746032718177937417431101756313823635150129601855358558635996348271242920308406268552606733676301725088348399264293936151662467456410825402303921583389167882090767423931762347825907802328053 |

Now that we have value of `N`

, let’s move to the second and final step in solving the challenge!

## Factoring `N`

using Coppersmith’s Theorem

This step is almost the same as part-3 of Old-School challenge from Meepwn CTF 2018:

https://github.com/p4-team/ctf/tree/master/2018-07-13-meepwn-ctf/crypto_old_school#part3

We are given the following relation between `p`

and `q`

:

1 | tmp = randint(2**1023, 2**1024) |

We can approximate the value of `tmp`

and then try to recover `p`

and `q`

based on the approximation:

$ \Delta_1 = randint(2^{500}) $

$ \Delta_2 = randint(2^{500}) $

$ tmp = randint(2^{1023}, 2^{2014}) $

$ N = (0xdead*tmp + \Delta_1) * (0xbeef*tmp + \Delta_2)$

$ N = (0xdead*0xbeef)*tmp^2 + (0xdead*\Delta_2)*tmp + (0xbeef*\Delta_1)*tmp + (\Delta_1*\Delta_2) $

$ N = (0xdead*0xbeef)*tmp^2 + (0xdead*\Delta_2 + 0xbeef*\Delta_1)*tmp + (\Delta_1*\Delta_2) $

$ (0xdead*0xbeef)*tmp^2 + (0xdead*\Delta_2 + 0xbeef*\Delta_1)*tmp + (\Delta_1*\Delta_2 - N) == 0 $

We can take the approximate value of `tmp`

as:

$ tmp\_approx = \sqrt{\frac{N}{0xdead*0xbeef}}$

With the above approximation, we can calculate the upper bound of one of

the factors of N, let’s say q_approx as:

$ q\_approx = 0xbeef*tmp\_approx - 2^{500} $

**Note**: We still don’t have a strong mathematical explanation as to why $ q\_approx = 0xbeef*tmp\_approx - 2^{500} $ and not $ q\_approx = 0xbeef*tmp\_approx + 2^{500} $, we

deduced the formula based on the writeup for Meepwn CTF challenge mentioned earlier.

s0rc3r3r discussed it with Shalom (challenge author) about this, but the reason is still not clear; here is an

excerpt of the conversation from IRC:

So if you have a mathematical explanation, feel free to comment! I would love it!

/EONote

Now that we have q_approx, we can use Coppersmith’s Theorem to recover the actual value of q. I wrote the following script for this:

1 | hidden = 500 |

Let us see how the above script works:

We know that `q_approx`

is basically the upper bound for possible value of `q`

. To get the actual value we need to subtract a value `x`

from `q_approx`

such that the result becomes a factor of modulus `N`

.

Hence we wrote the script implementing the above idea!

If you want to learn about Coppersmith’s Attack in detail you can refer to this article from Crypton library:

https://github.com/ashutosh1206/Crypton/tree/master/RSA-encryption/Attack-Coppersmith

The full script (sagemath):

1 | from Crypto.Util.number import * |

Running the above script gives us the flag: **p4{S3cur1ty_th0ru9h_0b5cur1ty_4t_i7s_fin3s7}**