杂记(二)

记录些近期做的题目

2022西湖论剑

2022西湖论剑——LockbyLock

task.py

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

class Lock:
    def __init__(self, p, q) -> None:
        while True:
            self.p = p
            self.q = q
            self.n = self.p * self.q
            self.e = random.randint(10**14, 10**15)
            
            if gcd(self.e, (self.p-1)*(self.q-1)) == 1:
                self.d = invert(self.e, (self.p-1)*(self.q-1))
                break
    
    def lock(self, message: int) -> int:
        assert 1 < message < self.n
        return powmod(message, self.e, self.n)
    
    def unlock(self, cipher: int) -> int:
        assert 1 < cipher < self.n
        return powmod(cipher, self.d, self.n)


def secureProcedure(A, B):
    global flag
    flag = bytes_to_long(flag)
    print('Alice: lock lock lock lock unlock')
    msg1 = A.lock(flag)
    print(f'Alice: locked msg1 = {msg1}')
    print('Alice: lock lock lock lock')
    
    print('Bob: lock unlock lock lock')
    msg2 = B.lock(msg1)
    print(f'Bob: locked msg2 = {msg2}')
    print('Bob: lock lock lock lock')
    
    print('Alice: unlock unlock unlock...')
    msg3 = A.unlock(msg2)
    print(f'Alice: unlocked msg3 = {msg3}')
    print('Alice: lock lock lock lock')
    
    print('Bob: unlock unlock unlock...')
    msg = B.unlock(msg3)
    
    assert msg == flag
    print('Bob: lock lock unlock')
    print('Bob: lock by lock, lock lock right, unlock unlock unlock...')
    print('Alice: right right, lock lock unlock')
    print('Bob: lock lock lock, flag lock lock lock.')
    print('Alice: lock unlock lock lock, unlock lock lock')
    print('Bob: lock lock!')
    
    
def proxyProcedure(A, B):
    print('Agent: lock lock, lock lock lock, unlock lock lock right')
    print('Alice: lock!')
    print('Bob: lock lock, unlock lock!')
    omsg = int(input())
    
    print('Alice: lock lock lock lock unlock')
    msg1 = A.lock(omsg)
    print(f'Alice: locked msg1 = {msg1}')
    print('Alice: lock lock lock lock')
    
    print('Bob: lock unlock lock lock')
    msg2 = B.lock(msg1)
    print(f'Bob: locked msg2 = {msg2}')
    print('Bob: lock lock lock lock')
    
    print('Alice: unlock unlock unlock...')
    msg3 = A.unlock(msg2)
    print(f'Alice: unlocked msg3 = {msg3}')
    print('Alice: lock lock lock lock')
    
    print('Bob: unlock unlock unlock...')
    msg = B.unlock(msg3)
    
    
    assert msg == omsg
    print('Bob: lock, lock, locked lock lock lock unlock')
    print('Bob: lock by lock, lock lock right, lock unlock unlock unlock...')
    print('Alice: right right, locked lock lock lock unlock')
    print('Bob: lock lock!')
    

def main():
    p = getPrime(1024)
    q = getPrime(1024)
    AliceLock = Lock(p, q)
    BobLock = Lock(p, q)
    
    secureProcedure(AliceLock, BobLock)
    
    try:
        proxyProcedure(AliceLock, BobLock)
        proxyProcedure(AliceLock, BobLock)
        print('Lock: lock lock lock, unlock lock lock lock, lock lock unlock lock unlock lock, lock.')
    except Exception:
        print('lock unlock, lock locked, unlocked lock')


if __name__ == '__main__':
    main()

审计代码得知
$$ms{g}_1\equiv fla{g}^{e_1}\mathrm{mod}n$$

$$ms{g}_2\equiv fla{g}^{e_1\ast e_2}\mathrm{mod}n$$

$$ms{g}_3\equiv fla{g}^{e_2}\mathrm{mod}n$$

服务器给了两次proxyProcedure()的机会

通过proxyProcedure()我们可以得到3段密文

于是，我们输入2可得
$$c_1\equiv 2^{e_1}\mathrm{mod}n$$

$$c_2\equiv 2^{e_1\ast e_2}\mathrm{mod}n$$

$$c_3\equiv 2^{e_2}\mathrm{mod}n$$

再输入4可得
$$c{c}_1\equiv 4^{e_1}\mathrm{mod}n$$

$$c{c}_2\equiv 4^{e_1\ast e_2}\mathrm{mod}n$$

$$c{c}_3\equiv 4^{e_2}\mathrm{mod}n$$

把得到的两组密文进行组合，求得n。eg:$n=gcd(c_1^2-c{c}_1,c_3^2-c{c}_3)$

再求解离散对数获得$e_1,e_2$（${10}^{14}-{10}^{15}$大概几分钟）

再共模攻击

exp

from Crypto.Util.number import *
import gmpy2

