用吃奶的劲试着解释加密算法的数学原理
输入“/”快速插入内容
用吃奶的劲试着解释加密算法的数学原理
用吃奶的劲试着解释加密算法的数学原理
⏰ 剪存时间：2022-10-12 17:07:29 (UTC+8)
原创 王建硕 王建硕
2022-08-18 18:57:17
精确发文时间由壹伴提供
2022-08-18 18:57 发表于 云南
手机阅读
前不久 Jason 同学邀请复旦大学数学系的梅同学给希望了解 Web3 的朋友们上了 5 节硬核的数学课。从自然数开始，一直讲明白了 RSA 非对称式加密的细节。我再回顾一下，尝试解释这个其实还挺复杂的事儿。
（前方数学预警，但是我保证努力限制在小学数学知识范围以内）
大数无法分解
3 * 7 算出 21 容易吗？容易。反过来，21 是哪两个数的乘积？也不难，但肯定比算 3 * 7 麻烦。
同理 967 * 379 = 366493 容易。反过来， 366493 是哪两个数乘积？难多了。
随着乘积的不断变大，算乘法的难度略微增大，算是这个数是由哪两个数相乘的难度陡峭的增加。
一个一百位数字的数和一百位数字的数相乘，手工算不容易，但对计算机来说不难，结果是一个大约两百位数字的数字。
反过来，把这个200 位的数字分解？基本上现在能想到的办法就是近似于一个一个的试。别说算乘法了，光从一数到 80 位的数字，按照现在的计算水平，就要消耗掉一个中等恒星一生的能量了。所以，简单结论是，超级大的数字做分解不可能。
就利用这个简单的原理，加上听起来故弄玄虚的欧拉定理，就是一个精妙绝伦的 RSA 加密算法。
n 进制取个位
这个东西的数学名称叫「取模」，就是算「一个数除以 n 以后的余数是几」。
不过我们不用这个名字。我自己发明的一个混杂了数学和计算机的概念，叫做 n 进制取个位 。比如 n = 8，八进制下只取个位，超过的十、百、千位数就直接扔掉，那么 15 这个数本来八进制就是 1 7 ，只取个位，就是 7 。所以，我们规定，15 在八进制个位模式下，就等于 7。同样，23，31 等，在 8进制取个位下，都等于 7。这个「等于」，不是绝对数字的相等，而是经过了 n 进制取个位 ，我们用 ≡ 表示这种特殊的等于 （正规说法叫做“模 n 同余”，可以忽略） 。
这样，如果 n 是 4 万公里的话，数字的世界变成像地球一样，是一个循环。在赤道上可以 向东 走 1 万公里 ，和 向西 走 3 万公里 结果是一样的，甚至 向西 走 7 万 ， 11 万 ， 15 万 公里的终点是一样的，就是一圈一圈的转就是了。所以4 万进制取个位， 1 万 ≡ -7 万 ≡ -11 万 ≡ -15 万。注意，毕竟走 7 万公里和走 11 万公里不相等( = )，但是在地球赤道上走，他们的效果相等 ( ≡ )。
例子：比如在 20 进制取个位 下， 3 * 7 的结果就是 1 （本来是 21，结果走过头了， 又绕回来，回到了 1 ）。
连着乘两个数就是它本身
这有啥用呢？神奇的事情在于，在 20 进制取个位 下，任何数乘以 3 再乘以 7，就 相当于乘以 1， 就是这个数本身！
比如 12 * 3 = 36 ；36 % 20 = 16 ; 16 * 7 = 112; 112 % 20 = 12
变回原来了。神奇吗？
在 20 进制取个位 下，你把一个数乘以 3，我不用除以 3，而是继续乘以 7 ，就是原来那个数。不仅仅是 7，我把乘 3 的数字乘以 67，127，或者 187。。。。它都会回到原来那个数，只是转的圈数多了些。
这就使得，如果两个数在一个 n 进制取个位 下乘积为 1，这两个数不就是一个很好的加密和解密的工具吗？
比如数字大一点，在 366492 进制取个位下，任何数乘以 967 得到的数再乘以379，就是它本身。
公钥和密钥
如果我把 e = 967 当做公钥， d = 379 当做密钥，我只需要告诉别人（ e = 967, n = 366492 ）这两个数字，别人乘积以后交给我，我再乘以 d ，然后。。。。
不过有一个小问题，如果给出了（ e = 967, n = 366492 ）这两个数，别人除以 e 不就得到了我的秘钥 d 吗？毕竟，你可以算乘法，别人就可以算除法，而且难度差不多。我们把这个办法成为露馅儿加密法。
接下来要做的事情，就是想办法 把这自己的密钥藏起来 ，让别人拿到 n 进制数，还有公钥 e，没有办法算出我的密钥，但是依然可以用 e 加密，我可以用私钥 d 解密不就好了？
欧拉定理
我们引入 φ(n) 。它的定义可厉害了，是「 小于 n 的正整数中和 n 互质的数的个数 」。这个定义忽略就好，只要知道，如果 n 是两个素数 p, q 的乘积的话， φ(n) = (p-1 )(q-1)。
欧拉发现了一个惊天大秘密，居然在 n 进制取个位 下，如果 m 和 n 互为质数，m 的 φ(n) 次方 居然等于 1：