NSSCTF_crypto_[MoeCTF 2022]0rsa0

提示：小明文攻击    dp泄露

题目:

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

assert flag[0:7] == b'moectf{'
assert flag[-1:] == b'}'
flag = flag[7:-1]
assert len(flag) == 32

m1 = bytes_to_long(flag[0:16])
m2 = bytes_to_long(flag[16:32])

def enc1(m):
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    e = 3
    c = pow(m,e,n)
    return n,e,c

def enc2(m):
    p = getPrime(512)
    q = getPrime(512)
    e = 65537
    d = inverse(e,(p-1)*(q-1))
    n = p * q 
    dp2 = d % (p-1)
    c = pow(m,e,n)
    return n,e,c,dp2

n1,e1,c1 = enc1(m1)
n2,e2,c2,dp2 = enc2(m2)

print("n1="+ str(n1))
print("e1="+ str(e1))
print("c1="+ str(c1))
print("n2="+ str(n2))
print("e2="+ str(e2))
print("c2="+ str(c2))
print("dp2="+ str(dp2))

'''
n1=133024413746207623787624696996450696028790885302997888417950218110624599333002677651319135333439059708696691802077223829846594660086912881559705074934655646133379015018208216486164888406398123943796359972475427652972055533125099746441089220943904185289464863994194089394637271086436301059396682856176212902707
e1=3
c1=1402983421957507617092580232325850324755110618998641078304840725502785669308938910491971922889485661674385555242824
n2=159054389158529397912052248500898471690131016887756654738868415880711791524038820158051782236121110394481656324333254185994103242391825337525378467922406901521793714621471618374673206963439266173586955520902823718942484039624752828390110673871132116507696336326760564857012559508160068814801483975094383392729
e2=65537
c2=37819867277367678387219893740454448327093874982803387661058084123080177731002392119369718466140559855145584144511271801362374042596420131167791821955469392938900319510220897100118141494412797730438963434604351102878410868789119825127662728307578251855605147607595591813395984880381435422467527232180612935306
dp2=947639117873589776036311153850942192190143164329999603361788468962756751774397111913170053010412835033030478855001898886178148944512883446156861610917865
'''

首先题目给出了提示为dp泄露和小明文攻击

1. 第一部分解密：

   • 由于e1=3很小，且m1的立方远小于模数n1，可以直接对密文c1开三次方得到明文m1

   • gmpy2.iroot(c1, 3)计算c1的整数立方根，返回结果和是否精确的标志

2. 第二部分解密：

   • 题目给出了dp2 = d mod (p-1)，利用这个信息可以分解n2

   • 根据RSA原理，e*d ≡ 1 mod (p-1)(q-1)，所以e*dp ≡ 1 mod (p-1)

   • 计算gcd(2^(e*dp2) - 2, n2)可以得到p，因为2^(e*dp2) ≡ 2 mod p（费马小定理）

   • 得到p后，计算q = n2 // p，然后正常解密RSA

3. 组合flag：

   • 将两部分明文m1和m2分别转为字节，再解码为字符串。

   • 拼接成完整的flag，格式为NSSCTF{...}

下面展示脚本

from Crypto.Util.number import *  # 导入Crypto库中的数字处理工具
from gmpy2 import *  # 导入gmpy2高精度数学库

# 题目给出的参数
n1 = 133024413746207623787624696996450696028790885302997888417950218110624599333002677651319135333439059708696691802077223829846594660086912881559705074934655646133379015018208216486164888406398123943796359972475427652972055533125099746441089220943904185289464863994194089394637271086436301059396682856176212902707
e1 = 3  # 第一个RSA的公钥指数
c1 = 1402983421957507617092580232325850324755110618998641078304840725502785669308938910491971922889485661674385555242824  # 第一个密文

n2 = 159054389158529397912052248500898471690131016887756654738868415880711791524038820158051782236121110394481656324333254185994103242391825337525378467922406901521793714621471618374673206963439266173586955520902823718942484039624752828390110673871132116507696336326760564857012559508160068814801483975094383392729
e2 = 65537  # 第二个RSA的公钥指数
c2 = 37819867277367678387219893740454448327093874982803387661058084123080177731002392119369718466140559855145584144511271801362374042596420131167791821955469392938900319510220897100118141494412797730438963434604351102878410868789119825127662728307578251855605147607595591813395984880381435422467527232180612935306  # 第二个密文
dp2 = 947639117873589776036311153850942192190143164329999603361788468962756751774397111913170053010412835033030478855001898886178148944512883446156861610917865  # dp = d mod (p-1)

# 第一部分解密：e1=3的小指数攻击
# 因为e很小且m^3 < n1，可以直接开立方恢复明文
m1, is_cube = gmpy2.iroot(c1, 3)  # 对c1开三次方
print("第一部分明文：", long_to_bytes(m1))  # 将整数转为字节形式

# 第二部分解密：利用dp2泄露分解n2
# 原理：e*d ≡ 1 mod (p-1)(q-1) => e*dp ≡ 1 mod (p-1)
# 所以计算gcd(2^(e*dp2) - 2, n2) = p
temp = pow(2, e2 * dp2, n2)  # 计算2^(e*dp2) mod n2
p2 = gmpy2.gcd(temp - 2, n2)  # 计算gcd得到p
q2 = n2 // p2  # 计算q

# 计算欧拉函数和私钥d
phi = (p2 - 1) * (q2 - 1)  # 欧拉函数
d = gmpy2.invert(e2, phi)  # 计算模反元素d
m2 = pow(c2, d, n2)  # 解密得到明文
print("第二部分明文：", long_to_bytes(m2))

# 组合flag
str_m1 = long_to_bytes(m1).decode()  # 第一部分转为字符串
str_m2 = long_to_bytes(m2).decode()  # 第二部分转为字符串
print('完整flag：NSSCTF{' + str_m1 + str_m2 + '}')  # 组合成flag

运行后flag为

NSSCTF{T8uus_23jkjw_asr_3d32awd!5f&#@sd}