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
文章评论