# CopperSmith trong cuộc sống

## Coppersmith Method

Ta có $F(x) = x^d + a_{d-1}.x^{d-1} + ... + a_1.x + a_0$ là một đa thức bậc d. Giả sử tồn tại một hoặc nhiều giá trị nguyên $x_0$ sao cho $F(x_0) \equiv 0 \pmod N$. Làm sao để tìm được cái nghiệm nguyên đó.

Ta có rằng $F(x)$ sẽ có một nghiệm là $x_0$ sao cho $|x_0| < X$ với $X$ là một số được chỉ định. Và từ đó, ta đặt được ma trận cơ sở như sau:

$$
B = \begin{pmatrix} N & & & & & \\ & XN & & & & \\ & & X^2N & & & \\ & & &\ddots & & \\ & & & &X^{d-1}N & \\ a_0 & a_1X &a_2X^2 &\cdots &a_{d-1}B^{d-1} & X^d \end{pmatrix}
$$

Từ đó ta sẽ tìm được các hệ số của phương trình $G(x)$ sao cho $G(x_0) = 0$ trong trường $Z$.

Giờ ta lấy ví dụ cho phương pháp trên. Ta có giá trị $N = 10001$ và phương trình $F(x) = x^3 + 10x^2 + 5000x -222$, giờ ta sẽ tìm giá trị $x_0$ sao cho $F(x_0) \equiv 0 \pmod N$. Ta để giá trị $X = 10$ vì mình biết giá trị $x_0$ khá nhỏ.

Ta sẽ đặt ma trận theo công thức như trên:

$$
B = \begin{pmatrix}
N &0 &0 & 0 \\
0 & XN & 0 & 0 \\
0 &0 & X^2N & 0 \\
-222 & 5000X & 10X^2 & X^{3}
\end{pmatrix}
$$

Ta LLL ma trận này, có được kết quả như sau:

[    444      10   -2000   -2000]
[   9557     -10    2000    2000]
[   -222   50000    1000    1000]
[    989    2500  500100 -500000]

Ta thấy rằng dòng đầu tiên là $(444, 10, -2000, -2000)$ là dạng $(b_0, b_1/X, b_2/(X^2), b_3/(X^3))$. Từ đó ta có được phương trình $G(x) = -2x^3 - 2x^2 +x + 444$. Ta sử dụng **roots()** trong sage để tìm lại được giá trị $x_0$ vì $G(x_0) = 0 $ trong trường $Z$.

Từ đó ta tìm được $x_0 = 4$.

Full source không che cho ae.

N = 10001
X = 10

M = matrix([[N,    0,      0,       0], 
            [0,    X*N,    0,       0], 
            [0,    0,      X**2*N,  0], 
            [-222, 5000*X, 10*X**2, X**3]])

B = M.LLL()

coeffs = B[0]

P.<x> = PolynomialRing(ZZ)
G = coeffs[0] + coeffs[1]//X*x + coeffs[2]//X^2*x^2 + coeffs[3]//X^3*x^3
print(G)
print(G.roots())

Và bài viết này mình sẽ tổng hợp các dạng Coppersmith Attack cơ bản trong RSA.

## Factoring with high bits known

Trường hợp thứ nhất, ta có được dạng như sau:


Ta có được giá trị N, biết được phần lớn significant bits của p, trong đó ta không biết được giá trị r sao cho $p = a + r$. Thế giờ ta có được giá trị $a = 2^l*b$. Thế giờ làm sao để tìm được giá trị r đây.

Bây giờ, ta có phương trình $F(x) = a + x$. Ta biết rằng, sẽ có một giá trị $r$ sao cho $F(r) = p \equiv 0 \pmod p$. Nhưng ta không có biết giá trị $p$, thế nên ta sẽ dùng coppersmith để làm thử thách này.

Ta biết rằng, $|r| < R$ và R sẽ là được chỉ định sẵn. Thay vì sử dụng ma trận trên để tiến hành thì giờ mình sẽ phải dùng ma trận khác vì mình chưa biết giá trị p và chỉ biết được giá trị N.

$$
B = \begin{pmatrix}
R^2 &Ra &0\\
0 & R & a \\
0 & 0 & N
\end{pmatrix}
$$

