2月和3月总结笔记

Some wp

[hgame2021week2]signin

from libnum import *
from Crypto.Util import number

from secret import FLAG

m = s2n(FLAG)
a = number.getPrime(1024)
p = number.getPrime(1024)

c = a ** p * m % p

print("a = {}".format(a))
print("p = {}".format(p))
print("c = {}".format(c))
# a = 114860703441277641159010520457158779743406545528920568790985108964161284695646120202566466577905632104388633713510921541107712064183498148484917830523711193223293589592121551112550440675243616576203905342750212598333519257633313008795211410775228583376590610854565937051450960491199274401879127456639254354787
# p = 128337372863548733982628567035170003526593417952180525194192159178242702197521429086326104838106948416844886788242477807248072299082097134981718011660755395525206183882787666600218259021191537486566977688094471407299627161423853728124784268632944908474596463076060977522841693595025422665925345726268832156411
# c = 89307609447045247940453313245387079059195320809034029001135691327604934287433876029928261397471393214500935563825104638091048695922698852839685381899565313007469197828666213834055492744237102478143542837196793018354189910673128014928309895806759030851721114111420175990080693470002656332421701173726269842336

费马小定理:

$ a ^ {p} \equiv a\left(\bmod p\right) $

$$
\therefore c = \left(a * m\right) \bmod p
$$

设 ni 为 a mod p的逆元

两边同时乘ni，得
$$
m = (c * ni)\bmod p
$$
已知c,ni,p，可以求得m

from libnum import *
from gmpy2 import *
a = 114860703441277641159010520457158779743406545528920568790985108964161284695646120202566466577905632104388633713510921541107712064183498148484917830523711193223293589592121551112550440675243616576203905342750212598333519257633313008795211410775228583376590610854565937051450960491199274401879127456639254354787
p = 128337372863548733982628567035170003526593417952180525194192159178242702197521429086326104838106948416844886788242477807248072299082097134981718011660755395525206183882787666600218259021191537486566977688094471407299627161423853728124784268632944908474596463076060977522841693595025422665925345726268832156411
c = 89307609447045247940453313245387079059195320809034029001135691327604934287433876029928261397471393214500935563825104638091048695922698852839685381899565313007469197828666213834055492744237102478143542837196793018354189910673128014928309895806759030851721114111420175990080693470002656332421701173726269842336
ni = invert(a, p)
m = c * ni % p 
print n2s(m)
# hgame{M0du1@r_m4th+1s^th3~ba5is-Of=cRypt0!!}

Common Private Exponent（共私钥指数攻击，d相同）

# sage
from gmpy2 import *
from libnum import *
e0=
n0=
c0=
e1=
n1=
c1=
e2=
n2=
c2=

M=iroot(int(n2),int(2))[0]
a=[0]*4
a[0]=[M,e0,e1,e2]
a[1]=[0,-n0,0,0]
a[2]=[0,0,-n1,0]
a[3]=[0,0,0,-n2]

Mat = matrix(ZZ,a)
Mat_LLL=Mat.LLL()
d = abs(Mat_LLL[0][0])/M
print(n2s(pow(c1, d, n1)))

[NCTF2019]babyRSA

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

def nextPrime(n):
    n += 2 if n & 1 else 1
    while not isPrime(n):
        n += 2
    return n

p = getPrime(1024)
q = nextPrime(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(bytes_to_long(flag.encode()), e, n)

# d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
# c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804

已知
$$
e，d，c，q = nextprime(p)
$$

$$
(e*d-1)=k * (q-1)*(p-1)
$$

p,q接近，p*q为2048位

(e*d-1)是2064位的，所以k的取值范围为（pow(2,15),pow(2,16)）

通过爆破k的值，可以得到(p-1)*(q-1) 的值，对phi 开平方，进而求得p,q。

from gmpy2 import*
from sympy import* 
from libnum import*
e = 0x10001
d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
for k in range(pow(2,15),pow(2,16)):
    if (e*d-1)%k == 0:
        phi = (e*d-1)//k
        P1 = iroot(phi,2)[0]    #  对(q-1)*(p-1)开平方        
        p = nextprime(P1)     # 获取素数P        
        q_1 = phi//(p-1)      # 得到(q-1)        
        q = q_1+1
        if(isprime(q)):       # 对q进行素性检测
                   break            
print(p,q)
p=143193611591752210918770476402384783351740028841763223236102885221839966637073188462808195974548579833368313904083095786906479416347681923731100260359652426441593107755892485944809419189348311956308456459523437459969713060653432909873986596042482699670451716296743727525586437248462432327423361080811225076497
q=143193611591752210918770476402384783351740028841763223236102885221839966637073188462808195974548579833368313904083095786906479416347681923731100260359652426441593107755892485944809419189348311956308456459523437459969713060653432909873986596042482699670451716296743727525586437248462432327423361080811225075839
n=p*q
m = pow(c,d,n)
print(n2s(m))

[DiceCTF2021]newcrypt v2

#!/usr/bin/env python3

from Crypto.Util.number import *

flag = open('flag.txt','rb').read()

class Generator:
    def __init__(self,bits):
        self.p = getPrime(bits)
        self.q = getPrime(bits)
        self.N = self.p*self.q
        print(self.N)

    def gen(self):
        numbers = []
        for round in range(5):
            x = getRandomNBitInteger(1<<10)
            while x%2 != 1 or GCD(x,(self.p-1)*(self.q-1)) != 1:
                x = getRandomNBitInteger(1<<10)
            y = inverse(x,(self.p-1)*(self.q-1))
            numbers.append(y)
        print(numbers)

    def encrypt(self,m):
        return pow(m,0x1337,self.N)

g = Generator(1024)
g.gen()
m = bytes_to_long(flag)
print(g.encrypt(m))

只有一解，大佬的exp也没太看懂，之后有空再研究（好像又用到coppersmith了

已知n，e，c，和几组由随机的D生成的E，这几组E只给phin有关系，所以要通过这几组E求出p和q，就能求得d了。

# sage
import itertools
from sympy.solvers.diophantine.diophantine import diop_linear
from sympy import symbols

def getPolyInfo(poly):
    HM = poly.monomials()[0]            # HM: head monomial
    HC = poly.monomial_coefficient(HM)  # HC: head coefficient
    HT = HC*HM                          # HT: head term
    HI = poly.exponents()[0]            # HI: head index
    return {'HT':HT,'HC':HC,'HM':HM,'HI':HI}

# https://eprint.iacr.org/2012/675.pdf
def multivariate(N,E,beta,m,improve=False):

    # Setup multivariate simultaneous equations
    l = len(E)
    P,x = PolynomialRing(ZZ,l+1,'x').objgens() # y = x[-1]
    F = []
    for k in range(l):
        F.append((-1+x[k]*(x[-1]+N)))
    X = [floor(N^beta) for _ in range(l)] + [floor(3*N^.5)] # upper bounds

    # Construct polynomials: G
    G = []
    I = []
    for k in range(l):
        g = {}
        i_k = []
        for i in range(m+1):
            for j in range(i+1):
                g[i,j] = x[k]^(i-j) * F[k]^j * E[k]^(m-j)

                # check HM,HI
                polyinfo = getPolyInfo(g[i,j])
                assert polyinfo['HM'] == x[k]^i * x[-1]^j
                assert tuple(polyinfo['HI']) == tuple([i if (_ == k) else j if(_ == l) else 0 for _ in range(l+1)])
                i_k.append(tuple(polyinfo['HI']))
        G.append(g)
        I.append(i_k)

    # Get index set I+
    I_plus = set()
    for i in itertools.product(*I):
        I_plus.add(tuple([sum(i[k][j] for k in range(len(i))) for j in range(l+1)]))
    I_plus = sorted(I_plus)

    if improve:
        # Get index set I++
        I_pp = set()
        for idx in I_plus:
            if idx[-1] <= max(idx[:l]) or .5*idx[-1] + sum(idx[:l])*beta - sum(min(idx[k],idx[-1]) for k in range(l)) < 0:
                I_pp.add(idx)
        I_pp = sorted(I_pp)
        I_plus = I_pp

    # Construct polynomials: G+
    G_plus = []
    for idx in I_plus:
        J = []
        for j_tuples in itertools.product(range(idx[-1]+1),repeat=l):
            if sum(j_tuples) == idx[-1] and not any([idx[k] < j_tuples[k] for k in range(l)]):
                J.append(j_tuples)

        # Find GCD(HC)
        gcdn = -1
        for j in J:
            polyinfo = getPolyInfo(prod(G[k][idx[k],j[k]] for k in range(l)))
            gcdn = polyinfo['HC'] if (gcdn == -1) else gcd(gcdn,polyinfo['HC'])

        if len(J) > 1:
            arr = [getPolyInfo(prod(G[k][idx[k],J[j][k]] for k in range(l)))['HC'] for j in range(len(J))]
            sols = diop_linear(sum(arr[t]*x0 for t,x0 in enumerate(symbols("x0:%d"%len(J),integer=True)))-gcdn)
            a = [int(expr.subs({t:0 for t in sols[-1].free_symbols})) for expr in sols]
            assert sum(arr[t]*a[t] for t in range(len(J))) == gcdn
            poly = sum(a[j] * prod(G[k][idx[k],J[j][k]] for k in range(l)) for j in range(len(J)))
        else:
            poly = sum(prod(G[k][idx[k],j[k]] for k in range(l)) for j in J)

        # check HM
        for j in J:
            polyinfo = getPolyInfo(prod(G[k][idx[k],j[k]] for k in range(l)))
            assert polyinfo['HM'] == prod(x[k]^idx[k] for k in range(l+1))

        g_poly = poly.subs({x[i]:x[i]*X[i] for i in range(l+1)})
        G_plus.append(g_poly)

    # Get monomials
    monomials = set()
    for poly in G_plus:
        for m1 in poly.monomials():
            monomials.add(m1)
    monomials = sorted(monomials) # sort monomials

    # Setup matrix for LLL
    assert len(G_plus) == len(monomials)
    print("Matrix dimensions: {}x{}".format(len(G_plus),len(monomials)))
    L = Matrix(ZZ,len(G_plus),len(monomials))
    for i,poly in enumerate(G_plus):
        for j,m1 in enumerate(monomials):
            L[i,j] = poly.monomial_coefficient(m1)

    L = L.LLL()
    
    # Get system of polynomials
    H = [0 for _ in range(L.nrows())]
    for i in range(L.nrows()):
        for j,m1 in enumerate(monomials):
            H[i] += P(m1 * L[i,j] / m1.subs({x[k]:X[k] for k in range(l+1)}))

    # Find roots using Groebner basis
    H = [eq.change_ring(QQ) for eq in H]
    I = Ideal(*H[0:l+2])
    g = I.groebner_basis('giac')
    if g == [1]:
        return (0,0)
    x0 = var('x',n=l+1)
    sols = solve([eq(x0) for eq in g],x0,solution_dict=True)
    for s in sols:
        if [s[i].is_integer() for i in x0] == [True]*(l+1):
            p_plus_q = 1-s[x0[-1]]
            x1 = PolynomialRing(ZZ,'x').gen()
            f = x1**2 - p_plus_q*x1 + N
            roots = f.roots()
            p,q = roots[0][0],roots[1][0]
            return (p,q)
    return (0,0)

def test(l,n,beta,m,improve=False):
    '''
    l: number of RSA keys
    n: RSA bit length
    beta: ratio of secret keys to n
    '''
    p = random_prime(2^floor(n/2)-1,lbound=2^(floor(n/2)-1))
    q = random_prime(2^floor(n/2)-1,lbound=2^(floor(n/2)-1))
    N = p*q
    d_arr = []
    e_arr = []
    while True:
        d = getrandbits(floor(beta*n))
        if d%2 != 1 or gcd(d,(p-1)*(q-1)) != 1:
            continue
        d_arr.append(d)
        e = inverse_mod(d,(p-1)*(q-1))
        e_arr.append(e)
        if len(d_arr) == l:
            break
    print("N=pxq: {} = {} x {}".format(N,p,q))
    print("E:",e_arr)
    assert set(multivariate(N,e_arr,beta,m,improve=improve)) == set((p,q))
    print("Recovered successfully!")

# Tests
# test(2,2048,.4,3)
# test(3,1024,.46,2)
# test(4,2048,.465,1,True)
# test(5,2048,.5,1,True)

N = 14337596625981852268356733199577363454740211423306675087406912203612106754740920535831186446286722686623181504391319837160175722628785779086065934404508907495375575604993274597567269696998989342554512169936041805398614285019559611603192791406141673196062487187176974406170426326985080300401992871878272750861304966084697316255932229517848590059063403143320068885919541934394285204068719613486701354616465507009243987608727662705537132041395688365562715140968368814327462123434153164039701357637150078015089287814859891259359522535418157646847992980552057214329745061692026530855072281235664669710276172313808317219377
E = [12976676506376070110040406570149996101394527411415881605860843983349363069127746407886818103004002117366801754683449911816105354951654828869006253634088640931647307722477393307231188093852730642851927610384508472618758673499740002362888463449907850898256709493427721244039346744775543365490896192997672156351539772375297375865701816236826858372370828737647663910668758559951734259138880399000934641709724370982987684871113999721232035923836779554293705654708805788634929466224221204317582909006400475748926200070330888314906329563110519417492641071166678480550894995905707586159556311266401315984011972916692724662007, 1863763332200533355187495032998617435554266559806936864499583761336209979224578994667995146126874905256288657356393344293005098598793270446199080399410824354463753330703855276639236442323809498935079594864731622806981650099779625802394492866772783164556122039084479891630004937148495825596230840040565205548593767270423848984375003632523408070963142589587241988428801951874519861970126281101472254516564569333579422627371073253518765484477877683153600580032505599620122184765699186189626337136723831818155748441783703710300026814764444157324740641952652611754903513683898296023658398333790727757433569553518827781081, 2266107108355028257265149613659513002904527665415922083354756255551387373798380715368636460529830761909106090742940804896135018713646665813103359939678904950388594536893820576541648929534374197197699236090310478668004566290689920782095321065479404918697144906086349325096417620451929567373057958837794405051832027393710209669487434964110954150175622748681581358286557194922971711892121496052503670245966738246893335673371911853174980221559458430193451035071192245185753464656500832472716390638460484671724823329824542466725661315185971990283547100285181536347175215757494437839674240264046716971285767053511953014531, 3012665180743215926044185696769375844027893756273454464899436474243670235496407935713055380725328632598984826511997157495169513834153639995899362029217480834870286205900296318828132585598137285805346657507373383217564586845718076975940327895945639149538433468219499891765910172868182009270172797753293191815210844128651385425158004075468732463275400326825588500413826705324683883847629057842100412354271506810539904381290499384122685388561018876503682490390411350939677572500607680288271353610724980926630513275655559323486108263101876350397264023226898671971480444539423455934221932088753929657082051926857943772249, 11654698355361642253478315394509778991884549939645189298025844618346681492919905598771246194066168408610846920719586231628616008528010499420499104967297209036853716237681916872940149475834811605883772954478356917401690932414133714754145102545282932055458620466374791600444965981474694964466374906501557735419193196210081985354200587280684723865152043847523132554069361865253297610018545961901224789197822102327845824463263202308386229169765022168048658546459296356873527223601643713792899944747399360948976054350376734975776305888045491739605171010206699460442078038128020076159311221789613452312845058576145149846029]
c = 3956820731464413675248976184330090386023400385276540416612412624089512558297526443036270899672623474843471114663110309683900437072074275592048007465581536399064139915757208597226420873829762312175028263779702542540471556091196109301321307501425411404463271934422940357892918540470499135323435236378549758184835624591770086862646876844851191370941059743180644939927085439332975325190261804739679687807083505313731296227816013191899297272702691347829966232657275540293776915188791505265719622572712788357792237668230216117983278509746622406227163590935715374994406994094600128249001135177407180401006889949317057904629
p,q = multivariate(N,E,.5,1,True)
print(p,q)
assert p*q == N
phi = (p-1)*(q-1)
d = pow(0x1337,-1,phi)
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(pow(c,d,N)))

