专栏名称: 王建硕
王建硕的微信。
目录
相关文章推荐
搜狐科技  ·  余承东要发什么“别人想不到的产品”? ·  昨天  
搜狐科技  ·  余承东要发什么“别人想不到的产品”? ·  昨天  
开放知识图谱  ·  会议交流 | ... ·  2 天前  
李楠或kkk  ·  芊芊小美女的手速,0.92s 满电。 ... ·  2 天前  
大白聊IT  ·  硅谷芯片四巨头,全是华人在掌舵 ·  2 天前  
大白聊IT  ·  硅谷芯片四巨头,全是华人在掌舵 ·  2 天前  
51好读  ›  专栏  ›  王建硕

有人没看懂?再次尝试讲解 RSA 加密算法

王建硕  · 公众号  · 科技自媒体  · 2022-09-08 18:10

正文

上一次《 用吃奶的劲试着解释加密算法的数学原理 》,已经尽了我的最大努力解释 RSA 算法的具体数学原理了。结果还有同学说没看懂 。这在我写的文章里面属于少见的反馈。这不能忍,必须再来一次。

先上例子

假设一个人要把一个数字当众告诉我,却不想让其他人知道。如果我们没有事先约定什么暗号,怎么办?

我这里有一个办法。有三个神奇的数字: 5 , 14 , 11 ,其中, e = 5, n = 14 作为 公钥 (公开的钥匙),可以告诉任何人,但另外一个 d = 11 作为 密钥 (秘密的,不公开的钥匙),我谁都不告诉。

谁要是想给我传递任何数字,只要用这两个公钥对想传递的数字做点特殊的处理就可以:

取这个数字的 e 次方,再把除以 n 的余数告诉我就可以

比如,你想传递给我的数字是 m = 2 , 你就可以公开地把上述处理后的结果 c = 4 告诉我(因为 2 ^ 5 = 2 * 2 * 2 * 2 * 2 = 32。32 % 14 = 4)

我拿到 4 怎么办呢?我用我手里的私钥 d 做点类似上面那样的特殊处理:把别人给我的数字取 d 次方,再除以 n 取余数。得到的余数你猜是几?我们算一下

( 4 ^ 11 ) % 14 = 4194304 % 14 = 2

居然就是 你一开始想传递给我的数字 2

把想传递的数字 m ,用公钥处理后的数字 c ,再用私钥 d 做点处理就能逆向得到 m 本身(也就是说,2 的 5 次方除 14 取余数得到的数,再 11 次方除 14 取余数,就回到了 2 本身)。更神奇的是,小于 14 的任何一个数 m 的 5 次方再 11 次方,都是它本身 m。见下图:

神奇不神奇?如果找到了这样神奇的数字对,不就可以做加密和解密了?

这里的字母都是有含义的:

  • e 是 encryption,加密的意思

  • d 是 decryption,解密的意思

  • c 是 cipher,密文的意思

  • m 是 message,消息的意思


背后的数学原理

很显然真实的世界我们不能所有人都用这三个数,这几个数字太简单了。实际上 e 经常取 65537,d 和 n 都是十进制 100 多位的数字。怎么找到这么大却依然符合刚才说的神奇的性质的数字呢?

我们这么找:

先找两个大的素数(就是除了自己和 1 以外不能被任何数整除的数)p, q,把这两个数相乘,结果就是我们想找的 n ( n = p * q )。这样公钥就已经出来了( e = 65537, n = p * q )。我们接下来算私钥。

把 p、q 这两个数字各减去 1 ,再相乘,就得到一个新的乘积,我们命名为 φ 。「 φ = ( p - 1 ) * ( q - 1 )  」。φ 读作 /fai/

φ n 有什么神奇的关系吗?有的!18 世纪中期,大数学家欧拉发现了一个惊人的事实,当 m < n 且和 n 互质① 的时候:

m ^ φ % n = 1

在开头的例子里面,就是欧拉发现了,任何数字的 φ 次方除以 n 的余数都是 1 !大家可能可以猜得出来,我们就是用 p = 2, q = 7 算出 n = 14,φ = ( 2 - 1 ) * ( 7 - 1 ) = 1 * 6 = 6。欧拉说,任何小于 14 并且和 6 互质的数字的 6 次方除以 14 的余数都是 1 。

你给我一个数字,我知道他的 6 次方除以 14 的余数是 1 有啥用?除了是一个有趣的事实以外,能用来加密解密吗?

名字开头分别是 R、S、A 的三位教授就开始动脑筋了。能不能借用这个性质,把 φ 这个数字硬掰成两个数?然后告诉别人一个,自己留一个,是不是就可以用来加密解密了?接下来就是 RSA 的精巧却简单得让人不能相信的设计。







请到「今天看啥」查看全文