Coppersmith's Attack Note

William Lin

2024-02-25

Boneh and Durfee attack, Coppersmith's Attack, Coppersmith's short pad Attack, Cryptography, Franklin–Reiter Attack, Known High Bits Message Attack, Known High Bits Of p

Before all

自己在嗑RSA的時候會發現看到後來好多 Coppersmith’s 相關的東西……
所以今天就來整理一些
主要用來放攻擊方法和腳本，其他的數學我覺得底下 #meow 的連結一定會寫得更好。
之後應該會加更多東西(如果有看到?)

meow?

基本原理

~~其實跟 CTF WIKI 幾乎一樣~~
有個多項式$f$以及模數$N$
此時，必須要有模數$N$有個因數$b$滿足$b \geq N^\beta$，$0< \beta \leq1$，而$f$的最高次為$\delta$
則Coppersmith’s Method可以在複雜度為$O(c\delta^5 log^9(N))$內找到多項式所有的根$x_0$
其中，$|x_0|\leq c N^{\frac{\beta^2}{\delta}}$
而這裡面主要是使用LLL算法(詳細請看lattices章節)找到多項式g滿足：

跟 f 在模$N$底下具有相同的根
最高次小於 $\delta$
定義域為$Z$

Sage math 實作

review

在sage math裡面可以定義一個多項式環像是這樣：

1	P.<x>=PolynomialRing(Zmod(n))

則接下來所有帶x的多項式都會在Zmod(n)底下做事，也就是模$n$底下。
然而，有時候會發現無法使用，這時候就可以嘗試利用preparse函數：

1	preparse('P.<x>=PolynomialRing(Zmod(n))')

Result:

1	P = PolynomialRing(Zmod(n), names=('x',)); (x,) = P._first_ngens(1)

small_roots

在定義好PolymonialRing後，sage裡面可以定義多項式像是：

f=p0+x

然後使用：

1	f.small_roots()

可以直接得到該多項式在mod n底下的所有解(就是mod n為0的case)
但small_roots如果加了其他參數，像是：

1	f.small_roots(X=2**128, beta=0.4)

那sage就會去把所有模$b$底下，小於$2^{128}$的解算出來。
其中，所有$b$滿足$b\geq N^\beta$。

monic

f.monic()會把f最高項係數變成1，整個多項式解不變。

Known High Bits Of p

與一般的RSA題目一樣，但是多洩漏了其中一個質數大部分的bits。
source.py

from Crypto.Util.number import *
import secret
p=getPrime(1004)
q=getPrime(1004)
n=p*q
e=65537
m=bytes_to_long(secret.flag)
c=pow(m, e, n)
p0=(p>>120)<<120
print(f'{e=}\n{p0=}\n{n=}\n{c=}')

output:

e=65537
p0=100465147640470485747293851090553574310053846134542653110704375676461794188050191127456143420090556236801889086711291980553762803490312581046371622870118885986763001912930292410236052966369197265314469363900415533118122038452105876822779245783522825304703574113976849737577129994640979865687397702303744
n=9358294656208497385745434081628457905779263307683434943156483514225129151118781992081317431005767541191066082926013882312659363690266983156107387214041005908019920858498754227661688449973057792052555960805263584061590368578897283881536232480071584234752271762419511847036422301239877606394638940073902997079428457423278415147306781623381163825231265165174852942029342005272627678806408259172877110585065440907744079380341938662530592616068654539113193581491867956360391381284386206799666451643805534487406525739167743974211495493692774788851513689797110146360608259027416196901679191902424554095345163007
c=6170141117310175595348810174464424974102515146766823582968196972770630845077260468896168991247383199702954907173412521293108538007202468268521821472498223995423396084372233553988037880795510363416470730618971989758460635306563027013683072184493221401011751850093605052602074410616558416040654196817317524403836542977145554429556261174576928382083234138500759504174823279318744947301881921849301569065217486802173407809085814053069088495214821174942469051430725477655350720103052904487538623797670952706325913765157345516378821524593872129832388609068307445134272454291753269768219407292025886810682462973

在上面的範例裡，可以假設$f(x)=p0+x$，則當解出$f(x)$在$mod$ $p$下的根時，那個$x$就是p的後120 bits。
於是利用剛剛前面講過的small_roots就可以解決問題~
$\beta$的值通常會在0.4左右，看情況而定，能從一開始Coppersmith’s method利用條件算(
solve.sage:

e=65537
p0=100465147640470485747293851090553574310053846134542653110704375676461794188050191127456143420090556236801889086711291980553762803490312581046371622870118885986763001912930292410236052966369197265314469363900415533118122038452105876822779245783522825304703574113976849737577129994640979865687397702303744
n=9358294656208497385745434081628457905779263307683434943156483514225129151118781992081317431005767541191066082926013882312659363690266983156107387214041005908019920858498754227661688449973057792052555960805263584061590368578897283881536232480071584234752271762419511847036422301239877606394638940073902997079428457423278415147306781623381163825231265165174852942029342005272627678806408259172877110585065440907744079380341938662530592616068654539113193581491867956360391381284386206799666451643805534487406525739167743974211495493692774788851513689797110146360608259027416196901679191902424554095345163007
c=6170141117310175595348810174464424974102515146766823582968196972770630845077260468896168991247383199702954907173412521293108538007202468268521821472498223995423396084372233553988037880795510363416470730618971989758460635306563027013683072184493221401011751850093605052602074410616558416040654196817317524403836542977145554429556261174576928382083234138500759504174823279318744947301881921849301569065217486802173407809085814053069088495214821174942469051430725477655350720103052904487538623797670952706325913765157345516378821524593872129832388609068307445134272454291753269768219407292025886810682462973
P.<x>=PolynomialRing(Zmod(n))
f=p0+x
p_small=f.small_roots(2**121, 0.4)[0]
p=p0+p_small
q=int(n)//int(p)
phi=(p-1)*(q-1)
d=inverse(int(e), int(phi))
print(long_to_bytes(pow(int(c), int(d), int(n))))

註：會掛一堆int()是因為sage會把這些int當作PolynomialRing底下的物件。

Known High Bits Message Attack

在已經知道大部分訊息時的攻擊：
假設今天原始訊息為$M$，你已經知道前k個bits的$M_0$，那在拿到加密後的訊息：$M^e(mod)$ $N$時可以破解。
把多項式變成$(M_0+x)^e-C$即可owob

Franklin–Reiter Attack

一樣在RSA加密底下
令一個訊息$M_0$被$f(x)=ax+b$處理後為$M_1$，它們加密後分別是$C_0$以及$C_1$
則因為$x^e-C_0$和$f(x)^e-C_1$的解在模$N$底下都有$M_0$，所以只要算出它們的gcd，當中一定有$x-M_0$。
(所以在CTF競賽中，這類型題目的$e$一般不會太大，不然很難剛好線性。
攻擊複雜度為：$O(elog^2N)$

def attack(c1, c2, a, b, e, n):
    PR.<x>=PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (a*x+b)^e - c2
    g2 = g2.monic()
    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]

Coppersmith’s short pad Attack

當訊息的padding太小會出事，因為對應的多項式根很小(就是訊息)
詳細可以去看：https://en.wikipedia.org/wiki/Coppersmith%27s_attack#Coppersmith%E2%80%99s_short-pad_attack
實作：https://github.com/yud121212/Coppersmith-s-Short-Pad-Attack-Franklin-Reiter-Related-Message-Attack/blob/master/coppersmiths_short_pad_attack.sage

Boneh and Durfee attack

進階版的Wiener’s Attack
界是$d>N^{2.092}$
可以看：
https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage