前言
最近期中考试没怎么刷题来着，复现复现没参加的比赛吧～
题目
simpleSignin
task.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
from Crypto.Util.number import *
from gmpy2 import *
import os
flag = b'xxx'
p = next_prime(bytes_to_long(os.urandom(128)))
q = next_prime(bytes_to_long(os.urandom(128)))
r = next_prime(q)
n = p * q * r
e = 0x10001
print(f"n = {n}")
print(f"c = {pow(bytes_to_long(flag), e, n)}")
print(f"gift1 = {p % (2**10)}")
print(f"gift2 = {(p >> 20) % 2 ** 800}")
|
拿到题就知道这玩意是copper，好像比赛当天还有人在群里问来着，有点意思(，简单分析一下
gift1->低10位
gift2->右移20位后的低800位
我们可以认为已知了低820位，那10位可以爆破，那么前面直接copper求出
exp.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
n =
c =
gift1 = 513
gift2 =
e=65537
from Crypto.Util.number import *
PR.<x> = PolynomialRing(Zmod(n))
for i in range(2**10):
p_low = (gift2<<20)+(i<<10)+gift1
f = x*2**820+p_low
root = f.monic().small_roots(X=2^204,beta=0.33)
if root:
p = int(root[0]*2**820+p_low)
if n%p==0:
phi = p-1
d = inverse(e,phi)
m = pow(c,d,p)
flag=long_to_bytes(m)
print(flag)
break
|
NumberTheory
task.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
from Crypto.Util.number import *
import hint
flag=b'xxx'
e=65537
p=getPrime(512)
q=getPrime(512)
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
k=getPrime(1024)
assert hint + 233 * k == 233 * k * p
print(n)
print(c)
print(hint)
|
经典数论题
$$
hint=233k(p-1) \\
a^{hint}=a^{233k(p-1)} \mod p =1 \mod p \\
p=\gcd(a^{hint}-1,p)
$$
exp.py
1
2
3
4
5
6
7
8
9
10
11
12
13
|
from Crypto.Util.number import *
n=
c=
hint=
e = 65537
p = GCD(pow(2,hint,n)-1,n)
q = n//p
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)
|
easy_lwe
task.py
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 secrets import flag
assert len(flag) == 38
p = getPrime(512)
m = getPrime(512)
while m > p:
m = getPrime(512)
aa = []
cc = []
bb = []
for i in range(30):
a = getPrime(512)
b = getPrime(400)
c = (a * m + b) % p
aa.append(a)
cc.append(c)
bb.append(b)
enc = pow(m,flag,p)
print(f'p = {p}')
print(f'aa = {aa}')
print(f'cc = {cc}')
print(f'enc = {enc}')
|
part1是hnp问题，所以题目为什么叫lwe？直接用la佬的脚本就行了，微微改一下
part2是dlp问题，p-1是可分解的，经典Pohlig-Hellman，这里借鉴山石的思路，最后一个素数不用，而去爆破求解，效率更加快
exp.py
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
|
from Crypto.Util.number import *
p =
aa =
enc =
K = 2 ** 400
P = identity_matrix(30) * p
RC = matrix([[-1, 0], [0, 1]]) * matrix([aa, cc])
KP = matrix([[K / p, 0], [0, K]])
M = block_matrix([[P, 0], [RC, KP]], subdivide=False)
shortest_vector = M.LLL()
x = shortest_vector[1, -2] / K * p % p
print(x)
factors=[]#sage就能出来
dlogs = []
for fac in factors[:-1]:
t = (p - 1) // fac
dlog = discrete_log(G(pow(enc, t, p)), G(pow(x, t, p)))
dlogs += [dlog]
s = (p - 1) // factors[-1]
print(s)
res = crt(dlogs, factors[:-1])
for i in range(100):
if b'flag{'in long_to_bytes(res + i * s):
print(long_to_bytes(res + i * s))
break
|
easy_crypto
task.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
from secret import flag
from Crypto.Util.number import getPrime
flag = bin(int.from_bytes(flag, 'big'))[2:]
private_key = []
g = getPrime(10)
private_key.append(g)
for i in range(len(flag) - 1):
g = g * 2
private_key.append(g)
a = getPrime(20)
b = getPrime(len(flag) + 20)
public_key = []
for i in private_key:
public_key.append((a * i) % b)
print(public_key)
c = 0
for i in range(len(flag)):
c += int(str(flag)[i])*public_key[i]
print(c)
|
前面先套了个lcg，直接求出seed，后面就是背包
exp.py
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 *
#我是取的最后两组
y =
x =
public_key =
c =
b = 2*x - y
a = factor(public_key[0])[1][0]
private_key = []
for i in public_key:
private_key.append(int(i*pow(a,-1,b)%b))
c = c*pow(a,-1,b)%b
flag = ''
for i in private_key[::-1]:
if c >= i:
c -= i
flag = '1' + flag
else:
flag = '0' + flag
print(long_to_bytes(int(flag,2)))
|
总结
质量还好吧，感觉格还是不太熟，得多练练
