CoCalc Public Files4 - RSA / RSA.sagewsOpen in CoCalc with one click!
Author: Gabriel Chênevert
Description: Crypto @ ISEN Lille -- Lab 4: RSA
%html <h1> Lab 4 - RSA </h1> <br> <h2>A) Using RSA</h2> Check that you understand the arithmetic involved in the operation of the RSA cipher by encrypting a message of your choice with the following provided modulus and public encryption key:

Lab 4 - RSA


A) Using RSA

Check that you understand the arithmetic involved in the operation of the RSA cipher by encrypting a message of your choice with the following provided modulus and public encryption key:
load("n.sage"); n
load("e.sage"); e

I would like you to write your own modular exponentiation function to really appreciate how fast this operation is once it is performed properly. You can check it against Sage's built-in modular capabilities: Zmod(n) is used to denote the ring of integers modulo nn.

For example, here is the encryption of the string "Test vector", viewed as an integer written in base 256:

m = Zmod(n)(ZZ("Test vector".encode("hex"),16)) m^e

B) Exploiting RSA malleability

One of the weaknesses of unpadded RSA is the fact that an attacker can easily manipulate a ciphertext to produce a predictable effect on the plaintext. Demonstrate this by performing the following: in the file c.sage you will find the encrypted version of some secret integer mm; produce the ciphertext that corresponds to the integer 2m2m. (Since you have the encryption key, you can easily produce the ciphertexts corresponding to any plaintext of your liking.)

C) Breaking RSA

Generating RSA parameters is a bit more tricky than it might seem because special care should be exercised so that the modulus nn doesn't end up "by chance" easily factored by a special-purpose factorization algorithm.

For the provided modulus nn, you can try to ask Sage for its factorization: (but don't hold your breath... and be kind enough to stop the process at some point)

factor(n)

However, I was careless during the prime generation step and ended up with two primes that stand uncomfortably close to each other (say, with pq<230|p-q| < 2^{30}). Use this knowledge to find the factorization of nn in a matter of seconds and recover the secret decryption exponent dd. Verify your findings by decrypting the ciphertext provided in the file c.sage.

D) Parameter generation

Help me by generating a set of valid parameters (n,e,d)(n,e,d) for a 2048-bit RSA cryptosystem. You can use Sage's built-in is_prime() function to quickly test an integer for primality.