Coppersmith相关攻击

原理

Coppersmith 定理是在一个 e 阶模 n 的多项式\(f(x)\)中，若有根小于\(n^{\frac{1}{e}}\)，则可以用 O(log n)的算法求出根。

直接求解\(f(x)\)的根可能比较困难，在此利用LLL算法求得多项式\(g(x)\)，求得的多项式与\(f(x)\)具有相同的根\(x_0\)，\(g(x)\)具有更小的系数，且定义域为整数域。

本质思想就是把有限域上的方程转化到整数域。

理论基础

\[f(x,y) = \sum_{i=0}^{d}\sum_{j=0}^{e} a_{i,j}x^iy^j\]

Howgrave-Graham

需要构造一个系数更小的多项式，\(||g(x)||\)代表范数，即最大的系数。构造方法如下

LLL 算法

格基约化算法，通过对构造出的格，从而约化产生符合约束的多项式。

p 高位攻击

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

m=bytes_to_long(flag)
n = 25348605574630284342864323710011622959543974652863854537355760576386763162531478272446867731299572532294812374775121121761898206639041068156270466457595336452690367719842145233764550634280981441631262047763246059814963741143303914063537003244814908763379320576260885158458898112416692583017869283284022878603506583499699525249773663841642694427307104140944360804367072787670581252816486834658346431010523135392357008103555699542414687172408709153334263858639251735462278292703380745537045458408951791720967957274781161667526873251066303708008043058246747534357368350540174588670636827470901518225473676343782182718627
e = 65537

high_p = p>>462
c=pow(m,e,n)

print(high_p)
print(c)

#c = 2838585968727601235811102000208810377763570403442263788723014651093563843294336508586280687833863346617299165812054489406097873361940320732653656106836742334351707641172590772691775696065643337783752853707871271348294775407491819788305857447836923575366699374649494685209530440846553788854498950165868767060103944397665695513568787251626526985821169261973233666633938348865538364532419767347878581021598781082997830762785442482278387265054844200419966175619215512361010529309496176507520460375493466772893213031156341155066854128910227539653777680017545678773463877481232404008355330164324877400343396249494527269803
#high_p = 14719840533805965441436310401180369285271789871612468412671201109363519708733266615333097147637913934699335461421648585440665652199846830713164628016025539243988107497052

exp

from sage.all import *
n = 13139369168613206469808493070119137888363636548621629780897948879328793540933675072448361493321304924953815474270401406259487525517560528123707016104942485164559271692275987380567766009184969340122208041180122234792566147648471202470677782205185423853314467362074540818483729953544353584322270414479260852672948012862257167187569701381652931473637503302338392147780573148724508117699531886205586281824118899931516823621049590863613262210219765105389989391065557707559113268724368695051264276619633555407916385088611885715568165460641318205321508100969473959719364829756492542217470309748646183210141490634293731384313
p4=0xce2f93251a3a97404a11c1fe88cf15c7aaf26ffd508ff006933bff2e9ea0c6197a98f1188f03b74b16d564e958a84c877fc0e21faf00f0ae42f26bde226ebf7c9732f17d860b81d139799832d510b91001967fc33ff2d9fbd4c4767fa2438e48
e = 0x10001
pbits = 1024
kbits = pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
if roots:
    p = p4+int(roots[0])
    print ("n: ", n)
    print ("p: ", p)
    print ("q: ", n/p)

p 高位部分泄露

