Coppersmith

例子

from Crypto.Util.number import *
from sage.all import *
# p = getPrime(512)
# q = getPrime(512)
# n = p * q
# e = 65537
# leak = p >> 230
# m = bytes_to_long(flag)
# c = pow(m,e,n)
# print(n)
# print(leak)
# print(c)
 
n = 114007680041157617250208809154392208683967639953423906669116998085115503737001019559692895227927818755160444076128820965038044269092587109196557720941716578025622244634385547194563001079609897387390680250570961313174656874665690193604984942452581886657386063927035039087208310041149977622001887997061312418381
leak = 6833525680083767201563383553257365403889275861180069149272377788671845720921410137177
c = 87627846271126693177889082381507430884663777705438987267317070845965070209704910716182088690758208915234427170455157948022843849997441546596567189456637997191173043345521331111329110083529853409188141263211030032553825858341099759209550785745319223409181813931086979471131074015406202979668575990074985441810

PR = PolynomialRing(Zmod(n),'x')#此处创建了一个变量为x的环(用于求解方程的范围)
x = PR.gen()#将环内变量赋值给x

f = (leak<<230) +x
v = f.monic().small_roots(X=2**230, beta=0.4, epsilon=0.02)#epsilon为精度 一般越高越好 不设置可能会出错 X为求解范围一般越接近你需要求的p缺失的位数越好 此处用**用^会出现异或与指数混淆
p = int(f(v[0]))
m = pow(c, inverse_mod(65537, (p-1)),p)
 
print(long_to_bytes(int(m)))