针对RSA攻击的总结

这篇文章主要是针对RSA不太常见的攻击,常见RSA加密常见的攻击方式不展开讲了,给大家推荐一个好用的RSA的工具,是由B站风二西开发的RSA工具。

轩禹CTF_RSA工具3.6.1

上面常见的RSA攻击方式都有,同时可以分解n,接入了yafu和factor网站,对于CTF比赛开始对题目分析有一定帮助,分解n也非常方便,要注意:yafu要自己下载,下载之后会自己调用。

下面的很多式子没法直接呈现,只能用图片了

CopperSmith算法和其衍生的攻击方式

关联信息攻击

就是在模n下,有两个甚至有多个参量线性相关,可以有这个攻击,后面再讲别的攻击方法的时候也会有相同之处

例题描述:
已知两条RSA密文c1和 c2,它们由两个具有已知线性关系的明文 m1和 m2加密而来:

  • 公钥模数 n 和加密指数 e 已知。
  • 明文关系已知:m2 ≡ a*m1 + b (mod n),其中 a 和 b 已知。
  • 加密方式:c1 ≡ m1^e (mod n),c2 ≡ m2^e (mod n)。

解决方法:

判断是否为线性,进行联立求解

from gmpy2 import *
from Crypto.Util.number import *
n = ……
a = ……
b = ……
c1 = ……
c2 = ……
def attack(c1, c2, a, b, e, n):
    PR.<x>=PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (a*x + b)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    print(gcd(g1, g2))
    return -gcd(g1, g2)[0]
m1 = attack(c1, c2, a, b, 5, n)
flag = long_to_bytes(int(m1))
print(flag)

在下面介绍动态题目时用到了crypto-attacks项目,里面有针对的是 Franklin-Reiter 相关明文攻击 及其变体。

当两个明文 m_1 和 m_2 之间存在某种已知的代数关系,并且使用相同的 RSA 公钥 (N, e)进行加密时,攻击者可以在不需要私钥的情况下恢复出明文。

这个提供了两种攻击方式应对不同的变形

这是第一种,是线性相关的,这个输入f的时候注意

情况 A:线性关系(最常见)

假设已知 m_1 = m且m_2 = m + 100:

# f1 是原样输出,f2 是加 100
shared_secret = attack(N, e, c1, c2, lambda x: x, lambda x: x + 100)

情况 B:仿射关系

假设已知 m_1 = 2m + 3且m_2 = 5m + 7:

shared_secret = attack(N, e, c1, c2, lambda x: 2*x + 3, lambda x: 5*x + 7)

情况 C:使用预定义函数

如果你觉得 Lambda 表达式不直观,也可以使用普通的 def:

def func1(msg):
    return msg

def func2(msg):
    return msg + 0xdeadbeef

shared_secret = attack(N, e, c1, c2, func1, func2)

第二种是非线性关系,异或的情况,x直接填那个值就行

线性填充广播攻击

例题描述:
攻击者获得了同一明文
m 在不同RSA公钥下的多条密文,且每条密文的生成规则为:

  • c_i ≡ (a_i * m + b_i)^e (mod n_i),其中 i = 1, 2, ..., k。
  • 参数已知:每个密文 c_i、对应的模数 n_i、线性系数 a_i 和 b_i、以及公共的加密指数 e。
  • 模数不同:n_i 各不相同,且互不相关。

解决方法:

这个就是类似于中国剩余定理与CopperSmith算法的结合,每个循环先定义一个多项式环,这个多项式环为Ns[i]的整数域,后面在转换整数域,再转化统一的整数域。

过程是先通过CRT将所有 f(x) 合并为一个定义在更大模数下的多项式F(x),由于 m是 F(x) ≡ 0 (mod M) 的小根,再应用Coppersmith方法求解。

from gmpy2 import *
from Crypto.Util.number import *
Cs = ……
Ns = ……
A = [56, 126, 66, 10, 54]
B = [261, 191, 877, 352, 62]
e = 3
Fs = []
for i in range(5):
    PR.<x> = PolynomialRing(Zmod(Ns[i]))
    f = (A[i]*x + B[i])^e - Cs[i]
    f = f.monic()
    f = f.change_ring(ZZ)
    Fs.append(f)
F = crt(Fs, Ns)
M = reduce(lambda x, y: x * y, Ns)
FF = F.change_ring(Zmod(M))
m = FF.small_roots()
print(long_to_bytes(int(m[0])))

