rsa 加密原理 - GreenFaith/GreenFaith.github.io GitHub Wiki

互质

如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。
比如，15和32
欧拉函数

任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？
（比如，在1到8之中，有多少个数与8构成互质关系？
如果n是质数，则 φ(n)=n-1
欧拉定理

如果两个正整数a和n互质，则n的欧拉函数 φ(n)
a的φ(n)次方减去1，可以被n整除。
比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。
非对称加密

（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
（2）甲方获取乙方的公钥，然后用它对信息加密。
（3）乙方得到加密后的信息，用私钥解密。
整数分解

给出两个大质数，很容易就能将它们两个相乘。但是，给出它们的乘积，找出它们的因子就显得不是那么容易了。这就是许多现代密码系统的关键所在。如果能够找到解决整数分解问题的快速方法，几个重要的密码系统将会被攻破，包括RSA公钥算法和Blum Blum Shub随机数发生器。