[VNCTF2021]strange_function

from Crypto.Util.number import *
from hashlib import sha256
from secret import flag
import socketserver
import signal
import string
import random
import os

MENU = br'''[+] 1.function
[+] 2.check_answer
[+] 3.exit
'''

class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'[-] '):
        self.send(prompt, newline=False)
        return self._recvall()

    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
        _hexdigest = sha256(proof.encode()).hexdigest()
        self.send(f"[+] sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        x = self.recv(prompt=b'[+] Plz tell me XXXX: ')
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    def function(self, x):
        res = 0
        for i in range(self.lenth):
            numerator = ord(self.token[i])
            denominator = x - self.data[i]
            try:
                tmp = numerator / denominator
            except Exception as e:
                self.send(b'[+] Error!')
                return
            res += tmp
        return res

    def handle(self):
        signal.alarm(1000)
        if not self.proof_of_work():
            return
            
        self.send(b'[+] Welcome!')
        self.send(b'[+] Can you find the flag through the calculating?')

        self.score = 0
        self.token = ''.join(random.sample(string.ascii_letters + string.digits, 8))
        self.lenth = len(self.token)
        self.data = []
        for i in range(self.lenth):
            self.data.append(getRandomInteger(17))
        self.send(str(self.data).encode())

        while True:
            self.send(MENU, newline=False)
            choice = self.recv()
            if(choice == b'1'):
                self.send(b"[+] Plz give me your x: ")
                now = int(self.recv().strip().decode())
                now = self.function(now)
                self.send(("[+] let me show you the answer: "+str(now)).encode())
            elif(choice == b'2'):
                guess = self.recv().strip().decode()
                if(guess == self.token):
                    self.score += 1
                    self.send(b"[+] You win!")
                    self.send(("[!] Now your score: " + str(self.score)).encode())

                    self.token = ''.join([random.choice(string.digits + string.ascii_letters) for i in range((self.score+1)*8)])
                    self.lenth = len(self.token)
                    self.data = []
                    for i in range(self.lenth):
                        self.data.append(getRandomInteger(17))
                    self.send(str(self.data).encode())
                    
                    if(self.score >= 5):
                        self.send(flag.encode())
                else:
                    self.send(b'[+] What do you want to say???')
                    self.send(b'[!] Go away!')
                    break
            else:
                break

        self.request.close()

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10002
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

主要逻辑如下：

即每次反馈给我们的res等于token[i]/(x-data[i])的和

x是我们输入的数，每次输入data[i]+1，后面的每项分母很大，极限约等于0，所以每次的res都约等于token[i]

[NepCTF2021]Real_Base

#py2
import string
import random
from secret import flag,b_char

def encode(s):
    res=''
    binstr=[ bin(ord(s[i])).replace('0b','').zfill(8) for i in range(len(s))]
    p1=len(binstr) // 3
    p2=len(binstr) % 3
    part1 = binstr[0:3*p1]
    
    for i in range(p1):
        str_p1=binstr[i*3]+binstr[i*3+1]+binstr[i*3+2]
        tmp_str = [str_p1[x: x + 6] for x in [0, 6, 12, 18]]
        tmp_res = [b_char[int(x,2)]for x in tmp_str]
        res+=''.join(tmp_res)

    if p2:
        part2 = binstr[3*p1:]
        str_p2 = ''.join(part2)+(3-p2)*'0'*8
        tmp_str = [str_p2[x: x + 6] for x in [0, 6, 12, 18]][:p2+1]
        tmp_res = [b_char[int(x,2)]for x in tmp_str]
        res+=''.join(tmp_res)
        res +='='*(3-p2)
    return res
 
m1=random.sample(list(b_char),50)
print ''.join(m1)
print encode(m1)
print encode(flag)
# rTcb1BR8YVW2EOUjweXpIiLt5QCNg7ZAsD9muq3ylMhvofnx/P
# 2Br9y9fcu97zvB2OruZv0D3Bwhbj0uNQnvfdtC2TwAfPrdBJ3xeP4wNn0hzLzCVUlRa=
# tCvM4R3TzvZ7nhjBxSiNyxmP28e7qCjVxQn91SRM3gBKzxQ=

b_char = ‘abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ+/‘

base64变种，编码过程是每个转成八位二进制数之后，每六位切片，二进制转十进制对应到表上的位置，最后补位。所以我们解码就可以先把每个字符根据表上的位置全部转成六位二进制数，然后八个一组切片，转成十进制，ASCII码转字符。

s = 'tCvM4R3TzvZ7nhjBxSiNyxmP28e7qCjVxQn91SRM3gBKzxQ='
# b = ''
# for i in s:
#     for j in range(len(b_char)):
#         if i == b_char[j]:
#             b += str(bin(j)).replace('0b', '').zfill(6)
            # print b
# print b
b = '0100111001100101011100000111101101010111011101110110010101011111011000010011010001110010011001010101111101100010001100010110000101110011001100110111001000100001001000010100001001100010011110010101111101000011011000110110111101101101011100000111010001101001011011100110010101111101' #去掉末尾两个0
flag = ''
for i in range(0, len(b), 8):
    flag += chr(int(b[i: i+8], 2))
print flag

[NepCTF2021]easyEncryption

from Crypto.Cipher import AES
from random import randrange
from random import shuffle
from secret import flag1, flag2
import string
from hashlib import md5


ALPHABET = string.hexdigits[:-6]
ALPHABET_ALL = string.ascii_lowercase + \
    string.ascii_uppercase + string.digits


def plus(num1, num2):
    res = 0
    for i in range(4):
        tmp = (((num1 & 1) + (num2 & 1)) % 2)
        tmp = tmp << i
        res += tmp
        num1 >>= 1
        num2 >>= 1
    return res


def encrypt(msg, key, s):
    c = ''
    for i in msg:
        c_i = key[plus(key.index(i), s)]
        c += c_i
        s = key.index(i)
    return c


k = list(ALPHABET)
shuffle(k)
k = 'ca038b6194df72e5'

m = b'Welcome to NepCTF. I have a message for you '.hex() + flag1.hex()
cipher = encrypt(m, k, 7)
print(cipher)
# 93d4466bb2277405eb5265f1943efd76c5f335fab5800afdc4058ad587743555baadd4058cc21ac5e8e2130580043af40ac5e5e8e2133ac58cc66aad5880758cc66aadc46a85dcbbcee8a555dccbccc47cbf

# kk = []
# kk.append(k)
# while len(kk) < 500:
#     tmp_k = list(ALPHABET)
#     shuffle(tmp_k)
#     if encrypt(m, tmp_k, 7) == cipher:
#         kk.append(tmp_k)

kk = eval(open('22', 'r').read())


f = open('out.txt', 'w')

for k in kk:
    iv = b'i\xfd\xd1\xb9\x81U\x87\xde\xdbB\x9b\x1b\x14|\x97\x14'
    secret2 = flag2 + b'\x00' * (16 - (len(flag2) % 16))

    m = b"Hope you enjoy NepCtf"
    m = m + b"\x00" * (16 - (len(m) % 16))

    AES_keys = []
    for i in range(4):
        prefix = ALPHABET_ALL[randrange(0, len(ALPHABET_ALL))] + \
            ALPHABET_ALL[randrange(0, len(ALPHABET_ALL))]
        AES_keys.append(prefix.encode() + ''.join(k).encode() + b'\x00' * 6)

    for subkey in AES_keys:
        cipher = AES.new(subkey, AES.MODE_CBC, IV=iv)
        secret2 = cipher.encrypt(secret2)

    for subkey in AES_keys:
        cipher = AES.new(subkey, AES.MODE_CBC, IV=iv)
        m = cipher.encrypt(m)

    f.write(str((bytes.hex(secret2), bytes.hex(m), md5(
        ''.join(k).encode()).hexdigest())) + '\n')

求解第一部分的flag1很简单，通过找规律发现plus函数的逆运算还是plus

def plus(num1, num2):
    res = 0
    for i in range(4):
        tmp = (((num1 & 1) + (num2 & 1)) % 2)
        tmp = tmp << i
        res += tmp
        num1 >>= 1
        num2 >>= 1
    return res
key = 'ca038b6194df72e5'
s = 7
flag = '93d4466bb2277405eb5265f1943efd76c5f335fab5800afdc4058ad587743555baadd4058cc21ac5e8e2130580043af40ac5e5e8e2133ac58cc66aad5880758cc66aadc46a85dcbbcee8a555dccbccc47cbf'
flag1 = ''
for i in flag:
    c_i = key[plus(key.index(i), s)]
    flag1 += c_i
    s = key.index(c_i) # 这里特别要注意一下，不是i而是c_i
print(bytes.fromhex(flag1))
# b"Welcome to NepCTF. I have a message for you here's your flag1: flag{0d3c21dd36fe3b"

第二部分的flag2，遍历所有的AESKEY以及用这些key生成明文加密两次和密文解密两次的两个list，用set和&来找交集，并且找到这个交集使用了哪四个key，最后用这四个key解密即可。

from tqdm import tqdm
import string
from Crypto.Cipher import AES
def jiami(s, k):
    cipher = AES.new(k, AES.MODE_CBC, IV=iv)
    return cipher.encrypt(s)
def jiemi(s, k):
    cipher = AES.new(k, AES.MODE_CBC, IV=iv)
    return cipher.decrypt(s)
ALPHABET_ALL = string.ascii_lowercase + string.ascii_uppercase + string.digits
cipher = bytes.fromhex('26bd5910dfb1a236a7ca20650eb9ea3d846d1baacde9591cfdf28c852e16ddf6')
m = b"Hope you enjoy NepCtf"
m = m + b"\x00" * (16 - (len(m) % 16))
iv = b'i\xfd\xd1\xb9\x81U\x87\xde\xdbB\x9b\x1b\x14|\x97\x14'
k = 'ca038b6194df72e5'
list1 = []
list2 = []
list3 = []
list4 = []
# for a in tqdm(ALPHABET_ALL):#加密
#     for b in ALPHABET_ALL:
#         str1 = a+b
#         key1 = str1.encode() + ''.join(k).encode() + b'\x00' * 6
#         jiami1 = jiami(m, key1)
#         for c in ALPHABET_ALL:
#             for d in ALPHABET_ALL:
#                 str2 = c+d
#                 key2 = str2.encode() + ''.join(k).encode() + b'\x00' * 6
#                 jiami2 = jiami(jiami1, key2)
#                 list1.append(jiami2)
#                 list2.append(str(a+b+c+d))
# print('ok1')
# for a in tqdm(ALPHABET_ALL):
#     for b in ALPHABET_ALL:
#         str1 = a+b
#         key3 = str1.encode() + ''.join(k).encode() + b'\x00' * 6
#         jiemi1 = jiemi(cipher, key3)
#         for c in ALPHABET_ALL:
#             for d in ALPHABET_ALL:
#                 str2 = c+d
#                 key4 = str2.encode() + ''.join(k).encode() + b'\x00' * 6
#                 jiemi2 = jiemi(jiemi1, key4)
#                 list3.append(jiemi2)
#                 list4.append(str(a+b+c+d)) 
print('ok2')
# jiaoji = set(list1) & set(list3)
# print(jiaoji)
jiaoji = b'\x87\xf3b\xfe\xc8\xe3\x96q5\xdax\x01\xe1U\xfd\x88_:7\xb8\t\x82\x83\xdd5\x1atO\xe9\xdfn\xea'
# for i in tqdm(range(len(list1))):
    # if list1[i] == jiaoji:
    #     print(list2[i])
    #     exit()
    # if list3[i] == jiaoji:
    #     print(list4[i])
    #     exit()
print('ok3')
key1 = '8U'.encode() + ''.join(k).encode() + b'\x00' * 6
key2 = '9e'.encode() + ''.join(k).encode() + b'\x00' * 6
key3 = 'aT'.encode() + ''.join(k).encode() + b'\x00' * 6
key4 = 'lt'.encode() + ''.join(k).encode() + b'\x00' * 6
flag = bytes.fromhex('9da1f3806954ebe7f76b829f799901617ffae4eee96c5bb925f6fd58feecdef2c74505c02262e9d5480c2375300f2f3d404a6eee31f03e172c30b246c6490479d2d6d759611dc5cdc410d631b9709936')
flag2 = jiemi(jiemi(jiemi(jiemi(flag, key3), key4), key2), key1)
print(flag2)
# b'wow! you are wonderful, this is your flag2 : aaf2e86a3fe4af5156}\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'

[GKCTF2020]Backdoor

#!/usr/bin/python
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import gmpy2, binascii
import base64
from FLAG import flag

def rsa_encrypt(message):
    with open('./pub.pem' ,'r') as f:
        key = RSA.import_key(f.read())
    e = key.e
    n = key.n
    c = pow(bytes_to_long(flag), e, n)
 
    ciphertext = binascii.hexlify(long_to_bytes(c))
    return ciphertext

if __name__ == "__main__":
    text = base64.b64encode(rsa_encrypt(flag))
    with open('flag.enc','wb') as f:
        f.write(text)

某CVE

# f = '02142af7ce70fe0ddae116bb7e96260274ee9252a8cb528e7fdd29809c2a6032727c05526133ae4610ed944572ff1abfcd0b17aa22ef44a2'
# c = bytes_to_long(bytes.fromhex(f))
# print(c)
# with open('./pub.pem' ,'r') as f:
#     key = RSA.import_key(f.read())
# e = key.e
# n = key.n
# print(e, n)
from Crypto.Util import number
from gmpy2 import *
from libnum import *
c = 5902102609936183530036413041949205016072856184947596155784933422689438216690059498706287388882989673839294236821030261398121787376802
e = 65537 
n = 15518961041625074876182404585394098781487141059285455927024321276783831122168745076359780343078011216480587575072479784829258678691739
vals=39
M=1
n = mpz(15518961041625074876182404585394098781487141059285455927024321276783831122168745076359780343078011216480587575072479784829258678691739)
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999]
for x in range(0, vals):
    M=M*primes[x]