**注意:**可能e不同阶,此时可以考虑两种方法:

1、若m是原方程的根,直接式子乘上m,以达到同样的解

2、通过化简代数式化简成相同的阶

泄露部分m

已知部分m

例题描述:

在RSA加密中,已知密文 c ≡ m^e (mod n)。

核心解决方法:

p=(mh+x)**e-c(modn)

from gmpy2 import *
from Crypto.Util.number import *
n = 
m = 
c = 
m = m<<100#偏移量,可以直接看成<<向左移即移向高位,>>相反
print(long_to_bytes(m))
PR.<x> = PolynomialRing(Zmod(n))
f = (m+x)^3 - c
res = f.small_roots()
m = int(res[0] + m)
print(long_to_bytes(m))

泄露部分p

已知部分p

例题描述:

已知其中一个素数因子p的高位部分,即p的前若干比特。

核心解决方法:

要利用Coppersmith的第二个作用,求解其因数的根。

p(x)=ph+x(modn)

from gmpy2 import *
from Crypto.Util.number import *
n = ……
p = ……
c = ……
p = p<<100
PR.<x> = PolynomialRing(Zmod(n))
f = p+x
res = f.small_roots(X=2^100, beta=0.4)
p = int(res[0]) + p
q = n // p
print(q)
d = inverse(65537, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(m))

泄露部分d

例题描述:

已知私钥d的低位部分,即d的后若干比特。

解决方法:

d无法直接恢复,只能通过已知的d的低位部分回复p的低位部分,之后再转化为泄露部分p解决

f(x)=2**位数*x+pl(modn)

from gmpy2 import *
from Crypto.Util.number import *
n = ……
d = ……
c = ……
e = ……
def partial_p(p0, kbits, n):
    nbits = n.nbits()
    PR.<x> = PolynomialRing(Zmod(n))
    f=p0+2^kbits*x
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)
    if roots:
        x0=roots[0]
        p=gcd(int(p0+2^kbits*x0),n)
        return int(p)
def find_p(d0, kbits, e, n):
    X = var('X')  
    for k in range(1, e+1):  
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results: 
            p0 = ZZ(x[0]) 
            p = partial_p(p0, kbits, n)
            if p:
                return p
p = find_p(d, 410, e, n) 
print(p)
q = n // p
print(q)
D = inverse(e, (p-1)*(q-1))
print(D)
print(long_to_bytes(pow(c,int(D), n)))

Boneh-Durfee攻击

简单来说是维纳攻击的Pro版

例题描述:

私钥d的规模已知(或可推测)为 d ≈ n^δ,其中 δ 大于维纳攻击的界限(δ < 0.25),但小于某个上限(δ < 0.292)。

解决方法:

它这个看题目好像维纳攻击,但私钥规模大于0.25,维纳攻击无效,因此衍生出Boneh-Durfee攻击。

下面代码用作脚本,按照题目不同调整参数即可

from Crypto.Util.number import *

N = ……
e = ……
c = ……
debug = False
strict = False
helpful_only = True
dimension_min = 7 

def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii, ii] >= modulus:
            nothelpful += 1
    print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")


def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii, jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print(a)



def remove_unhelpful(BB, monomials, bound, current):
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB   
    for ii in range(current, -1, -1):
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            for jj in range(ii + 1, BB.dimensions()[0]):
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj

            
            if affected_vectors == 0:
               
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii - 1)
                return BB

            
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(
                        bound - BB[ii, ii]):
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii - 1)
                    return BB
    return BB





