21Feb1


huangx607087开学前的切题1

0.简介

一个密码学fw的切题笔记,很菜,别看

今天BUUCTF上到了2500分,Crypto榜,会解比较简单的格密码学的题目了。同时椭圆曲线的内容也看了一些。BUU上刷了几题,不过因为是深水区,都是非常难的大题目,看来自己CTF的水平还是有一定差距的(

1.[CISCN2018]sm

按照惯例应该先阅读一下题目,可以看出BUUCTF的深水区的题目都是非常难的,代码长度也相比于以前增加了很多。

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
from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
from Crypto.Cipher import AES
import hashlib
from random import randint
def gen512num():
order=[]
while len(order)!=512:
tmp=randint(1,512)
if tmp not in order:
order.append(tmp)
ps=[]
for i in range(512):
p=getPrime(512-order[i]+10)
pre=bin(p)[2:][0:(512-order[i])]+"1"
ps.append(int(pre+"0"*(512-len(pre)),2))
return ps
def run():
choose=getPrime(512)
ps=gen512num()
print "gen over"
bchoose=bin(choose)[2:]
r=0
bchoose = "0"*(512-len(bchoose))+bchoose
for i in range(512):
if bchoose[i]=='1':
r=r^ps[i]
flag=open("flag","r").read()
key=long_to_bytes(int(hashlib.md5(long_to_bytes(choose)).hexdigest(),16))
aes_obj = AES.new(key, AES.MODE_ECB)
ef=aes_obj.encrypt(flag).encode("base64")
open("r", "w").write(str(r))
open("ef","w").write(ef)
gg=""
for p in ps:
gg+=str(p)+"\n"
open("ps","w").write(gg)
run()

题目中给出了$r$这个数字的值,还给出了ps这个序列,当然还有加密后的flag。

题目的意思很简单,就是生成了一个素数$p$,然后把素数$p$的二进制表示出来,并且生成了$512$个数字。如果$p$的那个比特位是$1$那就把$r$异或一下ps序列中的值。最后,$r$的值就是对应$p$的$1$比特位上的那个pr值得异或和。

因此,我们首要的任务就是求$p$。而想要求$p$,就需要求出$r$是哪些pr值的和。

打开给出的pr,简单扫一眼,发现全是偶数(实际上仔细看的话,里面有且仅有一个奇数),说明了pr生成有玄机。再看一眼:原来生成数字的时候,先生成了一个$1$到$512$的一个排列,然后生成的那个数字,满足其最低位的那个比特位$1$,恰好是从右往左数对应排列的那个数字。

所以,我们就要计算出pr中所有数字的最低的$1$比特位所代表的数字,并对其取对数$\log_2$然后整数化。这样我们就可以得到一个$0-511$的一个序列。作为一个oier,我想起了以前oi时期用上的那个lowbit函数

得到对应的$0-511$序列之后,然后我们就可以计算异或和了。

自己的exp第一部分多了两个数组:endexnum,endexid(注:index怕撞库函数名,因此改成了endex)用于求排列的逆,数组$s$是用于计算排列的。比如:假如s[15]=334,那么有endexid[334]=15,且endexnum[334]对应的那个数的lowbit值为$15$。这样可以避免后期用for循环查找,比较省时间,虽然CTF对于时间的限制没有OI那么严格

因此,我们可以从$0$开始,判断$r$是否和$\log_2 \mathrm{lowbit}(x)=0$的那个$x$值异或过了。根据异或计算的性质,我们可以很快完成后面的计算过程。

很快我们就解出了一个$p$,看到它是奇数,验证了一下,发现竟然不是素数。回顾自己的解题过程,发现异或开始时对应的$p$值是最高位,而我却把它当成了最低位计算。调整后,发现重新结出来的$p$是个素数,那么考虑到大数中出现素数的概率并不高,因此可以认为是正确的。

最后就是正常的解密,直接模仿题目给的内容即可。

个人做题有个习惯,就是喜欢把题目给出的一些特别长的list放到另一个python文件中,在exp里面直接import

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from math import log2
from base64 import *
from hashlib import md5
from pslist import ps
from r import r
from ef import ef
def lowbit(x):
return x&(-x)
s=[]
endexnum,endexid=[0]*512,[0]*512
for i in range(512):
s.append(int(log2(lowbit(ps[i]))))
endexnum[s[-1]]=ps[i]
endexid[s[-1]]=i
kount=0
xored=[]
for i in range(512):
tmp1,tmp2=(r>>i)&1,(kount>>i)&1
if tmp1^tmp2:
xored.append(i)
kount^=endexnum[i]
p=0
for i in xored:
p+=(1<<(511-endexid[i]))
key=long_to_bytes(int(md5(long_to_bytes(p)).hexdigest(),16))
aes_obj = AES.new(key, AES.MODE_ECB)
ef=b64decode(ef)
ef=aes_obj.decrypt(ef)
print(ef)

然后我们就拿到了最后的flag:flag{shemir_alotof_in_wctf_fun!}

2.[Zer0pts2020]ROR

先看一下题目

1
2
3
4
5
6
7
8
9
10
11
12
import random
from secret import flag
ror = lambda x, l, b: (x >> l) | ((x & ((1<<l)-1)) << (b-l))
N = 1
for base in [2, 3, 7]:
N *= pow(base, random.randint(123, 456))
e = random.randint(271828, 314159)
m = int.from_bytes(flag, byteorder='big')
assert m.bit_length() < N.bit_length()
for i in range(m.bit_length()):
print(pow(ror(m, i, m.bit_length()), e, N))

一开始不知道ror究竟是个什么,自己写了个程序测试了一下,原来是将$x$循环左移$l$位,总字节数为$b$。

这道题乍一看以为是个RSA加密,但是根本不知道$N,e$的值,并且仅根据题目给出来的线索是根本求不出来的。不过还是能注意到$N$是个偶数,而一个数如果对一个偶数取模,那么其奇偶性不变。而乘方运算是不改变一个数字的奇偶性的。所以这道题给出的数字中,每个数字都泄露了明文的最后一个比特位,拼接起来就是flag。

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
s,i=0,0
fp=open("chall.txt","r")
while True:
try:
a=int(fp.readline())&1
s+=(a<<i)
i=i+1
except:
break
print(long_to_bytes(s))

zer0pts{0h_1t_l34ks_th3_l34st_s1gn1f1c4nt_b1t}

3.[羊城杯 2020]Power

PART 1

如果说前面两道题还算比较简单的,个人认为BUUCTF上从这道题开始,就是真正的硬核了。

首先看一下题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
import gmpy2
from secret import flag
p = getPrime(512)
q = getPrime(512)
n = p**4*q
e = 0x10001
phi = gmpy2.lcm(p - 1, q - 1)
d = gmpy2.invert(e, phi)
dp = d % (p - 1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print "dp = " + str(dp)
print "c = " + str(c)
y = #略去 *
g = 2
x = 2019*p**2 + 2020*p**3 + 2021*p**4
c1 = pow(g, x, y)
print "c1 = " + str(c1)
#最后给出了dp,c,c1的值。

题目代码较短但这并不意味着题目容易解出来。大致看了一下加密过程,我们应当先设法求出$p$。(不过$N$一直是未知的)。而想要求出$p$,就要尝试求出$x$。

首先,我们就是要解决一个离散对数问题。我们发现$y$是一个素数,因此我们尝试分解$y-1$,发现其大概是$100$万的光滑。

3

然后就可以使用我在离散对数笔记里提到的那个脚本解了。不过发现太难解了,跑了半小时,五分之一进度都没跑到。查了一下Sagemath的使用手册,发现可以这样做,用时40秒左右。

4

这样我们就解出了$x$。

解出$x$之后,由于$2021p^4+2020p^3+2019p^2-x=0$。这个关于$p$的函数具有单调性,因此我们可以使用OI中讲过的二分答案的方式解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from valc import C
def f(x):
return 2021*x**4+2020*x**3+2019*x**2-C
L,R=0,1<<5120
while L<=R:
M=(L+R)//2
if(f(M)>0):
R=M
elif(f(M)<0):
L=M
elif(f(M)==0):
print(M)
break
print(hex(L),hex(R))
for i in range(3):
input()

解出$p$之后,知道了$d_p$,查阅资料,可以用这样的算法解决,这个代码也是在已知$d_p,p$和$n$的结构为$p^kq$类型的求$m$方法。

5

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
from given import p,c,dp,e
mp1=pow(c,dp,p)
mp=pow(c,dp-1,p)
for i in range(2):
x=(c-pow(mp1,e))%(p**(i+1))
y=x*mp1*inverse(e,p)%(p**(i+1))
mp1+=y
print(long_to_bytes(mp1))

4.[watevrCTF 2019]Baby RLWE

PART 1

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
#Sagemath Ver 9.0
from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler as d_gauss
flag = bytearray(raw_input())
flag = list(flag)
n = len(flag)
q = 40961
## Finite Field of size q.
F = GF(q)
## Univariate Polynomial Ring in y over Finite Field of size q
R.<y> = PolynomialRing(F)
## Univariate Quotient Polynomial Ring in x over Finite Field of size 40961 with modulus b^n + 1
S.<x> = R.quotient(y^n + 1)
def gen_small_poly():
sigma = 2/sqrt(2*pi)
d = d_gauss(S, n, sigma)
return d()
def gen_large_poly():
return S.random_element()
## Public key 1
a = gen_large_poly()
## Secret key
s = S(flag)
file_out = open("downloads/public_keys.txt", "w")
file_out.write("a: " + str(a) + "\n")
for i in range(100):
## Error
e = gen_small_poly()
## Public key 2
b = a*s + e
file_out.write("b: " + str(b) + "\n")
file_out.close()

这道题直接就给出的是Sagemath里的应用。题目给出的数据是一个多项式$a(x)$,和$100$个多项式$b(x)$。仔细观察一下发现$b(x)$对应次数接近。初步判定$n=104$。

gen_large_poly()函数是在多项式环里随机选取一个元素,这个不难理解。不过最后不知道gen_small_poly()究竟讲的什么,不过我们可以把它放到Sagemath中试验一下

1

我们发现它生成的多项式的系数基本上在$[-2,2]$之间,说明最后加上的小多项式$e(x)$的每一项基本上也都是在$[-2,2]$之间。并且发现小多项式里面$0$是可取的。说明我们有可能只需要统计一下$b(x)$中对应次数哪个系数出现得最多,就说明原来的$b(x)$的值了。

因此,我们首先统计一下给出来的$100$个$b(x)$多项式值得情况,最终可以确定真正的$b(x)$。

确定$b(x)$之后,我们就可以求出$s(x)=a^{-1}(x)b(x)$,进而拿到了flag。

2

PART 2 扩展阅读内容

(1) 什么是后量子密码

上面这道题就这样结束了,那么RLWE究竟是个什么东西呢?来了解下:

后量子密码,作为未来 5-10 年逐渐代替 RSA、Diffie-Hellman、椭圆曲线等现行公钥密码算法的密码技术,正被越来越多的人所重视。本文是后量子密码科普专栏的第三篇。文中对基于格问题 (Ring Learning with Errors, RLWE) 的后量子密钥交换算法的原理进行介绍。

因此,这个问题得原理需要用到格。关于格密码学的基础内容,可以回顾我刚写的格密码笔记1到5

(2)LWE、RLWE

1996 年Ajtai 给出了格中困难问题从最坏情况到平均情况的规约证明。密码学中的困难性需要的是在 “平均情况” 下的困难性。Ajtai 的工作使得基于格问题构造的密码方案具有了可证明安全的性质。新的格困难问题中,有几种重要的平均情况困难的问题:SIS、LWE、RLWE 及变种。在一定的参数设定下,这些问题可以归约到 GapSVP、SIVP 等格上的困难问题(即求解这些问题并不比求解格上困难问题容易)。

下面介绍这几个问题的定义:

S1

太抽象了,我看不懂

说的简单一点,就是写出一个形如$as+e=b$的形式,其中$a,b$是均匀随机的内容,$s$是私钥,$e$是一个服从某种分布的随机扰动项。

一般情况下,会选取矩阵$A$,列向量$\vec s,\vec e,\vec b$。不过由于选取矩阵的开销太大,有时候还会选取多项式$n$次多项式$x^n+1$,素数域$GF(p)$,计算$a(x)s(x)+e(x)=b(x)$

(3)关于消除扰动项

S2

S3

S4

S5

如果上面的内容过于复杂引起不适,建议结束阅读。

5.总结

BUUCTF深水区的题目,都是非常难的题目,而这些题目也是大赛里面的题目,很有学习价值的,能学到很多心得加密过程和算法(。

不过自己一直都是个mmxfw,因为自己太菜了,哎(


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