writeup for 2021 NepCTF(To be continued

Posted on Edited on In Word count in article: 6.9k Reading time ≈ 6 mins.

太菜了太菜了太菜了, 虽然说跑出去玩了两天, 但还是花了半天时间做的, 一道Coppersmith’s short-pad attack没有想到调, 做了半天都没出来, 属实拉了. 最后也就做了个改表的base64….算是除了签到就没出吧(还有道古典不想查了5555

0x00 Real_Base

problem

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
#py2
import string
import random
from secret import flag,b_char

def encode(s):
    res=''
    binstr=[ bin(ord(s[i])).replace('0b','').zfill(8) for i in range(len(s))]
    p1=len(binstr) // 3
    p2=len(binstr) % 3
    part1 = binstr[0:3*p1]
    
    for i in range(p1):
        str_p1=binstr[i*3]+binstr[i*3+1]+binstr[i*3+2]
        tmp_str = [str_p1[x: x + 6] for x in [0, 6, 12, 18]]
        tmp_res = [b_char[int(x,2)]for x in tmp_str]
        res+=''.join(tmp_res)

    if p2:
        part2 = binstr[3*p1:]
        str_p2 = ''.join(part2)+(3-p2)*'0'*8
        tmp_str = [str_p2[x: x + 6] for x in [0, 6, 12, 18]][:p2+1]
        tmp_res = [b_char[int(x,2)]for x in tmp_str]
        res+=''.join(tmp_res)
        res +='='*(3-p2)
    return res
 
m1=random.sample(list(b_char),50)
print ''.join(m1)
print encode(m1)
print encode(flag)
# rTcb1BR8YVW2EOUjweXpIiLt5QCNg7ZAsD9muq3ylMhvofnx/P
# 2Br9y9fcu97zvB2OruZv0D3Bwhbj0uNQnvfdtC2TwAfPrdBJ3xeP4wNn0hzLzCVUlRa=
# tCvM4R3TzvZ7nhjBxSiNyxmP28e7qCjVxQn91SRM3gBKzxQ=

看了一下整个过程, 就是个base64, 但是表未知, 直接通过一对明文和密文回推表, 得出部分表基本上就能猜出整个表了, 直接用改过的表解码就行了.

exp

当时做的时候的脚本不见了5555555

0x01 你们一天天的不写代码, 难道是在等待爱情

古典大混合, 什么银河字母, 古精灵…..不找了

0x02 ChildRSA

problem

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
#childrsa.py
from Crypto.Util.number import *
from gmpy2 import iroot
from os import *
from secret import flag1,flag2,padding1,padding2
assert len(flag1)==20
assert len(flag1)>len(flag2)
assert len(flag2)==len(padding2)
def init1():
    m=(padding1*2**200+bytes_to_long(flag1))*2**200
    r1=getPrime(170)
    r2=getPrime(170)
    p=getPrime(1024)
    q=getPrime(1024)
    N=p*q

    return m,r1,r2,N
    
def enc1(m,r1,r2,N):
    c1=pow(m+r1,3,N)
    c2=pow(m+r2,3,N)
    return c1,c2

def init2():
    prefix = 2**1000
    r3 = prefix+flag2*2**200
    r4 = 2*prefix+padding2*2**200
    return r3,r4

def enc2(r3,r4):
    c3 = pow(r3*r4,3)
    return c3

(m,r1,r2,N) = init1()
(c1,c2)=enc1(m,r1,r2,N)
(r3,r4) = init2()
c3 = enc2(r3,r4)
print N
print(c1,c2,c3)

# output.txt
N= ...
(c1,c2,c3)= ...

就是这道题做了半天都没出来, 当时试了好久的Coppersmith’s short-pad attack(后面简写为Csp atk, 连都从0.01遍历到1了, 依旧没有出结果, 看了官方wp, WTF??? 调成1???, 为什么?

抱着这个问题我又重新翻了一下Sagemath文档, 找到了small_roots()的解释:

sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots(self, X=None, beta=1.0, epsilon=None, \*kwds*)

​ Let be the characteristic of the base ring this polynomial is defined over: N = self.base_ring().characteristic(). This method returns small roots of this polynomial modulo some factor of with the constraint that . Small in this context means that if is a root of modulo then . This is either provided by the user or the maximum is chosen such that this algorithm terminates in polynomial time. If is chosen automatically it is . The algorithm may also return some roots which are larger than X. This algorithm in this context means Coppersmith’s algorithm for finding small roots using the LLL algorithm. The implementation of this algorithm follows Alexander May’s PhD thesis referenced below.

INPUT:

  • X – an absolute bound for the root (default: see above)
  • beta – compute a root mod where is a factor of N and ( Default: 1.0, so . )
  • epsilon – the parameter described above. (Default: )
  • **kwds – passed through to method Matrix_integer_dense.LLL().

REFERENCES:

Don Coppersmith. Finding a small root of a univariate modular equation. In Advances in Cryptology, EuroCrypt 1996, volume 1070 of Lecture Notes in Computer Science, p. 155–165. Springer, 1996. http://cr.yp.to/bib/2001/coppersmith.pdf

Alexander May. New RSA Vulnerabilities Using Lattice Reduction Methods. PhD thesis, University of Paderborn, 2003. http://www.cs.uni-paderborn.de/uploads/tx_sibibtex/bp.pdf

文档里面给出了small_roots()使用的算法的paper, 有时间好好看一下.
这个函数需要注意的有三个参数X,beta,epsilon, 其中beta和epsilon也就是和 .

来看看这三个参数都该怎么填

  • : 这个算是最好填的, 可以理解成smallroot的上界, 一般来说题目中给出了要解的小根的位数kbits就设置. 而在Csp atk中, 理论可解上界是
  • : 这个可以理解成的因子的下界, 对于常规RSA中的, 一般就只有四个因子, 我们可以选取作为算法使用的因子, 所以其实可以从0取到1, 因为都可能成立, 但真正用的时候一般取.
  • : 神奇的参数, 不填就是, 文档中给出了一个关系式, 其实这个可以暂时忽略掉, 所以就有, 文档里并没有给出 到底该如何取, 但从这题的官方wp中是给出了, 其实就是多项式的次数. 所以对于Csp atk来说, , 的取法为

所以说,填1也是阔以的! 因为factor里面是有的!

按着上面的分析, 把从La佬那边拿来的Csp atk的板子稍微修改一下( 以后就用改进过的板子了嘿嘿嘿….

exp

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
def short_pad_attack(c1, c2, e, n , kbits = 0):
        if kbits == 0 :
            kbits = n.nbits()//(e*e)
        PRxy.<x,y> = PolynomialRing(Zmod(n))
        PRx.<xn> = PolynomialRing(Zmod(n))
        PRZZ.<xz,yz> = PolynomialRing(Zmod(n))
        g1 = x^e - c1
        g2 = (x+y)^e - c2
        q1 = g1.change_ring(PRZZ)
        q2 = g2.change_ring(PRZZ)
        h = q2.resultant(q1)
        h = h.univariate_polynomial()
        h = h.change_ring(PRx).subs(y=xn)
        h = h.monic()
        x = ceil(n.nbits() // kbits)
        for b in [0.4,0.5,0.6,1]:
            eps = (b^2) / (e^2) - (1/x)
            print(eps)
            if eps <= 0:
                eps = b / 8
            print('[+] try beta={} epsilon={}'.format(float(b),float(eps)))
            diff = h.small_roots(X=2^kbits, beta=b,epsilon=eps)
            if len(diff) > 0 :
                print('[+] find diff with beta={} and epsilon={}'.format(b,eps))
                return diff
        
        print('[-] can not find the diff')
        return diff
        
def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2
    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]

from Crypto.Util.number import long_to_bytes as l2b
n = ...
(c1,c2,c3)= ...
e= 3
diff = short_pad_attack(c1,c2,e,n,kbits=170)[0]
res = related_message_attack(c1,c2,diff,e,n)
l2b(res)
# b'\xd4!I\x80M\xf0\x80\\\xd9>\x19\xad\xdd^\x1d$\x99\xc1V\xc9/+\xdc\x97"\xb3 \x03\xef3\xd1\xea\x04\xf4\x81z$\xd2]{\xcb\xc4\x93\xe7\xf6\xb7\x9a\xb2\xe6a\x9fl\x99\xady\xa8\x9e\xa2\xf5\'\xa2\xfc\xe0Z\xa1\x1c\x15\rQ\x7fM\x99T\x93\x04\xc5\xdd\xdc\x80\xe4\x0f\x85)\x9f\xc3p\xdc\x03j.\x87kU\'Ud\x0bD")\x00\x00\x00\x00\x00Nep{Nep_n3p_ba4_bad_\x00\x00\x00\x03\tx@Q2\x1b3\x1f\r\xb2\x95\x86?kE\x1f\xe6\xaay\xf1\xe5'

可以看到flag已经出来一部分了Nep{Nep_n3p_ba4_bad_

来看看怎么求flag2, 先把给的条件写出来, 我们记

官方wp上面说想考一下二元的Coopersmith, 先放着, 有空了学习一波. 这题还可以直接解一元二次方程直接出

解方程解法

我们可以直接通过开三次方得出
咱们先联立一下的两个式子

这里要注意一下, , 也就是说所以其实咱们可以直接有

这样我们就能求出了, 然后我们直接式两边同时乘, 把带入, 就可以构造出一个关于的一元二次方程了.

解出发现…是假flag, md我算了那么久居然是个假的??? 突然想到会不会padding2才是真正的flag, 又把padding2算出来了, 果然….padding2才是真flag

exp

1
2
3
4
5
6
7
8
c = int(c3.nth_root(3) % (2^2001))
pdf =  int(c %2^1200 // 2^400)
x = var('x')
f = 2^1200 * pdf - c * x + 2^1201 * x^2 + 2^400 * x * pdf
flag2  = int(f.roots()[0][0])
padding = pdf // flag2
l2b(padding)
# b'1_l0v3_9ou}'

所以最后的flag就是Nep{Nep_n3p_ba4_bad_1_l0v3_9ou}

0x03 easyEncryption

暂时还没时间, 有空看看

0x04 lowExponent

暂时还没时间, 有空看看