TetCTF2020 | 2019rearrange - crypto-writeup-public

あとから考えたらこれFranklin-Reiter Related Message Attackだな

$n = p * q$ で

$c_1 = (m + a_1)^{e_1} \mod n$

$c_2 = (m + a_2)^{e_2} \mod n$

各c, a, eと nが与えられる

$f_1 = (X + a_1)^{e_1} - c_1, f_2 = (X + a_2)^{e_2} - c_2 \in \mathbb{Z_n}[X\rbrack$ を考える。 $\mathbb{Z_n}$ 上だから自明に $f_1(m) = f_2(m) = 0$ なのでこの多項式はそれぞれ $X-m$ で割り切れる。

したがって $gcd(f_1, f_2) = X-m$ が得られる。一変数多項式のgcd

ただし、こうして得た一次式 $aX + b$ のbがすなわち $m$ ということではない。

$aX + b \equiv X - m \mod n$ なので、 $a^{-1}(aX + b) \equiv X - m \mod n$

係数を比較して

$-a^{-1}b \equiv m \mod n$

ということになる。

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

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


R.<x> = PolynomialRing(Zmod(n))
f1 = (x + noise1)^e1 - c1
f2 = (x + noise2)^e2 - c2

b, a = gcd(f1, f2).coefficients()
m = (-inverse_mod(Integer(a), n) * b) % n
print(bytes.fromhex(hex(m)[2:]))