2023-N1CTF-junior-wp-crypto

很硬的题目，尝试复现一下。

ezezez

题目：

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

flag = flag + os.urandom(512 // 8 - len(flag) - 10)

m = bytes_to_long(flag)
magic = bytes_to_long(b'N1Junior_CheckIn')
e = 24

while True:
    p = getPrime(256)
    if (p-1) % e == 0:
        break
q = getPrime(256)
n=p*q

gx = [Zmod(n)(m)^e, Zmod(n)(magic), Zmod(n)(m+magic)^e]

a = getPrime(128)
b = getPrime(128)
Ep = EllipticCurve(GF(p),[a,b])
Eq = EllipticCurve(GF(q),[a,b])

gy = []
for x in gx:
    Gp = Ep.lift_x(x)
    Gq = Eq.lift_x(x)
    y = crt([int(Gp[1]),int(Gq[1])],[p,q])
    gy.append(y)
        
print(f'a = {a}')
print(f'n = {n}')
print(f'gy = {gy}')


"""
a = 259416965926853287275013962386631097709
n = 8963244108103857378610478915798540027754205184635651624801332901515870452435977078824267979279218575027152343028911705254378598817260939339516835322386427
gy = [1896722249337161391193797083807118705857637064141055866260977430130447249097804719101078827699386498665026965515554644281163046869672493999194358926022865, 1971472878970365404484102034878792535366624572891039926216530789642810299559238977732710681752685090332485586910206690093655977703795335533365202958013518, 4074555112002157403114317690671003025383051142150876016519408756236925988856478235258960189636836867363451314784889114354880607055705753428890566240606935]
"""

题目流程如下：

• 生成素数p、q，取其乘积为n
• 生成素数a、b，并用a、b生成两条曲线如下：

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

• 在这两个曲线上分别取三个点，并crt得到在如下曲线上的三个点的坐标：

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

• 其中三个点的横坐标分别是：

$$m^e , magic,(m+magic)^e$$

• 给出a、n以及三个点在模n曲线下的纵坐标，要求求出m

首先要明白的一点是为什么一定要在模p、q下的曲线先求出纵坐标再crt起来，这是因为n是两个大素数组成的难以分解的合数，因此在模n下的二次剩余是难以求解的，所以才必须在模p、q下分别求出后再crt。

但是对于解出m来说很容易，因为椭圆曲线本质上来说就是关于x、y的多项式，并且所有y值都给了的情况下，就只剩下关于三个横坐标的方程。而虽然本题没有给b，但是由于magic为已知量，所以求出b不是问题。

但是实际上不求b也完全可行，因为两两作差就能消去b。我们将点一、二作差，点二、三作差，就得到如下两个方程：

$$(m^e)^3 + a(m^e) - (magic)^3 - a(magic) - y_0 + y_1 = 0 \quad(mod\;n)$$ $$((m+magic)^e)^3 + a((m+magic)^e) - (magic)^3 - a(magic) - y_2 + y_1 = 0 \quad(mod\;n)$$

而这两个方程有公共根m，因此求gcd或者用groebner应该都行，我这里直接用groebner。

exp：

from Crypto.Util.number import *

a = 259416965926853287275013962386631097709
n = 8963244108103857378610478915798540027754205184635651624801332901515870452435977078824267979279218575027152343028911705254378598817260939339516835322386427
gy = [1896722249337161391193797083807118705857637064141055866260977430130447249097804719101078827699386498665026965515554644281163046869672493999194358926022865, 1971472878970365404484102034878792535366624572891039926216530789642810299559238977732710681752685090332485586910206690093655977703795335533365202958013518, 4074555112002157403114317690671003025383051142150876016519408756236925988856478235258960189636836867363451314784889114354880607055705753428890566240606935]
e = 24
t = bytes_to_long(b'N1Junior_CheckIn')

PR.<m,magic> = PolynomialRing(Zmod(n))
f1 = (m^e)^3 + a*(m^e) - magic^3 - a*magic - gy[0]^2 + gy[1]^2
f2 = ((m+magic)^e)^3 + a*(m+magic)^e - magic^3 - a*magic - gy[2]^2 + gy[1]^2
f3 = magic - t
res = Ideal([f1,f2,f3]).groebner_basis()
print(res)

flag = n - 8963244108103857378610473916499685337958102994866002007958751917348709988813159260063838668865808163331396353132849773965877550546775678652844675901977223
print(long_to_bytes(flag))

#secpunk{baby_crypt000_checkin}

fastmix

题目：

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

assert len(flag) == 48
gift = b'yX~\xe1\xd3\xe7\xcdw_)/G\xdc\x0er\x18\xc0\xb2\xc1sKv\xd4\x857\x94D\xf91\xc2\x98\x873\x8bG\xc3hG\xbbC\x98\x16e\xe8\x11C\n\x04'
block_size = 16
date = bytes_to_long(b'2023-1-31 10:00')
f1 = lambda x: (x << 1) ^ 0b110100011 if x & 0x80 else x << 1
f2 = lambda x: x ^ f1(f1(x))
f3 = lambda x: f1(f1(f1(x))) ^ f1(f1(x))


def slow_func(init, time):
    tmp = init
    for _ in range(time):
        tmp = sum([[
            f3(tmp[j]) ^ f2(tmp[j+1]) ^ f2(tmp[j+2]) ^ f1(tmp[j+3]),
            f1(tmp[j]) ^ f3(tmp[j+1]) ^ f1(tmp[j+2]) ^ f2(tmp[j+3]),
            f3(tmp[j]) ^ f2(tmp[j+1]) ^ f3(tmp[j+2]) ^ f2(tmp[j+3]),
            f2(tmp[j]) ^ f1(tmp[j+1]) ^ f2(tmp[j+2]) ^ f3(tmp[j+3])
        ] for j in range(0, 16, 4)], [])
    return bytes(tmp)


v = b''
for i in range(0, len(flag), block_size):
    block = gift[i:i+block_size]
    v += slow_func(block, date)

assert flag == v

speedup类型的题目，只要跑完这个程序就能拿到flag。但是由于有：

for _ in range(time):

这个语句，而time是：

date = bytes_to_long(b'2023-1-31 10:00')

所以直接跑是没办法的，需要加速。而加速主要需要关注的就是如下部分：

f1 = lambda x: (x << 1) ^ 0b110100011 if x & 0x80 else x << 1
f2 = lambda x: x ^ f1(f1(x))
f3 = lambda x: f1(f1(f1(x))) ^ f1(f1(x))


def slow_func(init, time):
    tmp = init
    for _ in range(time):
        tmp = sum([[
            f3(tmp[j]) ^ f2(tmp[j+1]) ^ f2(tmp[j+2]) ^ f1(tmp[j+3]),
            f1(tmp[j]) ^ f3(tmp[j+1]) ^ f1(tmp[j+2]) ^ f2(tmp[j+3]),
            f3(tmp[j]) ^ f2(tmp[j+1]) ^ f3(tmp[j+2]) ^ f2(tmp[j+3]),
            f2(tmp[j]) ^ f1(tmp[j+1]) ^ f2(tmp[j+2]) ^ f3(tmp[j+3])
        ] for j in range(0, 16, 4)], [])
    return bytes(tmp)

先看这三个lambda函数，其实对AES比较熟悉的话，会看出来这个与列混合那一步的有限域乘法很相似。而这题也就是换了个模多项式。具体来说，如果把x的8bit看作是模2下的多项式系数，那么x本身就可以看作是一个多项式，记为g(x)。那么f1、f2、f3就分别等价于：

$$xg(x)$$ $$(x^2 + 1)g(x)$$ $$(x^3+x^2)g(x)$$

f1是乘x很好想通，因为在这个GF(2^8)的域中，2就代表的是x。而f2、f3其实也就分别代表5和12对应的元素，也就是x^2 + 1和x^3+x^2。同时，所有运算都在下面的商环下进行：

$$F_2[x]/(x^8+x^7+x^5+x+1)$$

那么之后的事也很简单，因为异或就是这个有限域中的加法，所以slow_func中的主要运算就可以看作是元素为多项式的矩阵乘法，比如对于第一次运算，就是如下过程：

$$\left(\begin{matrix} t_0\\ t_1\\ t_2\\ t_3\\ \end{matrix} \right) = \left(\begin{matrix} x^3+x^2&x^2 + 1&x^2 + 1&x\\ x&x^3+x^2&x&x^2 + 1\\ x^3+x^2&x^2 + 1&x^3+x^2&x^2 + 1\\ x^2 + 1&x&x^2 + 1&x^3+x^2\\ \end{matrix} \right) \left(\begin{matrix} s_0\\ s_1\\ s_2\\ s_3\\ \end{matrix} \right) \quad$$

其中si就是初始状态构成的向量，那么最终flag的运算结果就是：

$$\left(\begin{matrix} v_0\\ v_1\\ v_2\\ v_3\\ \end{matrix} \right) = \left(\begin{matrix} x^3+x^2&x^2 + 1&x^2 + 1&x\\ x&x^3+x^2&x&x^2 + 1\\ x^3+x^2&x^2 + 1&x^3+x^2&x^2 + 1\\ x^2 + 1&x&x^2 + 1&x^3+x^2\\ \end{matrix} \right)^{time} \left(\begin{matrix} s_0\\ s_1\\ s_2\\ s_3\\ \end{matrix} \right) \quad$$

而由于可以进行矩阵快速幂，所以就可以加速得到结果了。

exp：

from Crypto.Util.number import *

gift = b'yX~\xe1\xd3\xe7\xcdw_)/G\xdc\x0er\x18\xc0\xb2\xc1sKv\xd4\x857\x94D\xf91\xc2\x98\x873\x8bG\xc3hG\xbbC\x98\x16e\xe8\x11C\n\x04'
block_size = 16
date = bytes_to_long(b'2023-1-31 10:00')

PR2.<a> = PolynomialRing(Zmod(2))
R2 = PR2.quotient(1+a+a^5+a^7+a^8,'x')

x_1 = R2([0,1]) #f1:*x
x_2 = R2([1,0,1]) #f2:*(x^2+1)
x_3 = R2([0,0,1,1]) #f3:*(x^3+x^2)

poly_matrix = Matrix(R2,[[x_3,x_2,x_2,x_1],
                         [x_1,x_3,x_1,x_2],
                         [x_3,x_2,x_3,x_2],
                         [x_2,x_1,x_2,x_3]])

def convert_to_vec(num):
    temp = list(map(int,bin(num)[2:].zfill(8)[::-1]))
    return R2(temp)

def fast_func(init,time):
    for i in range(0, 16, 4):
        tmp = vector(R2,list(map(convert_to_vec,[init[i],init[i+1],init[i+2],init[i+3]])))
        final = (poly_matrix^(time))*tmp
        for j in final:
            temp = list(map(str,list(j)[::-1]))
            print(chr(int("".join(temp),2)),end = "")

for i in range(0, len(gift), block_size):
    block = gift[i:i+block_size]
    fast_func(block, date)

#secpunk{checkin_but_@maz1ng_4lg3bra1c_5tructure}  

n1lucky

这个题目Van1sh在公众号上写过好题分享，写的非常详细清楚，看那一篇就好了。

RealSignin

题目：

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

m = bytes_to_long(flag)

def get_params(nbits):
    p = getPrime(nbits)
    q = getPrime(nbits // 2)
    r = getPrime(nbits // 2)
    if q < r:
        q, r = r, q
    e = 2023 + 666
    n = p * q * r
    phi = (p-1) * (q-1) * (r-1)
    d = inverse(e, phi)
    return e, n, d, p, q, r

def magic_process(dqr_):
    # only the correct data can pass this magic process!
    w = 11805048190103811318745740902058585490581588391715507077469771342521346595744141604699124341571677599846725074544467374849004088341619160922679491419964725
    x = dqr_ + 666
    y = dqr_ + 667
    PR.<z> = PolynomialRing(ZZ)
    f = w*(x*z+y*z-x*y) - 4*x*y*z
    z = f.roots()[0][0]

    assert w*(x*z+y*z-x*y) - 4*x*y*z == 0

e, n, d, p, q, r = get_params(512)

dqr = d % ((q-1) * (r-1))
dqr_ = (dqr >> 55) << 55
magic_process(dqr_)

print(f'e = {e}')
print(f'qr = {q % r}')
print(f'n = {n}')
print(f'c = {pow(m, e, n)}')

'''
e = 2689
qr = 47039394845246457267451844933135300719863788804596821520575305333413876649846
n = 102275105641047314957681561255971730180031931453885390971560104545784846810054168298038033889926837832908913447331571300831232278972182034546312860462560455575699889259884894407503661740178853200384106267596198200388045685183747251883536380886761864997738495990864526497955511125021398766971363828732464588761
c = 30057873321817268990724095993213394773233077509126537130493293224220768053789109305889627009912877888765075963369699610910695123551381348483962929764830148523075698671087735427795008522625385598116705013490990766089416767372146754468746664865469005120853463146265400060202176870467493380590559736303051981581
'''

题目先生成RSA的几个密钥相关量，n由三个素数p、q、r组成，其中p是512bit的素数，q、r分别为256bit且q>r，e为2689。

然后题目先计算出一个量：

$$dqr = d \quad(mod\;(q-1)(r-1))$$

然后抹去他的低55位，得到dqr’，然后用这个值构造x、y如下：

$$x = dqr' + 666$$ $$y = dqr' + 667$$

然后给出一个方程：

$$w(xz+yz-xy) - 4xyz = 0$$

并且仅给出w的值。此外，题目还给了我们q%r的值qr，以及公钥n和flag密文c，要求还原明文。

理一下解题思路，首先肯定要知道dqr’的值，才有后续利用copper解出dqr、进而求出n的完整分解的机会。所以当务之急就是解决下面这个不定方程：

$$w(xz+yz-xy) - 4xyz = 0$$

并且还知道一个信息是：

$$y = x+1$$

然后我这里的第一个思路是，注意到magic中有一句注释是：

# only the correct data can pass this magic process!

所以我在想，这是不是说方程有且仅有一个解的意思，也就是说dqr’的唯一整数解刚好就在对称轴上。于是我把这个不定方程的y消去，变成如下的形式：

$$(4z+w)x^2 + (4z+w-2zw)x - wz = 0$$

把x视作主元，得到的就是一个关于x的一元二次方程，而如果符合我们猜想的话，这个二次方程的判别式就该等于0，也就是：

$$(4z+w-2zw)^2 + 4wz(4z+w) = 0$$

但是这个方程没有整数解，所以并不是我们猜想的那样，因此需要另谋他法。我的第二个思路是把方程化成下面这个形式：

$$\frac{4}{w} = \frac{2x+1}{x(x+1)}- \frac{1}{z}$$

z应该是个很大的数，所以是不是代表着4/w的连分数展开可能会覆盖到x组成的这个分数？但是遗憾的是也没有成功，应该是不满足勒让德理论。

之后我问了zima师傅，知道有原题目可以参考：

Cyber Apocalypse CTF 2021 Part 1 | CryptoHack Blog

大致思路就是说，首先把原不定方程化成如下形式(其实就是第二种思路中，不代入y=x+1)：

$$\frac{4}{w} = \frac{1}{x} + \frac{1}{y} - \frac{1}{z}$$

接下来的步骤就有点想象力了，因为w是奇数，所以左边可以拆成：

$$\frac{4}{w} = \frac{2}{w-1} + \frac{2}{w+1} - \frac{4}{w(w-1)(w+1)}$$

所以就得到了符合要求的解。

然后这里我也有问yolbby师傅，他说他是类比成埃及分数做，我之前并不知道这个东西就去查了一下。埃及分数其实也就是分子为1的分数，那么之所以能类比，应该也是上面那个化简形式的存在：

$$\frac{4}{w} = \frac{1}{x} + \frac{1}{y} - \frac{1}{z}$$

然后对应的办法就是深搜迭代，但是由于数字很大，所以我自己瞎搜索了一下，没有实现出来这种办法。有兴趣的师傅可以自己试一试。

解出这个不定方程的之后就有dqr’，而为了得到完整的dqr，很显然需要copper解出其低55位。为此我们记这低55位为delta，构造下面这个方程：

$$e(dqr' + \delta) = 1 \quad(mod\;(q-1)(r-1))$$

展开成等式就有：

$$e(dqr' + \delta) = 1 + k(q-1)(r-1)$$

这里就和dq泄漏的思路类似(其实本质上来说没区别)，注意到k肯定小于e，而e又仅有2689，因此遍历1到e一定存在一个正确的k。而我们又有q模r的值，并且知道q和r都是256bit，所以一定有：

$$q = r + qr$$

那么代入上面那个式子：

$$e(dqr' + \delta) = 1 +k(r + qr-1)(r-1)$$

展开：

$$e(dqr' + \delta) = 1 +k(r^2+r(qr-2)+1-qr)$$

那么在模r下就有：

$$e(dqr' + \delta) = 1 +k(1-qr) \quad(mod\;r)$$

然后理论上来说就可以在模n下用copper求解出delta的值了。不过有一些小问题：

• r是256bit的因子并且比q小，因此beta最多就取到0.25
• beta取0.25的话，epsilon即使取到0.01，根的上界也就只有50出头，达不到要求，可能还要爆破几位

但是首先epsilon取0.01就很慢了，再爆破几位更慢，而且最外层还要爆破k，更更慢。最主要的是，我电脑还没换，这破电脑没有装flatter啊！

然后想到了一点点优化，就是刚才这个式子里：

$$e(dqr' + \delta) = 1 + k(q-1)(r-1)$$

应该是转化到模q下求解小根的话，由于有q>r，所以beta能稍微大一点，也许根的上界可以略有提升？因此我构造出如下的多项式：

$$e(dqr' + \delta) = 1 +k(1+qr) \quad(mod\;q)$$

然后还有一点就是，由于d肯定是奇数，模一个偶数也不改变奇偶性，所以LSB肯定是1，所以还能减小1bit。不过除此之外确实没想到其他优化了，就硬来吧。要是有flatter就好了，换了电脑一定马上装。

爆了差不多一个半小时出了结果(也算是运气不错，完整的爆估计要8个小时，装flatter还是很必要)。有了完整的dqr过后就可以用刚才的方程求根得到q、r，就有了n的完整分解，然后解密就好了。

exp：

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

e = 2689
qr = 47039394845246457267451844933135300719863788804596821520575305333413876649846
n = 102275105641047314957681561255971730180031931453885390971560104545784846810054168298038033889926837832908913447331571300831232278972182034546312860462560455575699889259884894407503661740178853200384106267596198200388045685183747251883536380886761864997738495990864526497955511125021398766971363828732464588761
c = 30057873321817268990724095993213394773233077509126537130493293224220768053789109305889627009912877888765075963369699610910695123551381348483962929764830148523075698671087735427795008522625385598116705013490990766089416767372146754468746664865469005120853463146265400060202176870467493380590559736303051981581

#part1 get dqr_
w = 11805048190103811318745740902058585490581588391715507077469771342521346595744141604699124341571677599846725074544467374849004088341619160922679491419964725
k = (w-1)//2
x = k
y = k+1
z = k*(k+1)*(2*k+1)
assert w*(x*z+y*z-x*y) - 4*x*y*z == 0
dqr_ = x-666


#part2 get dqr(use copper)
if(0):
    for tt in range(4):
        for k in trange(1,e):
            PR.<delta> = PolynomialRing(Zmod(n))
            f = e*(dqr_+2^3*delta+2*tt+1) - 1 - k*(1+qr)
            f = f.monic()
            res = f.small_roots(X=2^52,beta=0.25,epsilon=0.01)
            if(res != []):
                print(tt,k,res)  #0 2046 [2593202029823482]
                break
dqr = dqr_ + 2^3*2593202029823482 + 2*0 + 1
k = 2046


#part3 factor n
if(0):
    PR.<r> = PolynomialRing(ZZ)
    f = e*dqr - 1 - k*(r+qr-1)*(r-1)
    res = f.roots()
    print(res)
r = 67643325987256775010724943844390543569531594444330008512848332012702093716653
q = r + qr
p = n // q // r


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

#secpunk{reallyreallyreallyreally_ez_signin..}

errorcc

题目：

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

assert flag[:8]==b'secpunk{' and flag[-1:]==b'}'
flag = flag[8:-1]
m = bytes_to_long(flag)

p = getPrime(200)
a = random.randint(0, p-1)

while True:
    b = random.randint(0, p-1)
    E = EllipticCurve(Zmod(p), [a, b])
    if isPrime(E.order()):
        break
        
Ga = E.gens()[0]
gift = bytes_to_long(b'N1CTF Junior')
random.seed(gift)

G = []
for i in range(80):
    r = random.randint(0,p-1)
    G.append(tuple((r ^^ m)*Ga)[:-1])
    
for i in range(60):
    r = random.randint(0,p-1)
    G.append(tuple((r & m)*Ga)[:-1])
    
for i in range(60):
    r = random.randint(0,p-1)
    G.append(tuple((r | m)*Ga)[:-1])
    
f = open('output.txt','w')
f.write("Ga = "+str(tuple(Ga)[:-1])+"\n")
f.write("G = "+str(G))

output有点长，就不放在这里，需要的师傅可以找我要。

题目流程也很清晰：

• 首先把flag的头尾去了，然后转成大整数m
• 生成随机的200bit素数p，以及小于p的随机数a
• 然后爆破出一个b，使其生成的如下曲线的阶是素数：

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

• 然后取曲线上的生成元Ga，并以一个已知的gift作为随机数的种子，之后分别给出：

80个：

$$G_i = (m\oplus r_i)G_a$$

60个：

$$G_i = (m \;and\; r_i)G_a$$

60个：

$$G_i = (m \;|\; r_i)G_a$$

以及Ga，要求还原m。

首先肯定是要还原出曲线参数，这一部分很容易，因为所有给出的点都是曲线上的点，所以不论是手写一个消元或者是直接取groebner都能获得全部参数。然后需要注意的一点是，由于随机数种子给了我们，所以所有ri都已知。

有了参数a、b、p后就能计算其order。看到题目里保证其阶为素数，确实幻想过阶恰好为p然后直接smart attack，或者阶满足mov attack之类，但是的确都不行。也就是说这个ECC上的DLP是没办法求的，只能想办法利用给出的这些点来恢复m。

这里我首先就想到N1CTF的e2D1p一题，因为实在是非常类似：

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

类似在哪里呢？在那个题目中，有多组如下形式的等式：

$$c_i = e^{flag \oplus m_i} \quad(mod\;p)$$

并且给出每个等式的ci、ri。我们忽略掉那个题目恢复p的步骤，直接进入其恢复flag的第二步，也就是把p当作已知，那么对应于这个题目中的给了多组如下的点来说：

$$G_i = (m\oplus r_i)G_a$$

ci对应Gi，e对应Ga，mi对应ri，flag对应m，p对应order，完全可以一一对应。也就是说，似乎除了把离散对数形式从数构成的乘法群移到点构成的加法群，别的都没什么区别。

所以我就想到用一模一样的思路逐bit还原m，具体的就看那篇文章就好了。不过我就这么做没有做出来，因为所有那个形式的矩阵方程都无解。思考了一下，确实不应该直接这样就能出，毕竟后面的&和|给的足足120个点都还没有用到。

这题之后更新吧，暂时没什么思路了。

(2.1更新)

从zima师傅那里要到了一份这个题目的exp，然后看着代码理解了一下出题人的思路，豁然开朗。

先放他的exp：

import random
import time
from functools import reduce

f = open("output.txt",'r')
f.read(5)
Ga = eval(f.readline())
f.read(4)
G = eval(f.readline())

PR.<a,b> = PolynomialRing(ZZ)
polys = []

for i in range(4):
    x, y = G[i]
    polys.append(x*a+b+(x^3-y^2))

gb = Ideal(polys).groebner_basis()
p = gb[-1]
a = -gb[0].coefficients()[-1]%p
b = -gb[1].coefficients()[-1]%p

E=EllipticCurve(Zmod(p),[a, b])
Ga=E(Ga)

def xormat(r, P):
    mask = 1
    v = []
    for i in range(200):
        if r & mask == 0:
            v.append(1)
        else:
            v.append(-1)
            P = P-mask*Ga
        mask = mask << 1
    return v, P

def andmat(r, P):
    mask = 1
    v = []
    for i in range(200):
        if r & mask == 0:
            v.append(0)
        else:
            v.append(1)
        mask = mask << 1
    return v, P

def ormat(r, P):
    mask = 1
    v = []
    for i in range(200):
        if r & mask == 0:
            v.append(1)
        else:
            v.append(0)
            P = P-mask*Ga
        mask = mask << 1
    return v, P
    
L = []
R = []
random.seed(int.from_bytes(b'N1CTF Junior', 'big'))

print("===construct matrix begin===")
start = time.time()
for i in range(80):
    rn = random.randint(0,p-1)
    Q = E(G[i])
    v, P = xormat(rn, Q)
    L.append(v)
    R.append(P)
    
for i in range(80,140):
    rn = random.randint(0,p-1)
    Q = E(G[i])
    v, P = andmat(rn, Q)
    L.append(v)
    R.append(P)
    
for i in range(140,200):
    rn = random.randint(0,p-1)
    Q = E(G[i])
    v, P = ormat(rn, Q)
    L.append(v)
    R.append(P)
print("===construct matrix end===")
end = time.time()
print("cost {}s".format(end-start))

q = E.order()
L = Matrix(Zmod(q), L)
m = ''
O = 0*Ga
for i in range(200):
    u = vector(Zmod(q),[0]*i+[1]+[0]*(199-i))
    coeff = L.solve_left(u).change_ring(ZZ)
    S = 0*Ga
    for i in range(200):
        S += coeff[i]*R[i]
    if S == O:
        m = '0'+m
    else:
        m = '1'+m

print(bytes.fromhex(hex(int(m, 2))[2:]))

接下来就是讲这样做的道理是什么。

xor

首先，由于给出的都是位运算，因此所有式子都可以写成对于各bit的操作形式，我们就以xor举例，对于其中的某个式子，他本来是写成：

$$G = (m\oplus r)G_a$$

我们把m看作是200个未知bit组成的量(也就是按位，把它看作是200个变量)，那么这个式子可以写成：

$$G = (\sum_{j=0}^{199}{2^j(m_j \oplus r_{j})})G_a$$

这对于后面的&和|也是同理的，但是又为什么要这样写呢？我们用如下写法，让表达式更清晰一点：

$$G = 2^0(m_0 \oplus r_{0})G_a + 2^1(m_1 \oplus r_{1})G_a + ... + 2^{199}(m_{199} \oplus r_{199})G_a$$

这样写出来之后，式子由原来的一个普通点乘计算，变成了两百个独立的点乘计算，并在最后相加。注意这里刻意强调的每个点乘计算的独立性，因为每个bit之间是完全不会相互影响的。

而对于我们来说，我们有r的200个bit的值，这就又给这个式子增加了一些额外信息。由于r的每个bit只有0、1两个取值，所以我们分开讨论：

• r的当前bit(rj)为0，那么：

$$m_j \oplus r_{j} = m_j \oplus 0 = m_j$$

• r的当前bit(rj)为1，那么：

$$m_j \oplus r_{j} = m_j \oplus 1$$

明白了这两点后，仍然是注意到200个bit彼此独立，我们就随便取其中一bit来分析一下

$$2^j(m_j \oplus r_{j})G_a$$

我们需要关注的是，m的这一bit的取值，对于最终得到G的贡献是什么。如果rj为0，那么由刚才的式子知道，这个点乘就是：

$$2^j(m_j)G_a$$

而重点在于rj=1的时候，这个点会变成：

$$2^j(m_j \oplus 1)G_a$$

这个怎么处理呢？其实因为mj也只有两个取值，所以也可以先分别写出mj的两种情况对应的点乘：

• mj为0，则为：

$$2^j(0 \oplus 1)G_a = 2^j(0)G_a + 2^jG_a$$

• mj为1，则为：

$$2^j(1 \oplus 1)G_a = 2^j(-1)G_a + 2^jG_a$$

重要的一步来了，我们只需要配凑一个-1，就能把式子变成一个统一的含mj变量的形式：

$$2^j(m_j \oplus 1)G_a = -2^jm_jG_a + 2^jG_a$$

如此一来，把rj为0和1分别对应的mj形成的表达式分别代入最初那个式子中，就可以将m的200bit写在一个更清晰的表达式里了：

$$G = 2^0(m_0 \oplus r_{0})G_a + 2^1(m_1 \oplus r_{1})G_a + ... + 2^{199}(m_{199} \oplus r_{199})G_a$$

这里举个简单的例子帮助理解，比如r的bit序列为(由低到高)：

$$(0,1,...,0,1)$$

结合刚才的表达式代入这个式子里，就得到：

$$G = 2^0m_0G_a -2^1m_1G_a + 2^1G_a + ... + 2^{198}m_{198}G_a -2^{199}m_{199}G_a + 2^{199}G_a$$

移项就得到：

$$G - 2^1G_a - ... -2^{199}G_a = 2^0m_0G_a -2^1m_1G_a+ ... + 2^{198}m_{198}G_a-2^{199}m_{199}G_a$$

此时，等式左边是一个已知的点，等式右边是仅有m的200bit组成的算式。这其实就是一个涉及m的200个bit的方程了。那么由xor，我们可以得到80组这样的方程。

and ,or

其实xor想明白了，这两个异曲同工。因为我们要做的事情，仍然是根据r的200个bit的值，列出仅含m的200个bit的方程。那么对于&来说：

$$G = 2^0(m_0 \;and\; r_{0})G_a + 2^1(m_1 \;and\; r_{1})G_a + ... + 2^{199}(m_{199} \;and\;r_{199})G_a$$

这个就很简单，因为讨论rj的两种取值的话，显然rj为0整个式子乘数就取0，rj为1整个式子乘数就取mj，仍然是用刚才的(0,1,…,0,1)的r的bit序列举个例子，G就等于：

$$G = 0 + 2^1m_1G_a + ... + 0 + 2^{199}m_{199}G_a$$

对于|来说，分别讨论rj的两种取值，rj为1时，整个式子乘数取1，为0时取mj，因此对于作为例子的(0,1,…,0,1)的r的bit序列，G为：

$$G = 2^0m_0G_a + 2^1G_a + ... + 2^{198}m_{198}G_a + 2^{199}G_a$$

移一下项就变成需要的方程形式：

$$G-2^1G_a- 2^{199}G_a = 2^0m_0G_a + ... + 2^{198}m_{198}G_a$$

如此一来，and和or又各提供60个方程，我们就拥有了关于m的200个bit变量的200个方程。

利用上述方程

接下来的问题就变成，已知关于m的200个bit的200个方程，如何求解m。很自然地会想到先用矩阵方程把这个式子表示出来，就像下面这样：

$$L_{200\times 200} \left(\begin{matrix} m_0\\ m_1\\ ...\\ m_{199}\\ \end{matrix} \right) G_a = P_{200\times 1}$$

其中，L矩阵中的每一行，就是我们刚才每一个方程中Ga前的系数构成的向量，因为有200个方程所以是200x200的矩阵；而P向量中的每个元素就是列出的方程左边的点。

注意到，虽然矩阵L、点Ga以及向量P都是已知的，但是可以看出，这并不是一个普通的矩阵方程，因为它涉及到椭圆曲线的点乘，并且曲线难以求解dlp，所以不好统一转化到生成元上，从而变成纯数域的计算。所以是没有办法直接解矩阵方程得到解向量m的。

不过bit by bit的思路依然可以用，我们第一次求解如下矩阵方程：

$$(x_0,x_1,...,x_{199}) L = (1,0,...,0)$$

求出这个X向量的意义在于，我们把x代回刚才的式子里：

$$(x_0,x_1,...,x_{199}) L \left(\begin{matrix} m_0\\ m_1\\ ...\\ m_{199}\\ \end{matrix} \right) G_a = (x_0,x_1,...,x_{199}) P$$

那么也就是：

$$(1,0,...,0) \left(\begin{matrix} m_0\\ m_1\\ ...\\ m_{199}\\ \end{matrix} \right) G_a = (x_0,x_1,...,x_{199}) P$$

也就是：

$$m_0 G_a = (x_0,x_1,...,x_{199}) P$$

所以只需要等式右边的点是不是0*Ga就能判断m的当前bit是不是0.如此就可以逐bit还原m了。

exp：

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

#part1 groebner to get a,b,p
if(0):
    PR.<a,b> = PolynomialRing(ZZ)
    F = []
    for i in range(4):
        f = G[i][1]^2-G[i][0]^3-a*G[i][0]-b
        F.append(f)
    res = Ideal(F).groebner_basis()
    print(res)
p = 1287829304049714244524067710692915105281415000125398093331471
a = p-225347669189365890161624438870935953357140181565885210886229
b = p-270712467434746420425713635322490969521436540014940033725570
E = EllipticCurve(Zmod(p),[a,b])
ord = E.order()
Ga = E(Ga)
for i in range(len(G)):
    G[i] = E(G[i])


#part2 construct L
gift = bytes_to_long(b'N1CTF Junior')
random.seed(gift)
L = Matrix(Zmod(ord),200,200)
P = []

## 2.1 xor
for i in trange(80):
    ri = random.randint(0,p-1)
    temp = bin(ri)[2:].zfill(200)[::-1]
    tempG = G[i]
    for j in range(len(temp)):
        if(temp[j] == "0"):
            L[i,j] = 1
        else:
            L[i,j] = -1
            tempG -= 2^j*Ga
    P.append(tempG)

## 2.2 and
for i in trange(80,140):
    ri = random.randint(0,p-1)
    temp = bin(ri)[2:].zfill(200)[::-1]
    tempG = G[i]
    for j in range(len(temp)):
        if(temp[j] == "0"):
            L[i,j] = 0
        else:
            L[i,j] = 1
    P.append(tempG)

## 2.3 or
for i in trange(140,200):
    ri = random.randint(0,p-1)
    temp = bin(ri)[2:].zfill(200)[::-1]
    tempG = G[i]
    for j in range(len(temp)):
        if(temp[j] == "0"):
            L[i,j] = 1
        else:
            L[i,j] = 0
            tempG -= 2^j*Ga
    P.append(tempG)


#part3 bit by bit to recover flag
flag = ""
O = 0*Ga
for i in trange(200):
    u = vector(Zmod(ord),[0]*i + [1] + [0]*(199-i))
    temp = L.solve_left(u)
    S = O
    for j in range(len(temp)):
        S += int(temp[j])*P[j]
    if(S == O):
        flag += "0"
    else:
        flag += "1"
print(long_to_bytes(int(flag[::-1],2)))

#secpunk{f4ult_1nj3cti0n~p0werfu1!}

很巧妙的思路，类似的就可以把这个解法也拓展到N1CTF的e2dlp上，虽然都是bit by bit求但是还是有细微差别。