Coppersmith多元攻击 · To1in's Blog

coppersmith多元攻击

coppersmith多元脚本

import itertools
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 []

直接看这个函数的参数，

def small_roots(f, bounds, m=1, d=None):
- f: 多项式表达式，里面的变量就是要求的低位数或者未知数
- bounds： 求解的变量的界，一般填其比特数即可
- m： 确定要使用的 $f$ 和 $N$ 的高次幂，理论上越大越好，但越大越慢
- d: 确定要使用的变量移位数，默认为 $f.degree（）$

这个函数挺好用的，简单来说，就是把被隐去的低位数当作未知数，然后把原来的式子写成，由高位已知和低位未知变量构成的多项式，然后填一下界，再一个个试m，就可以解出结果。

例题

from Crypto.Util.number import *
from random import randint, getrandbits
from sympy import nextprime
from secret import flag, secreteBitNum
hint = bytes_to_long((f’secreteBitNum = {secreteBitNum}‘).encode())
tmp_e = 65537
tmp_p = getPrime(int(512))
tmp_q = getPrime(int(512))
tmp_N = tmp_p * tmp_q
print(f’tmp_N = {tmp_N}’)
print(pow(hint, tmp_e, tmp_N))
print(tmp_p >> 180)
target_bits = int(256)
prime = getPrime(target_bits)
s = randint(prime>>10, prime)
r = getrandbits(secreteBitNum)
t = (r*(s^2 + 2*s)) % prime
gifts = [3, 2]
ks = [floor(target_bits * (gift / (gift + 1))) for gift in gifts]
leak1 = s >> (target_bits - ks[0])
leak2 = t >> (target_bits - ks[1])
p = nextprime((s*(nextprime(s) * nextprime(r) + t)))
q = getPrime(p.bit_length())
N = p*q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, N)
print(f’prime = {prime}’)
print(f’c = {c}’)
print(f’N = {N}’)
print(f’leak1 = {leak1}’)
print(f’leak2 = {leak2}’)
"""
tmp_N = 67275889677378946734903321404206582364153218707836044936581311977721676158433934674861722018390091292542128885311842688233567992017423854706617140651934525455990460080562308585391373661331461122947028205118969966760791488914164391921330229025670176008518053339148134137770309365614255463111202481834705060173
40399377632586118650556149454962332599993544072289982576457293479237148938553095258299197606759611718110458893982875730643146645623512300513916266262798465380752083932871857821720398540072426424439422364690204675516506456125988918985863308292449915493404572808822346197667419207669315093927318993921905479596
4877155090632997781879191807827231697420271396210537080241322765167927413977000532975047982026915056
prime = 82321753209337659641812698792368753307257174920293482309329229017641186204037
c = 4327179356609269294409009935591795772603625779675971467878490086808144060225614005300908314649047950861015994603326121468330956776913366179511247457747179889685304469999218104955814145411915021238933150884498316563808220329632240175418452382843973948334446343545955570063628905102384071000832724697885872043017030707897928
N = 43941665823196509154346632368475246193489316520677500866461851257383928558997955146720003171553041820199105630143274308184375615057136594812756966125202091119439909980006181740220827474838356621605513939553184451557022029987518161532780360148932769025277495283357745880781214097057768654158857096614016596756958574010574773
leak1 = 4392924728395269190263639346144303703257730516994610750658
leak2 = 838456777370923849008096179359487752850229097203212
"""

首先第一部分

hint = bytes_to_long((f'secreteBitNum = {secreteBitNum}').encode())
tmp_e = 65537
tmp_p = getPrime(int(512))
tmp_q = getPrime(int(512))
tmp_N = tmp_p * tmp_q
print(f'tmp_N = {tmp_N}')
print(pow(hint, tmp_e, tmp_N))
print(tmp_p >> 180)

已知p高位，脚本直接梭

from Crypto.Util.number import *
n = 67275889677378946734903321404206582364153218707836044936581311977721676158433934674861722018390091292542128885311842688233567992017423854706617140651934525455990460080562308585391373661331461122947028205118969966760791488914164391921330229025670176008518053339148134137770309365614255463111202481834705060173
ph = 4877155090632997781879191807827231697420271396210537080241322765167927413977000532975047982026915056
pbits = 512
kbits = pbits - ph.nbits()
ph = ph << kbits
PR.< x > = PolynomialRing(Zmod(n))
f = x + ph
pl = f.small_roots(X = 2 ^ kbits, beta = 0.4)
p = ph + int(pl[0])
q = n // p
c = 40399377632586118650556149454962332599993544072289982576457293479237148938553095258299197606759611718110458893982875730643146645623512300513916266262798465380752083932871857821720398540072426424439422364690204675516506456125988918985863308292449915493404572808822346197667419207669315093927318993921905479596
phi = (p - 1) * (q - 1)
d = inverse(65537, phi)
hint = pow(c, d, n)
print(long_to_bytes(int(hint)))
#b’secreteBitNum = 26’

第二部分

target_bits = int(256)
prime = getPrime(target_bits)
s = randint(prime>>10, prime)
r = getrandbits(secreteBitNum)
t = (r*(s^2 + 2*s)) % prime
gifts = [3, 2]
ks = [floor(target_bits * (gift / (gift + 1))) for gift in gifts]
leak1 = s >> (target_bits - ks[0])
leak2 = t >> (target_bits - ks[1])

三元copper，构造如下，其中 $r,s_{low},t_{low}$ 是未知数

(14条消息) ctfshow-吃鸡杯-Crypto-Writeup_mxx307的博客-CSDN博客

利用上面链接里的脚本就能直接跑了

import itertools
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 []

prime = 82321753209337659641812698792368753307257174920293482309329229017641186204037
leak1 = 4392924728395269190263639346144303703257730516994610750658
leak2 = 838456777370923849008096179359487752850229097203212
PR.< r, s_low, t_low > = PolynomialRing(Zmod(prime))
f = r * (((leak1<<64) + s_low) ^ 2 + 2 * ((leak1<<64) + s_low)) - (leak2<<86) - t_low
bounds = (2 ^ 26, 2 ^ 64, 2 ^ 86)
solves = small_roots(f, bounds, m=3)
print(solves)

最后就直接解RSA就好了

leak1 = 4392924728395269190263639346144303703257730516994610750658
leak2 = 838456777370923849008096179359487752850229097203212
solves = (29943235, 2837580634489900859, 63360403616040741532234070)
c = 4327179356609269294409009935591795772603625779675971467878490086808144060225614005300908314649047950861015994603326121468330956776913366179511247457747179889685304469999218104955814145411915021238933150884498316563808220329632240175418452382843973948334446343545955570063628905102384071000832724697885872043017030707897928
N = 43941665823196509154346632368475246193489316520677500866461851257383928558997955146720003171553041820199105630143274308184375615057136594812756966125202091119439909980006181740220827474838356621605513939553184451557022029987518161532780360148932769025277495283357745880781214097057768654158857096614016596756958574010574773
s = (leak1<<64) + solves[1]
t = (leak2<<86) + solves[2]
r = solves[0]
p = next_prime((s * (next_prime(s) * next_prime(r) + t)))
q = N // p
phi = (p - 1) * (q - 1)
d = inverse(65537, phi)
print(long_to_bytes(int(pow(c, d, N))))

coppersmith多元脚本

例题

讨论