非对称加密有两个密钥：公钥和私钥，公钥用来加密数据，私钥用于解密
他们都源于一个公共原理：单向函数
单向函数的定义：
函数 f() 是一个单向函数，当且仅当：
- y = f(x) 计算比较容易
- x = f' (y) 计算是不可行的(需要的时间太长)
目前的公钥方案中主要使用了两个主流的单向函数：
- 大整数的因式分解
- 离散对数问题（DLP问题）
本文主要介绍 RSA 跟 ECC 这两种非对称加密算法
RSA
安全建立在基于大整数的因数分解问题（即对 N 的质因数分解求 p、q）
密文 = 明文^E (mod N)
对明文的加密过程就是明文的 E 次方对 N 求余，知道了 E 和 N 就可以对明文进行加密了，所以 E 和 N 的组合就是公钥
明文 = 密文^D (mode N)
对密文的解密过程就是密文的 D 次方对 N 求余，知道了 D 和 N 就可以对密文解密了，所以 D 和 N 的组合就是私钥
生成密钥对过程：
- 生成 N
N = p * q ( p和q为质数 )
L = lcm(p-1,q-1) ( lcm 为求最小公倍数 ) - 生成 E
1 < E < L
gcd(E,L)=1 ( gcd 为求最大公约数 ) - 生成 D
1 < D < L
E * D (mod L) = 1
ECC
基础知识
模运算
a = r (mod m) , r为余数，m为模数，r<m
例：42= 6 (mod 9)
群
群指的是一个元素集合 G 以及 两个元素值之间的操作 o 的集合，即 (G，o)：
- 群操作 o 是封闭的，即对所有的 a b，a b 属于G, a o b = c，c 也属于 G。
- 群操作 o 是可结合的，即 ao(boc) = (aob)oc。
- 存在一个元素 1 ，对所有的 a ，a 属于 G，均满足 a o 1 = 1 o a = a ，这个元素叫中性元或单位元
- a o a' = a' o a = 1，a’叫做 a 的逆元
- 如果 a o b = b o a，则群 G 为阿贝尔群或可交换群
有限群：
一个群 (G,o) 是有限的，仅当他拥有有限个元素，G 的基或阶可以表示为 |G|
密码学中使用的一般就是有限群
群的基或阶其实就是群元素的个数
例如：（Zn，+）Zn 的基为 |Zn|=n，因为 Zn = {0，1，2，... ，n-1}
元素的阶：
是指满足以下条件的最小正整数 k：
ord(a) = a^k = a o a o a .....a = 1 ,1 是单位元
循环群：
如果群 G 包含一个拥有最大阶 ord(x) = |G| 的元素 x，则这个群是个循环群，拥有最大阶的元素成为生成元。
这个 x 的幂值可以表示整个群
例：Z11 = {1，2，3，4，5，6，7，8，9，10}
x = 2 为生成元
基为 |Z11| = 10
2^10 = 1 (mod 11), 2的阶为10，即ord(2) = |Z11|
2 的幂值生成了所有元素
定理：
每个素数 p，( Zp,* )都是一个阿贝尔有限循环群
该定理说明每个素数域的乘法群都是循环群，对于构建离散对数密码体制非常重要
Hasse's定理：
给定一个曲线E mod p ，曲线上的点的个数表示为 #E 则：
p+1-2√p<=#E<=p+1+2√p
离散对数问题
基于Zp的离散对数问题（DLP）：
给定一个阶为 p-1 的有限循环群Zp，生成元为 a，b为另一个元素，DLP问题就是确定满足以下条件的整数 x（ 1 <= x <= p-1 ）的问题：
a^x = b (mod p)
当参数非常大的时候，求解 x 非常困难
推广的离散对数问题：
给定一个基为 n 的有限循环群 G，群操作为 o。生成元为a，b为另一个元素，DLP问题就是找到x（1 <= x <= n）使得：
a^x = a o a o a .... o a = b
椭圆曲线离散对数问题：
给定一个椭圆曲线E，群操作为+，生成元 G，T为另一个元素，dl问题就是找到 k(1 <= k <= #E) 使得：
kG = G + G + G +...+G = T
公钥密码体制正是找到了这样的一个群是的DLP问题成为了一个单向函数
应用在密码学中的椭圆曲线
基于椭圆曲线的非对称加密，跟 rsa 相比，密钥更短，强度更高
安全建立在基于椭圆曲线的离散对数问题，是一种推广的离散对数问题
- 二元三次曲线 y^2 = x^3 + a * x + b (mod p) （其中p为大质数）
- 定义的运算 P + Q = R,都是曲线上的点
循环群为椭圆曲线上的点，群操作为 +
抽象的无穷的点 0 为单位元，满足 P+0 = P
逆元 P+(-P) = 0，满足 -P = （Xp，p-Yp）
secp256k1曲线
基本参数：
-
离散曲线： y^2 = (x^3 + 7) mod p（其中x和y都是整形保证了离散）
p=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a=0
b=7 -
基点 G
G("0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798",
"483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8") -
点的集合 {G，2G，3G，... ，nG}，nG=O，O 为抽象的无穷点即单位元
n="0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141"
私钥生成公钥原理：
在上边的离散的椭圆曲线上，定义一套运算规则：
加法：P+Q = R
乘法： K=kG
k 为私钥，K 为公钥{r,s}，G为曲线上一点。
由 k、G 算 K 简单，由 K、G 推出 k 极难。
网友评论