c1 = [8919686474918897168952707528612673476553786170801874964846124642381101742458542901830715980268623452966929900752858132438049227721458797460208284488780251775873246769330504302287407994319765869577906215349894658046577390388263589451001732598244036632984412842562489431047594491566838467764983466958980842137844677536462841351093174828887606793643068632029093558130789058597121248035054616064617223778747297125600126660576460060955869895521110712425293590190315342597318561479687856366871472497231392109572085060634379088016694764906328293260246308300814975705006670492500134392078342888450718601718022222930993217282,7425518761994523073317364198947537442910885783906259167922831759980921168251754242069499709256145711530304827273647092602876125639390345250799155815552973274271252681365048383883276690297570135123140317311822486820469382365121145117987684635353219860768514397727531948192217069650335367422468548793299897763378603239057978280786893878765285050377795007037327434151657937614915353291680672904480481007754966874445330490973360536524163265310316559276582521483773857931781035768657973137352302775712706167004357095712599553396034676939636243002510825564410102241257798548639491115779622467253153775728235240585307152220,2181617192203661371735017429198359162025737220087292110511761294058994571110199418171508100871522936260815601099943610508062418354760460212007371379965312164347042760948453091027937608680972160660922852831321012001170313405282852695406864646594343019500600244293499453602954148451046674137010317368810968694921777372589439694486685444784368840750489911337547486361578130125527592186113274198383286718186344218718128274401041586797422577425053217277884781032962785854168676156369097197255913481111686453434425750750756198518882743512813182526191431261206629117677430322615123656908000515270191493488669189654571151751]
c2 = [14171898980683650703815823847617062194657416048901605497683325789644283283142462222704392691935282200835680484710371199815708437414455858753316025648847278736734706547605791804640257506333720487484751993950790713766493435260578130140865576108228116847730834444896471531676115828422044059446021739901318240494138854046095499591654181834708962519053826072002918803533427412731274233361491855387600981920631551574272954469826462733368624850249019030343941656391400900426587970256715590448491140264303909013929718849975528390677173911504084434106882720162635719168218523726338018089817351448818087370461379922861021909713,4860324160931804613459608271226507282150467135115350179864156987410506034051504290787680674119981385596563650589797251344620296331251716788646580253149097368340940984731009513388342050658541065281153662870532490604581093897306071132002827542237574363958475384451505396705074762830073742073864971463392248788973146151105753332464446669911841735820621741687451487332407322924989571202911174797144178489035778647173913241777729633238774307408660649739019370406319254293043292181100882609712233435119877867729739782865828025739689387156393991388981741717217281159767767553470723483112578556957696160678236801750337286609,12515071316992093975741719272231454936929693495951674694172997083706049310755670153534121767294433058514225580906553776851865814795478321272092342551997846797037649833037566074844174515072710950746349594961819349192580271366294872867594238848278426203923887216598026509614305014075314177282823116599839442013642149783998673592468085477417954161078019541898301361883281802528559120809048579663299636400105773272580455451337572425678187752701749521381591061675445691734941125014540376523538795103366249623802898160724737265398273542166418851825022650158041768183017130500629477827250620222284836291969907830395844393509]
c3 = [369858427774169904461049227452782560932273390006843066948952113537902955230694241872630184876128533763539804666594986550600066729556996678424073928770758937798064281859152460682292334835525838558750960184667676458620169407136641190032250303181877597669650158309820288061918115940356003614885937404886651273550231251946895945371753347619244532318674385519281497124130634157967089514131092246785587398424697807103123014787468819604775392736417084514888658871516880552887289444751642253959645225606192133589859862177318750339212901834546879650869875347729488909022955107604363483972579779145559848329176980848913878070,5654822427791974095246270532900190405950109607926280088377625546201144679670636916418191767454255193771537404495320329948460811648970795323928665802304017599628560376646415300140865793751181301698829644462758630246805539778990721719141629068609799643355921448991113823535040300166759700691992291039210552669941380818740641705272447221130347797777987693856808485682820997975665057551765604103729766946408295120655574617932634446928520077975913714743609551997907005944835003809338264936786195639188686278989010109386530859156260421210496165703425652796324045999507174633751258061125978685961702627123824708455687209741,6155569487283245742338000777385393886764169967844501278631567721744713134419841108219959053313555353334271249860864935118896778532864637949013633814326038999921032159115696345763508445026649884667249919023787499592869832754972412246656741357999132911729154882795079570688109191827957004527558878904939490355358470701060618902959479823476014931295935435372965659522455979350055521071614497737255431370247076414625456625404880871040998212051411303494906394765756593993881824157076376480221771841635364602260257935196984813868974689691893745299732855490564826087524621730349145021388197162527326675817019202561118078174]

temp1 = c2[0]**2 - c3[0]
temp2 = c2[1]**2 - c3[1]
n = gmpy2.gcd(temp1,temp2)

e1 = discrete_log_lambda(mod(c2[0],n),mod(2,n),(ZZ(10^14),ZZ(10^15)))
e2 = discrete_log_lambda(mod(c2[2],n),mod(2,n),(ZZ(10^14),ZZ(10^15)))
_,x,y = gmpy2.gcdext(e1,e2)
m = pow(c1[0],x,n)*pow(c1[2],y,n)%n
print(long_to_bytes(int(m)))

2022西湖论剑——MyErrorLearn

task.py

from Crypto.Util.number import *
import random, os
from gmpy2 import *
flag = os.getenv('DASFLAG')

p = random.getrandbits(1024)

print('> mod =', p)
secret = random.randint(1, p-1)

def XennyOracle():
    r = getPrime(512)
    d = invert(secret+r, p) - getPrime(246)
    print('> r =', r)
    print('> d =', d)

def task():
    for _ in range(3):
        op = int(input())
        if op == 1:
            XennyOracle()
        elif op == 2:
            ss = int(input())

            if ss == secret:
                print('flag: ', flag)

try:
    task()
except Exception:
    print("Error. try again.")

已知
$$d\equiv (secret+r{)}^{-1}-e\mathrm{mod}p$$
则有
$$(d_1+e_1)(secret+r_1)\equiv 1\mathrm{mod}p$$

$$(d_2+e_2)(secret+r_2)\equiv 1\mathrm{mod}p$$

$e$的数量级为246bit，把secret消去后只有$e_1,e_2$两个未知数，再用二元copper求小根得到$e_1,e_2$

上面的式子乘$(d_2+e_2)$，下面式子乘$(d_1+e_1)$得
$$(d_1+e_1)(d_2+e_2)(secret+r_1)\equiv d_2+e_2\mathrm{mod}p$$

$$(d_1+e_1)(d_2+e_2)(secret+r_2)\equiv d_1+e_1\mathrm{mod}p$$

化简得
$$(d_1+e_1)(d_2+e_2)(r_2-r_1)+(d_2+e_2)-(d_1+e_1)\equiv 0\mathrm{mod}p$$
用二元copper可解出$e_1,e_2$

再代入得$secret=(d_1+e_1{)}^{-1}-r_1\mathrm{mod}p$或者$secret=(d_2+e_2{)}^{-1}-r_2\mathrm{mod}p$

由于p不一定是素数，所以求逆元的时候可能不存在，多跑几次即可

exp

from Pwn4Sage.pwn import *
from tqdm import *
from Crypto.Util.number import *
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []


for i in trange(100):
    try:
        sh = remote("node4.anna.nssctf.cn",28593)
        p = int(sh.recvline().strip().decode().split("=")[-1])
        sh.sendline(b"1")
        sh.recvline()
        r1 = int(sh.recvline().strip().decode().split("=")[-1])
        d1 = int(sh.recvline().strip().decode().split("=")[-1])
        sh.sendline(b"1")
        sh.recvline()
        r2 = int(sh.recvline().strip().decode().split("=")[-1])
        d2 = int(sh.recvline().strip().decode().split("=")[-1])

        R.<x,y> = PolynomialRing(Zmod(p))

        f = (d1+x)*(d2+y)*(r2-r1)+(d2+y)-(d1+x)
        e1,e2 = small_roots(f,bounds=(2^246,2^246))[0]
        s = inverse(int(d1 + e1),p) - r1
        print(f"s = {s}")
        sh.sendline(b"2")
        sh.sendline(str(s).encode())
        sh.interactive()
    except:
        continue

