2022 SUSCTF

Van1sh 比赛小屋 Write Up
创建时间:
字数:3.7k 阅读:
  1. large case
  2. InverseProlem
  3. Ez_Pager_Tiper
  4. SpecialCurve3

large case

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
from secret import e,message

def pad(s):
    if len(s)<3*L:
        s+=bytes(3*L-len(s))
    return s

L=128
p=127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q=145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r=165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
n=p*q*r

assert isPrime(GCD(e,p-1)) and isPrime(GCD(e,q-1)) and isPrime(GCD(e,r-1)) and e==GCD(e,p-1)*GCD(e,q-1)*GCD(e,r-1)
assert len(message)>L and len(message)<2*L
assert b'SUSCTF' in message
m=bytes_to_long(pad(message))

c=pow(m,e,n)
print(c)
'''
2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
'''

根据题目，e是p-1,q-1,r-1的一个因子之积

image-20220228143414366

分解一下，考虑到最后一步肯定是开根然后CRT，e不可能太大，出题人也没那么好心，不会给你太小

所以ep应该是 757 或者 1709，eq 应该是66553，er应该是5156273

最后测出来 e = 757 * 66553 * 5156273

那么就先在 p , q , r 下分别进行一个 c 的“部分”解密，得出 m^ 757 % p， m^66553 % q，m^5156273 % r

考虑到这个 r 这部分实在是太大了，最后CRT的复杂度会很高。又注意到 原始 message的大小是介于 L 和 2L 之间的。最后是用 0 去填充到 3L 的。所以要想办法去掉这个填充。然后在 p 和 q 下去解 message 就可以了。去掉填充也很方便。因为是单纯的用 0 去填充的。所以相当于 m 乘以了一个 2^(8 * length)，到 c 这里就是乘上了 2^(8 * length * e)，所以最开始把 c 的这部分求逆求掉就好了。

然后就是在 p 下和 q 下 开根，再 CRT 结合。这一部分老生常谈，就不赘述了。

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
import random
import time
from Crypto.Util.number import long_to_bytes
from tqdm import tqdm

def AMM(o, r, q):
	# https://blog.soreatu.com/posts/intended-solution-to-crypto-problems-in-nctf-2019/
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - discrete_log(d, a)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c^r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result

# https://jayxv.github.io/2019/12/04/%E5%AF%86%E7%A0%81%E5%AD%A6%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%E4%B9%8B%E6%B5%85%E6%9E%90On%20r-th%20Root%20Extraction%20Algorithm%20in%20Fq/

def onemod(p,r): 
    t=p-2 
    while pow(t,(p-1)/r,p)==1: t-=1 
    return pow(t,(p-1)/r,p) 
 
def solution(p,root,e):  
    g=onemod(p,e) 
    may=set() 
    for i in range(e): 
        may.add(root*pow(g,i,p)%p) 
    return may


c = 2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
p=127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q=145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r=165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
N = p * q * r
ep = 757
eq = 66553
er = 5156273
c = (c * inverse_mod(int(pow(2,1024 * (ep*eq*er), N)), N ) % N)
cp = pow(c,inverse_mod(eq*er,p-1),p)
cq = pow(c,inverse_mod(ep*er,q-1),q)
mp = AMM(cp, ep, p)
mq = AMM(cq, eq, q)
mps = solution(p,mp,ep)
mqs = solution(q,mq,eq)
for mpp in tqdm(mps):
    for mqq in mqs:
        solution = CRT_list([int(mpp), int(mqq)], [p, q])
        if b"SUSCTF" in long_to_bytes(solution):
            print(long_to_bytes(solution))

InverseProlem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import numpy as np
#from secret import flag

def gravity(n,d=0.25):
    A=np.zeros([n,n])
    for i in range(n):
        for j in range(n):
            A[i,j]=d/n*(d**2+((i-j)/n)**2)**(-1.5)
    return A

n=len(flag)
A=gravity(n)
x=np.array(list(flag))
b=A@x
np.savetxt('b.txt',b)

