RSA加密算法原理及JS实现

黄欢达

发展史1976年以前，加密世界主要采用对称加密算法（Symmetric-key algorithm）。对称加密存在让人头疼的问题：甲乙双方通信，甲方必须把加密规则告诉乙方，否则无法解密。保存和传递密钥无法确保安全？1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，"DH密钥协议算法"。如上所示，Alice和Bob同时拥有了共享密钥K，私钥a,b也未在互联网上传播，且公开的A\B\g\p在短时间内无法破解出a,b,K。因此DH算法便可以在不安全的网络上协商出密钥，基于此构建安全的加密通道。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。这种新的加密模式被称为 **"非对称加密算法"**。如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。1977年，三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法，当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的，可以实现非对称加密。从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。在RSA算法中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。棱镜门据NSA前通讯员斯诺登所提供的机密文件显示，NSA跟RSA达成了一份价值1000万美元的合同，前者通过在后者的加密软件中植入一个缺陷公式，为自己留了一道“后门”。据悉，RSA存有缺陷公式的软件叫做Bsafe，而该缺陷公式的名字为Dual Elliptic Curve，它由NSA开发而出。BSafe是很多企业级用户采购安全软件，此举将让NSA通过随机数生成算法Bsafe的后门程序轻易破解各种加密数据。RSA原理根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。密钥生成过程步骤概述公式说明1随机p，qp,q选择一对不相等且足够大的质数2求nn = p*q计算质数p，q的乘积3求φ(n)φ(n) = (p-1)(q-1)计算n的欧拉函数4求e1 usingnamespacestd;intext_euc(inta,intb,int&x,int&y){if(b==0){x=1,y=0;returna;}intx1,y1,d;intd=ext_euc(b,a%b,x1,y1);x=y1;y=x1-a/b*y1;returnd;}intmain(){inta,b,x,y;cin>>a>>b;ext_euc(a,b,x,y);cout<