2024-XYCTF-wp-crypto

这个新生赛战线拉得很长，难度也不算特别新生，wp的题目顺序就按网站上显示的来。

x0r

题目描述：

nc版签到

题目：

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os

flag = open("flag.txt", "rb").read()
key = os.urandom(16)
iv = os.urandom(16)
flag = pad(flag, 16)


def aes_encrypt(key, plaintext):
    cipher = AES.new(key, AES.MODE_ECB)
    return cipher.encrypt(plaintext)


def encrypt(key, plaintext, iv):
    ciphertext = b""
    for i in range(0, len(plaintext), AES.block_size):
        key_block = aes_encrypt(key, iv)
        ciphertext_block = bytes(
            [plaintext[i + j] ^ key_block[j] for j in range(AES.block_size)]
        )
        ciphertext += ciphertext_block
        iv = key_block
    return ciphertext


while 1:
    try:
        print("1.print\n2.input\n3.exit")
        a = input("> ")
        if a == "1":
            print((iv + encrypt(key, flag, iv)).hex())
        elif a == "2":
            ivs = bytes.fromhex(input("iv: "))
            inputs = bytes.fromhex(input("message: "))
            print(encrypt(key, inputs, ivs).hex())
        elif a == "3":
            exit(0)
        else:
            print("You need input 1,2,3")
    except:exit(0)

一个交互题，连接上靶机后，靶机会生成完全随机的key和iv，然后给出以下几种选择：

• 输入1，可以得到本次的iv和flag的加密值
• 输入2，可以自定义输入一个iv以及消息，得到这个消息的加密值

这个题的突破点在于他的加密方式，仔细看encrypt函数：

def encrypt(key, plaintext, iv):
    ciphertext = b""
    for i in range(0, len(plaintext), AES.block_size):
        key_block = aes_encrypt(key, iv)
        ciphertext_block = bytes(
            [plaintext[i + j] ^ key_block[j] for j in range(AES.block_size)]
        )
        ciphertext += ciphertext_block
        iv = key_block
    return ciphertext

可以看到，他其实是将iv进行AES加密，然后将加密块与明文逐块进行异或，并更新iv。因此我们只需要先输入1得到iv和flag的密文，然后输入全0的消息去得到每次加密的iv块，然后再与密文做异或就得到flag了。

exp：

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

sh = remote("xyctf.top",39233)

#part1 get data
sh.recvuntil(b"> ")
sh.sendline(b"1")
temp = sh.recvline().strip().decode()
iv = long_to_bytes(int(temp[:32],16))
enc = long_to_bytes(int(temp[32:],16))

#part2 send msg
msg = 48*b"\x00"
sh.recvuntil(b"> ")
sh.sendline(b"2")
sh.recvuntil(b"iv: ")
sh.sendline(iv.hex().encode())
sh.recvuntil(b"message: ")
sh.sendline(msg.hex().encode())
enc_msg = long_to_bytes(int(sh.recvline().strip().decode(),16))
print(xor(enc_msg,enc))


#XYCTF{5647687b-6c8e-4e13-b73d-a54c39d95511}

Complex_rsa

题目描述：

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


class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)

    def __str__(self):
        if self.im == 0:
            return str(self.re)
        elif self.re == 0:
            if abs(self.im) == 1:
                return f"{'-' if self.im < 0 else ''}i"
            else:
                return f"{self.im}i"
        else:
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"


def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result


m = bytes_to_long(flag)
key = getRandomNBitInteger(m.bit_length())
c = m ^ key
com = Complex(key, c)
p = getPrime(512)
q = getPrime(512)
e = 9
enc = complex_pow(com, e, p * q)
print(enc)
print(Complex(p, q) * Complex(p, q))
# 66350931528185981323649477263900844564494528747802437244889229343520648562164950914433406604580038018765783183569276743239888668912948977370163046257917321742455772852779551569446155827368453262479370103326286297164105599131090881306108546341785251895116423206455175290083968296281375908109039893280371271943 + 65266730684129269806656018828265187384002656633231286337130178390517924611751697965395744944541329793503617856896706439809241745206839328124348693486741656130890593895436661857688522977866438805549144904296596887218275440542852887148071837153436265722614658566275517205322945316112048487893204059562830581004i
# -28814875173103880290298835537218644402443395484370652510062722255203946330565951328874411874019897676900075613671629765922970689802650462822117767927082712245512492082864958877932682404829188622269636302484189627580600076246836248427780151681898051243380477561480415972565859837597822263289141887833338111120 + 235362412848885579543400940934854106052672292040465052424316433330114813432317923674803623227280862945857543620663672974955235166884830751834386990766053503640556408758413592161122945636548462064584183165189050320898315823173824074873376450569212651128285746330837777597290934043912373820690250920839961482862i

题目是复数域上的一个RSA，他先将m与随机的key异或得到c，然后定义如下复数：

$$com = k + ci$$

之后题目给出如下两个值，要求还原m：

$$enc = com^9 \quad(mod\;pq)$$ $$(p+qi)(p+qi)$$

首先想到的肯定是利用第二个值先得到p、q，由于其展开式为：

$$(p^2-q^2) + 2pqi$$

所以实部和虚部分别对应p、q的一个二元方程，因此可以解出p、q来。

有了p、q之后就要想办法解决前面复数域上的RSA，由于复数域上有：

$$\phi = (p^2-1)(q^2-1)$$

至于为什么是这样可以看我另一篇文章：Crypto趣题-RSA(一) | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

所以预期是求e关于phi的逆元就可以直接解密，然而对于这个题却有些特殊，这是因为：

$$GCD(e,p^2-1) = GCD(e,q^2-1) = 3$$

所以逆元是不存在的，然而逆元不存在有不存在的办法，我们把加密的式子分别放到模p和模q下观察，这里以模p为例：

$$enc = com^9 \quad(mod\;p)$$

虽然不能直接求e关于p^2-1的逆元，但我们可以求出一个t使得它满足：

$$9t = 3 \quad(mod\;p^2-1)$$

也就是说我们可以拥有：

$$com^3 = enc^t \quad(mod\;p)$$

把com的实部虚部展开得到：

$$com^3 = (k+ci)^3 = (k^3 - 3kc^2) + (3k^2c - c^3)i \quad(mod\;p)$$

而这个实部与虚部其实也就提供了关于k、c模p下的两个等式，也就是：

$$f_1 = k^3 - 3kc^2 - re$$ $$f_2 = 3k^2c - c^3 - im$$

所以可以resultant消去其中一个变量，然后再在模p下求根，就得到了k、c的候选值；对于模q下同理 ，然后将所有可能值crt起来并进行异或，检查是否含flag头即可。

exp：

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

e = 9
pq2 = 235362412848885579543400940934854106052672292040465052424316433330114813432317923674803623227280862945857543620663672974955235166884830751834386990766053503640556408758413592161122945636548462064584183165189050320898315823173824074873376450569212651128285746330837777597290934043912373820690250920839961482862
p2_q2 = -28814875173103880290298835537218644402443395484370652510062722255203946330565951328874411874019897676900075613671629765922970689802650462822117767927082712245512492082864958877932682404829188622269636302484189627580600076246836248427780151681898051243380477561480415972565859837597822263289141887833338111120

class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)

    def __str__(self):
        if self.im == 0:
            return str(self.re)
        elif self.re == 0:
            if abs(self.im) == 1:
                return f"{'-' if self.im < 0 else ''}i"
            else:
                return f"{self.im}i"
        else:
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"


def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result

p = 10205509456040823453782883291824829705816298450992336115902525676510986341532486274067943978039013674207011185602314114359146043975207543018267242312660911
q = pq2 // 2 // p

