【CTF-Crypto】RSA-选择明密文攻击 一文通

RSA：选择明密文攻击

关于选择明/密文攻击，其实这一般是打一套组合拳的，在网上找到了利用的思路，感觉下面这个题目是真正将这个问题实现了，所以还是非常棒的一道题，下面先了解一下该知识点：(来自laz佬博客)

• 选择明文攻击：

这样可以发现n 就是这两个数的公约数，推导
$$\begin{gathered} c_2=2^e+k_{1}n \\ {c}_4=4^e+k_{2}n \\ {c}_2\ast c_2=(2^e+k_{1}n)(2^e+k_{1}n)=4^e+2\ast 2^e{k}_{1}n+(k_{1}n{)}^2 \\ {c}_2\ast c_2-c_4=(2^e+k_{1}n)(2^e+k_{1}n)=4^e+2\ast 2^e{k}_{1}n+(k_{1}n{)}^2-4^e+k_{2}n=n{K}^{\prime } \end{gathered}$$
同理可得c3*c3-c9 或者 c2*c2*c2 - c8 都会是上面这种结果形式

所以任意取两组的结果的最大公约数应该是n

个人踩坑：

注意最终使用的时候 要用最小倍数互素的两个数 否则没法解n

在上面 一个是2 一个是3 gcd（2,3）=1 所以可以成功解n

下面那个 两个都是3 gcd（3,3）=3 没办法成功解n

个人感觉这一点非常重要 因为在比赛过程中 就因为这个导致没做出来

获取n之后可以进行下一步攻击了

• 选择密文攻击

解释：密文c是我们想要去获取的真实数据（记为flagc），其中x是我们可以去构建的数据（记为myc） 推导
$$\begin{gathered} myc=x^{e}modn \\ y=flagc\ast myc=(m\ast x{)}^{e}modn \\ 这样把y发给服务器解密得到的结果就是m\ast x其中x是我们自己选择的与n互素的数 \\ 直接一除得到m \end{gathered}$$
下面上例题：

题目来源就是2024宁波天一永安杯，但是在复现的过程中，原始题目环境没了，所以把代码改成python本地交互进行复现

附件:

task.py:

import asyncio
import json
import websockets
from rsa_crypt import *async def handle_client(websocket):p = getPrime(1024)q = getPrime(1024)e = 65537crypt = RsaCrypt(p, q, e)await websocket.send("Pls send msgs and I'll return the result")async for message_raw in websocket:try:msg_json = json.loads(message_raw)if msg_json["cmd"] == "enc":data = bytes.fromhex(msg_json["data"])if b"flag" in data:await websocket.send("data can't contain \'flag\'")else:res = crypt.enc(data)if res:await websocket.send(res.hex())else:await websocket.send("args wrong")elif msg_json["cmd"] == "dec":data = bytes.fromhex(msg_json["data"])res = crypt.dec(data)if res:if b"flag" in res:await websocket.send("you can't decrypt flag")else:await websocket.send(res.hex())else:await websocket.send("args wrong")elif msg_json["cmd"] == "get_flag":with open("flag.txt", "rb") as file:flag = file.read()res = crypt.enc(flag)await websocket.send(res.hex())except AttributeError as err:await websocket.send("AttributeError: {}".format(err))except KeyError as err:await websocket.send("KeyError: {}".format(err))except TypeError as err:await websocket.send("TypeError: {}".format(err))async def main():server = await websockets.serve(handle_client, "0.0.0.0", 10002)await server.wait_closed()asyncio.run(main())

分析一下附件，主要提供了三个功能：

1. enc ：输入明文 返回密文 并且输入的明文中不能包含flag
2. dec ：输入密文 返回明文 并且返回的明文中不能包含flag
3. get_flag : 返回flag的密文

注意整套加密体系都是基于一组RSA加密的

然后这个交互方式比较新颖 是websocket，只要知道这个事情，其实还是蛮容易的，出题人给了我们交互的python文件

client.py:

