L3HCTF&西湖论剑wp

L3HCTF

ezECDSA

https://crypto.stackexchange.com/questions/44644/how-does-the-biased-k-attack-on-ecdsa-work

上述链接中假设a=0，进行了简化，我们这里由于有kp的存在，所以需要对其稍微变形。然后使用其格子进行规约即可。我这里用的右下角两个数不太好，需要一定概率才能得到正确答案，不太会调这个地方了hhhh。

from mpmath import matrix
from sage.all import *
from Crypto.Util.number import *
from pwn import *
from hashlib import sha256
import string

while 1:
    r = remote('121.36.197.254', 9999)
    p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
    n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
    xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
    yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8


    def proof_of_work():
        r.recvuntil(b'sha256(XXXX+')
        suffix = r.recv(16).decode()
        r.recvuntil(b' == ')
        tar = r.recvuntil(b'\n')[:-1].decode()
        table = string.digits + string.ascii_letters
        for a in table:
            for b in table:
                for c in table:
                    for d in table:
                        if sha256((a + b + c + d + suffix).encode()).hexdigest() == tar:
                            prefix = (a + b + c + d).encode()
                            return prefix


    r.send(proof_of_work() + b' ' * 6)
    l = 1 << 8
    Public_key = r.recvuntil(b'\n')[:-1].decode()
    t = []
    u = []
    for i in range(100):
        r.recvuntil(b"Give me your message:\n")
        r.sendline(b'1')
        r.recvuntil(b"r = ")
        r_sig = int(r.recvuntil(b'\n')[:-1].decode())
        r.recvuntil(b"s = ")
        s_sig = int(r.recvuntil(b'\n')[:-1].decode())
        r.recvuntil(b"kp = ")
        kp = int(r.recvuntil(b'\n')[:-1].decode())
        r.recvuntil(b"hash = ")
        hashh = int(r.recvuntil(b'\n')[:-1].decode())
        h = (hashh-s_sig*kp)%n
        t.append(r_sig * inverse(l * s_sig, n) % n)
        u.append((-h * inverse(l * s_sig, n)) % n)
    t.append(1)
    t.append(0)
    u.append(0)
    u.append(1)
    m = []
    for i in range(100):
        m.append([0] * i + [n] + [0] * (101 - i))
    m.append(t)
    m.append(u)
    m = matrix(m)
    X = m.LLL()[0]
    x = abs(m.LLL()[0][-2])
    print(X)
    if abs(X[-1]) != 1:
        r.close()
    else:
        r.recvuntil(b"Give me dA\n")
        r.sendline(str(x).encode())
        r.interactive()
#L3HCTF{c7b7e21f60fd1e2deb233fcfd7ebfa12}

西湖论剑

这次比赛时间还是很紧的，一共六道题，就给了8个小时，属实有点折磨。比赛当时出了3题，剩下3题都是有点思路做不下去，赛后看做出来的师傅wp复现了。

unknown_dsa

题目名字里有DSA，那肯定有签名的攻击，DSA常见的攻击就是复用k攻击，看题目源码，果然有

t = powmod(g, p * q - (p + q), p * q)
hm1 = bytes_to_long(SHA.new(m1).digest())
hm2 = bytes_to_long(SHA.new(m2).digest())
k = random.randint(1, q - 1)
r1 = powmod(g, k, p) % q
s1 = (hm1 + x1 * r1) * invert(k, q) % q
s2 = (hm2 + x1 * r1) * invert(k, q) % q
r2 = powmod(g, x1, p) % q
s3 = (hm1 + x2 * r2) * invert(k, q) % q

只需要知道$hm_1$和$hm_2$，就可以通过

得到k，然后随便求就结束了。所以这题的重点在如何获得$m_1,m_2$。

def main():
    for i in range(len(ul)):
        assert ul[i] ** 2 - wl[i] * vl[i] ** 2 == 1
    e = 7
    cl1 = [int(powmod(bytes_to_long(m1), e, x)) for x in ul]
    cl2 = [int(powmod(bytes_to_long(m2), e, y)) for y in vl]
    print(wl, cl1, cl2, sep=', ')

