前言
目前主流的非对称加密算法主要有几类:RSA、DHKE、Elliptic Curve。
虽然大类分成这几类,实际上他们底层的原理都是依赖于素数和同余原理来做的。素数是除了他本身和1以外,无法被其他任何正整数整除的数字。这样的数字有多少呢?无穷个。我们知道,一个数字的因式分解,最终都能分解成n个素数的相乘,由于素数有无穷多个,也就意味着一些巨大的数是很难分解的,特别是两个大的素数(例如几百位、上千位)的乘积就更难因式分解了,催生了很多在理论上不可行,但在经济上可行的加解密算法。为什么说是理论上不可行呢?因为数字再大,只要有恒心(例如几百年、上千年甚至几百亿年)总能把一个大数因式分解,也就是基本假设不成立,一旦能因式分解,所有的这类密码都将被破解。经济上可行是因为,因式分解一个这样的大数字花费的经济成本(计算机、电力等)太高,以至于不会有人去尝试暴力破解。当然,据说有可以破解这类的量子算法,基于量子计算机多维度并发计算,还是有机会的。目前量子计算机造价昂贵且还没有大规模商用,用于破解这类的密码成本也是相当高的,暂时还是安全的。对应的策略是,a:发明后量子加密算法,在量子计算机流行之后也能用后量子算法来加解密,保障量子计算机破解不了这类的密码;b:用量子纠缠实现通信,可以完全杜绝中间人攻击,此时密钥不是最重要的了。目前美国为主的西方国家主要在主导后量子密码学,而我国科学家更多在主导量子通信。
下面我会用相对易懂的预言推导一下这几类算法的原理,一些不太好理解的定理,不会太深入去推导。
1、RSA非对称加解密的基本原理
a)基本假设与前提:两个大素数的乘积无法(轻易地)被因式分解
b)算法实现:
1)随机生成两个大的素数,p、q
2)令 n = p * q,另 N = (p-1) * (q-1)
3)从 在 (1, n-1)区间内,找到一个随机数d
4)找到一个 e,满足 e * d ≡ 1 mod N
此时,d 与 n 结合就形成了私钥,记为 pubk = (d,n); e 与 n 结合形成私钥,记为 priv = (e, n)
假设有消息m
公钥加密过程,E(m) = m^e % n => 密文记为 c
私钥解密过程,D(c) = c^d % n =(m^e)^d % n = m^(ed) % n
由于 e * d ≡ 1 mod N, 所以 D(c) = m^(ed) % n = m ^ (1 mod N) % n = m % n (同余定理)
ed ≡ 1 mod (p-1) * (q-1) , 由于 p-1 与 q – 1 分别与 n 互质 (最大公约数为1), 所以 m ^ (ed) % n ≡ m ^ (1 % (q-1)*(p-1)) % n ≡ m % n (这句推导很魔幻,我看不懂,但大受震撼) , 从而解密过程无需知道p、q就能解密得到原文m。
示例代码可以从我的gist中找到,地址(https://gist.github.com/jiacheo/c01ca88ee308a8fe8293452cc71fdcb5)
2、DHKE 密钥交换的基本原理
DHKE严格上讲其实不是非对称加密算法,因为这个算法是通过非对称的方式来交换密钥,而最终通信双方使用相同的密钥来做对称的加解密。
算法原理如下:
先约定两个所有人都知道的素数 p、g,其中 p > g
通信双方,假设为A和B
A生成一个随机数a,B生成一个随机数b
A本地计算 d1 = g^a mod p
B本地计算 d2= g^b mod p
AB交换d1,d2(这时d1、d2可能被第三方窃取,但没关系)
A拿到d2计算 s = d2 ^ a mod p
B 拿到 d1 计算 s` = d1 ^ b mod p
可以看出 s = d2 ^ a mod p = (g ^ b) ^ a mod p = g^ab mod p
s` = d1 ^ b mod p = (g ^ b ) ^ a mod p = g ^ ab mod p == s
也就是A、B双方共同拿到了密钥s,后续通信可以通过s来进行。
假设中间有AB交换d1/d2的时候被窃取了,由于窃取的人不知道 a和b、所以无法计算出s,也就无法知道他们约定的密钥是什么了。
示例代码也可以从我的gist中找到,地址(https://gist.github.com/jiacheo/3dd14d4be509fb7f945b926cf237a921)
3、Elliptic Curve 椭圆曲线非对称加密的基本原理
a) 首先,先弄明白什么是椭圆曲线。
椭圆曲线是诸如 y2 = ax3 + bx + c 的一条曲线,其中a、b、c为常数。例如比特币的签名认证算法选用的就是 y2 = x3 + 7 的曲线,该曲线画出来大致长这样:
该曲线有以下特性(推导过程省略,知道他有这些特性就行了)
1)曲线是关于x轴对称的。
2)对曲线上任意两个非对称点做一条直线,该直线一定会和曲线相交与某一点
3)对曲线上任意一点(y = 0的点除外)做切线,该切线一定会和曲线相交与某一点
b)知道了曲线,我们定义一下曲线上的加法
已知曲线上的任意两点P、Q,其中P和Q非对称,那么P + Q的结果就是特性 2) 中连接这两点的直线与曲线相交的那一个点R`关于x轴对称的点R,记为 R = P + Q。特殊情况下,P 和 G 为同一点时,引用特性 3) 的切线相交点R`关于x周对称的点R,记为 R = P + Q = P + P = Q + Q = 2P = 2Q
所以这里也定义了乘法,乘法不是点和点相乘,而是系数和点相乘,代表这个点加了多少次。 x * P 代表 P点加了x次。
其中乘法(点乘)满足 分配律(和结合律),即 (a + b) * P = aP + bP ,例如: 4P = (2+2) * P = 2P + 2P
c)接下来定义私钥和公钥
我们选一个公众已知的点G,称作为基点。私钥是一个随机整数 x, 公钥则为 X = x * G。 即公钥就是 将基点相加了 x次。 目前已经证明,通过私钥x和基点G推导出公钥X是非常迅速的,最多不超过510次加法计算(如果密钥长度选定为256bit的话,510 = 255*2);而反过来通过公钥X和基点G是无法轻易的算出私钥x的,只能通过暴力枚举的方式,基本也是不可行的做法。所以从安全性上考虑,私钥和公钥对是成立的,那么如何利用私钥和公钥做加解密呢?
d)加解密过程
加密方是公钥X持有者,现有消息m需要加密。首先,公钥持有方,生成一个随机数字 r,将m生成一个加密点 (rG, m+rX) 发送给解密方。
解密方是私钥x持有者,得到加密点(rG, m+rX) (记作 a,b) 后 ,对b值做如下运算 b – x * a = m + rX – x * rG = m + r * x * G – x*r * G = m,即可得到原文m
即:
Encrypt(m) = (a,b) = (r*G, m + r*X) ==> c
Decrypt(c) = b – x * a = m + r * x * G – x * r * G = m
由于其他的公钥持有人,不知道 r ,也不知道 x,所以无法解密。 而私钥持有人是不需要知道r就能直接解密的,所以r也不需要传播,也就没有被窃取的风险。
e)补充说明
上面的推导过程貌似没有提到素数,其实这里是对曲线理想化的操作,实际上,曲线本身是连续的,而我们基本需要的数据域只是整数(离散的),而且是有限位的整数(虽然有限,也足够多了)。所以在限定整数域的时候,会引入一些素数的能力,以实现同余运算。这里就不多展开了,但素数作为循环群的阶,是保障算法的可行性非常必要的,不能忽略。例如比特币选的素数阶就是最接近2^255的一个大素数。
发表评论
沙发空缺中,还不快抢~