import os
import websocket # pip install websocket-client
import re
import threading
import jsondef handle_input(ws):try:while True:message = input()if message.lower() == 'exit':ws.close()breakelif message.lower() == 'help':print("enc: enc <msg>")print("dec: dec <msg_enc>")print("get_flag: get_flag")print("help: help")print("exit: exit")elif message.startswith("enc"):pattern = re.compile(r'\s(.*?)$')match = pattern.search(message)if match:data = match.group(1)ws.send(json.dumps({"cmd": "enc", "data": data}))elif message.startswith("dec"):pattern = re.compile(r'\s(.*?)$')match = pattern.search(message)if match:data = match.group(1)ws.send(json.dumps({"cmd": "dec", "data": data}))elif message == 'get_flag':ws.send(json.dumps({"cmd": "get_flag"}))except websocket.WebSocketException as err:print(err)def handle_recv(ws):try:while True:msg = ws.recv()print("Msg from server: {}".format(msg[1:]))except websocket.WebSocketException as err:print(err)def main():# uri = "ws://localhost:10002"uri = input("input uri: ")print("type 'help' to get help")ws = websocket.create_connection(uri)input_thread = threading.Thread(target=handle_input, args=(ws,), daemon=True)recv_thread = threading.Thread(target=handle_recv, args=(ws,), daemon=True)recv_thread.start()input_thread.start()recv_thread.join()input_thread.join()if __name__ == "__main__":main()

改后：

task.py

from rsa_crypt import *def handle_client():p = getPrime(1024)q = getPrime(1024)e = 65537crypt = RsaCrypt(p, q, e)while 1 :cmd = input("cmd >")data = input("data >")if cmd == "enc":data = bytes.fromhex(data)if b"flag" in data:print("data can't contain \'flag\'")else:res = crypt.enc(data)if res:print(res.hex())else:print("args wrong")elif cmd == "dec":data = bytes.fromhex(data)res = crypt.dec(data)if res:if b"flag" in res:print("you can't decrypt flag")else:print(res.hex())else:print("args wrong")elif cmd == "get_flag":with open("flag.txt", "rb") as file:flag = file.read()res = crypt.enc(flag)print(res.hex())if __name__ == "__main__":handle_client()

---

解题：

---

前置基础知识：

关于hex和int和bytes的转换问题

c2 = '0x0a6a9b7b2cb6429b0ace0486a01b0be6dfe072b1b44651e090218236b6d37b0645ed672ff68d5e7ec41cef35ff7d73987ac8caf6ad8c2a386d8fc8fb112c8804efa6b87056e90b56f46225b2e0a7227f24e40cd1ae25f59030beb0938bda2d7d841144c635db363ee0d46d2f035e7607a71921d289f3aae224e2807b3a2b924d1a7ac1749882bfcff02763d3fa59e6020d3f297d6f9b97e70e8521af8d777d621076976cb7c71c9d872177b8fa674a59629aaadcc9c0497e318360629a4273f2835562d4e44ad6b8c24e5f48d8bfec723698e10748b1b6b27f60f7a734186c744097b511cf3b0746e315b6be400a815138f333494bbcfc671766f06bf44a5183'
c2 = int(c2[2:], 16)
print(c2)c2 = bytes.fromhex(c2)
c2 = bytes_to_long(c2)
print(c2)

上面这两个方法都是一样的

---

首先通过选择明文 enc 获得 n

首先这样提取一下2 4 3 9 这个四个数字加密的结果

注意在传输的时候因为只接收16进制 所以数据的长度一定要是偶数 所以要前补0

