21Jan1


huangx607087寒假的切题1

0x00 简介

一个密码学废物的寒假切题记录的exp,别看,贼菜

近期BUUCTF的分数上到了500分,不过目前的形式依然很严峻,与我同级的一个人比我强很多,而我却在这里补基础,感觉校队里同一级除web方向的人不可同时存在2个及以上,压力还是非常大的

#define huangx607087 yongyuandefeiwu

0x01 ECC & RSA

这是一道结合了离散对数和椭圆曲线的密码体系,我们可以先看一下加密代码和题目所给出的的各种数据。

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
from fastecdsa.curve import P521 as Curve
from fastecdsa.point import Point
from Crypto.Util.number import bytes_to_long, isPrime
from os import urandom
from random import getrandbits
def gen_rsa_primes(G):
urand = bytes_to_long(urandom(521//8))
while True:
s = getrandbits(521) ^ urand
Q = s*G
if isPrime(Q.x) and isPrime(Q.y):
print("ECC Private key:", hex(s))
print("RSA primes:", hex(Q.x), hex(Q.y))
print("Modulo:", hex(Q.x * Q.y))
return (Q.x, Q.y)
flag = int.from_bytes(input(), byteorder="big")
ecc_p = Curve.p
a = Curve.a
b = Curve.b
Gx = Curve.gx
Gy = Curve.gy
G = Point(Gx, Gy, curve=Curve)
e = 0x10001
p, q = gen_rsa_primes(G)
n = p*q
file_out = open("downloads/ecc-rsa.txt", "w")
file_out.write("ECC Curve Prime: " + hex(ecc_p) + "\n")
file_out.write("Curve a: " + hex(a) + "\n")
file_out.write("Curve b: " + hex(b) + "\n")
file_out.write("Gx: " + hex(Gx) + "\n")
file_out.write("Gy: " + hex(Gy) + "\n")
file_out.write("e: " + hex(e) + "\n")
file_out.write("p * q: " + hex(n) + "\n")
c = pow(flag, e, n)
file_out.write("ciphertext: " + hex(c) + "\n")
'''
ECC Curve Prime: 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Curve a: -0x3
Curve b: 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00
Gx: 0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66
Gy: 0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650
e: 0x10001
p * q: 0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f
ciphertext: 0x3862c872480bdd067c0c68cfee4527a063166620c97cca4c99baff6eb0cf5d42421b8f8d8300df5f8c7663adb5d21b47c8cb4ca5aab892006d7d44a1c5b5f5242d88c6e325064adf9b969c7dfc52a034495fe67b5424e1678ca4332d59225855b7a9cb42db2b1db95a90ab6834395397e305078c5baff78c4b7252d7966365afed9e
'''

我们通过上面的加密过程可以发现:$(p,q)$实际上是椭圆曲线$y^2=x^3+ax+b$上面的点,所以我们可以有一个等式为$q^2=p^3+ap+b$,加上RSA中的等式$n=pq$,两边平方后带入$q^2$表达式为$n^2=p^5+ap^3+bp^2$,然后用以下的sagemath代码即可,注意求解多项式的根应该是$f=0$的根,所以最后要减去一个$n^2$,把方程化成$p^5+ap^3+bp^2-n^2=0$

1-1

最后求出来$3$个解,很显然,由于RSA中$p$是素数,那么只有第二个解符合题意。此时$n$就被分解成功,进而我们就很快地能够解密了。

下面附上一些Sagemath中对密码学有关的函数供以后查阅

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#整数域,有理数域和实数域
ZZ(3)
QQ(0.25)
RR(2^0.5)
#复数域
CC(1,2)
#生成虚数单位i
i=ComplexField().gen();(2+i)*(4+3*i)
#构造多项式环,返回具有给定属性和变量名的全局唯一的单变量或多元多项式环
#定义在整数域上的多项式环R,变量为w;ZZ也可换成其他数域
R.<w>=PolynomialRing(ZZ);R
(1 + w)^3
#有限环
RN=IntegerModRing(63)
FR=Integers(17);FR
#自身的代数扩展;exR=FR[w]/(w^2+3)
exR=FR.extension(w^2+3);exR
#以python整数的形式返回所有可逆元素的列表
FR.list_of_elements_of_multiplicative_group()
#假设环的乘法群是循环的,返回这个环的乘法群的生成元
FR.multiplicative_generator()
#返回这个环的一个随机元素
FR.random_element()
#上述几种方法对如下的域同样支持
#有限域
#素数域
G1=GF(37);G1
#伽罗瓦域
G2=GF(3^5);G2
#同时求商与余数
q,r=divmod(12,5)
#求公约数
d=gcd(12,5)
#扩展的欧几里得算法
d,u,v=xgcd(12,5)
#12在模5下的逆
u=inverse_mod(12,5)
#生成[lb,ub)之间的随机素数,注意ub在前,lb在后,lb可缺省为0
#可通过这种方式生成128位的随机素数
p=random_prime(2L**128,2L**127)
#判断是否为素数
is_prime(65537)
#第20个素数
nth_prime(20)
#计算x^y mod n
z=power_mod(12,5,17)
#欧拉函数
euler_phi(111)
#中国剩余定理,A=[a1,...,an],M=[m1,...,mn]
#ai=x mod mi,i=1,...,n
crt([1,2,3,4],[7,5,12,23])
#求自身的n次根
FR(12).nth_root(7,all='True')
#求多项式的根,roots方法必须作用在域上
R.<x>=PolynomialRing(G1)
xt=G1(12)
yt=xt^6
f=x^6-yt
f.roots()
#定义矩阵,默认定义在实数域
A = matrix([[1,2,3,5],[3,2,1,2],[1,1,1,0],[3,7,2,2]])
A^-1
#定义在其他域上的矩阵,如有限域
A = matrix(GF(13),[[1,2,3,5],[3,2,1,2],[1,1,1,0],[3,7,2,2]])
A^-1
#可以看到两个逆矩阵不一样
#定义向量,定义在有限域,默认定义在实数域
w = vector(GF(13),[1,1,4,3])
Y=A*w;Y
Z=w*A;Z
#解线性方程组AX=Y
X = A.solve_right(Y);X
#也可以使用符号\
A\Y
#解线性方程组XA=Y
X = A.solve_left(Z);X
#格基约减
A = matrix([[1,2,3,5],[3,2,1,2],[1,1,1,0],[3,7,2,2]])
#LLL算法
A.LLL()
#BKZ算法
A.BKZ()
p=ZZ('FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF',16)
a=ZZ('FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC',16)
b=ZZ('28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93',16)
#有限域GF(p)上的椭圆曲线y^2 = x^3 + a*x + b mod p
E=EllipticCurve(GF(p),[0,0,0,a,b])
#基点
g=E([ZZ('32c4ae2c1f1981195f9904466a39c9948fe30bbff2660be1715a4589334c74c7',16),ZZ('bc3736a2f4f6779c59bdcee36b692153d0a9877cc62a474002df32e52139f0a0',16)])
#基点的阶
n=ZZ('FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123',16)
#生成密钥
sk=random_prime(2*n//3,n//3)
#生成公钥
G=sk*g
#通用的求离散对数的方法
x=discrete_log(a,base,ord,operation)
#求离散对数的Pollard-Rho算法
x=discrete_log_rho(a,base,ord,operation)
#求离散对数的Pollard-kangaroo算法(也称为lambda算法)
x=discrete_log_lambda(a,base,bounds,operation)
#小步大步法
x=bsgs(base,a,bounds,operation)

2.[*ctf]little case&[NCTF2019]easyRSA

这两道题都是涉及到了RSA中$\gcd(p-1,q-1,e)=e$的情况,直接查阅RSA Notes 3中的相关内容即可,此处不再赘述。

3.[NPUCTF2020]Mersenne twister

一道梅森旋转题,还是先看一下题目

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 hashlib import *
from itertools import *
from binascii import hexlify , unhexlify
from flag import flag ,seed
assert len(flag) == 26
assert flag[:7] == 'npuctf{'
assert flag[-1] == '}'
XOR = lambda s1 ,s2 : bytes([x1 ^ x2 for x1 ,x2 in zip(s1 , s2)])
class mt73991:
def __init__(self , seed):
self.state = [seed] + [0] * 232
self.flag = 0
self.srand()
self.generate()
def srand(self):
for i in range(232):
self.state[i+1] = 1812433253 * (self.state[i] ^ (self.state[i] >> 27)) - i
self.state[i+1] &= 0xffffffff
def generate(self):
for i in range(233):
y = (self.state[i] & 0x80000000) | (self.state[(i+1)%233] & 0x7fffffff)
temp = y >> 1
temp ^= self.state[(i + 130) % 233]
if y & 1:
temp ^= 0x9908f23f
self.state[i] = temp
def getramdanbits(self):
if self.flag == 233:
self.generate()
self.flag = 0
bits = self.Next(self.state[self.flag]).to_bytes(4 , 'big')
self.flag += 1
return bits
def Next(self , tmp):
tmp ^= (tmp >> 11)
tmp ^= (tmp << 7) & 0x9ddf4680
tmp ^= (tmp << 15) & 0xefc65400
tmp ^= (tmp >> 18) & 0x34adf670
return tmp
def encrypt(key , plain):
tmp = md5(plain).digest()
return hexlify(XOR(tmp , key))
if __name__ == "__main__":
flag = flag.encode()
random = mt73991(seed)
f = open('./cipher.txt' , 'wb')
for i in flag:
key = b''.join([random.getramdanbits() for _ in range(4)])
cipher = encrypt(key , chr(i).encode())
f.write(cipher)

这道题目与之前我博客里的**PRNG MT Notes[2020.10.26]**所涉及到的题目基本一致,只不过是将密文中的每一位的md5值与生成的随机值进行异或。我们还是只需要求出Next函数的逆即可(那篇博客也提供了对应方法,简单调参即可使用)。

不过问题是我们无法知道完全的$233$个状态,只能得知我们仅有的$104$个状态。其中一个办法就是枚举seed,枚举规模约为$43$亿,实际上跑了$16$亿多一些。(不过好像可以不用枚举seed,具体方法待更新)

4.[ACTF新生赛2020]crypto-aes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Cryptodome.Cipher import AES
import os
import gmpy2
from flag import FLAG
from Cryptodome.Util.number import *

def main():
key=os.urandom(2)*16
iv=os.urandom(16)
print(bytes_to_long(key)^bytes_to_long(iv))
aes=AES.new(key,AES.MODE_CBC,iv)
enc_flag = aes.encrypt(FLAG)
print(enc_flag)
if __name__=="__main__":
main()

一道AES题目,我们可以看出key是$8$组$4$位$16$进制数,我们只需要把他给出来的第一个异或结果拿出来并输出$16$进制,发现前面是$4$组$\text{C981}_h$,而后面是不规则内容。我们只需要把不规则内容用$4$组$\text{C981}_h$进行异或即可。这样我们的key和iv就都拿到了

最后我们只需要模仿他的模式,即可解出flag了

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
from Crypto.Cipher import AES
iv=b'\x87lQbI0\xfc\xe6\xaa\x05P\xb1\x01\xd1pL'
cip=b'\x8c-\xcd\xde\xa7\xe9\x7f.b\x8aKs\xf1\xba\xc75\xc4d\x13\x07\xac\xa4&\xd6\x91\xfe\xf3\x14\x10|\xf8p'
key=long_to_bytes(0xc981c981c981c981c981c981c981c981c981c981c981c981c981c981c981c981)
aes=AES.new(key,AES.MODE_CBC,iv)
dec_flag = aes.decrypt(cip)
print(dec_flag)

5.[*ctf]GuessFlag(1)(2)

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
from random import randint
import os
from flag import flag
N=64
key=randint(0,2**N)
# print key
key=bin(key)[2:].rjust(N,'0')
count=0
while True:
p=0
q=0
new_key=''
zeros=[0]
for j in range(len(key)):
if key[j]=='0':
zeros.append(j)
p=zeros[randint(0,len(zeros))-1]
q=zeros[randint(0,len(zeros))-1]
try:
mask=int(raw_input("mask:"))
except:
exit(0)
mask=bin(mask)[2:]
if p>q:
tmp=q
q=p
p=tmp
cnt=0
for j in range(0,N):
if j in range(p,q+1):
new_key+=str(int(mask[cnt])^int(key[j]))
else:
new_key+=key[j]
cnt+=1
cnt%=len(mask)
key=new_key
try:
guess=int(raw_input("guess:"))
except:
exit(0)
if guess==int(key,2):
count+=1
print 'Nice.'
else:
count=0
print 'Oops.'
if count>2:
print flag

题目的意思很简单,服务器会保留一个随机的$64$位整数,并记录下所有的$0$位。你每次向服务器发送一个数字,然后服务器会任意选取已有密钥中$2$个$0$比特位,并将这$2$个$0$比特位之间的所有比特位依次循环异或你所发送数字的各个比特位。连续$3$次猜中密钥即可获得答案

一开始print(flag)是给出的,这次只需要发送三次$0$,这样密钥就保持不变,然后每次猜就猜他给出来的那个数,然后就可以获取flag

不过后面升级了,print(flag)这句话被删除了,这个时候就要想办法了我这个fw还问了学长,所以我自己果然是个fw。这个时候,我们只需要每次发送$1$,这样任意两个$0$之间的所有比特位都有可能被异或。不过我们多次本地实验后会发现:随着发送$1$的次数不断增多,密钥末尾的固定$1$比特位的长度越来越长,所以只需要不到$200$次的发送$1$,最后$64$个比特位就会全是$1$。所以我们每次猜密钥都猜$18446744073709551615$,也就是$2^{64}-1$,到最后就会连续$3$次猜中,最终我们就肯伊拿到flag

(这两道脑洞题个人认为质量还是挺高的,谁叫自己是个fw呢)


文章作者: huangx607087
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 huangx607087 !
  目录