SM2 椭圆曲线

# 0.参考
[1]   [椭圆曲线](https://www.cnblogs.com/Kalafinaian/p/7392505.html)
[2]   [武汉大学SM2](https://wenku.baidu.com/view/02c1d4ba650e52ea54189820.html)
[3] 杨波,现代密码学[M],清华大学出版社，2017
[4] [more on ecc](https://blog.xiaofuxing.name/2017/05/10/more_on_ecc.html)

# 1.椭圆曲线介绍

- 1985年Neal Koblitz and Victor Miller分别独立地提出将椭圆曲线应用在密码学中，提出了椭圆曲线密码系统(Elliptic Curve Cryptography,ECC),具有良好的特性(**密钥短，安全性高**)
 - E:y2=x3+ax+b(要求曲线上的点都是光滑的，即曲线上任意的点存在切线)
 
<center>
 ![椭圆曲线图](https://leanote.com/api/file/getImage?fileId=5b1f5bd7ab64410922000d76)
</center

- x、y有限域Z23={0,1,2,...22},即x,y∈域Z23，y2=x3+x+10 mod 23
 - 计算点集合x=1,(y2 mod 23)=(12 mod 23),try n*23+12=y2
 - 点集合(1,9),(1,14)(4,3),(4,20).....
<center>
![点集合](https://leanote.com/api/file/getImage?fileId=5b1f6026ab64410922000e03)
</center>

- 群的定义(一个集合加上一个运算的代数系统)
* 加法运算
 - 选择椭圆曲线上的两个不同坐标点P和Q，画一条直线经过**P**和**Q**，交椭圆曲线于一点，这一点关于X轴的对称点记为**R**，交点记为**-R**
 - **P + Q = R**
<center>
![群-加法](https://leanote.com/api/file/getImage?fileId=5b1f61afab64410922000e5a)
</center>

* 逆元(该点关于X轴的对称点,比如**R**与**-R**)

* 单位元($\overline{PQ}$与X轴垂直时，就没有交点，但我们认为有交点，是无穷远点，无穷远点就是单位元，记为$O$)
* $2P$ = $P$ + $P$ = $R$

<center>
![2P=P+P](https://leanote.com/api/file/getImage?fileId=5b1f65c8ab64410922000f15)
</center>

- 椭圆曲线密码离散对数问题
 
* 椭圆曲线点乘，也叫标量乘 $3P=2P+P=(22,13)+(5,5)=(8,22)$
* $kP = \overbrace{P+...+P} ^ {k个P}$
* $Q=kP$,已知$Q$ 和 $P$ 求$k$,求$k$比较困难，这就是**椭圆曲线离散对数问题(ECDLP)**
* 在实际使用中一般$Q$作为公钥，$k$为私钥

# 2.有限域中的乘法逆元与加法逆元

## 2.1 乘法逆元
任意的$w$属于Zp,$w != 0$,存在z属于Zp使得 w*z = 1(mod p)

## 2.2 P(x1, y1 ) + Q(x2 + y2)=(x3,y3)
 - 步骤一：计算斜率
<center>
 ![斜率计算公式](https://leanote.com/api/file/getImage?fileId=5b21d785ab64413f3e000763)
</center>
 - 步骤二:计算x3

<center>
![x计算](https://leanote.com/api/file/getImage?fileId=5b21d81aab64413f3e00077e)
</center>

- 步骤三:计算y3
<center>
![y的计算](https://leanote.com/api/file/getImage?fileId=5b21d840ab64413f3e000782)
</center>

>demo:y2=x3+x+6 mod 11
取G = (2,7)为生成元，2倍点的计算如下:
>>2G = (2,7) + (2,7) = (5,2)
步骤一：计算斜率
<center>
![斜率计算](https://leanote.com/api/file/getImage?fileId=5b21da4dab64413d2d0007de)
</center>

>>步骤二:计算x3
<center>
![计算x](https://leanote.com/api/file/getImage?fileId=5b21db91ab64413f3e000832)
</center>
>>步骤三:计算y3
<center>
![计算y](https://leanote.com/api/file/getImage?fileId=5b21dbacab64413d2d000857)
</center>

# 3.明文消息到椭圆曲线上的嵌入

## 3.1 平方剩余概念
设p为素数，如果存在一个正整数y，使得y2 = a mod p,则称a是模p的**平方剩余**

> **demo:** 求出mod 11的平方剩余
>> 12 mod 11= 1 mod 11=1
22 mod 11= 4 mod 11=4
32 mod 11= 9 mod 11=9
42 mod 11= 16 mod 11=5
62 mod 11= 36 mod 11= 3
72 mod 11= 49 mod 11= 5
82 mod 11= 64 mod 11= 9
92 mod 11= 81 mod 11= 4
102 mod 11= 100 mod 11=1
所以，mod 11 的平方剩余为{1,3,4,5,9}

## 3.2 明文消息嵌入
设明文消息是m(0=< m < M)
x= {mk + j,j =0,1,2,3....},其中k是一个足够整数，实际中k一般取值30-50.
直到x3 + ax + b mod p是平方剩余
反过来，为了从椭圆曲线上的点(x,y)得到明文消息m,只需要求 m =[x/30]

>**demo:** 椭圆曲线y2 = x 3 + 3x,p=4177,m=2174
>>x={30·2174 + j,j=0,1,2.....}
当j = 15时，x= 30·2174 + 15 = 65235，x3 + 3 x =652353 + 3 · 65235 = 1444 mod 4177 = 382 mod 4177 ,所以得到椭圆曲线上的点为(65235,38)

# 4. SM2椭圆曲线公钥密码加密算法
SM2算法分为基于素数域和基于二元扩域两种，仅介绍**基于素数域的SM2算法**

## 4.1 基本参数

---

如果椭圆曲线上一点p，存在最小正整数n,使得数乘 $np=O$,则称n为p的**阶**

---

- Fp的特征p为m比特长的素数，p要尽可能大，但太大会影响计算速度
 - 长度不小于192比特的比特串SEED
 - Fp上的2个元素a/b满足，4a3 + 27 b2 ≠ 0，定义曲线y2 = x2 + ax + b
 - 基点G=(xG,yG)
 - G的阶n为m比特长的素数，满足 n > 2191且n > 4 $\sqrt p$
 - h=$\frac{|E(F_{p})|}{n}$,h称为余因子，其中${|E(F_{p})|}$是曲线E(Fp)的点数

## 4.2 SEED和a、b的产生算法

- (1)任意选取长度不小于192比特的比特串SEED
 - (2)计算H=H256(SEED),其中H256表示256比特输出的SM3哈希算法
 - (3)$ R=\sum_{i=0}^{255} h_{i}2^i$
 - (4) 取 r = R mod p
 - (5) 在Fp上任意选择2个元素a，b，满足rb2=a3 mod p
 - (6) 若4a3 + 27b2 = 0 mod p,则转向(1)
 - (7) 所选择的Fp上曲线是E(Fp):y2=x2 + ax +b
 - (8)输出(SEED,a,b)

## 4.3 密钥产生
接收方为B，B的密钥取为**{1,2,...,n-1}**中的一个随机数dB,其中n是基点G的阶
B的公钥取为椭圆曲线上的点: **PB=dBG**,其中G是基点

## 4.4 加密算法

设发送方是A，A是要发送的消息表示成比特串M,M的长度为klen，加密运算如下：

- (1)选择随机数k <--{1,2,...,n-1}
 - (2)计算椭圆曲线点C1=kG=(x1,y1)
 - (3)计算椭圆曲线点S=hPB,若S是无穷远点，则报错并退出
 - (4)计算椭圆曲线点kPB=(x2,y2)
 - (5)计算t=KDF(x2 || y2,klen)
 - (6)计算C2=M $\bigoplus$ t
 - (7)计算C3 = Hash(x2 || M || y2)
 - (8)输出密文C=(C1,C2,C3)

<center>
![SM2加密算法流程图](https://leanote.com/api/file/getImage?fileId=5b235994ab64411c6a000f14)
</center>

## 4.5 解密算法

- (1) 从C中取出比特串C1,将C1表示成椭圆曲线上的点，验证C1是否满足椭圆曲线方程，若不满足则报错退出
 - (2)计算椭圆曲线点S=hC1,若S是无穷远点，则报错并退出
 - (3)计算dBC1=(x2,y2)
 - (4)计算t=KDF(x2 || y2,klen)
 - (5)从C中取出比特串C2,计算M'=C2 $\bigoplus$ t
 - (6)计算u=Hash(x2 || M ' || y2),从C中取出C3,若u ≠ C3,则报错退出
 - (7)输出明文M'
 
<center>
![SM2解密流程](https://leanote.com/api/file/getImage?fileId=5b235db8ab64411e95000f47)
</center>

# 5 SM2 code
> sm2.c

```c++
typedef struct ECCParameter_st
{
unsigned char p[ECC_BLOCK_LEN];//模数p
unsigned char a[ECC_BLOCK_LEN];//参数a
unsigned char b[ECC_BLOCK_LEN];//参数b
unsigned char Gx[ECC_BLOCK_LEN];//G点的x坐标
unsigned char Gy[ECC_BLOCK_LEN];//G点的y坐标
unsigned char Gn[ECC_BLOCK_LEN];//G点的阶
}ECCParamater;

```

```
typedef struct ECCrefPublicKey_st
{
unsigned int bits;
unsigned char x[ECCref_MAX_LEN];
unsigned char y[ECCref_MAX_LEN];
}ECCrefPublicKey

typedef struct ECCrefPrivetKey_st
{
unsigned int bits;
unsigned char D[ECCref_MAX_LEN];//64
}ECCrefPrivateKey;
```

信息安全从业人员^_^

导航

最近发表

友情链接