代码很短啊，就是生成了一个矩阵，然后右乘了一下flag，给了输出。

原本以为给矩阵求逆一下就可以了，后来发现这个矩阵有点问题的，当 n 等于85 的时候，发现这个矩阵的行列式，，不能说是没有，也许是非常小叭。

image-20220228145337338

反正此时 A^-1 * A ! = E，所以直接求逆是不可能的。这里用的也是浮点数，所以直接解方程也是会出现精度问题，导致结果向量 b 好像加了噪声似的。唉，噪声？LWE啊，用格子去约。由于太小了。我这里我给他们都放大了一定倍数。为了把 b 里面的小数点给去掉，数了下大概要 16 个0。

然后全部取整，搞成int，再在 A 里面求一个 b 的CVP，然后直接右除拿到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import numpy as np
def gravity(n,d=0.25):
    A=np.zeros([n,n+1])
    for i in range(n):
        for j in range(n):
            A[i,j]=int((d/n*(d**2+((i-j)/n)**2)**(-1.5))*10e16)
        A[i,j+1] = 0
    return A
n=85
A=gravity(n)
with open ("b.txt") as f:
	data = f.read().split("\n")
b = [int(eval(i)*10e16) for i in data]
b.append(100)
A = matrix(ZZ,A)
Ab = A.stack(vector(b))
AB = Ab.BKZ(block_size = 22)
assert AB[0][-1] == 100
cvp = vector(list(vector(b) - AB[0])[:-1])
s = A \ cvp
print("".join(chr(i) for i in s[:-1] ))

Ez_Pager_Tiper

magic_box.py

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
class lfsr():
    def __init__(self, seed, mask, length):
        self.length_mask = 2 ** length - 1
        self.mask = mask & self.length_mask
        self.state = seed & self.length_mask

    def next(self):
        next_state = (self.state << 1) & self.length_mask
        i = self.state & self.mask & self.length_mask
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        next_state ^= output
        self.state = next_state
        return output

    def getrandbit(self, nbit):
        output = 0
        for _ in range(nbit):
            output = (output << 1) ^ self.next()
        return output


class generator():
    def __init__(self, lfsr1, lfsr2, magic):
        self.lfsr1 = lfsr1
        self.lfsr2 = lfsr2
        self.magic = magic

    def infinit_power(self, magic):
        return int(magic)

    def malicious_magic(self, magic):
        now = (-magic & magic)
        magic ^= now
        return int(now), int(magic)

    def confusion(self, c1, c2):
        magic = self.magic
        output, cnt = magic, 0
        output ^= c1 ^ c2
        while magic:
            now, magic = self.malicious_magic(magic)
            cnt ^= now >> (now.bit_length() - 1)
            output ^= now
        output ^= cnt * c1
        return int(output)

    def getrandbit(self, nbit):
        output1 = self.lfsr1.getrandbit(nbit)
        output2 = self.lfsr2.getrandbit(nbit)
        return self.confusion(output1, output2)

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
from magic_box import *
from secret import mask1, mask2, seed1, seed2, seed3
n1, n2 = 64, 12

flag = 'SUSCTF{***}'

def encrypt(cipher, ipath, opath):
    ifile=open(ipath,'rb')
    ofile=open(opath,'wb')
    plaintext=ifile.read()
    for ch in plaintext:
        c=ch^cipher.getrandbit(8)
        ofile.write(long_to_bytes(c))
    ifile.close()
    ofile.close()

def problem1():
    r = getRandomInteger(6)
    magic = 1<<r
    lfsr1 = lfsr(seed1, mask1, n1)
    lfsr2 = lfsr(seed2, mask2, n2)
    cipher = generator(lfsr1, lfsr2, magic)
    encrypt(cipher, "MTk4NC0wNC0wMQ==_6d30.txt", "MTk4NC0wNC0wMQ==_6d30.enc")

