Crypto的工具太多啦，经常想不起来一些工具是怎么使用的，这里简单记录一下一些工具的使用。

flatter

加速LLL的工具，使用上也没什么特别的，直接使用模板即可。不知是conda还是ipynb的锅，我的flatter在直接使用的时候会找不到一个库，得自己添加进环境变量。

import os 
from re import findall
from subprocess import check_output

os.environ['DYLD_LIBRARY_PATH'] = "/Users/nightmare/flatter/build/lib"

def flatter(M):  
    # compile https://github.com/keeganryan/flatter and put it in $PATH  
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"  
    ret = check_output(["flatter"], input=z.encode())  
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
    
L = flatter(L) # L = L.LLL()

cuso

被群友安利了，好用的copper solver。使用上也很简单。就是得注意一下bounds的坑点（是取开区间不是取闭区间）
relations: 关系式
bounds: 界限
modulus: 模数
modulus_multiple: 模数的幂次
modulus_lower_bound: 模数的最低

example1:

import cuso
from sage.all import var

N = 7803960993055714764790127684076211863657988334421459147942569078964485679825779792612991909294331632362413082874625938556130231837335088680459104018893959
p_lsb = 779432292600303509528505569280402295375268661469
num_lsbs = 160

# x represents the unknown lsbs
x = var('x')
# f(x) == 0 (mod p) when x is the 96 most significant bits of p
f = 2**160 * x + p_lsb

# Only one polynomial in our system
relations = [f]
# We give lower and upper bounds of x
bounds = {x: (0, 2**96)}
roots = cuso.find_small_roots(
    relations,
    bounds,
    modulus = "p",
    modulus_multiple = N,
    modulus_lower_bound = 2**255,
)
assert len(roots) > 0
p = roots[0]["p"]
assert N % p == 0
print(f"Recovered factor p = {p}")

example2:

import cuso
from sage.all import var, inverse_mod

N = 7803960993055714764790127684076211863657988334421459147942569078964485679825779792612991909294331632362413082874625938556130231837335088680459104018893959
e = 7338455574804691890149651420174638680950093405994546367015621732049630822037090156191940077914112346956150999747345628657616947167917355899104335150736479
priv_exp_len = 136

p, q, k = var('p, q, k')
# By the RSA equation,
#     e * d = 1 + k*(p - 1)*(q - 1)
#         N = p * q
# where d, k, p, and q are unknown.
# The first relation is modulo e;
# the second doesn't have a modulus.
phi = (p - 1) * (q - 1)
relations = [
    0 == 1 + k * phi,
    N == p * q,
]
moduli = [
    e,
    None,
]

# We give lower and upper bounds of p, q, and k.
bounds = {
    p: (2**255, 2**256),
    q: (2**255, 2**256),
    k: (0, 2**priv_exp_len),
}
roots = cuso.find_small_roots(
    relations,
    bounds,
    modulus=moduli,
)
assert len(roots) > 0
phi = phi.subs(roots[0])
d = int(inverse_mod(e, phi))
print(f"Recovered small exponent d = {d}")

MT19937

自己搓的最简单。$s\cdot T=B$，$B$为泄漏的bits，$T$为恢复出的固定矩阵（根据泄漏位所在位置），$s$即为初始的$state$

from random import *

RNG = Random()

# 按照泄漏的方式重新泄漏(此处展示泄漏32位)
def get_row(RNG):
    v = []
    for i in range(len(l)):
        v += [int(_) for _ in bin(RNG.getrandbits(32))[2:].zfill(32)]
    return v

def build():
    T = []
    for i in range(19968):
        tmp = "0" * i + "1" + "0" * (19968-i-1)
        state = [int(tmp[32*j:32*(j+1)], 2) for j in range(624)]
        RNG.setstate((3, tuple(state+[624]), None)) # 恢复成设置好state的状态
        T.append(get_row(RNG))
    
    return matrix(GF(2), T)

T = build()
print(rank(T))
B = []
for i in range(len(l)):
    B += [int(_) for _ in bin(l[i])[2:].zfill(32)]

B = vector(GF(2), B)
s = T.solve_left(B)
print(s)
init = ''.join([str(_) for _ in s])
state = [int(init[32*j:32*(j+1)], 2) for j in range(624)]

RNG1 = Random()
RNG1.setstate((3,tuple(state+[624]),None))

z3

处理复杂混合逻辑的神器。去年省赛没下z3被狠狠的教训了。下面列举些常用的。
<，<=，>，> =，/，％和>>对应于有符号的版本。相应的，无符号运算符是ULT，ULE，UGT，UGE，UDiv，URem和LShR

#int类型
x = Int('x')
x, y, z = Ints('x y z')
#实数
x = Real('x')
x, y, z = Reals('x y z')
#16位向量（我觉的应该称为16bit的整数）
x = BitVec('x', 16)
x, y = BitVecs('x y', 16)
#解方程
solve(x > 2, y < 10, x + 2*y == 7)
#简化器（将式子化简）
simplify(x < y + x + 2)
#求解器
s = Solver()
s.add(x > 2, x < 10)
s.check() #有解则为sat
s.model() #求出的解
for d in m.decls(): print ("%s = %s" % (d.name(), m[d])) #遍历解
#precision=30即保留30位小数
set_option(precision=30)

primefac & yafu

光滑数分解：
python -m primefac -vs -m=p-1 xxxxxxx
python -m primefac -vs -m=p+1 xxxxxxx
yafu分解
yafu-x64 "factor(@)" -batchfile test.txt

N1gh7ma12e的小站

Crypto常用工具篇

flatter

cuso

MT19937

z3

primefac & yafu