Originally published at Inside the Mind of the G Machine. You can comment here or there.
工作中用某library写了些RSA公钥密钥对生成,则有空时就重新阅读并思考了下
先简单讲讲它的背景。他的被公布的发现发明是七十年代末,由美国的Rivest, Shamir, Adleman。维基百科的英文页也说这算法也是七十年代初就被英国情报局的一位数学
RSA算法
现在,我把RSA的技巧简单解释一下,细节也不必讲的太透彻,主要讲讲他的思路和启发。
基本数论有个欧拉定理(欧拉18世纪就发现了),它的断言为
,
为totient函数,
。
通过这个可以观察到在,若
,就可恢复
。那如果
,可以试试以
加密编码为
信息,收信方以
为自己的钥,以其解密。在
取
次方是计算复杂度很高的计算问题,则即使第三方知道被加密的信息是某数的
次方,也难以进行反过来的操作,而取
次方确是个复杂度为
的问题。那如何生成
和
呢,并使得他人无法快速从
计算出必保密的私钥
呢?在这一点,观察到计算
,若不是每一个小于
的整数都以欧几里得算法算出最大同因子,数与其互质的,那就得分解因式,而分解因式问
个比特的数的形式表示,还未知任何多项式时间的算法。所以可以随机选两个巨大的素数
和
,并让
,
。他方知道
但无法分解它则无法算出
。
是随机选的与
互质的数,它在
里的逆元素可以扩展欧几里得算法快速计算出来,以
命名,为公钥,传给他方,他方以
加密
,被加密的信息一旦受到可用仅自己知道的密钥
解密。
数位签章
我们已看到密钥可以给他方提供加密的方式保证中间监听者无法解密他方所传的信息。又一,可以将某双方同意定的哈西函数
在
上的值
的
次方(
为私钥),
同时发送。对方把发的信息解密了,也把数位签章以
(公钥)次方解密,若前者的哈西与后者同等,就能保证没问题,因为这验证了发信息的拥
非对称与对称加密
读者可以观察到该算法的不对称性,则RSA也被称为非对称加密。对称的加密方法也是有