2022西湖论剑——MyErrorLearnTwice

task.py

from Crypto.Util.number import *
import random, os
from gmpy2 import *
flag = os.getenv('DASFLAG')

p = random.getrandbits(1024)

print('> mod =', p)
secret = random.randint(1, p-1)

def XennyOracle():
    r = getPrime(512)
    d = invert(secret+r, p) - getPrime(328)
    print('> r =', r)
    print('> d =', d)

def task():
    for _ in range(16):
        op = int(input())
        if op == 1:
            XennyOracle()
        elif op == 2:
            ss = int(input())

            if ss == secret:
                print('flag: ', flag)

try:
    task()
except Exception:
    print("Error. try again.")

与上题不同之处在于$e$变成了328bit的数，交互次数从3次提高到了16次

但328bit相对p的大小依旧是小量，而且可获得的数据有15组，可以用格解决

类似上题的推导
$$(d_1+e_1)(d_2+e_2)(secret+r_1)\equiv d_2+e_2\mathrm{mod}p$$

$$(d_1+e_1)(d_2+e_2)(secret+r_2)\equiv d_1+e_1\mathrm{mod}p$$

化简得
$$(d_1+e_1)(d_2+e_2)(r_2-r_1)+(d_2+e_2)-(d_1+e_1)\equiv 0\mathrm{mod}p$$
我们每两组数据进行一次化简，便有了
$$(d_1+e_1)(d_i+e_i)(r_i-r_1)+(d_i+e_i)-(d_1+e_1)\equiv 0\mathrm{mod}p(2\le i\le 15)$$
展开得
$$e_1{e}_i(r_i-r_1)+e_i[d_1(r_i-r_1)+1]+e_1[d_i(r_i-r_1)-1]+[d_1{d}_i(r_i-r_1)+(d_i-d_1)]\equiv 0\mathrm{mod}p$$
记
$$A_i=r_i-r_1$$

$$B_i=d_1(r_i-r_1)+1$$

$$C_i=d_i(r_i-r_1)-1$$

$$D_i=d_1{d}_i(r_i-r_1)+(d_i-d_1)$$

则有
$$A_i{e}_1{e}_i+B_i{e}_i+C_i{e}_1+D_i\equiv 0\mathrm{mod}p$$
即
$$A_i{e}_1{e}_i+B_i{e}_i+C_i{e}_1+D_i+k_{i}p=0(2\le i\le 15)$$
构造格

本人在做题的时候在格的规格这里有卡顿，如有同样疑惑的师傅可以静下来思考一下再往下。

$e_1{e}_i$共14个，$e_i$共15个，$k_i$共14个。因此格的规格是$44\times 44$

为了提高规约成功的概率，对格进行调平，最后的格如下：

其中$T=2^{328},TT=2^{328\times 2},k=2^{328\times 3}$

得到$e_1$后，再代入得$secret=(d_1+e_1{)}^{-1}-r_1\mathrm{mod}p$

exp

from Pwn4Sage.pwn import *
from tqdm import *
from Crypto.Util.number import *

def getData():
    p = int(sh.recvline().strip().decode().split("=")[-1])
    r = []
    d = []
    for i in range(15):
        sh.sendline(b"1")
        sh.recvline()
        rr = int(sh.recvline().strip().decode().split("=")[-1])
        dd = int(sh.recvline().strip().decode().split("=")[-1])
        r.append(rr)
        d.append(dd)
    if len(r) == 15 and len(d) == 15:
        return r,d,p