def boneh_durfee(pol, modulus, mm, tt, XX, YY):   
    PR.<u,x,y> = PolynomialRing(ZZ)
    Q = PR.quotient(x * y + 1 - u)  # u = xy + 1
    polZ = Q(pol).lift()
    UU = XX * YY + 1
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x ^ ii * modulus ^ (mm - kk) * polZ(u, x, y) ^ kk
            gg.append(xshift)
    gg.sort()
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials():
            if monomial not in monomials:
                monomials.append(monomial)
    monomials.sort()
    for jj in range(1, tt + 1):
        for kk in range(floor(mm / tt) * jj, mm + 1):
            yshift = y ^ jj * polZ(u, x, y) ^ kk * modulus ^ (mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift)  
    for jj in range(1, tt + 1):
        for kk in range(floor(mm / tt) * jj, mm + 1):
            monomials.append(u ^ kk * y ^ jj)   
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU, XX, YY)
    if helpful_only:
        
        BB = remove_unhelpful(BB, monomials, modulus ^ mm, nn - 1)
        
        nn = BB.dimensions()[0]
        if nn == 0:
            print("failure")
            return 0, 0

    if debug:
        helpful_vectors(BB, modulus ^ mm)
   
    det = BB.det()
    bound = modulus ^ (mm * nn)
    if det >= bound:       
        if debug:
            diff = (log(det) - log(bound)) / log(2)          
        if strict:
            return -1, -1
    else:
        print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
    
    if debug:
        matrix_overview(BB, modulus ^ mm)
    
    if debug:
        print("optimizing basis of the lattice via LLL, this can take a long time")
    BB = BB.LLL()
    if debug:
        print("LLL is done!")
    
    if debug:
        print("looking for independent vectors in the lattice")
    found_polynomials = False
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):        
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w * z + 1, w, z) * BB[pol1_idx, jj] / monomials[jj](UU, XX, YY)
                pol2 += monomials[jj](w * z + 1, w, z) * BB[pol2_idx, jj] / monomials[jj](UU, XX, YY)          
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)          
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:    
                found_polynomials = True
                break
        if found_polynomials:
            break
    if not found_polynomials:       
        return 0, 0
    rr = rr(q, q)    
    soly = rr.roots()
    if len(soly) == 0:      
        return 0, 0
    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]   
    return solx, soly


delta = .271  
m = 8  
t = int((1 - 2 * delta) * m)  
X = 2 * floor(N ^ delta) 
Y = floor(N ^ (1 / 2))  
P.<x,y> = PolynomialRing(ZZ)
A = int((N + 1) / 2)
pol = 1 + x * (A + y)
solx, soly = boneh_durfee(pol, e, m, t, X, Y)
d = int(pol(solx, soly) / e)
print(d)
m = power_mod(c, d, N)
print(long_to_bytes(m))

二次coppersmith

针对有两个小整数根的情况

例题:

flag = b"flag{*********}"
s = bytes_to_long(flag)
p = getPrime(1024)
k = 128
d = 2
data = []
for _ in range(d):
    t = randint(1, p - 1)
    inv = inverse(s+t,p)
    h = (inv >> k) << k
    data.append((t, h))
print(p)
print(data)

exp:

from gmpy2 import *
from Crypto.Util.number import *
import itertools
p=167264670864949699243357401113153413519395292842449702828997572587750744834109623044157691349874788443790813991233493187794208993416335499200258467667251878377809772494422224799463216535077998226807333354887520008430717730163942897177961332163562331189299169807359374076510657092682573089393224676206465299481
t1=54205988582886778833457799475098659028926887812765603455747115607215401361621742985106290116194861063767444600441258507426158129383071764259602929436444817489805442555547918972855579813914210680247478024861432102196251008812915761410423068240889240928469255876570421762674154189999999792058567237621394396271
h1=2546698704243987536016492442967166113447850717026761327623738213470629383370759333483184881495588176808273661168597885481456942923393620297008613216304247190570943812048945341256947796531532546196494257883630230367512634958046836640727905189456714715052293584431397022936421091296508421575965932945498177536
t2=4343825245377051766505786024070186727131854242224107955057658697141719731502298050775438124008054391043556285558776400249635735928087246121689525142171481609750710988915493632267888553552842244530750198651613701139984013488023194742902848230076510741997604547571596886981566463754331330080252181562481666127
h2=2802720220541111900541354867712021493670777147149794113335529387112961462634010734123202153568969265423470761636550474743567712207627701527848956111416129699136305492622854346336413265233450906832479683876769460583246976169424803168278765255846550373688672750611910856303146814284162789519551077992712110080
A1=h1
A2=h2
B1=1-t1*A1
B2=1-t2*A2
PR = PolynomialRing(Zmod(p), names=['x', 'y'])
x, y = PR.gens()
f=B1*A2-B2*A1+y*(B1+A1*t2)-x*(B2+A2*t1)+x*y*(t2-t1)

