RSA Coppersmith相关攻击

Coppersmith 相关攻击与 Don Coppersmith 紧密相关，他提出了一种针对于模多项式（单变量，二元变量，甚至多元变量）找所有小整数根的多项式时间的方法。我们的目标是找到在模 N 意义下多项式所有的根，这一问题被认为是复杂的。Coppersmith method 主要是通过 Lenstra–Lenstra–Lovász lattice basis reduction algorithm（LLL）方法。

Factoring with High Bits Known

已知 p 的高位，那么可以分解出 p。值得注意的是，至少需要多少位呢，根据他的论文，p 的高位是 n 的位数的 9/32，即 p 的位数的约 9/16 时，即 2048 位的 n，需要大约 576 位。

下面是 sage 脚本，kbits 为未知的 bit 位，pbar 为部分 p，用 0 填充成了1024位。

p = 137766830150623136041380426365747755338417383354858364996824130233445685487362959882710345928710173203976979937363599586650363364004428962671250293539771900993808092850969494366720586587049044637726170652027884367836254867225581157950549268894758191204727136557549014197089936322935367590781268099221744202007
n = 23710546095911196398276567081447725078873946937524275067932712345126612727633896325957775864231070493525416297636393346475550272497807785244267828840284814159966674905060190585763597893452592340388965696931486150967942683323109307016318741136605114966378115575171980916344147772997856666261448917623642041278492643329131854647912490663017398276992995726880430059403003449250783803879452904989460825660215225706368990477424483056512956308417770485997558602901359894894513886397193284206359952165691572267752192295946838817438742107056020298264631744085274006560633356825059981771493369699797767817541745125283431389643

pbits = p.nbits()
kbits = pbits - 576
pbar = p & (2**pbits - 2**kbits)
print pbar
# 0xc42fbd0aa6e156f1ada54e84add1add5b8803a68b6e767567ba6ecca2c4e6389aa4a10285cc2aa9fda67423f3e48c5f0cfdcf43ed402f2e9d5b4a6cca9d3a4f2f4387a9c1b11133c0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
roots = f.small_roots(X=2**kbits, beta=0.4) # find root < 2^kbits with factor >= n^0.4
print  roots[0]+pbar

有时候可能已知的 bit 位数要比至少需要知道的位数少一些，那么可以爆破一下。
假如只知道 564 位，要比最少值少 12 位。

p = 175601521652715948366026598443771895157064273364422321693629605296213713859135199797988545792674328110343456449867669129208426954851381660161105490491369986263925731638014202956191111978011417126046934155921659867696283034191022988319628056493045334026452521375669565039665409499917925504438823349248729323779
n = 24624878511540387722908215297739664350796603441852606276125365246233153666570019802522895094379445339676294279799133453098518272822552300253726790897539971221358442495224025125558443302124261189348350867963393643768214391085720102981946349581199806088941133996135027194512643172012534303217051986618528438411617057743657888138375190452728881142593352375736616421505550300183198957140696491278745491400446806220712094644139089538752541631514567735337114742992310838225206617105657728920006015556185550126045031178553358618429605310873581336154022406775328416208422016964496080140518498506339217932893309906756435608679

pbits = p.nbits()
pbar = p & (2**pbits - 2**460)
print pbar
# 0xfa109b26b6e9410ce9045c39e4d46ff5eac1f00ef77d4474cdd0a947a23785514168dd7ac2f3ff820fd254c48e243630c8cc827b27a8d7a79222f3f0e2936e1537ff1a7cfc9bd0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

for i in range(4096):
    kbits = 448
    tmp = i*2**448
    tmp = pbar + tmp
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + tmp
    roots = f.small_roots(X=2**kbits, beta=0.4)
    if roots:
        print roots[0]+tmp
        break

Known High Bits Message Attack

知道 N、c、e 以及明文 m 的高位，可以恢复出全部明文 m，由于算法的约束，只适用于 e 较小的情况。

n = 22337509851779482001922211919231356432506451954107871703423509060246078250129580199451913673387343326060942030141358756830362349578148369572748546481389644834884090514670161628071135842192859462136510571371948783017263357736192878054832907064942480414753808746695073279006446243498509947445288505003601253366295968902614967103050745116988851904443868681339876938178402240389447947042217734512152842551862719496274500676130245898176107239059005296507659713502490303022824611023761781989725193845476472244468265369532319591834720048229339397412535358485467726782564424950627348600385043897692466957748491726352180427541
e = 3
m = 7055195484712808233257415263037177023007385299756293618552039260327855381856464341988946605919126857377504929590447900738096261672384835492885399938645927172438460381149355167547912801934663124402731027559692086183330926462095228987330051358824736994283787956767480892354767999393627393143512261430443540836543167977716685149095016687602808154013915847954961282512563983305388060582675124420000759180497064277220134862867216989730927564616651970055759567520845966735206449809269620486886143360134047108461969694793125359302093642260015232416844336298564702991329553169194001206423152119290426281482059511175238868956
c = pow(m, e, n)