def problem2():
    magic = getPrime(64)
    lfsr1=lfsr(seed1, mask1, n1)
    lfsr2=lfsr(seed3, mask2, n2)
    cipher = generator(lfsr1, lfsr2, magic)
    encrypt(cipher, "MTk4NC0xMi0yNQ==_76ff.txt", "MTk4NC0xMi0yNQ==_76ff.enc")
    # flag in it?
    print(f'hint={magic}')
    # hint = 15193544052573546419

problem1()
problem2()

两个problem，三个lfsr伪随机数生成器，prob1用了lfsr1 和 lfsr2，magic是 1 << r，看到generator，对于两个lfsr的输出是放进了confusion，然后output = magic ^ c1 ^ c2，然后是while magic的循环， now, magic = self.malicious_magic(magic)，经过测试，当 magic 等于 1 << r 的时候，也就是 2 的幂次的时候，

(-magic & magic) = magic，所以 now = magic， magic = 0，循环只会走一趟。接下来now取最高位，肯定是 1了，output异或一下now，相当于异或magic，那就只剩 c1 ^ c2 了。出来后 output ^= cnt * c1，cnt此时是1，所以output最后只剩 c2 了。所以 output = input ^ c2

1
2
3
4
def malicious_magic(self, magic):
    now = (-magic & magic)
    magic ^= now
    return int(now), int(magic)

那么，看到题目另一个data文件夹里，发现文件都是以Date: 开头的，然后lfsr2又只有12级，所以爆！也就是 4095^2

爆了之后就知道seed2和mask2了。

然后看到prob2，此时给出magic是一个素数，同样经过测试，会发现，所有的循环走完后，cnt是0，异或now的部分叠加起来，最后就是magic。所以最后的输出 output = input ^ c1 ^ c2

注意到，文件都是以Date: 开头，解密第一个prob也获得了线索，就是Date: 后面的日期就是文件名解base64，所以最后搞出来我们能获得16字节明文。有了16字节的明文、密文，然后这里我们是知道mask2的，我们只需要爆4095个seed3就能获得4095个c2，从而得到4095个16字节的c1。注意到lfsr1是64级的，那么我们只需要64 * 2 = 128 bit = 16 字节的输出就能恢复lfsr的所有参数了。所以我们用4095个c2去恢复参数，然后生成相应的密钥流，尝试解密，观察结果。

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
from Crypto.Util.number import *
from magic_box import *
import os
from tqdm import tqdm
import string

n1=64
n2=16
magic = 15193544052573546419

with open("MTk4NC0wNC0wMQ==_6d30.enc","rb") as f:
	data1 = f.read()

# data = data1[:4]
# for i in tqdm(range(4095)):
# 	for j in range(4095):
# 		lfsr2 = lfsr(i, j, n2)
# 		s = ""
# 		for ch in data:
# 			tmp = lfsr2.getrandbit(8)
# 			c = chr(tmp ^ ord(ch))
# 			if c not in "Date":
# 				break
# 			s+=c
# 		else:
# 			if c == "Date":
# 				print(i,j,s)
# 				# 73%|███████▎  | 2988/4095 [02:21<00:53, 20.67it/s](2989, 2053, 'Date')

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

class lfsr():
    def __init__(self, seed, mask, length):
        self.length_mask = 2 ** length - 1
        self.mask = mask & self.length_mask
        self.state = seed & self.length_mask

    def next(self):
        next_state = (self.state << 1) & self.length_mask
        i = self.state & self.mask & self.length_mask
        output = 0
        while i != 0:
            output ^^= (i & 1)
            i = i >> 1
        next_state ^^= output
        self.state = next_state
        return output

    def getrandbit(self, nbit):
        output = 0
        for _ in range(nbit):
            output = (output << 1) ^^ self.next()
        return output

n1=64
n2=16
with open("MTk4NC0xMi0yNQ==_76ff.enc","rb") as f:
	outputs = f.read()
# output = input ^ c1 ^ c2