k = 128
X = 2^k  # x (r1) 的上界
Y = 2^k  # y (r2) 的上界
bounds = (X, Y)

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []
root=small_roots(f, bounds, m=5)
print(root)
r1=204797914155582675798458399559613710204#由前一步的print得出结果
inv1 = (h1 + r1) % p
m = ( (1 - inv1 * t1) * inverse_mod(inv1, p) ) % p
print(long_to_bytes(m))

总结

  • 相关消息 → 多项式 GCD 或 CRT 合并
  • 广播攻击 → CRT + Coppersmith
  • 小私钥 → Boneh-Durfee格攻击
  • 两个未知数 → 二次coppersmith

动态题目

对于RSA的动态题目还是比较少的,基本上是以静态题目存在,以下的知识点是根据github上的crypto-attacks项目实现的,这个项目的全部脚本都要在sage10.8的环境里运行,在sage9.3里会报错,这个要特别注意!!!

下面的脚本只能给你一个大概的框架,不能原样照搬,还是要贴合题目修改

bleichenbacher攻击

这个脚本是针对于使用 PKCS #1 v1.5 填充标准的 RSA 加密。它通过不断向服务器发送精心构造的密文,并观察服务器返回的错误信息(填充是否合法),来逐位还原明文。这是一个比较基础的脚本,但我们所遇到的题目是动态题目,无法直接调用脚本,需要写一个连接的脚本来做桥梁,来实现这一功能

import socket
import logging
from Crypto.Util.number import bytes_to_long, long_to_bytes
# 导入你之前的攻击脚本
from bleichenbacher_attack import attack 

# 配置日志查看攻击进度
logging.basicConfig(level=logging.INFO, format='[%(levelname)s] %(message)s')

## --- 配置区 ---
TARGET_IP = "127.0.0.1"
TARGET_PORT = 1337
# 这里的 N 和 E 通常从题目给出的公钥文件 (pubkey.pem) 中提取
N = 0x... 
E = 65537
# 题目给出的需要解密的密文
C_HEX = "abcdef123456..." 
C_INT = int(C_HEX, 16)
## --------------

def padding_oracle(c_int):
    """
    连接到远程题目服务器,发送密文,根据回显判断 PKCS#1 v1.5 填充是否正确
    """
    try:
        # 1. 建立连接
        s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        s.settimeout(2.0) # 设置超时防止挂死
        s.connect((TARGET_IP, TARGET_PORT))

        # 2. 接收欢迎语(根据题目逻辑调整)
        # s.recv(1024) 

        # 3. 将整数密文转换为字节流发送
        # 长度应与模数 N 的字节数一致
        k = (N.bit_length() + 7) // 8
        payload = long_to_bytes(c_int, k)
        
        # 发送数据,可能需要 hex 编码或加换行符
        s.sendall(payload + b"\n")

        # 4. 读取服务器返回并判断
        response = s.recv(1024)
        s.close()

        # --- 核心判断逻辑 (根据 CTF 题目描述修改) ---
        # 成功的情况:服务器可能返回 "Success" 或 "Decrypted"
        # 失败的情况:服务器可能返回 "Invalid Padding" 或直接断开连接
        if b"Invalid" not in response:
            return True
        else:
            return False
            
    except (socket.timeout, ConnectionResetError):
        # 有些题目在填充错误时会直接断开连接,这也算一种预言机信号
        return False
    except Exception as e:
        logging.error(f"Socket error: {e}")
        return False

def run():
    print(f"[*] 正在连接 {TARGET_IP}:{TARGET_PORT} 开始攻击...")
    
    # 执行 Bleichenbacher 攻击
    # attack 函数会不断调用 padding_oracle 进行网络交互
    m_int = attack(padding_oracle, N, E, C_INT)

    if m_int:
        m_bytes = long_to_bytes(m_int)
        print(f"\n[+] 还原成功!原始字节 (含填充): {m_bytes.hex()}")
        # 尝试提取末尾的 Flag
        if b"\x00" in m_bytes:
            flag = m_bytes.split(b"\x00")[-1]
            print(f"[+] 提取到的明文内容: {flag}")
    else:
        print("\n[-] 攻击失败,请检查 Oracle 判断逻辑。")

if __name__ == "__main__":
    run()

desmedt_odlyzko攻击

这段代码实现的是 Desmedt-Odlyzko 攻击(也称为 选定明文伪造攻击)。

这是一种非常高明的 RSA 签名伪造手段。它的核心逻辑是:即使你不知道私钥,只要你能通过“签名预言机”获得一些特定消息的签名,你就可以利用这些已有的签名,通过线性代数运算,“拼凑”出你想要的目标消息的合法签名。

