介绍

rsa 加密算法，详情参见 wiki 百科

原理

  1. 任意选择两个不相等的大素数 RSA 加密算法 —— Eular 定理的典型应用 - 图1 和 RSA 加密算法 —— Eular 定理的典型应用 - 图2
  2. 计算 RSA 加密算法 —— Eular 定理的典型应用 - 图3 和 RSA 加密算法 —— Eular 定理的典型应用 - 图4 的乘积RSA 加密算法 —— Eular 定理的典型应用 - 图5
  3. 计算 RSA 加密算法 —— Eular 定理的典型应用 - 图6 由于 RSA 加密算法 —— Eular 定理的典型应用 - 图7 都是素数，故RSA 加密算法 —— Eular 定理的典型应用 - 图8
  4. 任意取一个整数 RSA 加密算法 —— Eular 定理的典型应用 - 图9 满足 RSA 加密算法 —— Eular 定理的典型应用 - 图10
  5. 因为 RSA 加密算法 —— Eular 定理的典型应用 - 图11 故由扩展欧几里得算法可计算 RSA 加密算法 —— Eular 定理的典型应用 - 图12 和 RSA 加密算法 —— Eular 定理的典型应用 - 图13 的线性组合，即计算RSA 加密算法 —— Eular 定理的典型应用 - 图14中 RSA 加密算法 —— Eular 定理的典型应用 - 图15 的值，计算出 RSA 加密算法 —— Eular 定理的典型应用 - 图16 后，即可使用 RSA 加密算法 —— Eular 定理的典型应用 - 图17 和 RSA 加密算法 —— Eular 定理的典型应用 - 图18 进行加密和解密，故将 RSA 加密算法 —— Eular 定理的典型应用 - 图19 和 RSA 加密算法 —— Eular 定理的典型应用 - 图20 封装成公钥，将 RSA 加密算法 —— Eular 定理的典型应用 - 图21 和 RSA 加密算法 —— Eular 定理的典型应用 - 图22 封装成私钥
  6. 现假设有明文 RSA 加密算法 —— Eular 定理的典型应用 - 图23 经公钥加密RSA 加密算法 —— Eular 定理的典型应用 - 图24将 RSA 加密算法 —— Eular 定理的典型应用 - 图25 作为密文，此处注意：明文 RSA 加密算法 —— Eular 定理的典型应用 - 图26 须为正整数且小于 RSA 加密算法 —— Eular 定理的典型应用 - 图27
  7. 接收端收到密文 RSA 加密算法 —— Eular 定理的典型应用 - 图28 后使用私钥解密出明文，即有RSA 加密算法 —— Eular 定理的典型应用 - 图29

注：等式 (4) 可由之前的知识证明，下面就证明其正确性及 RSA 加密算法的可靠性

证明

由于 RSA 加密算法 —— Eular 定理的典型应用 - 图30 都是素数，故有 RSA 加密算法 —— Eular 定理的典型应用 - 图31 根据“Fermat-Eular 定理”一节的定理一有 (1) 式成立

又由于 RSA 加密算法 —— Eular 定理的典型应用 - 图32 由前面章节的定理有，任意两个整数的最大公因数可以表示成这两个数的线性组合，在这里即是存在 RSA 加密算法 —— Eular 定理的典型应用 - 图33 使得 RSA 加密算法 —— Eular 定理的典型应用 - 图34 由扩展欧几里得算法可计算出 RSA 加密算法 —— Eular 定理的典型应用 - 图35 的值，且计算较容易，故 (2) 式成立

密文 RSA 加密算法 —— Eular 定理的典型应用 - 图36 要证明 RSA 加密算法 —— Eular 定理的典型应用 - 图37 即是要证明RSA 加密算法 —— Eular 定理的典型应用 - 图38
又因为 RSA 加密算法 —— Eular 定理的典型应用 - 图39 故有 RSA 加密算法 —— Eular 定理的典型应用 - 图40 即 RSA 加密算法 —— Eular 定理的典型应用 - 图41 即RSA 加密算法 —— Eular 定理的典型应用 - 图42
故 (5) 式变为RSA 加密算法 —— Eular 定理的典型应用 - 图43
现在分情况讨论

  • 当 RSA 加密算法 —— Eular 定理的典型应用 - 图44 时，由 Eular 定理有 RSA 加密算法 —— Eular 定理的典型应用 - 图45 故RSA 加密算法 —— Eular 定理的典型应用 - 图46得证
  • 当 RSA 加密算法 —— Eular 定理的典型应用 - 图47 时，因为 RSA 加密算法 —— Eular 定理的典型应用 - 图48 故假设 RSA 加密算法 —— Eular 定理的典型应用 - 图49 则有 RSA 加密算法 —— Eular 定理的典型应用 - 图50 则RSA 加密算法 —— Eular 定理的典型应用 - 图51则由 Eular 定理有RSA 加密算法 —— Eular 定理的典型应用 - 图52上式可写为RSA 加密算法 —— Eular 定理的典型应用 - 图53由算术基本定理可知 RSA 加密算法 —— Eular 定理的典型应用 - 图54 一定能被 RSA 加密算法 —— Eular 定理的典型应用 - 图55 整除，即 RSA 加密算法 —— Eular 定理的典型应用 - 图56 故上式可写为RSA 加密算法 —— Eular 定理的典型应用 - 图57又因 RSA 加密算法 —— Eular 定理的典型应用 - 图58 故上式即RSA 加密算法 —— Eular 定理的典型应用 - 图59故得证，同理 RSA 加密算法 —— Eular 定理的典型应用 - 图60 时也可得证

可靠性

由上面的过程，可知私钥 RSA 加密算法 —— Eular 定理的典型应用 - 图61 仅能由式子 RSA 加密算法 —— Eular 定理的典型应用 - 图62 计算得到

而计算该式子须知道 RSA 加密算法 —— Eular 定理的典型应用 - 图63 即是要知道 RSA 加密算法 —— Eular 定理的典型应用 - 图64

从而 RSA 加密算法的破解 与 大数因式分解 等价，当将 RSA 加密算法 —— Eular 定理的典型应用 - 图65 分解为 RSA 加密算法 —— Eular 定理的典型应用 - 图66 时，即意味着私钥被破解

以下内容摘自 wiki 百科

对极大整数做因数分解的难度决定了 RSA 算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。 假如有人找到一种快速因数分解的算法，那么 RSA 的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 密钥才可能被暴力破解。到 2008 年为止，世界上还没有任何可靠的攻击 RSA 算法的方式。

　　只要密钥长度足够长，用 RSA 加密的信息实际上是不能被解破的。

故大整数难分解成为了 RSA 的理论基础，且破解难度随着长度的增长不是线性的，故等到暴力破解出来，可能已经不知道多少年以后了，那破解的意义也就不大了，注：wiki 百科推荐重要数据使用 2048 位加密

本文作者注：等到量子计算机真正达到可用的级别，破解 RSA 应该没多大难度了吧