NCTF 2022 Official WriteUp——Crypto

Misc

只因因

首先通过重复的特征氨基酸序列对给出的基因片段进行排列

通过比对发现，3片段中的内容被1片段和5片段包含，6片段被2片段包含。

得出排序：4-2-5-1，把重复段去除，得到完整的基因段

TGTCTGCCATTCTTAAAAACAAAAATGTTGTTATTTTTATTTCAGATGCGATCTGTGAGCCGAGTCTTTA

其反向互补序列

TAAAGACTCGGCTCACAGATCGCATCTGAAATAAAAATAACAACATTTTTGTTTTTAAGA
ATGGCAGACA

通过http://www.ncbi.nlm.nih.gov/BLAST/中的核苷酸查询（blastn），并且根据题目限定的种属，找到对应基因名称

cystic fibrosis transmembrane conductance regulator，简写为CFTR。

非预期
直接搜索一段序列就能找到国外教材的原题，或者直接在给出的网站搜索一段序列就能找到对应蛋白质。

这题是对象的一道遗传学作业题的简化版，师傅们太强啦

Crypto

coloratura

一道经典的MT19937题。

看到本题取随机数的函数为 colors = long_to_bytes(getrandbits(width * height * 24))[::-1]，通过测试我们可以知道，getrandbits函数在收到超出32比特的参数，会把已生成的state放在低位，高位放置新生成的state。这里倒序则是把state0放在了最开始。

注意到draw.text((5, 5), flag, fill=(255, 255, 255))，flag填充的位置在(5,5)，所以我们有4行未经过异或的原值，其比特数为 $208*4*24=32*624$ ，刚好有624组state，然后我们就可以依次生成后续的内容得到原图，异或之后得到flag图像。

还有的师傅是通过图像的中间部分获取624个state，然后向前恢复状态，也是一种思路。

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


def invert_right(m, l, val=''):
    length = 32
    mx = 0xffffffff
    if val == '':
        val = mx
    i, res = 0, 0
    while i * l < length:
        mask = (mx << (length - l) & mx) >> i * l
        tmp = m & mask
        m = m ^ tmp >> l & val
        res += tmp
        i += 1
    return res


def invert_left(m, l, val):
    length = 32
    mx = 0xffffffff
    i, res = 0, 0
    while i * l < length:
        mask = (mx >> (length - l) & mx) << i * l
        tmp = m & mask
        m ^= tmp << l & val
        res |= tmp
        i += 1
    return res


def invert_temper(m):
    m = invert_right(m, 18)
    m = invert_left(m, 15, 4022730752)
    m = invert_left(m, 7, 2636928640)
    m = invert_right(m, 11)
    return m


def clone_mt(record):
    state = [invert_temper(i) for i in record]
    gen = random.Random()
    gen.setstate((3, tuple(state + [0]), None))
    return gen


