2018 BCTF guess_number

2019-06-27 本文已影响37人 Black_Sun

1.首先安装需要解密码的编程环境：

sage环境，
- 这个之前安装过，有点问题。所以以后有机会在进行总结
- 也可以使用在线环境。
  https://cocalc.com/projects?session=default
  http://www.sagemath.org/
安装 fpylll
- pip install fpylll 会报错：
  图片.png
  具体原因：不能使用pip安装。只能从github的源码安装
  本人找了个取巧的办法：
  使用apt-get安装：
  具体步骤和问题如下：
  图片.png
  解决办法：
  安装aptitude
  参考网站：https://blog.csdn.net/solo_ws/article/details/52834024

sudo apt-get install aptitude

使用aptitude安装：

图片.png

 sudo aptitude install python-fpylll

参考网站：http://installion.co.uk/kali/kali/main/p/python-fpylll/install/index.html

安装完成！！！！！

服务器的代码如下：

import random
from flag import FLAG
import gmpy2


def msb(k, x, p):
    delta = p >> (k + 1)
    ui = random.randint(x - delta, x + delta)
    return ui


def main():
    p = gmpy2.next_prime(2**160)
    for _ in range(5):
        alpha = random.randint(1, p - 1)
        # print(alpha)
        t = []
        u = []
        k = 10
        for i in range(22):
            t.append(random.randint(1, p - 1))
            u.append(msb(k, alpha * t[i] % p, p))
        print(str(t))
        print(str(u))
        guess = raw_input("Input your guess number: ")
        guess = int(guess)
        if guess != alpha:
            exit(0)


if __name__ == "__main__":
    main()
    print(FLAG)

这里注意下：自己在搭建服务环境的时候出现了如下问题：

图片.png

由于python会出现延时发送的问题：
解决办法：
1.一种办法是每次print后，都调用stdout flush()，把缓冲区打印出来，这个办法比较麻烦，要重载stdout，不推荐。
2.最简单的方法是用命令行参数-u启动python，禁用stdout缓冲
比如脚本是build-native.py，运行 python -u build-native.py就不会出现print延迟问题了

ncat -vc 'python -u server.py' -kl 127.0.0.1 8888

服务器代码简要说明：

u.append(msb(k, alpha * t[i] % p, p))
msb()函数：
这是一个Hidden number problem

公式

中文解释

参考文献：基于部分信息泄露的Hensel提升计算问题

HNP的定义如下：

给定质数 $p$ 、许多 $t \in \mathbb{F}_p$ 以及每一个对应的 $MSB_{l,p}(\alpha t)$ ，找出对应的 $\alpha$ 。

$MSB_{l,p}(x)$ 表示任一满足 $\lvert (x \mod p) - u \rvert \le \frac{p}{2^{l+1}}$ 的整数 $u$ ，近似为取 $x \mod p$ 的 $l$ 个最高有效位。

根据参考3中的描述，当 $l \approx \log^{\frac{1}{2}}{p}$ 时，有如下算法可以解决HNP：

我们可以将此问题转化为一个由该矩阵生成的格上的CVP问题：

$\left[ \begin{matrix} p & 0 & \dots & 0 & 0 \\ 0 & p & \ddots & \vdots & \vdots \\ \vdots & \ddots & \ddots & 0 & \vdots \\ 0 & 0 & \dots & p & 0 \\ t_1 & t_2 & \dots & t_{n} & \frac{1}{2^{l+1}} \end{matrix} \right]$

我们需要找到在格上离 $\mathbf{u}=(u_1, u_2, \dots, u_{n}, 0)$ 最近的向量，所以在这里，我们可以采用Babai's nearest plane algorithm。最终我们可以得到一组向量 $\mathbf{v}=(\alpha \cdot t_1 \mod p, \alpha \cdot t_2 \mod p, \dots, \frac{\alpha}{2^{l+1}})$ ，从而算出 $\alpha.$

注意，要做格基约化，必须满足msb. v向量中的最后一个，只要除以 ${2^{l+1}}$ ,即可得到 $\alpha$ .

参考文献：
https://www.iacr.org/archive/crypto2009/56770333/56770333.pdf

解题代码详解(python)：

from fpylll import *
import random
from gmpy2 import next_prime, invert
from pwn import *
r= remote('127.0.0.1',8888)
def solve(t, u):
    p = int(next_prime(2**160))
    k = 2**11

    m = [list(map(lambda s: s * k, t)) + [1]]
    m += [[0] * i + [p * k] + [0] * (22 - i) for i in range(22)]
    u = u + [0]
    u = list(map(lambda s: s * k, u))

    M = IntegerMatrix.from_matrix(m)
    U = tuple(u)

    M = LLL.reduction(M)

    v = CVP.closest_vector(M, U)

    x = v[-1]
    x = (p + x) % p
    return x


for i in range(5):
      t1 = r.recvline().strip()
      u1 = r.recvline().strip()
      print(r.recvuntil("number:"))
      #print(t1)
      #print(u1) 
      t = t1.replace('L', '')
      u = u1.replace('L', '')
      #print(t,u) 
      t = eval(t)
      u = eval(u)
      r.sendline(str(solve(t,u)))
      print(solve(t, u))