Sau khi LLL ma trận này, ta sẽ thu được một vector $v = (v_2R^2,v_1R,v_0)$. Từ đó ta sẽ thu được phương trình đó là:
$$G(x) = v_2x^2 + v_1x + v_0$$

Sử dụng **Small_roots()** để tìm nghiệm này trong trường số nguyên N. Từ đo ta sẽ tìm được nghiệm $x_0$ sao cho $F(r) = p \equiv 0 \pmod p$.

Ví dụ nhé:

from Crypto.Util.number import*

p = getPrime(256)
q = getPrime(256)

N = p*q

print("N =",N)

leak = p >> 50

print("leak =", leak)

N = 7395095234742666037684051897523264542646919131857814296416772482285538919823616800259900856635876774424361161011181340391193753666681187509889486528692191
leak = 57823132738426864464363216782718704455474298259322476798985828

Ta có được giá trị leak, nó chính là 206 bit đầu tiên của giá trị p. Giờ ta cần tìm lại 50 bit đó để có thể tìm lại giá trị p.

Ta có phương trình $F(x) = a + x$ hay $F(x) = 2^{50}*leak + x$. Giờ ta sẽ phải tìm lại giá trị $x$.

Vì $x$ chỉ có 50 bits, thế nên, $x < 2^{50}$, ta đặt $R = 2^{50}$. Đặt ma trận và giải thôi.

N = 7395095234742666037684051897523264542646919131857814296416772482285538919823616800259900856635876774424361161011181340391193753666681187509889486528692191
leak = 57823132738426864464363216782718704455474298259322476798985828
a = leak*(2**50)
R = 2^50

M = matrix([[R^2,  R*a,   0], 
            [0,    R,     a], 
            [0,    0,     N]])

B = M.LLL()


P.<x> = PolynomialRing(Zmod(N))
f = B[0][0]*x^2/R^2+B[0][1]*x/R+B[0][2]
f = f.monic()
r = f.small_roots()[0]
print(r)
assert N%(a+r) == 0
print("True")

Lưu ý rằng, với ma trận 3x3 này, thì chỉ hoạt động với $|r| < p^{\frac{1}{3}}$.

Trường hợp thứ 2, ta biết được trên 50% bit cuối.


from Crypto.Util.number import*

p = 80719458166485090412061521387237097412191135397591863765494490139068398356367
q = getPrime(256)

N = p*q

print("N =",N)

leak = (p >> 206) << 206 
leak = p - leak
print(("l = "),(leak))

Bài này, ta thấy rằng giá trị $p = x*2^{206} + leak$ và giá trị $x$ này chỉ có 50 bits, từ đó ta có được $x < 2^{50}$.

Giờ thay vì mình đặt ma trận (thực ra mình cũng không biết phải xử lý như nào) thì mình dùng ``small_roots()`` của sage.

Ta có phương trình như sau:

$f(x) = x*2^{206} + l$

N = 8184607042327669434556581522717729464699186752878347305196407508267297190651285316935331643487012853672006422832361180973332129168126358696280553063918687
l = 41624872242800636810329099425014504799728408816913306783893391

P.<x> = PolynomialRing(Zmod(N))

f = x*2^206 + l
f = f.monic()
result = f.small_roots(X=2^50, beta = 0.2, epsilon=1/200)
res = (result)[0]

assert N%(res*2^206 + l ) == 0
print("TRUE")

Ngoài ra thì còn rất nhiều trường hợp khác nha.

## Coppersmith's small public RSA exponent attack with partially known message

Ta có ví dụ như sau:

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

flag = b'Helloworld'
flag = bytes_to_long(flag)

n = getPrime(512) * getPrime(512)

c = pow(flag, 3, n)

res = iroot(c,3)[0]
res = long_to_bytes(res)
print(res)

Ta thấy rằng, ta chỉ cần căn bậc e của ciphertext là có thể thu được plaintext, đó là do $flag^3 < n$ thế nên ta mới làm được thế. Thế giờ như này thì sao ???

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

flag = b'ThepasswordisHelloworld'
flag = bytes_to_long(flag)

