RSA公开密钥加密算法

工作中用某library写了些RSA公钥密钥对生成,则有空时就重新阅读并思考了下这个已被广泛运用的加密技巧。我是高中时得知这个算法的,当然完全是似懂非懂,主要是那时候对其所基于的数论还未形成最基本的直觉,所以必然无法真正搞懂,不久就忘掉如没学一样。好的是,用现在更成熟的眼光看,这个算法真挺直接的,要点就那么几个。

先简单讲讲它的背景。他的被公布的发现发明是七十年代末,由美国的Rivest, Shamir, Adleman。维基百科的英文页也说这算法也是七十年代初就被英国情报局的一位数学家发现,但它直到九十年代末才被公布。那时候的计算力量还不足以让这个算法可被实现在我们日常生活中,但是好像八九十年代Rivest, Shamir, Adleman为此创办了一家公司,把它非常成功的商业化了,也赚了不少钱。毫无疑问,这算是比较重要的新技术和发展,美国也占了它的牛耳。这些如何进入别的国家(或是被别人也独立发现而至今为公布)我就不太清楚了,我读到过美国对密码学技术出口法律上有严格限制的,九十年代在美国好像有个做这个的人由于公开某加密技术而被美国政府调查,这个人的名字是Zimmerman

RSA算法

现在,我把RSA的技巧简单解释一下,细节也不必讲的太透彻,主要讲讲他的思路和启发。

基本数论有个欧拉定理(欧拉18世纪就发现了),它的断言为

a^{\phi(n)} \equiv 1 \mod n

\phi为totient函数,\phi(n) = |\{1 \leq k \leq n : \gcd(k, n) = 1\}|

通过这个可以观察到在a^m,若m \equiv 1 \mod \phi(n),就可恢复a。那如果d \cdot e \equiv 1 \mod \phi(n),可以试试以a^d加密编码为a信息,收信方以e为自己的钥,以其解密。在\mod nd次方是计算复杂度很高的计算问题,则即使第三方知道被加密的信息是某数的d次方,也难以进行反过来的操作,而取d次方确是个复杂度为\log d的问题。 Continue reading “RSA公开密钥加密算法”

Advertisements