print (r.recvline())

这里重点代码解释下：

 M = IntegerMatrix.from_matrix(m)# 构建矩阵
    U = tuple(u)

    M = LLL.reduction(M) ###LLL格机约化

    v = CVP.closest_vector(M, U) ###计算CVP最近距离向量

 x = v[-1]
    x = (p + x) % p #这里有可能出现负数，通过这步，把负数变正数

总结：

满足：

a是区间[1, p −1]

满足 $\lvert (x \mod p) - u \rvert \le \frac{p}{2^{l+1}}$

ui = random.randint(x - delta, x + delta)
表示u =at[i]- $p/2^{l+1}$

解：
1.构造如下矩阵：

图片.png
2.LLL格机约化得到满足格的最小基
3.算CVP最短距离
4.通过最进距离v向量的最后一个元素乘以 $p/2^{l+1}$ （本文解法是提前构造矩阵（第一步时），就乘以了 $p/2^{l+1}$ ）
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

下面重点讲一下另外一种解题思路（sage）：

这里主要是比起上面多了正交化，和通过正交化映射到每一个向基向量上

import socket
import ast
import telnetlib

#HOST, PORT = 'localhost', 9999
HOST, PORT = '60.205.223.220', 9999

s = socket.socket()
s.connect((HOST, PORT))
f = s.makefile('rw', 0)

def recv_until(f, delim='\n'):
    buf = ''
    while not buf.endswith(delim):
        buf += f.read(1)
    return buf

p = 1461501637330902918203684832716283019655932542983
k = 10

def solve_hnp(t, u):
    # http://www.isg.rhul.ac.uk/~sdg/igor-slides.pdf 
    M = Matrix(RationalField(), 23, 23)
    for i in xrange(22):
        M[i, i] = p
        M[22, i] = t[i]

    M[22, 22] = 1 / (2 ** (k + 1))

    def babai(A, w):
        A = A.LLL(delta=0.75)
        G = A.gram_schmidt()[0]
        t = w
        for i in reversed(range(A.nrows())):
            c = ((t * G[i]) / (G[i] * G[i])).round()
            t -= A[i] * c
        return w - t

    closest = babai(M, vector(u + [0]))
    return (closest[-1] * (2 ** (k + 1))) % p

for i in xrange(5):
    t = ast.literal_eval(f.readline().strip())
    u = ast.literal_eval(f.readline().strip())
    alpha = solve_hnp(t, u)
    recv_until(f, 'number: ')
    s.send(str(alpha) + '\n')

t = telnetlib.Telnet()
t.sock = s
t.interact()

具体代码如下：

图片.png

个人理解：
1.正交化后，得到两个向量的夹角（gs系数）：

图片.png
2.获得t在g[i]上的投影，（也就是将u投影到格基上）
3.t -= A[i] * c ：算出正交向量，（减去没给向量基中每个向量的最小值）
4.算CVP问题，算出最近的向量
相关文献：https://www.zybuluo.com/RunZhi/note/854221
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

eval():

描述

eval() 函数用来执行一个字符串表达式，并返回表达式的值。

语法:

以下是 eval() 方法的语法:
eval(expression[, globals[, locals]])

参数:

expression -- 表达式。
globals -- 变量作用域，全局命名空间，如果被提供，则必须是一个字典对象。
locals -- 变量作用域，局部命名空间，如果被提供，可以是任何映射对象。

返回值:

返回表达式计算结果。

strip()方法:

描述:

Python strip() 方法用于移除字符串头尾指定的字符（默认为空格或换行符）或字符序列。
注意：该方法只能删除开头或是结尾的字符，不能删除中间部分的字符。

语法：

strip()方法语法：
str.strip([chars]);

参数:

chars -- 移除字符串头尾指定的字符序列。

返回值:

返回移除字符串头尾指定的字符生成的新字符串。

random.randint(a,b)

以上实例我们使用了 random 模块的 randint() 函数来生成随机数，你每次执行后都返回不同的数字（0 到 9），该函数的语法为：

random.randint(a,b)

函数返回数字 N ，N 为 a 到 b 之间的数字（a <= N <= b），包含 a 和 b。

Python round() 函数:

描述
round() 方法返回浮点数x的四舍五入值。

语法
以下是 round() 方法的语法:
round( x [, n] )

参数
x -- 数值表达式。
n -- 数值表达式。

返回值
返回浮点数x的四舍五入值。

reversed 函数:

描述
reversed 函数返回一个反转的迭代器。

语法
以下是 reversed 的语法:
reversed(seq)
参数
seq -- 要转换的序列，可以是 tuple, string, list 或 range。
返回值
返回一个反转的迭代器。
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

基础知识：

格理论与密码学：

1.格：

定义：
线性独立空间上有集合:
image

格（Lattices）就是这些向量的线性组合，用公式表示如下：

image

。格L的维数等于格中向量的个数。

