Originally published at Inside the Mind of the G Machine. You can comment here or there.
工作中用某library写了些RSA公钥密钥对生成，则有空时就重新阅读并思考了下这个已被广泛运用的加密技巧。我是高中时得知这个算法的，当然完全是似懂非懂，主要是那时候对其所基于的数论还未形成最基本的直觉，所以必然无法真正搞懂，不久就忘掉如没学一样。好的是，用现在更成熟的眼光看，这个算法真挺直接的，要点就那么几个。
先简单讲讲它的背景。他的被公布的发现发明是七十年代末，由美国的Rivest, Shamir, Adleman。维基百科的英文页也说这算法也是七十年代初就被英国情报局的一位数学家发现，但它直到九十年代末才被公布。那时候的计算力量还不足以让这个算法可被实现在我们日常生活中，但是好像八九十年代Rivest, Shamir, Adleman为此创办了一家公司，把它非常成功的商业化了，也赚了不少钱。毫无疑问，这算是比较重要的新技术和发展，美国也占了它的牛耳。这些如何进入别的国家（或是被别人也独立发现而至今为公布）我就不太清楚了，我读到过美国对密码学技术出口法律上有严格限制的，九十年代在美国好像有个做这个的人由于公开某加密技术而被美国政府调查，这个人的名字是Zimmerman。
RSA算法
现在，我把RSA的技巧简单解释一下，细节也不必讲的太透彻，主要讲讲他的思路和启发。
基本数论有个欧拉定理（欧拉18世纪就发现了），它的断言为
，
为totient函数，
。
通过这个可以观察到在
，若
，就可恢复
。那如果
，可以试试以
加密编码为信息，收信方以
为自己的钥，以其解密。在
取
次方是计算复杂度很高的计算问题，则即使第三方知道被加密的信息是某数的次方，也难以进行反过来的操作，而取次方确是个复杂度为
的问题。那如何生成和呢，并使得他人无法快速从计算出必保密的私钥呢？在这一点，观察到计算
，若不是每一个小于
的整数都以欧几里得算法算出最大同因子，数与其互质的，那就得分解因式，而分解因式问题，若以分解任意
个比特的数的形式表示，还未知任何多项式时间的算法。所以可以随机选两个巨大的素数
和
，并让
，
。他方知道但无法分解它则无法算出。是随机选的与互质的数，它在
里的逆元素可以扩展欧几里得算法快速计算出来，以命名，为公钥，传给他方，他方以加密，被加密的信息一旦受到可用仅自己知道的密钥解密。
数位签章
我们已看到密钥可以给他方提供加密的方式保证中间监听者无法解密他方所传的信息。又一个核心功能就是这个密钥也可以用以做数位签章而验证身份。这个数位签章可以保证信息绝对是发信人发的，并未在中途改于某恶意的第三方。这个如何实现呢？要发信息，可以将某双方同意定的哈西函数
在上的值
的次方（为私钥），
同时发送。对方把发的信息解密了，也把数位签章以（公钥）次方解密，若前者的哈西与后者同等，就能保证没问题，因为这验证了发信息的拥有了某个代表并限制于某身份的密钥。若想对此有更清晰的图像，读者可以试试画个交换图标。
非对称与对称加密
读者可以观察到该算法的不对称性，则RSA也被称为非对称加密。对称的加密方法也是有的，它需要先双方互相安全交换共享的对称密钥，该钥代表可逆的加密及解密方法。想理解这个可以先参考下Diffie-Hellman密钥交换算法，这个算法很简单，比RSA还要简单。然后对称钥密钥加密方法有很多，什么DES，AES，Blowfish，若感兴趣可以看看，了解下它们的细节所在。
