RSA的算法介绍与数学原理

RSA

RSA是一种非对称加密！

非对称加密：

Alice与Bob直接传输消息，他们生成了两把钥匙，一把公钥，一把私钥，公钥给Alice，Alice使用公钥进行加密，而私钥只有Bob拥有，用来解密

加密过程：在接收消息前，Bob会生成两把钥匙，并将其中的公钥给Alice，Alice使用公钥将信息加密后传递给Bob，Bob收到信息后使用私钥进行解密，得到明文。

基本算法

1.乘法：两个质数相乘

2.伪随机数生成算法：生成伪随机数

3.Miller-Rabin测试：测试一个数是否为质数（单次测试的可信度不是特别高，需要用不同的参数进行多次独立测试）
基础理论：

（1）费马小定理：
当 p为质数，对于任意整数a, a^{p-1}\equiv 1(mod : \, p)
若a , p 互质，
且 a^{p-1}\equiv 1(mod : \, p)，不能推出 p 是质数
（如：卡迈克尔数）

（2）二次探测：如果 p是一个素数，且0,
则方程 x^{2}\equiv 1(mod: \, p)的解为 x = 1或 x = p - 1

4.快速幂：快速计算a^xmodn的值
扩展：取模运算的运算法则
(a + b)\% p = (a\% p + b\%p)\% p

(a - b)\% p = (a\% p - b\% p)\% p

(a * b)\% p = (a\% p * b\% p)\% p

a ^ b\% p = ((a\% p)^b)\% p

5.扩展欧几里得算法
欧几里得算法：
gcd(a, b) = gcd(b , a\%b)
扩展欧几里得算法：
求出ax + by = gcd的通解

数学定理

1.欧拉函数：
φ(n) 表示小于n的正整数中与n互质的数的所有个数
且若n能分解成两个质数p、q相乘就有
φ(n)=(p-1)(q-1)

2.欧拉定理：
对于任意互素的a和n，有a^{\varphi(n)}\equiv1(\mod n)

3.同余定理：
2个不同的整数a、b,被一个整数m相除时,得到相同的余数,那么可以称a、b同余
即：a≡b(mod m)

4.乘法逆元
若ab≡1(mod m)，则称a和b为关于m互为乘法逆元

加密过程

公钥:(n,e)

私钥:(n,d)

1.找到两个大质数p、q(伪随机数生成算法+Miller-Rabin算法）

2.计算两个质数的乘积并计算其欧拉函数

3.构造一个整数e
1<e<φ(n),且不等于p、q

4.求e对于φ(n)的乘法逆元d(d只有私钥拥有者才知道)
ed ≡ 1(mod φ(n))
即ed=kφ(n)+1

5.对于与n互素的a

以上就是RSA整体的简单介绍，在了解基础算法和数学理论之后，我们可以更加清晰地了解整个加密过程，希望大家可以和我一起快乐地学习密码学。