RSA公钥密码体制

前言

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

正文

RSA算法公式

M为明文，C为密文

  • 明文加密公式 C=M^e\ mod\ n
    e为公钥
  • 密文解密公式 M=C^d\ mod\ n
    d为私钥

RSA算法流程

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

RSA数论基础知识

1. 欧拉函数和欧拉定理
  • 欧拉函数
    定义：小于n且与n互素对的正整数的个数，记为\Phi(n),把\Phi(n)称为欧拉函数。显然对于素数p，每一个小于p的正整数都与p互素，所以有\Phi(p)=p-1。
    定理：设有两个素数p和q，p\neqq,那么对于n=pq，有
    \Phi(n)=\Phi(pq)=\Phi(p)\times\Phi(q)=(p-1)\times(q-1)
  • 欧拉定理
    对于任意互素的整数a和n，有a^{\Phi(n)}\equiv1\ mod\ n。
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容