Homework 6: Mining your Ps and Qs

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" (whose source code is on github if you're interested). 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 PyCryptodome 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 PyCryptodome for symmmetric encryption.

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

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.

- Python3 solver script named "hw6-sol.py." that takes the path to a file containing a list of RSA moduli as command line argument, and print the two moduli which share a common factor, separated by a comma.
- LaTeX typed answer PDF called "hw6-solutions.pdf"

The autograder...

- ... runs your script on a Ubuntu 22.04 Docker image
- ... has a 10 minute time limit and resource constrained (0.5 vCPU, 0.75 RAM)
- ... runs your code in a directory which contains an encrypted file named as "hw6.pdf.enc.asc" but as the decryption is much the same as it was in Homework 5, the autograder will not examine your decryption of that file, only your finding of moduli with a nontrivial common factor.

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.