beta = 1
epsilon = beta**2 / 7
nbits = n.nbits()
kbits = floor(nbits * (beta**2 / e - epsilon))
mbar = m & (2**nbits - 2**kbits)
# mbar = 0x37e34e4ec193004e9f4cbf4a2c1f9416f6ac425d365e44e431d8fbbea082825612bc3daeac837db750f2cc02574425cb0cd9ca047806ff1bac8c0cc1506d70f4e1e333d3536bc534d37dcbe23866a82eb938e7835cb73f72a5329f7b92259d538c8057dd6d5a8a6eca8762f8e62005abdedc8e6f28a007d5491717dbdfc6840685e028d1f8c3b6017c9cc6ee06a0fa2f5d04a6db92ede9b5060570e61a93d9eab571c05dfeda0ab929873d61fbdd1e39fb6c09aefb0c0b0ae85f451c106771f55edc473f90be372155e757cb9a6363c0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)**e - c
roots = f.small_roots(X=2**kbits, beta=1) # find root < 2^kbits with factor = n
print mbar + roots[0]

Partial Key Exposure Attack

若 e 较小，已知 d 的低位，可以分解出 N

def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()
    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  # find root = n^0.3
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)

def find_p(d0, kbits, e, n):
    X = var('X')
    for k in xrange(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

n = 0x00bef498e6eb2cffe71312da47ab89d2c47db7438ea2cfa992ddddbc2a01978001fc51e286e6ebf028396cdb8b3323c60e6b9d50cd84187cf7f48e3875a2f0890f70b02333ad89db2923863ce146562286f63fb0a1d0198e3a6862ba5ac12e85a5c6d0d27cb1c81bdf69cc5bc95b8001a2f744517f9437b4ddd5a076fc0e9a5de1a7a268c40f31aa29e8dc27c0b3a182299ca7a9335b4bd4585452f6107c238e486c98dd73a5f9862e9e80b152f53381c72f897107551c281259ac3ee32c4b4f46cc03127d1bf699acd0266f3c6729253c70da0c69b1560fa172735709866b375b6eba294e1ce8b46fba798ba380080b4bf9603998cac199d9cd46e30ae8da9e7f
e = 3
d = 0x7f4dbb449cc8aa9a0cb73c2fc7b1372da924d7b46c8a710c93e9281c010faaabfd8bec59ef47f5702648925cccc284099d138b33ad65a8a54db425a3c1f5b0b4f5cac22273b13cc617aed340d98ec1af4ed5206be011097c459726e72b7459192f35e1a8768567ea46883d30e7aaabc1fa2d8baa62cfcde93915a4a809bc3e9547bb07e1ecca16e51078312e89f0561e31b55db8b0ea5bc87a6ca7464a3d7c28a68c60e2ba88fe6a7d2b300d723e549910a987da89fc0a1c0de197a3d62c501b1f0e819891b1c32a0d6c233f2a285df87bb9e5c6c72d983ff3e706696bba639f573f9c3646968f02f3a615a438e20bb7c38d53621079f2899547a95350f3abeb

beta = 0.5
epsilon = beta^2/7
nbits = n.nbits()
kbits = floor(nbits*(beta^2+epsilon))
dbar = d & (2^kbits-1)
p = find_p(dbar, kbits, e, n)
print p

使用同一公钥对两个具有某种线性关系的消息 m1 与 m2 进行加密，截获加密后的消息 c1，c2，就可能可以获得对应的消息 m1 与 m2。当然这也只适用于 e 较小的情况下。

CTFwiki 上给出了 e=3 时的详细的推导过程，结论稍作变换，如下：

有 $m_2 \equiv f(m_1) \bmod n$ ，设 $f(x) = ax + b$ ，则：

$\begin{aligned} m_1 & \equiv \frac{b}{a }\frac {c_2 + 2a^3c_1-b^3} {c_2 - a^3c_1 + 2b^3} \bmod n \\ m_2 & \equiv am_1 + b \bmod n \end{aligned}$

一个例子加脚本如下：

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

n = 27999961103260014201601899762366044820480809373312115050371564539848082302780430427153180353435842547972555444276317070162315464285259805662094975950466904346143332100273982149375001438729479277431022569903839870448135062349087009147207066544742272396268644149664238996713128005232376082829877900496646299304348315421821559800336501335516298954006115121814521763266839112690563466734472419497568032615976792893651999727618813663596037797139267825617240849717819068585676575762343613780920312897453747902340404788459363791000774663003797688834330163393702828745669979560885773858988802185505911217634633131046317608921
e = 3
m = random.getrandbits(512)
c1 = pow(m, e, n)
# c1 = 42336544435242713761362702327083797110052081731814153741848691892510555299701770082173403496941569091996783650148561914213
c2 = pow(12345*m+666, e, n)
# c2 = 79650533717963039586406188756728037886077494795998849024898248311110042259473285239905209260363818322992442547011061382127424151667791

def get_m1(a, b, c1, c2, n):
    a3 = pow(a, 3, n)
    b3 = pow(b, 3, n)
    tmp1 = ((c2 + 2*a3*c1 - b3) * b) % n
    tmp2 = ((c2 - a3*c1 + 2*b3) * a) % n
    tmp3 = gmpy2.invert(tmp2, n)
    tmp4 = (tmp1 * tmp3) % n 
    return tmp4

m1 = get_m1(12345, 666, c1, c2, n)
print m1

当然还有推广结论，在 Low-Exponent RSA with Related Messages 这个 paper 中有说。

有个 2019 红帽杯的例子，这道题将明文 m 分成了 3 段 m0 m1 m2，m3 是一个和他们有线性关系的数字，有以下同余方程组：

$\begin{cases} {m_0}^{17} - c_0 \equiv 0 \bmod n \\ {m_1}^{17} - c_1 \equiv 0 \bmod n \\ {m_2}^{17} - c_2 \equiv 0 \bmod n \\ {m_3}^{17} - c_3 \equiv 0 \bmod n \\ m_1 + m_2 + m_3 - sum \equiv 0 \bmod n \\ 65537m_0 + 66666m_1 + 12345m_2 - m_3 \equiv 0 \bmod n \end{cases}$

sage 脚本：

N = 16084923760264169099484353317952979348361855860935256157402027983349457021767614332173154044206967015252105109115289920685657394517879177103414348487477378025259589760996270909325371731433876289897874303733424115117776042592359041482059737708721396118254756778152435821692154824236881182156000806958403005506732891823555324800528934757672719379501318525189471726279397236710401497352477683714139039769105043411654493442696289499967521222951945823233371845110807469944602345293068346574630273539870116158817556523565199093874587097230314166365220290730937380983228599414137341498205967870181640370981402627360812251649
Cs = [10607235400098586699994392584841806592000660816191315008947917773605476365884572056544621466807636237415893192966935651590312237598366247520986667580174438232591692369894702423377081613821241343307094343575042030793564118302488401888197517625333923710172738913771484628557310164974384462856047065486913046647133386246976457961265115349103039946802386897315176633274295410371986422039106745216230401123542863714301114753239888820442112538285194875243192862692290859625788686421276234445677411280606266052059579743874849594812733193363406594409214632722438592376518310171297234081555028727538951934761726878443311071990, 2665348075952836665455323350891842781938471372943896177948046901127648217780657532963063228780230203325378931053293617434754585479452556620021360669764370971665619743473463613391689402725053682169256850873752706252379747752552015341379702582040497607180172854652311649467878714425698676142212588380080361100526614423533767196749274741380258842904968147508033091819979042560336703564128279527380969385330845759998657540777339113519036552454829323666242269607225156846084705957131127720351868483375138773025602253783595007177712673092409157674720974653789039702431795168654387038080256838321255342848782705785524911705, 4881225713895414151830685259288740981424662400248897086365166643853409947818654509692299250960938511400178276416929668757746679501254041354795468626916196040017280791985239849062273782179873724736552198083211250561192059448730545500442981534768431023858984817288359193663144417753847196868565476919041282010484259630583394963580424358743754334956833598351424515229883148081492471874232555456362089023976929766530371320876651940855297249474438564801349160584279330339012464716197806221216765180154233949297999618011342678854874769762792918534509941727751433687189532019000334342211838299512315478903418642056097679717, 12534425973458061280573013378054836248888335198966169076118474130362704619767247747943108676623695140384169222126709673116428645230760767457471129655666350250668322899568073246541508846438634287249068036901665547893655280767196856844375628177381351311387888843222307448227990714678010579304867547658489581752103225573979257011139236972130825730306713287107974773306076630024338081124142200612113688850435053038506912906079973403207309246156198371852177700671999937121772761984895354214794816482109585409321157303512805923676416467315573673701738450569247679912197730245013539724493780184952584813891739837153776754362]
s = 280513550110197745829890567436265496990
e = 17

l = len(Cs)
PR = PolynomialRing(Zmod(N), 'x', l)
x = PR.gens()
f1 = (65537*x[0] - 66666*x[1] + 12345*x[2] - x[3])
f2 = x[0] + x[1] + x[2] - s
Fs = [f1, f2]
Fs.extend([(x[i]**e - Cs[i]) for i in range(l)])
I = Ideal(Fs)
B = I.groebner_basis()
m = ''
for b in B[:-1][::-1]:
    assert b.degree() == 1
    mi = ZZ(-b(0, 0, 0, 0))
    m += number.long_to_bytes(mi)
print m

Broadcast Attack with Linear Padding

Basic Broadcast Attack，如果一个用户使用同一个加密指数 e 加密了同一个 m，并发送给了其他 e 个用户。那么就会产生广播攻击，这一攻击由 Hastad 提出。但如果 m 具有线性填充的情况下，仍然可以攻击。

wiki 和一篇文章讲得很清楚。

总结一下就是：

计算所有 n 的乘积 N
用 CRT（中国剩余定理）计算 $T_i$
建立在模 N 下的多项式环
计算 $g_i = (am + b)^e - c$ ，这里就是将 m 线性填充
计算 $g = \sum T_i * g_i$
将多项式的最高次项系数化简为 1
寻找 g 的 small roots

这里还是一道 2019 红帽杯的题目：

from Crypto.Util import number
from Crypto.PublicKey import RSA
from hashlib import sha256
import json

msg = "......"
assert len(msg) == 95

Usernames = ['Alice', 'Bob', 'Carol', 'Dan', 'Erin']
N = [(number.getPrime(1024)*number.getPrime(1024)) for _ in range(4)]
Pks = [RSA.construct((N[0], 3L)), RSA.construct((N[1], 3L)), RSA.construct((N[2], 5L)), RSA.construct((N[3], 5L))]

for i in range(4):
    name = Usernames[i+1]
    open(name+'Public.pem', 'wb').write(Pks[i].exportKey('PEM'))
    data = {
        'from': sha256('Alice'.encode('utf-8')).hexdigest(),
        'to': sha256(name.encode('utf-8')).hexdigest(),
        'msg': msg
    }
    data = json.dumps(data, sort_keys=True)
    m = number.bytes_to_long(data)
    c = pow(m, Pks[i].e, Pks[i].n)
    open(name+'Cipher.enc', 'wb').write(number.long_to_bytes(c))

由于转为 json 时的 sort_keys=True，明文如下：

{"from": "3bc51062973c458d5a6f2d8d64a023246354ad7e064b1e4e009ec8a0699a3043", "msg": "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "to": "cd9fb1e148ccd8442e5aa74904cc73bf6fb54d1d54d333bd596aa9bb4bb4e961"}

明文一共 256 字节，前 85 字节已知且固定，中间 95 字节是要求的，后 76 字节变化但已知。虽然这里 e 不同，但前 2 个消息 e 都为 3。 small root 要求是要小于模数 n 的1/e 次方，(95 * 8 * 3) = 2280 > (2048 * 2) = 4096，因此用 e=3 的两个消息是肯定能解出的。

脚本如下：

from functools import reduce
import gmpy2

n = [22640954010915426297543528105336952330384450618088531011357119625793898448494501497506663609855784849285525398907876276538134790104672660571045986988734940181553735321072606120202314699500278363739778074369079211145843689256590505287669735942839161428911855885590456458155064329363748319200961350927411630365040865216376414524177487935796567848859911936123339341380236990448302091898494163405105412235779642512886561370016358003336010698347498678143955122458568762096403790726234733150025523728208604296207618681332434084455073366261052188714542076320237939478873949747102243580154745787685503612471585445641863188821, 17185478427836233889977748259262193452533213495836579877208609929707148397748583763053465797489213211142546950064850736687530533912181421568197458172993286500158251002596929717067363320396944846894867284019805974873358131331204344638194311468053608259346847591013685916511502272078591981284689005017177904034867725712068700518596026786671279073178274036774287547118666837874200411898039752679851992331405120058786633762319995417729026365492716080681181920311984799998451041728844282139324421575413693935806208318149127723071698867839793453070020689655967019199905364597561666449498984362711517175472632403749799549419]
c = [20049756238757336773611425027754063851844530356356700275349597330233222825639363254545383650014460396919361821299074996792116686523592665988019553368844062797742891025618754381338918927913901475928546510853688033255728177886898473942111364973182284906848518846632526761003652574683558105642149836977572074849487246635916582016336152081912194540608488986200464074714773114022937236260472436752302741496757951956036075134581782184201109851032611683309115615957031615915765172845231692192116644937575462751179315488815615634404170486004421843514599598352298133293828549652244774101011802250318894035577044523084175682601, 8395962151907610208152162942051461086214858395050766001242858315025145675473041053361712657775405730404150299462221408095466296230462361403089375927560531861556633206570997145738346209847103343864627640675424395013141994189650109554225472172815662349296316289007506103530623783778662412242775130434901826006040916198275796030854794765114252042859109937895456937456272840689383252347649632314827628968222525206140835954115052885746071802231172490360858528078464391481414791866455544825137002894313393874811232730829744414164694369153899034939036663319836416273382108749170545196123061715097096408783327892910385169447]
e = 3
mbar = [15544274873612998989866379328566946388285248570806564503108352867340017880252665817613208325183832507901409765669821491355202065667225050801744228447515864518584620720787409961012061302114074543857882368586098987225919736280924738224995075370843988377198544539266275729089636607095220506662375139381261384398438998662059177913249680151096549632879238896603189241688956490787338355571799212913598318011639865738648621731434747681682396930715043552472778331701738091587062917693835229391950847730617837543337471998802061973389340720433170042633451884844390746043635079083497185464124715717119052915013438803576714502781, 15544274873612998989866379328566946388285248570806564503108352867340017880252665817613208325183832507901409765669821491355202065667225050801744228447515864518584620720787409961012061302114074543857882368586098987225919736280924738224995075370843988377198544539266275729089636607095220506662375139381261384398438998662059177913249680151096549632879238896603189241688956490787338355571799212913598318011639865738648621731434747681682396930715043552472778331701733991049485714120357663081338580983163588987883815040112341393183479429685436337175694444720513269496978577270272192766705854550355666404326847416678342795901]

def modinv(a, m):
    return gmpy2.invert(gmpy2.mpz(a), gmpy2.mpz(m))

def CRT(n, a):
    N = reduce(lambda x, y: x * y, n)
    result = 0
    for n_i, a_i in zip(n, a):
        p = N / n_i
        s = modinv(p, n_i)
        result += a_i * s * p
    return result % N

T = []
T.append(CRT(n,[1,0]))
T.append(CRT(n,[0,1]))

N = reduce(lambda x, y: x * y, n)
P.<x> = PolynomialRing(Zmod(N))
g = 0
for i in range(2):
    g += ((x*2**608 + mbar[i])**e - c[i]) * T[i]
g = g.monic()
print g.small_roots(X=2**760, beta=1)

当然，根据 Alexander May and Maike Ritzenhofen 于 2008 年的结论，对于 SMUPE-problem，当 $\sum_{i=1}^k \frac{1}{e_i} > 1$ 时可解。

因此，这道题 1/3 + 1/3 + 1/5 + 1/5 = 16/15 > 1，可解。
设 4 组线性变换为 $f_i$ ，设 $F_i = {f_i}^e - c_i$ ，则可得到以下同余方程组：

$\begin{cases} F_0(x)^2 \equiv (f_0(x)^3 - c_0)^2\equiv 0 \bmod n_0 \\ F_1(x)^2 \equiv (f_1(x)^3 - c_1)^2\equiv 0 \bmod n_1 \\ xF_2(x) \equiv x(f_2(x)^5 - c_2)\equiv 0 \bmod n_2 \\ xF_3(x) \equiv x(f_3(x)^5 - c_3)\equiv 0 \bmod n_3 \\ \end{cases}$

之后的 sage 脚本如下：

PR = PolynomialRing(ZZ, 'x')
x = PR.gen()

Fs = []
for i in range(4):
    f =  PR((x*2**608 + mbar[i])**e[i] - c[i])
    ff = f.change_ring(Zmod(n[i]))
    ff = ff.monic()
    f = ff.change_ring(ZZ)
    Fs.append(f)

F = crt([Fs[0]**2, Fs[1]**2, x*Fs[2], x*Fs[3]], n)

N = reduce(lambda x, y: x * y, n)
F = F.change_ring(Zmod(N))

print F.small_roots(X=2**760, beta=7./8)

Boneh and Durfee attack

当 $d$ 较小时，满足 $d < N^{0.292}$ 时，我们可以利用该攻击，比 Wiener’s Attack 要强一些。

https://github.com/mimoo/RSA-and-LLL-attacks