《信息安全数学基础》全套PPT课件.ppt

* 10.4 不同特征有限域上的椭圆曲线群加法 设F为一个有限域，E是域F上的椭圆曲线，则E是一个由下列点组成的集合： E/F = {(x, y)∈F | y2 + a1xy + a3y = x3 + a2x2 + a4x + a6, a1, a3, a2, a4, a6 ∈ F} ∪{O} 其中O表示无穷远点。 这个点集在椭圆曲线加法运算下构成群。 密码学中采用的椭圆曲线定义在有限域GF(pm)上，m ≥ 1, p为素数。 * 定义10.2 如果椭圆曲线上一点P，存在最小的正整数n，使得nP = O，则称n为点P的阶；若n不存在，就说P是无限阶的。 事实上，在有限域上定义的椭圆曲线中任意点的阶都是存在的。 用Epm(a, b)表示有限域GF(pm)上的椭圆曲线E的点集{(x, y) ∈ E | x, y ∈ GF(pm) }∪{O}。 * 定义10.3 设P为椭圆曲线中的点，在等式 mP = P + P +…+ P = Q中，已知Q和P求m，称为椭圆曲线上的离散对数问题（ECDLP）。 定义在有限域上的椭圆曲线，已知m和点P，求点Q = mP在计算上容易；反之，已知点Q和点P，求m却是困难的。 椭圆曲线密码体制正是基于这个困难问题而设计的。目前，求椭圆曲线上的离散对数问题的最好算法是Pollard rho方法，具有指数复杂度。 * 不同有限域上的椭圆曲线加法运算如下： 1. GF(pm)（p 3, m ≥ 1）上的椭圆曲线 因为Char(GF(pm)) ≠ 2, 3，由表10.1，域GF(pm)上椭圆曲线E的Weierstrass方程可设为 E: y2 = x3 + ax + b， (10.24) 其中a, b ∈ GF(pm)，Δ = – 16(4a3 + 27b2) ≠ 0。 设P = (x1, y1), Q = (x2, y2)是E的两个点，O为无穷远点，E在GF(pm)上的运算规则为： (1) P + O = O + P = P； * (2) – P = (x1, – y1)，有P + (– P) = O； (3) 如果R = (x4, y4) = P + Q ≠ O，有 x4 = k2 – x1 – x2， y4 = k(x1 – x4) – y1； 其中 * 2. GF(3m)（m ≥ 1）上的椭圆曲线，j(E) ≠ 0* 因为Char(GF(3m)) = 3，由表10.1，域GF(3m)上椭圆曲线E的Weierstrass方程可设为 E: y2 = x3 + a2x2 + a6 (10.25) 其中a2, a6 ∈ GF(3m)，Δ = ≠ 0。 设P = (x1, y1), Q = (x2, y2)是E的两个点，O为无穷远点，E在GF(3m)上的运算规则为： (1) P + O = O + P = P； * * (3) 如果R = (x4, y4) = P1 + P2 ≠ O，有 x4 = k2 – x1 – x2 – a2， y4 = k(x1 – x4) – y1； 其中 * * 3. GF(3m)（m ≥ 1）上的椭圆曲线，j(E) = 0* 因为Char(GF(3m)) = 3，由表10.1，域GF(3m)上椭圆曲线E的Weierstrass方程可设为 E: y2 = x3 + a4x + a6， (10.26) 其中a4, a6 ∈ GF(3m)，Δ = ≠ 0。 设P = (x1, y1), Q = (x2, y2)是E的两个点，O为无穷远点，E在GF(3m)上的运算规则为： (1) P + O = O + P = P； * * (2) – P = (x1, – y1)； (3) 如果R = (x4, y4) = P1 + P2 ≠ O，有 x4 = k2 – x1 – x2 y4 = k(x1 – x4) – y1 其中 * * 4. GF(2m)（m ≥ 1）上的椭圆曲线，j(E) ≠ 0* 因为Char(GF(2m)) = 2，由表10.1，域GF(2m)上椭圆曲线E的Weierstrass方程可设为 E: y2 + xy = x3 + a2x2 + a6， (10.27) 其中a2, a6 ∈ GF(2m)，Δ = a6 ≠ 0。 设P = (x1, y1