可以看到，这里明显看到有一个低公钥指数广播攻击，然后assert的方程，实际上是标准的佩尔方程，百度找一下佩尔方程的求解方法，说连分数法比枚举法速度快，那就用连分数法求解，求出来的结果直接带入广播攻击。DSA的n可以查库分解，我们就可以直接复用k攻击的方法得到flag。

from gmpy2 import *
import math
from Crypto.Hash import SHA
from Crypto.Util.number import *
ul = []
vl = []
wl, cl1, cl2 = [3912956711, 4013184893, 3260747771], [
    2852589223779928796266540600421678790889067284911682578924216186052590393595645322161563386615512475256726384365091711034449682791268994623758937752874750918200961888997082477100811025721898720783666868623498246219677221106227660895519058631965055790709130207760704,
    21115849906180139656310664607458425637670520081983248258984166026222898753505008904136688820075720411004158264138659762101873588583686473388951744733936769732617279649797085152057880233721961,
    301899179092185964785847705166950181255677272294377823045011205035318463496682788289651177635341894308537787449148199583490117059526971759804426977947952721266880757177055335088777693134693713345640206540670123872210178680306100865355059146219281124303460105424], [
                   148052450029409767056623510365366602228778431569288407577131980435074529632715014971133452626021226944632282479312378667353792117133452069972334169386837227285924011187035671874758901028719505163887789382835770664218045743465222788859258272826217869877607314144,
                   1643631850318055151946938381389671039738824953272816402371095118047179758846703070931850238668262625444826564833452294807110544441537830199752050040697440948146092723713661125309994275256,
                   10949587016016795940445976198460149258144635366996455598605244743540728764635947061037779912661207322820180541114179612916018317600403816027703391110922112311910900034442340387304006761589708943814396303183085858356961537279163175384848010568152485779372842]


def solvePell(n):
    x = int(math.sqrt(n))
    y, z, r = x, 1, x << 1
    e1, e2 = 1, 0
    f1, f2 = 0, 1
    while True:
        y = r * z - y
        z = (n - y * y) // z
        r = (x + y) // z

        e1, e2 = e2, e1 + e2 * r
        f1, f2 = f2, f1 + f2 * r

        a, b = f2 * x + e2, f2
        if a * a - n * b * b == 1:
            return a, b


for i in wl:
    x, y = solvePell(i)
    ul.append(x)
    vl.append(y)
m1 = iroot(crt(cl1, n1),7)[0]
m2 = iroot(crt(cl2, n2),7)[0]
q = 895513916279543445314258868563331268261201605181
p = 95139353880772104939870618145448234251031105153406565833029787299040378395002190438381537974853777890692924407167823818980082672873538133127131356810153012924025270883966172420658777903337576027105954119811495411149092960422055445121097259802686960288258399754185484307350305454788837702363971523085335074839
m1 = long_to_bytes(m1)
m2 = long_to_bytes(m2)
hm1 = bytes_to_long(SHA.new(m1).digest())
hm2 = bytes_to_long(SHA.new(m2).digest())
r1, s1, s2 = 498841194617327650445431051685964174399227739376, 376599166921876118994132185660203151983500670896, 187705159843973102963593151204361139335048329243
r2, s3 = 620827881415493136309071302986914844220776856282, 674735360250004315267988424435741132047607535029
x1 = inverse(r1, q) * inverse(inverse(s2, q) - inverse(s1, q), q) * (hm1 * inverse(s1, q) - hm2 * inverse(s2, q)) % q
n, h, t = 85198615386075607567070020969981777827671873654631200472078241980737834438897900146248840279191139156416537108399682874370629888207334506237040017838313558911275073904148451540255705818477581182866269413018263079858680221647341680762989080418039972704759003343616652475438155806858735982352930771244880990190318526933267455248913782297991685041187565140859, 106239950213206316301683907545763916336055243955706210944736472425965200103461421781804731678430116333702099777855279469137219165293725500887590280355973107580745212368937514070059991848948031718253804694621821734957604838125210951711527151265000736896607029198, 60132176395922896902518845244051065417143507550519860211077965501783315971109433544482411208238485135554065241864956361676878220342500208011089383751225437417049893725546176799417188875972677293680033005399883113531193705353404892141811493415079755456185858889801456386910892239869732805273879281094613329645326287205736614546311143635580051444446576104548
g = inverse(t, n)
k = inverse(s2 - s1, q) * (hm2 - hm1) % q
x2 = (s3 * k - hm1) * inverse(r2, q) % q
print(long_to_bytes(x1) + long_to_bytes(x2))

