俱以我之名

参考文档中的「我是谁」、俱以我之名是维娜的技能，所以我们可以试图将 RSA 和「维娜」作为关键词搜索，出题人尝试了一下，是可以搜到的，于是展开学习。

维纳攻击思想，原理可以参照 Xenny 师傅的文章学习：wiener 攻击。

详细证明可以看维基百科：Wiener's attack.

我们可以借助连分数来分解 $p$ 和 $q$ 来对 RSA 打真伤。

在这里我们有

$$\begin{array}{c}\mathrm{Golden}\mathrm{\_}\mathrm{Oath}=(p-114)(p-514)(p+114)(p+514)(q-1919)(q-810)(q+1919)(q+810)\approx N^4\\ \frac{y}{\mathrm{Golden}\mathrm{\_}\mathrm{Oath}}\approx \frac{k}{x}\end{array}$$

from Crypto.Util.number import *
from gmpy2 import *
import random

n = 141425071303405369267688583480971314815032581405819618511016190023245950842423565456025578726768996255928405749476366742320062773129810617755239412667111588691998380868379955660483185372558973059599254495581547016729479937763213364591413126146102483671385285672028642742654014426993054793378204517214486744679
c = 104575090683421063990494118954150936075812576661759942057772865980855195301985579098801745928083817885393369435101522784385677092942324668770336932487623099755265641877712097977929937088259347596039326198580193524065645826424819334664869152049049342316256537440449958526473368110002271943046726966122355888321
y = 217574365691698773158073738993996550494156171844278669077189161825491226238745356969468902038533922854535578070710976002278064001201980326028443347187697136216041235312192490502479015081704814370278142850634739391445817028960623318683701439854891399013393469200033510113406165952272497324443526299141544564964545937461632903355647411273477731555390580525472533399606416576667193890128726061970653201509841276177937053500663438053151477018183074107182442711656306515049473061426018576304621373895497210927151796054531814746265988174146635716820986208719319296233956243559891444122410388128465897348458862921336261068868678669349968117097659195490792407141240846445006330031546721426459458395606505793093432806236790060342049066284307119546018491926250151057087562126580602631912562103705681810139118673506298916800665912859765635644796622382867334481599049728329203920912683317422430015635091565073203588723830512169316991557606976424732212785533550238950903858852917097354055547392337744369560947616517041907362337902584102983344969307971888314998036201926257375424706901999793914432814775462333942995267009264203787170147555384279151485485660683109778282239772043598128219664150933315760352868905799949049880756509591090387073778041
e = 65537

class ContinuedFraction():
    def __init__(self, numerator, denumerator):
        self.numberlist = []
        self.fractionlist = []
        self.GenerateNumberList(numerator, denumerator)
        self.GenerateFractionList()

    def GenerateNumberList(self, numerator, denumerator):
        while numerator != 1:
            quotient = numerator // denumerator
            remainder = numerator % denumerator
            self.numberlist.append(quotient)
            numerator = denumerator
            denumerator = remainder

    def GenerateFractionList(self):
        self.fractionlist.append([self.numberlist[0], 1])
        for i in range(1, len(self.numberlist)):
            numerator = self.numberlist[i]
            denumerator = 1
            for j in range(i):
                temp = numerator
                numerator = denumerator + numerator * self.numberlist[i - j - 1]
                denumerator = temp
            self.fractionlist.append([numerator, denumerator])

n = pow(n,4)
a = ContinuedFraction(y, n)
for k, x in a.fractionlist:
    # 判断哪一个是我们所需的 x
    if b'end' in long_to_bytes(x):
        print(x)
        print(k)
        break

print(long_to_bytes(x))
Golden_Oath = (x*y-1)//k
print(Golden_Oath)

