强网杯2024_crypto

前言#

一共七题，出了三个，但是海鲜市场上面已经py烂了，我该喜还是该忧呢？在这里就只写上自己已经出了的题，其他的慢慢复现，最近期中考试+香港比较忙。

题目#

EzRsa#

task

1
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
2
import random, gmpy2
3

4
class RSAEncryptor:
5
  def __init__(self):
6
    self.g = self.a = self.b = 0
7
    self.e = 65537
8
    self.factorGen()
9
    self.product()
10

11
  def factorGen(self):
12
    while True:
13
      self.g = getPrime(500)
14
      while not gmpy2.is_prime(2*self.g*self.a+1):
15
        self.a = random.randint(2**523, 2**524)
16
      while not gmpy2.is_prime(2*self.g*self.b+1):
17
        self.b = random.randint(2**523, 2**524)
18
      self.h = 2*self.g*self.a*self.b+self.a+self.b
19
      if gmpy2.is_prime(self.h):
20
        self.N = 2*self.h*self.g+1
21
        print(len(bin(self.N)))
22
        return
23

24
  def encrypt(self, msg):
25
    return gmpy2.powmod(msg, self.e, self.N)
26

27

28
  def product(self):
29
    with open('/flag', 'rb') as f:
30
      self.flag = f.read()
31
    self.enc = self.encrypt(self.flag)
32
    self.show()
33
    print(f'enc={self.enc}')
34

35
  def show(self):
36
    print(f"N={self.N}")
37
    print(f"e={self.e}")
38
    print(f"g={self.g}")
39

40

41
RSAEncryptor()

思路：重点代码是 $h=2gab+a+b$ 和 $N=2hg+1$ ,我们讲 $N$ 直接展开,其实就是 $N=(2ga+1)(2gb+1)$ ,这个就是老熟人了，Common Prime Rsa,可以参考独奏的文章，易知是 $g<a+b$ 的类型,我们之间修改模板就行了。

exp

1
from sage.groups.generic import bsgs
2
from Crypto.Util.number import *
3
from pwn import*
4
import gmpy2
5
from sympy import primerange
6
p=remote('47.94.226.70', 32973)
7

8
e=65537
9

10
N=p.recvline().decode().split('=')[1]
11
e=p.recvline().decode().split('=')[1]
12
g=p.recvline().decode().split('=')[1]
13
enc=p.recvline().decode().split('=')[1]
14
N=int(N)
15
e=int(e)
16
g=int(g)
17
enc=int(enc)
18
print(N)
19
print(e)
20
print(g)
21
print(enc)
22

23
nbits = 2048
24
gamma = 0.244
25
cbits = ceil(nbits * (0.5 - 2 * gamma))
26

27
M = (N - 1) // (2 * g)
28
u = M // (2 * g)
29
v = M - 2 * g * u
30
GF = Zmod(N)
31
x = GF.random_element()
32
y = x ^ (2 * g)
33
# c的范围大概与N^(0.5-2*gamma)很接近
34
c = bsgs(y, y ^ u, ((2**(cbits-5)), (2**(cbits+5))))
35
ab = u - c
36
apb = v + 2 * g * c
37
P.<x> = ZZ[]
38
f = x ^ 2 - apb * x + ab
39
a = f.roots()
40
if a:
41
    a, b = a[0][0], a[1][0]
42
    p = 2 * g * a + 1
43
    q = 2 * g * b + 1
44
    assert p * q == N
45
    print(p)
46
    print(q)
47
    phi=(p-1)*(q-1)
48
    d=gmpy2.invert(e,phi)
49
    m=pow(enc,d,N)
50
    print(long_to_bytes(m))

因为bsgs现在很慢，几乎被抛弃了，可以使用discrete_log_lambda,大概三秒跑出flag。

apbq#

task

1
from Crypto.Util.number import *
2
from secrets import flag
3
from math import ceil
4
import sys
5

6
class RSA():
7
    def __init__(self, privatekey, publickey):
8
        self.p, self.q, self.d = privatekey
9
        self.n, self.e = publickey
10

11
    def encrypt(self, plaintext):
12
        if isinstance(plaintext, bytes):
13
            plaintext = bytes_to_long(plaintext)
14
        ciphertext = pow(plaintext, self.e, self.n)
15
        return ciphertext
16

17
    def decrypt(self, ciphertext):
18
        if isinstance(ciphertext, bytes):
19
            ciphertext = bytes_to_long(ciphertext)
20
        plaintext = pow(ciphertext, self.d, self.n)
21
        return plaintext
22

