RSA体制是PKI最出名的体制,其他两种著名的公钥体制是离散对数体制和椭圆曲线体制(后续会慢慢介绍这两种体制的本质)。在介绍RSA体制前,先做一些简单的数学知识介绍。
众所周知,RSA算法的安全性基于将一个大数(非素数)分解为素数因子是及其困难的,可是大家可能并没有想过一个数(非素数)为什么一定可以因式分解,在很多人看来或许这是个无需证明的推论。此处我也不准备证明这个推论,不过我给出这个推论的严格定义,该推论名为算术基本定理(具体的证明,大家可以用数学归纳法证明),算术基本定理的定义如下:
至于因式分解的复杂度具体多少,因为本人水平有限,无法给出具体的推论以及证明。接下来我简单介绍一下RSA算法。
密钥生成:
1. 生成两个长度相等的随机大素数 p, q
2. 计算 n = pq, φ(n) = (p - 1)(q - 1),此处gcd(p, q) = 1,所以欧拉函数的值等于(p - 1) * (q - 1),具体欧拉函数的一些推论以及证明有机会和大家讨论
3. 随机选择整数 e,e 满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1
4. 计算整数 d, d 满足 1 < d < φ(n),ed ≡ 1 (mod φ(n)),≡为同余符号
5. (n, e) 为公钥,d 为私钥
私钥签名:
1. h = H(m),其中 H 是任意一个杂凑函数(比如sm3,md5),m为明文
2. s = h ^ d mod n,s 即为签名结果
公钥签名验证:
1. h = H(m), m 为明文
2. h1 = s ^ e mod n, s 为签名结果
3. if h == h1 return true else return false
具体的实现还需要加入一些随机值来保证安全性,为了性能考虑还会引入蒙哥马利等算法提升性能,具体的细节有机会和大家讨论,接下来我简单证明一下签名和验签:
因为 ed ≡ 1 (mod φ(n)), 所以 ed = mφ(n) + 1
因为s = h ^ d mod n, 所以 h ^ d ≡ s (mod n)
因为 h ^ d ≡ s mod n, 所以 s = h ^ d - kn, k 为整数
因为 h1 = s ^ e mod n,所以 s ^ e ≡ h1 mod n
因此要证明签名验证算法的正确性只需证明 h ≡ s ^ e mod n
因为 s = h ^ d - kn,所以代入式中得 h ≡ (h ^ d − kn) ^ e mod n
因为 kn 是 n 的倍数,所以只需证明 h ≡ (h ^ d ) ^ e mod n 即可
因为 ed = mφ(n) + 1,所以只需证明 h ≡ h ^ (mφ(n)+1) mod n 即可
因为 h ≡ h ^ (mφ(n)+1) mod n, 所以只需证明 h ≡ h1 h ^ (φ(n) ^ m) mod n 即可
根据欧拉定理 a ^ φ(n) ≡ 1 mod n 可得 h ≡ h 1 mod n,至此,证明完毕
灌水贴,大致扯了一下RSA算法,有机会和大家好好讨论