def getE():
    num = 15
    N = 3*num-1
    T = 2^(328*3)
    A = [r[i] - r[0] for i in range(1,num)]
    B = [d[0]*(r[i] - r[0]) + 1 for i in range(1,num)]
    C = [d[i]*(r[i] - r[0]) - 1 for i in range(1,num)]
    D = [d[0]*d[i]*(r[i] - r[0]) + (d[i] - d[0]) for i in range(1,num)]
    
    Ge = Matrix(ZZ,N,N)
    for i in range(N):
        Ge[i,i] = 1
    for i in range(num-1):
        Ge[2*num+i,2*num+i] = p*T
        
        Ge[i,2*num+i] = A[i]*T
        Ge[num-1,2*num+i] = C[i]*T
        Ge[num+i,2*num+i] = B[i]*T
        Ge[2*num-1,2*num+i] = D[i]*T
    
    for i in range(num):
        Ge[num-1+i,num-1+i] = 2^328
    Ge[2*num-1,2*num-1] = 2^(328*2)
    
    for line in Ge.LLL():
        if line[-1] == 0:
            e1 = int(abs(line[14]) // 2^328)
            if int(e1).bit_length() == 328:
                print(f"e1 = {e1}")
                return e1

def getFlag():
    secret = (inverse(int(d[0]+e1),p) - r[0]) % p
    print(f"secret = {secret}")
    sh.sendline(b"2")
    sh.sendline(str(secret).encode())
    sh.interactive()
    
sh = remote("node4.anna.nssctf.cn",28661)
r,d,p = getData()
e1 = getE()
getFlag()

2023西湖论剑

2023西湖论剑——Or1cle

无附件，通过getflag，输入的字符串，长度不是2的倍数，泄露源码

def signature(self,msg):
    h = int(hashlib.sha256(msg).hexdigest(),16)
    k = h^self.d
    r = (k*secp256k1.G).x
    s = inverse(k,secp256k1.q) * (h + r*self.d) % secp256k1.q
    return '%064x%064x' % (r, s)

def verify(self,z, signature):
    r, s = int(signature[:64], 16), int(signature[64:], 16)
    z = int(hashlib.sha256(z).hexdigest(), 16)
    s_inv = pow(s, secp256k1.q - 2, secp256k1.q)
    u1 = (z * s_inv) % secp256k1.q
    u2 = (r * s_inv) % secp256k1.q
    point = u1 * secp256k1.G + u2 * self.P
    return point.x == r

猜测得到flag的条件是让verify(signature)函数返回True

我们能控制的只有signature

非预期

因为verify没有对0采取处理，而且求逆元用的不是inverseorinvert，而是

s_inv = pow(s, secp256k1.q - 2, secp256k1.q)

因此，传入128个0即可让verify(signature)返回True

网鼎杯 2022 玄武组——crypto557

task.py

from Crypto.Util.number import *
import random
from secret import flag

f = open("output.txt","w")

for i in range(18):
    p = getPrime(256)
    x = random.randint(2, p-1)
    tmp = bytes_to_long(flag)
    enc = []
    for j in range(size(tmp)):
        r = random.randint(2, p-1)
        if tmp%2:
            enc += [pow(x, r, p)]
        else:
            enc += [r]
        tmp //= 2
    
    f.write("p = " + str(p) + "\n")
    f.write("enc = " + str(enc) + "\n")

题目根据m从低到高位为0或1给出不同的enc

所以我们解题思路也是通过enc来判断m当前位是0或1，本题用上二次剩余的性质

根据《信息安全数学基础》中的定理：如果$p$是奇素数，则模p的简化剩余系(也就是$(0,p-1)$)中有$\frac{p-1}{2}$个模p的平方剩余和$\frac{p-1}{2}$个平方非剩余，也就是说$x$是模p平方剩余的概率是0.5

所以我们做出下面分析

1. 如果$x$是模p的平方剩余，则$x^{\frac{p-1}{2}}\equiv 1\mathrm{mod}p$(这条是平方剩余的性质)，可推出$(x^{\frac{p-1}{2}}{)}^r\equiv 1\mathrm{mod}p$也就是$c^{\frac{p-1}{2}}\equiv 1\mathrm{mod}p$，$c$就是$x^r$，这个推导说明如果$x$是模p的平方剩余，则c也是模p的平方剩余
2. 如果$x$不是模p的平方剩余，则c是模p平方剩余的概率也为0.5，因为$c\equiv x^r\mathrm{mod}p$，这个c也是$(0,p-1)$的数
3. 再结合上m从低位到高位是0或1，可以推断出:
4. c是模p平方剩余的概率是$\frac{1}{2}\times 1+\frac{1}{2}\times \frac{1}{2}=0.75$，对应的是x是模p平方剩余，且$m$当前位数是1，添入enc的是$x^r\mathrm{mod}p$，或m当前位数是0，添入enc的是$r$
5. c不是模p平方剩余的概率是$\frac{1}{2}\times \frac{1}{2}+\frac{1}{2}\times \frac{1}{2}=\frac{1}{2}$，对应的是x不是模p平方剩余，所以c没有规律，就按照性质得知c是模p平方剩余的概率为$\frac{1}{2}$

所以根据每组c是模p平方剩余的概率可以判断出这组c对应的x是否为模p的平方剩余。

把所有是模p平方剩余的x提取出来之后，我们再作出下面的分析：

1. 已知x是模p的平方剩余
2. 如果当前的m是1，则添入enc的是$x^r\mathrm{mod}p$，应当也是模p的平方剩余
3. 如果当前的m是0，则添入enc的是$r$，它是模p平方剩余的概率是$\frac{1}{2}$

我们可以遍历所有x，判断当前的$c$是否为模p的平方剩余，只要遍历完所有x，发现c都是模p的平方剩余，则可以判断出m当前的位数就是1

exp

from Crypto.Util.number import *
import gmpy2

def getData():
    cipher = []
    p = []
    lines = open("output.txt", "rb").readlines()
    for i in range(0, len(lines), 2):
        pp = eval(lines[i].strip(b"p = ").strip(b"\n"))
        p.append(pp)
        cc = eval(lines[i+1].strip(b"enc = ").strip(b"\n"))
        cipher.append(cc)
    return cipher,p
    
cipher,p = getData()
x = []							#提取所有是模p平方剩余的x

for i in range(len(cipher)):
    num = 0
    for j in range(len(cipher[0])):
        if gmpy2.jacobi(cipher[i][j],p[i]) == 1:
            num += 1
    t = num / len(cipher[0])
    if t > 0.7:
        x.append(i)	

m = ''
for i in range(len(cipher[i])):
    num = True
    for j in x:
        if gmpy2.jacobi(cipher[j][i],p[j]) != 1:
            num = False
            break
    if num:
        m += '1'
    else:
        m += '0'

flag = long_to_bytes(int(m[::-1],2))
print(flag)
# flag{c8b10fb7-95f8-47a2-bfb3-b9489ad39711}

网鼎杯 2022 青龙组——Grasshopper

task.py

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

from grassfield import flag

p = getPrime(16)

k = [randrange(1,p) for i in range(5)]

for i in range(len(flag)):
    grasshopper = flag[i]
    for j in range(5):
        k[j] = grasshopper = grasshopper * k[j] % p
    print('Grasshopper#'+str(i).zfill(2)+':'+hex(grasshopper)[2:].zfill(4))

先理解题目的运算：

$i=0$时
$$k_{10}=g_0=ord(f)\times k_{00}\mathrm{mod}p$$

$$k_{11}=g_0=ord(f)\times k_{00}\times k_{01}\mathrm{mod}p$$

$$k_{12}=g_0=ord(f)\times k_{00}\times k_{01}\times k_{02}\mathrm{mod}p$$

$$k_{13}=g_0=ord(f)\times k_{00}\times k_{01}\times k_{02}\times k_{03}\mathrm{mod}p$$

$$k_{14}=g_0=ord(f)\times k_{00}\times k_{01}\times k_{02}\times k_{03}\times k_{04}\mathrm{mod}p$$

$i=1$时
$$k_{20}=g_1=ord(l)\times k_{10}\mathrm{mod}p$$

$$k_{21}=g_1=ord(l)\times k_{10}\times k_{11}\mathrm{mod}p$$

$$k_{22}=g_1=ord(l)\times k_{10}\times k_{11}\times k_{12}\mathrm{mod}p$$

$$k_{23}=g_1=ord(l)\times k_{10}\times k_{11}\times k_{12}\times k_{13}\mathrm{mod}p$$

$$k_{24}=g_1=ord(l)\times k_{10}\times k_{11}\times k_{12}\times k_{13}\times k_{14}\mathrm{mod}p$$

$i=2$时
$$k_{30}=g_2=ord(a)\times k_{20}\mathrm{mod}p$$

$$k_{31}=g_2=ord(a)\times k_{20}\times k_{21}\mathrm{mod}p$$

$$k_{32}=g_2=ord(a)\times k_{20}\times k_{21}\times k_{22}\mathrm{mod}p$$

$$k_{33}=g_2=ord(a)\times k_{20}\times k_{21}\times k_{22}\times k_{23}\mathrm{mod}p$$

$$k_{34}=g_2=ord(a)\times k_{20}\times k_{21}\times k_{22}\times k_{23}\times k_{24}\mathrm{mod}p$$

$i=3$时
$$k_{40}=g_3=ord(g)\times k_{30}\mathrm{mod}p$$

$$k_{41}=g_3=ord(g)\times k_{30}\times k_{31}\mathrm{mod}p$$

$$k_{42}=g_3=ord(g)\times k_{30}\times k_{31}\times k_{32}\mathrm{mod}p$$

$$k_{43}=g_3=ord(g)\times k_{30}\times k_{31}\times k_{32}\times k_{33}\mathrm{mod}p$$

$$k_{44}=g_3=ord(g)\times k_{30}\times k_{31}\times k_{32}\times k_{33}\times k_{34}\mathrm{mod}p$$

$i=4$时

先求$k_{53}=k_{54}\times k_{44}^{-1}\mathrm{mod}p$

再求$k_{43}=k_{44}\times k_{34}^{-1}\mathrm{mod}p⟶k_{52}=k_{53}\times k_{43}^{-1}\mathrm{mod}p$

再求$k_{33}=k_{34}\times k_{24}^{-1}\mathrm{mod}p⟶k_{42}=k_{43}\times k_{33}^{-1}\mathrm{mod}p⟶k_{51}=k_{52}\times k_{42}^{-1}\mathrm{mod}p$

再求$k_{23}=k_{24}\times k_{14}^{-1}\mathrm{mod}p⟶k_{32}=k_{33}\times k_{23}^{-1}\mathrm{mod}p⟶k_{41}=k_{42}\times k_{32}^{-1}\mathrm{mod}p⟶k_{50}=k_{51}\times k_{41}^{-1}\mathrm{mod}p$

然后$i=5$时
$$k_{60}=g_5=ord(‘{?}^{\prime })\times k_{50}\mathrm{mod}p$$

$$k_{61}=g_5=ord(‘{?}^{\prime })\times k_{50}\times k_{51}\mathrm{mod}p$$

$$k_{62}=g_5=ord(‘{?}^{\prime })\times k_{50}\times k_{51}\times k_{52}\mathrm{mod}p$$

$$k_{63}=g_5=ord(‘{?}^{\prime })\times k_{50}\times k_{51}\times k_{52}\times k_{53}\mathrm{mod}p$$

$$k_{64}=g_5=ord(‘{?}^{\prime })\times k_{50}\times k_{51}\times k_{52}\times k_{53}\times k_{54}\mathrm{mod}p$$

exp

from Crypto.Util.number import *
from gmpy2 import gcd,invert

g = []
lines = open("output.txt", "rb").readlines()
for i in range(len(lines)):
    g.append(int(lines[i].strip()[-4:].decode(),16))

know = b"flag{"
gmax = max(g)
for p in range(gmax+1,2**16):
    k14 = g[0]
    k24 = g[1]
    k34 = g[2]
    k44 = g[3]
    k54 = g[4]
    # if gcd(know[0],p) == 1 and gcd(know[1],p) == 1 and gcd(know[2],p) == 1 and gcd(know[3],p) == 1 and gcd(know[4],p) == 1:
    
    if isPrime(p):
        # step1
        k53 = k54 * invert(k44,p) % p
        # step2
        k43 = k44 * invert(k34,p) % p
        k52 = k53 * invert(k43,p) % p
        # step3
        k33 = k34 * invert(k24,p) % p
        k42 = k43 * invert(k33,p) % p
        k51 = k52 * invert(k42,p) % p
        # step4 
        k23 = k24 * invert(k14,p) % p
        k32 = k33 * invert(k23,p) % p
        k41 = k42 * invert(k32,p) % p 
        k50 = k51 * invert(k41,p) % p
        
        k = [k50,k51,k52,k53,k54]
        flag = 'flag{'
        for i in range(5,len(g)):
            _k = k[0]*k[1]*k[2]*k[3]*k[4]
            
            m = g[i] * invert(_k,p) % p
            
            flag += chr(m)
            for j in range(5):
                k[j] = m = m * k[j] % p
        if flag.endswith('}'):
            print(f"p = {p}")
            print(flag)
            # flag{749d39d4-78db-4c55-b4ff-bca873d0f18e}
            break

osuCTF

剪枝

task.py

from Crypto.Util.number import isPrime,bytes_to_long
import random
import os

def getWYSIprime():
    while True:
        digits = [random.choice("727") for _ in range(272)]
        prime = int("".join(digits))
        if isPrime(prime):
            return prime
        
# RSA encryption using the WYSI primes
p = getWYSIprime()
q = getWYSIprime()
n = p * q
e = 65537
flag = bytes_to_long(os.getenv("FLAG",b"osu{fake_flag_for_testing}"))
ciphertext = pow(flag,e,n)
print(f"n = {n}")
print(f"e = {e}")
print(f"ciphertext = {ciphertext}")
"""
n = 2160489795493918825870689458820648828073650907916827108594219132976202835249425984494778310568338106260399032800745421512005980632641226298431130513637640125399673697368934008374907832728004469350033174207285393191694692228748281256956917290437627249889472471749973975591415828107248775449619403563269856991145789325659736854030396401772371148983463743700921913930643887223704115714270634525795771407138067936125866995910432010323584269926871467482064993332990516534083898654487467161183876470821163254662352951613205371404232685831299594035879
e = 65537
ciphertext = 2087465275374927411696643073934443161977332564784688452208874207586196343901447373283939960111955963073429256266959192725814591103495590654238320816453299972810032321690243148092328690893438620034168359613530005646388116690482999620292746246472545500537029353066218068261278475470490922381998208396008297649151265515949490058859271855915806534872788601506545082508028917211992107642670108678400276555889198472686479168292281830557272701569298806067439923555717602352224216701010790924698838402522493324695403237985441044135894549709670322380450
"""

从低位往高位爆破即可，因为题目生成的素数只含7,2，所以每次爆破只需要2个数字，爆破起来蛮快的

exp

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

n = 2160489795493918825870689458820648828073650907916827108594219132976202835249425984494778310568338106260399032800745421512005980632641226298431130513637640125399673697368934008374907832728004469350033174207285393191694692228748281256956917290437627249889472471749973975591415828107248775449619403563269856991145789325659736854030396401772371148983463743700921913930643887223704115714270634525795771407138067936125866995910432010323584269926871467482064993332990516534083898654487467161183876470821163254662352951613205371404232685831299594035879
e = 65537
ciphertext = 2087465275374927411696643073934443161977332564784688452208874207586196343901447373283939960111955963073429256266959192725814591103495590654238320816453299972810032321690243148092328690893438620034168359613530005646388116690482999620292746246472545500537029353066218068261278475470490922381998208396008297649151265515949490058859271855915806534872788601506545082508028917211992107642670108678400276555889198472686479168292281830557272701569298806067439923555717602352224216701010790924698838402522493324695403237985441044135894549709670322380450

def findp(p,q):
    l = len(p)
    if l == 272 and n % int(p) == 0:
        q = n // int(p)
        print(f"p = {p}")
        print(f"q = {q}")
    else:
        table = ["2","7"]
        for i,j in itertools.product(table,repeat=2):
            pp = int(i + p)
            qq = int(j + q)
            if pp * qq % 10**l == n % 10**l:
                findp(i+p,j+q)
                
# findp("7","7")
p = 27777727727777722777277277777272772727772722777777277777277772227772772772227272727777772772772727227772777277727777777222777777277727772272272777772722727722777727277727727777777772772777772777277772222727227777777222727777772772272727777222777777277777727272772272272277
q = 77777772777772222722727222227777272777772777772277727772722777777777227277727272772727277277272772727227272772772222277777772727727772722772777272727777272722772777277777277777277777727777277277777277777272772772777777727772727277727777772772777772272772272222227777777227
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(ciphertext,d,n)
print(long_to_bytes(m))
# osu{h4v3_y0u_3v3r_n0t1c3d_th4t_727_1s_pr1m3?}

LCG泄露低位

task.py

from Crypto.Util.number import getPrime # https://pypi.org/project/pycryptodome/
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randrange
from math import floor

def lcg(s, a, b, p):
    return (a * s + b) % p

p = getPrime(floor(72.7))
a = randrange(0, p)
b = randrange(0, p)
seed = randrange(0, p)
print(f"{p = }")
print(f"{a = }")
print(f"{b = }")

def get_roll():
    global seed
    seed = lcg(seed, a, b, p)
    return seed % 100
out = []
for _ in range(floor(72.7)):
    out.append(get_roll())
print(f"{out = }")

flag = open("flag.txt", "rb").read()
key = bytes([get_roll() for _ in range(16)])
iv = bytes([get_roll() for _ in range(16)])
cipher = AES.new(key, AES.MODE_CBC, iv)
print(cipher.encrypt(pad(flag, 16)).hex())

'''
p = 4420073644184861649599
a = 1144993629389611207194
b = 3504184699413397958941
out = [39, 47, 95, 1, 77, 89, 77, 70, 99, 23, 44, 38, 87, 34, 99, 42, 10, 67, 24, 3, 2, 80, 26, 87, 91, 86, 1, 71, 59, 97, 69, 31, 17, 91, 73, 78, 43, 18, 15, 46, 22, 68, 98, 60, 98, 17, 53, 13, 6, 13, 19, 50, 73, 44, 7, 44, 3, 5, 80, 26, 10, 55, 27, 47, 72, 80, 53, 2, 40, 64, 55, 6]
enc = '34daaa9f7773d7ea4d5f96ef3dab1bbf5584ecec9f0542bbee0c92130721d925f40b175e50587196874e14332460257b'
'''

由$X_{n+1}\equiv a{X}_n+b\mathrm{mod}p$

拆成高低位来写，则有
$$H_{n+1}\times 100+L_{n+1}\equiv a(H_n\times 100+L_n)+b\mathrm{mod}p$$
化简得
$$H_{n+1}\equiv a{H}_n+(a{L}_n+b-L_{n+1})\times {100}^{-1}\mathrm{mod}p$$
于是有
$$H_2\equiv a{H}_1+(a{L}_1+b-L_2)\times {100}^{-1}\mathrm{mod}p$$

$$H_3\equiv a{H}_2+(a{L}_2+b-L_3)\times {100}^{-1}\mathrm{mod}p$$

即
$$H_3\equiv a^2{H}_1+(a(a{L}_1+b-L_2)+(a{L}_2+b-L_3))\times {100}^{-1}\mathrm{mod}p$$
写到这里是为了后面更好理解$B_i$如何计算

回到题目，简单来写就是
$$H_{n+1}\equiv A_n{H}_1+B_n\mathrm{mod}p$$
即$H_{n+1}=A_m{H}_1+B_n+k_{n}p$

构造格

exp

from Crypto.Cipher import AES
import gmpy2

p = 4420073644184861649599
a = 1144993629389611207194
b = 3504184699413397958941
out = [39, 47, 95, 1, 77, 89, 77, 70, 99, 23, 44, 38, 87, 34, 99, 42, 10, 67, 24, 3, 2, 80, 26, 87, 91, 86, 1, 71, 59, 97, 69, 31, 17, 91, 73, 78, 43, 18, 15, 46, 22, 68, 98, 60, 98, 17, 53, 13, 6, 13, 19, 50, 73, 44, 7, 44, 3, 5, 80, 26, 10, 55, 27, 47, 72, 80, 53, 2, 40, 64, 55, 6]
enc = '34daaa9f7773d7ea4d5f96ef3dab1bbf5584ecec9f0542bbee0c92130721d925f40b175e50587196874e14332460257b'

L = [0] + out
n = len(out)
A = [1]
B = [0]
for i in range(1,n):
    A.append(a*A[i-1] % p)
    B.append((a*B[i-1] + (a*L[i]+b-L[i+1])*gmpy2.invert(100,p))%p)

A = A[1:]
B = B[1:]

Ge = Matrix(ZZ,n+1,n+1)
for i in range(len(A)):
    Ge[i,i] = p
    Ge[-2,i] = A[i]
    Ge[-1,i] = B[i]

Ge[-2,-2] = 1
Ge[-1,-1] = p // 100

M = Ge.LLL()[0]
H1 = M[-2]
L1 = out[0]
seed1 = H1 * 100 + L1

seed = ((seed1 - b)*gmpy2.invert(a,p))%p
# print(seed)
# 1972400400839421538435
def lcg(s, a, b, p):
    return (a * s + b) % p

def get_roll():
    global seed
    seed = lcg(seed, a, b, p)
    return seed % 100

temp = []
for _ in range(floor(72.7)):
    temp.append(get_roll())
# print(temp == out)
# True
key = bytes([get_roll() for _ in range(16)])
iv = bytes([get_roll() for _ in range(16)])
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(bytes.fromhex(enc))
print(flag)
# osu{w0uld_y0u_l1k3_f1r5t_0r_53c0nd_p1ck}

HSCCTF 2024

EzMath

task.py

from Crypto.Util.number import *

flag = 'HSCCTF{*****************************************}'
x = bytes_to_long(flag.encode())
y = getPrime(200)
z = getPrime(200)
assert (x**2+1)*(y**2+1)*(z**2+1) + 4 * ((x*y*z)*(x+y+z)+(x*y+x*z+y*z)) == jl + 2*(x+y+z+x*y*z)*(x*y+y*z+x*z+1)

w = 1007766898498955907869786015006414110177963571599690507305616866798367726133772947904112344473803352290475298324967917118497719002314168582330651485077694557008496465717884047202330407870172675541471666596768873677342429660840647109788577728613362048023960188394853332768656214046219781162891725391990618222498709603165658933818803574737
a = jl + 2024
b = jl + 2025
c = getPrime(1000)
assert w*(a*c + b*c - a*b) == 4*a*b*c

先从第二个assert算出jl
$$\because w(ac+bc-ab)=4abc$$
同除$wabc$得
$$\frac{4}{w}=\frac{1}{a}+\frac{1}{b}-\frac{1}{c}$$
看了la佬博客才知道这是著名的丢番图方程，la佬也给出了论文

根据论文有
$$a=\frac{w-1}{2},b=\frac{w+1}{2}$$
然后便能解出jl

再根据第一个assert
$$jl=(x^2+1)(y^2+1)(z^2+1)+4[xyz(x+y+z)+(xy+xz+yz)]-2(x+y+z+xyz)(xy+yz+xz+1)$$
化简以后得到
$$jl=(x-1{)}^2(y-1{)}^2(z-1{)}^2$$
推导不太流利的话，可以用下面函数计算

R.<x,y,z> = PolynomialRing(ZZ)
f=(x**2+1)*(y**2+1)*(z**2+1) + 4 * ((x*y*z)*(x+y+z)+(x*y+x*z+y*z)) - 2*(x+y+z+x*y*z)*(x*y+y*z+x*z+1)
print(f.factor())

然后计算出$\sqrt{jl}$即$(x-1)(y-1)(z-1)$ 的所有因子，限制$x,y,z$的位数，进行爆破(参考HSCCTF 2024 | Lazzaro (lazzzaro.github.io))

exp

from Crypto.Util.number import *
import gmpy2

w = 1007766898498955907869786015006414110177963571599690507305616866798367726133772947904112344473803352290475298324967917118497719002314168582330651485077694557008496465717884047202330407870172675541471666596768873677342429660840647109788577728613362048023960188394853332768656214046219781162891725391990618222498709603165658933818803574737

a = (w-1) // 2
b = (w+1) // 2
jl = a - 2024

s = jl.nth_root(2)
print(f"s = {s}")

sf = divisors(s)

yz = []

for i in range(len(sf)):
    t = sf[i] + 1
    # 这个就是所有y,z的可能
    if t > 2^200:
        break
    if t > 2^199 and t < 2^200 and is_prime(t):
        yz.append(t)

for i in range(len(yz)):
    for j in range(i+1, len(yz)):
        x = long_to_bytes(s // ((yz[i]-1)*(yz[j]-1)) + 1)
        if x.isascii():
            print(x)
            # HSCCTF{math_is_good}

simple_rsa

task.py

# # sage
#
from Crypto.Util.number import *
from flag import flag,inc
flag.startwith(b'flag{')

"""
===================== Very very very easy rsa!!! =====================
Rsa public key cryptosystem has been use for many years, in which the
security of large prime number generation method has also been tested,
the following is one of the typical,can you complete this simple chal-
-lenge?
======================================================================
"""

class Enc_RSA():
    def __init__(self,my_own_number):
        self.my_own_number = my_own_number

    def my_own_p(self):
        while 1:
            x = getRandomNBitInteger(1020)
            Try = self.my_own_number*x**2 + 1
            if self.Assert(Try):
                if isPrime(Try//4):
                    return Try//4

    def encrypt(self,p,m):
        q = getPrime(2048)
        n = p*q
        e = 65537
        c = pow(m,e,n)
        return c,n

    def Assert(self,x):
        if x%4 == 0:
            return True
        else:
            return False



if __name__ == '__main__':
    m = bytes_to_long(flag)
    # (inc^3+79*inc^2+65*x+13) % 1009 == 75 and inc is the least number of the solutions
    simple_rsa = Enc_RSA(inc)
    my_own_p = simple_rsa.my_own_p()
    c,n = simple_rsa.encrypt(my_own_p,m)

    print('The number n is {}'.format(n))
    print('The number c is {}'.format(c))


n = 239991661594255432253524767015995553515237552533155266926256011465282762559353011052450949268256733652728779258766468919544696925923029971358451218605372587362458449054025033701801900645898472588154917088906800582917494664328520686255219374705615093349028400487500700497262125962699907814762260694512419306655681221550404511187947035240862982211439747534964306636253099170338798685973287325340707860219110341961583076710007409917903130974964116916771142272349466429861637432682323525150403022509642843376610181395841148978693337599615406649799191853827010907802086292506660315192889149853860466713408351169716170349941283866327264263674186111821195117718331162019362457552641053820550856338437084718718166335155055467914441669571434953065100946319980517952599059131363048098350727744633605485707572274095622988175888575181926216657671979400539900036737074022439888766895137513405183084782345787084384440219108285918795208147597105329833220778335653967184986454715474901645149893734487589920817923864154513632372040497339658475506015077106021525958925682144048668278652340622951676339892584652575698271269136840455952742490194969320271826016057595443197409385545226358578330860265774991784277066549276529111906273907674552737416753863
c = 109418524185171249754036328878536082517954029920067574655738384592535836773335628458417141595917825776593787435093397689973609739515369740356902095262586192608015183792599638006673560604912289524063947742864265648290222544146026010834512839441651151683977393085931597793493789773796447230096442592944882642030190816279289547021784085222443501471419720621671097963713920969317609128950658009064968297525559501068818689604481823678151138300279455535521354912993468606798440152484970180922154575782801057685058825930140799668236228757680911175511728786376925291100386181042980092849556078128905911704118673386991731613513557730970187099491096161742557673136761987701380023132477428777616821281546394707593721174087541309042519043802756642438656462900040566266286487497200417682129927549586193679630211442035605657360570424712008827694002996251982742270642787724129846345798013831392882500535407597060962835644676708823777282733770509418807720840903933760203606859546641772415565269905905400875432944204469576245094963764264460475437038261117576528119870956293781467399036647466377281634948738629392548705519595154811629053243321519324745857848358773804108513698662614500352057759607896553293314291425723185332246973550692552395028420164

首先需要关注的是 # (inc^3+79*inc^2+65*x+13) % 1009 == 75 and inc is the least number of the solutions

这里其实就是解方程$in{c}^3+79\times in{c}^2+65\times inc+13\equiv 75\mathrm{mod}1009$，应该是出题人打错了，所以x对应的就是inc

解方程后可以知道inc是427，然后根据生成素数的方式得知这是个RSA backdoor

参考RSA Backdoor Viability (icewizard4902.github.io)，套一下脚本

exp

class FactorRes(object):
    def __init__(self, r=None, c=None, u=None, a=None):
        self.r = r
        self.c = c
        self.u = u
        self.a = a

def xgcd(f, g, N):
    toswap = False
    if f.degree() < g.degree():
        toswap = True
        f, g = g, f
    r_i = f
    r_i_plus = g
    r_i_plus_plus = f
    s_i, s_i_plus = 1, 0
    t_i, t_i_plus = 0, 1
    while (True):
        lc = r_i.lc().lift()
        lc *= r_i_plus.lc().lift()
        lc *= r_i_plus_plus.lc().lift()
        divisor = gcd(lc, N)
        if divisor > 1:
            return divisor, None, None
        q = r_i // r_i_plus
        s_i_plus_plus = s_i - q * s_i_plus
        t_i_plus_plus = t_i - q * t_i_plus
        r_i_plus_plus = r_i - q * r_i_plus
        if r_i_plus.degree() <= r_i_plus_plus.degree() or r_i_plus_plus.degree() == -1:
            if toswap == True:
                return r_i_plus, t_i_plus, s_i_plus
            else:
                return r_i_plus, s_i_plus, t_i_plus,
        r_i, r_i_plus = r_i_plus, r_i_plus_plus
        s_i, s_i_plus = s_i_plus, s_i_plus_plus
        t_i, t_i_plus = t_i_plus, t_i_plus_plus

def Qinverse (Hx, a, N):
    r,s,t = xgcd(a.lift(), Hx, N)
    if (s,t) == (None, None):
        res = r, 0
    else:
        rinv = r[0]^(-1)
        res = 1, s * rinv
    return res

def CMfactor(D, N):
    Hx = hilbert_class_polynomial(-D)
    res = FactorRes()
    ZN = Integers(N)
    R.<x> = PolynomialRing(ZN)
    Hx = R(Hx)
    Q.<j> = QuotientRing(R, R.ideal(Hx))
    gcd, inverse = Qinverse(Hx, 1728 - j, N)
    if gcd == 1:
        a = Q(j * inverse)
    return CMfactor_core(N, a, Q, ZN, Hx, res)

def CMfactor_core(N, a, Q, ZN, Hx, res):
    for c in [1..10]:
        E = EllipticCurve(Q, [0, 0, 0, 3 * a * c ^ 2, 2 * a * c ^ 3])
        for u in [1..10]:
            rand_elem = ZN.random_element()
            res.rand_elem = int(rand_elem)
            w = E.division_polynomial(N, Q(rand_elem), two_torsion_multiplicity=0)
            poly_gcd = xgcd(w.lift(), Hx, N)[0]
            r = gcd(ZZ(poly_gcd), N)
            res.c = c
            res.u = u
            if r > 1 and r != N:
                return r, N//r

def main():
    sys.setrecursionlimit(50000)
    #####################################INPUTS####################################
    d = 427
    n = 239991661594255432253524767015995553515237552533155266926256011465282762559353011052450949268256733652728779258766468919544696925923029971358451218605372587362458449054025033701801900645898472588154917088906800582917494664328520686255219374705615093349028400487500700497262125962699907814762260694512419306655681221550404511187947035240862982211439747534964306636253099170338798685973287325340707860219110341961583076710007409917903130974964116916771142272349466429861637432682323525150403022509642843376610181395841148978693337599615406649799191853827010907802086292506660315192889149853860466713408351169716170349941283866327264263674186111821195117718331162019362457552641053820550856338437084718718166335155055467914441669571434953065100946319980517952599059131363048098350727744633605485707572274095622988175888575181926216657671979400539900036737074022439888766895137513405183084782345787084384440219108285918795208147597105329833220778335653967184986454715474901645149893734487589920817923864154513632372040497339658475506015077106021525958925682144048668278652340622951676339892584652575698271269136840455952742490194969320271826016057595443197409385545226358578330860265774991784277066549276529111906273907674552737416753863
    c = 109418524185171249754036328878536082517954029920067574655738384592535836773335628458417141595917825776593787435093397689973609739515369740356902095262586192608015183792599638006673560604912289524063947742864265648290222544146026010834512839441651151683977393085931597793493789773796447230096442592944882642030190816279289547021784085222443501471419720621671097963713920969317609128950658009064968297525559501068818689604481823678151138300279455535521354912993468606798440152484970180922154575782801057685058825930140799668236228757680911175511728786376925291100386181042980092849556078128905911704118673386991731613513557730970187099491096161742557673136761987701380023132477428777616821281546394707593721174087541309042519043802756642438656462900040566266286487497200417682129927549586193679630211442035605657360570424712008827694002996251982742270642787724129846345798013831392882500535407597060962835644676708823777282733770509418807720840903933760203606859546641772415565269905905400875432944204469576245094963764264460475437038261117576528119870956293781467399036647466377281634948738629392548705519595154811629053243321519324745857848358773804108513698662614500352057759607896553293314291425723185332246973550692552395028420164
    e = 65537
    #####################################INPUTS####################################

    p, q = CMfactor(d, n)

    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    flag = int(pow(c, d, n))
    print(flag.to_bytes((flag.bit_length() + 7) // 8, 'big').decode())

if __name__ == "__main__":
    main()

flag{!ep1y_@tree}