CBCTF2023

NaCl Lv1
  2024-01-04 22:22 2024-01-04 22:22 创建   2024-01-04 22:25:51 2024-01-04 22:25:51 更新    

二次剩余

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from hashlib import *
m = getRandomNBitInteger(300)

def gen_prime(n):
    p = getPrime(n)
    while p % 4 == 1:
        p = getPrime(n)
    return p

p = gen_prime(128)
print(f'p = {p}')
a = pow(m,2,p**3)

print(f'a = {a}')

flag = 'CBCTF{' + sha256(str(m).encode()).hexdigest() + '}'


'''
p = 334032027984155099402863982848235447227
a = 6363500121827697008224968006879792916113549541401919095721781619316319436679204160344656454420382763358609215987320
'''

先在模p的情况下求解二次剩余

1
2
3
4
5
6
7
8
9
10
#sagemath
p = 334032027984155099402863982848235447227
a = 6363500121827697008224968006879792916113549541401919095721781619316319436679204160344656454420382763358609215987320
PR.<x> = PolynomialRing(Zmod(p))
f=x^2-a
result=f.roots()
print(result)
‘‘‘
[(327148288665384316379705520751268986114, 1), (6883739318770783023158462096966461113, 1)]
’’’

然后用hensel liftting求模p^3的解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from hashlib import *

p = 334032027984155099402863982848235447227
a = 6363500121827697008224968006879792916113549541401919095721781619316319436679204160344656454420382763358609215987320
r=327148288665384316379705520751268986114

#hensel lifting
now=r
for i in range(1,3):
    v=(a%p^(i+1)-now^2)/p^i*inverse(2*now,p^i)
    now+=v*p^i%p^(i+1)
   
print('CBCTF{' + sha256(str(now).encode()).hexdigest() + '}')

CBCTF{1cb90edb5af365e836a7656b3397fe62a11469ceb6d6a91f152f07ff54b71b0e}

babyrsa

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
from Crypto.Util.number import *
from gmpy2 import *
from flag import flag
import math

def genprime():
    k = getRandomNBitInteger(64)
    p = 2023*k**5 + 2022*k**4 - 2023*k**3 - 2021*k**2 + 2020*k + 2019 + int(k**3*sin(k+2023)) - int(k**3*cos(k**2-2023)) + int(math.e**(23) * k)
    q = 2023*k**5 - 2022*k**4 + 2023*k**3 - 2021*k**2 + 2020*k - 2019 - int(k**2*sin(k*2023)) + int(k**2*cos(k**2*2023)) + int(math.e**(23) * k**2)
    p =next_prime(p)
    q =next_prime(q)
   
    return p,q

def encrypt(m,e,p,q):
    
    cp = pow(m,e,p)
    cq = pow(m,e,q)
    return cp,cq

m = bytes_to_long(flag)

p,q = genprime()
e = 65537
n = p*q
cp,cq = encrypt(m,e,p,q)

print(f'cp = {cp}')
print(f'cq = {cq}')
print(f'e = {e}')
print(f'n = {n}')

'''

cp = 2951478008429204122935337892738568379560198116832413976655842487911220583813451657632437020302109151
cq = 3042975941102854775825773171747972690767384220243723396259215468783407690302613940898320940464213373
e = 65537
n = 13226258685595630160447827442153267599814292160977306459359416297020102688049793771120158029953432640539514974565723831126909317859357612109049397896863392224521508922404189962829783829182814282953169

'''

先是多项式rsa，因为k比较大，所以看最高次就可以确定增减性然后二分查找直接开梭（虽然k在递减或波动区间的可能性不大，实在不行直接在对应区间爆破）

然后就是中国剩余映射在p，q下求出对应的值再crt得出m

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
from Crypto.Util.number import *
from gmpy2 import *
import math