23
def get_keypair(nbits, e = 65537):
24
    p = getPrime(nbits//2)
25
    q = getPrime(nbits//2)
26
    n = p * q
27
    d = inverse(e, n - p - q + 1)
28
    return (p, q, d), (n, e)
29

30
if __name__ == '__main__':
31
    pt = './output.txt'
32
    fout = open(pt, 'w')
33
    sys.stdout = fout
34

35
    block_size = ceil(len(flag)/3)
36
    flag = [flag[i:i+block_size] for i in range(0, len(flag), block_size)]
37
    e = 65537
38

39
    print(f'[+] Welcome to my apbq game')
40
    # stage 1
41
    print(f'┃ stage 1: p + q')
42
    prikey1, pubkey1 = get_keypair(1024)
43
    RSA1 = RSA(prikey1, pubkey1)
44
    enc1 = RSA1.encrypt(flag[0])
45
    print(f'┃ hints = {prikey1[0] + prikey1[1]}')
46
    print(f'┃ public key = {pubkey1}')
47
    print(f'┃ enc1 = {enc1}')
48
    print(f'----------------------')
49

50
    # stage 2
51
    print(f'┃ stage 2: ai*p + bi*q')
52
    prikey2, pubkey2 = get_keypair(1024)
53
    RSA2 = RSA(prikey2, pubkey2)
54
    enc2 = RSA2.encrypt(flag[1])
55
    kbits = 180
56
    a = [getRandomNBitInteger(kbits) for i in range(100)]
57
    b = [getRandomNBitInteger(kbits) for i in range(100)]
58
    c = [a[i]*prikey2[0] + b[i]*prikey2[1] for i in range(100)]
59
    print(f'┃ hints = {c}')
60
    print(f'┃ public key = {pubkey2}')
61
    print(f'┃ enc2 = {enc2}')
62
    print(f'----------------------')
63

64
    # stage 3
65
    print(f'┃ stage 3: a*p + q, p + bq')
66
    prikey3, pubkey3 = get_keypair(1024)
67
    RSA3 = RSA(prikey3, pubkey3)
68
    enc3 = RSA2.encrypt(flag[2])
69
    kbits = 512
70
    a = getRandomNBitInteger(kbits)
71
    b = getRandomNBitInteger(kbits)
72
    c1 = a*prikey3[0] + prikey3[1]
73
    c2 = prikey3[0] + b*prikey3[1]
74
    print(f'┃ hints = {c1, c2}')
75
    print(f'┃ public key = {pubkey3}')
76
    print(f'┃ enc3 = {enc3}')

part1#

已知 $pq=n,p+q=hints$ ,直接利用sympy解方程就可以了 exp

1
c=
2
pq =
3
n=
4
e=65537
5

6
from Crypto.Util.number import *
7
from sympy import*
8

9
p, q = symbols('p q')
10
eq1 = Eq(p+q, pq)
11
eq2 = Eq(p*q, n)
12
sol = solve((eq1, eq2), (p, q))
13
print(sol)
14

15
p=
16
q=
17
phi=(p-1)*(q-1)
18
d = inverse(e, phi)
19
m = pow(c, d, n)
20
print(long_to_bytes(m))

part2#

已知 $h=ap+bq$ ,而且有一百组，pq都是512bits，而ab是180bits，有这样小的数，我们就可以想到用格，因为自己太菜，直接找到了ductf2023年的exp，改成一百组，就直接出来了（好像四组就行） exp

1
import itertools
2
from Crypto.Util.number import long_to_bytes, GCD
3
from sage.all import Matrix, ZZ, QQ, ideal
4

5
hints =
6

7
n =
8
e = 65537
9
c =
10

11
V = hints
12
k = 2**400
13
M = Matrix.column([k * v for v in V]).augment(Matrix.identity(len(V)))
14
B = [b[1:] for b in M.LLL()]
15
M = (k * Matrix(B[:len(V)-2])).T.augment(Matrix.identity(len(V)))
16
B = [b[-len(V):] for b in M.LLL() if set(b[:len(V)-2]) == {0}]
17

18
for combination in itertools.product(range(101), repeat=2):
19
    T = combination[0] * B[0] + combination[1] * B[1]
20
    a = T[:len(V)]
21
    kq = GCD(a[1] * hints[0] - a[0] * hints[1], n)
22
    if 1 < kq < n:
23
        print('find!', kq, combination[0], combination[1])
24
        break
25

26
for i in range(2**16, 1, -1):
27
    if kq % i == 0:
28
        kq //= i
29
q = int(kq)
30
p = int(n // kq)
31
print(p, q)

part3#

写了一个小时，然后发现用的第二组密钥加密的，真的难崩正确写法可以参考这个帖子

21step#

task

1
import re
2
import random
3
from secrets import flag
4
print(f'Can you weight a 128 bits number in 21 steps')
5
pattern = r'([AB]|\d+)=([AB]|\d+)(\+|\-|\*|//|<<|>>|&|\^|%)([AB]|\d+)'
6

7
command = input().strip()
8
assert command[-1] == ';'
9
assert all([re.fullmatch(pattern, i) for i in command[:-1].split(';')])
10

11
step = 21
12
for i in command[:-1].split(';'):
13
    t = i.translate(str.maketrans('', '', '=AB0123456789'))
14
    if t in ['>>', '<<', '+', '-', '&', '^']:
15
        step -= 1
16
    elif t in ['*', '/', '%']:
17
        step -= 3
18
if step < 0:exit()
19

20
success = 0
21
w = lambda x: sum([int(i) for i in list(bin(x)[2:])])
22
for _ in range(100):
23
    A = random.randrange(0, 2**128)
24
    wa = w(A)
25
    B = 0
26
    try : exec("global A; global B;" + command)
27
    except : exit()
28
    if A == wa:
29
        success += 1
30

31
if success == 100:
32
    print(flag)

思路：很直接的题目，一个128bits的数，在21步算出他二进制中一的数量，直接找到Integer的类型源码，改成128位就好了

exp

1
from pwn import *
2

3
io = remote('39.107.90.219', 22677)
4
command = 'B=A>>1;B=B&113427455640312821154458202477256070485;A=A-B;B=A>>2;B=B&68056473384187692692674921486353642291;A=A&68056473384187692692674921486353642291;A=A+B;B=A>>4;A=A+B;A=A&20016609818878733144904388672456953615;B=A>>8;A=A+B;B=A>>16;A=A+B;B=A>>32;A=A+B;B=A>>64;A=A+B;A=A&127;'
5
io.recvuntil(b'Can you weight a 128 bits number in 21 steps')
6
for i in range(100):
7
    io.sendline(command)
8

9
io.recvline()
10
io.interactive()

总结#

没有爆零！！！其他的慢慢复现更新

a ctfer on the load

前言#

题目#

EzRsa#

apbq#

part1#

part2#

part3#

21step#

总结#