Home

# 知识点

  • 二元非线性同余方程组
  • Sage 的使用
  • Sylvester 结式法解二元多次方程

# Sylvester 结式法

  • 令f(x)f(x)、g(x)g(x) 分别数域PP 上的非常数多项式，且f(x)f(x) 的幂次为为mm，g(x)g(x) 的幂次为nn

    f(x)=a0+a1x+a2x2+⋯+amxmg(x)=b0+b1x+b2x2+⋯+bnxnf(x)=a_0+a_1x+a_2x^2+\cdots+a_mx^m\\ g(x)=b_0+b_1x+b_2x^2+\cdots+b_nx^n\\

  • 定义f(x)f(x) 与g(x)g(x) 的 Sylvester 结式为一个矩阵

    [amam−1am−2am−3⋯a0amam−1am−2⋯a0⋮⋮⋮⋮⋮⋮⋮⋮amam−1⋯a0bnbn−1bn−2bn−3⋯b0bnbn−1bn−2⋯b0⋮⋮⋮⋮⋮⋮⋮⋮bnbn−1⋯b0]\left[ \begin{matrix} a_m & a_{m-1} & a_{m-2} & a_{m-3} & \cdots & a_0\\ & a_m & a_{m-1} & a_{m-2} & \cdots & & a_0\\ \vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots\\ & & & & a_m & a_{m-1} & \cdots & a_0\\ b_n & b_{n-1} & b_{n-2} & b_{n-3} & \cdots & b_0\\ & b_n & b_{n-1} & b_{n-2} & \cdots & & b_0\\ \vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots\\ & & & & b_n & b_{n-1} & \cdots & b_0\\ \end{matrix} \right]

  • 定义f(x)f(x) 和g(x)g(x) 的 Sylvester 行列式为detdet (Sylvester 结式)，记作res(f,g)res(f,g)，这里的ambn≠0​a_mb_n\ne 0​

  • 定理：令f(x)f(x)、g(x)g(x) 分别数域PP 上的非常数多项式，则f(x)f(x)、g(x)g(x) 不互素当且仅当res(f,g)=0res( f, g)=0

# 解二元高次方程

令二元多次方程表示为