#已知两轮输出，恢复mask
data = b"Date: 1984-12-25"
output = bytes_to_long(outputs[:16])
inputs = bytes_to_long(data)
for seed3 in tqdm(range(4095)):
	lfsr2 = lfsr(seed3, 2053, n2)
	tmp = lfsr2.getrandbit(128)
	tmpc1 = list(bin(output ^^ inputs ^^ tmp)[2:].zfill(128))

	#已知两轮输出，恢复mask
	mat = [tmpc1[i:i+64] for i in range(64)]
	A = matrix(GF(2),mat)
	if not A.det():
		continue
	B = vector(GF(2),tmpc1[64:128])
	mask_int = list(A.solve_right(B))
	mask = ''.join(str(i) for i in mask_int)

	#mask = [int(n.str()) for n in A.solve_right(B).transpose().entries()]
	# 已知后一轮输出和mask，往前恢复一轮
	A = []
	for i in range(64):
	    B = []
	    for j in range(64):
	        if j == 63:
	            B.append(mask[i])
	        elif j == i-1:
	            B.append(1)
	        else:
	            B.append(0)
	    A.append(B)
	M = matrix(GF(2),A)
	M = M^64

	if not M.det():
		continue
	key = ""
	for i in M.solve_left(vector(GF(2),tmpc1[:64])):
	    key += str(i)
	key = int(key,2)

	lfsr1 = lfsr(key, int(mask,2), n1)
	lfsr2 = lfsr(seed3, 2053, n2)
	FLAG = ""
	# 少看几个，对了就停
	for i in range(32):
		tmp = lfsr1.getrandbit(8) ^^ lfsr2.getrandbit(8) ^^ (outputs[i])
		FLAG += chr(tmp)

	if FLAG[16] != "\r": #日期结束后是跟一个 \r\n
		continue
	else:
		print(FLAG,seed3,key,int(mask,2))

# ix'ÒMìýã&ÉúÈ 447 8149177008550264303 13814079135560313241984-12-25
# èû£¼’ñr,¤YÞìþ° 771 18096245683970471305 115606832613435467084-12-25
# Së“05ÔáuëÍC 1674 13294312146216746169 115187255862075445261984-12-25
#  75%|███████▍  | 3053/4095 [00:49<00:16, 63.38it/s]Date: 1984-12-25
# Though the hun 3054 5071452738113266023 9223372036854775811
#  91%|█████████ | 3713/4095 [01:00<00:06, 60.53it/s]

seed3 = 3054
key = 5071452738113266023
mask1 = 9223372036854775811

# 然后那这几个数解完所有密文就行

SpecialCurve3

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
from Crypto.Util.number import *
from secret import flag,getMyPrime
import hashlib
import random

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

    def __str__(self):
        return f'SpecialCurve({self.p},{self.a},{self.b})'

    def add(self,P1,P2):
        x1,y1=P1
        x2,y2=P2
        if x1==0:
            return P2
        elif x2==0:
            return P1
        elif x1==x2 and (y1+y2)%self.p==0:
            return (0,0)
        if P1==P2:
            t=(2*self.a*x1-self.b)*inverse(2*y1,self.p)%self.p
        else:
            t=(y2-y1)*inverse(x2-x1,self.p)%self.p
        x3=self.b*inverse(self.a-t**2,self.p)%self.p
        y3=x3*t%self.p
        return (x3,y3)

    def mul(self,P,k):
        assert k>=0
        Q=(0,0)
        while k>0:
            if k%2:
                k-=1
                Q=self.add(P,Q)
            else:
                k//=2
                P=self.add(P,P)
        return Q

def problem(size,k):
    p=getMyPrime(size)
    x=random.randint(1,p-1)
    y=random.randint(1,p-1)
    e=random.randint(1,p-1)
    a=k*random.randint(1,p-1)**2%p
    b=(a*x**2-y**2)*inverse(x,p)%p
    curve=SpecialCurve(p,a,b)
    G=(x,y)
    Q=curve.mul(G,e)
    print(f'curve={curve}')
    print(f'G={G}')
    print(f'Q={Q}')
    return e

