RSA是目前最有影响力和常用的公钥加密算法
这篇笔记目的是梳理RSA算法加解密的证明思路
RSA算法是一种非对称密码算法,所谓非对称,就是指该算法需要一对密钥,若使用其中一个进行加密,则需要另一个才能解密。
RSA算法涉及3个参数: n, e1, e2
其中要求:
-
①n是两个大质数p,q的积,n的二进制表示时所占位数即密钥长度 -
②e1, e2是一对相关的值,e1可任意取，但要求与(p-1)(q-1)互质 -
③再选择e2,要求(e1e2) ≡ 1 (mod(p-1) * (q-1))
这里我们假设有A B 2个对象，A要利用RSA算法向B发送数据。
(N, e1)是B公共登记的或是其它可访问文件里的公钥，(N, e2)是B本地的私钥
M (message) 是A要发送的明文数据，C (ciphertext)是密文,简单应有如下关系
即A将数据通过公钥(N, e1)加密后得C，将C发送给B，B需要通过私钥(N, e2)解密可以还原得到M。
于是自然有公式
C = M^e1 % NC^e2 = M^(e1e2) % N欲使Ce2 % N = M, 即需使得 M(e1e2) % N = M，也即
M^(e1e2) ≡ M % N ④现在我们看前提③，即 e1e2 ≡ 1 (mod(p-1) * (q-1))
再往前看前提①，即N是2个大素数p,q的积。那么有多少个与N互素且比N小的数呢？这个数被称为欧拉函数φ(N)。逆向思考，与N不互素的数有多少？对于N，不互素的数有
1p, 2p, 3p,....,(q-1)p
1q, 2q, 3q,....,(p-1)q
上面总共有(q-1) + (p-1)个，那么由于互补，与N互素的数有(pq - 1) - [(q-1)+(p-1)],即
(p-1)(q-1)个，那么前提③，其实就是 e1e2 ≡ 1 mod φ(N)上式的另外一种表述方式：存在整数k满足
e1e2 = kφ(N) + 1
回头看式子④，可以得知，我们现在的目的就是去证明
M(kφ(N)+1) ≡ M % N
首先看2个关于模算数的基本结果和欧拉定理：
[(a % n) × (b % n)] % n = (a × b) % n
可知若x % n = 1, 则 x^y % n = 1， 同理若 x % n = 0, 则x^y % n = 0
[(a % n) - (b % n)] % n = (a - b) % n
欧拉定理：若a与n互素，则有 a^(φ(n)) mod n = 1
要证明M(kφ(N)+1) ≡ M % N， 而N=pq,我们从N的因子p入手。首先证明M(kφ(N)+1) ≡ M % p
- 若M和p不互素，即M % p= 0,则 M(kφ(N)+1) ≡ M % p
- 若M和p互素。由欧拉定理M(φ(p)) % p = 1
M(kφ(N)+1) % p = [M× M(p-1)k(q-1)] % p
= (M % p) × [M^(φ(p)) % p] k(q-1)
= (M % p) × 1k(q-1) = M % p
由上两项证明可知 M(kφ(N)+1) ≡ M % p
可得 [M(kφ(N)+1) - M] % p = [M(kφ(N)+1) % p - M % p] = 0
根据同样的证明可得 [M(kφ(N)+1) - M] % q = 0。 又因为p ≠ q，所以必然存在一个整数r使得 M(kφ(N)+1) - M = (pq)r=Nr
即 [M(kφ(N)+1) - M] % N = 0 即 M(kφ(N)+1) ≡ M % N
