RSA-EDA365

RSA

RSA算法是基于数论中的同余理论。如果用m代表明文，c代表密文，E(m)代表加密运算，D（c）代表解密运算，x=y(mode z)表示x和y模z同余，则加密和解密算法简单表示如下：
加密算法 c=E(m)=me(mod n)
解密算法 m=D(c)=cd(mod n)
其中n和密钥e是公开的，而密钥d是保密的。
下面讨论密钥的求取：
①选取两个随机大素数p和q（保密）；
②设n=p×q；
③欧拉函数φ（n）=（p-1）（q-1）（保密）；
④选取与φ（n）互素的正整数e，即满足gcd(φ(n),e)=1和0<e<φ(n)；
⑤计算d(保密)，使满足e×d=1（mod φ(n)），即d和e相对于模φ(n)互为逆元素。
由RSA算法原理可知，RSA算法的核心是求模取余运算，其安全性是建立在大合数因子分解困难的基础之上的。