n = getPrime(128) * getPrime(128)

c = pow(flag, 3, n)

res = iroot(c,3)[0]
res = long_to_bytes(res)
print(res)

Ta thấy rằng nó không thể nào thu được flag nữa vì giờ $flag^3 > n$, thế nên không thể dùng cách này được.

Thế nhưng, ta có được 1 đoạn cảu flag là ``Thepasswordis`` và độ dài password là 10 thì sao nhỉ. Nó sẽ là một lỗ hỏng chết người.

Ta sẽ lấy một ví dụ từ code trên nha.

n = 59312888513457939420172910311807468626196867627183950757924932183129165330733
c = 39081361749964208648430462616065115944008922837296404959579953271519086617821

Ta có được rằng $m^e \pmod N = c$. Suy ra $m^e - c = 0 \mod N$.

Ta đặt được phương trình

$$f(x) = (M + x)^e - c = 0$$

Với M là các plaintext đã biết và x là phần chưa biết và ta cần phải đặt trong trường số nguyên tố N.

Code tấn công đây nha.

from Crypto.Util.number import*

n = 59312888513457939420172910311807468626196867627183950757924932183129165330733
c = 39081361749964208648430462616065115944008922837296404959579953271519086617821


M = b'Thepasswordis' + b'\x00'*10
M = bytes_to_long(M)

P.<x> = PolynomialRing(Zmod(n))
f = (M + x)^3 - c
f = f.monic()
res = f.small_roots(epsilon=1/50)

print(res)

Đôi lúc bạn cần phải chỉnh sửa các thông số trong hàm small_roots() để tăng kết quả tìm kiếm, mình ban đầu có để 1/20 mà không ra nên run vcl =)))

Mình cùng thử thách khó hơn nhóe

### KMACTF 2023 lần 2

from Crypto.Util.number import *

p = getPrime(2048)
q = getPrime(2048)
n = p*q
e = 2

print(f'{n = }')

flag = "KMA{anh che roi!!!!!!!}"
l = len(flag)
print(f'{l = }')

msg = f'''
Gửi đến những người em thân yêu của anh, hôm nay anh muốn chia sẻ với các em một câu chuyện về kho báu. 
Trong câu chuyện này, kho báu được chia thành hai nửa, và mỗi nửa mang trong mình một ý nghĩa đặc biệt.
Nửa đầu tiên anh giấu ở đây: {flag[:l//2]}
Còn đây là nửa thứ hai: {flag[l//2:]}
Hãy tìm ra kho báu của anh đi, anh để hết trong msg rồi đó.
Chúc các em may mắn !!!
'''

c = pow(bytes_to_long(msg.encode()), e,n)
print(f'{c = }')


n = 284195696721751741542976970377246384163200746062783759329661617188815436776424189078521874168074640320924439097731870753354899953210403298438375686437215681238598996375382536537768278254146374135440697791835320902172928838535170207920563260188268857178412014945665843067884706362429213081345697201062048319151146709862154724701120787598264599428501030945241764332469820283330386978451487308358496070493019375227430237712951734594609189071738774562063639368050519599690219339371888693892756654714125742546793650545564645761412676393745546867317157950660276413454704121923686068169935524575099441009254762051678974615084672006274688302115077734407074204036930371634952480748870905140950407665202776686680232626404222734370828402377048157739018826752500816695651244608931659579045297636939347065142654266415418100162785201594053030962306454285243690682313810711305540434910861763618201288903763117959626276874769295456013747611282355250494278056557319959998777444026981083893016148032869660521587008308779834135343779295437340050873017686606894792594175473683376016830206421076702465312246840917660142641545140295983913838540847955749716541937276104901379735588334581049297927341758018775135576856481243743641314705618868934645861372761
l = 46
c = 197348052174145638785229215457497516691585910055835441125583073645980013777032065006627024581136020897300252228534006100306209234223154204281916399887451961006595700453576912583653484661863741375270305419615721406198781214515934675523007505165820308082654403780811498250984535336719680589351485735567955825720119048693747519278867766555710216038040229689357846375187513096350835998852728799656866437148777620905204000517049701112204778019184506339386241329691058153055354968087261832501249138236077313408204182929051641521267083356295624561257562991234261668632037087231724232716833294744291699334965334803826200727633700589654688863746449952492047286765973034494755978048670534899135052018421945310658805856492088479095070115314198579191182336314746398558742288499341372595578846975164079893641205584309595266932028754927985671375042116891444819656916960144209962788439147210122667753145683940192069926363191913583924164601419393905729897192079336412469978182139715148777895764888053578167383521367586833983484951931519842177634434322107919818397921097644416813823140565831649561406124639176188646350960425853516784830094432718779747088309513889971075211757981041043652016970888838329334179083984287540371718185534696012444989603691

