CCA on Textbook RSA

Turns out padding is important


Discuss The Problem

You've recovered this ciphertext being sent to a server:

912fcd40a901aa4b7b60ec37ce6231bb87783b0bf36f824e51fe77e9580ce1adb5cf894410ff87684969795525a63e069ee962182f3ff876904193e5eb2f34b20cfa37ec7ae0e9391bec3e5aa657246bd80276c373798885e5a986649d27b9e04f1adf8e6218f3c805c341cb38092ab771677221f40b72b19c75ad312b6b95eafe2b2a30efe49eb0a5b19a75d0b31849535b717c41748a6edd921142cfa7efe692c9a776bb4ece811afbd5a1bbd82251b76e76088d91ed78bf328c6b608bbfd8cf1bdf388d4dfa4d4e034a54677a16e16521f7d0213a3500e91d6ad4ac294c7a01995e1128a5ac68bfc26304e13c60a6622c1bb6b54b57c8dcfa7651b81576fc
It was encrypted with textbook RSA. The server's public key is:
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAqalgjUvRvu7jzhFRzC0a
crh232Pkn3CqyNrlBPWRfKr3n1oWrloLj8LlWbZGj7SbZI0Clm6iMAPyCNdWtjER
LYauhV4Eguff29XpDQbVa1gSNtuam9UkLy7KgrXC+VKIUK2+eLfRg+Kx7jsuifJF
M56IBGdAoNBQSfV2o3rKqUUMUcd89bW6heVyOcKgVY7rofDmBnrTucZQCHtrNepy
64rGjABdSjikx9jUDLKRWUqDIf9sCHiBKmWag1n3Z2XNVZcVluwgGjBjjznFIwhe
E8dVnQciROpw34Tze6gTGVF2/GLHWGN4OD9aUpOwP1RDJl3451BfJ5/lYG02vPFH
+QIDAQAB
-----END PUBLIC KEY-----
The server will also decrypt any ciphertext that it's asked to, other than the original. To get the plaintext associated with a ciphertext, encode the ciphertext into the url:
https://id0-rsa.pub/problem/rsa_oracle/[message]
where the message is the ciphertext as a hex string. Recover the original message, and submit it as a lower-case hex string.

Test Vector

The ciphertext
9241dcc291a36d3163d2eec780e2a199b11f1db816952150135bda673b48fb6daa4c48927e0acc58202ffe843152e3d188e15d60b21f5ac3f6f5203ba82e1a86e15d82f2d6cc27bd35ca40a2e71f61551c3f994898fb7d2c0f3346e8237417a7b6d42c812abc2fb3d72f603f158a62bd1e8af0edb010a91741026f22e628986f6d84e5cb626bdcd7dbb3c5334a85edf903a7f68508035ff83e3a3fa7fd296046a4808b4a954d1667075255f6a98382d189476d34cc0cf023951e56f34c63a8073c0d078506ae4a22c1634203daa479ac4f106fe88b346bb46652effa186e987b99a396bc59daf1ea3f06915c0dfe9ac04b26b328eb633857e783ab87cdac4f4f
decrypts to
8d076f851f92cb76f0dbfe7b4e79575f14bc7383582ab5b4ff1ba8b0e077ba37