不久前，Jason同学邀请复旦大学数学系的梅同学给想学习Web3的朋友们上五堂硬核数学课。 我们从自然数开始，讲解了RSA非对称加密的细节。 让我再回顾一下并尝试解释一下这个实际上相当复杂的事情。
（前面有数学警告，但我保证尽量保持在小学数学知识范围内）
大数无法分解
3 * 7 很容易算出 21 吗？ 简单的。 相反，21 是哪两个数的乘积？ 不难，但是绝对比计算3*7麻烦。
同样，967 * 379 = 366493 很容易。 相反，366493 是哪两个数字的乘积？ 困难得多。
随着乘积不断增长，计算乘法的难度略有增加，计算该数与哪两个数相乘的难度急剧增加。
一个百位数字乘以一个百位数字用手算起来不容易，但对计算机来说却不难。 结果是一个大约两百位的数字。
反过来，分解这个200位数字？ 基本上现在能想到的方法就是一一尝试。 别说乘法，按照现在的计算水平，光是从一位数到八十位，就需要消耗一颗中型恒星一生的能量。 因此，简单的结论是，不可能分解极大的数字。
利用这个简单的原理，再加上听起来神秘的欧拉定理，就是一个精妙的RSA加密算法。
n 以一位数字为基数
这个东西的数学名称是“模”，就是计算“一个数除以n后的余数是多少”。
但我们不使用这个名字。 我发明了一个混合数学和计算机的概念，称为 n 进制系统来获取个位数字。 例如n=8，八进制只取个位，多余的十位、百位、千位直接丢弃。 那么数字15本来是八进制的17，只取个位，就是7。因此，我们规定八进制单位模式下15等于7。 同样，23、31等，取八进制中的个位时，都等于7。这个“等于”并不是绝对的数值相等，而是以n为基数的一位数。 我们用 ≡ 来表示这个特殊的等号（正式术语叫“modulo n congruence”，可以忽略）。
这样，如果n为4万公里，数字世界就变成了地球一样的循环。 在赤道上，向东走一万公里，结果与向西走三万公里的结果是一样的。 即使向西走7万公里、11万公里、15万公里，终点都是一样的，一圈一圈就可以了。 。 因此，基数 40,000 取为 10,000−70,000−110,000−150,000。 注意，毕竟步行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：
m^φ(n) == 1
两边同时求 k 次方：
m ^(k *φ(n))≡1
两边都乘以 m：
m^(k*φ(n)+1)=m
k *φ(n) + 1 是什么意思？ 即，这是“除以φ(n)余数为1”的数。 换句话说，只要找到两个数字e*d，使它们的乘积除以φ(n)的余数为1即可。这很容易找到。 有一种方法叫做欧氏除法，但我在这里跳过它。 我们通常将e设置为固定值65537，然后就可以找到满意的d。
最后，这是最令人惊奇的一步，如果我们能找到这样的e，d，我们就告诉全世界关于e和n的信息，并要求他们取要加密的数字m的n基数的e次方。 给我，如果我将这个数字进行 d 次方，我会得到 m。
(m^e)^d=m
改组
现在所有人无一例外都应该晕过去了。 这个是正常的。 让我们再澄清一点。
也就是说，如果我能找到一个基数n，无论我用什么方法，在这个n个位的基数中，我都能找到两个数字e和d。 E对全世界开放，d对我自己保密，同时如果任意一个数m的e次方d次方等于原来的m，加解密算法不就成立了吗？ 就像我之前说的，一个数乘以另一个数总是等于原来的数？
但秘密加密方法的二乘算法的明显缺陷是，当给定e和n时，d也被给定。
在这个新算法中，给出了 e。 给定了n，但e * d ≡1的底不是简单的n，而是φ(n)，它与n同源但不同。 仅仅因为基础系统已经改变，我们就不能使用隐藏加密方法中的两次乘法。 相反，我们借用了欧拉令人震惊的发现并进行了两次求幂运算。
可以根据 n 计算 φ(n) 吗？ 如果你有能力分解n，当然φ(n)是现成的，只需将两个因数各减一，然后相乘即可。
但是p和q可以很容易地从n中找到吗？ 根据最早无法分解的大数，即使你想找到100个太阳并烧掉它们，p和q就像脚手架一样。 一旦计算出n，就计算出φ(n)，然后将其丢弃。 那么 φ(n) 就是一个秘密。 如果 φ(n) 是秘密，那么即使有 e 也无法找到 d。
因此，整个算法极其复杂且安全。
例如
我们找到两个脚手架数：p = 2，q = 7，并计算n = 2 * 7 = 14，φ(n)=(2 - 1) * (7 - 1) = 6。这两个脚手架数p，q计算出 n 和 φ(n) 后就退休了。 求6进制个位时，e * d ≡ 1很好办，只需e = 5, d = 11 (5 * 11 = 55 = 6 * 9 + 1 ≡ 1)即可。
这样，向全世界公布的数字是(e = 5, n = 14)，而留给自己的数字是d = 11。 φ(n) 永远不要告诉任何人。 φ(n)就像总统，n就像他的影子。 世界只能看到他的影子，看不到总统本人。 庆幸的是，影子行走在人间，无惧暗杀，总统也安然躲在防空洞里。
我们来试试吧。 14位单位模式下，如果要转的数为m = 2，别人算出m^e，则为2^5=32=2*14+4^4
现在软件加密算法，4可以在互联网上随意传输。 有一个只有我知道的秘密是11，我得到之后，算出了4的11次方，4^11 == 4,194,304 % 14 == 2，这不就是别人想给我的数字吗？ 前提是我们认为别人不能将n=14分解成2*7，否则所有秘密都会暴露。
肉眼可见14等于2*7。
这个数n：
8244510028552846134424811607219563842568185165403993284663167926323062664016599954791570992777758342053528270976182274842 613932440401371500161580348160559
是 p
91119631364788082429447973540947485602743197897334544190979096251936625222447
乘以 q
90480063462359689383464046547151387793654963394705182576062449707683914045697
即使是电脑眼也看不到它。 p和q就像两个门神，守护着他们身后的秘密入口。 但计算 φ(n) 以及根据 p 和 q 计算 e 和 d 却是小菜一碟。
如果我们知道n的组成是p、q，我们就可以根据上面的算法选择e和d：
65537
2545549238258797954286678713888152865623498585866759298032549597771444725977268190722532488574321463855938811396613702406 984581214587037347197409962813953
也就是说，在这个游戏中，如果有人想传一个数字m给我，他只需要把它算到n进制单位的65537次方（m^65537），然后我再算到它的d次方。 我拿回了原来的号码。
这个精巧的算法就是RSA加密算法。
希望有人能够理解。 我真的尽力了。
