安恒五月月赛密码学wp

bbcrypto

手算salt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import inverse
import itertools
c = '177401504b0125272c122743171e2c250a602e3a7c206e014a012703273a3c0160173a73753d'

c = [int(c[i: i + 2], 16) for i in range(0, len(c), 2)]

salt = 'ahh'
m = ''
salt = itertools.cycle(salt)

for i in c:
m += chr((inverse(57, 128) * (i - ord(next(salt)))) % 128)
print(m)
>>> flag{ad7d973ffdd285b476a1a727b3a8fbc4}

easy LCG

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

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

def next(self):
self.seed = (self.a*self.seed+self.b) % self.m
return self.seed >> 16


g = 183096451267674849541594370111199688704
A = 102248652770540219619953045171664636108622486775480799200725530949685509093530
B = 74913924633988481450801262607456437193056607965094613549273335198280176291445
M = 102752586316294557951738800745394456033378966059875498971396396583576430992701
Cipher = 13040004482819935755130996285494678592830702618071750116744173145400949521388647864913527703

a = 3844066521
b = 3316005024
m = 2249804527
state1 = 16269
state2 = 4249


def gen_AB():
x = ''
for _ in range(64):
x += '1' if lcg.next() % 2 else '0'
return pow(g, int(x, 2), M), int(x, 2)

for i in tqdm(range(2 ** 16 - 1)):
seed = (state2 << 16) + i
lcg = LCG(seed)
tA, ta = gen_AB()
if tA == A:
break

tB, tb = gen_AB()
assert (tB == B)
key = pow(A, tb, M)
print(long_to_bytes(Cipher ^ key))
>>> b'flag{4dfe14e0c6c21ffcf5a3b4f0ed1911f6}'

knapsack

题目加密方式为私钥加密,属于NP问题,但是数列为超递增数列可以在多项式时间内求出

首先算出A,B从而算出私钥key1,其中key1为依次减小的序列.其中比赛时我把rn // 2**i看成了(rn // 2)**i所以一度陷入自我怀疑的状态

因为pub文件最后的数字很小我们可以直接因式分解得到其中较大的数检查是否为素数即可得到A,B由前两行相减,其中第一行乘二,再加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
from Crypto.Util.number import *
from tqdm import tqdm
with open('pub.txt', 'r') as f:
key2 = f.readlines()
key2 = [int(key2[i][:-1]) for i in range(len(key2))]

a = 11243098275181678343
b = 335428611041311731398614259824482604248524861615176787429946575184146370361110652887115402376826444538743339055691850202034085349274540292019392290484025358504275054761608502214481606484088807087063751542648223811793597463026662881020647708165593980984857948283181770647446888695205803952635117800114545071259

key1 = []
for i in key2:
key1.append((i * inverse(a, b)) % b)

cipher = 0x8ab3086a3df540d4652c191951756a6574aca491d933e479330532f0586ce03862f82f36dea8038b8bfb0b394331d7a93050efa2a26e46d9d8ca394600456cd79e02890a2c31b02e920c28a9f27c3943ec68fe5555ff4056358f35869859d67d67702edf44b10a7690acbaeea1f4def46392922069bfb71c173a210e9ab384f7
m = ''
for i in key1:
if cipher > i:
m += '1'
cipher -= i
else:
m += '0'
list(m).reverse()
m = ''.join(m)
print(long_to_bytes(int(m, 2)))

image-20200523165745879

image-20200523165720359

RC4_img

搁置

Backpacker

搁置

评论