Bài này ý của tác giả chắc không phải dùng small_roots() nhưng mà small_root() vẫn có thể giải được trong bài này.

from Crypto.Util.number import long_to_bytes, bytes_to_long

n = 284195696721751741542976970377246384163200746062783759329661617188815436776424189078521874168074640320924439097731870753354899953210403298438375686437215681238598996375382536537768278254146374135440697791835320902172928838535170207920563260188268857178412014945665843067884706362429213081345697201062048319151146709862154724701120787598264599428501030945241764332469820283330386978451487308358496070493019375227430237712951734594609189071738774562063639368050519599690219339371888693892756654714125742546793650545564645761412676393745546867317157950660276413454704121923686068169935524575099441009254762051678974615084672006274688302115077734407074204036930371634952480748870905140950407665202776686680232626404222734370828402377048157739018826752500816695651244608931659579045297636939347065142654266415418100162785201594053030962306454285243690682313810711305540434910861763618201288903763117959626276874769295456013747611282355250494278056557319959998777444026981083893016148032869660521587008308779834135343779295437340050873017686606894792594175473683376016830206421076702465312246840917660142641545140295983913838540847955749716541937276104901379735588334581049297927341758018775135576856481243743641314705618868934645861372761
l = 46
c = 197348052174145638785229215457497516691585910055835441125583073645980013777032065006627024581136020897300252228534006100306209234223154204281916399887451961006595700453576912583653484661863741375270305419615721406198781214515934675523007505165820308082654403780811498250984535336719680589351485735567955825720119048693747519278867766555710216038040229689357846375187513096350835998852728799656866437148777620905204000517049701112204778019184506339386241329691058153055354968087261832501249138236077313408204182929051641521267083356295624561257562991234261668632037087231724232716833294744291699334965334803826200727633700589654688863746449952492047286765973034494755978048670534899135052018421945310658805856492088479095070115314198579191182336314746398558742288499341372595578846975164079893641205584309595266932028754927985671375042116891444819656916960144209962788439147210122667753145683940192069926363191913583924164601419393905729897192079336412469978182139715148777895764888053578167383521367586833983484951931519842177634434322107919818397921097644416813823140565831649561406124639176188646350960425853516784830094432718779747088309513889971075211757981041043652016970888838329334179083984287540371718185534696012444989603691
e = 2

G = PolynomialRing(Zmod(n), names='x')
x = G.gen()

msg = '''
Gửi đến những người em thân yêu của anh, hôm nay anh muốn chia sẻ với các em một câu chuyện về kho báu. 
Trong câu chuyện này, kho báu được chia thành hai nửa, và mỗi nửa mang trong mình một ý nghĩa đặc biệt.
Nửa đầu tiên anh giấu ở đây: aaaaaaaaaaaaaaaaaaaaaaa
Còn đây là nửa thứ hai: aaaaaaaaaaaaaaaaaaaaaaa
Hãy tìm ra kho báu của anh đi, anh để hết trong msg rồi đó.
Chúc các em may mắn !!!
'''

m1 = bytes_to_long((msg.replace('aaaaaaaaaaaaaaaaaaaaaaa','\x00'*23)).encode())
poly= (m1+x)**2 - c
root=poly.small_roots()
if root:
    print(long_to_bytes(m1+int(root[0])))

Còn rất nhiều dạng coppersmith khác rất hay, nhưng mà có lẽ mình sẽ bổ sung vào writeups của mình trên blog á, mọi người đón chờ nhé. Moazzzz