RSA的算法介绍与数学原理

2020年09月25日 39点热度 0人点赞 0条评论

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 = 1x = 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.欧拉定理:
对于任意互素的an,有a^{\varphi(n)}\equiv1(\mod n)

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

4.乘法逆元
ab≡1(mod m),则称ab为关于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整体的简单介绍,在了解基础算法和数学理论之后,我们可以更加清晰地了解整个加密过程,希望大家可以和我一起快乐地学习密码学。

luoluo

我爱吃螺蛳粉

文章评论