e1=problem(128,1)
e2=problem(256,0)
e3=problem(512,-1)
enc=bytes_to_long(hashlib.sha512(b'%d-%d-%d'%(e1,e2,e3)).digest())^bytes_to_long(flag.encode())
print(f'enc={enc}')

三个problem，有几个华点，生成prime的方式没给，估计有蹊跷。果不其然，经过全都是p+1 smooth的。所以三条线中阶要是等于p+1，就能直接爆了。

第二个华点，problem1用的p很小，显然是要把曲线上的点映射到整数域上去开log。

第三个华点，problem2的 a = 0，一般来说是条奇异曲线，可能会有些比较简单的映射规则。（那么第一个华点应该是给problem3用的了）

先看第一个，不难看出是条圆锥曲线：y^2 = a x ^ 2 + b x

此时 a 是一个二次剩余，我们记为 y^2 = a^2 x ^ 2 + b x 好了。

img

用共点推的，然后直接测这个映射

f: (x,y) -> （k+a）/ (k-a)

e · (x,y) -> ((k+a）/ (k-a) )^e 其中k = y / x

发现不是共点的时候也满足，那么第一个problem解决。

第二个problem，a = 0，从上面看就知道 k2 = k1 / 2，所以y2 = y1 * x2 / (2 * x1)，把 x 都用 y 表示一下，消一下，就得到了 2 * y1 = y2，再简单测一下就能发现是一个简单的倍数关系，那除一下就好了。

第三个problem，此时给 a 取负了，那么这一部分就不是二次剩余了，有限整数域下我们是求不出上面的 a 的（就是开根），所以估计要用到第一个华点，测一下这条线的阶，乘一下p +1 发现回到 0 了，那么显然了，这里就去子群里爆破求解，最后crt组合得解。

去子群里爆破的步骤，就是把G 和 Q 都降阶（就是两边乘以 （p + 1） // order)，此时G 和 Q 的阶都是 order 了，然后就在这个order里去爆，当 i * G == Q 时，此时 i = e % order，

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
from Crypto.Util.number import *
#from secret import flag,getMyPrime
from Crypto.Util.number import getPrime as getMyPrime
import hashlib
import random
flag = "a"*40

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

    def __str__(self):
        return f'SpecialCurve({self.p},{self.a},{self.b})'

    def add(self,P1,P2):
        x1,y1=P1
        x2,y2=P2
        if x1==0:
            return P2
        elif x2==0:
            return P1
        elif x1==x2 and (y1+y2)%self.p==0:
            return (0,0)
        if P1==P2:
            t=(2*self.a*x1-self.b)*inverse(2*y1,self.p)%self.p
        else:
            t=(y2-y1)*inverse(x2-x1,self.p)%self.p
        x3=self.b*inverse(self.a-t**2,self.p)%self.p
        y3=x3*t%self.p
        return (x3,y3)

    def mul(self,P,k):
        assert k>=0
        Q=(0,0)
        while k>0:
            if k%2:
                k-=1
                Q=self.add(P,Q)
            else:
                k//=2
                P=self.add(P,P)
        return Q

def problem(size,k):
    p=getMyPrime(size)
    x=random.randint(1,p-1)
    y=random.randint(1,p-1)
    e=random.randint(1,p-1)
    a=k*random.randint(1,p-1)**2%p
    b=(a*x**2-y**2)*inverse(x,p)%p
    curve=SpecialCurve(p,a,b)
    G=(x,y)
    Q=curve.mul(G,e)
    print(f'curve={curve}')
    print(f'G={G}')
    print(f'Q={Q}')
    return e

sage:
# problem1
K = GF(p)
a = int(K(a).nth_root(2))

kG = K(G[1])) / K(G[0]))
kQ = K(Q[1]) / K(Q[0])
fG = K((kG+a)) / K((kG-a))
fQ = K((kQ+a)) / K((kQ-a))
e1 = log(fQ,fG)
# problem2
e2 = K(Q[1]) / K(G[1])


