2023WMCTF

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 1.7k 阅读时长 ≈ 6 分钟

复现WMCTF——Crypto部分题目

badprime

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

M = 0x7cda79f57f60a9b65478052f383ad7dadb714b4f4ac069997c7ff23d34d075fca08fdf20f95fbc5f0a981d65c3a3ee7ff74d769da52e948d6b0270dd736ef61fa99a54f80fb22091b055885dc22b9f17562778dfb2aeac87f51de339f71731d207c0af3244d35129feba028a48402247f4ba1d2b6d0755baff6

def getMyprime(BIT):
    while True:
        p = int(pow(65537, getRandomRange(M>>1, M), M)) + getRandomInteger(BIT-int(M).bit_length()) * M
        if isPrime(p):
            return p

p = getMyprime(1024)
q = getPrime(1024)
n = p * q
m = bytes_to_long(flag)

print("Try to crack the bad RSA")
print("Public key:", n)
print("The flag(encrypted):", pow(m, 65537, n))
print("Well well, I will give you the hint if you please me ^_^")
leak = int(input("Gift window:"))
if M % leak == 0:
    print("This is the gift for you: ", p % leak)
else:
    print("I don't like this gift!")

第一眼看这个p的生成方式，以及M，就以为是roca。

尝试了很久用roca来分解n，并没成功

看到$hint \equiv p \mod leak$，这个$leak$是$M$的因子，M是前126个素数之积(无所谓)，直接把M进去

得到$hint \equiv p \mod M$

$\therefore p = hint + KM$，这里得到的$hint=971bit$，$M=971bit$，所以$k$大概只有$53bit$

可以爆出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#sage
from Crypto.Util.number import *
import gmpy2

hint= 
M = 19467773070115377343221509599623925236459751278180415885837207534756855405403128279156705968461708578168638327032034542684864920135818987044810141311008655898015207220772515212093850725541003213054560185603695585660265284153421684796257245143362498012760214539505870197264858636122745485373430
n = 
c = 
e = 65537

R.<k> = PolynomialRing(Zmod(n))

f = k*M + hint
f = f.monic()
roots = f.small_roots(X = 2^55,beta = 0.4)

#print(roots)
p = int(roots[0])*M + hint
q = n // p
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(int(m)))

signin

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

def pr(msg):
    print(msg)


def gen_prime(bit):
    while 1:
        P = getPrime(bit)
        if len(bin(P)) - 2 == bit:
            return P

pq_bit = 512
offset = 16

P,Q = [gen_prime(pq_bit) for i in range(2)]
N = P * Q
gift = int(bin(P ^ (Q >> offset))[2+offset:],2)
pr(N)
pr(gift)

inpP = int(input())
if inpP != P:
    pr(b"you lose!")
    exit()

secret = randrange(0,P)
bs = [randrange(0,P) for _ in range(38)]

results = [(bi * secret) % P for bi in bs]
rs = [ri & (2 ** offset - 1)  for ri in results]

pr(bs)
pr(rs)
inpsecret = int(input())
if inpsecret == secret:
    pr(flag)

又是类似$p \otimes q$的题目，类似于DAS7月赛

先遍历$2^{15}——2^{16}$恢复出gift，再爆出p,q

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
from tqdm import *

h = 
N = 

for j in trange(2**15,2**16):
    gift = int(bin(j)[2:] +bin(h)[2:].rjust(496,'0'),2)
    pbar = gift >>(512-16)
    while True:
        try:
            qbar = (N>>(1024 - pbar.bit_length()*2))//pbar
            qbar = qbar>>6
            gifts = gift^(qbar<<(512-16-qbar.bit_length()))
            pbar = gifts >> (512-16-qbar.bit_length())

        except:
            break

    for i in range(64):
        p = (pbar<<6)+i
        if N % p == 0:
            q = N//p
            print("[+] p =",p)
            print("[+] q =",q)
            break

$\because R_i \equiv B_i × secret \mod p$，题目只给出了$R_i$的低16位

$r_i \equiv R_i \mod 2^{16}$

$\therefore r_i \equiv (B_i \times secret \mod p) \mod 2^{16}$

因为前面$R_i \equiv B_i × secret \mod p$

