Names of the collaborators:
The RSA modulus is a 2048-bit integer:
we can thus use it to encrypt any byte-string of length no bigger than .
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 .
For example, here is the encryption of the string "Test vector", viewed as an integer written in base 256:
Here's another way to write the fast exponentiation function: (scanning the binary expansion of the exponent from right to left and using a temporary variable that is repeatedly squared)
Some unit tests:
Using public-key encryption with (plain-)RSA is only a matter of computing a modular power:
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 ; produce the ciphertext that corresponds to the integer . (Since you have the encryption key, you can easily produce the ciphertexts corresponding to any plaintext of your liking.)
We know that this ciphertext satisfies We would like to find some other ciphertext that decrypts to : or, taking powers on both sides, Easy enough!
Generating RSA parameters is a bit more tricky than it might seem because special care should be exercised so that the modulus doesn't end up "by chance" easily factored by a special-purpose factorization algorithm.
For the provided modulus , 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)
However, I was careless during the prime generation step and ended up with two primes tthat stand uncomfortably close to each other (say, with ). Use this knowledge to find the factorization of in a matter of seconds and recover the secret decryption exponent . Verify your findings by decrypting the ciphertext provided in the file c.sage.
If with and "close", then both and need to be close to . An exhaustive search for a divisor of starting at that number is then guaranteed to end quickly:
Just for fun, let's check that this indeed gives us the ability to decrypt messages encrypted with the RSA modulus .