前言
一共七题，出了三个，但是海鲜市场上面已经py烂了，我该喜还是该忧呢？在这里就只写上自己已经出了的题，其他的慢慢复现，最近期中考试+香港比较忙。
题目
EzRsa
task
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
|
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import random, gmpy2
class RSAEncryptor:
def __init__(self):
self.g = self.a = self.b = 0
self.e = 65537
self.factorGen()
self.product()
def factorGen(self):
while True:
self.g = getPrime(500)
while not gmpy2.is_prime(2*self.g*self.a+1):
self.a = random.randint(2**523, 2**524)
while not gmpy2.is_prime(2*self.g*self.b+1):
self.b = random.randint(2**523, 2**524)
self.h = 2*self.g*self.a*self.b+self.a+self.b
if gmpy2.is_prime(self.h):
self.N = 2*self.h*self.g+1
print(len(bin(self.N)))
return
def encrypt(self, msg):
return gmpy2.powmod(msg, self.e, self.N)
def product(self):
with open('/flag', 'rb') as f:
self.flag = f.read()
self.enc = self.encrypt(self.flag)
self.show()
print(f'enc={self.enc}')
def show(self):
print(f"N={self.N}")
print(f"e={self.e}")
print(f"g={self.g}")
RSAEncryptor()
|
思路：
重点代码是
$$ h=2gab+a+b $$
和
$$ N=2hg+1 $$
,我们讲
$$N$$
直接展开,其实就是
$$ N=(2ga+1)(2gb+1) $$
,这个就是老熟人了，Common Prime Rsa,可以参考独奏的文章，易知是
$$g
的类型,我们之间修改模板就行了。
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
|
from sage.groups.generic import bsgs
from Crypto.Util.number import *
from pwn import*
import gmpy2
from sympy import primerange
p=remote('47.94.226.70', 32973)
e=65537
N=p.recvline().decode().split('=')[1]
e=p.recvline().decode().split('=')[1]
g=p.recvline().decode().split('=')[1]
enc=p.recvline().decode().split('=')[1]
N=int(N)
e=int(e)
g=int(g)
enc=int(enc)
print(N)
print(e)
print(g)
print(enc)
nbits = 2048
gamma = 0.244
cbits = ceil(nbits * (0.5 - 2 * gamma))
M = (N - 1) // (2 * g)
u = M // (2 * g)
v = M - 2 * g * u
GF = Zmod(N)
x = GF.random_element()
y = x ^ (2 * g)
# c的范围大概与N^(0.5-2*gamma)很接近
c = bsgs(y, y ^ u, ((2**(cbits-5)), (2**(cbits+5))))
ab = u - c
apb = v + 2 * g * c
P.<x> = ZZ[]
f = x ^ 2 - apb * x + ab
a = f.roots()
if a:
a, b = a[0][0], a[1][0]
p = 2 * g * a + 1
q = 2 * g * b + 1
assert p * q == N
print(p)
print(q)
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(enc,d,N)
print(long_to_bytes(m))
|
因为bsgs现在很慢，几乎被抛弃了，可以使用discrete_log_lambda,大概三秒跑出flag。
apbq
task
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
|
from Crypto.Util.number import *
from secrets import flag
from math import ceil
import sys
class RSA():
def __init__(self, privatekey, publickey):
self.p, self.q, self.d = privatekey
self.n, self.e = publickey
def encrypt(self, plaintext):
if isinstance(plaintext, bytes):
plaintext = bytes_to_long(plaintext)
ciphertext = pow(plaintext, self.e, self.n)
return ciphertext
def decrypt(self, ciphertext):
if isinstance(ciphertext, bytes):
ciphertext = bytes_to_long(ciphertext)
plaintext = pow(ciphertext, self.d, self.n)
return plaintext
def get_keypair(nbits, e = 65537):
p = getPrime(nbits//2)
q = getPrime(nbits//2)
n = p * q
d = inverse(e, n - p - q + 1)
return (p, q, d), (n, e)
if __name__ == '__main__':
pt = './output.txt'
fout = open(pt, 'w')
sys.stdout = fout
block_size = ceil(len(flag)/3)
flag = [flag[i:i+block_size] for i in range(0, len(flag), block_size)]
e = 65537
print(f'[+] Welcome to my apbq game')
# stage 1
print(f'┃ stage 1: p + q')
prikey1, pubkey1 = get_keypair(1024)
RSA1 = RSA(prikey1, pubkey1)
enc1 = RSA1.encrypt(flag[0])
print(f'┃ hints = {prikey1[0] + prikey1[1]}')
print(f'┃ public key = {pubkey1}')
print(f'┃ enc1 = {enc1}')
print(f'----------------------')
# stage 2
print(f'┃ stage 2: ai*p + bi*q')
prikey2, pubkey2 = get_keypair(1024)
RSA2 = RSA(prikey2, pubkey2)
enc2 = RSA2.encrypt(flag[1])
kbits = 180
a = [getRandomNBitInteger(kbits) for i in range(100)]
b = [getRandomNBitInteger(kbits) for i in range(100)]
c = [a[i]*prikey2[0] + b[i]*prikey2[1] for i in range(100)]
print(f'┃ hints = {c}')
print(f'┃ public key = {pubkey2}')
print(f'┃ enc2 = {enc2}')
print(f'----------------------')
# stage 3
print(f'┃ stage 3: a*p + q, p + bq')
prikey3, pubkey3 = get_keypair(1024)
RSA3 = RSA(prikey3, pubkey3)
enc3 = RSA2.encrypt(flag[2])
kbits = 512
a = getRandomNBitInteger(kbits)
b = getRandomNBitInteger(kbits)
c1 = a*prikey3[0] + prikey3[1]
c2 = prikey3[0] + b*prikey3[1]
print(f'┃ hints = {c1, c2}')
print(f'┃ public key = {pubkey3}')
print(f'┃ enc3 = {enc3}')
|
part1
已知
$$pq=n,p+q=hints$$,直接利用sympy解方程就可以了
exp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
c=
pq =
n=
e=65537
from Crypto.Util.number import *
from sympy import*
p, q = symbols('p q')
eq1 = Eq(p+q, pq)
eq2 = Eq(p*q, n)
sol = solve((eq1, eq2), (p, q))
print(sol)
p=
q=
phi=(p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
|
part2
已知
$$h=ap+bq$$,而且有一百组，pq都是512bits，而ab是180bits，有这样小的数，我们就可以想到用格，因为自己太菜，直接找到了ductf2023年的exp，改成一百组，就直接出来了（好像四组就行）
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
|
import itertools
from Crypto.Util.number import long_to_bytes, GCD
from sage.all import Matrix, ZZ, QQ, ideal
hints =
n =
e = 65537
c =
V = hints
k = 2**400
M = Matrix.column([k * v for v in V]).augment(Matrix.identity(len(V)))
B = [b[1:] for b in M.LLL()]
M = (k * Matrix(B[:len(V)-2])).T.augment(Matrix.identity(len(V)))
B = [b[-len(V):] for b in M.LLL() if set(b[:len(V)-2]) == {0}]
for combination in itertools.product(range(101), repeat=2):
T = combination[0] * B[0] + combination[1] * B[1]
a = T[:len(V)]
kq = GCD(a[1] * hints[0] - a[0] * hints[1], n)
if 1 < kq < n:
print('find!', kq, combination[0], combination[1])
break
for i in range(2**16, 1, -1):
if kq % i == 0:
kq //= i
q = int(kq)
p = int(n // kq)
print(p, q)
|
part3
写了一个小时，然后发现用的第二组密钥加密的，真的难崩
正确写法可以参考这个帖子
21step
task
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
|
import re
import random
from secrets import flag
print(f'Can you weight a 128 bits number in 21 steps')
pattern = r'([AB]|\d+)=([AB]|\d+)(\+|\-|\*|//|<<|>>|&|\^|%)([AB]|\d+)'
command = input().strip()
assert command[-1] == ';'
assert all([re.fullmatch(pattern, i) for i in command[:-1].split(';')])
step = 21
for i in command[:-1].split(';'):
t = i.translate(str.maketrans('', '', '=AB0123456789'))
if t in ['>>', '<<', '+', '-', '&', '^']:
step -= 1
elif t in ['*', '/', '%']:
step -= 3
if step < 0:exit()
success = 0
w = lambda x: sum([int(i) for i in list(bin(x)[2:])])
for _ in range(100):
A = random.randrange(0, 2**128)
wa = w(A)
B = 0
try : exec("global A; global B;" + command)
except : exit()
if A == wa:
success += 1
if success == 100:
print(flag)
|
思路：很直接的题目，一个128bits的数，在21步算出他二进制中一的数量，直接找到Integer的类型源码，改成128位就好了
exp
1
2
3
4
5
6
7
8
9
10
|
from pwn import *
io = remote('39.107.90.219', 22677)
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;'
io.recvuntil(b'Can you weight a 128 bits number in 21 steps')
for i in range(100):
io.sendline(command)
io.recvline()
io.interactive()
|
总结
没有爆零！！！其他的慢慢复现更新
