要说起RSA算法的话就不得不提欧拉这个伟大的数学家，他在数学的很多方面都有很多研究，而RSA也正是基于他在数论上的欧拉公式才建立起来的。欧拉公式稍后再说，先简单说一下公钥密钥的非对称算法的概念，平常我们用的加密算法往往都是对称的，也就是说加密密钥和解密密钥是一样的，比如凯撒密码，你把每个字母后移3位，a变成d，b变成e，这里3就是加密密钥，然后解密的时候前移3位，这时候3就是解密密钥，非对称加密顾名思义就是加密密钥和解密密钥是不同的，恩，数学就是能干很多神奇的事情啊。

数论在很长的一段时间里被认为是没用的，纯数学的，优美的理论，一直到1976年。当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人提出了公开密钥密码的新思想（论文"New Direction in Cryptography"），再后来，1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出了RSA。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

首先介绍欧拉函数，表示是小于或等于n的正整数中与n互质的数的数目，比如，小于6和6互质的只有1和5。并且如果n的分解式为那么，然后有欧拉定理如果n，m是整数且gcd(n,m)=1，那么：

话说费马小定理就是欧拉定理的特殊性形式，下面开始说明RSA的主要步骤。

• 首先选出两个素数p，q，令n=p*q

• 再选出e，满足gcd(e,(p-1)*(q-1))=1

• 计算出d，满足d*e=1 (mod (p-1)*(q-1))

• 丢弃p,q(不要让其他人知道)公布n,e保留d，到这一步就是d作为密钥，e作为公钥

• 发送密文时,令

• 发送密文时,令

让我们具体一点，比如A要给B传送数据M=52，B选出p=17,q=11则n=187,选出e=7,算出d=23，A通过查询知n=187,e=7,计算得出C=35发给B，B通过计算得出M=52

好了我们来简单说明一下RSA的正确性吧，因为选取的p和q是素数，所以，因为d*e=1 (mod (p-1)*(q-1))，设，则

那么这种非对称加密算法解决了什么问题呢，首先他解决了密钥在非安全信道传播的问题，简单说你和别人想要加密传输资料，但是加密需要把密钥告诉对方才可以，这时候就可以直接把公钥发给对方，即使公钥被其他人截获，也无法通过公钥推算出密钥，换言之，除了拥有密钥的你之外，别人是不能解密内容的。另外公钥密钥还有一个用途就是数字签名了，一份东西你用私钥加密，别人都可以用公钥解密，因为别人没有私钥，所以加密的只可能是你，这样就是可以防止抵赖等，而且公钥密钥还有一系列很有意思的用途这里就不展开说了。数论，密码学神马的还是很有趣的啊。

建议继续学习：

1. RSA 公钥格式转换之PHP实现    (阅读：4859)
2. 为什么要用公钥/私钥而不是密码去做SSH身份验证    (阅读：4530)
3. 公钥私钥加密解密数字证书数字签名详解    (阅读：3749)
4. 千万不要迷信规律：大反例合集    (阅读：3684)
5. 跨越千年的RSA算法    (阅读：2848)
6. 几个精彩的数论问题    (阅读：1688)
7. RSA 算法是如何诞生的    (阅读：1663)
8. 密码学及公钥基础设施入门    (阅读：758)