2022NCTF

这次Crypto题目对于我来说过于困难，还好战队的佬写了wp

Coloratura

题目

from Crypto.Util.number import long_to_bytes
from PIL import Image, ImageDraw
from random import getrandbits

width = 208
height = 208
flag = open('flag.txt').read()


def makeSourceImg():
    colors = long_to_bytes(getrandbits(width * height * 24))[::-1]
    img = Image.new('RGB', (width, height))
    x = 0
    for i in range(height):
        for j in range(width):
            img.putpixel((j, i), (colors[x], colors[x + 1], colors[x + 2]))
            x += 3
    return img


def makeFlagImg():
    img = Image.new("RGB", (width, height))
    draw = ImageDraw.Draw(img)
    draw.text((5, 5), flag, fill=(255, 255, 255))
    return img


if __name__ == '__main__':
    img1 = makeSourceImg()
    img2 = makeFlagImg()
    img3 = Image.new("RGB", (width, height))
    for i in range(height):
        for j in range(width):
            p1, p2 = img1.getpixel((j, i)), img2.getpixel((j, i))
            img3.putpixel((j, i), tuple([(p1[k] ^ p2[k]) for k in range(3)]))
    img3.save('attach.png')

解题脚本

from PIL import Image

def inverse_shift(x, shift, type, mask=0xffffffff, nbit=32):
    res = x
    for _ in range(nbit//shift):
        if type == 'l': res = x ^ res << shift & mask
        if type == 'r': res = x ^ res >> shift & mask
    return res
def crack_extract(x):
    x = inverse_shift(x, 18, 'r')
    x = inverse_shift(x, 15, 'l', 4022730752)
    x = inverse_shift(x,  7, 'l', 2636928640)
    x = inverse_shift(x, 11, 'r')
    return x
def crack_twist(cur):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908b0df
    state = cur
    for i in range(623,-1,-1):
        tmp = state[i]^state[(i+397)%624]
        # recover Y,tmp = Y
        if tmp & high == high:
            tmp ^= mask
            tmp <<= 1
            tmp |= 1
        else:
            tmp <<=1
        # recover highest bit
        res = tmp&high
        # recover other 31 bits,when i =0,it just use the method again it so beautiful!!!!
        tmp = state[i-1]^state[(i+396)%624]
        # recover Y,tmp = Y
        if tmp & high == high:
            tmp ^= mask
            tmp <<= 1
            tmp |= 1
        else:
            tmp <<=1
        res |= (tmp)&low
        state[i] = res
    return state
def extract(x):
    y = x
    y = y ^ y >> 11
    y = y ^ y << 7 & 2636928640
    y = y ^ y << 15 & 4022730752
    y = y ^ y >> 18
    return y

width = 208
height = 208
img3 = Image.open('attach.png')
out = []
for i in range(height):
    for j in range(width):
        pix = img3.getpixel((j, i))
        out += [pix[0], pix[1], pix[2]]

out = [hex(_)[2:].zfill(2) for _ in out][::-1]
out = ''.join(out)
now_rand = [out[i: i + 8] for i in range(0, len(out), 8)][::-1]
now_rand = [int(_, 16) for _ in now_rand]

state = [crack_extract(_) for _ in now_rand[-624:]]
ini_rand = []
while len(ini_rand) < len(now_rand):
    ini_rand = [extract(_) for _ in state] + ini_rand
    state = crack_twist(state)

ini_rand = [hex(_)[2:].zfill(8) for _ in ini_rand][::-1]
ini_rand = ''.join(ini_rand)
ini = [ini_rand[i: i + 2] for i in range(0, len(ini_rand), 2)][::-1]
ini = [int(_, 16) for _ in ini]

x = 0
flag = Image.new('RGB', (width, height))
for i in range(height):
    for j in range(width):
        pix = img3.getpixel((j, i))
        flag.putpixel((j, i), (pix[0] ^ ini[x], pix[1] ^ ini[x + 1], pix[2] ^ ini[x + 2]))
        x += 3
flag.show()

dp_promax

题目

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


nbits = 2200
beta = 0.4090
p, q = getPrime(int((1. - beta) * nbits)), getPrime(int(beta * nbits))
dp = getrandbits(50) | 1
while True:
    d = (p - 1) * getrandbits(2800) + dp
    if GCD((p - 1) * (q - 1), d) == 1:
        break
e = inverse(d, (p - 1) * (q - 1))
N = p * q
flag = bytes_to_long(open('flag.txt', 'rb').read())

c = pow(flag, e, N)
print(N)
print(e)
print(c)

"""
46460689902575048279161539093139053273250982188789759171230908555090160106327807756487900897740490796014969642060056990508471087779067462081114448719679327369541067729981885255300592872671988346475325995092962738965896736368697583900712284371907712064418651214952734758901159623911897535752629528660173915950061002261166886570439532126725549551049553283657572371862952889353720425849620358298698866457175871272471601283362171894621323579951733131854384743239593412466073072503584984921309839753877025782543099455341475959367025872013881148312157566181277676442222870964055594445667126205022956832633966895316347447629237589431514145252979687902346011013570026217
13434798417717858802026218632686207646223656240227697459980291922185309256011429515560448846041054116798365376951158576013804627995117567639828607945684892331883636455939205318959165789619155365126516341843169010302438723082730550475978469762351865223932725867052322338651961040599801535197295746795446117201188049551816781609022917473182830824520936213586449114671331226615141179790307404380127774877066477999810164841181390305630968947277581725499758683351449811465832169178971151480364901867866015038054230812376656325631746825977860786943183283933736859324046135782895247486993035483349299820810262347942996232311978102312075736176752844163698997988956692449
28467178002707221164289324881980114394388495952610702835708089048786417144811911352052409078910656133947993308408503719003695295117416819193221069292199686731316826935595732683131084358071773123683334547655644422131844255145301597465782740484383872480344422108506521999023734887311848231938878644071391794681783746739256810803148574808119264335234153882563855891931676015967053672390419297049063566989773843180697022505093259968691066079705679011419363983756691565059184987670900243038196495478822756959846024573175127669523145115742132400975058579601219402887597108650628746511582873363307517512442800070071452415355053077719833249765357356701902679805027579294
"""

发现N可以分解

import gmpy2
import libnum
e = 13434798417717858802026218632686207646223656240227697459980291922185309256011429515560448846041054116798365376951158576013804627995117567639828607945684892331883636455939205318959165789619155365126516341843169010302438723082730550475978469762351865223932725867052322338651961040599801535197295746795446117201188049551816781609022917473182830824520936213586449114671331226615141179790307404380127774877066477999810164841181390305630968947277581725499758683351449811465832169178971151480364901867866015038054230812376656325631746825977860786943183283933736859324046135782895247486993035483349299820810262347942996232311978102312075736176752844163698997988956692449
c = 28467178002707221164289324881980114394388495952610702835708089048786417144811911352052409078910656133947993308408503719003695295117416819193221069292199686731316826935595732683131084358071773123683334547655644422131844255145301597465782740484383872480344422108506521999023734887311848231938878644071391794681783746739256810803148574808119264335234153882563855891931676015967053672390419297049063566989773843180697022505093259968691066079705679011419363983756691565059184987670900243038196495478822756959846024573175127669523145115742132400975058579601219402887597108650628746511582873363307517512442800070071452415355053077719833249765357356701902679805027579294
p=3628978044425516256252147348112819551863749940058657194357489608704171827031473111609089635738827298682760802716155197142949509565102167059366421892847010862457650295837231017990389942425249509044223464186611269388650172307612888367710149054996350799445205007925937223059
q=12802692475349485610473781287027553390253771106432654573503896144916729600503566568750388778199186889792482907407718147190530044920232683163941552482789952714283570754056433670735303357508451647073211371989388879428065367142825533019883798121260838408498282273223302509241229258595176130544371781524298142815099491753819782913040582455136982147010841337850805642005577584947943848348285516563
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,p*q)
print(libnum.n2s(int(m)))
#nctf{Th1s_N_May_n0t_s0@o0@@_secur3}

