打开附件：

from Crypto.Util.number import *
from shin import flag


m=bytes_to_long(flag)
r=getPrime(1024)
assert r%4==3
p=getPrime(1024)
assert pow(p,(r-1)//2,r)==1
q=getPrime(1024)
e=65537
n=p*q
a=pow(p,2,r)
c=pow(m,e,n)
print(f"n = {n}")
print(f"r = {r}")
print(f"a = {a}")
print(f"c = {c}")
'''
n = 14859096721972571275113983218934367817755893152876205380485481243331724183921836088288081702352994668073737901001999266644597320501510110156000004121260529706467596723314403262665291609405901413014268847623323618322794733633701355018297180967414569196496398340411723555826597629318524966741762029358820546567319749619243298957600716201084388836601266780686983787343862081546627427588380349419143512429889606408316907950943872684371787773262968532322073585449855893701828146080616188277162144464353498105939650706920663343245426376506714689749161228876988380824497513873436735960950355105802057279581583149036118078489
r = 145491538843334216714386412684012043545621410855800637571278502175614814648745218194962227539529331856802087217944496965842507972546292280972112841086902373612910345469921148426463042254195665018427080500677258981687116985855921771781242636077989465778056018747012467840003841693555272437071000936268768887299
a = 55964525692779548127584763434439890529728374088765597880759713360575037841170692647451851107865577004136603179246290669488558901413896713187831298964947047118465139235438896930729550228171700578741565927677764309135314910544565108363708736408337172674125506890098872891915897539306377840936658277631020650625
c = 12162333845365222333317364738458290101496436746496440837075952494841057738832092422679700884737328562151621948812616422038905426346860411550178061478808128855882459082137077477841624706988356642870940724988156263550796637806555269282505420720558849717265491643392140727605508756229066139493821648882251876933345101043468528015921111395602873356915520599085461538265894970248065772191748271175288506787110428723281590819815819036931155215189564342305674107662339977581410206210870725691314524812137801739246685784657364132180368529788767503223017329025740936590291109954677092128550252945936759891497673970553062223608
'''

本题是一个结合了RSA加密和二次剩余性质的混合加密方案，通过分析给定的加密代码和参数，需要恢复出原始的flag。

已知信息

1. RSA加密参数：n, c, e=65537
2. 特殊参数：r (1024位素数，满足r≡3(mod 4))
3. 辅助参数：a = p² mod r
4. 断言条件：pow(p,(r-1)//2,r)==1（确保p是模r的二次剩余）

解题思路

核心原理

1. 欧拉准则：若p是模r的二次剩余，则p^((r-1)/2) ≡ 1 (mod r)
2. 模平方根计算：当r≡3(mod 4)时，若a是模r的二次剩余，则a的平方根为±a^((r+1)/4) mod r
3. RSA分解：通过恢复p的值来分解n=p×q

解题步骤

1. 计算模平方根：利用a和r计算p的值
2. 分解n：用恢复的p值整除n得到q
3. RSA解密：计算私钥d并解密密文c

详细解题过程

步骤1：计算p的值

根据题目给出的参数：

1. r = 145491538843334216714386412684012043545621410855800637571278502175614814648745218194962227539529331856802087217944496965842507972546292280972112841086902373612910345469921148426463042254195665018427080500677258981687116985855921771781242636077989465778056018747012467840003841693555272437071000936268768887299
2. a = 55964525692779548127584763434439890529728374088765597880759713360575037841170692647451851107865577004136603179246290669488558901413896713187831298964947047118465139235438896930729550228171700578741565927677764309135314910544565108363708736408337172674125506890098872891915897539306377840936658277631020650625

由于r≡3(mod 4)，我们可以直接计算a的模平方根：

步骤2：验证并分解n

计算得到p的候选值后，验证其是否能整除n：

1. 若n % p == 0，则p为正确值
2. 否则尝试r-p（另一个可能的根）

得到p后，计算q = n // p。

步骤3：RSA解密

1. 计算φ(n) = (p-1) × (q-1)
2. 计算私钥d = e^(-1) mod φ(n)
3. 解密明文m = c^d mod n
4. 将m转换为字节串得到flag

完整代码：

from Crypto.Util.number import *
import gmpy2

n = 14859096721972571275113983218934367817755893152876205380485481243331724183921836088288081702352994668073737901001999266644597320501510110156000004121260529706467596723314403262665291609405901413014268847623323618322794733633701355018297180967414569196496398340411723555826597629318524966741762029358820546567319749619243298957600716201084388836601266780686983787343862081546627427588380349419143512429889606408316907950943872684371787773262968532322073585449855893701828146080616188277162144464353498105939650706920663343245426376506714689749161228876988380824497513873436735960950355105802057279581583149036118078489
r = 145491538843334216714386412684012043545621410855800637571278502175614814648745218194962227539529331856802087217944496965842507972546292280972112841086902373612910345469921148426463042254195665018427080500677258981687116985855921771781242636077989465778056018747012467840003841693555272437071000936268768887299
a = 55964525692779548127584763434439890529728374088765597880759713360575037841170692647451851107865577004136603179246290669488558901413896713187831298964947047118465139235438896930729550228171700578741565927677764309135314910544565108363708736408337172674125506890098872891915897539306377840936658277631020650625
c = 12162333845365222333317364738458290101496436746496440837075952494841057738832092422679700884737328562151621948812616422038905426346860411550178061478808128855882459082137077477841624706988356642870940724988156263550796637806555269282505420720558849717265491643392140727605508756229066139493821648882251876933345101043468528015921111395602873356915520599085461538265894970248065772191748271175288506787110428723281590819815819036931155215189564342305674107662339977581410206210870725691314524812137801739246685784657364132180368529788767503223017329025740936590291109954677092128550252945936759891497673970553062223608



exponent = (r + 1) // 4
p_candidate = pow(a, exponent, r)
print(f"[+] 计算出的 p 的候选值: {p_candidate}")

if n % p_candidate == 0:
    p = p_candidate
    q = n // p
    print("[+] 找到正确的 p，成功分解 n!")
elif n % (r - p_candidate) == 0:
    p = r - p_candidate
    q = n // p
    print("[+] 找到正确的 p (取负根)，成功分解 n!")
else:
   
    raise ValueError("无法通过平方根分解 n，请检查数据。")

# 3. 计算 RSA 私钥参数
phi = (p - 1) * (q - 1)
e = 65537

# 计算模逆元 d
d = inverse(e, phi) # 这里使用 Crypto.Util.number 中的 inverse 或 gmpy2.invert

# 4. RSA 解密
m = pow(c, d, n)

# 5. 转换为字符串并输出
flag = long_to_bytes(m)
print(f"\n[+] 解密得到的 Flag: {flag.decode('utf-8', errors='ignore')}")
    

最后得到flag为HDCTF{0ce04f81-516b-4132-81a2-b0b7166e03ad}