Sagemath 应用

一元多项式求根

这里用到 sage 快速计算多项式的根值，下面举例两种写法

第一种：

sage: x = PolynomialRing(RationalField(), 'x').gen()

sage: f = x^3 - 1

sage: f.roots()

[(1, 1)]

参数含义：

PolynomialRing 是用于构造多项式环，其中的 x 是定义多项式的变量

roots() 用于计算多项式的根，[(1, 1)] 中第一个值是根，第二个值是它的多重性。

第二种：

求单变量方程的解：

sage: x = var('x')

sage: solve(x^2 + 3*x + 2,x)

[x == -2, x == -1]

求解多变量方程的解：

sage: x,y = var('x,y')

sage: solve([x+y == 6 , x - y == 4],x,y)

[[ x == 5 , y == 1 ]]

例题：[2022MapleCTF] brsaby

from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG

msg = bytes_to_long(FLAG)
p = getPrime(512)
q = getPrime(512)
N = p*q
e = 0x10001
enc = pow(msg, e, N)
hint = p**4 - q**3

print(f"{N = }")
print(f"{e = }")
print(f"{enc = }")
print(f"{hint = }")

'''
N = 134049493752540418773065530143076126635445393203564220282068096099004424462500237164471467694656029850418188898633676218589793310992660499303428013844428562884017060683631593831476483842609871002334562252352992475614866865974358629573630911411844296034168928705543095499675521713617474013653359243644060206273
e = 65537
enc = 110102068225857249266317472106969433365215711224747391469423595211113736904624336819727052620230568210114877696850912188601083627767033947343144894754967713943008865252845680364312307500261885582194931443807130970738278351511194280306132200450370953028936210150584164591049215506801271155664701637982648648103
hint = 20172108941900018394284473561352944005622395962339433571299361593905788672168045532232800087202397752219344139121724243795336720758440190310585711170413893436453612554118877290447992615675653923905848685604450760355869000618609981902108252359560311702189784994512308860998406787788757988995958832480986292341328962694760728098818022660328680140765730787944534645101122046301434298592063643437213380371824613660631584008711686240103416385845390125711005079231226631612790119628517438076962856020578250598417110996970171029663545716229258911304933901864735285384197017662727621049720992964441567484821110407612560423282
'''

方程 hint = p**4 - q**3 左右同时乘以 p**3 ,得到：

hint*p3 = p7 - N**3

除了 p 其他变量都是已知的，所以构成了多项式求根值的问题，直接用sage计算

#sage
from gmpy2 import *
from libnum import *
from Crypto.Util.number import *

N = 134049493752540418773065530143076126635445393203564220282068096099004424462500237164471467694656029850418188898633676218589793310992660499303428013844428562884017060683631593831476483842609871002334562252352992475614866865974358629573630911411844296034168928705543095499675521713617474013653359243644060206273
e = 0x10001
c = 110102068225857249266317472106969433365215711224747391469423595211113736904624336819727052620230568210114877696850912188601083627767033947343144894754967713943008865252845680364312307500261885582194931443807130970738278351511194280306132200450370953028936210150584164591049215506801271155664701637982648648103
hint = 20172108941900018394284473561352944005622395962339433571299361593905788672168045532232800087202397752219344139121724243795336720758440190310585711170413893436453612554118877290447992615675653923905848685604450760355869000618609981902108252359560311702189784994512308860998406787788757988995958832480986292341328962694760728098818022660328680140765730787944534645101122046301434298592063643437213380371824613660631584008711686240103416385845390125711005079231226631612790119628517438076962856020578250598417110996970171029663545716229258911304933901864735285384197017662727621049720992964441567484821110407612560423282

p = var('p')
f = pow(p,7)-hint*pow(p,3) - N**3
p = solve(f,p)[0]
# print(p)
P = 11917573148183173444338385104784582231114229409447057112131253050235068806316496452352116287542988361044359262597423159386263430710183647113674868056755407
q = N//P
d = invert(e,(q-1)*(P-1))
m = pow(c,d,N)
print(n2s(int(m)))