前言

RSA密码是目前使用最为广泛的公钥密码。它的可靠性是基于大数的因子分解问题，只有很短的RSA密钥才可能被穷举法破解，只要密钥的长度足够长，用RSA加密的信息实际上是不可能被破解的。

正文

RSA算法公式

M为明文，C为密文

• 明文加密公式
  e为公钥
• 密文解密公式
  d为私钥

RSA算法流程

1. 确定n
   独立选取两个大素数p，q（100~200位十进制数字） 。
2. 确定e
   计算n的欧拉函数值，在~中随机选取整数e，使得,即欧拉函数值和公钥的最大公因数为1，即为互素数。
3. 确定d
   计算e 模 的乘法逆元，即为d。 (同余）
   即

RSA数论基础知识

1. 欧拉函数和欧拉定理

• 欧拉函数

  定义：小于n且与n互素对的正整数的个数，记为,把称为欧拉函数。显然对于素数p，每一个小于p的正整数都与p互素，所以有。
  定理：设有两个素数p和q，pq,那么对于n=pq，有
  

• 欧拉定理

  对于任意互素的整数a和n，有。