所以可以把mod 2^16 和mod p交换

于是有$r_i \equiv (B_i×secret \mod 2^{16}) \mod p \longrightarrow r_i \equiv B_i×secret + k_i×2^{16} \mod p$

$\therefore k_i×2^{16} \equiv B_i×secret -r_i \mod p \longrightarrow k_i \equiv B_i×secret×inv - r_i×inv \mod p $这里$inv$是$2^{16}$模$p$的逆元

最后可以得到$k_i = B_i×secret×inv - r_i×inv + l_ip$

于是有

这里的$k_i \approx 496bit$，所以取$K=2^{496}$，为了让右边向量的值都差不多大，调出$\frac{K×secret}{p}$

因为这题不是很清楚secret的大小，我就直接套脚本了。

现学的，理解不是很透彻

推导

$$
\because R_i \equiv B_i × secret \mod p
$$
题目只给出了$R_i$的低16位，即$r_i$
$$
R_{ihigh} \times 2^{16} + r_i \equiv B_i \times secret \mod p
$$
则有
$$
R_{ihigh} \times 2^{16} + r_i = B_i \times secret + k_i \times p
$$
其中$R_{ihigh} \approx 2^{496}$，$secret \approx 2^{512}$，$k_i \approx 2^{512}$

考虑把$R_{ihigh}$单独放在等号左边
$$
R_{ihigh} \equiv (B_i \times secret - r_i ) \times (2^{16})^{-1} \mod p
$$

$$
R_{ihigh} = (B_i \times secret - r_i) \times (2^{16})^{-1} + k_i \times p
$$

构造格

$R_{ihigh} \approx 496bit$，取$K = 2^{496}$

调整格为

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
from tqdm import *
from gmpy2 import *

h = 
N = 

for j in trange(2**15,2**16):
    gift = int(bin(j)[2:] +bin(h)[2:].rjust(496,'0'),2)
    pbar = gift >>(512-16)
    while True:
        try:
            qbar = (N>>(1024 - pbar.bit_length()*2))//pbar
            qbar = qbar>>6
            gifts = gift^(qbar<<(512-16-qbar.bit_length()))
            pbar = gifts >> (512-16-qbar.bit_length())

        except:
            break

    for i in range(64):
        p = (pbar<<6)+i
        if N % p == 0:
            q = N//p
            print("[+] p =",p)
            print("[+] q =",q)
            break

p = 
B =
R = 
temp = gmpy2.invert(2^16,p)

mbits = 512
lbits = 32
bits = mbits - lbits
n = len(R)

M = Matrix(QQ,n+2,n+2)
for i in range(n):
    M[i,i] = p
    M[-2,i] = B[i]*temp
    M[-1,i] = -R[i]*temp

t = QQ(2^bits / p)
K = 2^bits

M[-2,-2] = t
M[-1,-1] = K

for line in M.LLL():
    if abs(line[-1]) == K:
        secret = abs(line[-2]) // t
        print(secret)

HNP问题参考：lattice的HNP问题学习_无趣的浅的博客-CSDN博客

浅尝 Lattice 之 HNP-安全客 - 安全资讯平台 (anquanke.com)

welcome_signer1 —— 先搁着

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from sympy import isprime
from tqdm import tqdm 
import random

flag = b"***********************************"
def pad(message):
    return message + b"\x00"*((16-len(message)%16)%16)

def myfastexp(m,d,N,j,N_):
    A = 1
    d = bin(d)[2:]
    n = len(d)
    for i in range(n-1,-1,-1):
        if i < j:
            #print(A)
            N = N_
        A = A*A % N
        if d[i] == "1":
            A = A * m % N
    return A

def encrypt(message,key):
    key = bytes.fromhex(md5(str(key).encode()).hexdigest())
    enc = AES.new(key,mode=AES.MODE_ECB)
    c   = enc.encrypt(pad(message))
    return c


border = "|"
print(border*75)
print(border, "Hi all, I have created an algorithm that can quickly calculate powers. ", border)
print(border, "But it looks like there's something wrong with it. Your task is to get ", border)
print(border, "its private key,and decrypt the cipher to cat the flag ^-^             ", border)
print(border*75)


