非对称加密及RSA算法

非对称加密及RSA算法

最近在学习区块链相关的知识，发现其保证去中心化的一个重要的手段就是基于密码学中的非对称加密。

何为非对称加密？

在回答这个问题之前，我觉得有比说一下对称加密。所谓对称加密，就是加密和解密都使用同一个密钥。那么很显然，非对称加密就是加密和解密使用不同的密钥。

非对称加密有两个密钥：公钥和私钥，公钥是公开的，私钥是私密的，公钥加密的可以用私钥解开，私钥加密的东西可以用公钥解开，即加密和解密的密钥是不同的。举个例子，甲要发信息给乙，那么甲可以使用乙方的公钥对机密信息进行加密签名后发送给乙方，乙方收到数据后用自己的私钥对数据进行解密。

好了，非对称加密的概念我们很好理解，那么具体如何实现非对称加密呢？

常用的加密算法有​​RSA​​​、​​Elgamal​​​、背包算法、Rabin、D-H、​​ECC​​（椭圆曲线加密算法）。其中，使用最广泛的是RSA算法。下面我们就具体介绍一下RSA算法，主要参考博客​安全体系（二）——RSA算法详解。​​

RSA

算法来源

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

数学基础

质数：除了1和它自己不能被别的数整除，这个数就是质数。

互质：两个正整数，除了1以外，没有其他公因子，那么这两个数就是互质的。

欧拉函数：对于任意一个正整数n，如果n=p₁^k1p₂^k2…p_r^kr，其中，p¹,p²,…,p^k为质数，那么在小于n的正整数中，可以用下面的公式求解与n互质的数的个数：   

φ(n)=n(1-1/p₁)(1-1/p₂)…(1-1/p_r)

欧拉定理：如果a和n互为质数，则a^φ(n)≡1(mod n)，其中φ(n)为n的欧拉函数。

模反元素：如果两个正整数a和n互质，那么一定可以找到整数b，使得ab-1被n整除，或者说ab被n除的余数是1。这时b被称为a的模反元素。用公式表示为：ab≡1(mod n)。

算法过程

密钥生成

1、选择两个不同的质数p和q；

2、计算两者的乘积为n，将n转换成二进制后，二进制的长度即为密钥的长度；

3、计算n的欧拉函数φ(n)；

4、选择整个e，其中φ(n)>e>1，且e与φ(n)互质；

5、计算e对φ(n)的模范元素d；

6、将n和e封装成公钥，将n和d封装成私钥。

加密

m^e=c(mod n)，其中m为需要加密的信息，c为加密后的信息。

解密

m^e=c(mod n)，其中c为解密前的信息，m为解密后的信息。