hardrsa

y是光滑数，所以直接离散对数梭，就可以得到p的方程，然后解一下就可以得到p，之后就是已知dp和p，梭就完事了。

from z3 import *
import sympy
from Crypto.Util.number import *
c1 = 78100131461872285613426244322737502147219485108799130975202429638042859488136933783498210914335741940761656137516033926418975363734194661031678516857040723532055448695928820624094400481464950181126638456234669814982411270985650209245687765595483738876975572521276963149542659187680075917322308512163904423297381635532771690434016589132876171283596320435623376283425228536157726781524870348614983116408815088257609788517986810622505961538812889953185684256469540369809863103948326444090715161351198229163190130903661874631020304481842715086104243998808382859633753938512915886223513449238733721777977175430329717970940440862059204518224126792822912141479260791232312544748301412636222498841676742208390622353022668320809201312724936862167350709823581870722831329406359010293121019764160016316259432749291142448874259446854582307626758650151607770478334719317941727680935243820313144829826081955539778570565232935463201135110049861204432285060029237229518297291679114165265808862862827211193711159152992427133176177796045981572758903474465179346029811563765283254777813433339892058322013228964103304946743888213068397672540863260883314665492088793554775674610994639537263588276076992907735153702002001005383321442974097626786699895993544581572457476437853778794888945238622869401634353220344790419326516836146140706852577748364903349138246106379954647002557091131475669295997196484548199507335421499556985949139162639560622973283109342746186994609598854386966520638338999059
y = 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839
g = 2
x = sympy.discrete_log(y,c1,g)
s = Solver()
p=Int('p')
s.add(2019*p**2 + 2020*p**3 + 2021*p**4 == 43776275628859890575232443794319298551934804213472744927022818696759188901977390266973172755658396197421139420206549889337117978597883154859965236605452518446448639813055134133587564045471804447818058571586426895800984805588363855865218690877547419152765512143095217413477343835473963637692441032136163289964756172316289469159500312630529091350636808491697553069388388303341623047737553556123142002737059936569931163197364571478509576816349348146215101250803826590694039096063858424405382950769415272111843039715632655831594224288099608827345377164375927559338153505991404973888594356664393487249819589915881178770048740)

if s.check() == sat:
    print(s.model())
p = 12131601165788024635030034921084070470053842112984866821070395281728468805072716002494427632757418621194662541766157553264889658892783635499016425528807741
dp = 379476973158146550831004952747643994439940435656483772269013081580532539640189020020958796514224150837680366977747272291881285391919167077726836326564473
c = 57248258945927387673579467348106118747034381190703777861409527336272914559699490353325906672956273559867941402281438670652710909532261303394045079629146156340801932254839021574139943933451924062888426726353230757284582863993227592703323133265180414382062132580526658205716218046366247653881764658891315592607194355733209493239611216193118424602510964102026998674323685134796018596817393268106583737153516632969041693280725297929277751136040546830230533898514659714717213371619853137272515967067008805521051613107141555788516894223654851277785393355178114230929014037436770678131148140398384394716456450269539065009396311996040422853740049508500540281488171285233445744799680022307180452210793913614131646875949698079917313572873073033804639877699884489290120302696697425
d = dp%(p-1)
m = pow(c,d,p)
print(long_to_bytes(m))

密码⼈集合

数独题，把每个字符从1-9编个号，找个在线解数独的网站就行。

FilterRandom

import random
from secret import init1,init2,flag
assert flag==b'DASCTF{%d-%d}'%(init1,init2)
 
class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**length-1
 
    def next(self):
        nextdata = (self.init << 1) & self.lengthmask 
        i = self.init & self.mask & self.lengthmask 
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output
 