for a in range(1,20):
    for k in range(50):
        p=mpz(k*M+(65537**a %M))
        if is_prime(p):
            q = mpz(n//p)
            if is_prime(q):
                print('p=%d\nq=%d'%(p,q))
p=4582433561127855310805294456657993281782662645116543024537051682479
q=3386619977051114637303328519173627165817832179845212640767197001941
d = invert(e, (p-1)*(q-1))
print n2s(pow(c, d, n))
# flag{760958c9-cca9-458b-9cbe-ea07aa1668e4}

[V&N2020 公开赛]easy_RSA

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

def getprime(bits):
    while 1:
        n = 1
        while n.bit_length() < bits:
            n *= next_prime(randint(1,1000))
        if isPrime(n - 1):
            return n - 1

m = bytes_to_long(b'flag{************************************}')

p = getprime(505)
q = getPrime(512)
r = getPrime(512)
assert m < q

n = p * q * r
e = 0x10001
d = invert(q ** 2, p ** 2)
c = pow(m, 2, r)
cipher = pow(c, e, n)

print(n)
print(d)
print(cipher)


'''

7941371739956577280160664419383740967516918938781306610817149744988379280561359039016508679365806108722198157199058807892703837558280678711420411242914059658055366348123106473335186505617418956630780649894945233345985279471106888635177256011468979083320605103256178446993230320443790240285158260236926519042413378204298514714890725325831769281505530787739922007367026883959544239568886349070557272869042275528961483412544495589811933856131557221673534170105409
7515987842794170949444517202158067021118454558360145030399453487603693522695746732547224100845570119375977629070702308991221388721952258969752305904378724402002545947182529859604584400048983091861594720299791743887521228492714135449584003054386457751933095902983841246048952155097668245322664318518861440
1618155233923718966393124032999431934705026408748451436388483012584983753140040289666712916510617403356206112730613485227084128314043665913357106301736817062412927135716281544348612150328867226515184078966397180771624148797528036548243343316501503364783092550480439749404301122277056732857399413805293899249313045684662146333448668209567898831091274930053147799756622844119463942087160062353526056879436998061803187343431081504474584816590199768034450005448200

'''

1. Williams’p+1 algorithm

   https://0xdktb.top/2020/02/28/Summary-of-Crypto-in-CTF-RSA/#RSA-William%E2%80%99s-p-1-and-Pollard%E2%80%99s-p-1

2. p < q ，分解q^2的时候要加上p^2的倍数

3. 模数是素数，e = 2，求解二次平方根：Tonelli–Shanks算法

from gmpy2 import *
from libnum import *
from primefac import *
from tqdm import tqdm
n = 7941371739956577280160664419383740967516918938781306610817149744988379280561359039016508679365806108722198157199058807892703837558280678711420411242914059658055366348123106473335186505617418956630780649894945233345985279471106888635177256011468979083320605103256178446993230320443790240285158260236926519042413378204298514714890725325831769281505530787739922007367026883959544239568886349070557272869042275528961483412544495589811933856131557221673534170105409
# p = williams_pp1(n)
# print p
p = 102634610559478918970860957918259981057327949366949344137104804864768237961662136189827166317524151288799657758536256924609797810164397005081733039415393
e = 0x10001
d = 7515987842794170949444517202158067021118454558360145030399453487603693522695746732547224100845570119375977629070702308991221388721952258969752305904378724402002545947182529859604584400048983091861594720299791743887521228492714135449584003054386457751933095902983841246048952155097668245322664318518861440
cipher = 1618155233923718966393124032999431934705026408748451436388483012584983753140040289666712916510617403356206112730613485227084128314043665913357106301736817062412927135716281544348612150328867226515184078966397180771624148797528036548243343316501503364783092550480439749404301122277056732857399413805293899249313045684662146333448668209567898831091274930053147799756622844119463942087160062353526056879436998061803187343431081504474584816590199768034450005448200
q2 = invert(d, p**2)
# for i in tqdm(range(10000)):
# 	q = iroot(q2+i*p**2, 2)
# 	if q[1]:
# 		print q[0]
# 		exit()
q = 7534810196420932552168708937019691994681052660068275906973480617604535381306041583841106383688654426129050931519275383386503174076258645141589911492908993
r = n // p // q
d1 = invert(e, (p-1)*(q-1)*(r-1))
c = pow(cipher, d1, n)
def legendre(a, p):
    return pow(a, (p - 1) // 2, p)
def tonelli(n, p):
    assert legendre(n, p) == 1
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    if s == 1:
        return pow(n, (p + 1) // 4, p)
    for z in range(2, 10000):
#    for z in range(2, p):
        if p - 1 == legendre(z, p):
            break
    c = pow(z, q, p)
    r = pow(n, (q + 1) // 2, p)
    t = pow(n, q, p)
    m = s
    t2 = 0
    while (t - 1) % p != 0:
        t2 = (t * t) % p
        for i in range(1, m):
            if (t2 - 1) % p == 0:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        r = (r * b) % p
        c = (b * b) % p
        t = (t * c) % p
        m = i
    return r
m = tonelli(c, r)
print n2s(m)
# flag{fd462593-25e4-4631-a96a-0cd5c72b2d1b}

[DASCTF三月赛]son_of_NTRU

from random import randrange
from Crypto.Util.number import *
from gmpy2 import invert
def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def generate():
    p = getPrime(1024)
    while True:
        f = randrange(1,(p//2)**(0.5))
        g = randrange((p//4)**(0.5),(p//2)**(0.5))
        if gcd(f,p)==1 and gcd(f,g)==1:
            break
    h = (invert(f,p)*g)%p
    return h,p,f,g

def encrypt(m,h,p):
    assert m<(p//4)**(0.5)
    r = randrange(1,(p//2)**(0.5))
    c = (r*h+m)%p
    return c

h,p,f,g = generate()

from flag import flag
c = encrypt(bytes_to_long(flag),h,p)
print("h = {}".format(h))
print("p = {}".format(p))
print("c = {}".format(c))
# h = 70851272226599856513658616506718804769182611213413854493145253337330709939355936692154199813179587933065165812259913249917314725765898812249062834111179900151466610356207921771928832591335738750053453046857602342378475278876652263044722419918958361163645152112020971804267503129035439011008349349624213734004
# p = 125796773654949906956757901514929172896506715196511121353157781851652093811702246079116208920427110231653664239838444378725001877052652056537732732266407477191221775698956008368755461680533430353707546171814962217736494341129233572423073286387554056407408816555382448824610216634458550949715062229816683685469
# c = 4691517945653877981376957637565364382959972087952249273292897076221178958350355396910942555879426136128610896883898318646711419768716904972164508407035668258209226498292327845169861395205212789741065517685193351416871631112431257858097798333893494180621728198734264288028849543413123321402664789239712408700

https://xz.aliyun.com/t/7163

# sage
h = 70851272226599856513658616506718804769182611213413854493145253337330709939355936692154199813179587933065165812259913249917314725765898812249062834111179900151466610356207921771928832591335738750053453046857602342378475278876652263044722419918958361163645152112020971804267503129035439011008349349624213734004
p = 125796773654949906956757901514929172896506715196511121353157781851652093811702246079116208920427110231653664239838444378725001877052652056537732732266407477191221775698956008368755461680533430353707546171814962217736494341129233572423073286387554056407408816555382448824610216634458550949715062229816683685469
c = 4691517945653877981376957637565364382959972087952249273292897076221178958350355396910942555879426136128610896883898318646711419768716904972164508407035668258209226498292327845169861395205212789741065517685193351416871631112431257858097798333893494180621728198734264288028849543413123321402664789239712408700
# Construct lattice.
v1 = vector(ZZ, [1, h])
v2 = vector(ZZ, [0, p])
m = matrix([v1,v2]);
# Solve SVP.
shortest_vector = m.LLL()[0]
f, g = shortest_vector
# print(f, g)
# Decrypt
f = 3052745506321037491577220926923466609715612813029263120922605939187287981215931840968854538555321338710902665095952768815345285556873715325200121768087377 
g = 6390108444026998457573135563944030351069358995011779835195686570376684843461358071141777920310356437442825541867565659114422145012850808683785653621804110
a = f*c % p % g
m = a * inverse_mod(f, g) % g
# print(m)
print(bytes.fromhex(hex(m)[2:]))
# b'flag{93d02e3bf2c7458a47aac58387140dd5}'

[DASCTF三月赛]FeedBack

from secret import flag
from string import hexdigits
import random
from functools import reduce
def cycle(c:list,a:list)->int:
    return reduce(lambda x,y: x+y,map(lambda x: x[0]*x[1],zip(c,a))) 
def enc(m:list,k:list)->list:
    for i in range(len(k)*2):
        m.append(cycle(m[i:i+len(k)],k))
    return m[len(k):]
print(hexdigits)
if __name__ == "__main__":
    key=[ord(random.choice(hexdigits)) for i in range(len(flag))]
    c=enc(list(flag),key)
    print(c)

# flag = [180320, 12795604, 913707946, 65244867544, 4658921499366, 332678259897680, 23755460291939729, 1696299282824525162, 121127152307279309992, 8649291534003765460181, 617617459134250473857819, 44102031285199767595231826, 3149180993372727865351695610, 224872656429052251931507068163, 16057416742916791898621189838002, 1146607313446549338631740275859490, 81875456824588820793005728503088789, 5846457066530480582594997088868317921, 417476268914312098171907310476576578536, 29810607197367740257089118506396936455267, 2128677406710643996313598469435818995764283, 152001851952900202233154866795341968398324618, 10853952282423997785255606215412380976089774602, 775045031593704366379150517314704054142878227755, 55343416422679709865626814221707233611767499083451, 3951891330799176591085237005754672086216649002044116, 282191561344334793283891774610663595748300192924237652, 20150371209182455377207293308509352961052348504530516058, 1438871729308714548579613052036192683042976990785336035213, 102745097443187470470063857372230471012050786200205019335560, 7336689458539737357933680339939811164938123954552946412371136, 523888862345101730958585832445722009143686030486587614405269619, 37409180481229224476184683624742923927721083153229315469794323846, 2671266531631899605156440693785360699681088880751785277451781995127, 190746356675660819059021289711194688989007498945709965975632125093772, 13620569925986012345710256811290898483914841356894501064938828451682289, 972600097542764210429602165761543702875470220807440912087468994318947199, 69450173882625967125859360885466807837084362724230554403206714010957033564, 4959208480970674965771932762141990438694621159829420665293248503741956497339, 354120765763611360372631234091033326236527919343510113669886900852817067794937, 25286599106731127999761204195099137001826484641202640190432847596126102129290177, 1805632869356683189091740036886552559813413339716342384679179468460652986832630119, 128934304100758873373068786008043012614625306314330902439450614878647840309940810799, 9206774564238985792239909901043542380389506567225353556524468058541750913201465442258, 657425488646345934124836595103998888905043390553798696290609052666406363868364633227987, 46944591735815161454850764823066332748372328488810515939042504343121621896260739496814215, 3352158885381868382186614128492698209211597671157972107257901283108688995314288195559935895, 239366640061152248661380413770610731951278310979044705869198442025229868870474962029566786828, 17092384440374810990148000504438682199862673994374786921479630475896214666270304948184067943963, 1220510952499186818225235173267171189892653750839095345581049972346091269304188809141591821528945, 87152672604981875905661244747737456527193455119785950165560211136820203006355054095176767065463607, 6223285687554056604834063330772248822879874758146969128122776216276580479221618865554693862254391145, 444384361274324240336894080988769378714126300500080707977898823502774400070423897702729938853457320554, 31732025566514505285832183071784730973330427403124198140983516899800427456134314554661472009492580417251]

主要的运算逻辑就是边移位边和key相乘再求和

先把key作为未知数，利用前27位c和key运算生成后27位c的逻辑求得key

再把27位flag作为未知数，利用27位flag和key运算生成前27位c的逻辑求得flag

z3解方程组

from z3 import *
c = [180320, 12795604, 913707946, 65244867544, 4658921499366, 332678259897680, 23755460291939729, 1696299282824525162, 121127152307279309992, 8649291534003765460181, 617617459134250473857819, 44102031285199767595231826, 3149180993372727865351695610, 224872656429052251931507068163, 16057416742916791898621189838002, 1146607313446549338631740275859490, 81875456824588820793005728503088789, 5846457066530480582594997088868317921, 417476268914312098171907310476576578536, 29810607197367740257089118506396936455267, 2128677406710643996313598469435818995764283, 152001851952900202233154866795341968398324618, 10853952282423997785255606215412380976089774602, 775045031593704366379150517314704054142878227755, 55343416422679709865626814221707233611767499083451, 3951891330799176591085237005754672086216649002044116, 282191561344334793283891774610663595748300192924237652, 20150371209182455377207293308509352961052348504530516058, 1438871729308714548579613052036192683042976990785336035213, 102745097443187470470063857372230471012050786200205019335560, 7336689458539737357933680339939811164938123954552946412371136, 523888862345101730958585832445722009143686030486587614405269619, 37409180481229224476184683624742923927721083153229315469794323846, 2671266531631899605156440693785360699681088880751785277451781995127, 190746356675660819059021289711194688989007498945709965975632125093772, 13620569925986012345710256811290898483914841356894501064938828451682289, 972600097542764210429602165761543702875470220807440912087468994318947199, 69450173882625967125859360885466807837084362724230554403206714010957033564, 4959208480970674965771932762141990438694621159829420665293248503741956497339, 354120765763611360372631234091033326236527919343510113669886900852817067794937, 25286599106731127999761204195099137001826484641202640190432847596126102129290177, 1805632869356683189091740036886552559813413339716342384679179468460652986832630119, 128934304100758873373068786008043012614625306314330902439450614878647840309940810799, 9206774564238985792239909901043542380389506567225353556524468058541750913201465442258, 657425488646345934124836595103998888905043390553798696290609052666406363868364633227987, 46944591735815161454850764823066332748372328488810515939042504343121621896260739496814215, 3352158885381868382186614128492698209211597671157972107257901283108688995314288195559935895, 239366640061152248661380413770610731951278310979044705869198442025229868870474962029566786828, 17092384440374810990148000504438682199862673994374786921479630475896214666270304948184067943963, 1220510952499186818225235173267171189892653750839095345581049972346091269304188809141591821528945, 87152672604981875905661244747737456527193455119785950165560211136820203006355054095176767065463607, 6223285687554056604834063330772248822879874758146969128122776216276580479221618865554693862254391145, 444384361274324240336894080988769378714126300500080707977898823502774400070423897702729938853457320554, 31732025566514505285832183071784730973330427403124198140983516899800427456134314554661472009492580417251]
# k=[Int('k%d'%i) for i in range(27)]
f=[Int('f%d'%i) for i in range(27)]
# for i in range(27):
#     print('s.add(')
#     for j in range(27):
#         if j !=26:
#             print('c[{}]*k[{}]+'.format(i+j,j),end='')
#         else: 
#         	print('c[{}]*k[{}]'.format(i+j,j),end='')
#     print('==c[{}])'.format(i+j+1))
s=Solver()
# s.add(
# c[0]*k[0]+c[1]*k[1]+c[2]*k[2]+c[3]*k[3]+c[4]*k[4]+c[5]*k[5]+c[6]*k[6]+c[7]*k[7]+c[8]*k[8]+c[9]*k[9]+c[10]*k[10]+c[11]*k[11]+c[12]*k[12]+c[13]*k[13]+c[14]*k[14]+c[15]*k[15]+c[16]*k[16]+c[17]*k[17]+c[18]*k[18]+c[19]*k[19]+c[20]*k[20]+c[21]*k[21]+c[22]*k[22]+c[23]*k[23]+c[24]*k[24]+c[25]*k[25]+c[26]*k[26]==c[27])
# s.add(
# c[1]*k[0]+c[2]*k[1]+c[3]*k[2]+c[4]*k[3]+c[5]*k[4]+c[6]*k[5]+c[7]*k[6]+c[8]*k[7]+c[9]*k[8]+c[10]*k[9]+c[11]*k[10]+c[12]*k[11]+c[13]*k[12]+c[14]*k[13]+c[15]*k[14]+c[16]*k[15]+c[17]*k[16]+c[18]*k[17]+c[19]*k[18]+c[20]*k[19]+c[21]*k[20]+c[22]*k[21]+c[23]*k[22]+c[24]*k[23]+c[25]*k[24]+c[26]*k[25]+c[27]*k[26]==c[28])
# s.add(
# c[2]*k[0]+c[3]*k[1]+c[4]*k[2]+c[5]*k[3]+c[6]*k[4]+c[7]*k[5]+c[8]*k[6]+c[9]*k[7]+c[10]*k[8]+c[11]*k[9]+c[12]*k[10]+c[13]*k[11]+c[14]*k[12]+c[15]*k[13]+c[16]*k[14]+c[17]*k[15]+c[18]*k[16]+c[19]*k[17]+c[20]*k[18]+c[21]*k[19]+c[22]*k[20]+c[23]*k[21]+c[24]*k[22]+c[25]*k[23]+c[26]*k[24]+c[27]*k[25]+c[28]*k[26]==c[29])
# s.add(
# c[3]*k[0]+c[4]*k[1]+c[5]*k[2]+c[6]*k[3]+c[7]*k[4]+c[8]*k[5]+c[9]*k[6]+c[10]*k[7]+c[11]*k[8]+c[12]*k[9]+c[13]*k[10]+c[14]*k[11]+c[15]*k[12]+c[16]*k[13]+c[17]*k[14]+c[18]*k[15]+c[19]*k[16]+c[20]*k[17]+c[21]*k[18]+c[22]*k[19]+c[23]*k[20]+c[24]*k[21]+c[25]*k[22]+c[26]*k[23]+c[27]*k[24]+c[28]*k[25]+c[29]*k[26]==c[30])
# s.add(
# c[4]*k[0]+c[5]*k[1]+c[6]*k[2]+c[7]*k[3]+c[8]*k[4]+c[9]*k[5]+c[10]*k[6]+c[11]*k[7]+c[12]*k[8]+c[13]*k[9]+c[14]*k[10]+c[15]*k[11]+c[16]*k[12]+c[17]*k[13]+c[18]*k[14]+c[19]*k[15]+c[20]*k[16]+c[21]*k[17]+c[22]*k[18]+c[23]*k[19]+c[24]*k[20]+c[25]*k[21]+c[26]*k[22]+c[27]*k[23]+c[28]*k[24]+c[29]*k[25]+c[30]*k[26]==c[31])
# s.add(
# c[5]*k[0]+c[6]*k[1]+c[7]*k[2]+c[8]*k[3]+c[9]*k[4]+c[10]*k[5]+c[11]*k[6]+c[12]*k[7]+c[13]*k[8]+c[14]*k[9]+c[15]*k[10]+c[16]*k[11]+c[17]*k[12]+c[18]*k[13]+c[19]*k[14]+c[20]*k[15]+c[21]*k[16]+c[22]*k[17]+c[23]*k[18]+c[24]*k[19]+c[25]*k[20]+c[26]*k[21]+c[27]*k[22]+c[28]*k[23]+c[29]*k[24]+c[30]*k[25]+c[31]*k[26]==c[32])
# s.add(
# c[6]*k[0]+c[7]*k[1]+c[8]*k[2]+c[9]*k[3]+c[10]*k[4]+c[11]*k[5]+c[12]*k[6]+c[13]*k[7]+c[14]*k[8]+c[15]*k[9]+c[16]*k[10]+c[17]*k[11]+c[18]*k[12]+c[19]*k[13]+c[20]*k[14]+c[21]*k[15]+c[22]*k[16]+c[23]*k[17]+c[24]*k[18]+c[25]*k[19]+c[26]*k[20]+c[27]*k[21]+c[28]*k[22]+c[29]*k[23]+c[30]*k[24]+c[31]*k[25]+c[32]*k[26]==c[33])
# s.add(
# c[7]*k[0]+c[8]*k[1]+c[9]*k[2]+c[10]*k[3]+c[11]*k[4]+c[12]*k[5]+c[13]*k[6]+c[14]*k[7]+c[15]*k[8]+c[16]*k[9]+c[17]*k[10]+c[18]*k[11]+c[19]*k[12]+c[20]*k[13]+c[21]*k[14]+c[22]*k[15]+c[23]*k[16]+c[24]*k[17]+c[25]*k[18]+c[26]*k[19]+c[27]*k[20]+c[28]*k[21]+c[29]*k[22]+c[30]*k[23]+c[31]*k[24]+c[32]*k[25]+c[33]*k[26]==c[34])
# s.add(
# c[8]*k[0]+c[9]*k[1]+c[10]*k[2]+c[11]*k[3]+c[12]*k[4]+c[13]*k[5]+c[14]*k[6]+c[15]*k[7]+c[16]*k[8]+c[17]*k[9]+c[18]*k[10]+c[19]*k[11]+c[20]*k[12]+c[21]*k[13]+c[22]*k[14]+c[23]*k[15]+c[24]*k[16]+c[25]*k[17]+c[26]*k[18]+c[27]*k[19]+c[28]*k[20]+c[29]*k[21]+c[30]*k[22]+c[31]*k[23]+c[32]*k[24]+c[33]*k[25]+c[34]*k[26]==c[35])
# s.add(
# c[9]*k[0]+c[10]*k[1]+c[11]*k[2]+c[12]*k[3]+c[13]*k[4]+c[14]*k[5]+c[15]*k[6]+c[16]*k[7]+c[17]*k[8]+c[18]*k[9]+c[19]*k[10]+c[20]*k[11]+c[21]*k[12]+c[22]*k[13]+c[23]*k[14]+c[24]*k[15]+c[25]*k[16]+c[26]*k[17]+c[27]*k[18]+c[28]*k[19]+c[29]*k[20]+c[30]*k[21]+c[31]*k[22]+c[32]*k[23]+c[33]*k[24]+c[34]*k[25]+c[35]*k[26]==c[36])
# s.add(
# c[10]*k[0]+c[11]*k[1]+c[12]*k[2]+c[13]*k[3]+c[14]*k[4]+c[15]*k[5]+c[16]*k[6]+c[17]*k[7]+c[18]*k[8]+c[19]*k[9]+c[20]*k[10]+c[21]*k[11]+c[22]*k[12]+c[23]*k[13]+c[24]*k[14]+c[25]*k[15]+c[26]*k[16]+c[27]*k[17]+c[28]*k[18]+c[29]*k[19]+c[30]*k[20]+c[31]*k[21]+c[32]*k[22]+c[33]*k[23]+c[34]*k[24]+c[35]*k[25]+c[36]*k[26]==c[37])
# s.add(
# c[11]*k[0]+c[12]*k[1]+c[13]*k[2]+c[14]*k[3]+c[15]*k[4]+c[16]*k[5]+c[17]*k[6]+c[18]*k[7]+c[19]*k[8]+c[20]*k[9]+c[21]*k[10]+c[22]*k[11]+c[23]*k[12]+c[24]*k[13]+c[25]*k[14]+c[26]*k[15]+c[27]*k[16]+c[28]*k[17]+c[29]*k[18]+c[30]*k[19]+c[31]*k[20]+c[32]*k[21]+c[33]*k[22]+c[34]*k[23]+c[35]*k[24]+c[36]*k[25]+c[37]*k[26]==c[38])
# s.add(
# c[12]*k[0]+c[13]*k[1]+c[14]*k[2]+c[15]*k[3]+c[16]*k[4]+c[17]*k[5]+c[18]*k[6]+c[19]*k[7]+c[20]*k[8]+c[21]*k[9]+c[22]*k[10]+c[23]*k[11]+c[24]*k[12]+c[25]*k[13]+c[26]*k[14]+c[27]*k[15]+c[28]*k[16]+c[29]*k[17]+c[30]*k[18]+c[31]*k[19]+c[32]*k[20]+c[33]*k[21]+c[34]*k[22]+c[35]*k[23]+c[36]*k[24]+c[37]*k[25]+c[38]*k[26]==c[39])
# s.add(
# c[13]*k[0]+c[14]*k[1]+c[15]*k[2]+c[16]*k[3]+c[17]*k[4]+c[18]*k[5]+c[19]*k[6]+c[20]*k[7]+c[21]*k[8]+c[22]*k[9]+c[23]*k[10]+c[24]*k[11]+c[25]*k[12]+c[26]*k[13]+c[27]*k[14]+c[28]*k[15]+c[29]*k[16]+c[30]*k[17]+c[31]*k[18]+c[32]*k[19]+c[33]*k[20]+c[34]*k[21]+c[35]*k[22]+c[36]*k[23]+c[37]*k[24]+c[38]*k[25]+c[39]*k[26]==c[40])
# s.add(
# c[14]*k[0]+c[15]*k[1]+c[16]*k[2]+c[17]*k[3]+c[18]*k[4]+c[19]*k[5]+c[20]*k[6]+c[21]*k[7]+c[22]*k[8]+c[23]*k[9]+c[24]*k[10]+c[25]*k[11]+c[26]*k[12]+c[27]*k[13]+c[28]*k[14]+c[29]*k[15]+c[30]*k[16]+c[31]*k[17]+c[32]*k[18]+c[33]*k[19]+c[34]*k[20]+c[35]*k[21]+c[36]*k[22]+c[37]*k[23]+c[38]*k[24]+c[39]*k[25]+c[40]*k[26]==c[41])
# s.add(
# c[15]*k[0]+c[16]*k[1]+c[17]*k[2]+c[18]*k[3]+c[19]*k[4]+c[20]*k[5]+c[21]*k[6]+c[22]*k[7]+c[23]*k[8]+c[24]*k[9]+c[25]*k[10]+c[26]*k[11]+c[27]*k[12]+c[28]*k[13]+c[29]*k[14]+c[30]*k[15]+c[31]*k[16]+c[32]*k[17]+c[33]*k[18]+c[34]*k[19]+c[35]*k[20]+c[36]*k[21]+c[37]*k[22]+c[38]*k[23]+c[39]*k[24]+c[40]*k[25]+c[41]*k[26]==c[42])
# s.add(
# c[16]*k[0]+c[17]*k[1]+c[18]*k[2]+c[19]*k[3]+c[20]*k[4]+c[21]*k[5]+c[22]*k[6]+c[23]*k[7]+c[24]*k[8]+c[25]*k[9]+c[26]*k[10]+c[27]*k[11]+c[28]*k[12]+c[29]*k[13]+c[30]*k[14]+c[31]*k[15]+c[32]*k[16]+c[33]*k[17]+c[34]*k[18]+c[35]*k[19]+c[36]*k[20]+c[37]*k[21]+c[38]*k[22]+c[39]*k[23]+c[40]*k[24]+c[41]*k[25]+c[42]*k[26]==c[43])
# s.add(
# c[17]*k[0]+c[18]*k[1]+c[19]*k[2]+c[20]*k[3]+c[21]*k[4]+c[22]*k[5]+c[23]*k[6]+c[24]*k[7]+c[25]*k[8]+c[26]*k[9]+c[27]*k[10]+c[28]*k[11]+c[29]*k[12]+c[30]*k[13]+c[31]*k[14]+c[32]*k[15]+c[33]*k[16]+c[34]*k[17]+c[35]*k[18]+c[36]*k[19]+c[37]*k[20]+c[38]*k[21]+c[39]*k[22]+c[40]*k[23]+c[41]*k[24]+c[42]*k[25]+c[43]*k[26]==c[44])
# s.add(
# c[18]*k[0]+c[19]*k[1]+c[20]*k[2]+c[21]*k[3]+c[22]*k[4]+c[23]*k[5]+c[24]*k[6]+c[25]*k[7]+c[26]*k[8]+c[27]*k[9]+c[28]*k[10]+c[29]*k[11]+c[30]*k[12]+c[31]*k[13]+c[32]*k[14]+c[33]*k[15]+c[34]*k[16]+c[35]*k[17]+c[36]*k[18]+c[37]*k[19]+c[38]*k[20]+c[39]*k[21]+c[40]*k[22]+c[41]*k[23]+c[42]*k[24]+c[43]*k[25]+c[44]*k[26]==c[45])
# s.add(
# c[19]*k[0]+c[20]*k[1]+c[21]*k[2]+c[22]*k[3]+c[23]*k[4]+c[24]*k[5]+c[25]*k[6]+c[26]*k[7]+c[27]*k[8]+c[28]*k[9]+c[29]*k[10]+c[30]*k[11]+c[31]*k[12]+c[32]*k[13]+c[33]*k[14]+c[34]*k[15]+c[35]*k[16]+c[36]*k[17]+c[37]*k[18]+c[38]*k[19]+c[39]*k[20]+c[40]*k[21]+c[41]*k[22]+c[42]*k[23]+c[43]*k[24]+c[44]*k[25]+c[45]*k[26]==c[46])
# s.add(
# c[20]*k[0]+c[21]*k[1]+c[22]*k[2]+c[23]*k[3]+c[24]*k[4]+c[25]*k[5]+c[26]*k[6]+c[27]*k[7]+c[28]*k[8]+c[29]*k[9]+c[30]*k[10]+c[31]*k[11]+c[32]*k[12]+c[33]*k[13]+c[34]*k[14]+c[35]*k[15]+c[36]*k[16]+c[37]*k[17]+c[38]*k[18]+c[39]*k[19]+c[40]*k[20]+c[41]*k[21]+c[42]*k[22]+c[43]*k[23]+c[44]*k[24]+c[45]*k[25]+c[46]*k[26]==c[47])
# s.add(
# c[21]*k[0]+c[22]*k[1]+c[23]*k[2]+c[24]*k[3]+c[25]*k[4]+c[26]*k[5]+c[27]*k[6]+c[28]*k[7]+c[29]*k[8]+c[30]*k[9]+c[31]*k[10]+c[32]*k[11]+c[33]*k[12]+c[34]*k[13]+c[35]*k[14]+c[36]*k[15]+c[37]*k[16]+c[38]*k[17]+c[39]*k[18]+c[40]*k[19]+c[41]*k[20]+c[42]*k[21]+c[43]*k[22]+c[44]*k[23]+c[45]*k[24]+c[46]*k[25]+c[47]*k[26]==c[48])
# s.add(
# c[22]*k[0]+c[23]*k[1]+c[24]*k[2]+c[25]*k[3]+c[26]*k[4]+c[27]*k[5]+c[28]*k[6]+c[29]*k[7]+c[30]*k[8]+c[31]*k[9]+c[32]*k[10]+c[33]*k[11]+c[34]*k[12]+c[35]*k[13]+c[36]*k[14]+c[37]*k[15]+c[38]*k[16]+c[39]*k[17]+c[40]*k[18]+c[41]*k[19]+c[42]*k[20]+c[43]*k[21]+c[44]*k[22]+c[45]*k[23]+c[46]*k[24]+c[47]*k[25]+c[48]*k[26]==c[49])
# s.add(
# c[23]*k[0]+c[24]*k[1]+c[25]*k[2]+c[26]*k[3]+c[27]*k[4]+c[28]*k[5]+c[29]*k[6]+c[30]*k[7]+c[31]*k[8]+c[32]*k[9]+c[33]*k[10]+c[34]*k[11]+c[35]*k[12]+c[36]*k[13]+c[37]*k[14]+c[38]*k[15]+c[39]*k[16]+c[40]*k[17]+c[41]*k[18]+c[42]*k[19]+c[43]*k[20]+c[44]*k[21]+c[45]*k[22]+c[46]*k[23]+c[47]*k[24]+c[48]*k[25]+c[49]*k[26]==c[50])
# s.add(
# c[24]*k[0]+c[25]*k[1]+c[26]*k[2]+c[27]*k[3]+c[28]*k[4]+c[29]*k[5]+c[30]*k[6]+c[31]*k[7]+c[32]*k[8]+c[33]*k[9]+c[34]*k[10]+c[35]*k[11]+c[36]*k[12]+c[37]*k[13]+c[38]*k[14]+c[39]*k[15]+c[40]*k[16]+c[41]*k[17]+c[42]*k[18]+c[43]*k[19]+c[44]*k[20]+c[45]*k[21]+c[46]*k[22]+c[47]*k[23]+c[48]*k[24]+c[49]*k[25]+c[50]*k[26]==c[51])
# s.add(
# c[25]*k[0]+c[26]*k[1]+c[27]*k[2]+c[28]*k[3]+c[29]*k[4]+c[30]*k[5]+c[31]*k[6]+c[32]*k[7]+c[33]*k[8]+c[34]*k[9]+c[35]*k[10]+c[36]*k[11]+c[37]*k[12]+c[38]*k[13]+c[39]*k[14]+c[40]*k[15]+c[41]*k[16]+c[42]*k[17]+c[43]*k[18]+c[44]*k[19]+c[45]*k[20]+c[46]*k[21]+c[47]*k[22]+c[48]*k[23]+c[49]*k[24]+c[50]*k[25]+c[51]*k[26]==c[52])
# s.add(
# c[26]*k[0]+c[27]*k[1]+c[28]*k[2]+c[29]*k[3]+c[30]*k[4]+c[31]*k[5]+c[32]*k[6]+c[33]*k[7]+c[34]*k[8]+c[35]*k[9]+c[36]*k[10]+c[37]*k[11]+c[38]*k[12]+c[39]*k[13]+c[40]*k[14]+c[41]*k[15]+c[42]*k[16]+c[43]*k[17]+c[44]*k[18]+c[45]*k[19]+c[46]*k[20]+c[47]*k[21]+c[48]*k[22]+c[49]*k[23]+c[50]*k[24]+c[51]*k[25]+c[52]*k[26]==c[53])
# if s.check()==sat:
#     m=s.model()
#     for i in range(27):
#         print(m[k[i]],end=',')
k=[50,55,51,70,57,68,100,54,49,55,55,66,97,52,65,48,50,52,66,53,49,98,53,102,102,99,70]
# for i in range(27):
#     print('s.add(')
#     for j in range(27):
#         if i+j<=26:
#             if j !=26:
#                 print('f[{}]*k[{}]+'.format(i+j,j),end='')
#             else: print('f[{}]*k[{}]'.format(i+j,j),end='')
#         else:
#             if j !=26:
#                 print('c[{}]*k[{}]+'.format(i+j-27,j),end='')
#             else: print('c[{}]*k[{}]'.format(i+j-27,j),end='')
#     print('==c[{}])'.format(i))
s.add(
f[0]*k[0]+f[1]*k[1]+f[2]*k[2]+f[3]*k[3]+f[4]*k[4]+f[5]*k[5]+f[6]*k[6]+f[7]*k[7]+f[8]*k[8]+f[9]*k[9]+f[10]*k[10]+f[11]*k[11]+f[12]*k[12]+f[13]*k[13]+f[14]*k[14]+f[15]*k[15]+f[16]*k[16]+f[17]*k[17]+f[18]*k[18]+f[19]*k[19]+f[20]*k[20]+f[21]*k[21]+f[22]*k[22]+f[23]*k[23]+f[24]*k[24]+f[25]*k[25]+f[26]*k[26]==c[0])
s.add(
f[1]*k[0]+f[2]*k[1]+f[3]*k[2]+f[4]*k[3]+f[5]*k[4]+f[6]*k[5]+f[7]*k[6]+f[8]*k[7]+f[9]*k[8]+f[10]*k[9]+f[11]*k[10]+f[12]*k[11]+f[13]*k[12]+f[14]*k[13]+f[15]*k[14]+f[16]*k[15]+f[17]*k[16]+f[18]*k[17]+f[19]*k[18]+f[20]*k[19]+f[21]*k[20]+f[22]*k[21]+f[23]*k[22]+f[24]*k[23]+f[25]*k[24]+f[26]*k[25]+c[0]*k[26]==c[1])
s.add(
f[2]*k[0]+f[3]*k[1]+f[4]*k[2]+f[5]*k[3]+f[6]*k[4]+f[7]*k[5]+f[8]*k[6]+f[9]*k[7]+f[10]*k[8]+f[11]*k[9]+f[12]*k[10]+f[13]*k[11]+f[14]*k[12]+f[15]*k[13]+f[16]*k[14]+f[17]*k[15]+f[18]*k[16]+f[19]*k[17]+f[20]*k[18]+f[21]*k[19]+f[22]*k[20]+f[23]*k[21]+f[24]*k[22]+f[25]*k[23]+f[26]*k[24]+c[0]*k[25]+c[1]*k[26]==c[2])
s.add(
f[3]*k[0]+f[4]*k[1]+f[5]*k[2]+f[6]*k[3]+f[7]*k[4]+f[8]*k[5]+f[9]*k[6]+f[10]*k[7]+f[11]*k[8]+f[12]*k[9]+f[13]*k[10]+f[14]*k[11]+f[15]*k[12]+f[16]*k[13]+f[17]*k[14]+f[18]*k[15]+f[19]*k[16]+f[20]*k[17]+f[21]*k[18]+f[22]*k[19]+f[23]*k[20]+f[24]*k[21]+f[25]*k[22]+f[26]*k[23]+c[0]*k[24]+c[1]*k[25]+c[2]*k[26]==c[3])
s.add(
f[4]*k[0]+f[5]*k[1]+f[6]*k[2]+f[7]*k[3]+f[8]*k[4]+f[9]*k[5]+f[10]*k[6]+f[11]*k[7]+f[12]*k[8]+f[13]*k[9]+f[14]*k[10]+f[15]*k[11]+f[16]*k[12]+f[17]*k[13]+f[18]*k[14]+f[19]*k[15]+f[20]*k[16]+f[21]*k[17]+f[22]*k[18]+f[23]*k[19]+f[24]*k[20]+f[25]*k[21]+f[26]*k[22]+c[0]*k[23]+c[1]*k[24]+c[2]*k[25]+c[3]*k[26]==c[4])
s.add(
f[5]*k[0]+f[6]*k[1]+f[7]*k[2]+f[8]*k[3]+f[9]*k[4]+f[10]*k[5]+f[11]*k[6]+f[12]*k[7]+f[13]*k[8]+f[14]*k[9]+f[15]*k[10]+f[16]*k[11]+f[17]*k[12]+f[18]*k[13]+f[19]*k[14]+f[20]*k[15]+f[21]*k[16]+f[22]*k[17]+f[23]*k[18]+f[24]*k[19]+f[25]*k[20]+f[26]*k[21]+c[0]*k[22]+c[1]*k[23]+c[2]*k[24]+c[3]*k[25]+c[4]*k[26]==c[5])
s.add(
f[6]*k[0]+f[7]*k[1]+f[8]*k[2]+f[9]*k[3]+f[10]*k[4]+f[11]*k[5]+f[12]*k[6]+f[13]*k[7]+f[14]*k[8]+f[15]*k[9]+f[16]*k[10]+f[17]*k[11]+f[18]*k[12]+f[19]*k[13]+f[20]*k[14]+f[21]*k[15]+f[22]*k[16]+f[23]*k[17]+f[24]*k[18]+f[25]*k[19]+f[26]*k[20]+c[0]*k[21]+c[1]*k[22]+c[2]*k[23]+c[3]*k[24]+c[4]*k[25]+c[5]*k[26]==c[6])
s.add(
f[7]*k[0]+f[8]*k[1]+f[9]*k[2]+f[10]*k[3]+f[11]*k[4]+f[12]*k[5]+f[13]*k[6]+f[14]*k[7]+f[15]*k[8]+f[16]*k[9]+f[17]*k[10]+f[18]*k[11]+f[19]*k[12]+f[20]*k[13]+f[21]*k[14]+f[22]*k[15]+f[23]*k[16]+f[24]*k[17]+f[25]*k[18]+f[26]*k[19]+c[0]*k[20]+c[1]*k[21]+c[2]*k[22]+c[3]*k[23]+c[4]*k[24]+c[5]*k[25]+c[6]*k[26]==c[7])
s.add(
f[8]*k[0]+f[9]*k[1]+f[10]*k[2]+f[11]*k[3]+f[12]*k[4]+f[13]*k[5]+f[14]*k[6]+f[15]*k[7]+f[16]*k[8]+f[17]*k[9]+f[18]*k[10]+f[19]*k[11]+f[20]*k[12]+f[21]*k[13]+f[22]*k[14]+f[23]*k[15]+f[24]*k[16]+f[25]*k[17]+f[26]*k[18]+c[0]*k[19]+c[1]*k[20]+c[2]*k[21]+c[3]*k[22]+c[4]*k[23]+c[5]*k[24]+c[6]*k[25]+c[7]*k[26]==c[8])
s.add(
f[9]*k[0]+f[10]*k[1]+f[11]*k[2]+f[12]*k[3]+f[13]*k[4]+f[14]*k[5]+f[15]*k[6]+f[16]*k[7]+f[17]*k[8]+f[18]*k[9]+f[19]*k[10]+f[20]*k[11]+f[21]*k[12]+f[22]*k[13]+f[23]*k[14]+f[24]*k[15]+f[25]*k[16]+f[26]*k[17]+c[0]*k[18]+c[1]*k[19]+c[2]*k[20]+c[3]*k[21]+c[4]*k[22]+c[5]*k[23]+c[6]*k[24]+c[7]*k[25]+c[8]*k[26]==c[9])
s.add(
f[10]*k[0]+f[11]*k[1]+f[12]*k[2]+f[13]*k[3]+f[14]*k[4]+f[15]*k[5]+f[16]*k[6]+f[17]*k[7]+f[18]*k[8]+f[19]*k[9]+f[20]*k[10]+f[21]*k[11]+f[22]*k[12]+f[23]*k[13]+f[24]*k[14]+f[25]*k[15]+f[26]*k[16]+c[0]*k[17]+c[1]*k[18]+c[2]*k[19]+c[3]*k[20]+c[4]*k[21]+c[5]*k[22]+c[6]*k[23]+c[7]*k[24]+c[8]*k[25]+c[9]*k[26]==c[10])
s.add(
f[11]*k[0]+f[12]*k[1]+f[13]*k[2]+f[14]*k[3]+f[15]*k[4]+f[16]*k[5]+f[17]*k[6]+f[18]*k[7]+f[19]*k[8]+f[20]*k[9]+f[21]*k[10]+f[22]*k[11]+f[23]*k[12]+f[24]*k[13]+f[25]*k[14]+f[26]*k[15]+c[0]*k[16]+c[1]*k[17]+c[2]*k[18]+c[3]*k[19]+c[4]*k[20]+c[5]*k[21]+c[6]*k[22]+c[7]*k[23]+c[8]*k[24]+c[9]*k[25]+c[10]*k[26]==c[11])
s.add(
f[12]*k[0]+f[13]*k[1]+f[14]*k[2]+f[15]*k[3]+f[16]*k[4]+f[17]*k[5]+f[18]*k[6]+f[19]*k[7]+f[20]*k[8]+f[21]*k[9]+f[22]*k[10]+f[23]*k[11]+f[24]*k[12]+f[25]*k[13]+f[26]*k[14]+c[0]*k[15]+c[1]*k[16]+c[2]*k[17]+c[3]*k[18]+c[4]*k[19]+c[5]*k[20]+c[6]*k[21]+c[7]*k[22]+c[8]*k[23]+c[9]*k[24]+c[10]*k[25]+c[11]*k[26]==c[12])
s.add(
f[13]*k[0]+f[14]*k[1]+f[15]*k[2]+f[16]*k[3]+f[17]*k[4]+f[18]*k[5]+f[19]*k[6]+f[20]*k[7]+f[21]*k[8]+f[22]*k[9]+f[23]*k[10]+f[24]*k[11]+f[25]*k[12]+f[26]*k[13]+c[0]*k[14]+c[1]*k[15]+c[2]*k[16]+c[3]*k[17]+c[4]*k[18]+c[5]*k[19]+c[6]*k[20]+c[7]*k[21]+c[8]*k[22]+c[9]*k[23]+c[10]*k[24]+c[11]*k[25]+c[12]*k[26]==c[13])
s.add(
f[14]*k[0]+f[15]*k[1]+f[16]*k[2]+f[17]*k[3]+f[18]*k[4]+f[19]*k[5]+f[20]*k[6]+f[21]*k[7]+f[22]*k[8]+f[23]*k[9]+f[24]*k[10]+f[25]*k[11]+f[26]*k[12]+c[0]*k[13]+c[1]*k[14]+c[2]*k[15]+c[3]*k[16]+c[4]*k[17]+c[5]*k[18]+c[6]*k[19]+c[7]*k[20]+c[8]*k[21]+c[9]*k[22]+c[10]*k[23]+c[11]*k[24]+c[12]*k[25]+c[13]*k[26]==c[14])
s.add(
f[15]*k[0]+f[16]*k[1]+f[17]*k[2]+f[18]*k[3]+f[19]*k[4]+f[20]*k[5]+f[21]*k[6]+f[22]*k[7]+f[23]*k[8]+f[24]*k[9]+f[25]*k[10]+f[26]*k[11]+c[0]*k[12]+c[1]*k[13]+c[2]*k[14]+c[3]*k[15]+c[4]*k[16]+c[5]*k[17]+c[6]*k[18]+c[7]*k[19]+c[8]*k[20]+c[9]*k[21]+c[10]*k[22]+c[11]*k[23]+c[12]*k[24]+c[13]*k[25]+c[14]*k[26]==c[15])
s.add(
f[16]*k[0]+f[17]*k[1]+f[18]*k[2]+f[19]*k[3]+f[20]*k[4]+f[21]*k[5]+f[22]*k[6]+f[23]*k[7]+f[24]*k[8]+f[25]*k[9]+f[26]*k[10]+c[0]*k[11]+c[1]*k[12]+c[2]*k[13]+c[3]*k[14]+c[4]*k[15]+c[5]*k[16]+c[6]*k[17]+c[7]*k[18]+c[8]*k[19]+c[9]*k[20]+c[10]*k[21]+c[11]*k[22]+c[12]*k[23]+c[13]*k[24]+c[14]*k[25]+c[15]*k[26]==c[16])
s.add(
f[17]*k[0]+f[18]*k[1]+f[19]*k[2]+f[20]*k[3]+f[21]*k[4]+f[22]*k[5]+f[23]*k[6]+f[24]*k[7]+f[25]*k[8]+f[26]*k[9]+c[0]*k[10]+c[1]*k[11]+c[2]*k[12]+c[3]*k[13]+c[4]*k[14]+c[5]*k[15]+c[6]*k[16]+c[7]*k[17]+c[8]*k[18]+c[9]*k[19]+c[10]*k[20]+c[11]*k[21]+c[12]*k[22]+c[13]*k[23]+c[14]*k[24]+c[15]*k[25]+c[16]*k[26]==c[17])
s.add(
f[18]*k[0]+f[19]*k[1]+f[20]*k[2]+f[21]*k[3]+f[22]*k[4]+f[23]*k[5]+f[24]*k[6]+f[25]*k[7]+f[26]*k[8]+c[0]*k[9]+c[1]*k[10]+c[2]*k[11]+c[3]*k[12]+c[4]*k[13]+c[5]*k[14]+c[6]*k[15]+c[7]*k[16]+c[8]*k[17]+c[9]*k[18]+c[10]*k[19]+c[11]*k[20]+c[12]*k[21]+c[13]*k[22]+c[14]*k[23]+c[15]*k[24]+c[16]*k[25]+c[17]*k[26]==c[18])
s.add(
f[19]*k[0]+f[20]*k[1]+f[21]*k[2]+f[22]*k[3]+f[23]*k[4]+f[24]*k[5]+f[25]*k[6]+f[26]*k[7]+c[0]*k[8]+c[1]*k[9]+c[2]*k[10]+c[3]*k[11]+c[4]*k[12]+c[5]*k[13]+c[6]*k[14]+c[7]*k[15]+c[8]*k[16]+c[9]*k[17]+c[10]*k[18]+c[11]*k[19]+c[12]*k[20]+c[13]*k[21]+c[14]*k[22]+c[15]*k[23]+c[16]*k[24]+c[17]*k[25]+c[18]*k[26]==c[19])
s.add(
f[20]*k[0]+f[21]*k[1]+f[22]*k[2]+f[23]*k[3]+f[24]*k[4]+f[25]*k[5]+f[26]*k[6]+c[0]*k[7]+c[1]*k[8]+c[2]*k[9]+c[3]*k[10]+c[4]*k[11]+c[5]*k[12]+c[6]*k[13]+c[7]*k[14]+c[8]*k[15]+c[9]*k[16]+c[10]*k[17]+c[11]*k[18]+c[12]*k[19]+c[13]*k[20]+c[14]*k[21]+c[15]*k[22]+c[16]*k[23]+c[17]*k[24]+c[18]*k[25]+c[19]*k[26]==c[20])
s.add(
f[21]*k[0]+f[22]*k[1]+f[23]*k[2]+f[24]*k[3]+f[25]*k[4]+f[26]*k[5]+c[0]*k[6]+c[1]*k[7]+c[2]*k[8]+c[3]*k[9]+c[4]*k[10]+c[5]*k[11]+c[6]*k[12]+c[7]*k[13]+c[8]*k[14]+c[9]*k[15]+c[10]*k[16]+c[11]*k[17]+c[12]*k[18]+c[13]*k[19]+c[14]*k[20]+c[15]*k[21]+c[16]*k[22]+c[17]*k[23]+c[18]*k[24]+c[19]*k[25]+c[20]*k[26]==c[21])
s.add(
f[22]*k[0]+f[23]*k[1]+f[24]*k[2]+f[25]*k[3]+f[26]*k[4]+c[0]*k[5]+c[1]*k[6]+c[2]*k[7]+c[3]*k[8]+c[4]*k[9]+c[5]*k[10]+c[6]*k[11]+c[7]*k[12]+c[8]*k[13]+c[9]*k[14]+c[10]*k[15]+c[11]*k[16]+c[12]*k[17]+c[13]*k[18]+c[14]*k[19]+c[15]*k[20]+c[16]*k[21]+c[17]*k[22]+c[18]*k[23]+c[19]*k[24]+c[20]*k[25]+c[21]*k[26]==c[22])
s.add(
f[23]*k[0]+f[24]*k[1]+f[25]*k[2]+f[26]*k[3]+c[0]*k[4]+c[1]*k[5]+c[2]*k[6]+c[3]*k[7]+c[4]*k[8]+c[5]*k[9]+c[6]*k[10]+c[7]*k[11]+c[8]*k[12]+c[9]*k[13]+c[10]*k[14]+c[11]*k[15]+c[12]*k[16]+c[13]*k[17]+c[14]*k[18]+c[15]*k[19]+c[16]*k[20]+c[17]*k[21]+c[18]*k[22]+c[19]*k[23]+c[20]*k[24]+c[21]*k[25]+c[22]*k[26]==c[23])
s.add(
f[24]*k[0]+f[25]*k[1]+f[26]*k[2]+c[0]*k[3]+c[1]*k[4]+c[2]*k[5]+c[3]*k[6]+c[4]*k[7]+c[5]*k[8]+c[6]*k[9]+c[7]*k[10]+c[8]*k[11]+c[9]*k[12]+c[10]*k[13]+c[11]*k[14]+c[12]*k[15]+c[13]*k[16]+c[14]*k[17]+c[15]*k[18]+c[16]*k[19]+c[17]*k[20]+c[18]*k[21]+c[19]*k[22]+c[20]*k[23]+c[21]*k[24]+c[22]*k[25]+c[23]*k[26]==c[24])
s.add(
f[25]*k[0]+f[26]*k[1]+c[0]*k[2]+c[1]*k[3]+c[2]*k[4]+c[3]*k[5]+c[4]*k[6]+c[5]*k[7]+c[6]*k[8]+c[7]*k[9]+c[8]*k[10]+c[9]*k[11]+c[10]*k[12]+c[11]*k[13]+c[12]*k[14]+c[13]*k[15]+c[14]*k[16]+c[15]*k[17]+c[16]*k[18]+c[17]*k[19]+c[18]*k[20]+c[19]*k[21]+c[20]*k[22]+c[21]*k[23]+c[22]*k[24]+c[23]*k[25]+c[24]*k[26]==c[25])
s.add(
f[26]*k[0]+c[0]*k[1]+c[1]*k[2]+c[2]*k[3]+c[3]*k[4]+c[4]*k[5]+c[5]*k[6]+c[6]*k[7]+c[7]*k[8]+c[8]*k[9]+c[9]*k[10]+c[10]*k[11]+c[11]*k[12]+c[12]*k[13]+c[13]*k[14]+c[14]*k[15]+c[15]*k[16]+c[16]*k[17]+c[17]*k[18]+c[18]*k[19]+c[19]*k[20]+c[20]*k[21]+c[21]*k[22]+c[22]*k[23]+c[23]*k[24]+c[24]*k[25]+c[25]*k[26]==c[26])
if s.check()==sat:
    m=s.model()
    for i in range(27):
        print(chr(int(str(m[f[i]]))),end='')
# flag{_FeedBack_is_so_e@sy_}

[DASCTF三月赛]threshold

#make.sage
import random
flag = bytearray("DASCTF{********************************}".encode())
flag = list(flag)
length = len(flag)
N=53
p=257
q=28019
d=18
f=[1]*19+[-1]*18+[0]*16
random.shuffle(f)
g=[1]*18+[-1]*18+[0]*17
random.shuffle(g)

Q.<x> = Zmod(q)[]
P.<y> = Zmod(p)[]
fx=Q(f)
fy=P(f)
gx=Q(g)
Fqx=fx.inverse_mod(x^N-1)
Fpy=fy.inverse_mod(y^N-1)
hx=(Fqx*gx).mod(x^N-1)
r=[1]*10+[-1]*22+[0]*21
random.shuffle(r)
rx=Q(r)
mx=Q(flag)
ex=(p*rx*hx+mx).mod(x^N-1)
print(ex)
print(hx)

#7367*x^52 + 24215*x^51 + 5438*x^50 + 7552*x^49 + 22666*x^48 + 21907*x^47 + 10572*x^46 + 19756*x^45 + 4083*x^44 + 22080*x^43 + 1757*x^42 + 5708*x^41 + 22838*x^40 + 4022*x^39 + 9239*x^38 + 1949*x^37 + 27073*x^36 + 8192*x^35 + 955*x^34 + 4373*x^33 + 17877*x^32 + 25592*x^31 + 13535*x^30 + 185*x^29 + 9471*x^28 + 9793*x^27 + 22637*x^26 + 3293*x^25 + 27047*x^24 + 21985*x^23 + 13584*x^22 + 6809*x^21 + 24770*x^20 + 16964*x^19 + 8866*x^18 + 22102*x^17 + 18006*x^16 + 3198*x^15 + 19024*x^14 + 2777*x^13 + 9252*x^12 + 9684*x^11 + 3604*x^10 + 7840*x^9 + 17573*x^8 + 11382*x^7 + 12726*x^6 + 6811*x^5 + 10104*x^4 + 7485*x^3 + 858*x^2 + 15100*x + 15860
#14443*x^52 + 10616*x^51 + 11177*x^50 + 24769*x^49 + 23510*x^48 + 23059*x^47 + 21848*x^46 + 24145*x^45 + 12420*x^44 + 1976*x^43 + 16947*x^42 + 7373*x^41 + 16708*x^40 + 18435*x^39 + 18561*x^38 + 21557*x^37 + 16115*x^36 + 7873*x^35 + 20005*x^34 + 11543*x^33 + 9488*x^32 + 2865*x^31 + 11797*x^30 + 2961*x^29 + 14944*x^28 + 22631*x^27 + 24061*x^26 + 9792*x^25 + 6791*x^24 + 10423*x^23 + 3534*x^22 + 26233*x^21 + 14223*x^20 + 15555*x^19 + 3381*x^18 + 23641*x^17 + 2697*x^16 + 11303*x^15 + 6030*x^14 + 7355*x^13 + 20693*x^12 + 1768*x^11 + 10059*x^10 + 27822*x^9 + 8150*x^8 + 5458*x^7 + 21270*x^6 + 22651*x^5 + 8381*x^4 + 2819*x^3 + 3987*x^2 + 8610*x + 6022

多项式的格基规约，只需关注每项的系数即可

# sage
p = 257
q = 28019
P.<y> = Zmod(p)[]
Q.<x> = Zmod(q)[]
hx = 14443*x^52 + 10616*x^51 + 11177*x^50 + 24769*x^49 + 23510*x^48 + 23059*x^47 + 21848*x^46 + 24145*x^45 + 12420*x^44 + 1976*x^43 + 16947*x^42 + 7373*x^41 + 16708*x^40 + 18435*x^39 + 18561*x^38 + 21557*x^37 + 16115*x^36 + 7873*x^35 + 20005*x^34 + 11543*x^33 + 9488*x^32 + 2865*x^31 + 11797*x^30 + 2961*x^29 + 14944*x^28 + 22631*x^27 + 24061*x^26 + 9792*x^25 + 6791*x^24 + 10423*x^23 + 3534*x^22 + 26233*x^21 + 14223*x^20 + 15555*x^19 + 3381*x^18 + 23641*x^17 + 2697*x^16 + 11303*x^15 + 6030*x^14 + 7355*x^13 + 20693*x^12 + 1768*x^11 + 10059*x^10 + 27822*x^9 + 8150*x^8 + 5458*x^7 + 21270*x^6 + 22651*x^5 + 8381*x^4 + 2819*x^3 + 3987*x^2 + 8610*x + 6022
ex = 7367*x^52 + 24215*x^51 + 5438*x^50 + 7552*x^49 + 22666*x^48 + 21907*x^47 + 10572*x^46 + 19756*x^45 + 4083*x^44 + 22080*x^43 + 1757*x^42 + 5708*x^41 + 22838*x^40 + 4022*x^39 + 9239*x^38 + 1949*x^37 + 27073*x^36 + 8192*x^35 + 955*x^34 + 4373*x^33 + 17877*x^32 + 25592*x^31 + 13535*x^30 + 185*x^29 + 9471*x^28 + 9793*x^27 + 22637*x^26 + 3293*x^25 + 27047*x^24 + 21985*x^23 + 13584*x^22 + 6809*x^21 + 24770*x^20 + 16964*x^19 + 8866*x^18 + 22102*x^17 + 18006*x^16 + 3198*x^15 + 19024*x^14 + 2777*x^13 + 9252*x^12 + 9684*x^11 + 3604*x^10 + 7840*x^9 + 17573*x^8 + 11382*x^7 + 12726*x^6 + 6811*x^5 + 10104*x^4 + 7485*x^3 + 858*x^2 + 15100*x + 15860
temp = []
for i in range(53):
    this = [0] * i + [1] + [0] * (53 - i - 1)
    for j in range(53):
        this.append(hx[(-i + j) % 53])
    temp.append(this)
for i in range(53):
    this = [0]*53 + [0] * i + [28019] +  [0] * (52 - i)
    temp.append(this)
M = Matrix(ZZ ,temp)
B = M.LLL()
_f = B[0][:53]
_g = B[0][53:]
fqx = Q(list(_f))
gqx = Q(list(_g))
fpy = P(list(_f))
Fpy=fpy.inverse_mod(y^53-1)
Fqx=fqx.inverse_mod(x^53-1)
ax = (fqx * ex).mod(x^53-1)
a = []
for i in ax:
    a.append(Mod(i, q).lift_centered())
ay = P(a)
m = ''
for i in list((Fpy * ay).mod(y^53-1)):
    m += chr(i)
print(m)
# DASCTF{9bba98e8024da44a3250acbc06bebc7b}

[V&N2020公开赛]CRT

import hashlib
from functools import reduce
from Crypto.Util.number import *

ms = [getRandomNBitInteger(128) for i in range(8)]
p = reduce(lambda x,y: x*y, ms)
x = getRandomRange(1, p)
cs = [x % m  for m in ms]

flag = "flag{" + hashlib.sha256(str(x).encode()).hexdigest() + "}"
# assert("4b93deeb" in flag)

# ms = [284461942441737992421992210219060544764, 218436209063777179204189567410606431578, 288673438109933649911276214358963643204, 239232622368515797881077917549177081575, 206264514127207567149705234795160750411, 338915547568169045185589241329271490503, 246545359356590592172327146579550739141, 219686182542160835171493232381209438048]
# cs = [273520784183505348818648859874365852523, 128223029008039086716133583343107528289, 5111091025406771271167772696866083419, 33462335595116820423587878784664448439, 145377705960376589843356778052388633917, 128158421725856807614557926615949143594, 230664008267846531848877293149791626711, 94549019966480959688919233343793910003]

中国剩余定理模不互素，需要合并不互素的两个方程。通过不断合并方程最终达到一个满足方程组的最小解。求一个满足条件的解,所以需要爆破。

#coding=utf-8
from hashlib import *
from gmpy2 import *
def merge(a1,n1,a2,n2):
    d = gcd(n1,n2)
    c = a2-a1
    if c%d!=0:
        return 0
    c = (c%n2+n2)%n2
    c = c//d
    n1 = n1//d
    n2 = n2//d
    c *= invert(n1,n2)
    c %= n2
    c *= n1*d
    c += a1
    global n3
    global a3
    n3 = n1*n2*d
    a3 = (c%n3+n3)%n3
    return 1
def exCRT(a,n):
    a1=a[0]
    n1=n[0]
    le= len(a)
    for i in range(1,le):
        a2 = a[i]
        n2=n[i]
        if not merge(a1,n1,a2,n2):
            return -1
        a1 = a3
        n1 = n3
    global mod
    mod=n1
    return (a1%n1+n1)%n1
ms = [284461942441737992421992210219060544764, 218436209063777179204189567410606431578, 288673438109933649911276214358963643204, 239232622368515797881077917549177081575, 206264514127207567149705234795160750411, 338915547568169045185589241329271490503, 246545359356590592172327146579550739141, 219686182542160835171493232381209438048]
cs = [273520784183505348818648859874365852523, 128223029008039086716133583343107528289, 5111091025406771271167772696866083419, 33462335595116820423587878784664448439, 145377705960376589843356778052388633917, 128158421725856807614557926615949143594, 230664008267846531848877293149791626711, 94549019966480959688919233343793910003]
x=exCRT(cs,ms)
flag=sha256(str(x).encode()).hexdigest()
while "4b93deeb" not in flag:
    x=x+mod
    flag = sha256(str(x).encode()).hexdigest()
print(flag)

[AFCTF2018]MyOwnCBC

#!/usr/bin/python2.7
# -*- coding: utf-8 -*-

from Crypto.Cipher import AES
from Crypto.Random import random
from Crypto.Util.number import long_to_bytes

def MyOwnCBC(key, plain):
	if len(key)!=32:
		return "error!"
	cipher_txt = b""
	cipher_arr = []
	cipher = AES.new(key, AES.MODE_ECB, "")
	plain = [plain[i:i+32] for i in range(0, len(plain), 32)]
	print plain
	cipher_arr.append(cipher.encrypt(plain[0]))
	cipher_txt += cipher_arr[0]
	for i in range(1, len(plain)):
		cipher = AES.new(cipher_arr[i-1], AES.MODE_ECB, "")
		cipher_arr.append(cipher.encrypt(plain[i]))
		cipher_txt += cipher_arr[i]
	return cipher_txt
	
key = random.getrandbits(256)
key = long_to_bytes(key)

s = ""
with open("flag.txt","r") as f:
	s = f.read()
	f.close()

with open("flag_cipher","wb") as f:
	f.write(MyOwnCBC(key, s))
	f.close()

上一组的密文作为下一组的key

with open("flag_cipher","rb") as f:
	plain = f.read()
	f.close()
key = plain[:32]
plain = [plain[i:i+32] for i in range(0, len(plain), 32)]
flag = b''
for i in range(1, len(plain)):
	cipher = AES.new(key, AES.MODE_ECB)
	flag += cipher.decrypt(plain[i])
	key = plain[i]
print(flag)
# b"mode of operation is an algorithm that uses a block cipher to provide an information service such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation (encryption or decryption) of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.\n\nMost modes require a unique binary sequence, often called an initialization vector (IV), for each encryption operation. The IV has to be non-repeating and, for some modes, random as well. The initialization vector is used to ensure distinct ciphertexts are produced even when the same plaintext is encrypted multiple times independently with the same key. Block ciphers have one or more block size(s), but during transformation the block size is always fixed. Block cipher modes operate on whole blocks and require that the last part of the data be padded to a full block if it is smaller than the current block size. There are, however, modes that do not require padding because they effectively use a block cipher as a stream cipher.\n\nHistorically, encryption modes have been studied extensively in regard to their error propagation properties under various scenarios of data modification. Later development regarded integrity protection as an entirely separate cryptographic goal. Some modern modes of operation combine confidentiality and authenticity in an efficient way, and are known as authenticated encryption modes.\n\nAh you found it~ afctf{Don't_be_fooled_by_yourself}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"

Polynomial Ring

多项式中的欧拉函数

对于多项式P(y)来讲，欧拉函数phi(P(y))表示所有不高于P(y)幂级的环内所有多项式中，与P(y)无除1以外的公因式的其他多项式的个数。

$ \phi = (p^{P(x).degree()} - 1)*(p^{Q(x).degree()} - 1) $

some api in sagemath

1. R. = PolynomialRing(GF(p)) 系数都小于p的多项式环

2. out = R.random_element(degree=30) 随机，幂级为30

3. out.is_irreducible() 不可约的

4. R.quotient(N) 多项式除法

Pollard’s p-1 Factorization Algorithm

principle

$ L = i(p-1) = j(q-1)+k $

$ a^{L} = a^{i(p-1)} = (a^{p-1})^{i} \equiv 1^{i} \equiv 1 (\bmod p) $

$ a^{L} = a^{j(q-1)+k} = a^{k}(a^{q-1})^{j} \equiv a^{k} \cdot 1^{j} \equiv a^{k}(\bmod q) $

$ p = gcd(a^{L}-1, N) $

Pollard发现如果p-1由一些小素数相乘得到，那么

$ p = gcd(a^{n!}-1, N) $

其中n的值不太大，可以通过爆破

sum = 2
for i in range(1,n):
    sum = pow(sum,i,n)
    # print(sum)
    if(gcd(sum-1,n)!=1):
        print(i)
        print(gcd(sum-1,n))
        break

Smooth Number

一个数的所有素因子都小于等于B，叫作B-smooth number

Short Pad Attack & Related Message Attack

padding长度小于等于$ \frac{n.nbits()}{e^{2}} $

# sage
def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

    g1 = x^e - c1
    g2 = (x+y)^e - c2

    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)

    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()

    kbits = n.nbits()//(2*e*e)
    diff = h.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.4

    return diff

def related_message_attack(c1, c2, diff, e, n): #small e
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]


if __name__ == '__main__':
    n = 
    e = 

    c1 =
    c2 = 

    diff = short_pad_attack(c1, c2, e, n)
    print("difference of two messages is %d" % diff)

    m1 = related_message_attack(c1, c2, diff, e, n)
    print("m1:", m1)
    print("m2:", m1 + diff)

AES.CBC

bit翻转

admin=0 -> admin=1

选择明文攻击

$ iv = M_{1} \oplus M_{2} \oplus C $

padding oracle

PKCS5填充、有交互、key和iv都未知、利用服务器对padding检查有不同回显、末位逐位爆破

[NepCTF2021]ChildRSA

#childrsa
from Crypto.Util.number import *
from gmpy2 import iroot
from os import *
from secret import flag1,flag2,padding1,padding2
assert len(flag1)=20
assert len(flag1)>len(flag2)
assert len(flag2)=len(padding2)
def init1():
    m=(padding1*2**200+bytes_to_long(flag1))*2**200
    r1=getPrime(170)
    r2=getPrime(170)
    p=getPrime(1024)
    q=getPrime(1024)
    N=p*q

    return m,r1,r2,N
    
def enc1(m,r1,r2,N):
    c1=pow(m+r1,3,N)
    c2=pow(m+r2,3,N)
    return c1,c2

def init2():
    prefix = 2**1000
    r3 = 2*prefix+flag2*2**200
    r4 = 2*prefix+padding2*2**200
    return r3,r4

def enc2(r3,r4):
    c3 = pow(r3*r4,3)
    return c3

(m,r1,r2,N) = init1()
(c1,c2)=enc1(m,r1,r2,N)
(r3,r4) = init2()
c3 = enc2(r3,r4)
print N
print(c1,c2,c3)

Coppersmith’s Random Padding Attack

$  c_1 \equiv (m+r_1)^{3}\mod{N}$

$ c_2\equiv(m+r_2)^{3}\mod{N} $

可以看成是
$$
c_1 \equiv M^{3}\mod{N}\
$$

$$
c_2\equiv(M+r)^{3}\mod{N}
$$

然后化简两个公式，将M抵消掉，得到只有r的⼀元⽅程
$$
r^9+(3c_1-3c_2)r^6+(3c_1^2+21c_1c_2+3c_2^2)r^3+(c_1-c_2)^3=0\mod{N}
$$
因为r1、r2最多170位，所以r也是最多170位。此时利⽤coppersmith可以得到r的值
$$
170bits \approx N^{\frac{1}{12}}
$$

$$
epsilon =\frac{1}{9} - \frac{1}{12} = \frac{1}{36}
$$

求得r之后⽤Franklin-Reiter Related Message Attack 得到M。由于M=padding 1|| flag1 || r1 ,因此直接转

化成字节可以得到flag1。

from Crypto.Util.number import * 
#from gmpy2 import iroot 
N=28158376030783126462160089589823483713527137233213875572448002306591587078780130580064960928000260046723470757493523772992812185236491055072491361217940285809743091958889318723862394925161624189393204199333582056921761101170728126732633570787046368451452592297474997001720894985956809324776433753817913573764903118962295218320504483249302086522864189503976194142497460351928118211969015560337732569710308337625261805046420223294551248496856153012197979278463862836023897894535718512636307578414641240750045867326554984308461337470720249462693325847418638485693227856545631806676082705971847561028566848739943309350523L
(c1,c2,c3)=(24224099638194324112593871012681573152728137743988130174034194747749499893806613392393262358304278286207848016575593184397104060179978140321847376670647434030870270659753891424180300938412183930402939964298221231907700551385713992208907288670440128651459855106370601996167821568454498946189809679805856760077602954185656580735443254919133313869021875507715983005654259694427753140006431537962760663821770319611657591446033183695065991242937214964884018439712856483970516075937859659014842147053482562615064262033128353761384111673580976781273192034059752430319614321781718852031021334707002690826600780316128823557078, 9346750271098236574311526832166143274981900619073634627239673835573015044474781208925371397721856252589055337535370071073022935304585017378639576719997933317896392172224331035651304165371533650982779424261861522620182573561472976299952543222698749313342053690793739259992577314602927389157124886863152775368006245054707996451092743563826965858367896714784027494674462238582099575028052030487857739015972028019673964986909534784865442448462755269733906210352597618064622408012998910837512387765999752231309660534222112023575816948992389787796776523706795068869288928522584197893586912900864981983132389327089147168146,12107764658433896580107280538635135643387858852976620070691115333175114455948516277086646541412419646593297889201461016204186139568117475108121483620886979081055400119823555863287145558918960315604392538385365775518531415962595383790406519796107060397002742243430892069572422621367817969753308155681207288179722229190134116638193477979912363191546805420859415583321036973918671704414861068461071208456971522273733442192940846444300605718874968169235475237419035100359757819694303844991958162933063957514071374815976765116772095057060790532835820921941088145846413070125370893266694322242100018189171839236880288990785924731992240524566660760922463600094468267262479875177563252492042982465535450638009272498423063736302466479967160885598220013264243699170187377424360056887609494799576319202957855035769847474106037568257493594313444725436907261296589305657506580644724070073124760436092785070723978602029411520504130916009400359604526646351156436915392008166680858644751752849852559564642823536994015310787265345702214921009048446529410934651620740678596168179297695317825626377519087362620254075060283392495964100088104432955208048486368967069833933648053224437409662903374041626724752539021740964387214123704727358129789524527156031473687977024441000979679744414175754810038626527843431424394300602082336759566303619981176757419266691542040519548871088083534246850686949005736818866455421187638056233493672106359797782169712261131423897346468178309589638059793798304934967642857700497827862408132279349488890162419922934863936257606996005393045700768753829407234139813940831919160314036065245565171960402080772504580960750282631405024166104777299328579173845225098623353952827436661379857324363184646746357839176347923656698542515335105484998791972994614628816209171376677660216724863205662719962318372864)
def cop_solve(N,c1,c2): 
    PR.<x>=PolynomialRing(Zmod(N)) 
    f = x^9+3*(c1-c2)*x^6+(3*c1^2+21*c1*c2+3*c2^2)*x^3+(c1-c2)^3 
    x0=f.small_roots(X=2**170,beta=1.0,epsilon = 1/36) 
    if len(x0) != 0: 
        print(x0[0]) 
    else:
        print("error") 
    return x0[0] 
def gcd(a, b): 
    return a.monic() if b == 0 else gcd(b, a % b) 
def franklin_solve(N,r,c1,c2): 
    R.<X> = Zmod(N)[] 
    f1 = X^3 - c1 
    f2 = (X + r)^3 - c2 
    return long_to_bytes(-gcd(f1, f2).coefficients()[0]) 
R = cop_solve(N,c1,c2) 
M = franklin_solve(N,R,c1,c2) 
print(M[100:-20])#flag1 
#28158376030783126462160089589823483713527137233213875572448002306591587078780130580064960928000260046723470757493523772992812185236491055072491361217940285809743091958889318723862394925161624189393204199333582056921761101170728126732633570787046368451452592297474997001720894985956809324776433753817913573764903118962295218320504483249302086522864189503976194142497460351928118211969015560337732569710308337625261805046420223294551248496856153012197979278463862836023897894535718512636307578414641240750045867326554984308461337470720249462693325847418638485693227856340154690304590078577734025351629922056279918570359
#b'\x00\x00\x00\x00\x00Nep{Nep_n3p_ba4_bad_\x00\x00\x00\x03\t'

flag2直接解⽅程

from Crypto.Util.number import * 
#from gmpy2 import iroot 
c3 = 12107764658433896580107280538635135643387858852976620070691115333175114455948516277086646541412419646593297889201461016204186139568117475108121483620886979081055400119823555863287145558918960315604392538385365775518531415962595383790406519796107060397002742243430892069572422621367817969753308155681207288179722229190134116638193477979912363191546805420859415583321036973918671704414861068461071208456971522273733442192940846444300605718874968169235475237419035100359757819694303844991958162933063957514071374815976765116772095057060790532835820921941088145846413070125370893266694322242100018189171839236880288990785924731992240524566660760922463600094468267262479875177563252492042982465535450638009272498423063736302466479967160885598220013264243699170187377424360056887609494799576319202957855035769847474106037568257493594313444725436907261296589305657506580644724070073124760436092785070723978602029411520504130916009400359604526646351156436915392008166680858644751752849852559564642823536994015310787265345702214921009048446529410934651620740678596168179297695317825626377519087362620254075060283392495964100088104432955208048486368967069833933648053224437409662903374041626724752539021740964387214123704727358129789524527156031473687977024441000979679744414175754810038626527843431424394300602082336759566303619981176757419266691542040519548871088083534246850686949005736818866455421187638056233493672106359797782169712261131423897346468178309589638059793798304934967642857700497827862408132279349488890162419922934863936257606996005393045700768753829407234139813940831919160314036065245565171960402080772504580960750282631405024166104777299328579173845225098623353952827436661379857324363184646746357839176347923656698542515335105484998791972994614628816209171376677660216724863205662719962318372864
def coron(pol, X, Y, k=2, debug=False): 
    if pol.nvariables() != 2: 
        raise ValueError("pol is not bivariate") 
    P.<x,y> = PolynomialRing(ZZ) 
    pol = pol(x,y) 
    xoffset = 0 
    while pol(xoffset,0) == 0: 
        xoffset += 1 
    pol = pol(x+xoffset,y) 
    while gcd(pol(0,0), X) != 1: 
        X = next_prime(X, proof=False) 
    while gcd(pol(0,0), Y) != 1: 
        Y = next_prime(Y, proof=False) 
    pol = P(pol/gcd(pol.coefficients())) # seems to be helpful 
    p00 = pol(0,0) 
    delta = max(pol.degree(x),pol.degree(y)) # maximum degree of any variable 
    W = max(abs(i) for i in pol(x*X,y*Y).coefficients()) 
    u = W + ((1-W) % abs(p00)) 
    N = u*(X*Y)^k # modulus for polynomials 
    p00inv = inverse_mod(p00,N) 
    polq = P(sum((i*p00inv % N)*j for i,j in zip(pol.coefficients(), pol.monomials()))) 
    polynomials = []
    for i in range(delta+k+1): 
        for j in range(delta+k+1): 
            if 0 <= i <= k and 0 <= j <= k: 
                polynomials.append(polq * x^i * y^j * X^(k-i) * Y^(k-j)) 
            else:
                polynomials.append(x^i * y^j * N) 
    monomials = [] 
    for i in polynomials: 
        for j in i.monomials(): 
            if j not in monomials: 
                monomials.append(j) 
    monomials.sort() 
    L = matrix(ZZ,len(monomials)) 
    for i in range(len(monomials)): 
        for j in range(len(monomials)): 
            L[i,j] = polynomials[i](X*x,Y*y).monomial_coefficient(monomials[j]) 
    L = matrix(ZZ,sorted(L,reverse=True)) 
    if debug: 
        print("Bitlengths of matrix elements (before reduction):") 
        print(L.apply_map(lambda x: x.nbits()).str()) 
    L = L.LLL() 
    if debug: 
        print("Bitlengths of matrix elements (after reduction):") 
        print(L.apply_map(lambda x: x.nbits()).str()) 
    roots = [] 
    for i in range(L.nrows()): 
        if debug: 
            print("Trying row {}".format(i)) 
        pol2 = P(sum(map(mul, zip(L[i],monomials)))(x/X,y/Y)) 
        r = pol.resultant(pol2, y) 
        if r.is_constant(): # not independent 
            continue 
    for x0, _ in r.univariate_polynomial().roots(): 
        if x0-xoffset in [i[0] for i in roots]: 
            continue
        if debug: 
            print("Potential x0:",x0) 
        for y0, _ in pol(x0,y).univariate_polynomial().roots(): 
            if debug: 
                print("Potential y0:",y0) 
            if (x0-xoffset,y0) not in roots and pol(x0,y0) == 0: 
                roots.append((x0-xoffset,y0)) 
    return roots 
prefix = 2**1000 
P.<x,y> = PolynomialRing(ZZ) 
f = ((prefix+x*2**200)*(2*prefix+y*2**200))^3-c3 
x0, y0 = coron(f, X=2**160, Y=2**160, k=1, debug=True)[0] 
print(long_to_bytes(x0),long_to_bytes(y0)) 

flag2求解报错，尚未解决。。

[NepCTF2021]lowExponent

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

def Encrypt(e, nbits, msg):
    p, q = [getPrime(int(nbits)) for _ in range(2)]
    N = p*q
    x = int(msg)
    while True:
        a, b = [getRandomRange(1, N) for _ in range(2)]
        P.<Yp> = PolynomialRing(Zmod(p))
        fp = x^3 + a*x + b - Yp^2
        P.<Yq> = PolynomialRing(Zmod(q))
        fq = x^3 + a*x + b - Yq^2
        try:
            yp, yq = int(fp.roots()[0][0]), int(fq.roots()[0][0])
            y = crt([yp, yq], [p, q])
            E = EllipticCurve(IntegerModRing(N), [a, b])
            msg_point = E.point((x, y))
            Ep = EllipticCurve(IntegerModRing(p), [a, b])
            Eq = EllipticCurve(IntegerModRing(q), [a, b])
            N1 = Ep.order()
            N2 = 2*p+2-N1
            N3 = Eq.order()
            N4 = 2*q+2-N3
            d = {
                ( 1, 1): inverse_mod(e, lcm(N1, N3)),
                ( 1,-1): inverse_mod(e, lcm(N1, N4)),
                (-1, 1): inverse_mod(e, lcm(N2, N3)),
                (-1, 1): inverse_mod(e, lcm(N2, N4))
            }
            break
        except:
            pass
    cip_point = e*msg_point
    ciphertext = cip_point.xy()[0]
    privKey = (d, p, q)
    pubKey = (a, b, N)
    return (ciphertext, pubKey, privKey)

def Decrypt(ciphertext, pubKey, privKey):
    d, p, q = privKey
    a, b, N = pubKey
    x = ciphertext
    w = x^3 + a*x + b % N
    P.<Yp> = PolynomialRing(Zmod(p))
    fp = x^3 + a*x + b -Yp^2
    yp = fp.roots()[0][0]
    P.<Yq> = PolynomialRing(Zmod(q))
    fq = x^3 + a*x + b -Yq^2
    yq = fq.roots()[0][0]
    y = crt([int(yp), int(yq)], [p, q])
    E = EllipticCurve(IntegerModRing(N), [a, b])
    cip_point = E.point([x, y])
    legendre_symbol_p = legendre_symbol(w, p)
    legendre_symbol_q = legendre_symbol(w, q)
    msg_point = d[(legendre_symbol_p, legendre_symbol_q)]*cip_point
    return msg_point.xy()[0]


msg = bytes_to_long(flag)
f = open("data", "w")
for i in range(70):
    current_st = time()
    cipher = Encrypt(3, 256, msg)
    f.writelines("{}, {}, {}, {}\n".format(cipher[0],*cipher[1]))
f.close()

加密后的结果是椭圆曲线上的点， Division Polynomials使我们可以⽤仅含⼀个未知数的多项式来表⽰这个点

的x坐标：

$$
\begin{aligned}

\psi_{-1} &=-1 \

\psi_{0} &=0 \

\psi_{1} &=1 \

\psi_{2} &=2 y \

\psi_{3} &=3 x^{4}+6 a x^{2}+12 b x-a^{2} \

\psi_{4} &=4 y\left(x^{6}+5 a x^{4}+20 b x^{3}-5 a^{2} x^{2}-4 a b x-8 b^{2}-a^{3}\right) \

\psi_{2 i+1} &=\psi_{i}\left(\psi_{i+2} \psi_{i-1}^{2}-\psi_{i-2} \psi_{i+1}^{2}\right) / 2 y, i \geq 2 \

\psi_{2 i} &=\psi_{i+2} \psi_{i}^{3}-\psi_{i+1}^{3} \psi_{i-1}, i \geq 3

\end{aligned}
$$

此外，还可以定义多项式 $\phi_{m}$ 和 $\omega_{m}$：

$$
\begin{aligned}

\phi_{m} &=x \psi_{m}^{2}-\psi_{m+1} \psi_{m-1} \

\omega_{m} &=\left(\psi_{m+2} \psi_{m-1}^{2}-\psi_{m-2} \psi_{m+1}^{2}\right) / 4 y

\end{aligned}
$$

那么椭圆曲线上的数乘，就可以⽤Division Polynomials来表⽰了：
$$
m P=\left(\frac{\phi_{m}(P)}{\psi_{m}(P)^{2}}, \frac{\omega_{m}(P)}{\psi_{m}(P)^{3}}\right)
$$

$$
ciphertext=\frac{\phi_{m}(P)}{\psi_{m}(P)^{2}}
$$

$$
f=ciphertext\cdot \psi_{m}(P)^{2}-\phi_{m}(P)=0\ (mod\ n)
$$

由于密⽂给了70组，所以 $f_i$ 多项式⼀共有70个，由于指数 $e=3$，所以 $f_i$ 为九次同余⽅程，可以通

过中国剩余定理将70个同余⽅程合并成⼀个，这时得到的是⼀个系数很⼤，模数N也很⼤的九次同余⽅程，这

时可以通过格基规约算法得到模这个很⼤的N的意义下的、较⼩的系数，当真实系数⼩于N时，同余⽅程便可

以直接看作等号连接的⽅程，即可很⽅便的求解⼀个较⼩的根（明⽂）。

⾮预期：在使⽤CRT合并成⼀个同余式之后，由于明⽂m相对n过于⼩，可以⽤

coppersmith求解出根。

from functools import reduce
from Crypto.Util.number import * 
f = open("data", "r") 
ciphertext = [] 
a, b, n = [], [], [] 
for i in range(70): 
	ci, ai, bi, ni = [int(num) for num in f.readline().strip().split(", ")] 
	ciphertext.append(ci) 
	a.append(ai) 
	b.append(bi) 
	n.append(ni) 
	e = 3 
	deg = 9 
	coeffi = [] 
	for i in range(70): 
		E = EllipticCurve(IntegerModRing(n[i]), [a[i], b[i]]) 
		P.<m> = PolynomialRing(Zmod(n[i])) 
		f = ciphertext[i]*E._multiple_x_denominator(e, m) - E._multiple_x_numerator(e, m) 
		coeffi.append(f.coefficients(sparse=False)) 
		large_coeffi = [crt([int(coeffi[j][i]) for j in range(70)], [n[j] for j in range(70)]) for i in range(deg+1)] 
		N_bitlength = sum([n[i].bit_length() for i in range(70)]) 
		min_n = min(n) 
		N = reduce(lambda x, y: x*y, n) 
		Sc = large_coeffi
var("x") 
assume(x, 'integer') 
f = Sc[9]*x^9+Sc[8]*x^8+Sc[7]*x^7+Sc[6]*x^6+Sc[5]*x^5+Sc[4]*x^4+Sc[3]*x^3+Sc[2]*x^2 +Sc[1]*x+Sc[0] 
lat = [] 
lat.append([large_coeffi[i]*min_n**i for i in range(deg+1)]+[1/(deg+1)]) 
for i in range(deg+1): 
	lat.append([((min_n**j)*N if (i==j) else 0) for j in range(deg+1)]+[0]) 
	Mat = matrix(lat) 
	Mat_LLL = Mat.LLL() 
for lin in range(deg): 
	Sc = [int(i) for i in Mat_LLL[lin]] 
	Sc = [(Sc[i]//(min_n**i)) for i in range(deg+1)] 
	var("x") 
	assume(x, 'integer') 
	f = Sc[9]*x^9+Sc[8]*x^8+Sc[7]*x^7+Sc[6]*x^6+Sc[5]*x^5+Sc[4]*x^4+Sc[3]*x^3+Sc[2]*x^2 +Sc[1]*x+Sc[0] 
	print(factor(f)) 
	break 
''' 
m = 3088969433059681806521206959873975785377227976800172674306727155831805513908352148702210247662586117242206183337522557 
print(long_to_bytes(m)) 
'''

运行报错，待解决

Hasted广播攻击

使用不同但互质的模数n，相同的指数e、加密e个明文得到e个密文

$ c_{i} = (a_{i}x + b{i})^{e} \bmod n_{i} , i = 1,2,\cdots,e $

e个式子：$ (a_{i}x + b{i})^{e} - c_{i} \equiv 0 \bmod n_{i} , i = 1, 2, \cdots , e $

$ \because n_{i}互素 和 中国剩余定理 $

$ \therefore P(x) \equiv 0 \bmod M , M = \prod_{i=1}^{e} n_{i} $

$ \because P(x)有唯一解，且满足LLL算法的约束条件 $

$ \therefore 可以用coppersmith的smallroots求解 $

# sage
def linearPaddingHastads1(cArray, nArray, aArray, bArray, e=3, eps=1/8):
    if(len(cArray) == len(nArray) == len(aArray) == len(bArray) == e):
        for i in range(e):
            cArray[i] = Integer(cArray[i])
            nArray[i] = Integer(nArray[i])
            aArray[i] = Integer(aArray[i])
            bArray[i] = Integer(bArray[i])
        TArray = [-1]*e
        for i in range(e):
            arrayToCRT = [0]*e
            arrayToCRT[i] = 1
            TArray[i] = crt(arrayToCRT, nArray)
        P.<x> = PolynomialRing(Zmod(prod(nArray)))
        gArray = [-1]*e
        for i in range(e):
            gArray[i] = TArray[i]*(pow(aArray[i]*x + bArray[i], e) - cArray[i])
        g = sum(gArray)
        g = g.monic()
        # Use Sage's inbuilt coppersmith method
        roots = g.small_roots(epsilon=eps)
        if(len(roots) == 0):
            print("No Solutions found")
            return -1
        return roots[0]
    else:
        print("CiphertextArray, ModulusArray, and the linear padding arrays need to be of the same length," +
              "and the same size as the public exponent")

def linearPaddingHastads2(cArray, nArray, aArray, bArray, e=3, eps=1/8):
    cnt = e
    PR = PolynomialRing(ZZ, 'x')
    x = PR.gen()
    Fs = []
    for i in range(cnt):
        f = PR((A[i]*x + B[i])**e - Cs[i])
        ff = f.change_ring(Zmod(Ns[i]))
        ff = ff.monic()
        f = ff.change_ring(ZZ)
        Fs.append(f)
    F = crt(Fs, Ns)
    M = reduce(lambda x, y: x * y, Ns)
    FF = F.change_ring(Zmod(M))
    m = FF.small_roots(epsilon=1/16)
    if m:
        return m[0]
    else:
        return None