RSA公钥加密算法笔记

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 % N
C^e2 = M^(e1e2) % N
欲使C^e2 % 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) × 1^k(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