superecc

题目

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

assert flag[:5] == b'nctf{'


class super_ecc:
    def __init__(self):
        self.a = 73101304688827564515346974949973801514688319206271902046500036921488731301311
        self.c = 78293161515104296317366169782119919020288033620228629011270781387408756505563
        self.d = 37207943854782934242920295594440274620695938273948375125575487686242348905415
        self.p = 101194790049284589034264952247851014979689350430642214419992564316981817280629

    def add(self, P, Q):
        (x1, y1) = P
        (x2, y2) = Q
        x3 = (x1 * y2 + y1 * x2) * inverse(self.c * (1 + self.d * x1 * x2 * y1 * y2), self.p) % self.p
        y3 = (y1 * y2 - self.a * x1 * x2) * inverse(self.c * (1 - self.d * x1 * x2 * y1 * y2), self.p) % self.p
        return (x3, y3)

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


flag = bytes_to_long(flag[5:-1])
ecc = super_ecc()
G = (30539694658216287049186009602647603628954716157157860526895528661673536165645,
     64972626416868540980868991814580825204126662282378873382506584276702563849986)
S = ecc.mul(flag, G)
print(S)
# (98194560294138607903211673286210561363390596541458961277934545796708736630623,
# 58504021112693314176230785309962217759011765879155504422231569879170659690008)

