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 $n$.

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 $m$; produce the ciphertext that corresponds to the integer $2m$. (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 $n$ doesn't end up "by chance" easily factored by a special-purpose factorization algorithm.

For the provided modulus $n$, 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 $|p-q| < 2^{30}$). Use this knowledge to find the factorization of $n$ in a matter of seconds and recover the secret decryption exponent $d$. 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)$ for a 2048-bit RSA cryptosystem. You can use Sage's built-in is_prime() function to quickly test an integer for primality.