huangx607087开学前的切题1
0.简介
一个密码学fw的切题笔记,很菜,别看
今天BUUCTF上到了2500分,Crypto榜,会解比较简单的格密码学的题目了。同时椭圆曲线的内容也看了一些。BUU上刷了几题,不过因为是深水区,都是非常难的大题目,看来自己CTF的水平还是有一定差距的(
1.[CISCN2018]sm
按照惯例应该先阅读一下题目,可以看出BUUCTF的深水区的题目都是非常难的,代码长度也相比于以前增加了很多。
1 | from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long |
题目中给出了$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 | from Crypto.Util.number import * |
然后我们就拿到了最后的flag:flag{shemir_alotof_in_wctf_fun!}
2.[Zer0pts2020]ROR
先看一下题目
1 | import random |
一开始不知道ror究竟是个什么,自己写了个程序测试了一下,原来是将$x$循环左移$l$位,总字节数为$b$。
这道题乍一看以为是个RSA加密,但是根本不知道$N,e$的值,并且仅根据题目给出来的线索是根本求不出来的。不过还是能注意到$N$是个偶数,而一个数如果对一个偶数取模,那么其奇偶性不变。而乘方运算是不改变一个数字的奇偶性的。所以这道题给出的数字中,每个数字都泄露了明文的最后一个比特位,拼接起来就是flag。
1 | from Crypto.Util.number import * |
zer0pts{0h_1t_l34ks_th3_l34st_s1gn1f1c4nt_b1t}
3.[羊城杯 2020]Power
PART 1
如果说前面两道题还算比较简单的,个人认为BUUCTF上从这道题开始,就是真正的硬核了。
首先看一下题目。
1 | from Crypto.Util.number import * |
题目代码较短但这并不意味着题目容易解出来。大致看了一下加密过程,我们应当先设法求出$p$。(不过$N$一直是未知的)。而想要求出$p$,就要尝试求出$x$。
首先,我们就是要解决一个离散对数问题。我们发现$y$是一个素数,因此我们尝试分解$y-1$,发现其大概是$100$万的光滑。
然后就可以使用我在离散对数笔记里提到的那个脚本解了。不过发现太难解了,跑了半小时,五分之一进度都没跑到。查了一下Sagemath的使用手册,发现可以这样做,用时40秒左右。
这样我们就解出了$x$。
解出$x$之后,由于$2021p^4+2020p^3+2019p^2-x=0$。这个关于$p$的函数具有单调性,因此我们可以使用OI中讲过的二分答案的方式解决。
1 | from Crypto.Util.number import * |
解出$p$之后,知道了$d_p$,查阅资料,可以用这样的算法解决,这个代码也是在已知$d_p,p$和$n$的结构为$p^kq$类型的求$m$方法。
1 | from Crypto.Util.number import * |
4.[watevrCTF 2019]Baby RLWE
PART 1
1 | #Sagemath Ver 9.0 |
这道题直接就给出的是Sagemath里的应用。题目给出的数据是一个多项式$a(x)$,和$100$个多项式$b(x)$。仔细观察一下发现$b(x)$对应次数接近。初步判定$n=104$。
gen_large_poly()
函数是在多项式环里随机选取一个元素,这个不难理解。不过最后不知道gen_small_poly()
究竟讲的什么,不过我们可以把它放到Sagemath中试验一下
我们发现它生成的多项式的系数基本上在$[-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。
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 等格上的困难问题(即求解这些问题并不比求解格上困难问题容易)。
下面介绍这几个问题的定义:
太抽象了,我看不懂
说的简单一点,就是写出一个形如$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)关于消除扰动项
如果上面的内容过于复杂引起不适,建议结束阅读。
5.总结
BUUCTF深水区的题目,都是非常难的题目,而这些题目也是大赛里面的题目,很有学习价值的,能学到很多心得加密过程和算法(。
不过自己一直都是个mmxfw,因为自己太菜了,哎(