SM2算法原理.pdf

SM2 算法
1、算法原理
椭圆曲线算法是通过方程确定的，SM2 算法采用的椭圆曲线方程为：
y2 = x3 + ax + b
在 SM2 算法标准中，通过指定 a、b 系数，确定了唯一的标准曲线。

下面通过图示展示算法原理。请参见下图：

图1 椭圆曲线算法原理
上图为方程：y2 = x3–x 的曲线。
1、P点为基点；
2、通过 P 点做切线，交与点 2P 点，在 2P’点做竖线，交与 2P 点，2P 点
即为 P 点的 2 倍点；
3、进一步，P 点和 2P 点之间做直线，交与 3P’点，在 3P’点做竖线，交与
3P 点，3P 点即为 P 点的 3 倍点；
4、同理，可以计算出 P 点的 4、5、6、… 倍点；
5、如果给定图上 Q 点是 P 的一个倍点，请问 Q 是 P 的几倍点呢？
6、直观上理解，正向计算一个倍点是容易的，反向计算一个点是 P 的几倍
点则困难的多。
在椭圆曲线算法中，将倍数 d 做为私钥，将 Q 做为公钥。
2、椭圆曲线系统参数
Fp 上椭圆曲线系统参数包括：
a) 域的规模 q = p，p 是大于 3 的素数；
b) (选项)一个长度至少为 192 的比特串 SEED；
c) Fp 中的两个元素 a 和 b，它们定义椭圆曲线 E 的方程：y2 = x3+ax+b；
d) 基点 G = (xG;yG) ∈ E(Fp)，G ≠ O；
e) 基点 G 的阶 n(要求：n > 2191 且 n > 4p1=2)；
f) (选项)余因子 h = #E(Fp)=n。
3、密钥对的生成
输入：一个有效的 Fq(q = p 且 p 为大于 3 的素数，或 q = 2m)上椭圆曲线系
统参数的集合。
输出：与椭圆曲线系统参数相关的一个密钥对(d;P)。
a) 用随机数发生器产生整数 d ∈ [1;n−2]；
b) G 为基点，计算点 P = (xP;yP) = [d]G；
c) 密钥对是(d;P)，其中 d 为私钥，P 为公钥。
4、加密算法及流程
设需要发送的消息为比特串 M，klen 为 M 的比特长度。