Contents

Writeup for crypto in RCTF 2021

👴第二次打RCTF,周末又来苟了个水题,👴太极吧菜了,全靠队友带

https://gitee.com/ljahum/images/raw/master/img/20210913104029.png

uncommon1

气死了气死了,明明都已经把fastgcd修好了

拿着fastgcd日了半天uncommon2,以为没用,直接扔掉了

淦,根本没考虑过会出现同样的素数,太菜了,明明上课学过的😀😀😀

Fastgcd

这是个什么玩意呢?

众所周知GCD可以快速的算出两个数最大公约数,但如果有$N$个数我可能要算大概$N^2$次

于是一群数学家想:能不能概一个算法吧它的复杂度降低一点?

https://gitee.com/ljahum/images/raw/master/img/20210914230602.png

大概流程如下

生成树这种概念已经太久远了,👴记不清了

https://gitee.com/ljahum/images/raw/master/img/20210914230805.png

或者长这样:

https://gitee.com/ljahum/images/raw/master/img/image-20210914232240947.png

u神不知在那篇文章找到的实现流程:

https://gitee.com/leonsec/images/raw/master/upload_26fe1784ad7c7f16345c3deb248fa320.png

文章说复杂度为$O(N(lgN)^2lg(lgN))$

和$N^2$相比就很舒服了

implement

u神的证明:

https://gitee.com/ljahum/images/raw/master/img/20210914234126.png

完全没想到这一层,上学期还学过,太摆了


fastgcd实现:

你让👴实现这玩意👴肯定是会当场摆烂的,所以👴找到了现成的仓库

https://github.com/sagi/fastgcd

拖下来发现不能立马intsall,于是我们来着手修install

 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
#!/bin/bash

__exists() {
    which $1 1>/dev/null 2>&1
}

get="fetch";
! __exists fetch && get="curl -OL";

if [ ! -d gmp-5.0.5 ];
then

    if [ ! -f gmp-5.0.5.tar.bz2 ];
    then
        $get ftp://ftp.gmplib.org/pub/gmp-5.0.5/gmp-5.0.5.tar.bz2
    fi

    sum=`openssl sha1 gmp-5.0.5.tar.bz2 | awk -F' ' '{print $2}'`

    if [[ $sum != "12a662456033e21aed3e318aef4177f4000afe3b" ]];
    then
        echo ''
        echo '=========================================='
        echo 'ERROR: could not verify gmp-5.0.5.tar.bz2;'
        echo 'Downloaded over untrusted channel (non-https)'
        echo '=========================================='
        exit;
    fi

    tar xf gmp-5.0.5.tar.bz2
fi

cd gmp-5.0.5
patch -p 1 < ../gmp-5.0.5.patch
mkdir ../gmp-patched
./configure --prefix=$PWD/../gmp-patched/
make
make install
cd ..
make

显然是$get ftp://ftp.gmplib.org/pub/gmp-5.0.5/gmp-5.0.5.tar.bz2出了问题(反正我下载不下来)

于是上gmp官网手动下一个

https://gitee.com/ljahum/images/raw/master/img/20210914233123.png

修改install.sh,修改源码报错的预编译代码

fastgcd.c

1
2
3
4
5
6
7
8
9
#define NTHREADS 4 // Get from compile-time argument?

// #ifdef mpz_raw_64 // if patched gmp, use large format int i/o
// #define __mpz_inp_raw mpz_inp_raw_64
// #define __mpz_out_raw mpz_out_raw_64
// #else // otherwise use normal i/o...beware 2^31 byte size limit
#define __mpz_inp_raw mpz_inp_raw
#define __mpz_out_raw mpz_out_raw
// #endif

install.sh

1
2
3
4
5
6
7
8
9
tar xf gmp-5.0.5.tar.bz2
cd gmp-5.0.5
patch -p 1 < ../gmp-5.0.5.patch
mkdir ../gmp-patched
./configure --prefix=$PWD/../gmp-patched/
make
make install
cd ..
make

直接install编译

提取数据为input.modle的格式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
from Crypto.Util.number import *
from tqdm import 
size = 2**22
with open("lN.bin","rb") as f:
    data = f.read()

f1 = open("data","w+")
for i in tqdm(range(size)):
    tmp = hex(bytes_to_long(data[i*64:(i+1)*64]))[2:]
    f1.write(tmp+'\n')

开跑~~

https://gitee.com/ljahum/images/raw/master/img/X9%605(RM~)CL34X%60SG52U$D5.jpg

结果:

比u神多花了5分钟,还是机子不太行🐨🐨🐨

https://gitee.com/ljahum/images/raw/master/img/20210914233648.png

solve

1
2
3
4
5
6
7
8
9
In [2]: s=0x7f2ec3455a5f6763645f5472333333333333338a2068398023
   ...:

In [3]: from Crypto.Util.number import *

In [4]: long_to_bytes(s)
Out[4]: b'\x7f.\xc3EZ_gcd_Tr3333333\x8a h9\x80#'

In [5]:

uncommon2

A AGCD problem,using lattice reduce is simple to solve it

AGCD

$n_i=p*q_i+r_i$形式的AGCD问题,利用格规约是可解的

👴看到很多文章都有打法介绍,但是只有这篇介绍了格子的结构(

https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/

https://gitee.com/ljahum/images/raw/master/img/20210913000636.png

一把梭哈就能解uncommon2

solve

 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
#! /usr/bin/sage
from sage.all import *
from sage.groups.generic import bsgs
from Crypto.Util.number import *
from Crypto.Util.number import *
with open("lN.bin","rb") as f:
    data = f.read()

f1 = open("./data","wb")
size = 128
print('size',size)
nn=[]  
for i in range(size):
    nn.append((bytes_to_long(data[i*64:(i+1)*64])))
B = [[0 for i in range(size)] for _ in range(size)]
x0 = nn[0]
B[0][0]=2^305
for i in range(1,size):
    B[0][i]=nn[i]
    # B[0][i]=i
# print(B)
# print(x0)
print('start LLL....')
for i in range(1,size):
    B[i][i]=-x0
B = Matrix(B)
V = B.LLL()
q = abs(V[0][0])

q = q>>305
print(x0-q)
p = x0//q
print(long_to_bytes(p))


# flag{Simpl3_LLL_TrIck}

attachment

refer

https://www.usenix.org/system/files/conference/usenixsecurity12/sec12-final228.pdf

https://cr.yp.to/lineartime/multapps-20080503.pdf

https://github.com/sagi/fastgcd