RSA算法原理
数论的一些知识
欧拉函数 φ(x)
将不大于正整数 m 且与之互素的正整数个数称之为欧拉函数，记为 φ(m)
欧拉定理
设正整数 m 与整数 a 互素，则
aφ(m) ≡ 1 (mod m)
欧拉函数的积性
定义：设正整数 m 与 n 互素，若 f(mn) = f(m) f(n)，则称数论函数 f 为积性函数
->定理：设正整数 n 有素分解式 n = p1a1 p2a2 … psas，则积性函数 f 的函数值
f(n) = f(p1a1) f(p2a2) … f(psas)
φ(x) 的计算
定理1 若 p 为素数，则 φ(p) = p - 1；反之，若自然数p满足等式 φ(p) = p - 1，则 p 是素数
定理2 若 p 为素数，a 为正整数，则
φ(pa) = pa - pa-1
定理3 设正整数 n 有素分解式 n = p1a1 p2a2 … psas，则
φ(x) = n (1-${1\over p_{1}}$) (1-${1\over p_{2}}$) … (1-${1\over p_{s}}$)
定理4 设 n 是大于2的正整数，则欧拉函数 φ(x) 是偶数
模反元素
若两个正整数 a 和 n 互素，那么必有整数 b，使得 ab ≡ 1 (mod n)。此时，称 b 为 a 的”模反元素“
证明：由欧拉定理知
aφ(n) ≡ 1 (mod n)
那么至少有 b = aφ(n)-1，满足
ab = a * aφ(n)-1 = aφ(n) ≡ 1 (mod n)
所以正整数 a 和 n 互素的前提下，a 的模反元素 b 一定存在
模反元素没有唯一性
证明：已知 b = aφ(n)-1 是 a 的模反元素
ab ≡ 1 (mod n) <=> ab = kn + 1 ( k ∈ Z )
令 t = k - a
ab = ( t + a )n + 1
a( b - n) = tn + 1
即 a( b - n) ≡ 1 (mod n)
那么 (b - n) 也是 a 的模反元素，而且同样构造于 mod n 上
费马小定理
若素数 p 不整除正整数 a ，则
ap-1 ≡ 1 ( mod p )
以上所有内容看不懂请从头学习《初等数论》
密钥的生成
Step 1：随机选两个不相等的质数 p 和 q
一般这两个质数越大安全性越高
Step 2：计算 p * q = n
n 转换为二进制的位数即为密钥长度
Step 3：计算欧拉函数 φ(n)
算法如上所示
Step 4：随机选择一个整数 e（1< e < φ(n)，e 与 φ(n) 互素）
常用建议的是 65537
Step 5：计算 e 对于 φ(n) 的模反元素 d
e 与 φ(n) 互素，由模反元素定义知，存在 d 满足
ed ≡ 1 (mod φ(n))
可以利用扩展欧几里得算法求解
Step 6：公钥和私钥
公钥： n 和 e
私钥： n 和 d
加密解密
约定明文为 M，密文为 S
加密：
使用到公钥 ( n , e )
C ≡ Me ( mod n )
解密：
使用到私钥 ( n , d )
M ≡ Cd ( mod n )
证明：由加密方程知
Me + remainder = C + kn + remainder
C = Me - kn
代入解密方程右半：
( Me - kn )d mod n = Med mod n
由于 ed ≡ 1 (mod φ(n))，故
ed = hφ(n) + 1
代入上式：
Cd ≡ Mhφ(n)+1 (mod n)
(1) 若 M 与 n互素：
由欧拉定理知
Mφ(n) ≡ 1 (mod n)
Mφ(n) = kn + 1
( Mφ(n) )h = ( kn + 1 )h ≡ 1 ( mod n )
Mhφ(n)+1 ≡ M ( mod n )
(2) 若 M 与 n 不互素：
由于 n 有唯一素分解式 n = p * q
则 gcd( M , n ) = p 或 gcd( M , n ) = q
不妨：gcd( M , n ) = q ； M = k * p
由费马小定理：
mq-1 ≡ 1 ( mod q )
使用欧拉定理同上：
( Mφ(q) )h(p-1) = ( kq + 1 )h(p-1) ≡ 1 ( mod q )
-> ( Mq-1 )h(p-1) ≡ 1 ( mod q )
已知
φ(n) = ( p - 1 )( q - 1 )
ed = hφ(n) + 1
-> Med-1 ≡ 1 ( mod q )
-> Med-1 = sq + 1
-> Med = sqM + M
M = k * p
-> Med = sqkp + M
-> Med = skn + M
-> Med ≡ M ( mod n )
综上所述，解密方程 M ≡ Cd ( mod n ) 成立
RSA算法的安全性
解密的关键在私钥中的模反元素 d
ed ≡ 1 (mod φ(n))
要求出 d 必定需要知道 φ(n)
在公钥中可以获得 n ，但是不知道 p 和 q 的情况下，只能依靠
1. 计算 n 的素分解式 p ，q
2. 迭代验证 0 ~ n 中与 n 互素的整数个数
事实是，在 n 的素分解式未知的情况下几乎不可能在可接受时间内获得d，
所以认为算法是安全的
但是针对不恰当的参数设置，RSA有可能被破解，详细方法可以参考以下资料