1
$\begingroup$

I'm in a teacher-like position and would like my students to practice certain classes of RSA attacks. However I don't really know how to go about it and how to sensibly choose the parameters such that they have to practice the attack I had in mind when creating the challenge.

As two very concrete instances of this issue, I'd like to ask for advice on how to choose parameters such that my students have to (or are at least reasonably pushed towards) using

  • The chinese remainder theorem and / or
  • Wiener's attack on small-decryption exponent RSA.

So, how does one create RSA parameters to let them practice these two methods?

| improve this question | |
$\endgroup$
  • $\begingroup$ means if i want to prepare some exemple of rsa factorization and use for exmple the chinese remainder , how i would choose 128 bits or 256 .... $\endgroup$ – Dcoder Dec 24 '16 at 3:32
  • $\begingroup$ I have a feeling that you want to produce RSA challenges yourself and are asking now how to formulate them such that the students are forced to use CRT or Wiener's attack. Is this interpretation correct? $\endgroup$ – SEJPM♦ Dec 24 '16 at 11:41
  • $\begingroup$ I've edited your question (drastically) to be much clearer now. If I screwed up at any point don't hesitate to ping me (with @SEJPM ) or to edit your actual meaning in. As of now I have to oppose the on-going close-votes as "unclear what is being asked". $\endgroup$ – SEJPM♦ Dec 24 '16 at 17:02
  • $\begingroup$ @SEJPM Well, the word "drastically" definitely is an understatement, looking at the fact you converted an unclear one-liner into a 3-paragraph question… not bad, assuming that that's indeed what the asker intended to ask. ;) $\endgroup$ – e-sushi Dec 25 '16 at 23:43
3
$\begingroup$

So you want them to practice using the CRT and Wiener's attack. I can now explain you how I would create a challenge in this direction.
As a side note please tell your students that they have to approach these problems with CRT / Wiener or they'll be very frustrated and maybe post here to ask for solutions which we can't offer because we don't which attack has to be applied which leads to frustration on all sides.

CRT

The main benefit of the CRT is that it provides a speed-up when we can piece our modulus into many small prime factors. As such I'd like to propose the following methodology:

Pick a small bound $B$ (less than $2^{20}$ so even trial division works). Pick your desired modulus size that rules out anything but small-factor-based factoring attacks (something like 100k bits, please also tell your students that they should use a small-factor attack here). Successively pick 100-10000 random primes smaller than $B$ and apply small exponents to each of them until you are satisfied with the resulting size of the modulus. Pick a valid $e$ and a message and textbook-encrypt the message. Provide the students with $e$, the modulus and the ciphertext and ask them to recover the message. Now to get the decryption done, they'll have to factor first and then use CRT. If they're not using CRT they'll have to wait a significantly longer amount of time (minutes as opposed to seconds at least). To fine-tune these parameters I suggest you try them out with and without CRT on your personal machine until you're satisfied with the time difference.

Wiener's attack

Pick an ordinary RSA modulus, ie a 2048-bit modulus with balanced primes that withstands all known factoring attacks just like you would for a production keypair. Now pick the private exponent first, such that it satiesfies the condition for Wiener's attack, i.e. it is small enough. Then construct $e$ as you normally would $d$, encrypt a message and provide the students with the ciphertext, $e$ and the modulus. Their task is then to recover the message. Test it yourself that one can actually recover the private exponent from this given set of data. And tell your students that they need to apply Wiener's attack or "one of the attacks we discussed in class previously".

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.