def my_filter(c1,c2):
    if random.random()>0.1:
        return str(c1)
    else:
        return str(c2)
 
N=64
mask1=random.getrandbits(N)
mask2=random.getrandbits(N)
print(mask1)
print(mask2)
l1=lfsr(init1,mask1,N)
l2=lfsr(init2,mask2,N)
output=''
for i in range(2048):
    output+=my_filter(l1.next(),l2.next())
print(output)
'''
17638491756192425134
14623996511862197922
10001011010100011000100101001011100010110111001100001110000111011011100101101101000111101100010111100011000011111111010101111100101010101100010100000111011010011110111000100000101100101010110100111100011000101010101011011111011011000001101001011000010000011110001111001111011100110011111111101000111101001010000110001110111101001001101011101101001010001101010010110000000000001001101100101011110011010110011010110110011001001111001010100011110111100100010110111100110010000000010010011110001100000011000001110001000000010000100100101100000011100000011110101001011010011010100001101000010100100000011001011001000110000000000111011101000110010110111110010101110010001010001111111000011010000011001110111001000010011000000111010111100000100010011001111101110110100100011111000111000011111101010010110011111100010000100101011000001010101111101111001000011101111000111000101011010111100110001011011100101001010110110110110011100100111100110001101110010100010111100000110000010110100010001100011011001100100110101110010100011101110110010000010011100000011100000101010011011111110000100000010001010111011011111110100111100011100011110110010001011101111001011101010110111001001000111001001111001111110111111100001111100100110011111110110101000011010111110010001100000111100010011100011010000101010111010101101000011001110011000000110110110001101100110101110010010111011100110101000110000011001010100000110000000001110010001010001001101111100001111111011010010011100110010000111010001001111111110000010101110011010100100101101100111000010110100110010001010110111110011000111011101110100010000110110110011001011111011111000000000000001110000001000011000110111000000110100110110001111011111100010010011100101010000111000011111010000001010010011101010010110011000000001111110000000010111011000010001111000100110101110001000011111001101111111100011111011001001110000101001101110100111010011011101000110010000001001000001100110001110101100001000110100100010111101100010100110011111010011100100001101111010000110110101111111001111011100001101100000001101111100100
'''

题面如上，这题的难点在于my_filter这个函数，自己调试一下可以发现，2048个里面大约有1850个是l1生成的。那么应该存在连续64个输出都来自于l1。也就是知道lfsr的一个状态，那么可以逆lfsr回到初态，再利用初态生成输出流，若与题目中输出流相符程度很大，则可以认为此时的初态是正确的。

尽管每次只输出一个比特，但是l1，l2都在递推，所以我们把其中不符合的取出来，就得到l2生成的不连续的结果，此时需要使用lfsr的矩阵形式把初始状态逆出来。对于lfsr两个相邻状态，写做如下形式

掩码矩阵

于是就有$A_{i-1}M=A_i$，那么可以得到任意状态与最初态的关系$A_0=\begin{pmatrix}a_0&a_1&a_2&\cdots&a_{n-1}\end{pmatrix}$，即为：$A_0M^{i}=A_i$。

这是对于连续输出的情况，对于不连续的，设掩码向量$m=\begin{pmatrix}c_{n-1}&c_{n-2}&\cdots&c_0\end{pmatrix}^T$,对$A_0M^{i}=A_{i}$，两边同时右乘掩码向量$M$，那么$A_0M^{i}m=A_{i}m=a_i$，记$B_i=M^{i}m$。那么一系列列向量组成的矩阵$B=[B_i,B_{i+k_1},...,B_{i+k_n}]$。记不连续输出$C=[a_i,a_{i+k_1},...a_{i+k_n}]$。那么$A_0B=C$，由此$B,C$都已知，通过解方程可以得到初态行向量。

class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2 ** length - 1

    def next(self):
        nextdata = (self.init << 1) & self.lengthmask
        i = self.init & self.mask & self.lengthmask
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output


def backtrace(state, mask):
    mask = ((mask & 0x7FFFFFFFFFFFFFFF) << 1) + 1
    i = state & mask
    outPut = 0
    while i != 0:
        outPut ^= (i & 1)
        i = i >> 1
    state >>= 1
    return (outPut << 63) + state


