背景
- 突然有人这么一给我干蒙了！
非对称首先想到的是 RSA DSA
- RSA 也是我们比较熟悉的对称算法 也用的比较多 私钥 公钥
- 比如 gitlab ssh
- openssh、生成秘钥、rsa秘钥
- DSA 用的少 也是非对称的签名算法 也要用到公钥红河私钥
另外一个不常用的 非对称算法 ECC
- 基于椭圆曲线的算法
- 资料参考 1 ECC椭圆曲线加密算法：介绍
- 资料参考 2 ECC椭圆曲线加密算法：有限域和离散对数
- 看的我云里雾里 关键点 椭圆曲线 、群、基点
下面简单的验证一下 RSA的概念的计算过程
- 原理：基于大数分解困难的 和欧若拉函数 来实现的
- 例如 两个质数A,B 相乘得到一个 P 但是你很难P推断出两个质数
- 公钥私钥的过程演示：
- 1 选择两个质数p 和 q 计算乘积
- 例如 ：phi(12) = 4 有四个质数 1、5 、7 、 11
- 随机选择两个 p= 7 、p= 11 即n= 7 * 11 = 77
- 2 计算欧公式 phi(n) = (p-1)(q-1) : (7-1) * (11-1) = 60
- 3 选择选择一个整数 e作为公钥且 1 < e < phi(n) 并且和phi(n)互质
- e 选取为 17 得到公钥（n,e）= (77,17)
- 4 计算私钥d 满足ed ≡ 1(mod phi(n)) 即：d为e的模phi(n)的逆元
- 使用拓展欧力几德算法得到： d=53 得到私钥（n,d）= (77,53)
- 5 使用公钥对明文进行加密 ，得到密文C = M^e（mod n）
- 选择 M =25 C = b^e(mod n) = 00011001 ^ 17(mod 77) = 59
- 6 使用私钥对密文进行解密 ，得到密文M = C^d（mod n）
- 选择 C = 59 M = C^e(mod n) = 59^ 53 (mod 77) = 25
下面简单的验证一下 ECC 的概念的计算过程
-
ECDH 是对DH和ECC算法改进和拓展
-
ECDSA 也是对DSA和ECC算法改进和拓展
-
ECC原理：利用椭圆曲线在在有限的上的离散对数
- 任意取椭圆曲线上两点P、Q 做直线（若P、Q两点重合，则做P点的切线），
- 交于椭圆曲线的另一点R，那么规定 P + Q + R = 0，也就是 P + Q = - R。
- P+Q 做椭圆运算 ，给定的n和p则有最高次幂的算法来计算Q=nP 可以算出Q
- 但是如果Q和P，需要找到n呢？就很难，这就是离散对数数学问题
-
公钥私钥的过程演示：
-
1 选择合适的椭圆曲线E 也就是二元方程（至关重要不可泄露）
- 例如 y²= x³+ax+b
- a、b为常数 a=1 、b = 6 得到 y²= x³+x+1
-
2 选择一个点G作为基点且G必须满足其阶n位素数 （至关重要不可泄露）
- 在有限域上计算在模数p情况下得到
- x =0 ,y² =6 不满足整数解
- x =1 ,y² = 8 不满足整数解
- x =2 ,y² =16 解为y=4或y=-4，其中y=4满足方程
- 在有限域上计算在模数p情况下得到
-
选定一个起点G，可以是椭圆曲线上的任意一点；
- 选择起始点为 G = (0,1)，私钥为 n = 5，已知椭圆曲线上的点为（2,4）
- G = (0,1)；
- n = 5；
- 选择起始点为 G = (0,1)，私钥为 n = 5，已知椭圆曲线上的点为（2,4）
-
4 计算公钥 P = nG
- 2G = (2,-3)
- 3G = (0,-1)
- 4G = 自相撞
- 5G = 4G + G = 自相撞
- 得到 P = nG = 5G = (0,-1)
-
5 计算私钥 Q = n(x,y)
- 2n = (2,4) + (2,4) = (3,3)
- 3n= 自相撞
- 4n = 自相撞
- 5n = (3,3) + (2,4) = (6,10)
- 得到 Q = n(x,y) = 5(2,4) = (6,10)
-
6 使用公钥对明文进行加密
- 首先选择一个随机数 k，例如 k = 17。
- 第一部分 ： 计算点 C = kP = 17(0,-1) = (8,15)
- 第二部分： s = kQ + m = 17(6,10) + 123 = (195,343)
- 完整密文 (C,s) = ((8,15),(195,343))
-
7 使用私钥对密文进行解密
- 对点 C 进行 k 倍的计算得到 kP = 17(0,-1) = (8,15)。
- 计算 s - kQ = (195,343) - 17(6,10) = 123