n = 13226258685595630160447827442153267599814292160977306459359416297020102688049793771120158029953432640539514974565723831126909317859357612109049397896863392224521508922404189962829783829182814282953169
k=0
p = 2023*k**5 + 2022*k**4 - 2023*k**3 - 2021*k**2 + 2020*k + 2019 + int(k**3*sin(k+2023)) - int(k**3*cos(k**2-2023)) + int(math.e**(23) * k)
q = 2023*k**5 - 2022*k**4 + 2023*k**3 - 2021*k**2 + 2020*k - 2019 - int(k**2*sin(k*2023)) + int(k**2*cos(k**2*2023)) + int(math.e**(23) * k**2)
i=2**64
j=0
while j<=i:
    k=(i+j)//2
    p = 2023*k**5 + 2022*k**4 - 2023*k**3 - 2021*k**2 + 2020*k + 2019 + int(k**3*sin(k+2023)) - int(k**3*cos(k**2-2023)) + int(math.e**(23) * k)
    q = 2023*k**5 - 2022*k**4 + 2023*k**3 - 2021*k**2 + 2020*k - 2019 - int(k**2*sin(k*2023)) + int(k**2*cos(k**2*2023)) + int(math.e**(23) * k**2)
    m=next_prime(p)*next_prime(q)
    if m==n:
        break
    if m>n:
        i=k-1
    if n>m:
        j=k+1
p,q=next_prime(p),next_prime(q)
#"k=17821511070084697841"

dp=inverse(e,p-1)
dq=inverse(e,q-1)
mp=pow(cp,dp,p)
mq=pow(cq,dq,q)
m=crt([mp,mq],[p,q])
print(long_to_bytes(m))

b‘CBCTF{U3e_b1n@3y-s2arc9-ca7_2asi1y-fin9_K-&_CRT_1s-Use75l!!!}’

Mixtrue

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
from Crypto.Util.number import *
import random
from gmpy2 import *
from flag import flag

p = getPrime(256)
q = getPrime(256)
while p > q:
    q = getPrime(256)
n = p*q
hint1 = p^2*q

hint2 = p*q^2

print(f'hint1 = {hint1}')
print(f'hint2 = {hint2}')


s = [getPrime(512) for _ in range(2)]
a,b = getPrime(32),getPrime(32)

c = (s[0]*a**2*b + s[1]*a*b**2) % p**2 

print(f'c = {c}')
print(f's = {s}')

class LCG:
    def __init__(self, seed, a, b, m):
        self.seed = seed 
        self.a = a  
        self.b = b  
        self.m = m  

    def generate(self):
        self.seed = (self.a * self.seed + self.b) % self.m
        return self.seed


lcg = LCG(flag, a, b, q**2)

for i in range(getPrime(8)):
    lcg.generate()

print(f'x = {lcg.generate()}')


hint1 = 204639519228482132227892124558206581852901166540934482956077092683272047215603
hint2 = 5223497084433284165407855714831225232980885646146697788945658224946492136469028456907776417823381149203014730026034726336823564762750860023257769169870671
c = 3800357091980764536414497032084521685838674051584417343344124843521990588109085151037748013700811799398796635922619667885187270167830981934930753782605245
s=[10631535627345799018411095033606552047599892624931967169233572506891701326528002384214254342729805768875583936111640196339241117790402788019517706376783183, 10457198125564719416520015786706105819881358861954538824120777188536392438469456037047204911363866908866056107415656206075097420502319938820524677159455243]
x=48683026035031143742103130326904565575492854

先按位求p，q（深搜）；在格规约爆破a，b；再在结果上反过来跑九次

躲猫猫 Ⅰ

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

