The Pretty Bad Privacy encryption tool can be used to insecurely encrypt files to a 2048-bit RSA public key using 256-bit AES.
The pdf file for your next homework assignment has been encrypted using PBP to the following RSA public key:
-----BEGIN PUBLIC KEY----- MIIBHzANBgkqhkiG9w0BAQEFAAOCAQwAMIIBBwKCAQBqQNthSEdTeQsnUp+nxnS0 b/0Iu5y6eVpruxVJClpJ8GGgIF3mWpA3fH8zL5BkJPsoZPGYxt2+6itFuxH3xuZY yI6MAPUGO0O5G918b3e8J38QVypRMAVYUd3t9nBacsKGO6ttIwgh9e6udqbVRYv2 H4FQeaeht3D9XItjQ/ZxzJiRTADuH2awh/AF8efDBBjHIywSjNhdBIw2Ay8VGXWF XNTykek1CceX6AoO8wfeyWHOaNZwBrLvAZBU1pJD2n/meecC2afWeQGo+PzTi9kW 9TfoUDIpyAIMggfZqFy/Z0mf9a5y4NKLnrq7WpXu4Q7JTq1fV4lXKQogWufSnidp AgED -----END PUBLIC KEY-----(You can also download the public key as a file.)
The encrypted file is available here. Your task is to break the RSA-encrypted AES session key and use it to decrypt the homework file. Fortunately for you, PBP uses PKCS#1v1.5 signature padding for encryption.
You will want to use Coppersmith's method to recover the key. You can find concrete examples in the lecture slides from class and a bit more detail in this survey.
You may use pure Python or any version of Sage to implement your solution, just document what version you used for the graders. The Sage 9.x code used to encrypt the homework is here. Sage's documentation for LLL lattice basis reduction is here and documentation on polynomial construction and root-finding is here.
Please submit your code as hw8-solution.py and a short description of how you solved the problem to Gradescope by June 2, 2022. Gradescope will automatically test your attack code using a different RSA key and different ciphertext, but the same attack should still work. Your program should read the public key from a file named "key.pub" and the ciphertext from a file named "hw8.pdf.enc.asc", and should write the plaintext it recovers to a file named "hw8.pdf". (You can assume the value of e in the autograder's RSA key is the same as in the key above.)
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.
For reference, we give some excerpts from the OpenPBP RFC, inspired by the OpenPGP RFC and the relevant section of the PKCS#1 RFC.
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.
8.1 Encryption-block formatting
A block type BT, a padding string PS, and the data D shall be
formatted into an octet string EB, the encryption block.
EB = 00 || BT || PS || 00 || D . (1)
The block type BT shall be a single octet indicating the structure of
the encryption block. For this version of the document it shall have
value 00, 01, or 02. For a private- key operation, the block type
shall be 00 or 01. For a public-key operation, it shall be 02.
The padding string PS shall consist of k-3-||D|| octets. For block
type 00, the octets shall have value 00; for block type 01, they
shall have value FF; and for block type 02, they shall be
pseudorandomly generated and nonzero. This makes the length of the
encryption block EB equal to k.