SM2加密算法

几何学基础

  1. 欧式几何
  • 从一点向另一点可以引一条直线。
  • 任意线段能无限延伸成一条直线。
  • 给定任意线段,可以以其一个端点作为圆心,该线段作为半径作一个圆。
  • 所有直角都相等。
  • 若两条直线都与第三条直线相交,并且在同一边的内角之和小于两个直角,则这两条直线在这一边必定相交。
  1. 罗巴切夫斯基几何
  • 第五公设不能被证明。
  • 在新的公理体系中展开的一连串推理,得到了一系列在逻辑上无矛盾的新的定理,并形成了新的理论。这个理论像欧氏几何一样是完善的、严密的几何学。
  1. 黎曼几何
    对于三维空间,有以下三种情形:
  • 曲率恒等于零
  • 曲率为负常数
  • 曲率为正常数

前两种情形分别对应于欧几里得几何学和罗巴切夫斯基几何学,而第三种情形则是黎曼本人的创造,它对应于另一种非欧几何学。黎曼的这第三种几何就是用命题“过直线外一点所作任何直线都与该直线相交”代替第五公设作为前提,保留欧氏几何学的其他公理与公设,经过严密逻辑推理而建立起来的几何体系。这种几何否认“平行线”的存在,是另一种全新的非欧几何,这就是如今狭义意义下的黎曼几何,它是曲率为正常数的几何,也就是普通球面上的几何,又叫球面几何。

椭圆曲线

定义:一条椭圆曲线就是一组被 \(y^2 = x^3 + ax + b\) 定义的且满足 \(4a3+27b2≠0\) 的点集。

椭圆曲线加法(非有限域):
在椭圆曲线上取一点P(Xp,Yp),再取一点Q(Xq,Yq),连接P、Q两点作一条直线,这条直线将在椭圆曲线上交于第三点G,过G点作垂直于X轴的直线,将过椭圆曲线另一点R(一般是关于X轴对称的点),R点则被定义为P+Q的结果,既P+Q=R:
椭圆曲线加法(有限域):
公式如下
Xr = (λ² - Xp - Xq) mod p
Yr = (λ(Xp - Xr) - Yp) mod p
椭圆曲线乘法:
乘法简化成加法

伽罗瓦域

有限域亦称伽罗瓦域(galois field),是仅含有限个元素的域,它是伽罗瓦(Galois,E.)于18世纪30年代研究代数方程根式求解问题时引出的.有限域的特征数必为某一素数p,因此它含的素域同构于Zp.若F是特征为p的有限域,则F中元素的个数为pⁿ,n为某一正整数.元素个数相同的有限域是同构的.因此,通常用GF(pⁿ)表示pⁿ元的有限域.GF(pⁿ)的乘法群是(pⁿ-1)阶的循环群.

有限域椭圆曲线点的阶

如果椭圆曲线上一点P,存在最小的正整数n使得数乘 \(n P = O ∞ ​\) ,则将n称为P的阶
若n不存在,则P是无限阶的.

加密原理

考虑 \(K=kG\) ,其中K、G为椭圆曲线Ep(a,b)上的点,n为G的阶(\(nG=O∞ \)​ ),k为小于n的整数。则给定k和G,根据加法法则,计算K很容易但反过来,给定K和G,求k就非常困难。因为实际使用中的ECC原则上把p取得相当大,n也相当大,要把n个解点逐一算出来列成上表是不可能的。这就是椭圆曲线加密算法的数学依据 。

  • 点G称为基点(base point)

  • \(k(k<n)\) 为私有密钥(private key)

  • K为公开密钥(public key)

    下面是利用椭圆曲线进行加密通信的过程:

    1. 用户A选定一条椭圆曲线Ep(a,b),并取椭圆曲线上一点,作为基点G。
    2. 用户A选择一个私有密钥k,并生成公开密钥K=kG。
    3. 用户A将Ep(a,b)和点K,G传给用户B。
    4. 用户B接到信息后 ,将待传输的明文编码到Ep(a,b)上一点M(编码方法很多,这里不作讨论),并产生一个随机整数r(r<n)。
    5. 用户B计算点 \(C1 = M + r K \)和\(C2 = M + r K \)。
    6. 用户B将 C 1 、 C 2传给用户A。
    7. 用户A接到信息后,计算 \(C 1 − k C 2\) ​,结果就是点M。再对点M进行解码就可以得到明文。 因为\( C 1 − k C 2 = M + r K − k ( r G ) = M + r k G − k r G = M\)

密钥交换ECDH

ECDH使得交换双方可以在不共享任何秘密的情况下协商出一个密钥。密钥磋商过程:
假设密钥交换双方为Alice、Bob,有相同的椭圆曲线。

  1. Alice生成随机数私钥a,计算a*G。 生成Alice公钥
  2. Bob生成随机数私钥b,计算b*G。 生成Bob公钥
  3. Alice将公钥aG和基点G传递给Bob。窃听者C可以获取公钥aG和基点G。
  4. Bob将bG传递给Alice。同理,窃听者C同样可以获得bG。
  5. Bob收到Alice传递过来的公钥a*G,计算Q =baG;
  6. Alice收到Bob传递的公钥b*G,计算Q=abG,窃听者C可以获得G、aG、bG但是得不到abG

签名

用私钥 a 对消息 m签名,得到的结果是两个整数 (r,s),计算过程如下。

  1. 随机生成临时私钥 k,并计算其对应的公钥 K=k⋅G=(xK,yK)
  2. 计算 \(r=xK mod n\),若 r为 0,则回到第一步
  3. 计算消息 m的哈希 e=hash(m),并将 e的二进制序列转成一个整数
  4. 计算\( s=k−1(e+ra)modn\),若 s为 0,则回到第一步
  5. 得到签名 (r,s)

热门相关:我的治愈系游戏   前任无双   道君   花月颂   锦乡里