com = Complex(66350931528185981323649477263900844564494528747802437244889229343520648562164950914433406604580038018765783183569276743239888668912948977370163046257917321742455772852779551569446155827368453262479370103326286297164105599131090881306108546341785251895116423206455175290083968296281375908109039893280371271943 , 65266730684129269806656018828265187384002656633231286337130178390517924611751697965395744944541329793503617856896706439809241745206839328124348693486741656130890593895436661857688522977866438805549144904296596887218275440542852887148071837153436265722614658566275517205322945316112048487893204059562830581004)
re = int(complex_pow(com, inverse(3,(p^2-1)//3), p).re)
im = int(complex_pow(com, inverse(3,(p^2-1)//3), p).im)


PR.<a,b> = PolynomialRing(Zmod(p))
f1 = a^3 - 3*a*b^2 - re
f2 = 3*a^2*b - b^3 - im
h = f1.sylvester_matrix(f2, a).det()
res1 = h.univariate_polynomial().monic().roots()
print(res1)


re = int(complex_pow(com, inverse(3,(q^2-1)//3), q).re)
im = int(complex_pow(com, inverse(3,(q^2-1)//3), q).im)
PR.<a,b> = PolynomialRing(Zmod(q))
f1 = a^3 - 3*a*b^2 - re
f2 = 3*a^2*b - b^3 - im
h = f1.sylvester_matrix(f2, a).det()
res1 = h.univariate_polynomial().monic().roots()
print(res1)

crt：

from Crypto.Util.number import *
from sympy.ntheory.modular import crt
#M = crt(n,c)[0]

pq2 = 235362412848885579543400940934854106052672292040465052424316433330114813432317923674803623227280862945857543620663672974955235166884830751834386990766053503640556408758413592161122945636548462064584183165189050320898315823173824074873376450569212651128285746330837777597290934043912373820690250920839961482862
p2_q2 = -28814875173103880290298835537218644402443395484370652510062722255203946330565951328874411874019897676900075613671629765922970689802650462822117767927082712245512492082864958877932682404829188622269636302484189627580600076246836248427780151681898051243380477561480415972565859837597822263289141887833338111120
p = 10205509456040823453782883291824829705816298450992336115902525676510986341532486274067943978039013674207011185602314114359146043975207543018267242312660911
q = pq2 // 2 // p

resp = [(5741279734159523094711430662094390392066954482529914882030709450295074947781529110509321968864008611691202383770840412010325910906148313511187473860891035, 1), (4429927739780647098163182245695850111737474361073472216489514077452142827783532166774438977867801037416377640995299677179237078298139871084989841206362410, 1), (34301982100653260908270384034589202011869607388949017382302148763768565967424996784183031307204025099431160836174025169583054770919358422089927245407466, 1)]
resq = [(10739940731745824081418381715901342901309159762856543362640396906171107996295925365437945464907432967788383551341616951552057327658847904490010061152434332, 1), (8586549363626610854952590733794044071899545915261216635206863621255915665043556027382073545902963458915586846862230166123268280750109862724278599667847493, 1), (7045447028567292693464036821896048537001778022349939312880599967825498301190014724113928977446846014453607030578761699581827447107524459504793000974080961, 1), (5276901669007862459606429311418416791067007412160397323233728060764482838272522831695179159225558247215591099096136610833622276098301992005638773878483349, 1), (4073305908343434001432234700505703739500538013701467077531217640906529193773037971902079461771703238283853345951042314327641038705737553746426200870882295, 1), (3735799333948544298117875399520421256169239519249120000907464407334065474418981528427034590769440802753611282812668144292181442455716588786153175184716817, 1), (3722039472368511317694313824581779119019195065732852920938680419139949899687211960294412748248774573691326211744547172363931044270883035467641541946900209, 1), (2532203573284115839943680788607708204602770120790189755204953987476111829919496668633934893315585793821873529667573847786200205063152150526940602177115763, 1), (412391777749762922348152402206151838186656562632033608965544858648517072916178764607518361571369361991330463978453617074285039619075164749001716157536065, 1)]

cp = []
cq = []
for i in resp:
    cp.append(i[0])

for i in resq:
    cq.append(i[0])

KEY = []
for i in cp:
    for j in cq:
        n = [p,q]
        c = [i,j]
        key = crt(n,c)[0]
        KEY.append(key)


resp = [(8001885192071749859699066040025029961395167917875583646644249565155819105797467000967544636712092306411149367493633723366623965498649673837196063800580404, 1), (1662435559780994004386842122204566836802794060667449753807174598739830437128828179292947062605594949711892539092095892832053999186054026591407366803020136, 1), (541188704188079589696975129595232907618336472449302715451101512615336798606191093807452278721326418083969279016584498160468079290503842589663811709060371, 1)]
resq = [(8503432605028099223082740882529347146997316989367545950492333769305549393260049047195629451308480848275471020811688622917531588079409913760096873405190234, 1), (8366627759634051290333268012004602352405002740363136177900446298441200900164136168489014946546974693508397220434695162939560760156985163750847606373150919, 1), (7838336389145961788946008207588532360344213223957590603935032631402061939530140801549439038388256401440065798242555755132126684810445868962728928464941121, 1), (6857325280540966155209571629622673516628729233046153216919246004917826296064185951208599616644606134509118662339264343895819605897243323286865301166906602, 1), (6192229064658828721072838954681858729975625467636197870361944867014338842334277705562409203724381687673713439770131476110414702628279278489497356226657489, 1), (4121694029664041978927797165221546618939268589175297893513650941901521328887423207726634825943843128912526687991267349501555811582062174969259522939168771, 1), (2475586705176908911054627912314872988570680832853905159940563177513798231691560111739604991279968415146174329518843070479843829399895584496027950700885139, 1), (1217221620337618917243787804704498765774078541871944235501766658464684396657530547334482771121693798142550712746858805371783011221995724541464038836673061, 1), (552125404455481483107055129763683979120974776461988888944465520561196942927622301688292358201469351307145490177725937586378107953031679744096093896423948, 1)]
cp = []
cq = []
for i in resp:
    cp.append(i[0])

for i in resq:
    cq.append(i[0])

CC = []
for i in cp:
    for j in cq:
        n = [p,q]
        c = [i,j]
        cc = crt(n,c)[0]
        CC.append(cc)

for i in CC:
    for j in KEY:
        if(b"flag" in long_to_bytes(i ^ j)):
            print(long_to_bytes(i ^ j))
print(len(CC))

#flag{Complex_is_so_fun_and_I_think_you_know_Sylvester!}

factor1

题目描述：

这个e咋比n还大啊

题目：

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

p = getPrime(512)
q = getPrime(512)
d = getPrime(512)
e = gmpy2.invert(d, (p**3 - 1) * (q**3 - 1))
flag = "XYCTF{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
print(e)
print(p * q)
# 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163
# 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793

题目很明显的一点是d较小，仅有512bit，所以应该是想办法构造copper，而构造copper的依据就是以下等式：

$$ed = 1 + k(p^3-1)(q^3-1)$$

稍加变形后放到模e下就有：

$$f = 1 + k(n^3 - (p^3 + q^3) + 1) \quad(mod\;e)$$

k应该是和d相近的小量，p^3+q^3在模e下也较小，因此造出下面的二元copper：

$$f = 1 + x(n^3 - y + 1) \quad(mod\;e)$$

之后大力调一下二元copper的参数就好了。

exp：

from Crypto.Util.number import *
import hashlib
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 []


#part1 get k,p3q3
e = 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163
n = 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793

PR.<x,y> = PolynomialRing(Zmod(e))
f = 1 + x * (n^3 - y + 1)
res = small_roots(f , bounds = (2^512,(2^512)^3) , m=7 , d=3)
k = int(res[0][0])
p3q3 = int(res[0][1])


#part2 factor n
p, q = var('p, q')
res = solve([p*q == n, p^3 + q^3 == p3q3], p, q)
#print(res)
p = 9212046353930376594996890089494718736894378991991381248242532319628627449681664076081705664941905594411935750003102856235503684466394327681725704255564467
q = n // p
assert p*q == n


#part3 get flag
flag = "XYCTF{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
print(flag)


#XYCTF{a83211a70e18145a59671c08ddc67ba4}

new_LCG

题目描述：

lcg练习

题目：

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

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p * q * r


class LCG1:
    def __init__(self, seed, a, b, m):
        self.seed = seed
        self.a = a
        self.b = b
        self.m = m
        self.sum = 0

    def next(self):
        old_seed = self.seed
        self.seed = (self.a * self.seed + self.b * self.sum) % self.m
        self.sum += old_seed
        return self.seed


class LCG2:
    def __init__(self, seed, q, A, B):
        self.E = EllipticCurve(GF(q), [A, B])
        self.P = self.E.lift_x(seed)
        self.b = self.E.random_point()

    def next(self):
        self.P = self.P + self.b
        return self.P[0]


a1 = random.randint(1, p)
b1 = random.randint(1, p)
seed1 = random.randint(1, p)
lcg1 = LCG1(seed1, a1, b1, p)
c1 = []
for _ in range(10):
    c1.append(lcg1.next())

a2 = random.randint(1, q)
b2 = random.randint(1, q)
seed2 = random.randint(1, q)
lcg2 = LCG2(seed2, q, a2, b2)
c2 = []
for _ in range(10):
    c2.append(lcg2.next())

c = bytes_to_long(flag)
e = 65537
print(n)
print(pow(c, e, n))
print(c1)
print(c2)
# 942554394956393500634473023924044851150783066435925660508624376974971108656861080872622432250172571195245180102507380675343264066303507696268870722959770362631674931170602993210221083436437860191861911457384526742569208842886612504579678703976889217504241741044075116270718940025586448491942058697669033418724145042156461740336592337509609124425828725269151627786668070531098444935129266626770404736852607352075247856808563388127774523912002202264558855255067503
# 91351185520045025851535940537599785616890151570421939971146348618267656786110090770321857244701820126026227283965934212135946431643320325513590505155214070540638751565105300361430272638957420276596026161454413739823593506516275224444666187442238624864548263927274591212614561916913851855552516864387460946267629794664216228596534684933791607740725160394841711539767932339281214673649553407414347293480522175832736301571839298158011533849603878482322619858083471
# [6924229081976334180193477951417117275396656434968000032228908231511246053064833236257422745299036986875244562025221130619850904830372215788197314906896784,707045810464337488125013716300756405499020414540801863434513087687914538170573314824134496890600422837133767094273649381435979038909605432188919586751472,561487665739111774897165274560908487232457333748910467998343202097778699925650682704996443560224288857862513676706660506594465853704042586896087391214886,6498834369085375452441121562339384727357898216850540864190840194924515286757125433756518026123451611578553656133012172518080309106483207567929943790044792,5508345401684913940610183958526398635406187349043368834080838153611810896629693027245511688366776749176652858929409374912959736262162942801190344337268446,7604410082265211154108357446507297790451766698177313130672954202813796888988719242951127448112228332967892794819415211618572734294964346056056171483002307,7699815879242527638422887386550759485127768822609011364311314299885418068889791030639324882736871756700299169635780542149704586720216395186814592666988591,829748131720382599696653359722612708514830904084605048590882951300049701148883021283243506081300427041733299385325284399270633917941134488957784480285437,7084115400374950827522650500486495223539292992998875483730758098005030106055310282589342193536381973309924074043955222228738842206417828828756951777504457,7482796067314266426215648326036921955183807741134787613584977300821023398375789725848056657250086288687570875979072368004217788222537115232191230702833854]
# [12573984103581521249597169818949825744876735847170990673204303602848066091917704946653820386665801380026230957120354174481948164514637637956459534723582285, 6441954407109995413858792101472089558106780628459991101662507565699664222341697230094798036088532393057448200220905589679548875702178737462785403325555226, 11684244745641367106386196774447204674089853123966422387024948921795099192025069760680924547214190425118261001002764397184950251157744938735586522727499550, 10396243416373326695473843427139385116708652845789644861965876346553795313454773668473030130335970707089781482749749170266279229263892370064669233541305377, 9090748241360606371310281608818966855338110969397659720953951845805983771894064629343960530245792700858927510839835850767728294266738917884471006979663157, 11489848045104749332790333272128633885019156159805805159750174723808043569789257625027794186359921080743368220606914862583644262009648261345452266067697628, 649349258009900424806913260265314442160901414078390702088746248078789581041616487825633046538335114117254875547413590064940767523651802950986197978665018, 6302136940345077947382276151657194124073457559487274425879887978386901058162385833414602346299055653879087077862824771863209271498552774720708307840705334, 5844526398244645236473089500608731415060125566027525405618000580381149761653744142808567706048834618328671311836990498943019718294135733114642775270792763, 4834548043993868659061606699822957422840040425976833628462093089330507589865407793951971491111695171201542345470702059513427268037868859282999222070054388]

题目分为两个不同的LCG，均给出连续十组数据，需要恢复各自的模数从而实现最后的RSA解密。

LCG1

第一个LCG的递推过程为：

$$x_{i+1} = ax_{i} + b\sum_{j=0}^{i-1}x_{j} \quad(mod\;p)$$

由于初始种子未知，所以实际上一共有a、b、p、x0四个未知数，但是给了连续的数据，相当于提供了十个方程，所以建groebner来解完全够了。

LCG2

第二个LCG是椭圆曲线上的LCG，其递推过程为：

$$P_{i+1} = P_i + b$$

其中b是椭圆曲线上的一个随机点，生成随机数的步骤就是取当前Pi的横坐标。

而我们并不知道椭圆曲线方程，能拿到的仅有连续十个横坐标而已，也就是说对于这条椭圆曲线来说：

$$y^2 = x^3 + ax + b \quad(mod\;p)$$

参数a、b、p都是未知量。同时，给出的十个点的纵坐标，以及种子的横纵坐标和b的横纵坐标都是未知的，看上去未知的量的个数超过了我们能建立的方程数量。

然而仔细想的话会知道，每个点的纵坐标其实都是可以用横坐标和曲线方程来联系的，所以严格来说纵坐标并不算未知量，只是曲线方程里的纵坐标有平方项，比较难以处理。但这个时候可以使用一个类似于西湖论剑”MyCurveErrorLearn”一题的消元技巧，把连续的三个点看作一组，这个时候其实就有：

$$P_1 = P_2 - b$$ $$P_3 = P_2 + b$$

由椭圆曲线的点加公式知道，如果有：

$$G_1 + G_2 = G_3$$

那么其横坐标满足关系：

$$x_3 = (\frac{y_2-y_1}{x_2-x_1})^2 - x_1 - x_2$$

如果记b=(gx,gy)，则-b=(gx,-gy)，那么对于P2-b和P2+b分别有：

$$x_1 = (\frac{gy+y_2}{gx-x_2})^2 - gx - x_2$$ $$x_3 = (\frac{gy-y_2}{gx-x_2})^2 - gx - x_2$$

所以得到：

$$x_1 + x_3 = (\frac{gy+y_2}{gx-x_2})^2 + (\frac{gy-y_2}{gx-x_2})^2 - 2gx - 2x_2$$

打开括号后合并同类项：

$$(gx-x_2)^2(x_1 + x_3) = 2(gy^2 + y_2^2) - 2(gx + x_2)(gx-x_2)^2$$

此时可以发现，这样做的好处在于消去了所有纵坐标不是二次的项，而纵坐标的二次项都可以用椭圆曲线方程来代换，也就是：

$$(gx-x_2)^2(x_1 + x_3) = 2(gx^3 + ag_x + b + x_2^3 + ax_3 + b) - 2(gx + x_2)(gx-x_2)^2$$

如此一来，所有的未知数就只剩下了b的横坐标gx以及椭圆曲线的参数a、b、p，而我们显然可以用给出的十组横坐标建立多组上面这个形式的方程，然后就可以groebner求解出模数。

exp：

from Crypto.Util.number import *

e = 65537
n = 942554394956393500634473023924044851150783066435925660508624376974971108656861080872622432250172571195245180102507380675343264066303507696268870722959770362631674931170602993210221083436437860191861911457384526742569208842886612504579678703976889217504241741044075116270718940025586448491942058697669033418724145042156461740336592337509609124425828725269151627786668070531098444935129266626770404736852607352075247856808563388127774523912002202264558855255067503
c = 91351185520045025851535940537599785616890151570421939971146348618267656786110090770321857244701820126026227283965934212135946431643320325513590505155214070540638751565105300361430272638957420276596026161454413739823593506516275224444666187442238624864548263927274591212614561916913851855552516864387460946267629794664216228596534684933791607740725160394841711539767932339281214673649553407414347293480522175832736301571839298158011533849603878482322619858083471
c1 = [6924229081976334180193477951417117275396656434968000032228908231511246053064833236257422745299036986875244562025221130619850904830372215788197314906896784,707045810464337488125013716300756405499020414540801863434513087687914538170573314824134496890600422837133767094273649381435979038909605432188919586751472,561487665739111774897165274560908487232457333748910467998343202097778699925650682704996443560224288857862513676706660506594465853704042586896087391214886,6498834369085375452441121562339384727357898216850540864190840194924515286757125433756518026123451611578553656133012172518080309106483207567929943790044792,5508345401684913940610183958526398635406187349043368834080838153611810896629693027245511688366776749176652858929409374912959736262162942801190344337268446,7604410082265211154108357446507297790451766698177313130672954202813796888988719242951127448112228332967892794819415211618572734294964346056056171483002307,7699815879242527638422887386550759485127768822609011364311314299885418068889791030639324882736871756700299169635780542149704586720216395186814592666988591,829748131720382599696653359722612708514830904084605048590882951300049701148883021283243506081300427041733299385325284399270633917941134488957784480285437,7084115400374950827522650500486495223539292992998875483730758098005030106055310282589342193536381973309924074043955222228738842206417828828756951777504457,7482796067314266426215648326036921955183807741134787613584977300821023398375789725848056657250086288687570875979072368004217788222537115232191230702833854]
c2 = [12573984103581521249597169818949825744876735847170990673204303602848066091917704946653820386665801380026230957120354174481948164514637637956459534723582285, 6441954407109995413858792101472089558106780628459991101662507565699664222341697230094798036088532393057448200220905589679548875702178737462785403325555226, 11684244745641367106386196774447204674089853123966422387024948921795099192025069760680924547214190425118261001002764397184950251157744938735586522727499550, 10396243416373326695473843427139385116708652845789644861965876346553795313454773668473030130335970707089781482749749170266279229263892370064669233541305377, 9090748241360606371310281608818966855338110969397659720953951845805983771894064629343960530245792700858927510839835850767728294266738917884471006979663157, 11489848045104749332790333272128633885019156159805805159750174723808043569789257625027794186359921080743368220606914862583644262009648261345452266067697628, 649349258009900424806913260265314442160901414078390702088746248078789581041616487825633046538335114117254875547413590064940767523651802950986197978665018, 6302136940345077947382276151657194124073457559487274425879887978386901058162385833414602346299055653879087077862824771863209271498552774720708307840705334, 5844526398244645236473089500608731415060125566027525405618000580381149761653744142808567706048834618328671311836990498943019718294135733114642775270792763, 4834548043993868659061606699822957422840040425976833628462093089330507589865407793951971491111695171201542345470702059513427268037868859282999222070054388]


############################################# lcg1
PR.<a,b,x0> = PolynomialRing(ZZ)
F = [a*x0 - c1[0]]
for i in range(9):
    f = a*c1[i] + b*(x0+sum(c1[:i])) - c1[i+1]
    F.append(f)
res = Ideal(F).groebner_basis()
p = ZZ(res[3].univariate_polynomial()(0))


############################################# lcg2
PR.<A,B,gx> = PolynomialRing(ZZ)
F = []
for i in range(1,10-1):
    f = (gx-c2[i])^2*(c2[i-1]+c2[i+1]) - 2*(gx^3+A*gx+B+c2[i]^3+A*c2[i]+B) + 2*(gx+c2[i])*(gx-c2[i])^2
    F.append(f)
res = Ideal(F).groebner_basis()
q = ZZ(res[3].univariate_polynomial()(0))


############################################# decrypt
r = n // p // q
phi = (p-1)*(q-1)*(r-1)
d = inverse(e,phi)
print(long_to_bytes(int(pow(c,d,n))))


#flag{71fc0bc1-167a-43f0-ab0f-e0df3bea8ed3}

不过关于这个问题其实有一篇论文：

merai_predictingEC-LCG.pdf (elte.hu)

而论文中提到最少可以只给七组数据，但是我这个方法实际测试下来必须全部用上才行。而论文的具体实现在Theorem 1中，其构造了一个5x6的矩阵，并且说明其前四列的列向量线性无关后，证明了一个由前四列列向量以及一个u向量构成的矩阵，其行列式是p的倍数，因此可以与n求gcd得到p。

easy_ecc

题目描述：

easy!!!

题目：

from Crypto.Util.number import *
from hashlib import sha256
from secret import flag, secret,SECRET

assert flag[6:-1] == sha256(long_to_bytes(secret)).hexdigest().encode()


class ECC_easy:
    def __init__(self):
        self.a = 1365855822212045061018261334821659180641576788523935479
        self.b = 17329427219955161804703200105884322768704934833367341
        self.p = 1365855822212045061018261334821659180641576788523935481

    def add(self, P, Q):
        mul_inv = lambda x: pow(x, -1, self.p)
        x1, y1 = P
        x2, y2 = Q
        if P!=Q:
            l=(y2-y1)*inverse(x2-x1,self.p)%self.p
        else:l=(3*x1**2+2*self.a*x1+1)*inverse(2*self.b*y1,self.p)%self.p
        temp1 = (self.b*l**2-self.a-x1-x2)%self.p
        temp2 = ((2*x1+x2+self.a)*l-self.b*l**3-y1)%self.p
        x3 = temp1
        y3 = temp2
        return x3, y3

    def mul(self, x, P):
        Q = SECRET
        x = x % self.p
        while x > 0:
            if x & 1:
                Q = self.add(Q, P)
            P = self.add(P, P)
            x >>= 1
        return Q

    def ispoint(self, x, y):
        return (self.a * x ** 2 + x ** 3+x) % self.p == (self.b * y ** 2) % self.p


ecc = ECC_easy()
LLLL = (1060114032187482137663886206406014543797784561116139791,752764811411303365258802649951280929945966659818544966)
assert ecc.ispoint(LLLL[0], LLLL[1])
END = ecc.mul(secret, LLLL)
print(END)

# (695174082657148306737473938393010922439779304870471540,414626357054958506867453055549756701310099524292082869)

题目基于一条曲线上的dlp，由ispoint函数可以看出曲线符合下面的方程：

$$By^2 = x^3 + Ax^2 + x \quad(mod\;p)$$

这是一条蒙哥马利曲线，其向Weierstrass形式曲线上的映射方式可以在之前写过的这篇文章里找到：

Crypto趣题-曲线 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

由于参数都给定了，所以很轻松就能得到Weierstrass形式曲线的参数，然而在sage内建立椭圆曲线方程时会产生singular的报错，说明这是一条奇异曲线。简单分解一下曲线方程可以发现它是node形式的singular curve：

$$y^2 = (x - \alpha)^2(x - \beta)$$

对于singular curve来说，其分两种情况cusp和node，其中cusp指椭圆曲线方程有三重根，而node指有两重根。也就是说他们的方程分别可以写成如下形式：

$$y^2 = x^3$$ $$y^2 = (x - \alpha)^2(x - \beta)$$

而两种形式的singular curve都存在不同方式的向数域上的映射，对于node而言是：

$$E \rightarrow F_p :(x,y) \rightarrow \frac{y + \sqrt{\alpha - \beta}(x - \alpha)}{y - \sqrt{\alpha - \beta}(x - \alpha)}$$

所以可以映射到Fp下去求数域上的dlp，并且p-1是比较光滑的所以dlp易求。

其实这里还有一个可能存在的小问题，就是$\alpha - \beta$并不一定是模p下的二次剩余，当他不是二次剩余时，这个映射其实是向Fp2的一个映射，那个时候会多出一个p+1的子群

exp：

from Crypto.Util.number import *
from hashlib import sha256

A = 1365855822212045061018261334821659180641576788523935479
B = 17329427219955161804703200105884322768704934833367341
p = 1365855822212045061018261334821659180641576788523935481

#part2 map to ECC
F = GF(p)
a = F(3-A^2) / F(3*B^2)
b = F(2*A^3-9*A) / F(27*B^3)


def edwards_to_ECC(x,y):
    x3 = (F(3*x) + F(A)) / F(3*B)
    y3 = F(y) / F(B)
    #now curve is y^2 = x^3 + ax + b
    return (x3,y3)

G = (1060114032187482137663886206406014543797784561116139791,752764811411303365258802649951280929945966659818544966)
mG = (695174082657148306737473938393010922439779304870471540,414626357054958506867453055549756701310099524292082869)

G_ecc = edwards_to_ECC(G[0],G[1])
mG_ecc = edwards_to_ECC(mG[0],mG[1])


#part3 singular curve attack(map point to Fp)
P.<x> = GF(p)[]
f = x^3 + a*x + b
print(f.factor())

alpha = -544257272453066077953551360625531658485543339865638914
beta = -277341277305912905111158613570595863670490108792657653

def map(x, y):
    r = F(alpha - beta).sqrt()
    t = F(r * (x - alpha))
    return F((y + t) / (y - t))

mg = map(mG_ecc[0], mG_ecc[1])
g = map(G_ecc[0], G_ecc[1])

m = discrete_log(mg,g,ord = p-1)

flag = b"XYCTF{" + sha256(long_to_bytes(int(m))).hexdigest().encode() + b"}"
print(flag)


#XYCTF{ec9a6e17537e81b7f593f65f7e2ca5d575e6b34c504c24e4afb40c1e9dc4be0d}

反方向的密码 相思

题目描述：

长相思兮长相忆,短相思兮无穷极。你所寻找的flag到底在哪里呢？flag格式为XYCTF{*}

题目：

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


def hash(x):
    return hashlib.sha256(x.encode()).digest()


def pad(message):
    return message + hash(str(len(message)))


m = bytes_to_long(pad(flag))
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
e = 3
print(pow(m, e, n))
print(n)
# 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053
# 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243

题目基于如下等式：

$$c = (m \;|| \; h(m_{len}))^3 \quad(mod\;n)$$

由于sha256长度是固定的32字节，并且flag长度应该在可以爆破的范围内，所以不妨假设我们爆破到了正确的flag长度，就有下式成立：

$$c = (256^{32}m + h)^3 \quad(mod\;n)$$

由于加密指数并不大，所以可以把整个式子看作是模n下的单元copper去求解m，并且由于有已知的flag头尾其实还可以进一步减小根的大小，不过不做这一步处理也可以直接跑出来，因为上界已经足够了。

exp：

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


def hash(x):
    return hashlib.sha256(x.encode()).digest()

e = 3
c = 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053
n = 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243

PR.<x> = PolynomialRing(Zmod(n))
for length in trange(20,50):
    suffix = bytes_to_long(hash(str(length)))
    f = (256^32*x + suffix)^3 - c
    f = f.monic()
    res = f.small_roots(X=256^length,beta=1,epsilon=0.05)
    if(res != []):
        print(long_to_bytes(int(res[0])))
        break

#XYCTF{!__d3ng__hu0__1@n__3h@n__Chu__!}

反方向的密码 情难

题目描述：

衣带渐宽终不悔,为伊消得人憔悴。你苦苦思念的flag在ta的彼岸也会思念你吗？flag格式为XYCTF{*}

题目：

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


def hash(x):
    return hashlib.sha512(x.encode()).digest() * 2


def pad(message):
    return (message[: len(message) // 2] + hash(str(len(message))) + message[len(message) // 2 :])


p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p * q
e = 2
m = bytes_to_long(pad(flag))
print(pow(m, e, n))
print(n)
# 3335299537518434350008670067273514020883265809787658909900831303201069228111667477512288715627313377374377192065531931991830331266940281529429758933125645068623703704431432931062515459304407129764836169638068667723468109909932687335727824459807903558617156661138991973933280805156893120951135488168923425258119689993859896540097318197048436676318334502053269738046279338047497258783747007084564814994803144049365117574904704816542523015746396519693505167963245600047742456478545640334467678554748227823020862550712083249012329745708139070338928730226897923885785783461594034339595106377701306570280371612953393097739
# 26278624299187148406559772770865336226934633734285979741424867540828670397865189685966828527168795621543490979182417570078991930822041468539855006585233692884235331084907340302530060261742100702658312435180527335101284800616106884692498603300926488358017928867672861988448488439356448543527810620591324774111321619391264173779312033252573140028630441135269056099074531502841259940379636699304810677716177080486265721322966814104627525953974143476452058638927511594884002185219080847495835727300670028011001853179659250270200020884333850083063514830095064730932997593930711871108436386821290545084229347398808220810263

这是上一个题目的升级，变化如下：

• p、q提升到1024bit数量级，加密指数e降到2
• pad方式变成了：

$$pad(m) = m_1 || h(m_{len}) || h(m_{len}) || m_2$$

• 并且其中哈希函数变成了sha512

但是思路依然没有变化，把加密那一步的等式写出来：

$$c = (m_1 || h(m_{len}) || h(m_{len}) || m_2)^{2} \quad(mod\;n)$$

两个哈希的长度依然固定，均为64字节，所以爆破flag长度可以同时确定以下几个信息：

• 哈希的具体值
• m1以及哈希值的移位数量

确定这两个之后就可以将m1，m2视作二元方程的小根来二元copper了。

同时要注意一个细节，那就是flag长度为奇数的时候，m1和m2拆分长度并不一样，这也会影响对应的移位数。此外，这题小根上界比较紧，所以推荐的做法是把已知的flag头尾给去掉，并且调大多元copper的参数。

exp：

from Crypto.Util.number import *
import hashlib
from tqdm 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 []

def hash(x):
    return hashlib.sha512(x.encode()).digest() * 2

c = 3335299537518434350008670067273514020883265809787658909900831303201069228111667477512288715627313377374377192065531931991830331266940281529429758933125645068623703704431432931062515459304407129764836169638068667723468109909932687335727824459807903558617156661138991973933280805156893120951135488168923425258119689993859896540097318197048436676318334502053269738046279338047497258783747007084564814994803144049365117574904704816542523015746396519693505167963245600047742456478545640334467678554748227823020862550712083249012329745708139070338928730226897923885785783461594034339595106377701306570280371612953393097739
n = 26278624299187148406559772770865336226934633734285979741424867540828670397865189685966828527168795621543490979182417570078991930822041468539855006585233692884235331084907340302530060261742100702658312435180527335101284800616106884692498603300926488358017928867672861988448488439356448543527810620591324774111321619391264173779312033252573140028630441135269056099074531502841259940379636699304810677716177080486265721322966814104627525953974143476452058638927511594884002185219080847495835727300670028011001853179659250270200020884333850083063514830095064730932997593930711871108436386821290545084229347398808220810263

head = bytes_to_long(b"XYCTF{")
tail = bytes_to_long(b"}")
PR.<x,y> = PolynomialRing(Zmod(n))

#len = 73
for length in trange(70,100):
    suffix = bytes_to_long(hash(str(length)))
    if(length % 2 == 0):
        f = (256^(128+length//2)*(256^(length//2-6)*head + x) + 256^(length//2)*suffix + 256*y + tail)^2 - c
        bounds = (256^(length//2-6),256^(length//2-1))
        res = small_roots(f,bounds,1,4)
        if(res != []):
            print(res)
            break
    else:
        f = (256^(128+length//2+1)*(256^(length//2-6)*head + x) + 256^(length//2+1)*suffix + 256*y + tail)^2 - c
        bounds = (256^(length//2-6),256^(length//2))
        res = small_roots(f,bounds,1,4)
        if(res != []):
            print(res)
            break

#XYCTF{jun_mai_quan_xia_ni_xiao_gu___wo_ji_ren_jian_xue_man_tou____114514}

LCG_and_HNP

题目描述：

HNP练习

题目：

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


class LCG:
    def __init__(self, seed, a, b, p):
        self.seed = seed
        self.a = a
        self.b = b
        self.p = p

    def next(self):
        self.seed = (self.seed * self.a + self.b) % self.p
        return self.seed >> (self.p.bit_length() - 8)


m = bytes_to_long(flag)
p = getPrime(128)
a = random.randint(1, p)
b = random.randint(1, p)
seed = random.randint(1, p)
out = []
lcg = LCG(seed, a, b, p)
for i in range(30):
    out.append(lcg.next())
key = ""
while 1:
    key += str(lcg.next())
    if int(key) >= m:
        break

with open("out.txt", "w") as f:
    f.write(f"p={p}\n")
    f.write(f"a={a}\n")
    f.write(f"b={b}\n")
    f.write(f"out={out}\n")
    f.write(f"c={int(key)^m}")

题目是一个比较经典的LCG高位泄露问题。给出连续三十组LCG的泄露高位，要求还原LCG，从而获得由其后续状态拼接而成的密钥key去解得flag。

这类HNP解法也都比较固定，由于泄露的是高位，所以对于相邻的两组数据可以写成：

$$2^{120}x_{i+1,m} + x_{i+1,l} = a(2^{120}x_{i,m} + x_{i,l}) + b \quad(mod\;p)$$

移项整理一下就得到：

$$x_{i+1,l} - ax_{i,l} + (2^{120}x_{i+1,m} - a2^{120}x_{i,m} - b) = 0 \quad(mod\;p)$$

展开为等式：

$$x_{i+1,l} - ax_{i,l} + (2^{120}x_{i+1,m} - a2^{120}x_{i,m} - b) + k_ip = 0$$

其中$x_{i+1,l},x_{i,l}$就是我们想要规约出的两个120bit的小量。将三十组这样的等式结合起来就可以造出如下格：

$$\left( \begin{matrix} 1 & &&&&& -a &&&& \\ &1 &&&&&1 &-a&&& \\ & &1&&&& &1&-a&& \\ & &&\ddots&&& &&&\ddots& \\ & &&&1&&&&&&1 \\ & &&&&1&c_1&c_2&c_3&\cdots&c_{30} \\ &&&&&&p \\ &&&&&&&p \\ &&&&&&&&p \\ &&&&&&&&&\ddots \\ &&&&&&&&&&p \\ \end{matrix} \right)$$

这个格具有线性关系：

$$(x_1,x_2,...,x_{30},1,k_1,k_2,...,k_{29}) \left( \begin{matrix} 1 & &&&&& -a &&&& \\ &1 &&&&&1 &-a&&& \\ & &1&&&& &1&-a&& \\ & &&\ddots&&& &&&\ddots& \\ & &&&1&&&&&&1 \\ & &&&&1&c_1&c_2&c_3&\cdots&c_{30} \\ &&&&&&p \\ &&&&&&&p \\ &&&&&&&&p \\ &&&&&&&&&\ddots \\ &&&&&&&&&&p \\ \end{matrix} \right) = (x_1,x_2,...,x_{30},1,0,0,...,0)$$

当然还有一些配系数的细节操作，由于我前面不少文章都有提到，这里就不展开了。

exp：

from Crypto.Util.number import *

p = 183640370379099520304414468793633666661
a = 36108041497607074474855679331694767924
b = 65925932211985158779695144876342622462
out = [34, 95, 100, 114, 16, 23, 17, 118, 115, 29, 73, 47, 12, 133, 78, 30, 30, 73, 87, 15, 85, 47, 20, 136, 6, 106, 74, 27, 116, 8]
c = 6003642257316152022364486167163125577018867662610595926973616937741281227891381713617380

nums = 30
L = Matrix(ZZ,2*nums,2*nums)
for i in range(nums-1):
    L[i,i] = 1
    L[i,nums+1+i] = -a
    L[i+1,nums+1+i] = 1
    L[nums,nums+1+i] = 2^120*out[i+1] - 2^120*a*out[i] - b
    L[nums+1+i,nums+1+i] = p
L[nums-1,nums-1] = 1
L[nums,nums] = 2^120

L[:,nums+1:] *= p
res = L.LLL()[0]

x = 2^120*out[-1] + abs(res[nums-1])
key = ""
for i in range(100):
    x = (a*x + b) % p
    key += str(x >> 120)
    flag = long_to_bytes(int(key) ^^ c)
    if(b"XYCTF" in flag):
        print(flag)
        break

#XYCTF{2h1_21_ZHi_5h0u_yU_zI_xI3_l@0}

happy_to_solve1

题目描述：

so happy

题目：

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


def get_happy_prime():
    p = getPrime(512)
    q = sympy.nextprime(p ^ ((1 << 512) - 1))
    return p, q


m = bytes_to_long(flag)
p, q = get_happy_prime()
n = p * q
e = 65537
print(n)
print(pow(m, e, n))
# 24852206647750545040640868093921252282805229864862413863025873203291042799096787789288461426555716785288286492530194901130042940279109598071958012303179823645151637759103558737126271435636657767272703908384802528366090871653024192321398785017073393201385586868836278447340624427705360349350604325533927890879
# 14767985399473111932544176852718061186100743117407141435994374261886396781040934632110608219482140465671269958180849886097491653105939368395716596413352563005027867546585191103214650790884720729601171517615620202183534021987618146862260558624458833387692782722514796407503120297235224234298891794056695442287

题目基于RSA分解，其中p、q两个素数的关系是：q是p逐位取反后再取nextprime的值。

这其实就自然产生了两种做法：

• 第一种方法是：由于q可以写成：

$$q = 2^{512} - p + t$$

• 其中t是nextprime带来的小偏差，可以爆破得到，因此可以在ZZ上解如下方程得到p、q：

$$p(2^{512} - p + t) = n$$

• 第二种方法就是正常剪枝，由于p、q大部分高比特位均只有两种可能，所以从高位向低位剪枝就可以得到p、q，最后由于nextprime导致不能深搜的部分就小爆一下解决

exp：

1：

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

n = 24852206647750545040640868093921252282805229864862413863025873203291042799096787789288461426555716785288286492530194901130042940279109598071958012303179823645151637759103558737126271435636657767272703908384802528366090871653024192321398785017073393201385586868836278447340624427705360349350604325533927890879
c = 14767985399473111932544176852718061186100743117407141435994374261886396781040934632110608219482140465671269958180849886097491653105939368395716596413352563005027867546585191103214650790884720729601171517615620202183534021987618146862260558624458833387692782722514796407503120297235224234298891794056695442287
e = 65537

PR.<x> = PolynomialRing(ZZ)
for t in trange(2000):
    f = x*(2^512 - x + t) - n
    res = f.roots()
    if(res != []):
        p = int(res[0][0])
        q = n // p
        print(long_to_bytes(pow(c,inverse(e,(p-1)*(q-1)),n)))
        break

#XYCTF{3f22f4efe3bbbc71bbcc999a0a622a1a23303cdc}

2：

from Crypto.Util.number import *

def find(p,q,length):
    pmin = int(p + (512-length)*"0" , 2)
    pmax = int(p + (512-length)*"1" , 2)
    qmin = int(q + (512-length)*"0" , 2)
    qmax = int(q + (512-length)*"1" , 2)

    if(pmin*qmin > n or pmax*qmax < n):
        return
    
    if(length == 502):
        for i in range(2**10):
            pp = int(p + bin(i)[2:].zfill(10),2)
            if(n % pp == 0):
                qq = n // pp
                print(long_to_bytes(pow(c,inverse(e,(pp-1)*(qq-1)),n)))
                exit()
    
    find(p+"0" , q+"1" , length+1)
    find(p+"1" , q+"0" , length+1)

n = 24852206647750545040640868093921252282805229864862413863025873203291042799096787789288461426555716785288286492530194901130042940279109598071958012303179823645151637759103558737126271435636657767272703908384802528366090871653024192321398785017073393201385586868836278447340624427705360349350604325533927890879
c = 14767985399473111932544176852718061186100743117407141435994374261886396781040934632110608219482140465671269958180849886097491653105939368395716596413352563005027867546585191103214650790884720729601171517615620202183534021987618146862260558624458833387692782722514796407503120297235224234298891794056695442287
e = 65537

find("1","0",1)


#XYCTF{3f22f4efe3bbbc71bbcc999a0a622a1a23303cdc}

happy_to_solve2

题目描述：

so so happy

题目：

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


def get_happy_prime():
    while 1:
        p = int("".join([random.choice("123") for _ in range(512)]))
        q = int("".join([random.choice("567") for _ in range(512)]))
        if isPrime(p) and isPrime(q):
            return (p,q)

m = bytes_to_long(flag)
p ,q= get_happy_prime()
n = p * q
e = 65537
print(n)
print(pow(m, e, n))
# 697906506747097082736076931509594586899561519277373830451275402914416296858960649459482027106166486723487162428522597262774248272216088755005277069446993003521270487750989061229071167729138628583207229945902389632065500739730301375338674342457656803764567184544685006193130563116558641331897204457729877920989968662546183628637193220770495938729301979912328865798266631957128761871326655572836258178871966196973138373358029531478246243442559418904559585334351259080578222274926069834941166567112522869638854253933559832822899069320370733424453856240903784235604251466010104012061821038897933884352804297256364409157501116832788696434711523621632436970698827611375698724661553712549209133526623456888111161142213830821361143023186927163314212097199831985368310770663850851571934739809387798422381702174820982531508641022827776262236373967579266271031713520262606203067411268482553539580686495739014567368858613520107678565628269250835478345171330669316220473129104495659093134763261751546990704365966783697780787341963138501
# 153383826085102296581238539677668696644156148059026868813759015106139131297135097831661048493079405226972222492151356105759235749502324303047037349410709021152255315429280760639113724345836532087970918453353723090554450581657930847674930226113840172368662838756446364482977092478979838209396761279326533419699056209983721842484996150025403009644653678928025861445324715419893797015875541525590135843027312322236085581571452084477262582966972702577136904385741443870527205640874446616413917231260133364227248928492574610248881137364204914001412269740461851747883355414968499272944590071623223603501698004227753335552646715567802825755799597955409228004284739743749531270833084850113574712041224896044525292591264637452797151098802604186311724597450780520140413704697374209653369969451501627583467893160412780732575085846467289134920886789952338174193202234175299652687560232593212131693456966318670843605238958724126368185289703563591477049105538528244632434869965333722691837462591128379816582723367039674028619947057144546

这个题目就是个更经典的深搜了，只是把情景从二进制移到了十进制，具体深搜策略为：

• 从高位往低位逐位深搜
• 将p未深搜到的位置全部填1与将q未深搜到的位置全部填5，乘积应不大于n
• 将p未深搜到的位置全部填3与将q未深搜到的位置全部填7，乘积应不小于n

从而找到n的分解。

exp：

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

e = 65537
n = 697906506747097082736076931509594586899561519277373830451275402914416296858960649459482027106166486723487162428522597262774248272216088755005277069446993003521270487750989061229071167729138628583207229945902389632065500739730301375338674342457656803764567184544685006193130563116558641331897204457729877920989968662546183628637193220770495938729301979912328865798266631957128761871326655572836258178871966196973138373358029531478246243442559418904559585334351259080578222274926069834941166567112522869638854253933559832822899069320370733424453856240903784235604251466010104012061821038897933884352804297256364409157501116832788696434711523621632436970698827611375698724661553712549209133526623456888111161142213830821361143023186927163314212097199831985368310770663850851571934739809387798422381702174820982531508641022827776262236373967579266271031713520262606203067411268482553539580686495739014567368858613520107678565628269250835478345171330669316220473129104495659093134763261751546990704365966783697780787341963138501
c = 153383826085102296581238539677668696644156148059026868813759015106139131297135097831661048493079405226972222492151356105759235749502324303047037349410709021152255315429280760639113724345836532087970918453353723090554450581657930847674930226113840172368662838756446364482977092478979838209396761279326533419699056209983721842484996150025403009644653678928025861445324715419893797015875541525590135843027312322236085581571452084477262582966972702577136904385741443870527205640874446616413917231260133364227248928492574610248881137364204914001412269740461851747883355414968499272944590071623223603501698004227753335552646715567802825755799597955409228004284739743749531270833084850113574712041224896044525292591264637452797151098802604186311724597450780520140413704697374209653369969451501627583467893160412780732575085846467289134920886789952338174193202234175299652687560232593212131693456966318670843605238958724126368185289703563591477049105538528244632434869965333722691837462591128379816582723367039674028619947057144546

def find(ph,qh):
    if(len(ph) == 512):
        p = int(ph)
        q = n // p
        if(p*q == n):
            d = inverse(e,(p-1)*(q-1))
            print(long_to_bytes(pow(c,d,n)))
            exit()
    
    pmin = int(ph + (512-len(ph))*"1")
    qmin = int(qh + (512-len(qh))*"5")
    pmax = int(ph + (512-len(ph))*"3")
    qmax = int(qh + (512-len(qh))*"7")

    if(pmin*qmin <= n and pmax*qmax >=n):
        for i in ("1","2","3"):
            for j in ("5","6","7"):
                find(ph+i,qh+j)

find("","")


#XYCTF{7f4b2241951976ce5ef6df44503209059997e5085d1bc21f6bef4d9effb29fd0}

happy_to_solve3

题目描述：

so so so happy

题目：

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

n = 1024
rho = 2
gamma = 0.352
delta = (1 - gamma) / 2


def get_happy_prime():
    p = getPrime(n // 2)
    q = getPrime(n // 2)
    N = p * q
    if 2 * q - p > gmpy2.iroot(N, 3)[0] and 2 * q - p < int(N**gamma / 16):
        d = random.randint(int(N ** (delta - 0.001)), int(N**delta))
        e = gmpy2.invert(d, (p - 1) * (q - 1))
        return N, e


N, e = get_happy_prime()
m = bytes_to_long(flag)
print(N)
print(e)
print(pow(m, e, N))
# 262520792590557046276663232446026434827811478251833823563978322470880473096166170973396967071440576532100045206129176936699321058518888771220060450723297988984995658582283884954240129867538637146924315603797818982078845855992582229939200744016516540207525916858674450616913948112117516831530578235916528257187
# 202935305174706906986376186864051444100197589482194720650385604617995167023220940138899902073948844285283834058445151666398192104922822110762965750590312021079147170573038600118139119881722125346545331027913695559130179278058419339157557267195396326664433859683010193688491694572425231599139974726246205888139
# 66173406204647583141174847814283540389326401056490970592017577810775087017197392456634167609680060931553017712058528056769618111925816921272571306246667527546366331057781905353553621522209713637253380859235235590286779517552635935384231694255450099095196595516174794966487058693308544109311774074970769293357

题目基于RSA分解，其参数特殊性在于：

• p和2q的差距是个350bit左右的小量
• d仅有333bit左右，达到了N^0.324

所以应该是要完成诸如boneh and durfee之类的低解密指数攻击，但是d并不在0.292的理论上界之内，因此要想办法利用上第一个条件。

而第一个条件给我们的信息其实是：

$$2q - p = t$$

所以有：

$$(2q-t)q = n$$

由于t是一个350bit左右的小量，所以对n/2开根，得到的高位也就是q的高位，有了q的高位也就有了p的高位，所以就可以把已知的高位信息加入到boneh的攻击中去求根。具体怎么实施可以看下面这篇文章的Insights一题：

2023-CryptoCTF-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

exp：

from Crypto.Util.number import *
import itertools

"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = False

"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct 
upperbound on the determinant. Note that this 
doesn't necesseraly mean that no solutions 
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False

"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension

############################################
# Functions
##########################################

# display stats on helpful vectors
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1

    print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print (a)

# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
    # end of our recursive function
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB

    # we start by checking from the end
    for ii in range(current, -1, -1):
        # if it is unhelpful:
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            # let's check if it affects other vectors
            for jj in range(ii + 1, BB.dimensions()[0]):
                # if another vector is affected:
                # we increase the count
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj

            # level:0
            # if no other vectors end up affected
            # we remove it
            if affected_vectors == 0:
                print ("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB

            # level:1
            # if just one was affected we check
            # if it is affecting someone else
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # if it is affecting even one vector
                    # we give up on this one
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # remove both it if no other vector was affected and
                # this helpful vector is not helpful enough
                # compared to our unhelpful one
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # nothing happened
    return BB

""" 
Returns:
* 0,0   if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May
    
    finds a solution if:
    * d < N^delta
    * |x| < e^delta
    * |y| < e^0.5
    whenever delta < 1 - sqrt(2)/2 ~ 0.292
    """

    # substitution (Herrman and May)
    PR.<u, x, y> = PolynomialRing(ZZ)
    Q = PR.quotient(x*y + 1 - u) # u = xy + 1
    polZ = Q(pol).lift()

    UU = XX*YY + 1

    # x-shifts
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()

    # x-shifts list of monomials
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials():
            if monomial not in monomials:
                monomials.append(monomial)
    monomials.sort()
    
    # y-shifts (selected by Herrman and May)
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # substitution
    
    # y-shifts list of monomials
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)

    # construct lattice B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)

    # Prototype to reduce the lattice
    if helpful_only:
        # automatically remove
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        # reset dimension
        nn = BB.dimensions()[0]
        if nn == 0:
            print ("failure")
            return 0,0

    # check if vectors are helpful
    if debug:
        helpful_vectors(BB, modulus^mm)
    
    # check if determinant is correctly bounded
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        print ("We do not have det < bound. Solutions might not be found.")
        print ("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print ("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^mm)

    # LLL
    if debug:
        print ("optimizing basis of the lattice via LLL, this can take a long time")

    BB = BB.LLL()

    if debug:
        print ("LLL is done!")

    # transform vector i & j -> polynomials 1 & 2
    if debug:
        print ("looking for independent vectors in the lattice")
    found_polynomials = False
    
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            # for i and j, create the two polynomials
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)

            # resultant
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)

            # are these good polynomials?
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print ("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break

    if not found_polynomials:
        print ("no independant vectors could be found. This should very rarely happen...")
        return 0, 0
    
    rr = rr(q, q)

    # solutions
    soly = rr.roots()

    if len(soly) == 0:
        print ("Your prediction (delta) is too small")
        return 0, 0

    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]

    #
    return solx, soly


nbit = 1024
n = 262520792590557046276663232446026434827811478251833823563978322470880473096166170973396967071440576532100045206129176936699321058518888771220060450723297988984995658582283884954240129867538637146924315603797818982078845855992582229939200744016516540207525916858674450616913948112117516831530578235916528257187
e = 202935305174706906986376186864051444100197589482194720650385604617995167023220940138899902073948844285283834058445151666398192104922822110762965750590312021079147170573038600118139119881722125346545331027913695559130179278058419339157557267195396326664433859683010193688491694572425231599139974726246205888139
c = 66173406204647583141174847814283540389326401056490970592017577810775087017197392456634167609680060931553017712058528056769618111925816921272571306246667527546366331057781905353553621522209713637253380859235235590286779517552635935384231694255450099095196595516174794966487058693308544109311774074970769293357

import gmpy2
qh = int(gmpy2.iroot(n//2,2)[0] >> 360 << 360)
ph = (n // qh) >> 360 << 360


#part1 boneh and durfee to get d
if(1):
    m = 3
    delta = 0.33
    t = int((1-2*delta) * m)  # optimization from Herrmann and May
    X = 2*floor(n^delta)  # this _might_ be too much
    Y = 2^360   # correct if p, q are ~ same size

    A = (n+1)//2 - (ph+qh)//2
    PR.<x,y> = PolynomialRing(ZZ)
    f = 1+x*(A+y)
    res = boneh_durfee(f, e, m, t, X, Y)
    print(res)

#part2 get d
res = (11905625603785812461702294975756895543980946484478574101835243414442286593759448613358049647316155274, 152665725363549086276160040606397627101715395584023352342706962320368673856094243978666140464721353176202314)
k2 = 11905625603785812461702294975756895543980946484478574101835243414442286593759448613358049647316155274
pl_ql = 152665725363549086276160040606397627101715395584023352342706962320368673856094243978666140464721353176202314
d = (1+k2*(A+pl_ql)) // e
print(len(bin(d)))
print(long_to_bytes(int(pow(c,d,n))))


#XYCTF{68f1880cdafd99fbf9a156946cb39dd86477886f1d115636e149e12c16f99af0}

重生之我要当oi爷 pro

题目描述：

算法什么的很简单啦

题目：

def f(a, b, p):
    t = 0
    for i in range(len(b)):
        t += pow(a, i, p) * b[i] % p
    return t % p

p = 1041231053

a = open("flag.png", "rb").read()
b = open("enc.txt", "w")
for i in range(len(a)):
    b.write(str(i) + str(f(i, a, p)) + "\n")

题目是今年picoCTF的原题flag_printer，是基于普通拉格朗日插值的优化，由于有一百多万个点对所以直接插值会相当慢，必须要用分治法去减小复杂度。

算法具体原理我并没有仔细去研究，可以参考：

多项式多点求值|快速插值 - OI Wiki (oi-wiki.org)

由于是原题所以找个exp就能直接跑了，我直接用的普通速度的脚本，sage9.3大约跑了3h左右，听说用原repository的fast脚本只需要十分钟。

exp：

import multiprocessing as mp

p = 1041231053

X = []
Y = []
for line in open(r'D:\CTF_challs\py\crypto\2024\XYCTF 2024\encoded.txt', 'r').read().strip().split('\n'):
    x, y = line.split(' ')
    X.append(int(x))
    Y.append(int(y))

K = GF(p)
R = PolynomialRing(K, 'x')

def compZ(X):
    x = R.gen()
    Z = K(1)
    for xk in X:
        Z *= (x-xk)
    return Z

def comp(X, Y, Xother):
    Z = compZ(Xother)
    Y = [y/Z(x) for x, y in zip(X, Y)]
    return Y, Z

def solve(X, Y):
    n = len(Y)
    print("Solving for", n, "points...")

    # just use lagrange interpolation if the degree is small enough
    if n <= 10:
        return R.lagrange_polynomial(list(zip(X, Y)))

    nhalf = n // 2

    X1 = X[:nhalf]
    Y1 = Y[:nhalf]
    X2 = X[nhalf:]
    Y2 = Y[nhalf:]

    # parallelize the computation of the two halves
    if nhalf > 10000:
        with mp.Pool(2) as pool:
            result1 = pool.apply_async(comp, (X1, Y1, X2))
            result2 = pool.apply_async(comp, (X2, Y2, X1))

            Y1, Z2 = result1.get()
            Y2, Z1 = result2.get()
    else:
        Y1, Z2 = comp(X1, Y1, X2)
        Y2, Z1 = comp(X2, Y2, X1)

    # solve recursively
    f1 = solve(X1, Y1)
    f2 = solve(X2, Y2)

    # put it back together
    return f1*Z2 + f2*Z1

def test():
    Xt = X[:1000]
    Yt = Y[:1000]
    f = solve(Xt, Yt)
    for x, y in zip(Xt, Yt):
        assert f(x) == y

test()

f = solve(X, Y)

with open("111.bmp","wb") as tt:
    tt.write(bytearray(f.coefficients(sparse=False)[:-1]))

Random_rr

题目描述：

你们最爱的随机数

题目：

from Crypto.Util.number import *

from random import randint
flag=b'XYCTF{uuid}'
flag = bytes_to_long(flag)
n = 472993274721871037103726599805149366727531552333249750035977291933239067588481589544777397613192273114354221827196579379954069925604091911249655707080927769808587176515295614018992848517984372306879552247519117116110554431341268358177159108949791969262793325836353834899335531293329721598226413212541536002401507477776699642647348576111445702197483449777741566350285229621935507081895389023444249054515395783080003733803406382744631528246608154546123270319561514117323480441428953306734274538511770278887429407127143049023747710881993279361892937905382946820141513009017756811296722630617325141162244806884220212939955235410280899112731530527048274396186038160728562551536558223235783656985493518204710943916486379681906506757757594165379493317173050550893487151879681122510523721157284728808336110950008840684602353984682117748018347433177541603140491131603068512706893984834735290809952944273565203183330739252949245209529232254867201402656024997949207918675051941911990640248052951780195402390132237903538546705181463959793972284823588987652138458328270662652334799233015314673544813649692428544375538627858921763941533600553536579901589575693816746953261108022490849251974419402753031545629158199093099096735356165044275617408697
rr = 11898141078345200236264081467585899457224809417108457314508072413792599039332439547789237898270544336909458761754683941320649771736625000667170176071314483
def generate():
    fw = open("random", "w")
    for i in range(648):
        fw.write(str(random.getrandbits(32))+"\n")
    fw.close()
generate()
key = str(random.getrandbits(32))
key1= int(str(key)[0])
ks = [randint(0, rr**(i+key1-1)) for i in range(16)]
c1 = pow(sum(k*flag**i for i, k in enumerate(ks)), 127, n)
c2 = pow(flag, 65537, n)
ks = [pow(69, k+key, rr**(i+key1)) for i, k in enumerate(ks)]
print(f"{ks = }")
print(f"{c1 = }")
print(f"{c2 = }")

这个题目交给队友去完成了，在完成第一步MT19937的伪随机数预测之后，剩下的部分和bi0sCTF的rr一题完全相同，可以参考：

2024-bi0sCTF-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

Complex_dlp

题目描述：

复数域下的dlp

hint：如何把复数转成实数

题目：

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


class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)

    def __str__(self):
        if self.im == 0:
            return str(self.re)
        elif self.re == 0:
            if abs(self.im) == 1:
                return f"{'-' if self.im < 0 else ''}i"
            else:
                return f"{self.im}i"
        else:
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"


def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result


flag = flag.strip(b"XYCTF{").strip(b"}")
p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027
g = Complex(3, 7)
x = bytes_to_long(flag)
print(complex_pow(g, x, p))
# 5699996596230726507553778181714315375600519769517892864468100565238657988087817 + 198037503897625840198829901785272602849546728822078622977599179234202360717671908i

这个题目我先按照hint对应的思路讲，因为我的做法相比较起来不容易理解一些。

hint解法

hint指出想办法把复数转化到实数上，其实这个意思和矩阵利用行列式转化到实数上很像。比如对于复数c，由于有：

$$c = a + bi$$

其模长为：

$$|c| = \sqrt{a^2 + b^2}$$

而对于c的平方来说：

$$c^2 = (a^2 - b^2) + 2abi$$

所以其模长为：

$$|c^2| = \sqrt{(a^2 - b^2)^2 + 4a^2b^2} = a^2 + b^2$$

可以看出对于复数来说，将其做平方，其模长也会对应做平方；推而广之，复数的n次幂的模长也就是复数模长的n次幂。所以这样一来就可以把复数域的dlp转化到GF(p)上求解了，由于p-1很光滑所以dlp易求。

实际处理可能会遇到一个问题，就是模长的根号内部可能并不是二次剩余，但是处理方式也很简单，把模长的dlp再转化为模长平方的dlp即可。

我的思路

我的做法和抽象代数关系大一些，由于题目p模4余3，因此x^2+1是个不可约多项式，所以模p下的复数域其实可以看做是由该多项式作为双边理想构成的GF(p)的二次扩域：

$$C = \frac{Z_p[x]}{x^2 + 1}$$

这个扩域的大小是p^2，其乘法群是一个大小为p^2-1的循环群(去掉零元)，所以分别有大小为p-1、p+1的子群，由于p-1光滑所以可以直接在该子群求解dlp。

exp：

from Crypto.Util.number import *

p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027
F.<i> = GF(p^2, modulus = x^2 + 1)

g = F(3 + 7*i)
c = F(5699996596230726507553778181714315375600519769517892864468100565238657988087817 + 198037503897625840198829901785272602849546728822078622977599179234202360717671908*i)

m = discrete_log(F(c^(p+1)) , F(g^(p+1)) , operation="*" , ord=p-1)
print(long_to_bytes(int(m)))

#XYCTF{___c0mp13x_d1p_15_3@5y_f0r_y0u___}

Sign1n[签到]

题目描述：

看看密码签到题吧 :D

题目：

from Crypto.Util.number import *
from tqdm import *
import gmpy2
flag=b'XYCTF{uuid}'
flag=bytes_to_long(flag)
leak=bin(int(flag))
while 1:
    leak += "0"
    if len(leak) == 514:
        break

def swap_bits(input_str):
    input_list = list(input_str[2:])
    length = len(input_list)

    for i in range(length // 2):
        temp = input_list[i]
        input_list[i] = input_list[length - 1 - i]
        input_list[length - 1 - i] = temp

    return ''.join(input_list)

input_str = leak
result = swap_bits(input_str)
a=result

def custom_add(input_str):
    input_list = list(input_str)
    length = len(input_list)
    
    for i in range(length):
        input_list[i] = str((int(input_list[i]) + i + 1) % 10)

    result = ''.join(input_list)
    return result


input_str = a
result = custom_add(input_str)
b=result
print(b)
#12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567891134567799012455779902334677900124556899012356679001344567990233457780113445788911245667991134457799122355788001245578890223467799013445688902335578800123457889113346778902344567991223557880013355689911245667900124556789122355788001234678891133467799023445679902334568900123556899012456679001344578801233467789112355779912234577990233556780113

把代码理完就可以知道直接回推就可以得到初始值。

exp：

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

b = 12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567891134567799012455779902334677900124556899012356679001344567990233457780113445788911245667991134457799122355788001245578890223467799013445688902335578800123457889113346778902344567991223557880013355689911245667900124556789122355788001234678891133467799023445679902334568900123556899012456679001344578801233467789112355779912234577990233556780113
c = list(map(int,str(b)))

#part1 reverse custom
for i in range(len(c)):
    c[i] = (c[i] - 1 - i) % 10

#part2 recover swap
for i in range(len(c)//2):
    temp = c[i]
    c[i] = c[511-i]
    c[511-i] = temp


#part3 get flag
flag = "0" + "".join(list(map(str,c)))[:-1]
print(long_to_bytes(int(flag,2)))


#XYCTF{38d8d9e8-0c9e-48e0-b1b6-5593dd30f6ea}

babyRSAMAX

题目描述：

听说你们数学很好，我不信我不信；）

题目：

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

flag = b'XYCTF{******}'
e = '?'
def getBabyPrime(nbits):
    while True:
        p = 1
        while p.bit_length() <= nbits:
            p *= choice(sieve_base)
        
        if isPrime(p+1):
            return p+1

p = getBabyPrime(512)
q = getBabyPrime(512)
n = p*q
gift1 = (pow(p,e,n)-pow(q,e,n)) % n
gift2 = pow(p+q,e,n)

t = 65537
x = bytes_to_long(e)
y = pow(x, t, n)

m = bytes_to_long(flag)
c = powmod(m, e, n)

print(f'n = {n}')
print(f'gift1 = {gift1}')
print(f'gift2 = {gift2}')
print(f'c = {c}')
print(f'y = {y}')

'''
n = 39332423872740210783246069030855946244104982381157166843977599780233911183158560901377359925435092326653303964261550158658551518626014048783435245471536959844874036516931542444719549997971482644905523459407775392702211086149279473784796202020281909706723380472571862792003687423791576530085747716706475220532321
gift1 = 4549402444746338327349007235818187793950285105091726167573552412678416759694660166956782755631447271662108564084382098562999950228708300902201571583419116299932264478381197034402338481872937576172197202519770782458343606060544694608852844228400457232100904217062914047342663534138668490328400022651816597367310
gift2 = 111061215998959709920736448050860427855012026815376672067601244053580566359594802604251992986382187891022583247997994146019970445247509119719411310760491983876636264003942870756402328634092146799825005835867245563420135253048223898334460067523975023732153230791136870324302259127159852763634051238811969161011462
c = 16938927825234407267026017561045490265698491840814929432152839745035946118743714566623315033802681009017695526374397370343984360997903165842591414203197184946588470355728984912522040744691974819630118163976259246941579063687857994193309554129816268931672391946592680578681270693589911021465752454315629283033043
y = 1813650001270967709841306491297716908969425248888510985109381881270362755031385564927869313112540534780853966341044526856705589020295048473305762088786992446350060024881117741041260391405962817182674421715239197211274668450947666394594121764333794138308442124114744892164155894256326961605137479286082964520217

'''

题目基于RSA分解，不过给了很多额外条件，具体来说有如下几个：

• p-1、q-1均光滑

算了不写了，因为只用上面这个条件就可以完成n的分解，之后就可以解第一层得到加密指数e为4096，之后可以用rabin解flag也可以直接有限域开根。

exp：

from Crypto.Util.number import *

n = 39332423872740210783246069030855946244104982381157166843977599780233911183158560901377359925435092326653303964261550158658551518626014048783435245471536959844874036516931542444719549997971482644905523459407775392702211086149279473784796202020281909706723380472571862792003687423791576530085747716706475220532321
gift1 = 4549402444746338327349007235818187793950285105091726167573552412678416759694660166956782755631447271662108564084382098562999950228708300902201571583419116299932264478381197034402338481872937576172197202519770782458343606060544694608852844228400457232100904217062914047342663534138668490328400022651816597367310
gift2 = 111061215998959709920736448050860427855012026815376672067601244053580566359594802604251992986382187891022583247997994146019970445247509119719411310760491983876636264003942870756402328634092146799825005835867245563420135253048223898334460067523975023732153230791136870324302259127159852763634051238811969161011462
c = 16938927825234407267026017561045490265698491840814929432152839745035946118743714566623315033802681009017695526374397370343984360997903165842591414203197184946588470355728984912522040744691974819630118163976259246941579063687857994193309554129816268931672391946592680578681270693589911021465752454315629283033043
y = 1813650001270967709841306491297716908969425248888510985109381881270362755031385564927869313112540534780853966341044526856705589020295048473305762088786992446350060024881117741041260391405962817182674421715239197211274668450947666394594121764333794138308442124114744892164155894256326961605137479286082964520217

#part1 factor n(p-1 smooth)
a = 2
m = 2
while True:
    a = pow(a, m, n)
    p = GCD(a-1, n)
    if p != 1 and p != n:
        break
    m += 1
q = n // p
phi = (p-1)*(q-1)


#part2 get e
e = pow(y,inverse(65537,phi),n)
#print(long_to_bytes(e))
e = 4096


#part3 get flag
res = Zmod(p)(c).nth_root(e, all=True)
for i in res:
    temp = long_to_bytes(int(i))
    if(b"XYCTF" in temp):
        print(temp)


#XYCTF{Rabin_is_so_biggggg!}

fakeRSA

题目描述：

无描述就是最好的描述，嘿嘿！

hint：考点:jordan

题目：

from Crypto.Util.number import *

flag = b'XYCTF{******}'
n = ZZ(bytes_to_long(flag))
p = getPrime(int(320))
print(p)

G = Zmod(p)

def function(X, Y, Z):
    def part(a, b, c):
        return vector([9 * a - 36 * c, 6 * a - 27 * c, b])
    def parts(n):
        Gx.<a, b, c> = G[]
        if n == 0: return vector([a, b, c])
        mid = parts(n // 2)
        result = mid(*mid)
        if n % 2 == 0: return result
        else: return part(*result)
    return parts(n)(X, Y, Z)

print(function(69, 48, 52))


#1849790472911267366045392456893126092698743308291512220657006129900961168811898822553602045875909
#(1431995965813617415860695748430644570118959991271395110995534704629241309597572003500157255135707, 1011565891130611736600822618382801465506651972373410962205810570075870804325974377971089090196019, 784497518859893244278116222363814433595961164446277297084989532659832474887622082585456138030246)

完成这个题目要分析清楚function函数的功能，对于part函数，其作用为实现一个如下的线性变换：

$$\left( \begin{matrix} a'\\ b'\\ c' \end{matrix} \right) = \left( \begin{matrix} 9 && -36 \\ 6 && -27 \\ & 1 & \\ \end{matrix} \right) \left( \begin{matrix} a\\ b\\ c \end{matrix} \right) \quad(mod\;p)$$

而parts函数则是在用递归方式实现矩阵快速幂，所以function最终返回的结果其实是：

$$\left( \begin{matrix} a'\\ b'\\ c' \end{matrix} \right) = \left( \begin{matrix} 9 && -36 \\ 6 && -27 \\ & 1 & \\ \end{matrix} \right)^n \left( \begin{matrix} 69\\ 48\\ 52 \end{matrix} \right) \quad(mod\;p)$$

其中n是flag的值，也就是说我们实际上是要解决一个矩阵dlp问题。

而这个题目必须要使用jordan form来求解，这是因为如果使用行列式方法，p-1并不光滑；如果使用一般线性群的阶，他所有的子群阶也都不光滑。而jordan form求dlp的本质是解一个模p下的线性方程组，所以和p-1是否光滑并没有关系。

具体来说，现在的问题如下，记：

$$L = \left( \begin{matrix} 9 && -36 \\ 6 && -27 \\ & 1 & \\ \end{matrix} \right)$$ $$Ln = \left( \begin{matrix} 9 && -36 \\ 6 && -27 \\ & 1 & \\ \end{matrix} \right)^n$$

其中Ln可以由初始态和终态去继续递推几次，得到满秩的线性方程组求解得到，所以现在就是已知L和Ln，求解指数n的dlp问题。

而化为jordan form的做法原理如下，任何一个非奇异矩阵L都可以通过如下方式变换成jordan form：

$$L = PJP^{-1}$$

其中P是可逆矩阵，J是jordan型矩阵。这样做的好处在于矩阵的幂次可以写为：

$$Ln = L^n = (L)^n = (PJP^{-1})^n = PJ^nP^{-1}$$

所以有：

$$P^{-1}LnP = J^n$$

而对于题目的L，其jordan form是一个特征值为3的三阶jordan块：

$$J = \left( \begin{matrix} 3 &1& \\ &3& 1 \\ & &3 \\ \end{matrix} \right)$$

特征值为a的n阶jordan块就是指如下形式的矩阵：

$$J_{n}(a) = \left( \begin{matrix} a &1&& \\ &a& 1& \\ && \ddots& \\ & &&a&1 \\ & &&&a \\ \end{matrix} \right)$$

可以看出这样的jordan块其实满足：

$$J_n(a) = J_n(0) + aE$$

所以对于本题的J^n，可以将下式用二项式定理展开：

$$J^n = (J(0) + 3E)^n = J(0)^n + 3nJ(0)^{n-1} + ... + 3^nE$$

而由于J(0)自乘三次之后就会变成0矩阵，所以其实最后就剩：

$$J^n = (J(0) + 3E)^n = C^n_{2}3^{n-2}J(0)^{2} + n3^{n-1}J(0) + 3^nE$$

类似的可以推到更高阶的二项式展开情形

所以J^n最终为：

$$J^n = \left( \begin{matrix} 3^n &n3^{n-1}&C^n_{2}3^{n-2} \\ &3^n& n3^{n-1} \\ & &3^n \\ \end{matrix} \right)$$

所以通过取他的左上角的值，可以得到3^n和n3^(n-1)在模p下的值，所以求n就很简单了。

exp：

from Crypto.Util.number import *

p = 1849790472911267366045392456893126092698743308291512220657006129900961168811898822553602045875909
G = Zmod(p)


L = Matrix(Zmod(p),[
    [9,0,-36],
    [6,0,-27],
    [0,1,0]
])
vec1 = (69, 48, 52)
vec2 = (1431995965813617415860695748430644570118959991271395110995534704629241309597572003500157255135707, 1011565891130611736600822618382801465506651972373410962205810570075870804325974377971089090196019, 784497518859893244278116222363814433595961164446277297084989532659832474887622082585456138030246)

vec1 = vector(Zmod(p),vec1)
vec2 = vector(Zmod(p),vec2)

M1 = Matrix(Zmod(p),Matrix(vec1).T)
M1 = M1.augment(L*vec1)
M1 = M1.augment(L^2*vec1)

M2 = Matrix(Zmod(p),Matrix(vec2).T)
M2 = M2.augment(L*vec2)
M2 = M2.augment(L^2*vec2)

R = M2*M1^(-1)

gl, P = L.jordan_form(transformation=True)
gr = P^(-1)*R*P

g = gl[0,0] 
t = gr[0,1] # t = ng^(n-1)
k = gr[1,1] # k = g^n
#so gt = nk  ->  n = gtk^(-1)

n = g * t * inverse(k,p) % p

print(long_to_bytes(int(n)))

#XYCTF{y0u_finally_f0und_t3h_s3cr3ts!!}

铜匠

题目描述：

copper练习

题目：

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

m = bytes_to_long(flag)
m1 = getRandomRange(1, m)
m2 = getRandomRange(1, m)
m3 = m - m1 - m2


def task1():
    e = 149
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    d = inverse(e,(p-1)*(q-1))
    return (pow(m1, e, n), d >> 222 << 222, n)


def task2():
    e = 65537
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    return (pow(m2, e, n), (p + q) & ((1 << 624) - 1), n)


def task3():
    e = 65537
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    return (pow(m3, e, n), (p ^ q) >> 200, n)


c1, leak1, n1 = task1()
c2, leak2, n2 = task2()
c3, leak3, n3 = task3()
print(c1, leak1, n1)
print(c2, leak2, n2)
print(c3, leak3, n3)
# (89623543982221289730635223555830551523170205418976759060541832483843039074358160566735322009158596405712449020903311144480669706226166537602750967447480664875090686428406188847601970724994074417752345460791736191511081890913041143570455636020205647345764692062144226011846336769477026234106683791286490222089, 138474880017294332349992670187778287774153347391371789199005713563195654993662610111557185709277805165708109047494971468100563949333712521647405765501704478862377527360106399421209690341743821320754482338590671565510629203215009008479290995785318405211007685664887994061938667418220613430135743123498167435264, 146331610798417415036517077006943013321623040860385791423062775325646472298267580898028515394910588437521335092742913111680737790430660749825981979147191282007208147041227246620008377726207734522466015971515317594545750944838673018946440525615131606652748549901880641896940968837669894325535750125282351577689)
# (5473961166821344576614003060897848014482672788904094340704447882490091115468180944569409159343222459801235179587721232166576530621751748850763430788036935832653535110975154800191323351333883661451331971042214143454441651165718504131976920077768864850035471790911190772583977173388975105970866592974077361193822302653046511418190410043729876062517148438923211673300268277037622337403526399584759202097925983596261279676101079771530118525540842499517622478819211528345668513680064744443628779623340175578509413636950545134641050948185944279029949957748464529075830770617236599864271566534714755373562527112224962839980,62964793504732923650344975634773688108135580826064134090114181449607062497690184718845295432644650580930430061411603385577783897575232298084007041511817031640186953023971498914096209984730,20748652069632848434897928314437138341436264859802586939154590237186029244907936870477844563166827587536149170710720365760129683024401957095447466056746469055173897234659911291443605912459271248059341147358511860537769587963189092648473894868209838600346115919726589891777340166174017389513260737891557712152871714337946675533597049874155202056200170954033849176655928144354665553271709442011723088448485570394208728775665739819536229908847043007472178803394055783543378990699834066614262050119443421709878598533329555838915158259138297060574425019923291353077080236769586821808150397875920110335669136563171420068201)
# (34640310217688693418173336791306022698488916505988760907493665070072623574363578354500529023855888624978101429772253437880445815006839767802433777006836665709335479076676231470534690281412388704665083311568028710188940132495410474044569100181764053297307413009214044407982980600917158732129850605715306726034, 3763587651775261955566046684899146246387485307521708557610018711932791630073528010801142052497, 94848869174430082173244966077736519396702141299429965725051314270443078621842166791082354594193554380275167898342497998871366256044865879909218309960595691008663632410356093966762639308253848450178310347612630814852054763933063313537694449475061227647475480417779126252294793767003555255527593551612032661749)

题目是三个part的copper，这里分开阐述。

part1

第一部分似乎和密码挑战赛的赛题11撞了，这里不太好直接展开说做法，密码挑战赛结束之后再更新。

part2

题目泄露的信息是p+q的低624位。由于有：

$$n = pq$$

这个等式自然在任何模数下都成立，也就有：

$$n = pq \quad(mod\;2^{624})$$

把已知条件放进来：

$$n = p(leak-p) \quad(mod\;2^{624})$$

所以可以在模2^624下解得p可能的低624bit，然后就转化成p低位泄露的问题了，对所有可能值逐一copper来得到正确解。

part3

题目泄露的信息是p^q的高312位，这里需要把剪枝和copper结合起来，做法可以参考鹏城杯的一道题目：

2023-鹏城杯-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

exp：

from Crypto.Util.number import *
from tqdm 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()
    
    k = ZZ(f.coefficients().pop(0))
    g = gcd(k, N)
    k = R(k/g)

    f *= 1/k
    f = f.change_ring(ZZ)

    vars = f.variables()
    G = Sequence([], f.parent())
    for k in range(m):
        for i in range(m-k+1):
            for subvars in itertools.combinations_with_replacement(vars[1:], i):
                g = f**k * prod(subvars) * N**(max(d-k, 0))
                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, Integer(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 []


c1,leak1,n1 = (89623543982221289730635223555830551523170205418976759060541832483843039074358160566735322009158596405712449020903311144480669706226166537602750967447480664875090686428406188847601970724994074417752345460791736191511081890913041143570455636020205647345764692062144226011846336769477026234106683791286490222089, 138474880017294332349992670187778287774153347391371789199005713563195654993662610111557185709277805165708109047494971468100563949333712521647405765501704478862377527360106399421209690341743821320754482338590671565510629203215009008479290995785318405211007685664887994061938667418220613430135743123498167435264, 146331610798417415036517077006943013321623040860385791423062775325646472298267580898028515394910588437521335092742913111680737790430660749825981979147191282007208147041227246620008377726207734522466015971515317594545750944838673018946440525615131606652748549901880641896940968837669894325535750125282351577689)
c2,leak2,n2 = (5473961166821344576614003060897848014482672788904094340704447882490091115468180944569409159343222459801235179587721232166576530621751748850763430788036935832653535110975154800191323351333883661451331971042214143454441651165718504131976920077768864850035471790911190772583977173388975105970866592974077361193822302653046511418190410043729876062517148438923211673300268277037622337403526399584759202097925983596261279676101079771530118525540842499517622478819211528345668513680064744443628779623340175578509413636950545134641050948185944279029949957748464529075830770617236599864271566534714755373562527112224962839980,62964793504732923650344975634773688108135580826064134090114181449607062497690184718845295432644650580930430061411603385577783897575232298084007041511817031640186953023971498914096209984730,20748652069632848434897928314437138341436264859802586939154590237186029244907936870477844563166827587536149170710720365760129683024401957095447466056746469055173897234659911291443605912459271248059341147358511860537769587963189092648473894868209838600346115919726589891777340166174017389513260737891557712152871714337946675533597049874155202056200170954033849176655928144354665553271709442011723088448485570394208728775665739819536229908847043007472178803394055783543378990699834066614262050119443421709878598533329555838915158259138297060574425019923291353077080236769586821808150397875920110335669136563171420068201)
c3,leak3,n3 = (34640310217688693418173336791306022698488916505988760907493665070072623574363578354500529023855888624978101429772253437880445815006839767802433777006836665709335479076676231470534690281412388704665083311568028710188940132495410474044569100181764053297307413009214044407982980600917158732129850605715306726034, 3763587651775261955566046684899146246387485307521708557610018711932791630073528010801142052497, 94848869174430082173244966077736519396702141299429965725051314270443078621842166791082354594193554380275167898342497998871366256044865879909218309960595691008663632410356093966762639308253848450178310347612630814852054763933063313537694449475061227647475480417779126252294793767003555255527593551612032661749)
e1,e2,e3 = 149,65537,65537


############################################# task1
k1 = e1*leak1 // n1 + 1
PR.<x,y> = PolynomialRing(Zmod(e1*leak1))
f = 1 + k1*((n1+1)-y) - e1*x
bounds = (2^222,2^513)

res = small_roots(f,bounds,m=2,d=2)
leak = int(res[0][1])

PR.<x> = PolynomialRing(RealField(1000))
f = x*(leak-x) - n1
ph = int(f.roots()[0][0])


PR.<x> = PolynomialRing(Zmod(n1))
f = ph + x
res = f.small_roots(X=2^(222+6), beta=0.499,epsilon=0.02)[0]
p1 = int(ph + res)
q1 = n1 // p1
d1 = inverse(e1,(p1-1)*(q1-1))
m1 = pow(c1,d1,n1)


############################################# task1
if(0):
    PR.<x> = PolynomialRing(Zmod(n2))
    pl = var('pl')
    p0 = solve_mod([pl*(leak2-pl) - n2  == 0], 2^624)
    for i in tqdm(p0):
        temp = int(i[0])
        f = 2^624*x + temp
        f = f.monic()
        res = f.small_roots(X=2^(1024-624), beta=0.499,epsilon=0.05)
        if(res != []):
            print(res,i)
p2 = 2^624*1818858780662674672546519234621144829011634239453991533158800384602749900390376290902354433158869501621068317141437803547 + 30799806171826831530692477758473366666506107409058776239288103697521834047472422841398780886795811096950227412499497614896605408091510012455390741008241034524397897872311534501791582888829
q2 = n2 // p2
d2 = inverse(e2,(p2-1)*(q2-1))
m2 = pow(c2,d2,n2)


############################################# task1
leak3 = leak3 << 200
LEAK = bin(leak3)[2:].zfill(512)
def find(ph,qh,h):
    pM = int(ph + (512-h)*"1",2)
    qM = int(qh + (512-h)*"1",2)
    pm = int(ph + (512-h)*"0",2)
    qm = int(qh + (512-h)*"0",2)

    if(h == 512 - 200):
        PR.<x> = PolynomialRing(Zmod(n3))
        f = pm + x
        res = f.small_roots(X=2^200,beta=0.499)
        if(res != []):
            p3 = int(pm + int(res[0]))
            q3 = n3 // p3
            d3 = inverse(e3,(p3-1)*(q3-1))
            m3 = pow(c3,d3,n3)
            print(long_to_bytes(int(m1+m2+m3)))

    if(pM*qM < n3 or pm*qm > n3):
        return
    
    if(LEAK[h] == "0"):
        find(ph+"1",qh+"1",h+1)
        find(ph+"0",qh+"0",h+1)
    else:
        find(ph+"1",qh+"0",h+1)
        find(ph+"0",qh+"1",h+1)

find("1","1",1)


#XYCTF{___y0u_k0nW_h0w_t0_s01v3_c0pP3r_th15_15_y0r_fl@9_hahahaha!!!___}

factor3

题目描述：

这个e咋比n还大啊*逆天！*逆天！

题目：

from Crypto.Util.number import *
import random

flag = b'XYCTF{*****}'
m = bytes_to_long(flag)
def gainPrime():
    while True:
        x = random.getrandbits(256)
        y = random.getrandbits(256)

        if y % 2 == 0:
            continue

        p = x ** 3 + 3 * y ** 3
        if p.bit_length() == 768 and p % 2 == 1 and isPrime(p):
            return p

p, q = gainPrime(), gainPrime()
N = p * q
phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
d = getPrime(320)
e = inverse(d, phi)
c = d**2^m

print(f"N: {N}")
print(f"e: {e}")
print(f"c: {c}")

N: 913125842482770239379848062277162627509794409924607555622246822717218133091223291889541294440266178282194506242444509803611492259403578922020590849630191477864719052980160940803309686069818208833547621252544423652489179493083138385424424384165228024273745733240109761707533778691158938848158094054261174692601673435971526522219273943464877956131040249169850420336023942653021547841666224446678539579529590840999008107782784268926145671962239929431694391039559247
e: 494518390582436635999115147756676313570637682518235195828939117782099618734167908630788943568232122157772909140885391963441876427590731524706959546524212914108888799081844320513851526790475333924396837458796755678072486028072639014677580265244176441153444956871730684233063789931539669072735599696830757690822185323538738397827461580678488181113667710378657058297572328491762536595872579603698945272140918157163640403488075948987156585480146162739943419183496337465468187233821931312507662218106713861638334075899266373256620752680354704533272722692596941861606161634082613228896420520465402725359166156632884432690715903666803067996854084671477445131853993177110154928274312496230096270510089973592664248613332000290545537840595645944390047611474888693558676781309912289044962293014118087259307560444929227407113819165713213046898243995956550944640168932947118400215917515277554126694376415569909534496134700668701465649939
c: 4450931337369461482106945992542133557585962894030505065110870389112565329875502952762182372926117037373210509516570958483606566274369840551132381128665744266165792377925899683228751870742727716

题目基于求解RSA的私钥，需要获取d^2并与c异或得到明文m的值。而参数具有如下特殊性：

• d仅有320bit
• e和d满足的式子为：

$$ed = 1 + k(p^2+p+1)(q^2+q+1)$$

其中k和d数量级相近。

我的思路依然是copper，将式子展开得到：

$$ed = 1 + k(n^2 + pq^2 + q^2 + p^2q + n + q + p^2 + p + 1)$$

合并一下同类项：

$$ed = 1 + k[n^2 + n + 1 + n(p+q) + p^2 + q^2 + p + q]$$

再变换：

$$ed = 1 + k[n^2 + n + 1 + n(p+q) + (p+q)^2 - 2n + p + q]$$

所以最终得到：

$$ed = 1 + k[n^2 - n + 1 + (n+1)(p+q) + (p+q)^2]$$

令x=k，y=p+q，得到模e下的多项式：

$$f = 1 + x[n^2 - n + 1 + (n+1)y + y^2] \quad(mod\;e)$$

然后就可以copper求解出k和p+q的值了。

exp：

from Crypto.Util.number import *
from gmpy2 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 []

n = 913125842482770239379848062277162627509794409924607555622246822717218133091223291889541294440266178282194506242444509803611492259403578922020590849630191477864719052980160940803309686069818208833547621252544423652489179493083138385424424384165228024273745733240109761707533778691158938848158094054261174692601673435971526522219273943464877956131040249169850420336023942653021547841666224446678539579529590840999008107782784268926145671962239929431694391039559247
e = 494518390582436635999115147756676313570637682518235195828939117782099618734167908630788943568232122157772909140885391963441876427590731524706959546524212914108888799081844320513851526790475333924396837458796755678072486028072639014677580265244176441153444956871730684233063789931539669072735599696830757690822185323538738397827461580678488181113667710378657058297572328491762536595872579603698945272140918157163640403488075948987156585480146162739943419183496337465468187233821931312507662218106713861638334075899266373256620752680354704533272722692596941861606161634082613228896420520465402725359166156632884432690715903666803067996854084671477445131853993177110154928274312496230096270510089973592664248613332000290545537840595645944390047611474888693558676781309912289044962293014118087259307560444929227407113819165713213046898243995956550944640168932947118400215917515277554126694376415569909534496134700668701465649939
c = 4450931337369461482106945992542133557585962894030505065110870389112565329875502952762182372926117037373210509516570958483606566274369840551132381128665744266165792377925899683228751870742727716

PR.<x,y>=PolynomialRing(Zmod(e))
f = 1 + x*(n^2-n+1 + (n+1)*y + y^2)
res = small_roots(f, (2^320,2^769), m=2, d=3)

pplusq = int(res[0][1])
pminusq = iroot(pplusq^2-4*n,2)[0]
p = (pplusq + pminusq) // 2
q = n // p

d = inverse(e,(p^2+p+1)*(q^2+q+1))
print(long_to_bytes(d^2 ^^ c))


#XYCTF{I_love_to_read_the_crypto_paper_and_try_to_ak_them}