但得知道服务器加密的逻辑。 这个攻击主要是用在动态环境中

交互脚本

from pwn import *
import hashlib
from sage.all import ZZ
# 假设你的 Desmedt-Odlyzko 脚本保存在 desmedt_odlyzko.py 中
from desmedt_odlyzko import attack 

## --- 1. 配置基础参数 ---
HOST = '10.0.0.1'
PORT = 1337
N = 0x... 
E = 65537
TARGET_MESSAGE = b"Transfer 1000000 to Hacker's Account"

# 建立长连接,避免频繁重连
io = remote(HOST, PORT)

## --- 2. 定义 Hash Oracle (本地计算) ---
def my_hash_oracle(m_int):
    """
    模拟题目服务端的哈希逻辑
    """
    # 将整数转为字节,计算 SHA256(这里是以sha256为例)
    m_bytes = str(m_int).encode() 
    h = hashlib.sha256(m_bytes).digest()
    return bytes_to_long(h)

## --- 3. 定义 Sign Oracle (网络交互) ---
def my_sign_oracle(m_int):
    """
    与远程靶机交互获取签名
    """
    # 假设菜单 1 是签名功能
    io.sendlineafter(b"Choice: ", b"1")
    
    # 将消息转为 Hex 发送
    m_hex = hex(m_int)[2:]
    io.sendlineafter(b"Message (hex): ", m_hex.encode())
    
    # 提取返回的签名
    io.recvuntil(b"Signature: ")
    s_hex = io.recvline().strip()
    
    return int(s_hex, 16)

## --- 4. 执行攻击 ---
def start_attack():
    # 将目标消息转为整数
    target_m_int = bytes_to_long(TARGET_MESSAGE)
    
    print(f"[*] 开始伪造签名,目标消息: {TARGET_MESSAGE}")
    
    # 调用之前的攻击函数
    # 注意:如果攻击过程中发现 B 过大,程序会卡在分解步骤,建议微调消息内容
    forgery_signature = attack(
        hash_oracle=my_hash_oracle,
        sign_oracle=my_sign_oracle,
        N=N,
        e=E,
        target_m=target_m_int
    )
    
    print(f"\n[+] 伪造成功!")
    print(f"[+] 伪造签名 (Hex): {hex(forgery_signature)}")
    
    # 验证伪造结果 (验证方案:s^e % N == hash(m))
    local_hash = my_hash_oracle(target_m_int)
    if pow(forgery_signature, E, N) == local_hash:
        print("[!] 本地校验通过!现在可以提交给靶机了。")
        
        # 提交伪造的签名 (假设菜单 2 是校验功能)
        io.sendlineafter(b"Choice: ", b"2")
        io.sendlineafter(b"Message: ", TARGET_MESSAGE.hex().encode())
        io.sendlineafter(b"Signature: ", hex(forgery_signature)[2:].encode())
        print(io.recvall().decode())
    else:
        print("[-] 校验失败,请检查哈希逻辑是否一致。")

if __name__ == "__main__":
    start_attack()

lsb_oracle攻击

RSA 经典的 LSB Oracle 攻击(也称为 Parity Oracle 攻击)

已知n,e,c,不断的乘上2的几次方,服务器返回m%2的值,也就是m的是否为偶数还是奇数,从而判断m

出动态题目

动态脚本

from sage.all import ZZ, pow
from pwn import *
import log

# === 配置区域 ===
HOST = 'target.example.com'
PORT = 1337
N = 0x...
E = 65537 
C = 0x... 

def get_oracle(fake_cipher):
    io = remote(HOST, PORT, level='error')
    
    # 示例交互逻辑:
    # 1. 接收服务器菜单或提示,一定要改
    io.recvuntil(b"Give me cipher: ")
    
    # 2. 发送构造的密文 (十六进制或字符串格式)
    io.sendline(hex(fake_cipher).encode())
    
    # 3. 接收判断结果
    response = io.recvall()
    
    io.close()
    
    # 示例判断逻辑:假设服务器返回 "Even" 或 "Odd"
    if b"Even" in response:
        return 0
    else:
        return 1

