21Feb1

huangx607087开学前的切题1

0.简介

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

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

1.[CISCN2018]sm

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

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

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

先看一下题目

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。

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上从这道题开始，就是真正的硬核了。

首先看一下题目。

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$万的光滑。

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

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

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

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$方法。

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

#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中试验一下

我们发现它生成的多项式的系数基本上在$[-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 等格上的困难问题（即求解这些问题并不比求解格上困难问题容易）。

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