id0-rsa.pubのメモ【CCA on Textbook RSA】

CCA on Textbook RSA

以下問題文。

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.

https://id0-rsa.pub/problem/rsa_oracle/[message]このURLに暗号文をくっつけて送ると復号してくれるらしい。しかし、肝心の与えられた暗号文を送ると403が返ってくるので困る。。。
与えられた暗号文をc1、平文をm1とすると、c1 = ( m1 ** e ) % Nとなる。また、公開鍵が用意されているので、平文m2を用意し、m2の暗号文をc2とすると、c2 = (m2 ** e) % Nとなる。
ここで、（c1 * c2) % Nをc12としてRSAによる復号を行うと、平文m12は以下のようになる。

m12 = (c1 * c2) % N = (((m1 ** e) * (m2 ** e))**d) % N = (m1 * m2) % N

よってm1 = m12 // m2となり、与えられた暗号文の平文を求めることができる。
まず、公開鍵の中身を確認してeとNを確認。

openssl rsa -text -noout -pubin -in pub.key

あとは先ほど示した手順をプログラムで書く。

import requests

def decrypt(ciphertext):
    return requests.get("https://id0-rsa.pub/problem/rsa_oracle/{}".format(ciphertext)).text

ciphertext = "912fcd40a901aa4b7b60ec37ce6231bb87783b0bf36f824e51fe77e9580ce1adb5cf894410ff87684969795525a63e069ee962182f3ff876904193e5eb2f34b20cfa37ec7ae0e9391bec3e5aa657246bd80276c373798885e5a986649d27b9e04f1adf8e6218f3c805c341cb38092ab771677221f40b72b19c75ad312b6b95eafe2b2a30efe49eb0a5b19a75d0b31849535b717c41748a6edd921142cfa7efe692c9a776bb4ece811afbd5a1bbd82251b76e76088d91ed78bf328c6b608bbfd8cf1bdf388d4dfa4d4e034a54677a16e16521f7d0213a3500e91d6ad4ac294c7a01995e1128a5ac68bfc26304e13c60a6622c1bb6b54b57c8dcfa7651b81576fc"
cipher = int(ciphertext, 16)

N = 21417796527836084184909381847347996579544574856536138887095572895605838936183797133497945149041143747935697840040038878051837066916098917830507702189036474052559440023560073044871506915412125924451079846179181310933243078160174081203833277764294560781167257508183474040791469949490073063621508350223394644084480243319785802072416191661242887403456436340352491914665462451622845195529700750590231557792010569404312659993869936897967297972271825868537334316050945924043213637990528504616783764719232801862604492419501841834817152625201356251989468366357139655821655574801663780279380761798039447128430604777726363650041
e = 65537

c1 = cipher
m2 = 3
c2 = (m2 ** e) % N

c12 = (c1 * c2) % N
m12 = int(decrypt(hex(c12)[2:]), 16)

m1 = m12 // m2
solution = hex(m1)[2:]
print(solution)