杂记(三)

这篇文章主要记录期末月做的一些赛题

R3CTF

r0system

审计代码发现，可以自己注册个账号完成登录

登录之后，在修改密码那里居然可以改所有用户的密码

def R0System(USERNAME): 
    global login_tag,PublicChannels
    option = int(input((b"Hello "+ USERNAME + b",do you need any services? ").decode()))
    if option == 1:
        username     = bytes.fromhex(input(b"Username[HEX]: ".decode())) 
        new_password = bytes.fromhex(input(b"New Password[HEX]: ".decode()))
        tag,msg = USER.reset_password(username,new_password)
        print(msg.decode())

那思路就是改Bob的密码，然后得到Bob的私钥，再求Alice和Bob的会话密钥完成解密

exp.py

class Curve: 
    def __init__(self):
        # Nist p-256
        self.p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
        self.a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
        self.b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
        self.G = (0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 
                  0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
        self.n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551

    def add(self,P, Q):
        if (P == (0, 0)):
            return Q
        elif (Q == (0, 0)):
            return P
        else: 
            x1, y1 = P
            x2, y2 = Q
            if ((x1 == x2) & (y1 == -y2)):
                return ((0, 0))
            else:
                if (P != Q):
                    l = (y2 - y1) * pow(x2 - x1, -1, self.p)
                else:
                    l = (3 * (x1**2) + self.a) * pow(2 * y1, -1, self.p)
            x3 = ((l**2) - x1 - x2) % self.p
            y3 = (l * (x1 - x3) - y1) % self.p
            return x3, y3

    def mul(self, n , P):
        Q = P
        R = (0, 0)
        while (n > 0):
            if (n % 2 == 1):
                R = self.add(R, Q)
            Q = self.add(Q, Q)
            n = n // 2
        return R
    
    
from Crypto.Util.number import long_to_bytes,bytes_to_long,isPrime
from hashlib import md5
from Crypto.Cipher import AES

curve = Curve()
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
# E = EllipticCurve(GF(p),[a,b])
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551

G = (0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
encflag = "e3b70f0fc960e3cc28f5b02667e5483f6dd6cc267435d33cd222071f949da4a9fc383ad4282a28c81c8b106546b0dc5e61b0908f6d0edb07a2072a9f3b3c0a2aa4b990d1a903b33e5921336f68533b7fce5cd401816016e369e6941336dcf441"
tmpA = "ce760c0651d6f4e7466173d5bebe4803af2b0aea75ebb1948785e50fd1c911f18f887c172dd64d979fc501b13c5e76418e24920671610563bb0233fc1cf1a789"
tmpB = "fc7ac593d124c0f5c10ed04623c5d5e80bc4af3215956cba0dcf27d9a6a7e11b4412f38ef83403e9a844e11fbc349b05795808a38cb90b99dbb165c54aa38ba2"

Ax = bytes.fromhex(tmpA)[:32]
Ay = bytes.fromhex(tmpA)[32:]
Bx = bytes.fromhex(tmpB)[:32]
By = bytes.fromhex(tmpB)[32:]
A = (bytes_to_long(Ax),bytes_to_long(Ay))
B = (bytes_to_long(Bx),bytes_to_long(By))

b = 0x4627ff9ebfc02af8e8b2eb2a276ac028d874de10df417221d49d838bc6a5e733
KEY = md5(str(curve.mul(b,A)).encode()).digest()

aes = AES.new(KEY,AES.MODE_ECB)
flag = aes.decrypt(bytes.fromhex(encflag))
print(flag)
# R3CTF{p3rm1$sions_n33d_Att3nt1%n!_NeXt_l3vE1_l1Nk_1s_https://reurl.cc/Vz7GzZ_a702ba611b24}

r1system

上一题做完之后，拿到这题的附件

审计完代码发现，这题和上题区别在于，这题初始化只有Alice一个账号，而且我们居然能注册Bob的账号

注册之后和Alice交换密钥就好了

exp

from Crypto.Util.number import long_to_bytes,bytes_to_long,isPrime
from hashlib import md5
from Crypto.Cipher import AES


encflag = "b421ed525e970681412ade94b2c9eeb5365d0cec75fed997525ce31fe8878dac9f4ea3992a5e54c27acfd81d456cc8ae27ff666c470637067e05d73cd53d2da1"
key = "4b257eda7fda459a7844014378f08b8e"

aes = AES.new(bytes.fromhex(key),AES.MODE_ECB)
flag = aes.decrypt(bytes.fromhex(encflag))
print(flag)
# R3CTF{pRN9_I1k3_qc9_1S_3Z_To_50IVe_38e5d6dd3eaa}

CryptoCTF

另外一篇博客

熊猫杯

client.py

from Crypto.Util.number import *
from socket import *
from secret import flag
from random import randint
import os

class Oblivious_Transfer():
    def __init__(self,host,port):
        self.client = socket(AF_INET,SOCK_STREAM)
        self.client.connect((host,port))

    def recv_para1(self):
        self.client.send(b"Give me RSA public key")
        self.n1, self.e1 = [int(i) for i in self.client.recv(2048).decode().split('\n')]
        print(f"n1 = {self.n1}")
        print(f"e1 = {self.e1}")

    def recv_para2(self):
        self.client.send(b"Give me RSA public key")
        self.n2, self.e2 = [int(i) for i in self.client.recv(2048).decode().split('\n')]
        print(f"n2 = {self.n2}")
        print(f"e2 = {self.e2}")

    def transfer1(self):
        self.client.send(b"Give me x")
        self.x1 = [int(i) for i in self.client.recv(2048).decode().split('\n')]
        #self.b = randint(0, 1)
        self.k1 = randint(1, self.n1)
        #v = (pow(self.k1, self.e1, self.n1) + self.x1[self.b]) % self.n1
        #self.client.send(str(v).encode())
        self.client.send(str(self.k1).encode())
        self.m1 = [int(i) for i in self.client.recv(2048).decode().split('\n')]
        print(f"x1 = {self.x1}")
        print(f"m1 = {self.m1}")

    def transfer2(self):
        self.client.send(b"Give me x")
        self.x2 = [int(i) for i in self.client.recv(2048).decode().split('\n')]
        #self.b = randint(0, 2)
        self.k2 = randint(1, self.n2)
        #v = (pow(self.k2, self.e2, self.n2) + self.x2[self.b]) % self.n2
        #self.client.send(str(v).encode())
        self.client.send(str(self.k2).encode())
        self.m2 = [int(i) for i in self.client.recv(2048).decode().split('\n')]
        print(f"x2 = {self.x2}")
        print(f"m2 = {self.m2}")

    def close(self):
        self.client.close()

OT = Oblivious_Transfer("127.0.0.1", 3333)
try:
    OT.recv_para1()
    OT.transfer1()

    OT.recv_para2()
    OT.transfer2()
except:
    OT.close()

'''
n1 = 11271769636481167201792947869036553992227573210518633030219178803383349111691460202925344961485630519396298556298353185729133425424986251013234507574460564567554706523170816213012134101324728485027759939177868268886490620475377111559309854971172536072912492915397424686135393068344370029572892256194814415101890916563130328570803042252136741183269883671849873603956230726294410435185435014274882048506167456427852608126478349488290872256072029149848433197043410728314084380999316723835302043375017580973032065204288589969252813061043853493941665391349852606781487173854475699462142399025313772992266906492948457481343
e1 = 3
x1 = [9515572144467353102693379312418710955214891592376652277288115734279056734333735433842688458064791727513305863861235023479729328042101083071837571497065148511710639753106684253478831875505030519724899081680516833763198547371577091213443181418357026416055217075672599840276222008249647801652670192401687584389238718466389175705227396073077728212161850918020236614953688339567726286493333833192267092340593829218909756169268170625006694216875605112065267454732423903631737275763224769800017009573049312062340144144829220945642953262132895898315831950065807615456546917913668105293794016444579372988387899070119905188852, 1892034120103884655057748481218744968570886603116770464293986717297275954889143292301699430583870055377213531296557183365836328935582605537911332825510113738818872104690943672685087209698335996263632901023795785958711815234874952640699783061740546868363055353091127902362863942669248423826595254894726944833887263833323809149528895833061490548685459108186763244472560195193139974039077951072951624681272257192017679341819986081273918682657482308353776379587845617737285532310255049963865808295659252810449272607145518278622472711380742500844288926728181235765064078778435360592122889548497811844849141090787687431691]
m1 = [6016241168918008003676308976207100363787886056310414524692817266526816044605861589333265680725516797725157476881964627121341856194031952078224223712707203444145810288009516867166444302906259425595314875099543375758202468607877956110531218864874778701312073626804583736300557519077867674205675297659120854857631861820501341218694648899186245660067972817620811237063040820817563464199716096063261214384822141532599155146824331413684812783001628935032487957306346174008702256595545954862755182240217576044236510482955069793116079796093428542806091985359518377611477601123779397291583947727903087310885258578166713562127, 5440147501940638137024850606017297210337534677408842136379920848781712980462447118877171733606863014259702536891618925774163741294802932568915293766589177284295703266970860357526016987325665154313719066965567249222221131682926705272951530070261409867083615183965724021333853123572753014882129436586571389423155293377948368049140838120533008304139511510566634163176216591511566937364023875888461854372432939610104040445984493844672803393249479769170488441311099318570005369329133726459281759202562040178972797271360551614266347925035798206639977703364862505440147494902280456168540628714355582075950777307761924432387]
n2 = 13734553138242318628382054742480981343446984988191688662254986243627157625179176065241156011696302206618179554684039418464583144145503176708791330560172722535768542184698066880611009153616062090684034664602606266851696293869899452519578725665110985148196543998607394795861120331954638386927099371326884429866634685812799207305104476545524154915042406729289612658166510017492482175075872284724725422863660604254919264739710275468027278899773185461791413509280443599747367129337405961244474327733607586747648790915994322826728272773783653766560606552040854271186948727715576352830926898026093434984246855183310757045761
e2 = 97
x2 = [13177195145643985162369622498401365177499138154538273683105144116544719466309962486453254331776465984111024384000978936709809981151700299715082451736814113126287335911167543580326081550513657585920705158990979388476560541554360224739435428369017964910714020825020400206978492083575209281469099197416561057829071411270433371623496230236473419547584375357556353533487865301248950946032111351087126169856720042454654832226420081909659506864195491980123873801598391036249027256808516343923925600130215162930220263798094559698140483803320057081107578634042891033997459769087238265628113428210401614417877839230901721993190, 6087668416419425621015217192937881819030086776814461931461321271071632965704332777171900656493718038405650018773284906392054768417180630397123329675678721202895156479498192567976488835849134098984496538043518882047967632186092698690848611693438041802874429890978003588117644629011459601875026269618173841010295947617126507755463408314735056141532883079433786701501106150571651039383128288126543960497006195953471865106598447153220760899089004772873548377773392286170683824466138705674297182685522941020265251198373775479428578340308681511331066572161101438312245374528237712280314548370382811282427949209246902963620]
m2 = [11290088192896104506026832060270527943714366880404242912266063784753126354203886059118599709669598729492075209588587167909865752372998401224088902550832115846922950445881033989219174580290127597931540821558287876108098891608071532321402919702498057050600028620041146727752759548708970938132742356572135342729734097482396575542041618189798845322991442136889598236510334924501541556553680371235401907549785446331539870340463389985682807901483008146184213709636864164058105540385607059315722869586747109233390594619151596441257862747687967610987191500891685999700118692739878206205390683771336361205725982750841624412918, 13297923293604079904865691526854689771243166342933215235463378384491550135554561777664960232137603383114093048818781509117309259419714741409995439792770006827393488190799203124259891829424051546917028377316926517036925667257317044743094940629506839160375855343993956627134396913916798323848609907197075057202723651440732344941034655107043117917579554777531225809712600877171322938484588653102197119270286456014097076345973054360242768465566465700893203405936053400775455573738231554838583225080952941328332237618198730448032110880353626965942852413612822837453591096974975301303294918593974328897924663396162439300901]
'''

server.py

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from socket import *
from secret import flag
from random import randint
from gmpy2 import invert, gcd
import os

length = len(flag)
flag1 = flag[:length//2]
flag2 = flag[length//2:]

class Oblivious_Transfer():
    def __init__(self,host,port):
        self.server = socket(AF_INET,SOCK_STREAM)
        self.server.bind((host,port))
        self.server.listen(5)
        self.connection, self.addr = self.server.accept()
    
    def keygen1(self):
        while True:
            p = getPrime(1024)
            q = getPrime(1024)
            e = 3
            n = p * q
            phi = (p-1)*(q-1)
            if gcd(e, phi) == 1:
                d = invert(e, phi)
                self.n1 = n
                self.e1 = e
                self.d1 = d
                return

    def keygen2(self):
        while True:
            p = getPrime(1024)
            q = getPrime(1024)
            e = 97
            n = p * q
            phi = (p-1)*(q-1)
            if gcd(e, phi) == 1:
                d = invert(e, phi)
                self.n2 = n
                self.e2 = e
                self.d2 = d
                return

    def gen_msg1(self):
        self.msg1 = [bytes_to_long(flag1), bytes_to_long(os.urandom(length//2))]

    def gen_msg2(self):
        self.c = [randint(1, self.n2) for i in range(2)]
        self.msg2 = [bytes_to_long(pad(flag2, 256)), self.c[0] * bytes_to_long(pad(flag2, 256)) + self.c[1], bytes_to_long(os.urandom(length//2))]
        print(f"c = {self.c}")

    def send_para1(self):
        self.connection.recv(2048)
        self.connection.send(str(self.n1).encode() + b'\n' + str(self.e1).encode())

    def send_para2(self):
        self.connection.recv(2048)
        self.connection.send(str(self.n2).encode() + b'\n' + str(self.e2).encode())

    def transfer1(self):
        self.connection.recv(2048)
        self.x1 = [randint(1, self.n1) for i in range(2)]
        self.connection.send(str(self.x1[0]).encode() + b'\n' + str(self.x1[1]).encode())
        v1 = int(self.connection.recv(2048).decode())
        self.m1 = [(pow(v1-self.x1[i], self.d1, self.n1) + self.msg1[i]) % self.n1 for i in range(2)]
        self.connection.send(str(self.m1[0]).encode() + b'\n' + str(self.m1[1]).encode())

    def transfer2(self):
        self.connection.recv(2048)
        self.x2 = [randint(1, self.n2) for i in range(2)]
        self.connection.send(str(self.x2[0]).encode() + b'\n' + str(self.x2[1]).encode())
        v2 = int(self.connection.recv(2048).decode())
        print(f"v2 = {v2}")
        self.m2 = [(pow(v2-self.x2[i], self.d2, self.n2) + self.msg2[i]) % self.n2 for i in range(2)]
        self.connection.send(str(self.m2[0]).encode() + b'\n' + str(self.m2[1]).encode())

    def close(self):
        self.server.close()

OT = Oblivious_Transfer("127.0.0.1", 3333)

try:
    OT.keygen1()
    OT.gen_msg1()
    OT.send_para1()
    OT.transfer1()

    OT.keygen2()
    OT.gen_msg2()
    OT.send_para2()
    OT.transfer2()
except:
    OT.close()

'''
c = [2022192084163865871637311910190343009806372281260940433264866710576717827000158190013454140869282023553794168299850642713592857046603901804667940047118351375526819434245929363285575321841139031828203969945166801239181091856967945653548638281912992865859782543006093627628764190870048182733564610346559175554351590756572067638680287831888951790549721647896128434643949839982021154615115260457999786151004733151130820602433196485192091297036565179140159868992152310647228915941684271200707824836388347153359567736106504118830380335535571497974547855922884383469780130087191722420344937756494122346487016566419242463836, 12061552506303089886042745624408653176981782225020423963019198845243742139258023869466665561793608045001319021047887667664174994585869340313951796548176269089114160706384746387983277073112591591489643976442622321188641202129622786824693293150098394659731881683945896467114040450861544761586718952331369001004695294268894235852363740831011251046468659589566501557902013744612394168830044111638387497950139803719642714677584615407052702028855832555056064595619857064644590245323361565888668910950428292688990851782269368022834514035734196544300120061524133712573144079293439936276463509498262847888571155492592609260783]
v2 = 9556276713294185634675025767802869929252472183681399946558259127635089951399817649411122499036657904914953334191629273438214371861747375930220930123236040473592720606113932507502872050616210539047321307830911690987874269273684519795136175561107095807358688729096068293698083610276557300656827563421114987688852668095314933405088107467416611145574761738655696672560862813137945205091832198111391817949039251665825121659323773270436391580589841573178391221735428798318886660824941824216932260996644044749424023313841093829840154123672637916095508058599701154434489213872161152359221137791753598589303710126033417598315
'''

part1

由题意得
$$
m_{11} \equiv (v_1 - x_{11})^{d_1} + msg_0 \mod n_1
$$

$$
m_{12} \equiv (v_1 - x_{12})^{d_1} + msg_1 \mod n_1
$$

简单化简可以得到
$$
(m_{11}-msg_0)^3 \equiv v_1 - x_{11} \mod n_1
$$

$$
(m_{12}-msg_1)^3 \equiv v_1 - x_{12} \mod n_1
$$

展开
$$
m_{11}^{3} - 3m_{11}^2msg_0 + 3m_{11}msg_0^2 - msg_0^3 \equiv v_1 - x_{11} \mod n_1
$$

$$
m_{12}^{3} - 3m_{12}^2msg_1 + 3m_{12}msg_1^2 - msg_1^3 \equiv v_1 - x_{12} \mod n_1
$$

两个式子相减得到
$$
(m_{11} - m_{12})^3 - 3(m_{11}^2msg_0 -m_{12}^2msg_1) + 3(m_{11}msg_0^2-m_{12}msg_1^2) \equiv (x_{12}-x_{11}) \mod n_1
$$
不展开也行(

msg0和msg1都是168bit，用二元copper即可

part2

由题意得

$$
m_{21} \equiv (v_2 - x_{21})^{d_2} + msg_2 \mod n_2\
m_{22} \equiv (v_2 - x_{22})^{d_2} + (c_{0}\times msg_2 + c_1) \mod n_2
$$

简单化简得
$$
m_{21} - msg \equiv (v_2 - x_{21})^{d_2} \mod n_2
$$

$$
m_{22} - (c_0\times msg + c_1) \equiv (v_2 - x_{22})^{d_2} \mod n_2
$$

两边乘方得到
$$
(m_{21} - msg)^{e_2} \equiv (v_2 - x_{21}) \mod n_2\
$$

$$
(m_{22} - (c_0\times msg + c_1))^{e_2} \equiv (v_2 - x_{22}) \mod n_2
$$

然后相关消息攻击即可

exp

# sage
from Crypto.Util.number import *
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

c = [2022192084163865871637311910190343009806372281260940433264866710576717827000158190013454140869282023553794168299850642713592857046603901804667940047118351375526819434245929363285575321841139031828203969945166801239181091856967945653548638281912992865859782543006093627628764190870048182733564610346559175554351590756572067638680287831888951790549721647896128434643949839982021154615115260457999786151004733151130820602433196485192091297036565179140159868992152310647228915941684271200707824836388347153359567736106504118830380335535571497974547855922884383469780130087191722420344937756494122346487016566419242463836, 12061552506303089886042745624408653176981782225020423963019198845243742139258023869466665561793608045001319021047887667664174994585869340313951796548176269089114160706384746387983277073112591591489643976442622321188641202129622786824693293150098394659731881683945896467114040450861544761586718952331369001004695294268894235852363740831011251046468659589566501557902013744612394168830044111638387497950139803719642714677584615407052702028855832555056064595619857064644590245323361565888668910950428292688990851782269368022834514035734196544300120061524133712573144079293439936276463509498262847888571155492592609260783]
v2 = 9556276713294185634675025767802869929252472183681399946558259127635089951399817649411122499036657904914953334191629273438214371861747375930220930123236040473592720606113932507502872050616210539047321307830911690987874269273684519795136175561107095807358688729096068293698083610276557300656827563421114987688852668095314933405088107467416611145574761738655696672560862813137945205091832198111391817949039251665825121659323773270436391580589841573178391221735428798318886660824941824216932260996644044749424023313841093829840154123672637916095508058599701154434489213872161152359221137791753598589303710126033417598315
n1 = 11271769636481167201792947869036553992227573210518633030219178803383349111691460202925344961485630519396298556298353185729133425424986251013234507574460564567554706523170816213012134101324728485027759939177868268886490620475377111559309854971172536072912492915397424686135393068344370029572892256194814415101890916563130328570803042252136741183269883671849873603956230726294410435185435014274882048506167456427852608126478349488290872256072029149848433197043410728314084380999316723835302043375017580973032065204288589969252813061043853493941665391349852606781487173854475699462142399025313772992266906492948457481343
e1 = 3
x1 = [9515572144467353102693379312418710955214891592376652277288115734279056734333735433842688458064791727513305863861235023479729328042101083071837571497065148511710639753106684253478831875505030519724899081680516833763198547371577091213443181418357026416055217075672599840276222008249647801652670192401687584389238718466389175705227396073077728212161850918020236614953688339567726286493333833192267092340593829218909756169268170625006694216875605112065267454732423903631737275763224769800017009573049312062340144144829220945642953262132895898315831950065807615456546917913668105293794016444579372988387899070119905188852, 1892034120103884655057748481218744968570886603116770464293986717297275954889143292301699430583870055377213531296557183365836328935582605537911332825510113738818872104690943672685087209698335996263632901023795785958711815234874952640699783061740546868363055353091127902362863942669248423826595254894726944833887263833323809149528895833061490548685459108186763244472560195193139974039077951072951624681272257192017679341819986081273918682657482308353776379587845617737285532310255049963865808295659252810449272607145518278622472711380742500844288926728181235765064078778435360592122889548497811844849141090787687431691]
m1 = [6016241168918008003676308976207100363787886056310414524692817266526816044605861589333265680725516797725157476881964627121341856194031952078224223712707203444145810288009516867166444302906259425595314875099543375758202468607877956110531218864874778701312073626804583736300557519077867674205675297659120854857631861820501341218694648899186245660067972817620811237063040820817563464199716096063261214384822141532599155146824331413684812783001628935032487957306346174008702256595545954862755182240217576044236510482955069793116079796093428542806091985359518377611477601123779397291583947727903087310885258578166713562127, 5440147501940638137024850606017297210337534677408842136379920848781712980462447118877171733606863014259702536891618925774163741294802932568915293766589177284295703266970860357526016987325665154313719066965567249222221131682926705272951530070261409867083615183965724021333853123572753014882129436586571389423155293377948368049140838120533008304139511510566634163176216591511566937364023875888461854372432939610104040445984493844672803393249479769170488441311099318570005369329133726459281759202562040178972797271360551614266347925035798206639977703364862505440147494902280456168540628714355582075950777307761924432387]
n2 = 13734553138242318628382054742480981343446984988191688662254986243627157625179176065241156011696302206618179554684039418464583144145503176708791330560172722535768542184698066880611009153616062090684034664602606266851696293869899452519578725665110985148196543998607394795861120331954638386927099371326884429866634685812799207305104476545524154915042406729289612658166510017492482175075872284724725422863660604254919264739710275468027278899773185461791413509280443599747367129337405961244474327733607586747648790915994322826728272773783653766560606552040854271186948727715576352830926898026093434984246855183310757045761
e2 = 97
x2 = [13177195145643985162369622498401365177499138154538273683105144116544719466309962486453254331776465984111024384000978936709809981151700299715082451736814113126287335911167543580326081550513657585920705158990979388476560541554360224739435428369017964910714020825020400206978492083575209281469099197416561057829071411270433371623496230236473419547584375357556353533487865301248950946032111351087126169856720042454654832226420081909659506864195491980123873801598391036249027256808516343923925600130215162930220263798094559698140483803320057081107578634042891033997459769087238265628113428210401614417877839230901721993190, 6087668416419425621015217192937881819030086776814461931461321271071632965704332777171900656493718038405650018773284906392054768417180630397123329675678721202895156479498192567976488835849134098984496538043518882047967632186092698690848611693438041802874429890978003588117644629011459601875026269618173841010295947617126507755463408314735056141532883079433786701501106150571651039383128288126543960497006195953471865106598447153220760899089004772873548377773392286170683824466138705674297182685522941020265251198373775479428578340308681511331066572161101438312245374528237712280314548370382811282427949209246902963620]
m2 = [11290088192896104506026832060270527943714366880404242912266063784753126354203886059118599709669598729492075209588587167909865752372998401224088902550832115846922950445881033989219174580290127597931540821558287876108098891608071532321402919702498057050600028620041146727752759548708970938132742356572135342729734097482396575542041618189798845322991442136889598236510334924501541556553680371235401907549785446331539870340463389985682807901483008146184213709636864164058105540385607059315722869586747109233390594619151596441257862747687967610987191500891685999700118692739878206205390683771336361205725982750841624412918, 13297923293604079904865691526854689771243166342933215235463378384491550135554561777664960232137603383114093048818781509117309259419714741409995439792770006827393488190799203124259891829424051546917028377316926517036925667257317044743094940629506839160375855343993956627134396913916798323848609907197075057202723651440732344941034655107043117917579554777531225809712600877171322938484588653102197119270286456014097076345973054360242768465566465700893203405936053400775455573738231554838583225080952941328332237618198730448032110880353626965942852413612822837453591096974975301303294918593974328897924663396162439300901]

def franklinReiter(n):
    PR.<m> = PolynomialRing(Zmod(n))
    g1 = (m2[0] - m)^97 - (v2 - x2[0])
    g2 = (m2[1] - (c[0]*m + c[1]))^97 - (v2 - x2[1])
    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]

R.<M0,M1> = PolynomialRing(Zmod(n1))
f = (m1[0] - M0)^3 - (m1[1] - M1)^3 + x1[0] - x1[1]
res = small_roots(f,(2^167,2^167),m=2,d=4)
msg1,_ = res[0]
flag1 = long_to_bytes(int(msg1))
msg2 = franklinReiter(n2)
flag2 = long_to_bytes(int(msg2))
print(flag1 + flag2)
# flag{fcdb818c-0db0-348f-4145-87d8051cc3c5}

UIUCTF

Determined

server.py

from Crypto.Util.number import bytes_to_long, long_to_bytes
from itertools import permutations
from SECRET import FLAG, p, q, r



def inputs():
    print("[DET] First things first, gimme some numbers:")
    M = [
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
    ]
    try:
        M[0][0] = p
        M[0][2] = int(input("[DET] M[0][2] = "))
        M[0][4] = int(input("[DET] M[0][4] = "))

        M[1][1] = int(input("[DET] M[1][1] = "))
        M[1][3] = int(input("[DET] M[1][3] = "))

        M[2][0] = int(input("[DET] M[2][0] = "))
        M[2][2] = int(input("[DET] M[2][2] = "))
        M[2][4] = int(input("[DET] M[2][4] = "))

        M[3][1] = q
        M[3][3] = r

        M[4][0] = int(input("[DET] M[4][0] = "))
        M[4][2] = int(input("[DET] M[4][2] = "))
    except:
        return None
    return M

def handler(signum, frame):
    raise Exception("[DET] You're trying too hard, try something simpler")

def fun(M):
    def sign(sigma):
        l = 0
        for i in range(5):
            for j in range(i + 1, 5):
                if sigma[i] > sigma[j]:
                    l += 1
        return (-1)**l

    res = 0
    for sigma in permutations([0,1,2,3,4]):
        curr = 1
        for i in range(5):
            curr *= M[sigma[i]][i]
        res += sign(sigma) * curr
    return res

def main():
    print("[DET] Welcome")
    M = inputs()
    if M is None:
        print("[DET] You tried something weird...")
        return

    res = fun(M)
    print(f"[DET] Have fun: {res}")

if __name__ == "__main__":
    main()

gen.py

from SECRET import FLAG, p, q, r
from Crypto.Util.number import bytes_to_long
n = p * q
e = 65535
m = bytes_to_long(FLAG)
c = pow(m, e, n)
# printed to gen.txt
print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
"""
n = 158794636700752922781275926476194117856757725604680390949164778150869764326023702391967976086363365534718230514141547968577753309521188288428236024251993839560087229636799779157903650823700424848036276986652311165197569877428810358366358203174595667453056843209344115949077094799081260298678936223331932826351
e = 65535
c = 72186625991702159773441286864850566837138114624570350089877959520356759693054091827950124758916323653021925443200239303328819702117245200182521971965172749321771266746783797202515535351816124885833031875091162736190721470393029924557370228547165074694258453101355875242872797209141366404264775972151904835111
"""

主要思路是利用server分解n

首先有个固定了部分值的矩阵M，?是我们要输入的值
$$
M =
\begin{pmatrix}
p & 0 & ? & 0 & ?\\
0 & ? & 0 & ? & 0\\
? & 0 & ? & 0 & ?\\
0 & q & 0 & r & 0\\
?&0&?&0&0
\end{pmatrix}
$$
第一反应是全填1，此时M如下
$$
M =
\begin{pmatrix}
p & 0 & 1 & 0 & 1\\
0 & 1 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1\\
0 & q & 0 & r & 0\\
1 & 0 & 1 & 0 & 0
\end{pmatrix}
$$
但这个时候会发现curr一定是0，但我们可以找出curr不为0的排列有

(0, 1, 4, 3, 2)
(0, 3, 4, 1, 2)
(2, 1, 4, 3, 0)
(2, 3, 4, 1, 0)
(4, 1, 0, 3, 2)
(4, 1, 2, 3, 0)
(4, 3, 0, 1, 2)
(4, 3, 2, 1, 0)

对于每个排列来看，得到的sign()值分别为

-1
1
1
-1
1
-1
-1
1

得到的curr如下

pr
pq
r
q
r
r
q
q

那么得到的res就是
$$
-pr + pq +r-q+r-r-q+q
$$
即
$$
pq-pr-q+r
$$
这对我们分解n没什么关系，所以，我们的目的就是输入什么样的值，能够让res仅仅与p,q有关

经过测试发现

输入1,1,0,1,1,1,1,1,1，此时M如下
$$
M =
\begin{pmatrix}
p & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1\\
0 & q & 0 & r & 0\\
1 & 0 & 1 & 0 & 0
\end{pmatrix}
$$
此时输出的$res = pq-q$

利用这个来求q，即完成了n的分解

exp

from Crypto.Util.number import *

res = 158794636700752922781275926476194117856757725604680390949164778150869764326023702391967976086363365534718230514141547968577753309521188288428236024251993827021237309488607099396251558718631178638562077858262514078537543492352337967199580389883367433729078970596973723167029400868564841912135610784434189991222
n = 158794636700752922781275926476194117856757725604680390949164778150869764326023702391967976086363365534718230514141547968577753309521188288428236024251993839560087229636799779157903650823700424848036276986652311165197569877428810358366358203174595667453056843209344115949077094799081260298678936223331932826351
e = 65535
c = 72186625991702159773441286864850566837138114624570350089877959520356759693054091827950124758916323653021925443200239303328819702117245200182521971965172749321771266746783797202515535351816124885833031875091162736190721470393029924557370228547165074694258453101355875242872797209141366404264775972151904835111

q = n - res
p = n // q
d = inverse(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(int(m)))

回过头来可以发现其实fun就是个计算行列式的函数。

Without a Trace

server.py

import numpy as np
from Crypto.Util.number import bytes_to_long
from itertools import permutations
from SECRET import FLAG


def inputs():
    print("[WAT] Define diag(u1, u2, u3. u4, u5)")
    M = [
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
    ]
    for i in range(5):
        try:
            M[i][i] = int(input(f"[WAT] u{i + 1} = "))
        except:
            return None
    return M

def handler(signum, frame):
    raise Exception("[WAT] You're trying too hard, try something simpler")

def check(M):
    def sign(sigma):
        l = 0
        for i in range(5):
            for j in range(i + 1, 5):
                if sigma[i] > sigma[j]:
                    l += 1
        return (-1)**l

    res = 0
    for sigma in permutations([0,1,2,3,4]):
        curr = 1
        for i in range(5):
            curr *= M[sigma[i]][i]
        res += sign(sigma) * curr
    return res

def fun(M):
    f = [bytes_to_long(bytes(FLAG[5*i:5*(i+1)], 'utf-8')) for i in range(5)]
    F = [
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
    ]
    for i in range(5):
        F[i][i] = f[i]

    try:
        R = np.matmul(F, M)
        return np.trace(R)

    except:
        print("[WAT] You're trying too hard, try something simpler")
        return None

def main():
    print("[WAT] Welcome")
    M = inputs()
    if M is None:
        print("[WAT] You tried something weird...")
        return
    elif check(M) == 0:
        print("[WAT] It's not going to be that easy...")
        return

    res = fun(M)
    if res == None:
        print("[WAT] You tried something weird...")
        return
    print(f"[WAT] Have fun: {res}")

if __name__ == "__main__":
    main()

过了check之后，服务器返回矩阵$M\times F$的迹

而$F$是以flag为对角元素的对角矩阵，我们只需要让$M$为单位矩阵然后传入$256^{20},256^{15},256^{10},256^5,1$，得到的值就是flag

Naptime

task.sage

from random import randint
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
import numpy as np

def get_b(n):
    b = []
    b.append(randint(2**(n-1), 2**n))
    for i in range(n - 1):
        lb = sum(b)
        found = False
        while not found:
            num = randint(max(2**(n + i), lb + 1), 2**(n + i + 1))
            if num > lb:
                found = True
                b.append(num)

    return b

def get_MW(b):
    lb = sum(b)
    M = randint(lb + 1, 2*lb)
    W = getPrime(int(1.5*len(b)))

    return M, W

def get_a(b, M, W):
    a_ = []
    for num in b:
        a_.append(num * W % M)
    pi = np.random.permutation(list(i for i in range(len(b)))).tolist()
    a = [a_[pi[i]] for i in range(len(b))]
    return a, pi


def enc(flag, a, n):
    bitstrings = []
    for c in flag:
        # c -> int -> 8-bit binary string
        bitstrings.append(bin(ord(c))[2:].zfill(8))
    ct = []
    for bits in bitstrings:
        curr = 0
        for i, b in enumerate(bits):
            if b == "1":
                curr += a[i]
        ct.append(curr)

    return ct

def dec(ct, a, b, pi, M, W, n):
    # construct inverse permuation to pi
    pii = np.argsort(pi).tolist()
    m = ""
    U = pow(W, -1, M)
    ct = [c * U % M for c in ct]
    for c in ct:
        # find b_pi(j)
        diff = 0
        bits = ["0" for _ in range(n)]
        for i in reversed(range(n)):
            if c - diff > sum(b[:i]):
                diff += b[i]
                bits[pii[i]] = "1"
        # convert bits to character
        m += chr(int("".join(bits), base=2))

    return m


def main():
    flag = 'uiuctf{I_DID_NOT_LEAVE_THE_FLAG_THIS_TIME}'

    # generate cryptosystem
    n = 8
    b = get_b(n)
    M, W = get_MW(b)
    a, pi = get_a(b, M, W)

    # encrypt
    ct = enc(flag, a, n)

    # public information
    print(f"{a =  }")
    print(f"{ct = }")

    # decrypt
    res = dec(ct, a, b, pi, M, W, n)

if __name__ == "__main__":
    main()

首先测了一下，发现直接用dec函数就可以解密，但我们缺少参数

各个参数并不是很大，可以用爆破的思路完成

我们首先求出所有12bit的素数W，再爆破M。用a求回那个被打乱的b，判断sorted(b)是不是一个超递增序列

然后再求排列pi，然后用dec解密

exp

from Crypto.Util.number import *
from tqdm import trange,tqdm
from gmpy2 import gcd
import numpy as np

def is_superincreasing(sequence):
    sum = 0
    for num in sequence:
        if num < sum:
            return False
        sum += num
    return True

def dec(ct, a, b, pi, M, W, n):
    # construct inverse permuation to pi
    pii = np.argsort(pi).tolist()
    m = ""
    U = pow(W, -1, M)
    ct = [c * U % M for c in ct]
    for c in ct:
        # find b_pi(j)
        diff = 0
        bits = ["0" for _ in range(n)]
        for i in reversed(range(n)):
            if c - diff > sum(b[:i]):
                diff += b[i]
                bits[pii[i]] = "1"
        # convert bits to character
        m += chr(int("".join(bits), base=2))

    return m

tmp = [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, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093]
a =  [66128, 61158, 36912, 65196, 15611, 45292, 84119, 65338]
ct = [273896, 179019, 273896, 247527, 208558, 227481, 328334, 179019, 336714, 292819, 102108, 208558, 336714, 312723, 158973, 208700, 208700, 163266, 244215, 336714, 312723, 102108, 336714, 142107, 336714, 167446, 251565, 227481, 296857, 336714, 208558, 113681, 251565, 336714, 227481, 158973, 147400, 292819, 289507]

for W in tqdm(tmp):
    for M in range(2**15,2**17+1):
        if gcd(M,W) == 1:
            b = []
            inv = inverse(W,M)
            for i in range(8):
                tmp_b = a[i] * inv % M
                b.append(tmp_b)
            b = sorted(b)
            if is_superincreasing(b) and 128 <= b[0] <= 256:
                print(b)
                print(f"W = {W}")
                print(f"M = {M}")
                pi = []
                origin_a = [num * W % M for num in b]      # 未打乱
                try:
                    for i in range(len(a)):
                        pi.append(origin_a.index(a[i]))
                    print(pi)
                    flag = dec(ct, a, b, pi, M, W, 8)
                    print(flag)
                    # uiuctf{i_g0t_sleepy_s0_I_13f7_th3_fl4g}
                    break
                except:
                    pass
        else:
            pass

春秋杯夏季赛

ezzzecc

cipher.txt

p = getPrime(256)
a = getPrime(256)
b = getPrime(256)
E = EllipticCurve(GF(p),[a,b])
m = E.random_point()
G = E.random_point()
k = getPrime(18)
K = k * G
r = getPrime(256)
c1 = m + r * K
c2 = r * G

cipher_left = s2n(flag[:len(flag)//2]) * m[0]   #flag的前半部分乘m[0]，所以只要用密文的除于m[0]即可得到flag前半部分
cipher_right = s2n(flag[len(flag)//2:]) * m[1]   #flag的后半部分点乘m[1]


p = koZP3YQAklARRNrmYfjxoKIAXegOcG4jMOmKb08uESOkCCn72d6UM2NWgefYPEMq4EJ1M0jKaqt02Guo5Ubccjqg4QZaaHbScREx38UMLQKwG0LcDd8VFX1zkobc1ZQn4L3DhKQrgJZI55todgOdJuHN532bxScAvOF26gJyQclPtRHn3M6SHrRCEXzzmszd68PJlLB6HaabrRrCW9ZoAYSZetM5jDBtNCJLpR0CBZUUk3Oeh2MZQu2vk8DZ1QqNG49hlxGfawp1FXvAZPdMwixzkhEQnbCDcOKzYyT6BZF2Dfd940tazl7HNOswuIpLsqXQ2h56guGngMeYfMXEZV09fsB3TE0N934CLF8TbZnzFzEkOe8TPTK2mWPVSrgmbsGHnxgYWhaRQWg3yosgDfrEa5qfVl9De41PVtTw024gltovypMXK5XMhuhogs0EMN7hkLapLn6lMj
p的格式为p={p}

a = 87425770561190618633288232353256495656281438408946725202136726983601884085917
b = 107879772066707091306779801409109036008421651378615140327877558014536331974777
K = (49293150360761418309411209621405185437426003792008480206387047056777011104939 : 43598371886286324285673726736628847559547403221353820773139325027318579443479)
G = (34031022567935512558184471533035716554557378321289293120392294258731566673565 : 74331715224220154299708533566163247663094029276428146274456519014761122295496)
私钥k小于1000000
c1 = (3315847183153421424358678117707706758962521458183324187760613108746362414091 : 61422809633368910312843316855658127170184420570309973276760547643460231548014)
c2 = (12838481482175070256758359669437500951915904121998959094172291545942862161864 : 60841550842604234546787351747017749679783606696419878692095419214989669624971)
cipher_left = 75142205156781095042041227504637709079517729950375899059488581605798510465939
cipher_right = 61560856815190247060747741878070276409743228362585436028144398174723191051815

点都在曲线上，利用
$$
y \equiv x^3 + ax + b \mod p
$$
我们随意取两个点
$$
x_i^3 + ax_i +b \equiv y_i^2 \mod p
$$
进行移项
$$
k_1p = x_1^3 + ax_1 + b - y_1^2
$$

$$
k_2p = x_2^3+ax_2 +b -y_2^2
$$

然后求公因数即可得到p，得到p之后爆破私钥

再利用$M = C_1-kC_2$求解

exp

# sage
from Crypto.Util.number import *
import gmpy2
from tqdm import *

a = 87425770561190618633288232353256495656281438408946725202136726983601884085917
b = 107879772066707091306779801409109036008421651378615140327877558014536331974777
K = (49293150360761418309411209621405185437426003792008480206387047056777011104939 , 43598371886286324285673726736628847559547403221353820773139325027318579443479)
G = (34031022567935512558184471533035716554557378321289293120392294258731566673565 , 74331715224220154299708533566163247663094029276428146274456519014761122295496)
c1 = (3315847183153421424358678117707706758962521458183324187760613108746362414091 , 61422809633368910312843316855658127170184420570309973276760547643460231548014)
c2 = (12838481482175070256758359669437500951915904121998959094172291545942862161864 , 60841550842604234546787351747017749679783606696419878692095419214989669624971)
cipher_left = 75142205156781095042041227504637709079517729950375899059488581605798510465939
cipher_right = 61560856815190247060747741878070276409743228362585436028144398174723191051815

k1p = (K[0]^3 + a*K[0] + b) - K[1]^2
k2p = (G[0]^3 + a*G[0] + b) - G[1]^2
p = gmpy2.gcd(k1p,k2p)
print(p)

E = EllipticCurve(GF(p),[a,b])
G = E(G)
K = E(K)
c1 = E(c1)
c2 = E(c2)

for k in trange(2^17,2^18):
    M = c1 - c2*k
    m1 = cipher_left * inverse(M[0],p) % p
    m2 = cipher_right * inverse(M[1],p) % p
    flag = long_to_bytes(int(m1)) + long_to_bytes(int(m2))
    if b"flag" in flag:
        print(flag)
        break
        # flag{2d6a7e4e-02d3-11ef-8836-a4b1c1c5a2d2}

signature

task.py

import os
import hashlib
from Crypto.Util.number import *
from Crypto.PublicKey import DSA
import random
def gen_proof_key():
    password = 'happy_the_year_of_loong'
    getin = ''
    for i in password:
        if random.randint(0, 1):
            getin += i.lower()
        else:
            getin += i.upper()
    ans = hashlib.sha256(getin.encode()).hexdigest()
    return getin,ans

def gen_key():
    pri = random.randint(2,q - 2)
    pub = pow(g,pri,p)
    return pri,pub

def sign(m,pri):
    k = int(hashlib.md5(os.urandom(20)).hexdigest(),16)
    H = int(hashlib.sha256(m).hexdigest(),16)
    r = pow(g,k,p) % q
    s = pow(k,-1,q) * (H + pri * r) % q
    return r,s

def verify(pub,m,signature):
    r,s = signature
    if r <= 0 or r >= q or s <= 0 or s >= q:
        return False
    w = pow(s,-1,q)
    H = int(hashlib.sha256(m).hexdigest(),16)
    u1 = H * w % q
    u2 = r * w % q
    v = (pow(g,u1,p) * pow(pub,u2,p) % p) % q
    return v == r
    
def login():
    print('Hello sir,Plz login first')
    menu = '''
    1.sign
    2.verify
    3.get my key
    '''
    times = 8
    while True:
        print(menu)
        if times < 0:
            print('Timeout!')
            return False
        choice = int(input('>'))
        if choice == 1:
            name = input('Username:').encode()
            if b'admin' in name:
                print('Get out!')
                return False
            r,s = sign(name,pri)
            print(f'This is your signature -- > {r},{s}')
            times -= 1
        elif choice == 2:
            print('Sure,Plz input your signature')
            print(pri)
            r = int(input('r:'))
            s = int(input('s:'))
            if verify(pub,b'admin',(r,s)) == True:
                print('login success!')
                return True
            else:
                print('you are not admin')
                return False
        elif choice == 3:
            print(f'Oh,your key is {(p,q,g)}')
getin,ans = gen_proof_key()
print(f'Your gift --> {ans[:6]}')
your_token = input('Plz input your token\n>')
if your_token != getin:
    print('Get out!')
    exit(0)

key = DSA.generate(1024)
p, q, g = key.p, key.q, key.g
pri, pub = gen_key()
if login() == False:
    exit(0)
print(open('/flag','r').read())

关注验签过程
$$
v \equiv g^{s^{-1}\times H(admin)} \times g^{xr}\mod p \mod q
$$

$$
v \equiv g^{k(H(admin) + xr)^{-1}(H(admin) + xr)} \mod p \mod q \quad = r
$$

题目要求用admin来验签，思路很简单，就是求出k，然后自己构造出r和s发给服务器即可，(并不需要求k)

通过$s \equiv k^{-1}(H+xr) \mod q$，有
$$
k \equiv s^{-1}(H+xr) \mod q
$$

$$
\therefore k \equiv s^{-1}H + s^{-1}xr \mod q
$$

令$A = s^{-1}r \mod q,B = s^{-1}h \mod q$
$$
\therefore k \equiv A_ix + B_i \mod q
$$
造格
$$
\begin{pmatrix}
t_1 & t_2 & … & t_8 & x & 1
\end{pmatrix}
\begin{pmatrix}
q & 0 & … & 0 & 0 & 0\\
0 & q & … & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & … & q & 0 & 0\\
A_1 & A_2 & … & A_8 & 1 & 0\\
B_1 & B_2 & … & B_8 & 0 & K
\end{pmatrix}
=
\begin{pmatrix}
k_1 & k_2 & … & k_8 & x & K
\end{pmatrix}
$$
q:160bit,k:128bit,x:160bit左右

d太大了，我们把d消去，有
$$
(r_0s_i)k_i - (r_1s_0)k_0 \equiv (h_ir_0-h_0r_i) \mod q
$$
同乘$(r_0s_i)^{-1}$有
$$
k_i - (r_0s_i)^{-1}(r_1s_0)k_0 \equiv (r_0s_i)^{-1}(h_ir_0-h_0r_i) \mod q
$$
令$A = (r_0s_i)^{-1}(r_1s_0) \mod q$，$B = (r_0s_i)^{-1}(h_ir_0-h_0r_i) \mod q$

所以有
$$
k_i \equiv A_ik_0 + B_i \mod q
$$
构造格
$$
\begin{pmatrix}
t_1 & t_2 & … & t_8 & k_0 & 1
\end{pmatrix}
\begin{pmatrix}
q & 0 & … & 0 & 0 & 0\\
0 & q & … & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & … & q & 0 & 0\\
A_1 & A_2 & … & A_8 & 1 & 0\\
B_1 & B_2 & … & B_8 & 0 & K
\end{pmatrix}
=
\begin{pmatrix}
k_1 & k_2 & … & k_8 & k_0 & K
\end{pmatrix}
$$

求出k0之后，我们计算$r \equiv g^{k_0} \mod p \mod q$，$s \equiv k^{-1}(H(admin) + xr) \mod q$

再把r,s发过去即可

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

def pass_proof(head):
    password = 'happytheyearofloong'
    table = itertools.product([0,1],repeat=19)
    for i in tqdm(table):
        getin = ""
        for j in range(len(i)):
            if i[j] == 0:
                getin += password[j].lower()
            else:
                getin += password[j].upper()
        msg = getin[:5] + "_" + getin[5:8] + "_" + getin[8:12] + "_" + getin[12:14] + "_" + getin[14:]
        h = hashlib.sha256(msg.encode()).hexdigest()
        if h[:6] == head:
            print(msg)
            return msg
        
sh = remote("8.147.132.12",41792)
head = sh.recvline().strip().decode().split(" ")[-1]
msg = pass_proof(head)
sh.recvuntil(b"Plz input your token")
sh.sendlineafter(b">",msg.encode())
sh.recvuntil(b"3.get my key\n")
sh.sendlineafter(b">",b"3")
(p,q,g) = eval(sh.recvline().strip().decode().split("Oh,your key is ")[-1])

H = []
R = []
S = []

for i in range(8):
    name = b"a"*(i+1)
    sh.recvuntil(b"3.get my key\n")
    sh.sendlineafter(b">",b"1")
    sh.sendlineafter(b"Username:",name)
    data = sh.recvline().strip().decode()
    print(data)
    r = int(data.split(" ")[-1].split(',')[0])
    s = int(data.split(" ")[-1].split(',')[1])
    h = int(hashlib.sha256(name).hexdigest(),16)
    R.append(r)
    S.append(s)
    H.append(h)

def get_k():
    n = len(R)
    r0 = R[0]
    h0 = H[0]
    s0 = S[0]
    A = []
    B = []

    for i in range(n):
        a = inverse((r0 * S[i]),q) * (R[i] * s0) % q
        b = inverse((r0 * S[i]),q) * (H[i]*r0 - h0 * R[i])
        A.append(a)
        B.append(b)
        
    Ge = Matrix(ZZ,n+2,n+2)
    for i in range(n):
        Ge[i,i] = q
        Ge[-2,i] = A[i]
        Ge[-1,i] = B[i]
    K = 2**128
    Ge[-2,-2] = 1
    Ge[-1,-1] = K

    for line in Ge.LLL():
        if abs(line[-1]) == K:
            return line[-2]

k0 = get_k()
print(f"k0 = {k0}")
sh.recvuntil(b"3.get my key\n")
sh.sendlineafter(b">",b"2")
sh.recvline()
x = int(sh.recvline().strip().decode())
r = pow(g,k0,p) % q
hh = int(hashlib.sha256(b"admin").hexdigest(),16)
s = pow(k0,-1,q) * (hh + x*r) % q
sh.sendlineafter(b"r:",str(r).encode())
sh.sendlineafter(b"s:",str(s).encode())
print(sh.recvline().strip().decode())
print(sh.recvline().strip().decode())

补充

由于对DSA没学到位，上面的思路似乎多此一举了，题目给出了私钥，所以只需要拿admin以及私钥构造r,s即可，k可以随便取

如果没给出私钥，那就需要按照上面的思路，先求出k，再求出私钥。

happy2024——Unsolved

not2022but2024

from Crypto.Util.number import *

CBC_key = b''

p,q = getPrime(512),getPrime(512)
n = p * q
N = n**2 + 2024
hint = (pow(3, 2022, N) * p**2 + pow(5, 2022, N) * q**2) % N
c = pow(bytes_to_long(CBC_key), 65537, n)

print('n =', n)
print('h =', hint)
print('c =', c)

'''
n = 104765768221225848380273603921218042896496091723683489832860494733817042387427987244507704052637674086899990536096984680534816330245712225302233334574349506189442333792630084535988347790345154447062755551340749218034086168589615547612330724516560147636445207363257849894676399157463355106007051823518400959497
h = 7203581190271819534576999256270240265858103390821370416379729376339409213191307296184376071456158994788217095325108037303267364174843305521536186849697944281211331950784736288318928189952361923036335642517461830877284034872063160219932835448208223363251605926402262620849157639653619475171619832019229733872640947057355464330411604345531944267500361035919621717525840267577958327357608976854255222991975382510311241178822169596614192650544883130279553265361702184320269130307457859444687753108345652674084307125199795884106515943296997989031669214605935426245922567625294388093837315021593478776527614942368270286385
c = 86362463246536854074326339688321361763048758911466531912202673672708237653371439192187048224837915338789792530365728395528053853409289475258767985600884209642922711705487919620655525967504514849941809227844374505134264182900183853244590113062802667305254224702526621210482746686566770681208335492189720633162
'''

$$
h \equiv 3^{2022}\times p^2 + 5^{2022}\times q^{2} \mod N
$$

因为$N = n^2 + 2024$，在模N下，$p,q$比较小

ctfshow西瓜杯

这场比赛题目蛮简单的，主要拼手速吧

奇怪的条形码

从手机充电口看这张图片，得到密文Y3Rmc2hvd3t4aWd1YmVpX21pc2NfZ3JhbV9oZXJlX2ZsYWd9

base64解码得到ctfshow{xigubei_misc_gram_here_flag}

简单密码

密文647669776d757e83817372816e707479707c888789757c92788d84838b878d9d

ctfshow转16进制是63746673686f77

c对应的那个密文是c的ASCII码加一，以此类推

exp

c = "647669776d757e83817372816e707479707c888789757c92788d84838b878d9d"

c_block = [c[i:i+2] for i in range(0,len(c),2)]

flag = ""
for i in range(len(c_block)):
    tmp = int(c_block[i],16)
    m = tmp - (i+1)
    flag += chr(m)

print(flag)
# ctfshow{xiguabei_just_ez_signin}

factor

task.py

from Crypto.Util.number import *
import gmpy2
import os
from enc import flag

hint = os.urandom(36)
tmp = bytes_to_long(hint)
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
d = getPrime(400)
phi = (p-1)*(q-1)
e = gmpy2.invert(d,phi)
n = p*q
c = pow(m,e,n)
leak1 = p^tmp
leak2 = q^tmp
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"leak1 = {leak1}")
print(f"leak2 = {leak2}")
'''
n = 145462084881728813723574366340552281785604069047381248513937024180816353963950721541845665931261230969450819680771925091152670386983240444354412170994932196142227905635227116456476835756039585419001941477905953429642459464112871080459522266599791339252614674500304621383776590313803782107531212756620796159703
e = 10463348796391625387419351013660920157452350067191419373870543363741187885528042168135531161031114295856009050029737547684735896660393845515549071092389128688718675573348847489182651631515852744312955427364280891600765444324519789452014742590962030936762237037273839906251320666705879080373711858513235704113
c = 60700608730139668338977678601901211800978306010063875269252006068222163102100346920465298044880066999492746508990629867396189713753873657197546664480233269806308415874191048149900822050054539774370134460339681949131037133783273410066318511508768512778132786573893529705068680583697574367357381635982316477364
leak1 = 13342820281239625174817085182586822673810894195223942279061039858850534510679297962596800315875604798047264337469828123370586584840078728059729121435462780
leak2 = 10901899434728393473569359914062349292412269512201554924835672710780580634465799069211035290729536290605761024818770843901501694556825737462457471235151530
'''

直接利用leak1 ^ leak2 = p ^ q剪枝

exp

from Crypto.Util.number import *
import gmpy2

n = 145462084881728813723574366340552281785604069047381248513937024180816353963950721541845665931261230969450819680771925091152670386983240444354412170994932196142227905635227116456476835756039585419001941477905953429642459464112871080459522266599791339252614674500304621383776590313803782107531212756620796159703
e = 10463348796391625387419351013660920157452350067191419373870543363741187885528042168135531161031114295856009050029737547684735896660393845515549071092389128688718675573348847489182651631515852744312955427364280891600765444324519789452014742590962030936762237037273839906251320666705879080373711858513235704113
c = 60700608730139668338977678601901211800978306010063875269252006068222163102100346920465298044880066999492746508990629867396189713753873657197546664480233269806308415874191048149900822050054539774370134460339681949131037133783273410066318511508768512778132786573893529705068680583697574367357381635982316477364
leak1 = 13342820281239625174817085182586822673810894195223942279061039858850534510679297962596800315875604798047264337469828123370586584840078728059729121435462780
leak2 = 10901899434728393473569359914062349292412269512201554924835672710780580634465799069211035290729536290605761024818770843901501694556825737462457471235151530

gift = leak1 ^ leak2

def findp(p,q):
    if len(p) == 512:
        pp = int(p,2)
        if n % pp == 0:
            p = pp
            q = n // p
            print("p = ",p)
            print("q = ",n // q)
            d = gmpy2.invert(e,(p-1)*(q-1))
            m = pow(c,d,n)
            print(long_to_bytes(int(m)))
            
    else:
        l = len(p)
        pp = int(p,2)
        qq = int(q,2)
        if (pp ^ qq) % (2 ** l) == gift %(2**l) and pp * qq %(2 ** l) == n % (2**l):
            findp('1' + p,'1' + q)
            findp('1' + p,'0' + q)
            findp('0' + p,'1' + q)
            findp('0' + p,'0' + q)

findp("1","1")
# cftshow{do_you_know_what_is_xor_and_prune!!!}

给你d又怎样

task.py

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

flag="ctfshow{***}"
m=bytes_to_long(flag.encode())
e=65537
p=getPrime(128)
q=getPrime(128)
n=p*q
phin=(p-1)*(q-1)
d=invert(e,phin)
c=pow(m,e,n)
print("c=",c)
print("hint=",pow(n,e,c))
print("e=",e)
print("d=",d)
"""
c= 48794779998818255539069127767619606491113391594501378173579539128476862598083
hint= 7680157534215495795423318554486996424970862185001934572714615456147511225105
e= 65537
d= 45673813678816865674850575264609274229013439838298838024467777157494920800897
"""

这题主要问题是没有n

因为$hint \equiv n^e \mod c$

这个c可以分解为6091 * 8010963716765433514869336359812774009376685535134030237002058632158407912

所以可以求e模c的逆元，即可得到n

但是此时求出来的n是比c小的，n理应比c大，所以加回一个c即可

exp

from Crypto.Util.number import *

c= 48794779998818255539069127767619606491113391594501378173579539128476862598083
hint= 7680157534215495795423318554486996424970862185001934572714615456147511225105
e= 65537
d= 45673813678816865674850575264609274229013439838298838024467777157494920800897

# c = 8010963716765433514869336359812774009376685535134030237002058632158407913 * 6091
phic = 6090 * 8010963716765433514869336359812774009376685535134030237002058632158407912
dc = inverse(65537,phic)
n = pow(hint,dc,c) + c
m = pow(c,d,n)
print(long_to_bytes(m))
# ctfshow{Oh_u_knOw_4uler}

混合密码体系

task.py

# 库
from Crypto.Util.number import bytes_to_long,getPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

# 对称加密
flag = b'ctfshow{***}'      # 密文，隐藏
key = b'flag{***}'      # 会话密钥，隐藏
iv = b'flag{1fake_flag}'       # AES偏移向量，已知
# 对明文进行填充，使其长度符合AES加密的要求
padded_plaintext = pad(flag, AES.block_size)

# 创建AES加密对象
cipher = AES.new(key, AES.MODE_CBC, iv)

# 加密
ciphertext = cipher.encrypt(padded_plaintext)

# 加密后的文本通常是字节串，转成整数便于进行会话密钥的RSA加密
c1 = bytes_to_long(ciphertext)

print(f'c1 = {c1}')

# 非对称加密
m = bytes_to_long(key)
e = 0x10001
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c = pow(m,e,n)
print(f'p = {p}')
print(f'q = {q}')
print(f'n = {n}')
print(f'c2 = {c}')
# print("hint:key需要转成字节流也就是b''")

'''
c1 = 10274623386006297478525964130173470046355982953419353351509177330015001060887455252482567718546651504491658563014875
p = 126682770761631193509957156425049279522830651950325320826580754739365086374362604934854454428815835196844469535588686149210573266628767888593088817059600076401582225549728184309047483547810100015820325082976781284679340880386138390518973395696206374336712856387090369022746536868747455939074262253452873845903
q = 99825079362327808334563489684167271427241139432727401182808888165552821217781929397837262324242177528386988701584385208395369790542025175917752058047649096340776854252623173162664426065810683048016574420043010318337693586527652970534982946701493024718805916479479658257730226388868060010370893747360166996939
n = 12646117645119414744807511144503229609414192869007113075368323921021672404219693075011763838210400633721060798765473421092201704833591315689681668160927426685183273670665030724394172000165517517884654100267567861284096827407481978978840602383267875832034344793848710383473014512122260278131503985961857107838296047172582364612603344429943715046318283653354068887129071531081918798285138812386418361474496678248683513378861801570673376726388110813411011818940310547686977359605296489433805717348250520973842927175837164120905300831792358190183785344002217291207378744610039145999012939983693891188308725179098958690917
c2 = 5211902378262010726785508340196935051860438587769647187076059600864676774592415052428465708887047312982844957691943180258845015420187239772414768121857728821510440178906193308448250067671679439841031484589864038401572589752057423667532898133171822921282769652197139455317095891357335645435094243006629469245881345449943250189771998449015275390517315432969774421721243965028796050948747282387052634211032729131656214346307483397410725129682422969273915759947596313513270946529649661334582775282060624547405060499311618257517792321792697831000977711752728887999320311631022598717946355057272761740061999974856808147244
'''

先解RSA得到key，然后再解AES

exp

from Crypto.Util.number import *
from Crypto.Cipher import AES

c1 = 10274623386006297478525964130173470046355982953419353351509177330015001060887455252482567718546651504491658563014875
p = 126682770761631193509957156425049279522830651950325320826580754739365086374362604934854454428815835196844469535588686149210573266628767888593088817059600076401582225549728184309047483547810100015820325082976781284679340880386138390518973395696206374336712856387090369022746536868747455939074262253452873845903
q = 99825079362327808334563489684167271427241139432727401182808888165552821217781929397837262324242177528386988701584385208395369790542025175917752058047649096340776854252623173162664426065810683048016574420043010318337693586527652970534982946701493024718805916479479658257730226388868060010370893747360166996939
n = 12646117645119414744807511144503229609414192869007113075368323921021672404219693075011763838210400633721060798765473421092201704833591315689681668160927426685183273670665030724394172000165517517884654100267567861284096827407481978978840602383267875832034344793848710383473014512122260278131503985961857107838296047172582364612603344429943715046318283653354068887129071531081918798285138812386418361474496678248683513378861801570673376726388110813411011818940310547686977359605296489433805717348250520973842927175837164120905300831792358190183785344002217291207378744610039145999012939983693891188308725179098958690917
c2 = 5211902378262010726785508340196935051860438587769647187076059600864676774592415052428465708887047312982844957691943180258845015420187239772414768121857728821510440178906193308448250067671679439841031484589864038401572589752057423667532898133171822921282769652197139455317095891357335645435094243006629469245881345449943250189771998449015275390517315432969774421721243965028796050948747282387052634211032729131656214346307483397410725129682422969273915759947596313513270946529649661334582775282060624547405060499311618257517792321792697831000977711752728887999320311631022598717946355057272761740061999974856808147244

d = inverse(65537,(p-1)*(q-1))
key = long_to_bytes(pow(c2,d,n))
iv = b'flag{1fake_flag}'

cipher = AES.new(key, AES.MODE_CBC, iv)
c1 = long_to_bytes(c1)
flag = cipher.decrypt(c1)
print(flag)
# ctfshow{Hybrid_password_system_is_chaos}