while True:
# generate
    p = getPrime(512)
    q = getPrime(512)
    n = p*q
    e = 17
    if GCD(e,(p-1)*(q-1)) == 1:
        d = inverse(e,(p-1)*(q-1))
        n_ = n 
        break

msg = bytes_to_long(b"Welcome_come_to_WMCTF")
sig = pow(msg,d,n)

CHANGE = True
while True:
    try:
        ans = input("| Options: \n|\t[G]et data \n|\t[S]ignatrue \n|\t[F]ault injection \n|\t[Q]uit\n").lower().strip()
        
        if ans == 'f':
            if CHANGE:
                print(border,"You have one chance to change one byte of N. ")
                temp,index = input("bytes, and index:").strip().split(",")
                assert 0<= int(temp) <=255
                assert 0<= int(index) <= 1023 
                n_ = n ^ (int(temp)<<int(index))
                print(border,f"[+] update: n_ -> \"{n_}\"")
                CHANGE = False
            else:
                print(border,"Greedy...")
        elif ans == 'g':
            print(border,f"n = {n}")
            print(border,f"flag_ciphertext = {encrypt(flag,d).hex()}")
        elif ans == 's':
            index = input("Where your want to interfere:").strip()
            sig_ = myfastexp(msg,d,n,int(index),n_)
            print(border,f"signature of \"Welcome_come_to_WMCTF\" is {sig_}")
        elif ans == 'q':
            quit()
    except Exception as e:
        print(border,"Err...")
        quit()

welcome_signer2 —— 先搁着

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
import random

flag = b"***********************************"
def pad(message):
    return message + b"\x00"*((16-len(message)%16)%16)


def myfastexp(m,d,N,j,N_):
    A = 1
    B = m
    d = bin(d)[2:][::-1]
    n = len(d)
    N = N
    for i in range(n):
        if d[i] == '1':
            A = A * B % N
        #  a fault occurs j steps before the end of the exponentiation
        if i >= n-1-j:
            N = N_
        B = B**2 % N
    return A


def encrypt(message,key):
    key = bytes.fromhex(md5(str(key).encode()).hexdigest())
    enc = AES.new(key,mode=AES.MODE_ECB)
    c   = enc.encrypt(pad(message))
    return c


border = "|"
print(border*75)
print(border, "Hi all, I have another algorithm that can quickly calculate powers. ", border)
print(border, "But still there's something wrong with it. Your task is to get      ", border)
print(border, "its private key,and decrypt the cipher to cat the flag ^-^          ", border)
print(border*75)


while True:
# generate
    p = getPrime(512)
    q = getPrime(512)
    n = p*q
    e = 17
    if GCD(e,(p-1)*(q-1)) == 1:
        d = inverse(e,(p-1)*(q-1))
        n_ = n 
        break
n_ = n
msg = bytes_to_long(b"Welcome_come_to_WMCTF")
sig = pow(msg,d,n)
assert sig == myfastexp(msg,d,n,0,n_)
CHANGE = True
while True:
    try:
        ans = input("| Options: \n|\t[G]et data \n|\t[S]ignatrue \n|\t[F]ault injection \n|\t[Q]uit\n").lower().strip()
        
        if ans == 'f':
            if CHANGE:
                print(border,"You have one chance to change one byte of N. ")
                temp,index = input("bytes, and index:").strip().split(",")
                assert 0<= int(temp) <=255
                assert 0<= int(index) <= 1023 
                n_ = n ^ (int(temp)<<int(index))
                print(border,f"[+] update: n_ -> \"{n_}\"")
                CHANGE = False
            else:
                print(border,"Greedy...")
        elif ans == 'g':
            print(border,f"n = {n}")
            print(border,f"flag_ciphertext = {encrypt(flag,d).hex()}")
        elif ans == 's':
            index = input("Where your want to interfere:").strip()
            sig_ = myfastexp(msg,d,n,int(index),n_)
            print(border,f"signature of \"Welcome_come_to_WMCTF\" is {sig_}")
        elif ans == 'q':
            quit()
    except Exception as e:
        print(border,"Err...")
        quit()

​

-------------已经到底啦！-------------