文章目录
  1. 基本的环和域
  2. 数论基本函数
  3. 线性代数
  4. 离散椭圆曲线
  5. 离散对数
  6. coppersmith算法

基本的环和域

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
#整数域,有理数域和实数域
ZZ(3)
QQ(0.25)
RR(2^0.5)
#复数域
CC(1,2)
#生成虚数单位i
i=ComplexField().gen();(2+i)*(4+3*i)

#构造多项式环,返回具有给定属性和变量名的全局唯一的单变量或多元多项式环
#定义在整数域上的多项式环R，变量为w;ZZ也可换成其他数域
R.<w>=PolynomialRing(ZZ);R
(1 + w)^3

#有限环
RN=IntegerModRing(63)
FR=Integers(17);FR
#自身的代数扩展;exR=FR[w]/(w^2+3)
exR=FR.extension(w^2+3)；exR
#以python整数的形式返回所有可逆元素的列表
FR.list_of_elements_of_multiplicative_group()
#假设环的乘法群是循环的，返回这个环的乘法群的生成元
FR.multiplicative_generator()
#返回这个环的一个随机元素
FR.random_element()
#上述几种方法对如下的域同样支持

#有限域
#素数域
G1=GF(37);G1
#伽罗瓦域
G2=GF(3^5);G2

数论基本函数

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
#同时求商与余数
q,r=divmod(12,5)

#求公约数
d=gcd(12,5)

#扩展的欧几里得算法
d,u,v=xgcd(12,5)

#12在模5下的逆
u=inverse_mod(12,5)

#生成[lb,ub)之间的随机素数,注意ub在前,lb在后,lb可缺省为0
#可通过这种方式生成128位的随机素数
p=random_prime(2L**128,2L**127)

#判断是否为素数
is_prime(65537)

#第20个素数
nth_prime(20)

#计算x^y mod n
z=power_mod(12,5,17)

#欧拉函数
euler_phi(111)

#中国剩余定理,A=[a1,...,an],M=[m1,...,mn]
#ai=x mod mi,i=1,...,n
crt([1,2,3,4],[7,5,12,23])

#求自身的n次根
FR(12).nth_root(7,all='True')

#求多项式的根，roots方法必须作用在域上
R.<x>=PolynomialRing(G1)
xt=G1(12)
yt=xt^6
f=x^6-yt
f.roots()

线性代数

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
#定义矩阵，默认定义在实数域
A = matrix([[1,2,3,5],[3,2,1,2],[1,1,1,0],[3,7,2,2]])
A^-1
#定义在其他域上的矩阵，如有限域
A = matrix(GF(13),[[1,2,3,5],[3,2,1,2],[1,1,1,0],[3,7,2,2]])
A^-1
#可以看到两个逆矩阵不一样

#定义向量，定义在有限域，默认定义在实数域
w = vector(GF(13),[1,1,4,3])
Y=A*w;Y
Z=w*A;Z

#解线性方程组AX=Y
X = A.solve_right(Y);X
#也可以使用符号\
A\Y
#解线性方程组XA=Y
X = A.solve_left(Z);X

#格基约减
A = matrix([[1,2,3,5],[3,2,1,2],[1,1,1,0],[3,7,2,2]])
#LLL算法
A.LLL()
#BKZ算法
A.BKZ()

离散椭圆曲线

以国密SM2算法使用的椭圆曲线为例；

1
2
3
4
5
6
7
8
9
10
11
12
13
p=ZZ('FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF',16)
a=ZZ('FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC',16)
b=ZZ('28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93',16)
#有限域GF(p)上的椭圆曲线y^2 = x^3 + a*x + b mod p
E=EllipticCurve(GF(p),[0,0,0,a,b])
#基点
g=E([ZZ('32c4ae2c1f1981195f9904466a39c9948fe30bbff2660be1715a4589334c74c7',16),ZZ('bc3736a2f4f6779c59bdcee36b692153d0a9877cc62a474002df32e52139f0a0',16)])
#基点的阶
n=ZZ('FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123',16)
#生成密钥
sk=random_prime(2*n//3,n//3)
#生成公钥
G=sk*g

离散对数

前言：求解以base为底，a的对数；ord为base的阶，可以缺省，operation可以是’+’与’*‘，默认为’*‘；bounds是一个区间(ld,ud)，需要保证所计算的对数在此区间内。

1
2
3
4
5
6
7
8
9
10
11
#通用的求离散对数的方法
x=discrete_log(a,base,ord,operation)

#求离散对数的Pollard-Rho算法
x=discrete_log_rho(a,base,ord,operation)

#求离散对数的Pollard-kangaroo算法(也称为lambda算法)
x=discrete_log_lambda(a,base,bounds,operation)

#小步大步法
x=bsgs(base,a,bounds,operation)

coppersmith算法

coppersmith算法介绍链接

使用sage实现coppersmith相关攻击，GitHub链接

最后，sage的官方文档链接