{F(x,y)=0G(x,y)=0(1)\begin{cases} F(x,y)=0\\ G(x,y)=0 \end{cases} \tag{1}

首先我们利用主元法，把FF 和GG 看做是xx 的多项式f(x)f(x) 和g(x)g(x)，因此这两个多项式不互素，于是利用res(f,g)=0res(f,g)=0 可以得到一个关于yy 的方程组，然后解这个方程组得到yy 的值，对于每个yy 的值，带入FF 或GG 求的xx 即可

# 题目

from Crypto.Util.number import bytes_to_long, getPrime
from secret import flag
l = len(flag)
assert l == 56
x = bytes_to_long(flag[:l//2])
y = bytes_to_long(flag[l//2:])
p = getPrime(1024)
e = 0x10001
x = pow(x, e, p)
y = pow(y, e, p)
a = (7 * x + x * y + 77 * y ** 7) % p
b = (x ** 7 + 777 * y) % p
print(f'p = {p}')
print(f'a = {a}')
print(f'b = {b}')
# p = 160676801612994301361202519503059426958636739446670462398261976532859847492256822690640058297338763725128097587993428329580105931247817467950370089691908132361316857330836120708767594061772979871315614755470773991633234068651435625372887767258609941208307491359777513843529144444836847722372845148836203335627
# a = 30318995909014771647618268716833486449002423009996671727903532973647046764624121316716790986592523978549131384964872198795285872746623966910764159262479160147876027157581577141632378119375701270068263640642243000011932466519579133761464923463402462812787531220639360431295348786697861069940729757964584951972
# b = 51036630170491152581994259808984114372634216659979376101433163181132141957563047348137651942358538069256102718534893846618166559129391336639526588292370462975735415885732360576961407017238385374280336346614960555565504032093702784952402038043052556719843691506943605133036720410419999467125928578673380637828
题意就是要我们在已知a、b、q​a、b、q​和下面同余方程组


a≡7x+xy+77y7(modq)b≡x6+777y(modq)a\equiv7x+xy+77y^7 \pmod{q}\\
b\equiv x^6+777y\pmod{q}



求解x,yx,y 的值，然后已知ee 和下式


x≡m1e(modq)y≡m2e(modq)x\equiv m_1^e\pmod{q}\\
y\equiv m_2^e\pmod{q}



最终求解出m1m_1 和m2m_2


由于ZqZ_q 是一个有限域，所以可以把所有操作看做是在有限域下进行的，用 Sage 可以自动在有限域下进行操作，考虑把同余方程组变形成数域qq 下的多项式


{F(x,y)=77y7+xy+7x+a′=0G(x,y)=777y+x6+b′=0(1)\begin{cases}
F(x,y)=77y^7+xy+7x+a^{'}=0\\
G(x,y)=777y+x^6+b^{'}=0
\end{cases}
\tag{1}



其中a′a^{'} 和b′b^{'} 分别是aa、bb 在ZqZ_q 下的相反数


接下来是 Sage 脚本的编写


from sage.matrix.matrix2 import Matrix
def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))  #得到以 var 为变量的多项式 f1 和 f2 的 sylvester 结式的行列式
p = 160676801612994301361202519503059426958636739446670462398261976532859847492256822690640058297338763725128097587993428329580105931247817467950370089691908132361316857330836120708767594061772979871315614755470773991633234068651435625372887767258609941208307491359777513843529144444836847722372845148836203335627
a = 30318995909014771647618268716833486449002423009996671727903532973647046764624121316716790986592523978549131384964872198795285872746623966910764159262479160147876027157581577141632378119375701270068263640642243000011932466519579133761464923463402462812787531220639360431295348786697861069940729757964584951972
b = 51036630170491152581994259808984114372634216659979376101433163181132141957563047348137651942358538069256102718534893846618166559129391336639526588292370462975735415885732360576961407017238385374280336346614960555565504032093702784952402038043052556719843691506943605133036720410419999467125928578673380637828
e = 0x10001
P.<x, y> = PolynomialRing(Zmod(p))  #定义模 p 下的多项式环，变量为 x 和 y
F = 7 * x + x * y + 77 * y ** 7 - a #F(x,y)
G = x ** 7 + 777 * y - b            #G(x,y)
hx = resultant(F, G, y)      #得到关于 res (x)=0 的多项式
rx = hx.univariate_polynomial().roots()  #得到 res (f,g)=0 的根，即 x 的所有取值
#rx 中的每个元素一个二元组
x, _ = zip(*rx)    #获得所有二元组中的第一个元素
#zip 的用法
'''
a = ("John", "Charles", "Mike")
b = ("Jenny", "Christy", "Monica")
x = zip(a, b)
print(x):
(('John', 'Jenny'), ('Charles', 'Christy'), ('Mike', 'Monica'))
'''
y = [((b - i^7) * inverse_mod(777, p)) % p for i in x] #带回 x 得到 y
d = inverse_mod(e, p-1)
for i in range(len(x)):
    m1 = pow(x[i], d, p)
    m2 = pow(y[i], d, p)
    print(long_to_bytes(m1)+long_to_bytes(m2))
得到xx、yy 后就变成了求解RSARSA 了


最后会得到若干组解，其中


x=10473801139457439415841284907691978179887124828501791992501875324249
y=10027371126831070925652949180158084705794567689931733507098463327101



是合法的，最后的 flag  是 'ctfshow{1t_Is_S0o0o0o0o_3A5Y_70_50Lv3_m0duLaR_EqUAt10nS}


# 参考


CTF 七夕杯 WP