mask1 = 17638491756192425134
mask2 = 14623996511862197922
output = "10001011010100011000100101001011100010110111001100001110000111011011100101101101000111101100010111100011000011111111010101111100101010101100010100000111011010011110111000100000101100101010110100111100011000101010101011011111011011000001101001011000010000011110001111001111011100110011111111101000111101001010000110001110111101001001101011101101001010001101010010110000000000001001101100101011110011010110011010110110011001001111001010100011110111100100010110111100110010000000010010011110001100000011000001110001000000010000100100101100000011100000011110101001011010011010100001101000010100100000011001011001000110000000000111011101000110010110111110010101110010001010001111111000011010000011001110111001000010011000000111010111100000100010011001111101110110100100011111000111000011111101010010110011111100010000100101011000001010101111101111001000011101111000111000101011010111100110001011011100101001010110110110110011100100111100110001101110010100010111100000110000010110100010001100011011001100100110101110010100011101110110010000010011100000011100000101010011011111110000100000010001010111011011111110100111100011100011110110010001011101111001011101010110111001001000111001001111001111110111111100001111100100110011111110110101000011010111110010001100000111100010011100011010000101010111010101101000011001110011000000110110110001101100110101110010010111011100110101000110000011001010100000110000000001110010001010001001101111100001111111011010010011100110010000111010001001111111110000010101110011010100100101101100111000010110100110010001010110111110011000111011101110100010000110110110011001011111011111000000000000001110000001000011000110111000000110100110110001111011111100010010011100101010000111000011111010000001010010011101010010110011000000001111110000000010111011000010001111000100110101110001000011111001101111111100011111011001001110000101001101110100111010011011101000110010000001001000001100110001110101100001000110100100010111101100010100110011111010011100100001101111010000110110101111111001111011100001101100000001101111100100"
ratio = 0
init1 = 0
index = 0
for i in range(1984):
    tmp = int(output[i:i + 64], 2)
    count = 0

    for _ in range(i+64):
        tmp = backtrace(tmp, mask1)
    l1 = lfsr(tmp, mask1, 64)

    for j in range(2048):
        if l1.next() == int(output[j]):
            count += 1
    if count/2048 > ratio:
        ratio = count/2048
        init1 = tmp
        index = i
print(init1, ratio, index)
index = []
output2 = []
l1 = lfsr(init1, mask1, 64)
for i in range(2048):
    if l1.next() != int(output[i]):
        output2.append(int(output[i]))
        index.append(i)
print(index)
print(output2)

两段分开跑，上面的代码因为sagemath对于 ^ 符号解析为指数，所以会有问题

index=[4, 12, 30, 37, 41, 53, 69, 85, 97, 101, 146, 148, 193, 196, 260, 281, 341, 357, 390, 407, 428, 431, 438, 477, 520, 523, 529, 539, 541, 566, 607, 613, 619, 623, 640, 660, 733, 750, 811, 816, 824, 873, 887, 906, 910, 939, 948, 959, 971, 977, 1001, 1026, 1030, 1046, 1052, 1078, 1082, 1109, 1120, 1126, 1137, 1158, 1163, 1194]
output2=[1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0]
M=[]
mask2 = 14623996511862197922
mask = mask2.digits(2)[::-1]
for i in range(64):
    M.append([0]*64)
    M[i][i-1] = 1
    M[i][-1] = mask[i]
mask = matrix(Zmod(2), mask).T
M=matrix(Zmod(2), M)
A = []
index=index[:64]
output2=output2[:64]
for i in index:
    A.append((M^i*mask).list())
A =matrix(Zmod(2), A).T
C = vector(Zmod(2), output2)
init2=A.solve_left(C).list()
print(int(''.join([str(i) for i in init2]),2))

参考：非线性移位寄存器 - Hello World - Just So So ... (zbc53.top)

2021年西湖论剑线上赛 SU Write-up | TEAM-SU

SpecialCurve2

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


