5bei.cn大模型教程网备注：暂未搞懂题型1和题型2脚本为什么完全不一样
题型1
已知：dp >> 200或者(dp >> 200)
例题1：[祥云杯2020]Exposure
题目源码
from Crypto.Util.number import *
import gmpy2
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
e = 7621
d = gmpy2.invert(e, phi)
flag = b"flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}"
c = pow(bytes_to_long(flag), e, n)
dp = d % (p - 1)
print(dp >> 200)
print(c, e, n)
'''
dp>>200 = 1153696846823715458342658568392537778171840014923745253759529432977932183322553944430236879985
c = 46735962204857190520476434898881001530665718155698898882603422023484998388668858692912250418134186095459060506275961050676051693220280588047233628259880712415593039977585805890920089318643002597837000049626154900908543384761210358835843974072960080857150727010985827690190496793207012355214605393036388807616
e = 7621
n = 140376049134934822153964243403031201922239588054133319056483413311963385321279682186354948441840374124640187894619689719746347334298621083485494086361152915457458004998419817456902929318697902819798254427945343361548635794308362823239150919240307072688623000747781103375481834571274423004856276841225675241863
'''
解答：
本题为已知dp部分高位的情况，使用通过化简构造f(x)的Coppersmith解决
secret = 1153696846823715458342658568392537778171840014923745253759529432977932183322553944430236879985
c = 46735962204857190520476434898881001530665718155698898882603422023484998388668858692912250418134186095459060506275961050676051693220280588047233628259880712415593039977585805890920089318643002597837000049626154900908543384761210358835843974072960080857150727010985827690190496793207012355214605393036388807616
e = 7621
n = 140376049134934822153964243403031201922239588054133319056483413311963385321279682186354948441840374124640187894619689719746347334298621083485494086361152915457458004998419817456902929318697902819798254427945343361548635794308362823239150919240307072688623000747781103375481834571274423004856276841225675241863
[n, secret, c] = list(map(Integer, [n, secret, c]))
def facorize(e, dp):
for i in range(2, e):
p = (e * dp - 1 + i) // i
if n % p == 0:
return p
return -1
def recover(secret):
F.x> = PolynomialRing(Zmod(n))
d = inverse_mod(e, n)
for k in range(1, e):
print('k =',k)
f = (secret 200) + x + (k - 1) * d
x0 = f.small_roots(X=2 **(200 + 1), beta=0.44, epsilon=1/32)
if len(x0) != 0:
dp = x0[0] + (secret 200)
p = facorize(e, Integer(dp))
if p 0:
continue
else:
return p, dp
if __name__ == "__main__":
p, dp = recover(secret)
q = n // p
assert p * q == n
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
print('p =',p)
print('q =',q)
m = pow(c, d, n)
flag = bytes.fromhex(hex(m)[2:])
print(flag)
例题2：[某数据安全比赛]数据加密
题目描述：某公司针对内部数据进行水印标注，采用变异RSA算法进行加密防护，某一个关键的系数发生了微小的扰动。请分析参考代码，进行分析，提取出关键数据。
题目源码
from secret import flag
from gmpy2 import *
from Crypto.Util.number import *
p = getPrime(1024)
q = getPrime(1024)
N = p * q
e = 65537
d = invert(e, (p - 1) * (q - 1))
dp = d % (p - 1)
kp = (e * dp - 1)//(p - 1)
assert kp > 30000
a = (dp >> 200) 200
c = powmod(bytes_to_long(flag), e, N)
print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'a = {hex(a)}')
print(f'c = {hex(c)}')
# N = 0x9592248accf1848acbf096bc49ecdd058af529c3917084ac2362bdf6e64865e47fe22581a2c9f1f965e724235c36126dc7a6c4519a21d5aef253ac6095a6c45c02d0995b1acfa0005de5a403cc0142fc860993184434d5a76b25ff38df6d04c7f8f50fae4300d07ae19012801606306dcde98a0553b4527ccaf35cf14f244d60390156729754b6eeb28dfc18e22c49b89246fd7b0cd2cc312661b3e231d9aa58d679c038a8caad15ed75225b1a79cd18a0c76e5701bdf50d3f1a1875684a120fc93abd7dcd6cc7ab4e643cb50f5fa3eb44b3ff4c1a898547150861492c997d838abe414961133bf70c8383f7f77d05da16b7efc6962fb88e84d51dee12cd256b
# e = 0x10001
# a = 0x6fd6d76896bcd7458872b75275e506aa0d1018e87486852cf897268091910e076e38e4297d99b7a0b4d3ff0731ff6d4a977e65642d428c70bb40a8d2e8f579ff73726ab1ee79d8c1853baaba3cc6e87ccfbf17d88acc350bde25f7783a1611a8dac970b999f64700000000000000000000000000000000000000000000000000
# c = 0x8fd7548e2b52205df96b2a9b9a0acd7e1e98b3ad2fee6577c48c7cd2d709309f9f078bf3ad0621d9d09d3383c9e2b027de01a60d9537a94e2c1476d8d47c816f576779acafa686c0f08508e671990b1244ca675528253236fc09ce8436c5b422d154225eae1fa94cd86a65735acd95efd8d4ac4377b9e16c90610dab195f6283616c1c795631cdd9b9f8510b1b53f2843a285d5a7f45fd5ea47eef17701805e1db4c666d853af3b7d75975e7c2059f26a6fc61892897bc16d4ceca0a9f18eadee6546ecfa5b129c53447004fb2b90f9d55665e407fa45799f0727596f8248897ff3ce2bc2be5b099c33339c7e00f45398f78af002a5dc15cb7ee86c6d82bb673
解答
sage脚本：
a = 0x6fd6d76896bcd7458872b75275e506aa0d1018e87486852cf897268091910e076e38e4297d99b7a0b4d3ff0731ff6d4a977e65642d428c70bb40a8d2e8f579ff73726ab1ee79d8c1853baaba3cc6e87ccfbf17d88acc350bde25f7783a1611a8dac970b999f64700000000000000000000000000000000000000000000000000
secret = a >> 200
c = 0x8fd7548e2b52205df96b2a9b9a0acd7e1e98b3ad2fee6577c48c7cd2d709309f9f078bf3ad0621d9d09d3383c9e2b027de01a60d9537a94e2c1476d8d47c816f576779acafa686c0f08508e671990b1244ca675528253236fc09ce8436c5b422d154225eae1fa94cd86a65735acd95efd8d4ac4377b9e16c90610dab195f6283616c1c795631cdd9b9f8510b1b53f2843a285d5a7f45fd5ea47eef17701805e1db4c666d853af3b7d75975e7c2059f26a6fc61892897bc16d4ceca0a9f18eadee6546ecfa5b129c53447004fb2b90f9d55665e407fa45799f0727596f8248897ff3ce2bc2be5b099c33339c7e00f45398f78af002a5dc15cb7ee86c6d82bb673
e = 0x10001
n = 0x9592248accf1848acbf096bc49ecdd058af529c3917084ac2362bdf6e64865e47fe22581a2c9f1f965e724235c36126dc7a6c4519a21d5aef253ac6095a6c45c02d0995b1acfa0005de5a403cc0142fc860993184434d5a76b25ff38df6d04c7f8f50fae4300d07ae19012801606306dcde98a0553b4527ccaf35cf14f244d60390156729754b6eeb28dfc18e22c49b89246fd7b0cd2cc312661b3e231d9aa58d679c038a8caad15ed75225b1a79cd18a0c76e5701bdf50d3f1a1875684a120fc93abd7dcd6cc7ab4e643cb50f5fa3eb44b3ff4c1a898547150861492c997d838abe414961133bf70c8383f7f77d05da16b7efc6962fb88e84d51dee12cd256b
[n, secret, c] = list(map(Integer, [n, secret, c]))
def facorize(e, dp):
for i in range(2, e):
p = (e * dp - 1 + i) // i
if n % p == 0:
return p
return -1
def recover(secret):
F.x> = PolynomialRing(Zmod(n))
d = inverse_mod(e, n)
for k in range(38000, e): #重点修改的地方
print('k =',k)
f = (secret 200) + x + (k - 1) * d
x0 = f.small_roots(X=2 **(200 + 1), beta=0.44, epsilon=1/32)
if len(x0) != 0:
dp = x0[0] + (secret 200)
p = facorize(e, Integer(dp))
if p 0:
continue
else:
return p, dp
if __name__ == "__main__":
p, dp = recover(secret)
q = n // p
assert p * q == n
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
print('p =',p)
print('q =',q)
m = pow(c, d, n)
flag = bytes.fromhex(hex(m)[2:])
print(flag)
k = 38210
p = 134703618066290713388766691409981058740041048850563132471023856268106902380822774407120380802420995794360644141182174736604046437277776262160672283465809321911022337913283584019771139895074760683184094034830996534522902543451600792242994317001217319277001855043974386241603495737878292334675754033978747271121
q = 140171239521666801351939630933038120468046586881799380242893773086958102208654601740341710482879485423571294243879466087743391866366859929119172065271180251007218483654208339578000189155413602460258948900916186897629010583990988479243216552792003222833078976860064551506134672737479101044881042343765252510843
b'download:2025-01-01|download-id:dppp_coppersmith'
题型2
已知：dp >> 180
例题：[LitCTF 2025]leak
题目源码
from Crypto.Util.number import *
from enc import flag
m = bytes_to_long(flag)
p,q,e = getPrime(1024),getPrime(1024),getPrime(101)
n = p*q
temp = gmpy2.invert(e,p-1)
c = pow(m,e,n)
hint = temp>>180
print(f"e = {e}")
print(f"n = {n}")
print(f"c = {c}")
print(f"hint = {hint}")
'''
e = 1915595112993511209389477484497
n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951
c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399
hint = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930
'''
解答：
exp引用不知道战队wp，链接如下：
https://idontknowctf.xyz/2025/05/26/LitCTF2025-WriteUp/
# sage10.6
from Crypto.Util.number import *
import gmpy2
import itertools
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
print(d)
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 []
e = 1915595112993511209389477484497
n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951
c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399
leak = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930
leak = 180
R.x,y> = PolynomialRing(Zmod(n),implementation='generic')
f = e * (leak + x) + (y - 1)
res = small_roots(f,(2^180,2^101),m=2,d=4)
print(res)
for root in res:
dp_low = root[0]
dp = leak + dp_low
tmp = pow(2,e*dp,n) - 2
p = gmpy2.gcd(tmp,n)
q = n // p
d = inverse(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
# LitCTF{03ecda15d1a89b06454c6050c1bd489f}
文章来源于互联网:66RSA-已知dp高位数据
相关推荐: 超强磁力下载Plus 高级版 搭配搜索软件 资源秒搜秒播
获取地址：超强磁力 超强磁力下载Plus以其简洁的界面、强大的内核和极致的用户体验，迅速在用户群体中掀起热潮。它支持磁力链接、BT种子、HTTP/HTTPS等多种协议下载，具备多线程加速、断点续传、后台运行等专业功能，确保用户在各种网络环境下都能稳定高效地获取…
