The Pretty Bad Privacy encryption tool can be used to insecurely encrypt files to a 1024-bit RSA public key using 256-bit AES.
The pdf file for your next homework assignment has been encrypted using PBP to one of the RSA moduli in this file and public exponent e = 65537. The encrypted file is available here.
Unfortunately, factoring any of the 100,000 1024-bit moduli before your homework is due is infeasible, even with the help of nifty tools such as "Factoring as a Service". However, you know that certain malfunctioning implementations can sometimes generate non-unique prime numbers. We can't promise anything, but you suspect that some of the RSA moduli in the provided list were generated without sufficient entropy, and might share common factors. If two RSA moduli share a common factor, it is trivial to compute their GCD and factor both moduli. Unfortunately, looping over all pairs of moduli does not scale well, so you'll have some difficulty finishing the homework unless you use a more efficient algorithm.
Your task is to use the method described in this paper by your professor, Section 3.3, to compute the pairwise GCDs of the provided RSA keys. Once you have discovered some RSA private keys, you can then attempt to use them to recover the RSA-encrypted AES session key and decrypt the rest of homework file.
Please implement your solution using Sage 9.x. Please implement the pairwise GCD algorithm yourself. In order to make your solution run at a reasonable speed, you definitely want to make sure you're using Sage's Integer types and the associated fast multiplication and modular reduction instead of Python's int types. You do not need to implement any of the other encryption or decryption routines; feel free to use PyCrypto or another library for that part and reuse any code you wrote for previous homeworks. The code used to encrypt the homework is here. It uses Sage for mathematical calculations and PyCrypto for symmmetric encryption.
Please submit your code as hw6-sol.py and a short description of how you solved the problem along with a PDF named hw6-solutions.pdf of your LaTeXed solutions to the other problems to Gradescope by November 17. You may discuss this assignment in small groups with classmates, but please code and write up your solutions yourself. Please credit any collaborators you discussed with and any references you used.
You may find it helpful to experiment with RSA encryption and decryption mechanics using your own key pair. You can generate a 1024-bit RSA key on the command line with OpenSSL by running
openssl genrsa -out private_key.pem 1024
For reference, we provide the following excerpt from the PBP standard describing the format of an RSA-encrypted message.
5.1. Public-Key Encrypted Messages
The body of the message consists of a string of octets that is the
encrypted session key, followed by the symmetrically encrypted data.
- multiprecision integer (MPI) of RSA encrypted value m**e mod n.
- Encrypted data, the output of the AES symmetric-key cipher
operating in CBC mode, with PKCS 7 padding.
The session key is encoded as described in PKCS#1 block encoding
EME-PKCS1-v1_5 in Section 8.1 to form the "m" value
used in the formulas above.