humble_part, Ech0_part, Z3r0_part = flag[:len(flag)//3],flag[len(flag)//3:2*len(flag)//3],flag[2*len(flag)//3:]

#学活广场 humb1e似乎在旗杆背后探头探脑
secret = bin(bytes_to_long(humble_part))[2:]
R.<humb1e> = PolynomialRing(GF(getPrime(50)))
R = R.quo(humb1e^30+random.randint(1,2^49)*humb1e+1)
look_for_humb1e = [R(humb1e ^ (1500*random.choice([ord('h'),ord('u'),ord('m'),ord('b'),ord('1'),ord('e')]))) if i == '1' else R.random_element() for i in secret]

#都放假了四教还亮着灯？抓到Ech0在躲猫猫的时候偷学密码！
secret = bin(bytes_to_long(Ech0_part))[2:]
look_for_Ech0 = [prod([j[0]^(j[1]-1)*(j[0]-1) for j in factor(random.getrandbits(100))]) if i == '1' else getPrime(100)-1 for i in secret]

#雪下得好大，花圃周围的亮白色身影是Z3r0吗
secret = bin(bytes_to_long(Z3r0_part))[2:]
p = getPrime(512)
look_for_Z3r0 = [pow(31137,65537,p*getPrime(512)) if i == '1' else pow(31137,65537,getPrime(512)*getPrime(512)) for i in secret]

print(look_for_humb1e)
print(look_for_Ech0)
print(look_for_Z3r0)

第一部分：统计出现次数，最多的前五个

第二部分：+1检测是不是质数，然后稍作修改

第三部分：Mi-31137然后gcd会有公因数p

躲猫猫 Ⅱ

第一部分：就求群上元素然后看输出的矩阵在不在群元素里面

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
import random
from Crypto.Util.number import *
from Crypto.Cipher import AES
import os
from secret import flag

gtg_part, beeee_part, Seg_Tree_part = flag[:len(flag)//3],flag[len(flag)//3:2*len(flag)//3],flag[2*len(flag)//3:]


#你惊异地发现，树丛里黑糊糊的枝叶居然有点神似gtg的辫子
secret = bin(bytes_to_long(gtg_part))[2:]

def matrix_crt(mp,mq,p,q):
    m = matrix(Zmod(p*q),[[crt([int(mp[i,j]),int(mq[i,j])],[p,q]) for i in range(2)] for j in range(2)])
    return m

p = getPrime(20)
a,b = MatrixGroup(matrix(GF(149),[[41,21],[82,81]])),MatrixGroup(matrix(GF(163),[[41,21],[82,81]]))
ma,mb = a.gens()[0],b.gens()[0]

look_for_gtg = [list(matrix_crt(matrix(ZZ,ma^random.randint(1,p)),matrix(ZZ,mb^random.randint(1,p)),149,163)) if i == '1' else list(matrix(Zmod(149*163),[[random.randint(1,149*163)for _ in range(2)] for __ in range(2)])) for i in secret]


#前两天刚考完研，图书馆难得清静，你在9楼搜寻，只见角落闪烁着微光。好像是beeee！
secret = bin(bytes_to_long(beeee_part))[2:]
m,p = getPrime(1023),getPrime(1024)

def ppallier(m,p):
    c = pow(p+1,getPrime(40)*m,p^2)*pow(random.randint(1,p^2-1),p,p^2)%p^2
    return c

look_for_beeee = [pow(ppallier(m,p),p-1,p^2) if i == '1' else random.randint(1,p^2-1) for i in secret]


#看上去有人卡视野藏在协会天台上。你走了过去，Seg_Tree正在假装自己是一颗树。
secret = bin(bytes_to_long(Seg_Tree_part))[2:]
look_for_Seg_Tree = [AES.new(key = os.urandom(16),mode = AES.MODE_CFB,iv = os.urandom(16)).decrypt((os.urandom(16)*3)[:33]) if i == '1' else AES.new(key = os.urandom(16),mode = AES.MODE_CFB,iv = os.urandom(16)).encrypt((os.urandom(16)*3)[:33]) for i in secret]


print(look_for_gtg)
print(look_for_beeee)
print(look_for_Seg_Tree)
  • 标题: CBCTF2023
  • 作者: NaCl
  • 创建于 : 2024-01-04 22:22:00
  • 更新于 : 2024-01-04 22:25:51
  • 链接: https://www.naclwww.xyz/2024/01/04/CBCTF2023/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
此页目录
CBCTF2023
  1. 二次剩余
  2. babyrsa
  3. Mixtrue
  4. 躲猫猫 Ⅰ
  5. 躲猫猫 Ⅱ