SM2 - 公钥加密算法

符号
A,B：使用公钥密码系统的两个用户。
\(a,b\)：\(F_q\)中的元素，他们定义\(F_q\)上的一条椭圆曲线\(E\)。
\(d_B\)：用户B的私钥。
\(E⁡(F_q )\)：\(F_q\)上椭圆曲线\(E\)的所有有理点（包括无穷远点\(O\)）组成的集合。
\(F_q\)：包含\(q\)个元素的有限域。
\(G\)：椭圆曲线的一个基点，其阶为素数。
\(Hash()\)：密码杂凑函数。
\(H_v ()\)：消息摘要长度为\(v\)比特的密码杂凑函数。
\(KDF()\)：密钥派生函数。
\(M\)：待加密的消息。
\(M'\)：解密得到的消息。
\(n\)：基点\(G\)的阶（\(n\)是\(♯⁡E⁡(F_q )\)的素因子）。
\(O\)：椭圆曲线上的一个特殊点，称为无穷远点或零点，是椭圆曲线加法群的单位元。
\(P_B\)：用户B的公钥。
\(q\)：有限域\(F_q\)中元素的数目。
\(x‖y\)：\(x\)与\(y\)的拼接，其中\(x\)和\(y\)是比特串或字节串。
\([k]P\)：椭圆曲线上点\(P\)的\(k\)倍点，即：\(\lbrack k\rbrack P = \underset{k\text{个}}{\underbrace{P + P + \cdots + P}}\)，其中\(k\)是正整数。
\([x,y]\)：大于或等于\(x\)且小于或等于\(y\)的整数的集合。
\(⌈x⌉\)：顶函数，大于或等于\(x\)的最小整数。例如，\(⌈7⌉=7\)，\(⌈8.3⌉=9\)。
\(⌊x⌋\)：底函数，小于或等于\(y\)的最大整数。例如，\(⌊7⌋=7\)，\(⌊8.3⌋=8\)。
\(♯⁡E⁡(F_q )\)：\(E⁡(F_q )\)上点的数目，称为椭圆曲线\(E⁡(F_q )\)的阶。

密钥派生函数
设密码杂凑函数为\(H_v ()\)，其输出是长度为\(v\)比特的杂凑值。
密钥派生函数\(KDF⁡(Z,klen)\)：
输入：比特串\(Z\)，整数\(klen\)（表示要获得的密钥数据的比特长度，要求该值小于\((2^{32}-1)v\)）。
输出：长度为\(klen\)的密钥数据比特串\(K\)。

1. 初始化一个32比特构成的计数器\(ct=\mbox{0x}00000001\)；
2. 对\(i\)从\(1\)到\(⌈klen⁄v⌉\)执行：
   2.1. 计算\(Ha_i=H_v⁡(Z‖ct)\)；
   2.2. \(ct++\)；
3. 若\(klen⁄v\)是整数，令\(Ha!_{⌈klen⁄v⌉}=Ha_{⌈klen⁄v⌉}\)，否则令\(Ha!_{⌈klen⁄v⌉}\)为\(Ha_{⌈klen⁄v⌉}\)最左边的\((klen-(v×⌊klen⁄v⌋))\)比特；
4. 令\(K=Ha_1 ‖Ha_2 ‖⋯‖Ha_{⌈klen⁄v⌉-1} ‖Ha!_{⌈klen⁄v⌉}\)。

加密算法
设需要发送的消息为比特串\(M\)，\(klen\)为\(M\)的比特长度。
为了对明文\(M\)进行加密，作为加密者的用户A应实现以下运算步骤：

1. 用随机数发生器产生随机数\(k∈[1,n-1]\)；
2. 计算椭圆曲线点\(C_1=[k]G=(x_1,y_1 )\)；
3. 计算椭圆曲线点\(S=[h] P_B\)，若\(S\)是无穷远点，则报错并退出；
4. 计算椭圆曲线点\([k] P_B=(x_2,y_2 )\)；
5. 计算\(t=KDF⁡(x_2 ‖y_2,klen)\)，若\(t\)为全0比特串，则返回步骤1；
6. 计算\(C_2=M⊕t\)；
7. 计算\(C_3=Hash⁡(x_2 ‖M‖y_2 )\)；
8. 输出密文\(C=C_1 ‖C_2 ‖C_3\)。

解密算法
设\(klen\)为密文中\(C_2\)的比特长度。
为了对密文\(C=C_1 ‖C_2 ‖C_3\)进行解密，作为解密者的用户B应实现以下运算步骤：

1. 从\(C\)中取出比特串\(C_1\)，验证\(C_1\)是否满足椭圆曲线方程，若不满足则报错并退出；
2. 计算椭圆曲线点\(S=[h] C_1\)，若\(S\)是无穷远点，则报错并退出；
3. 计算\([d_B ] C_1=(x_2,y_2 )\)；
4. 计算\(t=KDF⁡(x_2 ‖y_2,klen)\)，若\(t\)为全0比特串，则报错并退出；
5. 从\(C\)中取出比特串\(C_2\)，计算\(M'=C_2⊕t\)；
6. 计算\(u=Hash⁡(x_2 ‖M' ‖y_2 )\)，从\(C\)中取出比特串\(C_3\)，若\(u≠C_3\)，则报错并退出；
7. 输出明文\(M'\)。

注：观察加密算法的步骤4与解密算法的步骤3，有如下等式成立