脚本

考查的是Twisted Edward Curve

题⽬定义了⼀个循环群上的点加法，搜索可以发现是Twisted Edward Curve

经过适当的变化可以将c消除掉，得到标准形式

对于Twisted Edward Curve，可以转化为等价的Montgomery Curve

Montgomery Curve的形式已经是Weierstrass形式的椭圆曲线，可以使⽤sage求解其阶，即求得了Twisted Edward Curve的阶寻找阶中的⼩素数因⼦，使⽤Pohlig Hellman + BSGS求解离散对数问题，得到flag的值

#!/usr/bin/env sage
class super_ecc:
    def __init__(self):
        self.a = 73101304688827564515346974949973801514688319206271902046500036921488731301311
        self.c = 78293161515104296317366169782119919020288033620228629011270781387408756505563
        self.d = 37207943854782934242920295594440274620695938273948375125575487686242348905415
        self.p = 101194790049284589034264952247851014979689350430642214419992564316981817280629
        self.INF = (0, self.c)

    def add(self, P, Q):
        (x1, y1) = P
        (x2, y2) = Q
        x3 = (x1 * y2 + y1 * x2) * inverse_mod(self.c * (1 + self.d * x1 * x2 * y1 * y2), self.p) % self.p
        y3 = (y1 * y2 - self.a * x1 * x2) * inverse_mod(self.c * (1 - self.d * x1 * x2 * y1 * y2), self.p) % self.p
        return (x3, y3)

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

def get_order():
    d = d * c^4 % p
    A = 2 * (a + d) * inverse_mod(a - d, p) % p
    B = 4 * inverse_mod(a - d, p) % p
    a1 = 0
    a3 = 0
    a2 = A*B%p
    a4 = B*B%p
    a6 = 0
    E=EllipticCurve(GF(p),[a1,a2,a3,a4,a6])
    np=E.cardinality()
    return ZZ(np)

ecc = super_ecc()

from tqdm import tqdm
def Pohlig_Hellman(L, R, sub_order, order):
    def add(P, Q):
        return ecc.add(P, Q)
    def mul(P, x):
        return ecc.mul(x % order, P)
    def BSGS(L, R, sub):
        L, R = mul(L, (order//sub)), mul(R, (order//sub))

        m, dic = sqrt(sub).round(), dict()
        ga = mul(L, 0)
        for i in tqdm(range(m + 1)):
            dic[str(ga)], ga = i, add(ga, L)
        gb = mul(L, (-m))
        for i in tqdm(range(sub//m + 1)):
            if str(R) in dic:
                sk = i*m + dic[str(R)]
                print(f"{sub} -> {sk}")
                return ZZ(sk)
            R = add(R, gb)
        return None

    sk = crt(
        [BSGS(L, R, sub) for sub in sub_order],
        sub_order
    )
    return sk

# order = get_order()
order = 101194790049284589034264952247851014979635478581961323247248565451562534055248
sub_order = [16, 113, 28921, 749971, 87374629]
G = (30539694658216287049186009602647603628954716157157860526895528661673536165645,
     64972626416868540980868991814580825204126662282378873382506584276702563849986)
S = (98194560294138607903211673286210561363390596541458961277934545796708736630623,
     58504021112693314176230785309962217759011765879155504422231569879170659690008)

sk = Pohlig_Hellman(G, S, sub_order, order)
from Crypto.Util.number import *
print(long_to_bytes(sk))