'''
103697213497220650500739251621743955651854455782387759691953279488676501281257640431561
56398712132783063027132828918468670442692437484816382768162819797891220782528221182512
b'5`\xf4\xf6t\xa3\x00end1n9_A_G2@nd_Ov3RTu2e\x1c\x13"H\x0f\xc9'
#400042032831098007958224589201074030167511216235146696966889080122265111949126155016295896501799032251334875101500882585261911204171467951139573150807043239564581043145433814155757093989016940205116328236031283789686099217459678429270939065783626769903068201144816933538226628329294355184200590029028565011348654002192085571172863125467318356642528249715812871925525776008917314884490518613080652875623759460663908309369135829140204137773254011408135516737187092812588388209697036416805176286184831779945910125467423823737934475944632379524991238593952097013985394648562259886597816452815669024660257170465154297959999722533255899489096196292778430386116108069053440749172609798098777046509743030019115282253351905670418760503352277616008654327326851761671410084489662135479597061419403235762755010286075975241013273964842915146756571330207605591193457296347769260777032489271278979332616929093357929916558230665466587125254822846466292980360420737307459205352964255972268278992730637939153686420457279334894980200862788513296786385507282999530973028293157179873999483225505784146175328159014143540959190522315340971608002638786511995717564457749873410017343184395040614025573440462522210939180555090227730875845671821586191943346000
'''

至此，$\mathrm{Golden}\mathrm{\_}\mathrm{Oath}$、$n$ 以及它们和 $p$、$q$ 关系均已知，利用两个等式解个二元方程即可。

这里我们使用 sympy 库解方程

Golden_Oath = 400042032831098007958224589201074030167511216235146696966889080122265111949126155016295896501799032251334875101500882585261911204171467951139573150807043239564581043145433814155757093989016940205116328236031283789686099217459678429270939065783626769903068201144816933538226628329294355184200590029028565011348654002192085571172863125467318356642528249715812871925525776008917314884490518613080652875623759460663908309369135829140204137773254011408135516737187092812588388209697036416805176286184831779945910125467423823737934475944632379524991238593952097013985394648562259886597816452815669024660257170465154297959999722533255899489096196292778430386116108069053440749172609798098777046509743030019115282253351905670418760503352277616008654327326851761671410084489662135479597061419403235762755010286075975241013273964842915146756571330207605591193457296347769260777032489271278979332616929093357929916558230665466587125254822846466292980360420737307459205352964255972268278992730637939153686420457279334894980200862788513296786385507282999530973028293157179873999483225505784146175328159014143540959190522315340971608002638786511995717564457749873410017343184395040614025573440462522210939180555090227730875845671821586191943346000
from sympy import symbols, Eq, solve

p, q = symbols('p q')
equation1 = Eq(p * q, n)
equation2 = Eq((p-114)*(p-514)*(p+114)*(p+514)*(q-1919)*(q-810)*(q+1919)*(q+810), Golden_Oath)
solutions = solve((equation1, equation2), (p, q))
print(f"p 和 q 的解: {solutions}")

'''
p 和 q 的解: [(-11256874906034337229658272553494271626180719204801621165552253304119314454014247481847595578004383239651599038196432752043642616511808644606155091511313329, -12563439896413287507369191021540890661182794010085857062984791988214078294298809633469029528754549607502031091193150571585844351836163514784874848514208151), (11256874906034337229658272553494271626180719204801621165552253304119314454014247481847595578004383239651599038196432752043642616511808644606155091511313329, 12563439896413287507369191021540890661182794010085857062984791988214078294298809633469029528754549607502031091193150571585844351836163514784874848514208151)]
'''

分解出 $p$ 和 $q$ 我们就成功对 RSA 打出了最真实的伤害，然后常规流程抬走

p = 11256874906034337229658272553494271626180719204801621165552253304119314454014247481847595578004383239651599038196432752043642616511808644606155091511313329
q = 12563439896413287507369191021540890661182794010085857062984791988214078294298809633469029528754549607502031091193150571585844351836163514784874848514208151
d = inverse(e, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(m))
# b'flag{rE@L_d@m@9e_15_7h3_mo5t_au7hEn7ic_dam49E}'