def lsb_oracle_attack(N, e, c):
    """
    核心攻击逻辑
    """
    N = ZZ(N)
    left = ZZ(0)
    right = N
    current_cipher = ZZ(c)
    
    # 预先计算 2^e mod N 以节省重复开销
    multiplier = pow(2, e, N)
    
    # 迭代次数为 N 的比特数
    bits = N.bit_length()
    print(f"[*] Total bits to leak: {bits}")
    
    with pb = iter_progress('Leaking'):
        for i in range(bits):
            # 1. 密文翻倍:c' = c * 2^e mod N
            current_cipher = (current_cipher * multiplier) % N
            
            # 2. 询问 Oracle
            lsb = get_oracle(current_cipher)
            
            # 3. 根据 LSB 收缩区间
            if lsb == 0:
                right = (right + left) // 2
            else:
                left = (right + left) // 2
            
            pb.update(f"Bit {i+1}/{bits} | Range: [{hex(left)[:20]}...]")

    return int(right)

if __name__ == "__main__":
    print("[*] Starting LSB Oracle Attack...")
    
    plaintext_int = lsb_oracle_attack(N, E, C)
    
    print("\n[+] Attack Completed!")
    print(f"[*] Raw Plaintext (int): {plaintext_int}")
    
    try:
        from Crypto.Util.number import long_to_bytes
        print(f"[*] Decoded Message: {long_to_bytes(plaintext_int).decode(errors='ignore')}")
    except:
        pass

manger攻击

Manger's Attack,这是针对 RSA-OAEP 填充的一种著名选择密文攻击(Chosen Ciphertext Attack)。

与之前讨论的 LSB Oracle 攻击不同,Manger 攻击利用的是 RSA-OAEP 标准中对解密结果的一个特定检查:解密出的第一个字节是否为 0x00。

满足的条件是已知n,e,c,可以与服务器交互得到一个能判断 (f^e * c) % N 解密后首字节是否为 00 的反馈,从而不断压缩范围,最终得到p

from pwn import *
from sage.all import ZZ
import logging

# 配置日志,可以看到攻击的步骤进度
logging.basicConfig(level=logging.INFO)

# === 题目配置区域 ===
HOST = 'target.example.com'
PORT = 1337
N = ZZ(0x...)  # 填入模数 N
E = ZZ(65537) # 填入公钥指数 e
C = ZZ(0x...)  # 填入待解密的密文 c

def padding_oracle(trial_c):
    """
    此函数负责与服务器交互。
    根据 Manger 攻击的定义:
    - 如果解密后的结果第一个字节是 0x00,返回 True (Oracle 成功)
    - 否则返回 False (Oracle 失败)
    """
    try:
        # 建立连接
        io = remote(HOST, PORT, level='error')
        
        # 1. 发送构造的密文 (根据题目要求调整格式)
        # 比如:io.recvuntil(b"Please input your cipher: ")
        io.sendline(hex(trial_c).encode())
        
        # 2. 读取响应
        response = io.recvall()
        io.close()
        
        # 3. 判断逻辑 (核心!)
        # 如果 OAEP 填充正确或首字节为 0,服务器通常不会报错或返回特定信息
        if b"Success" in response or b"Decrypted" in response:
            return True
        else:
            return False
            
    except Exception as e:
        logging.error(f"Oracle connection error: {e}")
        return False


def _step_1(padding_oracle, n, e, c):
    f1 = 2
    while padding_oracle((pow(f1, e, n) * c) % n):
        f1 *= 2
    return f1

