Homework 5: 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". 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.

You may use any programming language you like. Please implement the pairwise GCD algorithm yourself. 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. I recommend you use a library with fast arithmetic; Sage uses GMP for its integer types.

Please submit your code and a short description of how you solved the problem along with a PDF of your LaTeXed solutions to the other problems to Canvas before class on November 3. 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.