针对RSA攻击的总结
主要是围绕RSA的coppersmith、动态题目、RSA变种展开
针对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:
passmanger攻击
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的总结,这是第一次发文章,知识点或许不太全,或许有点小错误,恳请大佬们及时指出,后续还会继续补充。