上一次《
用吃奶的劲试着解释加密算法的数学原理
》,已经尽了我的最大努力解释 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 互质① 的时候:
在开头的例子里面,就是欧拉发现了,任何数字的 φ 次方除以 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 的精巧却简单得让人不能相信的设计。