符号计算辅助密码学

例题 BUU - DASbook - happy

# 以下四行 已知
c=0x7a7e031f14f6b6c3292d11a41161d2491ce8bcdc67ef1baa9e
e=0x872a335
#q + q*p^3 =1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586
#qp + q *p^2 = 1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594

PR.<q, p> = PolynomialRing(ZZ)

g1 = q + q * p ^ 3
g2 = q * p + q * p ^ 2

g1_数值 = 1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586
g2_数值 = 1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594

def GCD(g1, g2):
    while g2 != 0:
        g1, g2 = g2, g1 % g2
    return g1

g1GCDg2_符号 = GCD(g1, g2)
print(f'{g1GCDg2_符号 = }')
g1GCDg2_数值 = GCD(g1_数值, g2_数值)
g2除以g1GCDg2_符号 = g2 / g1GCDg2_符号
print(f'{g2除以g1GCDg2_符号 = }')
g2除以g1GCDg2_数值_p = g2_数值 / g1GCDg2_数值
print(f'{g2除以g1GCDg2_数值_p = }')

p = g2除以g1GCDg2_数值_p
把p带入g1 = q + q * p ^ 3
print(f'{把p带入g1 = }')
q_数值 = g1_数值 / 1554084360768842975383894014536904233345764673511716927564775930620902755476680298845463514 # coefficient() 系数
print(f'{q_数值 = }')
n = g2除以g1GCDg2_数值_p * q_数值
phi = (g2除以g1GCDg2_数值_p - 1) * (q_数值 - 1)
d = inverse_mod(e, phi)
m = pow(c, d, n)
from Crypto.Util.number import *
print(long_to_bytes(m))