书接上回，这一篇集合一下 Coppersmith’s Method 在 RSA 公钥密码体制中的一些应用。首先是比较经典的一些问题，摘自 2019 年 第三届强网杯的 copper study （历史非常的悠久了属于是，也是我刚开始玩 CTF 的时候）
第一关：Stereotyped messages
[+]Generating challenge 1
[+]n=0x44e360ce873d18d33eecc0829eb0801e71950e26576963c470f91f4c5e7f3e951f65404c6a87f4328495c9c64d39271f3317081aeab34bdf350c5f9bf0c5a49668f763cbf404e66f210336042c6a6e43eed6c6eaca69287ed91b2841148668fd3881b241317574cc8b307fb41593ff7caaa6f09e32f657399c63fe5f68995c5dL
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x20d40eecc8108d6c57b0ea2e1d7d165fb342813764f3760baf71e7929e3c22476de15b5e665ff8b869b5ed3a672aad4e9ef330bb7e18329ce2d0cccae369e244002882a273d3bf5a13b8936974768a920f5cbee52d0bb0323f867ff6305c5aa7ceb99453172332cd9837fdb05d6ea2d7eac39fd0d39960dc9ddbdd40f82b444bL
[+]((m>>72)<<72)=0x5377a12cada023e2714b4a9e80f1da87ca567f084e2862e704b813cd7f69b8dbbf67d60e73610fabb7896eeb3cc5a2c0915d03f9f8d44d000000000000000000L
[-]long_to_bytes(m).encode('hex')=
已知 ， 共 512bit 但是低 72bit 未知，
于是这道题即求模多项式 的解。
sagemath 也内建了使用 coppersmith's method 求小根的方法 small_roots，于是我们可以快速地写出以下脚本解决问题：
N = 0x44e360ce873d18d33eecc0829eb0801e71950e26576963c470f91f4c5e7f3e951f65404c6a87f4328495c9c64d39271f3317081aeab34bdf350c5f9bf0c5a49668f763cbf404e66f210336042c6a6e43eed6c6eaca69287ed91b2841148668fd3881b241317574cc8b307fb41593ff7caaa6f09e32f657399c63fe5f68995c5d
e = 3
c = 0x20d40eecc8108d6c57b0ea2e1d7d165fb342813764f3760baf71e7929e3c22476de15b5e665ff8b869b5ed3a672aad4e9ef330bb7e18329ce2d0cccae369e244002882a273d3bf5a13b8936974768a920f5cbee52d0bb0323f867ff6305c5aa7ceb99453172332cd9837fdb05d6ea2d7eac39fd0d39960dc9ddbdd40f82b444b
m = 0x5377a12cada023e2714b4a9e80f1da87ca567f084e2862e704b813cd7f69b8dbbf67d60e73610fabb7896eeb3cc5a2c0915d03f9f8d44d000000000000000000
P.<x> = Zmod(N)[]
f = (m + x)^e - c
kbits = 72
x0 = f.small_roots(X=2^kbits)[0]
print("m:", m + x0)
其中 small_roots 的参数在源码中有说明
Let `N` be the characteristic of the base ring this polynomial
is defined over: ``N = self.base_ring().characteristic()``.
This method returns small roots of this polynomial modulo some
factor `b` of `N` with the constraint that `b >= N^beta`.
Small in this context means that if `x` is a root of `f`
modulo `b` then `|x| < X`. This `X` is either provided by the
user or the maximum `X` is chosen such that this algorithm
terminates in polynomial time. If `X` is chosen automatically
it is `X = ceil(1/2 N^{beta^2/delta - epsilon})`.
The algorithm may also return some roots which are larger than `X`.
'This algorithm' in this context means Coppersmith's algorithm for finding
small roots using the LLL algorithm. The implementation of this algorithm
follows Alexander May's PhD thesis referenced below.
该函数会返回模多项式的小根，其中模数为传入 的一个因子 ，满足 ， 默认为 1.0，可由用户指定。返回的根小于 （不过也可能大于）， 是一个可选参数。 也可以由用户设定。（实际测试下来，即使用户指定了 ，通过调整 ，对出结果也有一定的帮助 ）
（PS：这里泄露的是明文的高位，其实还有泄露低位、泄露高低位的情况。但换汤不换药，无非是由 变成了 。但这都是单元的情况，如果是泄露的中间位，那式子就变成了 ，我们就需要使用二元 copper 去解了）
第二关：Factoring with high bits known
[+]Generating challenge 2
[+]n=0x5fe2743ec99568d645943147498849643932486590fb101f41c93ad7247161bc035d75dfb9e4b25209e26913098ecc1b7c4a92a47fb28452465d8b94e31844c4624da870140a48a28a0e6a3c6d9731b8488a63fd8ab9f5fe1ae86513c7444bb0aa39d44416b9cfa83c370f50c7a5a148a36823f0ddeed66ecf99117378c0640fL
[+]e=65537
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x2639582bf7b22fd52a7a519673574e1212b675c9c10763ffcbcf5a86b61f07c4ea536e48dfbd4f3201cb2e18f2a0946959223b3f32bd5b3166d6cdd185ad946e543504dcc42ac9a24c03343bc8e4379997c722b12c66acaed6ad64d35f2fbcc8f4d899c1081d4211987841d1be082801a07014de89050b71e584827020934755L
[+]((p>>128)<<128)=0xe4f16417011e6cc5ced2aad00d5865a0530f37c078dd22d942d0d0811c7053d973b621c4768a2a87a6d233be10db8e1a00000000000000000000000000000000L
[-]long_to_bytes(m).encode('hex')=
已知 且已知 的高 384 位。
同样的，这道题即求模多项式 的解。由于前面我们提到 small_roots 会返回模多项式的小根，其中模数为传入 的一个因子 ，满足 。那么这里我们将 设为 0.49 即可（基于假设 ）。
N = 0x5fe2743ec99568d645943147498849643932486590fb101f41c93ad7247161bc035d75dfb9e4b25209e26913098ecc1b7c4a92a47fb28452465d8b94e31844c4624da870140a48a28a0e6a3c6d9731b8488a63fd8ab9f5fe1ae86513c7444bb0aa39d44416b9cfa83c370f50c7a5a148a36823f0ddeed66ecf99117378c0640f
pbar = 0xe4f16417011e6cc5ced2aad00d5865a0530f37c078dd22d942d0d0811c7053d973b621c4768a2a87a6d233be10db8e1a00000000000000000000000000000000
P.<x> = Zmod(N)[]
f = pbar + x
kbits = 128
x0 = f.small_roots(X=2^kbits, beta=0.49)[0]
p = pbar + x0
print("p: ", p)
（PS：同第一关一样，这里的 是泄露了高位，与 泄露了低位的情况无太大差别）
第三关：Partial Key Exposure Attack
[+]Generating challenge 3
[+]n=0x6f209521a941ddde2294745f53711ae6a7a59aa4d0735f47328ac03e26a4e092bb1c4c885029950f52b1e071597dc6e6d5129afbdb4688ad0479d6f9655dafef915da0a3f5114989cb474a13a9a4a4293fd447739b3cc2b0a3966f21617f057e6c199c5fd4d11ce78fdf9112f53446578b6cfd2c405eb0d3389cd3965636f719L
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x6126eaf34233341016966d50c54c6f7401e98f2015bcbdc4d56f93f0c48590fcd8ee784521c503be322c0848f998dc3a6d630bc1043a4162467c4b069b6c0e186061ed2187d0b2d44e9797ce62569d2dab58d183d69b9d110369a8d690361b22223e34e65e51868646d0ebf697b10e21a97d028833719e87c1584d2564f21167L
[+]d=invmod(e,(p-1)*(q-1))
[+]d&((1<<512)-1)=0x1d8f1499c4f6d90716d89f76833823e8fca4dd4034f17157e4fd9f6f070e1526f3b4fa3fe507d645ec848e4d7ff3728eb8df04b72849feabaa3425f9fc510ec3L
[-]long_to_bytes(m).encode('hex')=
已知 和 d 的低 512bit
根据RSA相关参数我们有 ，
我们设 ，
则有 。
再设 的低位为 ，比特长度为
于是可以将等式 转为同余式
①
这里我们想消元，因为我们有
②
带入后可以把 ① 式的 给消去，
这样式子就只有一个未知数 了，即解同余式方程：
我们就可以得到 的低位 了。
至于 值，根据 ，因为有 ，因此 ，而这里 ，所以可以对 值进行枚举。
def recover_p(p0, n, L):
PR.<x> = Zmod(n)[]
nbits = int(n).bit_length()
p0bits = int(p0).bit_length()
f = 2^p0bits*x + p0
f = f.monic()
roots = f.small_roots(X=2^(nbits//2-p0bits), beta=0.4)
if roots:
x0 = roots[0]
p = gcd(2^L*x0 + p0, n)
return ZZ(p)
def find_p0(d0, e, n, L = 0):
X = var('X')
if not L:
L = int(d0).bit_length()
for k in range(1, e+1):
results = solve_mod([e*d0*X == k*n*X + k*X + X-k*X**2 - k*n], 2^L)
for x in results:
p0 = ZZ(x[0])
p = recover_p(p0, n, L)
if p and p != 1:
return p
n = 0x6f209521a941ddde2294745f53711ae6a7a59aa4d0735f47328ac03e26a4e092bb1c4c885029950f52b1e071597dc6e6d5129afbdb4688ad0479d6f9655dafef915da0a3f5114989cb474a13a9a4a4293fd447739b3cc2b0a3966f21617f057e6c199c5fd4d11ce78fdf9112f53446578b6cfd2c405eb0d3389cd3965636f719
e = 3
d0 = 0x1d8f1499c4f6d90716d89f76833823e8fca4dd4034f17157e4fd9f6f070e1526f3b4fa3fe507d645ec848e4d7ff3728eb8df04b72849feabaa3425f9fc510ec3
p = int(find_p0(d0, e, n))
print("found p: ", p)
q = n//int(p)
print("found d: ", inverse_mod(e, (p-1)*(q-1)))
第四关：Hastad's Broadcast Attack
[+]Generating challenge 4
[+]e=3
[+]m=random.getrandbits(512)
[+]n1=0x1819da5abb8b8158ad6c834cb8fd6bc3ed9a3bd3e33b976344173f1766bf909bda253f18c9d9640570152707e493e3d3d461becc7197367ab702af33d67805e938321915f439e33f616b41781c54c101f05db0760cc8ca0f09063f3142b5b31f6aa062f1e60bba1a45e3720ab462ebd31e1228f5c49ae3de8172bad77b2d5b57L
[+]c1=pow(m,e,n1)=0x7841e1b22f4d571b722807007dc1d550a1970a32801c4649e83f4b99a01f70815b3952a34eadc1ec8ba112be840e81822f1c464b1bb4b24b168e5cb38016469548c5afd8c1bdb55402d1208f3201a2a4098aef305a8380b8c5b6b5b17d9fb65a6bdfdcf21abc063924a6512f18f1dc22332dfc87f4a00925daf1988d43aaecdL
[+]n2=0x6d1164ffa8cb2b7818b5ac90ef121b94e38fd5f93636b212184717779c45581f13c596631b23781de82417f9c8126be4a04ab52a508397f9318c713e65d08961d172f24f877f48ef9e468e52e3b5b17cbbe81646903d650f703c51f2ad0928dd958700b939e1fd7f590f26a6d637bd9ef265d027e7364c4e5e40a172ce970021L
[+]c2=pow(m,e,n2)=0x58f26614932924c81d30ef2389d00cf2115652ced08d59e51619207a7836fd3908b3179fc0df03fe610059c1fe001ca421e01e96afc47147d77bbbe6a3f51c5c06f1baeab8dc245c2567a603f87dea0a053b8f5df4e68f28896d7d1ba3dd3dcd7c4652d59404fa237f4868e1bbc9ae529196739486d86bd1723a78dfac781fe5L
[+]n3=0xde53be1db600264b0c3511ae4939c82164ea1166aadfd8dd0af6e15eb9df79a5d1a2757d3d15630441790ecf834098a1cf4b5858003f0b7f3a72823de014ac0a7c827ed1ca4185b245774f442a05dee3fe6bf846e5b035caf3b3c574b88911b7e5b81fc2c638729240f949e09a25a3a4a762c31005684791577d5e9fc8221abdL
[+]c3=pow(m,e,n3)=0x89f9fabc7e8d6f0e92d31109ea4c024446b323d9f441d72db4eb296eba3011abe2a58e68ec21a663e6493981e21835a826f28d1bc28d3476273ff733ef69c152e7fbfebc826132266f6eb65c86b242417c06eb31453f99ed7e075ababbfc208d042a2436a766f24eb9af0f45b60eea2c4405edfabd87584806bc0a1a51f9ca7aL
[-]long_to_bytes(m).encode('hex')=
已知
对于这一关，由于我们知道 是512bit的，而用于加密的 等于3，因此三个 即为 在不同模下的剩余。由于 ，而三个模数 的 bit 长度分别为 。所以利用中国剩余定理我们是可以还原长度为 的的，最后我们再开个三次根就好得到 了。
但既然这里讲的是 coppersmith‘s method，那么我们再来看看如何用 coppersmith‘s method 来解决这道低指数广播攻击的问题。
用coppersmith‘s method来解决这道问题，我们还可以将问题推广到更一般的情况，就是加密的不再是相同的 m，而是具有线性关系的 ，比如：
，，我们就有三条式子
同样，由于这里的 彼此互素，因此利用 CRT 我们最终也能得到一个式子
m 显然会是这个式子的解，而又由于 ，因此利用 coppersmith‘s method 我们可以求解得m
Cs = []
Ns = []
A = [1, 1, 2]
B = [0, 1, 2]
e = 3
# solve
cnt = e
PR.<x> = PolynomialRing(ZZ)
x = PR.gen()
Fs = []
for i in range(cnt):
f = (A[i]*x + B[i])**e - Cs[i]
ff = f.change_ring(Zmod(Ns[i]))
ff = ff.monic()
f = ff.change_ring(ZZ)
Fs.append(f)
F = crt(Fs, Ns)
N = reduce( lambda x, y: x * y, Ns )
FF = F.change_ring(Zmod(N))
m = FF.small_roots(epsilon=0.05)
print("m: ",m)
第五关：Related Message Attack
[+]Generating challenge 5
[+]n=0xf2e5339236455e2bc1b1bd12e45b9341a3b223ddb02dec11c880fa4aa8835df9e463e4c446292cd5a2fe19b10017856654b6d6c3f3a94a95807712329f7dae2e1e6506094d5d2f9c8a05c35cbf3366330996db9bff930fe566016d5e850e232057d419292ce30df9c135d56ef1bb72c38838d4b127aa577ceb4aba94d4e0d55L
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x7175f2614b8d1a27b43f7c3873b3422658af28291ddc88b15f97f499e00cd4c5c4fd980f062376a61e5dd4c15d52d73262d3c066f1e8f46a04af6fead7c3960d2768a0d214bbc3e05d2f6e56aee158071574e55753624a19e094590fc3f9918a2065cd5ff7693e0d34517bc0072e6c9e444e66c4ece88d657f99e44bee48924L
[+]x=pow(m+1,e,n)=0xd5f4af36b5391bd731cfa4313466024ab1bc3b455024a5d8b218faba0e956252f01c4d01bd36765035c33d73e5af7f178aeb2606edf86814d74082c64828fa4c1666b69d05fab69dd1ef47b243356290fdb74e001f54edec70681cf52319c73bce9acda4803a9e97597ca21d60072c2d2b516f161bec1f6a91baa2e24c7655bL
[-]long_to_bytes(m).encode('hex')=
已知 ， 对应的密文，对应的密文
由于这里用的模数都是 ，我们不能套前面的脚本，这里的其中一种做法是求多项式下的最大公约是式（GCD ），
我们将问题转化一下，设我们有两个函数分别为 ，
显然对于这两个多项式有一个公共解：，因此两条式子都可以化成
【代表未知的多项式】
从而我们对这两个多项式求一个 GCD 就可以得到 ，但由于在模 下，得到的是正数，即 。所以最终 。
def franklinReiter(n,e,b,c1,c2):
R.<X> = Zmod(n)[]
f1 = X^e - c1
f2 = (X + b)^e - c2
m_ = GCD(f1,f2).coefficients()[0]
return Integer(- m_ % n)
def GCD(a, b):
if(b == 0):
return a.monic()
else:
return GCD(b, a % b)
e =
n =
b =
c1 =
c2 =
M = franklinReiter(n,e,b,c1,c2)
print(M)
第六关：Boneh Durfee Attack
[+]Generating challenge 6
[+]n=0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27L
[+]d=random.getrandbits(1024*0.270)
[+]e=invmod(d,phin)
[+]hex(e)=0x11722b54dd6f3ad9ce81da6f6ecb0acaf2cbc3885841d08b32abc0672d1a7293f9856db8f9407dc05f6f373a2d9246752a7cc7b1b6923f1827adfaeefc811e6e5989cce9f00897cfc1fc57987cce4862b5343bc8e91ddf2bd9e23aea9316a69f28f407cfe324d546a7dde13eb0bd052f694aefe8ec0f5298800277dbab4a33bbL
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0xe3505f41ec936cf6bd8ae344bfec85746dc7d87a5943b3a7136482dd7b980f68f52c887585d1c7ca099310c4da2f70d4d5345d3641428797030177da6cc0d41e7b28d0abce694157c611697df8d0add3d900c00f778ac3428f341f47ecc4d868c6c5de0724b0c3403296d84f26736aa66f7905d498fa1862ca59e97f8f866cL
[-]long_to_bytes(m).encode('hex')=
已知 ，私钥 只有 bit 。
继续来推式子：
设 ，
可得式子：
如果我们能在模 下解得该方程的根 ，由 就可以得到 了。
但具体怎么去求解这个方程呢？这就涉及多元coppersmith’s method了。sagemath 也没有相应的内建函数。
这里给出 William Wang 在 github 上开源的一份比较“通用型”的板子，可能也是大部分选手用的板子
# https://github.com/defund/coppersmith/blob/master/coppersmith.sage
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 univariate():
print('Univariate')
bounds = (floor(N^.3),)
roots = tuple(randrange(bound) for bound in bounds)
R = Integers(N)
P.<x> = PolynomialRing(R, 1)
monomials = [x, x^2, x^3]
f = sum(randrange(N)*monomial for monomial in monomials)
f -= f(*roots)
print(small_roots(f, bounds, m=7))
def bivariate():
print('Bivariate')
bounds = (floor(N^.15), floor(N^.15))
roots = tuple(randrange(bound) for bound in bounds)
R = Integers(N)
P.<x, y> = PolynomialRing(R)
monomials = [x, y, x*y, x^2]
f = sum(randrange(N)*monomial for monomial in monomials)
f -= f(*roots)
print(small_roots(f, bounds))
def trivariate():
print('Trivariate')
bounds = (floor(N^.12), floor(N^.12), floor(N^.12))
roots = tuple(randrange(bound) for bound in bounds)
R = Integers(N)
P.<x, y, z> = PolynomialRing(R)
monomials = [x, y, x*y, x*z, y*z]
f = sum(randrange(N)*monomial for monomial in monomials)
f -= f(*roots)
print(small_roots(f, bounds))
def boneh_durfee():
print('Boneh Durfee')
bounds = (floor(N^.255), 2^1024)
d = random_prime(bounds[0])
e = inverse_mod(d, (p-1)*(q-1))
roots = (e*d//((p-1)*(q-1)), (p+q)//2)
R = Integers(e)
P.<k, s> = PolynomialRing(R)
f = 2*k*((N+1)//2 - s) + 1
res = small_roots(f, bounds, m=4, d=4)
if res:
kk,ss = res[0]
#s = p+q/2
var('x,y')
s = solve([(x+y)-2*int(ss),x*y-N],x,y)
return 展开收缩[0].rhs(),s[0][1].rhs()]
return []
def approximate_factor():
print('Approximate factor')
bounds = (floor(N^.05), floor(N^.05))
roots = tuple(randrange(bound) for bound in bounds)
R = Integers(N)
P = PolynomialRing(R, len(bounds), 'x')
f = sum(randrange(2^128)*x for x in P.gens())
f += p - f(*roots)
print(small_roots(f, bounds, m=2, d=4))
def trivariate_v():
print('Trivariate')
bounds = (floor(N^.12), floor(N^.12), floor(N^.12))
roots = tuple(randrange(bound) for bound in bounds)
print(roots)
R = Integers(N)
P.<x, y, z> = PolynomialRing(R)
monomials = [x, y, x*y, x*z, y*z]
f = sum(randrange(N)*monomial for monomial in monomials)
f -= f(*roots)
print(small_roots(f, bounds))
if __name__ == '__main__':
print('Generating primes')
p = random_prime(2^1024)
q = random_prime(2^1024)
N = p*q
univariate()
bivariate()
trivariate()
boneh_durfee()
approximate_factor()
代码可能看着复杂，那这里简单说一下自己的粗鄙认知：相较于单元 copper 而言，多元 copper 无非就是从原来的找最前面的那一条短的系数向量，变成了找前面的多条短的系数向量（几个元就找几条呗），然后再求解一下方程组，就能把解都求出来了。（嗯，大概就是这样吧，如果想搞懂代码所用到的 ideal，variety 这些，那就需要再补充一点抽象代数的知识。）
不过这里 给的界是 ，几乎要到 Boneh Durfee Attack 的理论极限 0.272 了，所以这份通用板子并不太能出结果。要用 Boneh Durfee Attack 特制板子（做了一些优化）
import time
############################################
# Config
##########################################
"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True
"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct
upperbound on the determinant. Note that this
doesn't necesseraly mean that no solutions
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False
"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension
############################################
# Functions
##########################################
# display stats on helpful vectors
def helpful_vectors(BB, modulus):
nothelpful = 0
for ii in range(BB.dimensions()[0]):
if BB[ii,ii] >= modulus:
nothelpful += 1
print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
# display matrix picture with 0 and X
def matrix_overview(BB, bound):
for ii in range(BB.dimensions()[0]):
a = ('%02d ' % ii)
for jj in range(BB.dimensions()[1]):
a += '0' if BB[ii,jj] == 0 else 'X'
if BB.dimensions()[0] < 60:
a += ' '
if BB[ii, ii] >= bound:
a += '~'
print (a)
# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
# end of our recursive function
if current == -1 or BB.dimensions()[0] <= dimension_min:
return BB
# we start by checking from the end
for ii in range(current, -1, -1):
# if it is unhelpful:
if BB[ii, ii] >= bound:
affected_vectors = 0
affected_vector_index = 0
# let's check if it affects other vectors
for jj in range(ii + 1, BB.dimensions()[0]):
# if another vector is affected:
# we increase the count
if BB[jj, ii] != 0:
affected_vectors += 1
affected_vector_index = jj
# level:0
# if no other vectors end up affected
# we remove it
if affected_vectors == 0:
print ("* removing unhelpful vector", ii)
BB = BB.delete_columns([ii])
BB = BB.delete_rows([ii])
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB
# level:1
# if just one was affected we check
# if it is affecting someone else
elif affected_vectors == 1:
affected_deeper = True
for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
# if it is affecting even one vector
# we give up on this one
if BB[kk, affected_vector_index] != 0:
affected_deeper = False
# remove both it if no other vector was affected and
# this helpful vector is not helpful enough
# compared to our unhelpful one
if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
BB = BB.delete_columns([affected_vector_index, ii])
BB = BB.delete_rows([affected_vector_index, ii])
monomials.pop(affected_vector_index)
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB
# nothing happened
return BB
"""
Returns:
* 0,0 if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
"""
Boneh and Durfee revisited by Herrmann and May
finds a solution if:
* d < N^delta
* |x| < e^delta
* |y| < e^0.5
whenever delta < 1 - sqrt(2)/2 ~ 0.292
"""
# substitution (Herrman and May)
PR.<u, x, y> = PolynomialRing(ZZ)
Q = PR.quotient(x*y + 1 - u) # u = xy + 1
polZ = Q(pol).lift()
UU = XX*YY + 1
# x-shifts
gg = []
for kk in range(mm + 1):
for ii in range(mm - kk + 1):
xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
gg.append(xshift)
gg.sort()
# x-shifts list of monomials
monomials = []
for polynomial in gg:
for monomial in polynomial.monomials():
if monomial not in monomials:
monomials.append(monomial)
monomials.sort()
# y-shifts (selected by Herrman and May)
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
yshift = Q(yshift).lift()
gg.append(yshift) # substitution
# y-shifts list of monomials
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
monomials.append(u^kk * y^jj)
# construct lattice B
nn = len(monomials)
BB = Matrix(ZZ, nn)
for ii in range(nn):
BB[ii, 0] = gg[ii](0, 0, 0)
for jj in range(1, ii + 1):
if monomials[jj] in gg[ii].monomials():
BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
# Prototype to reduce the lattice
if helpful_only:
# automatically remove
BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
# reset dimension
nn = BB.dimensions()[0]
if nn == 0:
print("failure")
return 0,0
# check if vectors are helpful
if debug:
helpful_vectors(BB, modulus^mm)
# check if determinant is correctly bounded
det = BB.det()
bound = modulus^(mm*nn)
if det >= bound:
print("We do not have det < bound. Solutions might not be found.")
print("Try with highers m and t.")
if debug:
diff = (log(det) - log(bound)) / log(2)
print("size det(L) - size e^(m*n) = ", floor(diff))
if strict:
return -1, -1
else:
print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
# display the lattice basis
if debug:
matrix_overview(BB, modulus^mm)
# LLL
if debug:
print("optimizing basis of the lattice via LLL, this can take a long time")
BB = BB.LLL()
if debug:
print("LLL is done!")
# transform vector i & j -> polynomials 1 & 2
if debug:
print("looking for independent vectors in the lattice")
found_polynomials = False
for pol1_idx in range(nn - 1):
for pol2_idx in range(pol1_idx + 1, nn):
# for i and j, create the two polynomials
PR.<w,z> = PolynomialRing(ZZ)
pol1 = pol2 = 0
for jj in range(nn):
pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
# resultant
PR.<q> = PolynomialRing(ZZ)
rr = pol1.resultant(pol2)
# are these good polynomials?
if rr.is_zero() or rr.monomials() == [1]:
continue
else:
print("found them, using vectors", pol1_idx, "and", pol2_idx)
found_polynomials = True
break
if found_polynomials:
break
if not found_polynomials:
print("no independant vectors could be found. This should very rarely happen...")
return 0, 0
rr = rr(q, q)
# solutions
soly = rr.roots()
if len(soly) == 0:
print("Your prediction (delta) is too small")
return 0, 0
soly = soly[0][0]
ss = pol1(q, soly)
solx = ss.roots()[0][0]
#
return solx, soly
def example():
############################################
# How To Use This Script
##########################################
#
# The problem to solve (edit the following values)
#
# the modulus
N = 0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27
# the public exponent
e = 0x11722b54dd6f3ad9ce81da6f6ecb0acaf2cbc3885841d08b32abc0672d1a7293f9856db8f9407dc05f6f373a2d9246752a7cc7b1b6923f1827adfaeefc811e6e5989cce9f00897cfc1fc57987cce4862b5343bc8e91ddf2bd9e23aea9316a69f28f407cfe324d546a7dde13eb0bd052f694aefe8ec0f5298800277dbab4a33bb
# the hypothesis on the private exponent (the theoretical maximum is 0.292)
delta = .27 # this means that d < N^delta
#
# Lattice (tweak those values)
#
# you should tweak this (after a first run), (e.g. increment it until a solution is found)
m = 4 # size of the lattice (bigger the better/slower)
# you need to be a lattice master to tweak these
t = int((1-2*delta) * m) # optimization from Herrmann and May
X = 2*floor(N^delta) # this _might_ be too much
Y = floor(N^(1/2)) # correct if p, q are ~ same size
#
# Don't touch anything below
#
# Problem put in equation
P.<x,y> = PolynomialRing(ZZ)
A = int((N+1)/2)
pol = 1 + x * (A + y)
#
# Find the solutions!
#
# Checking bounds
if debug:
print("=== checking values ===")
print("* delta:", delta)
print("* delta < 0.292", delta < 0.292)
print("* size of e:", int(log(e)/log(2)))
print("* size of N:", int(log(N)/log(2)))
print("* m:", m, ", t:", t)
# boneh_durfee
if debug:
print("=== running algorithm ===")
start_time = time.time()
solx, soly = boneh_durfee(pol, e, m, t, X, Y)
# found a solution?
if solx > 0:
print("=== solution found ===")
if False:
print("x:", solx)
print("y:", soly)
d = int(pol(solx, soly) / e)
print("private key found:", d)
else:
print("=== no solution was found ===")
if debug:
print("=== %s seconds ===" % (time.time() - start_time))
if __name__ == "__main__":
example()
另外分享在 HFCTF 2022 嫖到的一个针对二元 copper 比较好用的板子
# https://github.com/1umi3re/my_ctf_challenge/blob/main/hfctf_2022/RRSSAA/exp.py
from gmpy2 import next_prime, iroot
from Crypto.Util.number import getPrime, inverse, GCD, bytes_to_long, long_to_bytes
from sage.all import *
def attack2(N, e, m, t, X, Y):
# 根据实际情况更改式子
PR = PolynomialRing(QQ, 'x,y', 2, order='lex')
x, y = PR.gens()
A = -(N-1)**2
F = x * y**2 + A * x + 1
G_polys = []
# G_{k,i_1,i_2}(x,y) = x^{i_1-k}y_{i_2-2k}f(x,y)^{k}e^{m-k}
for k in range(m + 1):
for i_1 in range(k, m+1):
for i_2 in [2*k, 2*k + 1]:
G_polys.append(x**(i_1-k) * y**(i_2-2*k) * F**k * e**(m-k))
H_polys = []
# y_shift H_{k,i_1,i_2}(x,y) = y^{i_2-2k} f(x,y)^k e^{m-k}
for k in range(m + 1):
for i_2 in range(2*k+2, 2*k+t+1):
H_polys.append(y**(i_2-2*k) * F**k * e**(m-k))
polys = G_polys + H_polys
monomials = []
for poly in polys:
monomials.append(poly.lm())
dims1 = len(polys)
dims2 = len(monomials)
MM = matrix(QQ, dims1, dims2)
for idx, poly in enumerate(polys):
for idx_, monomial in enumerate(monomials):
if monomial in poly.monomials():
MM[idx, idx_] = poly.monomial_coefficient(monomial) * monomial(X, Y)
B = MM.LLL()
found_polynomials = False
for pol1_idx in range(B.nrows()):
for pol2_idx in range(pol1_idx + 1, B.nrows()):
P = PolynomialRing(QQ, 'a,b', 2)
a, b = P.gens()
pol1 = pol2 = 0
for idx_, monomial in enumerate(monomials):
pol1 += monomial(a,b) * B[pol1_idx, idx_] / monomial(X, Y)
pol2 += monomial(a,b) * B[pol2_idx, idx_] / monomial(X, Y)
# resultant
rr = pol1.resultant(pol2)
# are these good polynomials?
if rr.is_zero() or rr.monomials() == [1]:
continue
else:
print(f"found them, using vectors {pol1_idx}, {pol2_idx}")
found_polynomials = True
break
if found_polynomials:
break
if not found_polynomials:
print("no independant vectors could be found. This should very rarely happen...")
PRq = PolynomialRing(QQ, 'z')
z = PRq.gen()
rr = rr(z, z)
soly = rr.roots()[0][0]
ppol = pol1(z, soly)
solx = ppol.roots()[0][0]
return solx, soly
文章戛然而止，但关于 RSA 与 coppersmith 的故事未完待续......
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论