Homework 6: Stereotyped RSA padding

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, which I am inadvisedly recycling from the previous homework:

-----BEGIN PUBLIC KEY----- MIIBIDANBgkqhkiG9w0BAQEFAAOCAQ0AMIIBCAKCAQEAxE0wQBkl1S98Vnv0rI3X s0kudAdQbY/TX6f1vjkCFirCnkAsnNVBg5l2XdCDcAVjPz4THfEgqh1BNSO2eDAt Nzbo6qMhK8Tdc3T8ZS74G/TltI4KKPqCJO2r/6ecJJhsaK+B/1Qv1IcC93ih8zLr aODw0+lc1eoHIkFRSzIv3fm5oj3I0VRaDY3kozHVPxxHF+xElbt+cDUhurtIDDtC V3T5IOAAxliAKMUcnIZ/C+MdsAH5BLSgEspkMGAFd3oo3Bty6HVdh84khk67kNs7 PGmS7l1lAk7YECPsRUpMPwV8GJZ0UufVk1KgYU8+YhZ01p/C1eqQhFw0sdhvnvn9 PwIBAw== -----END PUBLIC KEY-----

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 may use any programming language you like. The code used to encrypt the homework is here. It uses Sage for mathematical calculations and PyCrypto for symmmetric encryption. You will probably want to use an implementation of the LLL algorithm. Sage's documentation for that function is here and documentation on polynomial construction and root-finding is here. My slides with examples of Coppersmith attacks are available here.

Please submit your code and a short description of how you solved the problem to Canvas before 10:30am on December 1. 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.