# problem3
p=52373730653143623993722188411805072409768054271090317191163373082830382186155222057388907031638565243831629283127812681929449631957644692314271061305360051

# a=[(4, 1), (2663, 1), (5039, 1), (14759, 1), (18803, 1), (21803, 1), (22271, 1), (22307, 1), (23879, 1), (26699, 1), (35923, 1), (42727, 1), (48989, 1), (52697, 1), (57773, 1), (58129, 1), (60527, 1), (66877, 1), (69739, 1), (74363, 1), (75869, 1), (79579, 1), (80489, 1), (81043, 1), (81049, 1), (82531, 1), (84509, 1), (85009, 1), (91571, 1), (96739, 1), (98711, 1), (102481, 1), (103357, 1), (103981, 1)]
# FLAG=[]
# MOD=[]
# for each in a:
#     order_left = (p+1)//each[0]
#     QQ = curve.mul(Q,order_left)
#     GG = curve.mul(G,order_left) 
#     for i in range(each[0]):
#         if curve.mul(GG,i) == QQ:
#             FLAG.append(i)
#             MOD.append(each[0])
#             break
#     print(FLAG,MOD)

e3 = crt(FLAG,MOD)


curve=SpecialCurve(233083587295210134948821000868826832947,73126617271517175643081276880688551524,88798574825442191055315385745016140538)
G=(183831340067417420551177442269962013567, 99817328357051895244693615825466756115)
Q=(166671516040968894138381957537903638362, 111895361471674668502480740000666908829)
e1=184572164865068633286768057743716588370
print(curve.mul(G,e1)==Q)

curve=SpecialCurve(191068609532021291665270648892101370598912795286064024735411416824693692132923,0,58972296113624136043935650439499285317465012097982529049067402580914449774185)
G=(91006613905368145804676933482275735904909223655198185414549961004950981863863, 96989919722797171541882834089135074413922451043302800296198062675754293402989)
Q=(13504049588679281286169164714588439287464466303764421302084687307396426249546, 110661224324697604640962229701359894201176516005657224773855350780007949687952)
e2=131789829046710687154053378348742202935151384644040019239219239301007568911745
print(curve.mul(G,e2)==Q)
curve=SpecialCurve(52373730653143623993722188411805072409768054271090317191163373082830382186155222057388907031638565243831629283127812681929449631957644692314271061305360051,28655236915186704327844312279364325861102737672471191366040478446302230316126579253163690638394777612892597409996413924040027276002261574013341150279408716,42416029226399083779760024372262489355327595236815424404537477696856946194575702884812426801334149232783155054432357826688204061261064100317825443760789993)
G=(15928930551986151950313548861530582114536854007449249930339281771205424453985946290830967245733880747219865184207937142979512907006835750179101295088805979, 29726385672383966862722624018664799344530038744596171136235079529609085682764414035677068447708040589338778102975312549905710028842378574272316925268724240)
Q=(38121552296651560305666865284721153617113944344833289618523344614838728589487183141203437711082603199613749216407692351802119887009907921660398772094998382, 26933444836972639216676645467487306576059428042654421228626400416790420281717654664520663525738892984862698457685902674487454159311739553538883303065780163)

e3=23331486889781766099145299968747599730779731613118514070077298627895623872695507249173953050022392729611030101946661150932813447054695843306184318795467216
print(curve.mul(G,e3)==Q)

enc=bytes_to_long(hashlib.sha512(b'%d-%d-%d'%(e1,e2,e3)).digest())^4161358072766336252252471282975567407131586510079023869994510082082055094259455767245295677764252219353961906640516887754903722158044643700643524839069337
print(long_to_bytes(enc))
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com

赏

文章标题:2022 SUSCTF

文章字数:3.7k

本文作者:Van1sh

发布时间:2022-02-28, 11:18:35

最后更新:2022-02-28, 20:50:10

原始链接:http://jayxv.github.io/2022/02/28/2022 SUSCTF/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

©2020 Van1sh

Built with Hexo and 3-hexo theme

目录
×

喜欢就点赞,疼爱就打赏