def makeSourceImg():
    colors = long_to_bytes(g.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


height, width = 208, 208

img = Image.open('attach.png')
a = []
for i in range(4):
    for j in range(208):
        p = img.getpixel((j, i))
        for pi in p:
            a.append(pi)
M = []
for i in range(len(a) // 4):
    px = (a[4 * i + 3] << 24) + (a[4 * i + 2] << 16) + (a[4 * i + 1] << 8) + a[4 * i + 0]
    M.append(px)

g = clone_mt(M)

img1 = makeSourceImg()
img2 = Image.open('attach.png')
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('flag.png')

superecc

本题主要考察对于扭曲爱德华曲线方程到 Weierstrass 曲线的转换。

首先我们需要知道，本题使用的曲线方程为

这是一个一般性的扭曲爱德华曲线方程，我们对其变形，让其成为我们熟知的扭曲爱德华曲线形式

接下来，我们需要把扭曲爱德华曲线映射为蒙哥马利曲线，再用蒙哥马利曲线映射到 Weierstrass 曲线。映射方式如下：

映射后，我们分析曲线的阶和点的阶，发现符合Pohlig-Hellman的攻击方式。exp如下

from Crypto.Util.number import *
p = 101194790049284589034264952247851014979689350430642214419992564316981817280629
a = 73101304688827564515346974949973801514688319206271902046500036921488731301311
c = 78293161515104296317366169782119919020288033620228629011270781387408756505563
d = 37207943854782934242920295594440274620695938273948375125575487686242348905415
P.<z> = PolynomialRing(Zmod(p))

aa = a
dd = (d*c^4)%p
J = (2*(aa+dd)*inverse(aa-dd,p))%p
K = (4*inverse(aa-dd,p))%p
A = ((3-J^2)*inverse(3*K^2,p))%p
B = ((2*J^3-9*J)*inverse(27*K^3,p))%p

for i in  P(z^3+A*z+B).roots():
    alpha = int(i[0])
    print(kronecker(3*alpha^2+A,p))
    for j in P(z^2-(3*alpha^2+A)).roots():
        s = int(j[0])
        s = inverse_mod(s, p)
        if J==alpha*3*s%p:
            Alpha = alpha
            S = s

def twist_to_weier(x,y):
    v = x*inverse(c,p)%p
    w = y*inverse(c,p)%p
    assert (aa*v^2+w^2)%p==(1+dd*v^2*w^2)%p
    s = (1+w)*inverse_mod(1-w,p)%p
    t = s*inverse(v,p)%p
    assert (K*t^2)%p==(s^3+J*s^2+s)%p
    xW = (3*s+J) * inverse_mod(3*K, p) % p
    yW = t * inverse_mod(K, p) % p
    assert yW^2 % p == (xW^3+A*xW+B) % p
    return (xW,yW)

def weier_to_twist(x,y):
    xM=S*(x-Alpha)%p
    yM=S*y%p
    assert (K*yM^2)%p==(xM^3+J*xM^2+xM)%p
    xe = xM*inverse_mod(yM,p)%p
    ye = (xM-1)*inverse_mod(xM+1,p)%p
    assert (aa*xe^2+ye^2)%p==(1+dd*xe^2*ye^2)%p
    xq = xe*c%p
    yq = ye*c%p
    assert (a*xq^2+yq^2)%p==c^2*(1+d*xq^2*yq^2)
    return (xq,yq)

E = EllipticCurve(GF(p), [A, B])
G = twist_to_weier(30539694658216287049186009602647603628954716157157860526895528661673536165645,64972626416868540980868991814580825204126662282378873382506584276702563849986)
Q = twist_to_weier(98194560294138607903211673286210561363390596541458961277934545796708736630623,58504021112693314176230785309962217759011765879155504422231569879170659690008)
P = E(G)
Q = E(Q)
factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-2]
print(primes)
dlogs = []
for fac in primes:
    t = int(int(P.order()) // int(fac))
    dlog = discrete_log(t*Q,t*P,operation="+")
    dlogs += [dlog]
    print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
flag=crt(dlogs,primes)
print(long_to_bytes(flag))

当然，在选手wp里，我也看到有师傅在转化为蒙哥马利曲线后，就直接定义曲线，这也是可以的。

dp_promax

本题是Secure_in_N的加强版（Secure_in_N在NSSCTF上有，感兴趣的师傅可以去看看），实际上是作者对论文方法的改进，让界扩大了。

本题特别感谢春哥提供的出题思路和相关实现，春哥在我出这题时给我提供了很多帮助、解答了我很多疑问，如果师傅们对本题内容有什么想法欢迎找我或者春哥讨论。本题DeeBaTo师傅参考了 Small CRT-Exponent RSA Revisited ，此文章的方法是对本题涉及方法的进一步扩展，扩大了本题相关论文的边界，感兴趣的师傅们也可以找DeeBaTo师傅讨论（dbt太强辣）。

这道题目的数据，我在赛前在facdb上查了是没有n的分解的，但是在比赛期间又能查到。更抽象的是分解上传的时间在比赛前，emmmm，算是我出题的一个失误吧，如果直接放远程随机n的形式，效果应该会好一点。revenge方法和本题预期解一样，就不另外写题解了。

2002年，Alexander May发表了文章 Cryptanalysis of Unbalanced RSA with Small CRT-Exponent，在其第四节提到了一种构造多项式和对应格的方法，其界为 $\beta < N^{0.382}$ 。当时May构造的多项式为二元，这就会让格的行列式较大，对于更宽泛的界就难以归约出结果。

2006年，Daniel Bleichenbacher 和 Alexander May 发表了文章 New Attacks on RSA with Small Secret CRT-Exponents，在这篇文章里第四节，两人给当年的多项式，引入了一个对应 $p$ 的新变量 $z$，使得 $yz=N$。通过引入这个新变量，降低了y的幂，从而让其行列式变小，当然新变量的幂也会相反增大行列式，因此需要平衡这两者达到规约出结果的目的。本题的实现也是依照第四节中描述的方法实现的。

作者给多项式乘了系数 $z^s$ ，并得到如下多项式：

我们知道 $yz=N$ ，所以式子中需要对 $y,z$ 的积化简。对于单项式 $x^iy^j$， 当 $j\ge s$ ，单项式变为 $x^iy^{j-s}$，系数 $a_{i,j}$ 变为 $a_{i,j}N^s$；当 $j<s$ ，单项式变为 $x^iz^{s-j}$ ，系数变为 $a_{i,j}N^j$。

def trans(f):
    my_tuples = f.exponents(as_ETuples=False)
    g = 0
    for my_tuple in my_tuples:
        exponent = list(my_tuple)
        mon = x ^ exponent[0] * y ^ exponent[1] * z ^ exponent[2]
        tmp = f.monomial_coefficient(mon)
        
        my_minus = min(exponent[1], exponent[2])
        exponent[1] -= my_minus
        exponent[2] -= my_minus
        tmp *= N^my_minus
        tmp *= x ^ exponent[0] * y ^ exponent[1] * z ^ exponent[2]
        
        g += tmp
    return g

然后我们需要由系数向量 $g'(xX, yY, zZ),h'(xX, yY, zZ)$ 构造一个下三角矩阵。这里文章中并未告诉我们如何构造这样的矩阵，所以我们需要自己构造一个偏序。我们可以每次选一个多项式，跟已知的单项式集合做差，如果大小为1，就将这个差作为一个新的主元。

# construct partial order
while len(my_polynomials) > 0:
    for i in range(len(my_polynomials)):
        f = my_polynomials[i]
        current_monomial_set = set(x^tx * y^ty * z^tz for tx, ty, tz in f.exponents(as_ETuples=False))
        delta_set = current_monomial_set - known_set
        if len(delta_set) == 1:
            new_monomial = list(delta_set)[0]
            my_monomials.append(new_monomial)
            known_set |= current_monomial_set
            new_polynomials.append(f)            
            my_polynomials.pop(i)
            break
    else:
        raise Exception('GG')

于是，我们就可以构造出一个下三角矩阵，但由于我们之前化简的时候乘了 $N^j$，所以此时在对角线上可能有因数 $N^j$ ，这会让格的行列式大很多。我们需要对其对应的多项式乘上 $N^j$ 对 $e$ 的逆，以此消去这样的影响，让格的行列式尽可能的小。

# remove N^j
for i in range(nrows):
    Lii = L[i][i]
    N_Power = 1
    while (Lii % N == 0):
        N_Power *= N
        Lii //= N
    L[i][i] = Lii
    for j in range(ncols):
        if (j != i):
            L[i][j] = (L[i][j] * inverse_mod(N_Power, e^m))

此时，我们对格进行LLL规约，会得到两个短的系数向量 $f_1(xX, yY, zZ),f_2(xX, yY, zZ)$，根据Howgrave Graham定理，他们在整数域上有根 $(x_0,p,q)$。接下来就需要用式子 $yz=N$，消去 $z$，在消元后的二元多项式里找到解即可。

以上就是本题的大致思路，下面对一些用到的参数进行说明，这部分的内容在论文的证明部分，具体就不多赘述。

变量上界 $X=2N^{\alpha+\beta+\delta-1}$，$Y=N^{\beta}$，$Z=2N^{1-\beta}$

对于变量 $m$ 文章并没有给出明确的不等式，只说了 $N$ 和 $m$ 充分大，所以 $m$ 需要慢慢试（也许）。

完整exp如下

from copy import deepcopy
# https://www.iacr.org/archive/pkc2006/39580001/39580001.pdf
# Author: ZM__________J, To1in
N = 46460689902575048279161539093139053273250982188789759171230908555090160106327807756487900897740490796014969642060056990508471087779067462081114448719679327369541067729981885255300592872671988346475325995092962738965896736368697583900712284371907712064418651214952734758901159623911897535752629528660173915950061002261166886570439532126725549551049553283657572371862952889353720425849620358298698866457175871272471601283362171894621323579951733131854384743239593412466073072503584984921309839753877025782543099455341475959367025872013881148312157566181277676442222870964055594445667126205022956832633966895316347447629237589431514145252979687902346011013570026217
e = 13434798417717858802026218632686207646223656240227697459980291922185309256011429515560448846041054116798365376951158576013804627995117567639828607945684892331883636455939205318959165789619155365126516341843169010302438723082730550475978469762351865223932725867052322338651961040599801535197295746795446117201188049551816781609022917473182830824520936213586449114671331226615141179790307404380127774877066477999810164841181390305630968947277581725499758683351449811465832169178971151480364901867866015038054230812376656325631746825977860786943183283933736859324046135782895247486993035483349299820810262347942996232311978102312075736176752844163698997988956692449
alpha = log(e, N)
beta = 0.4090
delta = 50/2200
P.<x,y,z>=PolynomialRing(ZZ)

X = ceil(2 * N^(alpha + beta + delta - 1))
Y = ceil(2 * N^beta)
Z = ceil(2 * N^(1 - beta))

def f(x,y):
    return x*(N-y)+N
def trans(f):
    my_tuples = f.exponents(as_ETuples=False)
    g = 0
    for my_tuple in my_tuples:
        exponent = list(my_tuple)
        mon = x ^ exponent[0] * y ^ exponent[1] * z ^ exponent[2]
        tmp = f.monomial_coefficient(mon)
        
        my_minus = min(exponent[1], exponent[2])
        exponent[1] -= my_minus
        exponent[2] -= my_minus
        tmp *= N^my_minus
        tmp *= x ^ exponent[0] * y ^ exponent[1] * z ^ exponent[2]
        
        g += tmp
    return g


m = 5 # need to be adjusted according to different situations
tau = ((1 - beta)^2 - delta) / (2 * beta * (1 - beta))
sigma = (1 - beta - delta) / (2 * (1 - beta))

print(sigma * m)
print(tau * m)

s = ceil(sigma * m)
t = ceil(tau * m)
my_polynomials = []
for i in range(m+1):
    for j in range(m-i+1):
        g_ij = trans(e^(m-i) * x^j * z^s * f(x, y)^i)
        my_polynomials.append(g_ij)

for i in range(m+1):
    for j in range(1, t+1):
        h_ij = trans(e^(m-i) * y^j * z^s * f(x, y)^i)
        my_polynomials.append(h_ij)
        
known_set = set()
new_polynomials = []
my_monomials = []

# construct partial order
while len(my_polynomials) > 0:
    for i in range(len(my_polynomials)):
        f = my_polynomials[i]
        current_monomial_set = set(x^tx * y^ty * z^tz for tx, ty, tz in f.exponents(as_ETuples=False))
        delta_set = current_monomial_set - known_set
        if len(delta_set) == 1:
            new_monomial = list(delta_set)[0]
            my_monomials.append(new_monomial)
            known_set |= current_monomial_set
            new_polynomials.append(f)            
            my_polynomials.pop(i)
            break
    else:
        raise Exception('GG')
        
my_polynomials = deepcopy(new_polynomials)

nrows = len(my_polynomials)
ncols = len(my_monomials)
L = [[0 for j in range(ncols)] for i in range(nrows)]

for i in range(nrows):
    g_scale = my_polynomials[i](X * x, Y * y, Z * z)
    for j in range(ncols):
        L[i][j] = g_scale.monomial_coefficient(my_monomials[j])
        

# remove N^j
for i in range(nrows):
    Lii = L[i][i]
    N_Power = 1
    while (Lii % N == 0):
        N_Power *= N
        Lii //= N
    L[i][i] = Lii
    for j in range(ncols):
        if (j != i):
            L[i][j] = (L[i][j] * inverse_mod(N_Power, e^m))

L = Matrix(ZZ, L)
nrows = L.nrows()

L = L.LLL()
# Recover poly
reduced_polynomials = []
for i in range(nrows):
    g_l = 0
    for j in range(ncols):
        g_l += L[i][j] // my_monomials[j](X, Y, Z) * my_monomials[j]
    reduced_polynomials.append(g_l)

# eliminate z
my_ideal_list = [y * z - N] + reduced_polynomials

# Variety
my_ideal_list = [Hi.change_ring(QQ) for Hi in my_ideal_list]
for i in range(len(my_ideal_list),3,-1):
    print(i)
    V = Ideal(my_ideal_list[:i]).variety(ring=ZZ)
    print(V)
#[{z: 12802692475349485610473781287027553390253771106432654573503896144916729600503566568750388778199186889792482907407718147190530044920232683163941552482789952714283570754056433670735303357508451647073211371989388879428065367142825533019883798121260838408498282273223302509241229258595176130544371781524298142815099491753819782913040582455136982147010841337850805642005577584947943848348285516563, y: 3628978044425516256252147348112819551863749940058657194357489608704171827031473111609089635738827298682760802716155197142949509565102167059366421892847010862457650295837231017990389942425249509044223464186611269388650172307612888367710149054996350799445205007925937223059, x: 405726385819346439624373295724174904587513703028810607887196207245590677314635812068207279608967556024765942887396159920943510998058855747055443081960935792673829634461468743022155648395228589917369402664408573172965003110508338065148371590644205978916495280169653332814813227881426466}]

from Crypto.Util.number import *
q = 3628978044425516256252147348112819551863749940058657194357489608704171827031473111609089635738827298682760802716155197142949509565102167059366421892847010862457650295837231017990389942425249509044223464186611269388650172307612888367710149054996350799445205007925937223059
N = 46460689902575048279161539093139053273250982188789759171230908555090160106327807756487900897740490796014969642060056990508471087779067462081114448719679327369541067729981885255300592872671988346475325995092962738965896736368697583900712284371907712064418651214952734758901159623911897535752629528660173915950061002261166886570439532126725549551049553283657572371862952889353720425849620358298698866457175871272471601283362171894621323579951733131854384743239593412466073072503584984921309839753877025782543099455341475959367025872013881148312157566181277676442222870964055594445667126205022956832633966895316347447629237589431514145252979687902346011013570026217
p = N//q
c = 28467178002707221164289324881980114394388495952610702835708089048786417144811911352052409078910656133947993308408503719003695295117416819193221069292199686731316826935595732683131084358071773123683334547655644422131844255145301597465782740484383872480344422108506521999023734887311848231938878644071391794681783746739256810803148574808119264335234153882563855891931676015967053672390419297049063566989773843180697022505093259968691066079705679011419363983756691565059184987670900243038196495478822756959846024573175127669523145115742132400975058579601219402887597108650628746511582873363307517512442800070071452415355053077719833249765357356701902679805027579294
e = 13434798417717858802026218632686207646223656240227697459980291922185309256011429515560448846041054116798365376951158576013804627995117567639828607945684892331883636455939205318959165789619155365126516341843169010302438723082730550475978469762351865223932725867052322338651961040599801535197295746795446117201188049551816781609022917473182830824520936213586449114671331226615141179790307404380127774877066477999810164841181390305630968947277581725499758683351449811465832169178971151480364901867866015038054230812376656325631746825977860786943183283933736859324046135782895247486993035483349299820810262347942996232311978102312075736176752844163698997988956692449
d = inverse(e,(p-1))
print(d)
print(long_to_bytes(int(pow(int(c),int(d),int(p)))))

写在后面

时间过的真快，上上届的我还是只会签到的参赛选手，上届的我只是一个组织者（背锅人），今年就以出题人的身份和大家见面了。这次题目质量不知道师傅们是否满意，如果对某道密码题有什么想交流的欢迎来找我。

不知道明年会以什么身份和大家见面呢👻。