本文将讨论以下内容

• 一些与RSA算法相关的基本数学概念
  • 互质
  • 算术基本定理
  • 欧拉函数
  • 欧拉定理
  • 模反元素
  • 一些后续证明会用到的数学结论
• 如何生成公钥、私钥
• 公钥秘钥为何难以破解
• 如何利用公钥、私钥进行加密、解密
• 解密过程的数学证明
• 一个RSA小demo

建议初次阅读不要纠结欧拉公式和欧拉定理的相关证明（具体证明可以在参考资料中找到），要将精力放在公钥秘钥的生成以及如何使用公钥秘钥进行加密解密。（不过我个人最感兴趣的是解密过程的数学证明，因此还是补全了那个证明）

一些与RSA算法相关的基本数学概念

互质

如果两个整数除了1之外没有其它公约数，则称这两个数互质（比如7、15互质，8、9也是互质，注意一个数即使不是质数，也有可能和另外一个数互质）。 基于互质的性质，我们有以下推论：

• 任意两个质数互质，比如13和61。
• 一个数是质数，另一个数只要不是前者的倍数，则两者互质，比如3和10。
• 如果两个数之中，较大的那个数是质数，则两者互质，比如97和57。
• 1和任意自然数互质，比如1和99。
• p是大于1的整数，则p和p-1互质，比如57和56。
• p是大于1的奇数，则p和p-2互质，比如17和15。

一个RSA小demo

    (function() {
        //这段代码只能运行在chrome浏览器68之后的版本上
        const [p,q] = [17, 29];//选取两个质数
        const n = p*q;//n=493
        const fn = (p-1)*(q-1); //fn=448
        const e = 31 ;//e必须和φ(n)互质
        const d = 159//使用上面的getMin()算出d为159
        for (let i = 0; i < n; i++) {
            const ciphertext = BigInt(i) ** BigInt(e) % BigInt(n);
            const decrypt = BigInt(ciphertext) ** BigInt(d) % BigInt(n);
            console.log(`加密后为:${ciphertext} 解密后为:${Number(decrypt)}, 原文为${i}`);
            if(Number(decrypt)!= i){
                throw new Error("加密/解密出错");
            }
        }
    })();

参考资料 http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

PS： 发现原文有一处手写错误（20 mod 3 = 2），但是懒得重新再截图编辑了，大家凑合看吧。