p1–小明文攻击(在n较大，m较小时可以考虑使用)

p,q为5120为大素数，相应的n就会很大，那么考虑此时m相对就很小，于是有c = m**e 即在c和m**e取模过程中无损失，就可以使用gmpy2中的iroot函数进行开方，用法为iroot(a,b)返回结果为m = mpz(d)，true/false，需要注意的是这里mqz(d)中，d是结果，mqz是对整数的封装，结果true和false分别代表是否能够完全开平方，同时，这是一个元，想要用结果需要以m[0]的形式使用，用m[0]转换字符串即可得到flag

p2–低加密指数攻击(e很小，n很大时)

这次p和q比较正常，但可以看出e很小，同时n依旧很大，于是考虑用上一题方法，但解不出来，说明m**e > n，所以要用其他的方法，比如可以看到c还是比较大的，那么依旧考虑m较小，则通过 m**e = c + k*n可以爆破k来求得m。这是因为m较小的同时，e很小而c又很大，所以k注定不是很大。爆破出结果是11.

p3–rabin算法加密

无敌了兄弟，两个小时就这么过去了，怎么这么难

简单了解了一下本题需要的中国剩余定理，欧拉准则，二次剩余还有关键的rabin加密算法。结果发现还是看不懂wp，寄希望于ai能教会我吧

学了个半成，总结一下吧

首先本题限定了p = q = 3 (mod4) 以及 e = 2 这两个条件，提示我们这一题用rabin（雷宾）算法，使用这个算法需要了解中国剩余定理，二次剩余，欧拉准则，费马小定理以及rabin算法的加密解密原理。

所谓rabin算法加密，不是单向的加密解密，而是会解密出多个明文，通常答案在这些多个明文之中。先取得两个大素数p和q使得它们在模4的情况下和3同模。其次取得e=2。n = p*q，c = m^2(modn)。

解密原理则是m^2=c（modn），又因为n = p*q，则可以将上式化为

m^2=c(modp)

m^2=c(modq)

证明过程如下：

x² ≡ c (mod n)
⇒ x² – c ≡ 0 (mod n)
⇒ x² – c = k × n (对于某个整数k)
⇒ x² – c = k × p × q
⇒ x² – c = (k × q) × p
⇒ x² – c ≡ 0 (mod p)
⇒ x² ≡ c (mod p)

同理可得x²≡c (mod q)

在此基础上对两边进行开方可得到四个式子分别进行联立即可得到四个方程组，这里直接上图

但这里咱们的c未必是能开方的数字，所以我们换一种方法，将 x² ≡ c (mod p)开放后的结果转化为

x ≡ c^((p+1)/4) (mod p)这种形式，证明过程如下：

设 x = c^((p+1)/4) mod p

计算 x² mod p:
x² = [c^((p+1)/4)]² = c^((p+1)/2) = c^((4k+3+1)/2) = c^((4k+4)/2) = c^(2k+2)

现在考虑 c^((p-1)/2) mod p:
c^((p-1)/2) = c^((4k+3-1)/2) = c^((4k+2)/2) = c^(2k+1)

根据欧拉准则，如果c是模p的二次剩余，则 c^((p-1)/2) ≡ 1 (mod p)

因此：
x² = c^(2k+2) = c^(2k+1) × c ≡ 1 × c ≡ c (mod p)

这里用到的二次剩余与欧拉准则分别如下所示

费马小定理：对于素数p和任意与p互质的整数a，有：a^(p-1) ≡ 1 (mod p)

接着用得到的方程组通过中国剩余定理来求解对应的明文即可得到结果

中国剩余定理：

rabin算法过程，欧拉准则证明，二次剩余解释来自于xenny师傅nss上的文章

中国剩余定理借鉴：中国剩余定理学习笔记 – MashiroSky – 博客园

询问ai记录：https://chat.deepseek.com/share/f8q6dqe0fpoufidekb

rabin算法详解：密码学之公钥密码体系（4）：Rabin公钥密码方案_rabin密码体制-CSDN博客

rabin算法学习视频：现代密码学｜Rabin密码体制及其数学基础_哔哩哔哩_bilibili

最终代码实现：

# from Crypto.Util.number import *
# from gmpy2 import *

# p = 67711062621608175960173275013534737889372437946924512522469843485353704013203
# q = 91200252033239924238625443698357031288749612243099728355449192607988117291739
# e = 2
# c = 5251890478898826530186837207902117236305266861227697352434308106457554098811792713226801824100629792962861125855696719512180887415808454466978721678349614

# n = p * q

# def rabin_attack(c, n, p, q):
#     # Calculate square roots modulo p and q
#     c1 = pow(c, (p+1)//4, p)
#     c2 = pow(c, (q+1)//4, q)
#     cp1 = p - c1
#     cp2 = q - c2

#     # Calculate inverses
#     t1 = invert(p, q)  # p^{-1} mod q
#     t2 = invert(q, p)  # q^{-1} mod p

#     # Use CRT to combine the roots
#     m1 = (c1 * q * t2 + c2 * p * t1) % n
#     m2 = (c1 * q * t2 + cp2 * p * t1) % n
#     m3 = (cp1 * q * t2 + c2 * p * t1) % n
#     m4 = (cp1 * q * t2 + cp2 * p * t1) % n

#     return m1, m2, m3, m4

# ms = rabin_attack(c, n, p, q)

# for m in ms:
#     print(long_to_bytes(m))

p4–Wiener攻击

从原理来说还是很简单的感觉，主要是对于用d求phi下逆元e这个等式转换，再把一些较小的数忽略后得到一个等式，即e/n约等于k/d（k为一个常数）。在此之后就需要用到连分法来求e/n的值，进而得到成组的[k，d]，再用这些d挨个作为私钥进行解密，找到含有flag开头的答案

图片来自xenny在nss上的文章

代码实现：

from Crypto.Util.number import *
from gmpy2 import *

n = 6969872410035233098344189258766624225446081814953480897731644163180991292913719910322241873463164232700368119465476508174863062276659958418657253738005689
e = 3331016607237504021038095412236348385663413736904453330557803644384818257225138777641344877202234881627514102078530507171735156112302207979925588113589669
c = 1754994938947260364311041300467524420957926989584983693004487724099773647229373820465164193428679197813476633649362998772470084452129370353136199193923837

class ContinuedFraction():
    def __init__(self, numerator, denumerator):
        self.numberlist = []  # number in continued fraction
        self.fractionlist = []  # the near fraction list
        self.GenerateNumberList(numerator, denumerator)
        self.GenerateFractionList()

    def GenerateNumberList(self, numerator, denumerator):
        while numerator != 1:
            quotient = numerator // denumerator
            remainder = numerator % denumerator
            self.numberlist.append(quotient)
            numerator = denumerator
            denumerator = remainder

    def GenerateFractionList(self):
        self.fractionlist.append([self.numberlist[0], 1])
        for i in range(1, len(self.numberlist)):
            numerator = self.numberlist[i]
            denumerator = 1
            for j in range(i):
                temp = numerator
                numerator = denumerator + numerator * self.numberlist[i - j - 1]
                denumerator = temp
            self.fractionlist.append([numerator, denumerator])


a = ContinuedFraction(e, n)
for k, d in a.fractionlist:
    m = powmod(c, d, n)
    flag = long_to_bytes(m)
    
    if b'NSSCTF' in flag:
        print(flag)