TetCTF 2020-2019rearrange

roger

分析一下源码，发现我们的任务是已知n, e1, noise1, c1, e2, noise2, c2参数的值，求m的值。其中：

c1 ≡ (m+noise1)^e1 (mod n)
c2 ≡ (m+noise2)^e2 (mod n)

我们考虑采用多项式的思想来解题，将上述两个方程看成多项式的形式，有：

f1(x) = (x+noise1)^e1 - c1
f2(x) = (x+noise2)^e2 - c2

显然，当x=m时，有：

f1(x) = f2(x) = 0

即x = m是多项式f1和f2的一个公共解，也即f3 = gcd(f1,f2)的一个公共解，因此我们只需要计算gcd(f1,f2)，即可得到关于m在模n意义下的多项式方程，从而求出m。

将上述推导写成SageMath代码形式如下：

from binascii import *

n = 99432613480939068351562426450736079548256649399824074125897023718511347184177748762719404609118999419018534660223144728190056735099787907299980625300234355248546050583144387977927309463501291854876892509630938617460690481497010165530214494306444999151252999850250583288798888278770654238342967653191171473013
e1, noise1, c1 = (9102, 42926763857648808452080305910241720054908809667539630194138718908195450776152522239791644645043372458139920503040529361726409749150633609223017012694569617522037971161448894459262110250322393703607247036022683527543284339763718964451482238661494995313111724858075982045508601405376724544741352142401794693054, 48276023282567629527195243870327301962656940680898728928903255577939008086657887592958073923577657060463242759606506812938152312008130198252498457257386413883443843887507528097024367788094619479032221547513746486475136282357337951126122694205225292004957793882304453164618423156810792171305978347365910972343)
e2, noise2, c2 = (2109, 51208643076502294588477225830948052764402322839126847164816681682357946991156728371602766970288519802146987999203830056494899211501025949997165558057140744445002699137286162872658309250096136525032077525028373299701055357023079519776378532002052890676446838318133048612893135724217301724754396467377231356425, 30644829500627448217295366947497931474953886995151259599263428251525601964766004111974074015504963773615137800165460045351514062357500899618814273135292073698096477339942069685331462828432407501524816375109607227118357281435280158409804228556720158131377342049528810546024786899763038442784789928604641662412)

def Pgcd(a, b):
    while b != 0:
        a, b = b, a%b
    return a

P.<x> = PolynomialRing(Zmod(n))
f1 = (x+noise1)^e1 - c1
f2 = (x+noise2)^e2 - c2
f3 = Pgcd(f1,f2)
a, b = f3.coefficients()[::-1]
x = inverse_mod(ZZ(a),n)*(-b)
print unhexlify(hex(int(x))[2:-1])

执行脚本即可得到flag：

TetCTF{1t_1s_4ll_4b0ut_GCD_0v3r_p0lyn0m14ls}