rsa 加密算法原理

[GreenFaith]

rsa 加密原理

• 互质

  如果两个正整数，除了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随机数发生器。

[GreenFaith]