from Crypto.Util.number import *c2 = '18dad43498ef99bcf740fab4a0d841d47ea7d444fa43589668d459935ac5d49f33b5c9286b45b620cd47db42e8b06faac89c23fe226ea9c26fb5b376839751555f3a4e2630ed305f494c92e4a14f2f4e17f8fe8754a8983c23bada9f0ffde168ff9edfa8bad8600f4c2bdc2c7b24c2a95173d71624b7947ad20055f91f64eed289d83de9ec8cfbee9208f199600275bde66f6879f18cf31e7015eb57e8d336bcbd7eb8e288ee6f00aff0067dc5f2d1dec86b6e943a9a664f9bc551185c2aae7eb5ec8d23622f3c328cc376ea76dcc4e93b4f5e11f2faf16bb94e0f4abd27e39009edb183cb9bb9c5fafa6702fbe60e638fdad5b4414d2862a419647d4e9963c2'
# c2 = bytes.fromhex(c2)
# c2 = bytes_to_long(c2)
c2 = int(c2, 16)
c4 = '2de9d201fb272e6348b388986858564c60a363900d56062fe82aff41be9bc702d7e74670c4466d834ee7ee2974f91f894277ac6dbb188d052886b24a1a068194bbb53d60c9b3b3bb5f83f6224749ae96753b45c4a699c854d81d73ff2ef55c0cf2555b73c4e2d0d30765637a7407f13191db6e25787e3aecd7a6a756c5a272bd51117580b9e703845c9069e0ea1cd443b6c3b8735953638995f22e5bdf3eb0501a752dc765fc095cef2753fb20989890c79e3199bc2f26ef17a1a9eaa1d141625254494362c1b6055b290c358094af749110ccdf240352cf451fbc4b883e2ea870bfc8cfd50708446784dd02cfe08d0af5a6d65126c1af2f896992fba49b32a1'
c4 = bytes.fromhex(c4)
c4 = bytes_to_long(c4)c3 = '36705a0d4481f6fed91c9bde14b675c43365813530b8952cc932ca92754e6b41cd49b931f1c1e17b633d72a68b5cc7b99532e3c425967aaabcca9a581614d06ceab5d06907a6a148c78c6bd784337eddf15895e871f7d8878ac834d4f59d0f0b4a849864398f44c09bbc095699bcec9ba87b39648f36d7d03984fd41b776c554d8fc128c1d2e78930d4249b51f6d58b558ef6d639e660ece301559933d311559fa2069676269d4e9442fb4926ff785d1b696f53420c64e3fea0700cf36e66db1398e352095e5e5fe251851cc2bf66bcc9ee16acab3e1379f02434e04b7a2ac373c6a82258ee88b9908ec0f670bdcbf2e57ecacd36b7acf35a3c853e4cb0ccc5f'
c9 = '044ba814c1c82f43ff7a4889e8f3413dfe4ec72c31f31ab70d576183f8faa1087a026301eeb9008315f113518df67630c2ba79bf941c5738cf78ccbe8d1452acfefc2e28731d0dce39a24d20588f27cb292e9185e73e56816e897884b12b2f857f1b9a566e5565fe2166afbfcef175dc8b8293361e29540fdbdbe6d2e7e65ea32b298576c4e400fe073a91b50ec97c7307ae7e6906c1e63361074f03f8b821bd55429f7161d7c0c05650406edaf0c94cbe26e1a442d6aa4527bdb70ce7d6d1155c9884a4cf10a78e1d68a67fdd2a919b1720a0a72fbe89da25599e0d1b04c969a549cac0d6802185f8294d35f3ecc8e51ff34052679e74e2b75667069f8ed10f'
c3 = int(c3, 16)
c9 = bytes.fromhex(c9)
c9= bytes_to_long(c9)import gmpy2
print(gmpy2.gcd(c2 * c2 - c4, c3 * c3 - c9))

解得n之后

选择一个与n互素的x 先定为2测试一下

n = 16032715414973858391922072115505553924583249589860959102756767840433294451133495052970007553452554521932448831261452842632482022717930586378351925416682300801289110695586482452615115097726370136071224128287946142570794333305809297613875542364042636628694279973720665500782947643469013148558110483334922445477906616889670820981163140916119277042171383253155665772004573320513998731826184696725416178822833563136042551726041765924480362272382414738787726080960984488729479653680476479707779289631190083186571773329730791782347813567295448630512467064947881713508881619790565808541425379082620941932361583541190744879827
print(gmpy2.gcd(2, n))  #2和n互素  
#result = 1可以

通过交互 获得flagc密文

然后利用返回的密文 构造新的待解密密文

#2对应的密文为c2
c2 = '18dad43498ef99bcf740fab4a0d841d47ea7d444fa43589668d459935ac5d49f33b5c9286b45b620cd47db42e8b06faac89c23fe226ea9c26fb5b376839751555f3a4e2630ed305f494c92e4a14f2f4e17f8fe8754a8983c23bada9f0ffde168ff9edfa8bad8600f4c2bdc2c7b24c2a95173d71624b7947ad20055f91f64eed289d83de9ec8cfbee9208f199600275bde66f6879f18cf31e7015eb57e8d336bcbd7eb8e288ee6f00aff0067dc5f2d1dec86b6e943a9a664f9bc551185c2aae7eb5ec8d23622f3c328cc376ea76dcc4e93b4f5e11f2faf16bb94e0f4abd27e39009edb183cb9bb9c5fafa6702fbe60e638fdad5b4414d2862a419647d4e9963c2'
c2 = int(c2, 16)
enc = c2 * flagc % n
print(hex(enc)[2:])
print(hex(enc)[2:].zfill(512))  #如果长度不合适 可以补充一下

#结果：
flag = '0xccd8c2cef6e8cae6e8beccd8c2cefa'
print(long_to_bytes(int(flag[2:], 16)//2))  #除数就是x

拿下：