格是一组向量，它们是具有整系数的基向量的线性组合。因此，它是向量空间的子集（这些点在向量空间中形成网格），通过对这些点的操作（加、减、乘），它被称为格。

图片.png

欧几里德范数:
欧式距离（对应L2范数）：最常见的两点之间或多点之间的距离表示法，又称之为欧几里得度量，它定义于欧几里得空间中。n维空间中两个点 $x_i( x_{11},x_{12},…,x_{1n})$ 与 $x_2(x_{21},x_{22},…,x_{2n})$ 间的欧氏距离：

图片.png

L2范数: ||x||为x向量各个元素平方和的1/2次方，L2范数又称Euclidean范数或者Frobenius范数
范数:
向量的范数可以简单形象的理解为向量的长度，或者向量到零点的距离，或者相应的两个点之间的距离。
向量的范数定义：向量的范数是一个函数||x||,满足非负性||x|| >= 0，齐次性||cx|| = |c| ||x|| ，三角不等式||x+y|| <= ||x|| + ||y||。

CVP问题和SVP问题：

假定 image
是格中格L的基， image
则有必然存在整系数 image
使得：
image

这样的话，格中的问题就是矩阵运算了。

最短向量问题（SVP，The Shortest Vector Problem）：寻找一个格L中最短的非零向量。即，寻找一个满足其欧几里德范数||v||最小。

最接近向量问题（CVP，The Closest Vector Problem）：对于一个非格L中的向量w，在格中寻找一个向量v，使得||w-v||最小。

CVP和SVP都是NP完备问题，因此求解起来十分困难，因此这2个问题都是可以作为密钥体制的基础的。

图片.png

、、、、、、、、、、、、、、、、、、、、、、

Babai最接近向量算法(理解)

图片.png

原文：https://blog.csdn.net/u010536377/article/details/42142075

、、、、、、、、、、、、、、、、、、、、、、....................

CVP

CVP是Lattice-based cryptography中尤为重要的一个问题。

问题的基本定义如下：给定格 $L$ 的一组基与向量 $\mathbf{v}$ ，找到在 $L$ 上离 $\mathbf{v}$ 最近的一个向量。

Algorithms

Babai's nearest plane algorithm

该算法输入一组格 $L$ (秩为 $n$ )的基 $B$ 和一个目标向量 $\mathbf{t}$ ，输出CVP问题的近似解。

近似因子为 $\gamma = 2^{\frac{n}{2}}$

具体算法：

图片.png

其中 $c_j$ 为Gram-schmidt正交化中的系数取整，也即 $proj_{b_{j}}(b)$ 的取整。

对于该算法第二步的个人理解：在格基规约和正交化过后的基 $B$ 中找到一个最靠近 $\mathbf{t}$ 的线性组合。

Babai’s Rounding Technique

该算法是Babai's nearest plane algorithm的一个变种。

步骤可以表示为：

N = rank(B), w = target
- B' = LLL(B)
- Find a linear combination [l_0, ... l_N] such that w = sum(l_i * b'_i).
* (b'_i is the i-th vector in the LLL-reduced basis B')
- Round each l_i to it's closest integer l'_i.
- Result v = sum(l'_i * b'_i)

参考

Lecture 3 - CVP algorithm
Wikipedia
Playing “Hide-and-Seek” in Finite Fields: Hidden Number Problem and Its Applications （重要讲义）
https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch18.pdf
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
参考网站：
https://blog.csdn.net/kingzone_2008/article/details/15073987
https://bihu.com/article/1359958878 （基础知识）
https://blog.csdn.net/u010536377/article/details/42142075

https://github.com/nguyenduyhieukma/CTF-Writeups/blob/master/BCTF/2018/Crypto.ipynb （有空再理解下）
https://github.com/mimoo/RSA-and-LLL-attacks （RSA格基攻击）
Solving Hidden Number Problem with One Bit Oracle and Advice

https://www.jianshu.com/p/b72f440468f7 （需要深入理解下）
https://wheat2016.lip6.fr/HEAT_Paris_Damien.pdf（详细讲义）
https://wiki.x10sec.org/crypto/asymmetric/lattice/lattice-reduction/（LLL算法举例）
http://www.cits.rub.de/imperia/md/content/may/cryptanalysis_folien.pdf (格基技术讲义)
https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch18.pdf（Babai’s Nearest Plane Method）

2018 BCTF guess_number

1.首先安装需要解密码的编程环境：

安装完成！！！！！

服务器的代码如下：

服务器代码简要说明：

解题代码详解(python)：

总结：

下面重点讲一下另外一种解题思路（sage）：

eval():

语法:

参数:

返回值:

strip()方法:

random.randint(a,b)

Python round() 函数:

reversed 函数:

基础知识：

格理论与密码学：

Babai最接近向量算法(理解)

CVP

Algorithms

Babai's nearest plane algorithm

Babai’s Rounding Technique

相关内容

Hidden number problem

BCTF 2018 - guess_number

参考

猜你喜欢

热点阅读