def add(P1, P2):
    x1, y1 = P1
    x2, y2 = P2
    x3 = (x1 * x2 - y1 * y2) % n
    y3 = (x1 * y2 + x2 * y1) % n
    return (x3, y3)


def mul(P, k):
    assert k >= 0
    Q = (1, 0)
    while k > 0:
        if k % 2:
            k -= 1
            Q = add(P, Q)
        else:
            k //= 2
            P = add(P, P)
    return Q


def getMyPrime():
    while True:
        q = getPrime(88)
        p = 2 * q + 1
        if isPrime(p):
            return p


e = getPrime(256)
n = getMyPrime() * getMyPrime() * getMyPrime()
print('n=%d' % n)

G = (1, 1)
HINT = mul(G, e)
print('HINT=%s' % str(HINT))

x = bytes_to_long(flag[7:39])
y = bytes_to_long(flag[39:-1])
M = (x, y)
C = mul(M, e)
print('C=%s' % str(C))
'''
n=92916331959725072239888159454032910975918656644816711315436128106147081837990823
HINT=(1225348982571480649501200428324593233958863708041772597837722864848672736148168, 1225348982571480649501200428324593233958863708041772597837722864848672736148168)
C=(44449540438169324776115009805536158060439126505148790545560105884100348391877176, 73284708680726118305136396988078557189299357177640330968917927635171441710392723)
'''

看这题的坐标公式，不难联想到三角函数的加法公式，横坐标是cos加法，纵坐标是sin加法。可以想到把这两个点映射到极坐标，形式如下

那么点加法就变成了如下形式

可以联想到复数乘法，复数乘法便是模相乘、角相加。直角坐标系下的复数乘法的横坐标和纵坐标便也是满足上面的公式，所以这个问题就是基于模n意义下的复数乘法所构成的群。

然后这题n可以拆成$p,q,r$，我们只需要在这些子群下求解离散对数，然后CRT组合即可。具体证明在下面的链接里，春哥yyds，模p复数乘法群的阶性质 暨 西湖论剑 SpecialCurve2 writeup - 知乎 (zhihu.com)

我们需要知道的是，在复数群里，p的阶是$p^2-1$​。这题的另一个难点是求e，对于复数来说一般取模长从而对其指数运算：

现在我们已知$z_1,z_n$，只需要用离散对数求e即可，这里我比赛的时候并不知道怎么调用函数，看了几位爹的wp才稍微了解一点。求出来e，这题就没有难度了。

from Crypto.Util.number import *
n=92916331959725072239888159454032910975918656644816711315436128106147081837990823
HINT=(1225348982571480649501200428324593233958863708041772597837722864848672736148168, 1225348982571480649501200428324593233958863708041772597837722864848672736148168)
C=(44449540438169324776115009805536158060439126505148790545560105884100348391877176, 73284708680726118305136396988078557189299357177640330968917927635171441710392723)

p = 425886199617876462796191899
q = 502327221194518528553936039
r = 434321947632744071481092243

def addsqr(x, y):
    return x^2+y^2
def add(P1, P2):
    x1, y1 = P1
    x2, y2 = P2
    x3 = (x1 * x2 - y1 * y2) % n
    y3 = (x1 * y2 + x2 * y1) % n
    return (x3, y3)
def mul(P, k):
    assert k >= 0
    Q = (1, 0)
    while k > 0:
        if k % 2:
            k -= 1
            Q = add(P, Q)
        else:
            k //= 2
            P = add(P, P)
    return Q
g = addsqr(1, 1)
h2 = addsqr(*HINT)

h2p = Zmod(p)(h2)
gp = Zmod(p)(g)
e1 = h2p.log(gp)

h2p = Zmod(q)(h2)
gp = Zmod(q)(g)
e2 = h2p.log(gp)

h2p = Zmod(r)(h2)
gp = Zmod(r)(g)
e3 = h2p.log(gp)


e = crt([e1, e2, e3], [p-1, q-1, r-1])
print(e)

print(pow(g, e, n))
print(h2 % n)

d = inverse(e, (p^2-1)*(q^2-1)*(r^2-1))

M = mul(C, d)

print(M)
print(long_to_bytes(M[0]))
print(long_to_bytes(M[1]))