def _step_2(padding_oracle, n, e, c, B, f1):
    f2 = ((n + B) // B) * f1 // 2
    while not padding_oracle((pow(f2, e, n) * c) % n):
        f2 += f1 // 2
    return f2

def _step_3(padding_oracle, n, e, c, B, f2):
    mmin = (n + f2 - 1) // f2 # ceil_div
    mmax = (n + B) // f2      # floor_div
    while mmin < mmax:
        f = (2 * B) // (mmax - mmin)
        i = (f * mmin) // n
        f3 = (i * n + mmin - 1) // mmin # ceil_div
        if padding_oracle((pow(f3, e, n) * c) % n):
            mmax = (i * n + B) // f3
        else:
            mmin = (i * n + B + f3 - 1) // f3
    return mmin

def manger_attack(padding_oracle, n, e, c):
    # 计算字节长度 k 和边界 B
    k = (n.bit_length() + 7) // 8
    B = 2 ** (8 * (k - 1))
    
    assert 2 * B < n, "Manger 攻击条件不满足: 2B 必须小于 N"
    
    logging.info("Starting Manger's Attack...")
    
    logging.info("Step 1: Finding f1...")
    f1 = _step_1(padding_oracle, n, e, c)
    
    logging.info("Step 2: Finding f2...")
    f2 = _step_2(padding_oracle, n, e, c, B, f1)
    
    logging.info("Step 3: Binary search for m...")
    m = _step_3(padding_oracle, n, e, c, B, f2)
    
    return m

# === 执行脚本 ===
if __name__ == "__main__":
    recovered_m = manger_attack(padding_oracle, N, E, C)
    
    print("\n" + "="*30)
    print(f"解密成功!")
    print(f"明文 (int): {recovered_m}")
    print(f"明文 (hex): {hex(recovered_m)}")
    
    # 尝试转换成字符串
    try:
        from Crypto.Util.number import long_to_bytes
        print(f"明文 (bytes): {long_to_bytes(recovered_m)}")
    except:
        pass
    print("="*30)

RSA变种

对于RSA的难题,有些时候需要构建格进行解密,针对到目前为止我所学到的格攻击手法总结如下几种情况:

Dual RSA

Schmidt-Samoa密码系统

这个是刷题过程中遇见的,感觉也是比较新颖的

这个也是RSA的变种,已知的是N,C,d

加密的过程是这样,

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

def genKey(nbits):
    p = getPrime(nbits)
    q = getPrime(nbits)
    
    N = p*p*q
    d = inverse(N, (p-1)*(q-1)//GCD(p-1, q-1))
    return N,d

def encrypt(message,N):
    m = bytes_to_long(flag)
    c = pow(m, N, N)
    return c

nbits = 1024
m = bytes_to_long(flag)
N,d = genKey(nbits)
c = encrypt(m,N)

print('c =', c)
print('N =', N)
print('d =', d)

解密代码

import math
from Crypto.Util.number import *
c = 29897791365314067508830838449733707533227957127276785142837008063510003132596050393885548439564070678838696563164574990811756434599732001622138564176327233154381380717648392357672642893142367607369679906940371540867456654151408884171467638060523066406441697453971996011548195499549200103123841556085936672833238264876038160712793697159776332101536779874757463509294968879216810485825310481778472384531442206034564488532399171243463881900578407746982324779260941957792455217641883334131366614310644607114128868153897806362954456585661855569432513785225453501792356175649676419772626548071916379318631677869452985829916084336045071072493567871623113923140668031380684940109024609167449291380675124701557542736834722898328082888430566229322840781411336263268594978558564310744076581639469210462567543585251718744340216155557606004995449505782302864725856877289388008819135023371948017425832082773421030256964953984562211638060
N = 3231913372897424708803097969843687520868057190788284975066875241636436021279559026753076528399891936983240045179193386905918743759145596242896507856007669217275515235051689758768735530529408948098860529277921046146065473333357110158008648799207873976745048714516868561754202543130629713461365314627535982379718931633528922076268531363809414255082933615667770491818402126891370106045838695484124212397783571579791558324350069782623908757815983802849109451590357380624488436968737140312471089662428308113246310588336044438265822574558816510054763215983649467009345458480077882624118620789015758507736272402998721366662352794082495441303895025585316667229865533166614969641012195668280586477033200418153345241668242651407009849656745509386158276185301334443855737552801531617549980843398648751032649895403939319648954908487619711555700124294191702406981128355348449748466449951568451135718146828444185238617155432417897711198169
d = 220908195398117048628110042133057032501548264225985823161565460390793825899523662424732910718579350524590368287207857059670558852106434615134645183432670023784725430385048028248108677670095524205518013647694485975996499747580966911259433184798952372110628624294686853944766950244209186984164963987120416687012811346656498861438432610431705868541829977481875385468143747334359481673214618931159403123892213161430602430294790913847722073762999311674428134241956293914716183107414340330449465142849402354034926378025006749405210014879947411570380433942279355488861684317611066949685697268714760755591128598654573304969
a=2
mid=pow(a,N*d,N)-a
n=math.gcd(N,mid)
m=pow(c,d,n)
print(long_to_bytes(m))

以上是对RSA的总结,这是第一次发文章,知识点或许不太全,或许有点小错误,恳请大佬们及时指出,后续还会继续补充。