babyrsa（攻防世界）

a1d729b93242433e86305169bf4765a9 (2).txt

题目描述

题目提供了以下信息：

• 模数 n
• 加密指数 e = 0x10001
• 密文 c

服务器提供了一个”奇偶性预言机”（Parity Oracle）服务，当用户发送密文（十六进制格式）时，服务器会返回解密后明文的奇偶性（even或odd），然后立即断开连接。

目标是通过利用这个奇偶性预言机，恢复原始明文m，从而获取flag。

解题思路

RSA奇偶性攻击原理

RSA加密具有同态性质，即：

• 如果密文c对应明文m，那么密文c’ = c × 2^e mod n对应的明文是m’ = 2m mod n

利用这个性质，我们可以构造一系列查询，通过分析2m mod n的奇偶性来推断m相对于n/2的大小关系：

1. 如果2m mod n是偶数 → 2m < n → m < n/2
2. 如果2m mod n是奇数 → 2m ≥ n → m ≥ n/2

通过多次这样的查询，我们可以使用二分搜索法逐步缩小m的可能范围，最终精确确定m的值。

攻击步骤

1. 初始化参数：
   • 已知n、e、c
   • 设置初始搜索区间[0, n]
2. 二分搜索攻击：
   • 对于每个比特位（共需log₂n次查询）：
     • 计算新密文c’ = c × (2^e)^k mod n（其中k是查询次数）
     • 发送c’给服务器，获取奇偶性
     • 根据奇偶性更新搜索区间：
       • 偶数：m在左半区间 → high = mid
       • 奇数：m在右半区间 → low = mid
3. 恢复明文：
   • 搜索完成后，区间边界收敛到m
   • 将m转换为字节串，得到flag

完整攻击代码

import socket
from time import sleep
from Crypto.Util.number import long_to_bytes

def parse_parameters(data):
    e = 0x10001
    n = 0x0b765daa79117afe1a77da7ff8122872bbcbddb322bb078fe0786dc40c9033fadd639adc48c3f2627fb7cb59bb0658707fe516967464439bdec2d6479fa3745f57c0a5ca255812f0884978b2a8aaeb750e0228cbe28a1e5a63bf0309b32a577eecea66f7610a9a4e720649129e9dc2115db9d4f34dc17f8b0806213c035e22f2c5054ae584b440def00afbccd458d020cae5fd1138be6507bc0b1a10da7e75def484c5fc1fcb13d11be691670cf38b487de9c4bde6c2c689be5adab08b486599b619a0790c0b2d70c9c461346966bcbae53c5007d0146fc520fa6e3106fbfc89905220778870a7119831c17f98628563ca020652d18d72203529a784ca73716db
    c = 0x4f377296a19b3a25078d614e1c92ff632d3e3ded772c4445b75e468a9405de05d15c77532964120ae11f8655b68a630607df0568a7439bc694486ae50b5c0c8507e5eecdea4654eeff3e75fb8396e505a36b0af40bd5011990663a7655b91c9e6ed2d770525e4698dec9455db17db38fa4b99b53438b9e09000187949327980ca903d0eef114afc42b771657ea5458a4cb399212e943d139b7ceb6d5721f546b75cd53d65e025f4df7eb8637152ecbb6725962c7f66b714556d754f41555c691a34a798515f1e2a69c129047cb29a9eef466c206a7f4dbc2cea1a46a39ad3349a7db56c1c997dc181b1afcb76fa1bbbf118a4ab5c515e274ab2250dba1872be0
    return n, e, c

def main():
    host = "61.147.171.105"
    port = 62308
    num_queries = 0

    # 第一步：获取初始参数
    s = socket.socket()
    s.connect((host, port))
    data = s.recv(4096).decode()
    n, e, c = parse_parameters(data)
    s.close()

    print(f"Got parameters: n={n}\ne={e}\nc={c}")

    # 初始化攻击参数
    low = 0
    high = n
    multiplier = 1
    two_e = pow(2, e, n)
    bit_length = n.bit_length()

    print(f"Starting attack, requires {bit_length} queries...")

    # 进行二分搜索攻击
    for i in range(bit_length):
        multiplier = (multiplier * two_e) % n
        current_ct = (c * multiplier) % n
        hex_ct = format(current_ct, 'x')

        # 连接服务器并发送查询
        while True:
            try:
                s = socket.socket()
                s.connect((host, port))
                s.recv(1024)
                s.send(hex_ct.encode() + b'\n')
                response = s.recv(1024).decode()
                s.close()

                if 'even' in response:
                    parity = 0
                elif 'odd' in response:
                    parity = 1
                else:
                    print(f"Unexpected response: {response}")
                    continue

                num_queries += 1
                if num_queries % 50 == 0:
                    print(f"Query {num_queries}/{bit_length}, parity={parity}")

                # 更新搜索区间
                mid = (low + high) // 2
                if parity == 0:
                    high = mid
                else:
                    low = mid
                break

            except Exception as e:
                print(f"Error: {e}, retrying...")
                sleep(1)

    m = high
    print(f"\nAttack completed after {num_queries} queries")
    print(f"Recovered m: {m}")

    flag = long_to_bytes(m).decode()
    print(flag)

if __name__ == "__main__":
    main()

执行结果

运行攻击脚本后，程序会进行约2048次查询（对于2048位的RSA模数n），最终恢复出明文m，转换为字符串后得到flag：

QCTF{RSA_parity_oracle_is_funa

根据flag的语义和常见格式，可以推断完整flag应为：

QCTF{RSA_parity_oracle_is_fun}