writeup for 2021 3月dsactf

Posted on Edited on In Word count in article: 11k Reading time ≈ 10 mins.

orz 还是太菜了，这个比赛密码都被A穿了，我还是做不出NTRU，师傅们都说简单，多项式杀我
还是详细记录一下吧，加油

0x00 crypto_threshold

是签到没错了。。。

problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import random
from sympy import nextprime
from Crypto.Util.number import *
from secret import flag
from gmpy2 import gcd

def lcg(seed,params):
    (m,c,n)=params
    s = seed % n
    while True:
        s = (m * s + c) % n
        yield s
    

seed = getPrime(128)
m = getPrime(128)
c = getPrime(128)
n = getPrime(129)

print(m,c,n)
key_stream = lcg(seed,(m,c,n))
num=[]
for _ in range(6):
	num.append(next(key_stream))
	
print(num)
secret =  next(key_stream)

e = nextprime(secret)
p = getPrime(1024)
q = getPrime(1024)


_lambda = ((p-1)*(q-1)) / gcd(p-1,q-1)

flag = bytes_to_long(flag)


print(_lambda)
print(p*q)
print(pow(flag,e,p*q))
        
'''
# data
'''

analyses

条件全给的LCG，直接往下推就好了。
RSA, 直接求逆就是私钥了

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from sympy import nextprime
from Crypto.Util.number import *
from gmpy2 import invert

def lcg(seed, params):
    (m, c, n) = params
    s = seed % n
    return (m * s + c) % n

m, c, n = (315926151576125492949520250047736865439, 204423972944032372640132172728460755543,
           375402477603617093440157245062608289367)
seed = 287868671713011127830359814204794790287
e = nextprime(lcg(seed, (m, c, n)))
_lambda = 
d = invert(e, lam)
n = 
c = 
print(long_to_bytes(pow(c, d, n)))

0x01 FeedBack

流密码的路子，再熟悉不过了

problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from secret import flag
from string import hexdigits
import random
from functools import reduce

def cycle(c:list,a:list)->int:
    return reduce(lambda x,y: x+y,map(lambda x: x[0]*x[1],zip(c,a))) 

def enc(m:list,k:list)->list:
    for i in range(len(k)*2):
        m.append(cycle(m[i:i+len(k)],k))
    return m[len(k):]

if __name__ == "__main__":
    key=[ord(random.choice(hexdigits)) for i in range(len(flag))]
    c=enc(list(flag),key)
    print(c)

# data

analyses

简单说一下整个过程吧，key和flag的长度都是27这个仔细点看应该就可以看出来了.
记
这里的加密其实就是计算然后放在最后面

再来看看条件，题目给了一共54个。写成矩阵就知道这54个能干什么大事情了

所以这54个m已经可以解出全部的了

解出27个以后，就是题目所说的feedback了， 我们知道，前27个计算下一个，而, 可以看到这个式子里， 我们只有不知道，直接解方程或者爆破都可以解出来。解出就可以按着这个思路一路往回解，直到解出全部。

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# sagemath
def cycle(c,a):
    return reduce(lambda x,y: x+y,map(lambda x: x[0]*x[1],zip(c,a))) 

c = [...]
A = []
for i in range(27):
    v = c[i:i+27]
    A.append(v)
s = vector(c[27:])
A = Matrix(A)
a = A.solve_left(s)


c = c[:27]
m = []
for _ in range(27):
    for i in range(0xff):
        res = cycle([i] + c[:-1],a)
        if res == c[-1]:
            c = [i] + c[:-1]
            m.append(chr(i))
            break
''.join(m[::-1])

0x02 son_of_NTRU

做过一样的题了，那道题还是我格的启蒙，怎么会忘呢
https://xz.aliyun.com/t/7163 - 从一道CTF题初探NTRU格密码

problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#! /bin/bash/env python3
from random import randrange
from Crypto.Util.number import *
from gmpy2 import invert
def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def generate():
    p = getPrime(1024)
    while True:
        f = randrange(1,(p//2)**(0.5))
        g = randrange((p//4)**(0.5),(p//2)**(0.5))
        if gcd(f,p)==1 and gcd(f,g)==1:
            break
    h = (invert(f,p)*g)%p
    return h,p,f,g

def encrypt(m,h,p):
    assert m<(p//4)**(0.5)
    r = randrange(1,(p//2)**(0.5))
    c = (r*h+m)%p
    return c

h,p,f,g = generate()

from flag import flag
c = encrypt(bytes_to_long(flag),h,p)
print("h = {}".format(h))
print("p = {}".format(p))
print("c = {}".format(c))
# h = 70851272226599856513658616506718804769182611213413854493145253337330709939355936692154199813179587933065165812259913249917314725765898812249062834111179900151466610356207921771928832591335738750053453046857602342378475278876652263044722419918958361163645152112020971804267503129035439011008349349624213734004
# p = 125796773654949906956757901514929172896506715196511121353157781851652093811702246079116208920427110231653664239838444378725001877052652056537732732266407477191221775698956008368755461680533430353707546171814962217736494341129233572423073286387554056407408816555382448824610216634458550949715062229816683685469
# c = 4691517945653877981376957637565364382959972087952249273292897076221178958350355396910942555879426136128610896883898318646711419768716904972164508407035668258209226498292327845169861395205212789741065517685193351416871631112431257858097798333893494180621728198734264288028849543413123321402664789239712408700

analyses

不多说了，前面说的那个blog说的超级清楚。这道题在生成参数的时候给了一大堆条件就是为了在格基规约的时候能够把和规约出来。还有！那个同余式要参数够小才能模约去随机数。

exp

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import long_to_bytes as l2b
h = 70851272226599856513658616506718804769182611213413854493145253337330709939355936692154199813179587933065165812259913249917314725765898812249062834111179900151466610356207921771928832591335738750053453046857602342378475278876652263044722419918958361163645152112020971804267503129035439011008349349624213734004
p = 125796773654949906956757901514929172896506715196511121353157781851652093811702246079116208920427110231653664239838444378725001877052652056537732732266407477191221775698956008368755461680533430353707546171814962217736494341129233572423073286387554056407408816555382448824610216634458550949715062229816683685469
c = 4691517945653877981376957637565364382959972087952249273292897076221178958350355396910942555879426136128610896883898318646711419768716904972164508407035668258209226498292327845169861395205212789741065517685193351416871631112431257858097798333893494180621728198734264288028849543413123321402664789239712408700

v1 = vector([1,h])
v2 = vector([0,p])
f,g = Matrix([v1,v2]).LLL()[0]
f,g = abs(f),abs(g)
d = int(inverse_mod(f,g))
x = int((c * f) % p %g )
l2b((x * d)%g)

0x03 threshold

真正的NTRU，我太菜了不知道多项式要怎么处理，去dawn_wispher爷爷的Blog学习一下，学会了再来更新
3/29 俺回来了, 俺学会了, 不过这边只扔一波脚本, 具体原理可以去看我的另外一篇Translation of LatticeHacks

problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#make.sage
import random
flag = bytearray("DASCTF{********************************}".encode())
flag = list(flag)
length = len(flag)
N=53
p=257
q=28019
d=18
f=[1]*19+[-1]*18+[0]*16
random.shuffle(f)
g=[1]*18+[-1]*18+[0]*17
random.shuffle(g)

Q.<x> = Zmod(q)[]
P.<y> = Zmod(p)[]
fx=Q(f)
fy=P(f)
gx=Q(g)
Fqx=fx.inverse_mod(x^N-1)
Fpy=fy.inverse_mod(y^N-1)
hx=(Fqx*gx).mod(x^N-1)
r=[1]*10+[-1]*22+[0]*21
random.shuffle(r)
rx=Q(r)
mx=Q(flag)
ex=(p*rx*hx+mx).mod(x^N-1)
print(ex)
print(hx)

#7367*x^52 + 24215*x^51 + 5438*x^50 + 7552*x^49 + 22666*x^48 + 21907*x^47 + 10572*x^46 + 19756*x^45 + 4083*x^44 + 22080*x^43 + 1757*x^42 + 5708*x^41 + 22838*x^40 + 4022*x^39 + 9239*x^38 + 1949*x^37 + 27073*x^36 + 8192*x^35 + 955*x^34 + 4373*x^33 + 17877*x^32 + 25592*x^31 + 13535*x^30 + 185*x^29 + 9471*x^28 + 9793*x^27 + 22637*x^26 + 3293*x^25 + 27047*x^24 + 21985*x^23 + 13584*x^22 + 6809*x^21 + 24770*x^20 + 16964*x^19 + 8866*x^18 + 22102*x^17 + 18006*x^16 + 3198*x^15 + 19024*x^14 + 2777*x^13 + 9252*x^12 + 9684*x^11 + 3604*x^10 + 7840*x^9 + 17573*x^8 + 11382*x^7 + 12726*x^6 + 6811*x^5 + 10104*x^4 + 7485*x^3 + 858*x^2 + 15100*x + 15860
#14443*x^52 + 10616*x^51 + 11177*x^50 + 24769*x^49 + 23510*x^48 + 23059*x^47 + 21848*x^46 + 24145*x^45 + 12420*x^44 + 1976*x^43 + 16947*x^42 + 7373*x^41 + 16708*x^40 + 18435*x^39 + 18561*x^38 + 21557*x^37 + 16115*x^36 + 7873*x^35 + 20005*x^34 + 11543*x^33 + 9488*x^32 + 2865*x^31 + 11797*x^30 + 2961*x^29 + 14944*x^28 + 22631*x^27 + 24061*x^26 + 9792*x^25 + 6791*x^24 + 10423*x^23 + 3534*x^22 + 26233*x^21 + 14223*x^20 + 15555*x^19 + 3381*x^18 + 23641*x^17 + 2697*x^16 + 11303*x^15 + 6030*x^14 + 7355*x^13 + 20693*x^12 + 1768*x^11 + 10059*x^10 + 27822*x^9 + 8150*x^8 + 5458*x^7 + 21270*x^6 + 22651*x^5 + 8381*x^4 + 2819*x^3 + 3987*x^2 + 8610*x + 6022

analyses

NTRU, 参数够小就能通过格基规约求出私钥, 然后通过正常的解密流程进行解密了

这里有几个点需要注意一下:

  1. NTRU能够用来解密的私钥不止一个, 所以可能有多个私钥能够解密密文. 特别是规约之后的矩阵, 常常能规约出一大堆私钥来.

  2. 在构造格子的时候, 系数旋转的方向一定要正确, 在做这道题的时候我就因为旋转的方向反了做了一整天(我还一直以为自己解密写错了

  3. 造格子有很多方法, 这边记录一下两个

    第一个格子规约出来的上面行, 每行的前一半是私钥, 后一半是随机向量

    第二个格子规约出来的上面行, 每行的后一半是私钥, 前一半是随机向量

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
from random import *
Zx.<x> = ZZ[]

def balancedmod(f,N,q):
    g = list(((f[i] + q//2) %q) - q//2 for i in range(N))
    return Zx(g)

def convolution(f,g,N):
    return (f*g) % (x^N-1)

def randomdpoly(d,N):
    assert d <= N
    result = N*[0]
    for j in range(d):
        while True:
            r = randrange(N)
            if not result[r]: break
        result[r] = 1 - 2*randrange(2)
    return Zx(result)

def invertmodprime(f,N,p):
    T = Zx.change_ring(Integers(p)).quotient(x^N-1)
    return Zx(lift(1 / T(f)))

def invertmodpowerof2(f,N,q):
    assert q.is_power_of(2)
    g = invertmodprime(f,2,N)
    while True:
        r = balancedmod(convolution(g,f),q)
        if r == 1: 
            return g
        g = balancedmod(convolution(g,2 - r),q)
        
def randommessage(N,p):
    result = list(randrange(p) - 1 for j in range(N))
    return Zx(result)
        
def keypair(d,N,q,p):
    while True:
        try:
            f = randomdpoly(d,N)
            fp = invertmodprime(f,N,p)
            fq = invertmodpowerof2(f,N,q)
            break
        except:
            pass
    g = randomdpoly()
    publickey = balancedmod(p * convolution(fq,g,N),N,q)
    secretkey = f,fp
    return publickey,secretkey

def encrypt(message,publickey,N,q):
    r = randomdpoly(randint(N))
    return balancedmod(convolution(publickey,r) + message,N,q)

def decrypt(ciphertext,secretkey,N,q,p):
    f,fp = secretkey
    a = balancedmod(convolution(ciphertext,f,N),N,q)
    return balancedmod(convolution(a,fp,N),N,p)
    
def balancedmod(f,N,q):
    g = list(((f[i] + q//2) %q) - q//2 for i in range(N))
    return Zx(g)

def invertmodprime(f,N,p):
    T = Zx.change_ring(Integers(p)).quotient(x^N-1)
    return Zx(lift(1 / T(f)))

def convolution(f,g,N):
    return (f*g) % (x^N-1)

N = 53
q = 28019
p = 257
B = Matrix([[0 for _ in range(2*N)] for _ in range(2*N)])
ex = ...
hx = ...
H = hx.list()

sigma = 1
_lambda = 1

for i in range(N):
    for j in range(N):
        B[i+N,j] = int(H[j-i])
        if i == j:
            B[i,j] = sigma * q
            B[N+i,N+j] = _lambda * 1
            
L = B.LLL()[1]
fx = Zx(list(L[N:]))
fp = invertmodprime(fx,N,p)

for i in decrypt(ex,(fx,fp),N,q,p).list():
    print(chr(abs(i)),end='')

这个exp顺便把一些要用到的运算也放过来了, 以后做NTRU可以用这些运算来做