from sage.all import *
from Crypto.Util.number import *
n = 25348605574630284342864323710011622959543974652863854537355760576386763162531478272446867731299572532294812374775121121761898206639041068156270466457595336452690367719842145233764550634280981441631262047763246059814963741143303914063537003244814908763379320576260885158458898112416692583017869283284022878603506583499699525249773663841642694427307104140944360804367072787670581252816486834658346431010523135392357008103555699542414687172408709153334263858639251735462278292703380745537045458408951791720967957274781161667526873251066303708008043058246747534357368350540174588670636827470901518225473676343782182718627
p4 =0x3e67e7cacd2584224fb2026b40afbcc4281bd59f72f7801239d95c61c48ded7649924f794592fce806e032f16c2f4a90466905fc30037317074a6424d8bf078e959a1ed2d8e5c000
e = 0x10001
pbits = 1024
for i in range(0,4096):
    p4=0x3e67e7cacd2584224fb2026b40afbcc4281bd59f72f7801239d95c61c48ded7649924f794592fce806e032f16c2f4a90466905fc30037317074a6424d8bf078e959a1ed2d8e5c000
    p4=p4+int(hex(i),16)
    kbits = pbits - p4.nbits()
    p4 = p4 << kbits
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + p4
    f = f.monic()
    roots = f.small_roots(X=2^kbits, beta=0.4)
    if roots:
        p = p4+int(roots[0])
        print( "n: ", n)
        print("p: ", p)
        print ("q: ", n//p)
        break
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
print(long_to_bytes(pow(c, d, n)))

q 低位和 p 高位

from Crypto.Util.number import *
import gmpy2

p_high = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q_low = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
enc = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 65537
mod = pow(2,265)
p0 = n * inverse_mod(q_low,mod) % mod
PR.<x> = PolynomialRing(Zmod(n))
for i in range(2**5):
    f = p_high * (2^724) + p0 + (x * 32 + i) * mod
    f = f.monic()
    out_p = f.small_roots(2^454,0.4)
    if len(out_p) != 0:
        print(out_p[0])
        break
p = out_p[0] * 32 + i * mod + p_high * (2^724) + p0
# print(p)
p = 133637329398256221348922087205912367118213472434713498908220867690672019569057789598459580146410501473689139466275052698529257254973211963162087316149628000798221014338373126500646873612341158676084318494058522014519669302359038980726479317742766438142835169562422371156257894374341629012755597863752154328407
assert n % p == 0
q = n // p
fai_n = (p-1) * (q-1)
d = inverse_mod(e,fai_n)
m = pow(enc,d,n)
print(bytes.decode(long_to_bytes(m)))

dp 高位攻击

给定\(e,n,c,dp_0,k,\;dp_0=dp>>k\)

\[ edp\equiv ed\equiv 1\;mod\;(p-1)\\ edp=k(p-1)+1\\ edp+k-1=kp\\ edp+k-1 \equiv 0\; mod\; p\\ \because dp< p-1\\ \because edp=k(p-1)+1\\ \therefore e>k\\ \therefore e(dp_0 << k+x)+k-1 \equiv 0\;mod\;p \]

from Crypto.Util.number import *
import gmpy2

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
e = 7621
d = gmpy2.invert(e, phi)

flag = b"flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}"
c = pow(bytes_to_long(flag), e, n)

dp = d % (p - 1)
print(dp >> 200)
print(c, e, n)

'''

c = 46735962204857190520476434898881001530665718155698898882603422023484998388668858692912250418134186095459060506275961050676051693220280588047233628259880712415593039977585805890920089318643002597837000049626154900908543384761210358835843974072960080857150727010985827690190496793207012355214605393036388807616
e = 7621
n = 140376049134934822153964243403031201922239588054133319056483413311963385321279682186354948441840374124640187894619689719746347334298621083485494086361152915457458004998419817456902929318697902819798254427945343361548635794308362823239150919240307072688623000747781103375481834571274423004856276841225675241863
'''

EXP

from sage.all import *

n = 140376049134934822153964243403031201922239588054133319056483413311963385321279682186354948441840374124640187894619689719746347334298621083485494086361152915457458004998419817456902929318697902819798254427945343361548635794308362823239150919240307072688623000747781103375481834571274423004856276841225675241863
e = 7621
c = 46735962204857190520476434898881001530665718155698898882603422023484998388668858692912250418134186095459060506275961050676051693220280588047233628259880712415593039977585805890920089318643002597837000049626154900908543384761210358835843974072960080857150727010985827690190496793207012355214605393036388807616
s = 1153696846823715458342658568392537778171840014923745253759529432977932183322553944430236879985

def coppersmith(bits, k):
    F.<x> = PolynomialRing(Zmod(n))
    invE = inverse_mod(e, n)
    f = (s << bits) + x + (k - 1) * invE
    x0 = f.small_roots(X=2 ** bits, beta=0.44, epsilon=1/32)
    return x0

for k in range(1, e):
    bits = 200
    x0 = coppersmith(bits,k)
    if len(x0) != 0:
        x = Integer(x0[0])
        dp = x + (s << bits)
        p = (e*dp - 1) // k+1
        if p != -1:
            q = n // p
            assert n == p * q
            phi = (p-1)*(q-1)
            d = inverse_mod(e,phi)
            m=pow(c,d,n)

多元 coppersmith

原理学习 论文学习 1、 论文学习 2 脚本来源

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) #最高次项系数化为0，coefficients是多项式的降次幂排列系数
    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)
    print(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 []

具体参数说明，例如

PR.<r,s,t> = PolynomialRing(Zmod(prime))
f = r*(s^2+2*s)-t