RSA加密算法

rsa加密算法是一种典型的非对称加密算法，他的可靠性源于对极大整数做因式分解的高难度。

rsa密钥生成过程

选两个质数p,q
N=p*q
计算φ(N)（φ(N)是指小于等于n的正整数里所有与n互质的数的总和）
根据欧拉公式，由于p和q都是质数，φ(N)=（p-1)(q-1)
随机取一个质数e，使e满足1 < e < φ(N)
求一个整数d，使d满足 e*d ≡ 1 (mod φ(N)), 也就是 e*d -1 = kφ(n)
(N,e)作为公钥, (n,d)作为私钥
通过摘要算法将消息转化为m
则密文x=m^e%n
原文m=x^d%n

算法证明

m=x^d%n
m=(m^e%n)^d%n
根据模计算公式：
(a^b)%n=(a%n)^b%n
所以有：
(m^e%n)^d%n=((m^e)^d)%n=(m^e*d)%n
也就是证明:
(m^e*d)%n-m=0
由已知条件可知：
e*d-1=kφ(n)
而φ(n) = (p-1)(q-1)
所有也就是证明：
m^(1+kφ(n))%n-m=0
m^(k(p-1)(q-1)+1)%n-m=0
m(m^(k(p-1)(q-1))-1)%n=0(m>n)
根据费马小定理：
a^(p-1)%p=1(p是质数）
所以有：
m^(k(p-1)(q-1))-1可以整除p和q，也就是说可以整除p*q
而p*q=N
所以m^(k(p-1)(q-1))-1可以整除n
所以m(m^(k(p-1)(q-1)-1)%n=0
证明结束

安全性分析

根据以上证明过程可知，如果公钥n,e,以及密文x被截获到, 要想获取原文，需要得到d, 而要想得到d, 需得到φ(n), 要想知道φ(n)，则需要知道p和q，而要想得到p,q, 最快的办法就是对n进行因式分解.

但如果p,q选的足够大的话，对n进行因式分解是很耗时的，所以，p和q只要选的足够大，那么rsa就足够安全(虽然目前理论上并没有否认有对大整数进行快速因式分解的可能).