RSA算法的数学原理与证明
发布于 4 年前 作者 youth7 5170 次浏览 来自 分享

本文将讨论以下内容

  • 一些与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.png

一个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),但是懒得重新再截图编辑了,大家凑合看吧。

2 回复

写的很棒啊,但getMin写在了扩展欧几里得算法后面找了好久

@zy445566 其实最重要的内容都是参考阮一峰的博客的,只是他有一些数学细节没有给出,我把一些细节证明补充了。

回到顶部