RSA算法由来

RSA公钥加密算法是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。1987年7月首次在美国公布，当时他们三人都在麻省理工学院工作实习。RSA就是他们三人姓氏开头字母拼在一起组成的。

RSA算法公式

根据密钥的使用方法，可以将密码分为对称密码和公钥密码

对称密码：加密和解密使用同一种密钥的方式

公钥密码：加密和解密使用不同的密码的方式，因此公钥密码通常也称为非对称密码。

RSA的加密过程可以使用一个通式来表达

也就是说RSA加密是对明文的E次方后除以N后求余数的过程。

从通式可知，只要知道E和N任何人都可以进行RSA加密了，所以说E、N是RSA加密的密钥，也就是说E和N的组合就是公钥，我们用(E,N)来表示公钥

不过E和N不并不是随便什么数都可以的，它们都是经过严格的数学计算得出的。这里需要注意的是：E是加密（Encryption）的首字母，N是数字（Number）的首字母。

RSA算法定理

设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则:

C1 = P^e1mod n

C2 = P^e2 mod n

一、任何大于1的整数a能被因式分解为如下唯一形式:

a=p1p2…pl(p1,p2，…，pl为素数)

二、模运算

①{[a(mod n)]×[b(mod n)]}modn≡(a×b)(mod n)

②如果(a×b)=(a×c)(mod n),a与n互素，则

b=c(mod n)

三、费马定理

若p是素数，a与p互素，则

a^(p-1)≡1 (mod p)

四、欧拉定理

欧拉函数φ(n)表示不大于n且与n互素的正整数的个数。

当n是素数，φ(n)=n-1。n=pq,p,q均为素数时，则φ(n)= φ(p)φ(q)=(p-1)(q-1)。

对于互素的a和n，有a^φ(n)≡1(mod n)

RSA算法应用

数据传输

RSA的非对称特性用于数据传输很合适，这里生成了公钥给客户端，私钥放在服务器端用于解密传输过来的信息。

openssl genrsa -out rsa_private_key.pem 1024openssl rsa -in rsa_private_key.pem -pubout -out rsa_public_key.pem

生成公钥私钥，公钥给客户端，JS调用去加密，加密后的数据是乱码没有办法直接输出，因此需要base64进行编码。

Web登录密码加密传输

使用了RSA非对称加密算法，加密所用的密钥和解密所用的密钥是不相同的。简单来说就是：你使用我的公钥加密，我使用我的私钥来解密；如果你不使用我的公钥加密，那我无法解密；如果我没有私钥，我也没法解密。

RSA算法安全性

RSA是目前最有影响力和最常用的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。

RSA算法缺点

当然，作为一个加密算法，不管它有多强大，总还是有缺点的，下面小编就罗列了一些它的缺点，仅供参考哦！

产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。

安全性，RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NP问题。

速度太慢，由于RSA 的分组长度太大，为保证安全性，n 至少也要 600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级;且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。

不断接触之后，我们就会发现数学真的是一个很美妙的东西，只要我们足够了解它，就可以利用它来完成许多无法想象的事情；其实研究算法也好，编写代码也罢，不过都是我们为完成自己的美好想象不断探索的过程，因为有了这个过程才有了不断完善进步的创新，你说是吗？