第16章 · 播客 第2集
安全性和保密性设计 · RSA：从密钥爆炸到公钥私钥
🎙️ 本集播客：第2集：先用 45 把和 4950 把密钥算出对称体制的「密钥爆炸」，引出公私钥；再拆 RSA 的安全性依据、PK 等于 N 加 e、SK 等于 N 加 d 两把钥匙，加密解密签名三条公式逐个念、逐个演算，五个设计条件一个不落。 语音由微软 Edge 神经网络语音预生成（女声·晓伊，男声·云希）。点击下方任意对话可直接从该句开始播，当前句朗读时下一句已预先加载，无缝衔接。
明
阿明
上集你留了尾巴：对称加密好好的，为什么非要搞出公钥私钥两把钥匙？
雅
小雅
原文给了一个算术题，算完你就懂了。对称密钥加密中，密钥的生成、导入、存储、管理、分发等过程比较复杂，特别是随着用户的增加，密钥的需求量成倍增加——更大规模系统里，大量密钥的分配与管理是难以解决的问题。
雅
小雅
具体算：系统中有 n 个用户，每两个用户之间要建立密码通信，则系统中每个用户须掌握 n 减 1 除以 2 个密钥，系统中所需的密钥总数为 n 乘 n 减 1 除以 2 个。10 个用户，每个用户必须有 9 个密钥，系统中密钥总数 45 个；100 个用户，每个用户 99 个，总数 4950 个。
明
阿明
等等，这账不对吧？10 个用户每个 9 个密钥，那不是 90 个吗，怎么总数 45？
雅
小雅
问到点子上了，这正是题眼。用户 A 和 B 共用同一把会话密钥，A 账上有它、B 账上也有它，但系统里只算一把。所以总数不是 n 乘 n 减 1，要再除以 2。选择题问「100 个用户的系统共需多少把对称密钥」，答 4950，选项里放 9900 就是给你算重准备的。
雅
小雅
原文还补一刀：这还只是每个用户对之间用一种会话密钥的情况，如果不同会话要换不同密钥，总数更多。后面 16.3 密钥分配中心那节还会用同样的公式，先记住这个 n 乘 n 减 1 除以 2。
明
阿明
所以才需要不对称加密。它怎么定义的？
雅
小雅
不对称密钥加密在对信息加密和解密时分别采用两个不同的密钥，因此也称双钥加密方法。先产生一对密钥：一个是保密密钥，由用户自己保存，不能向外界泄漏，简称私钥；另一个是公开密钥，可对外公开，甚至可在公共目录中列示，简称公钥，因此也称公开密钥加密方法。
雅
小雅
配对规则一句话：只有使用私钥才能解密用公钥加密的数据，同时使用私钥加密的数据只能用公钥解密。这个互逆关系是后面数字签名全部逻辑的地基。
明
阿明
那保密通信怎么发起？用谁的公钥加密？
雅
小雅
这是年年考的方向题。发送者要向接收者发送保密信息，先用接收者的公开密钥对信息加密再发送；接收方用其私钥顺利解密，其他人即使收到密文也无法正确解读。口诀就一句：保密用对方的公钥加密，对方用自己私钥解密。方向反过来就是签名，后面讲。
雅
小雅
原文还给了算法上必须做到的五点，判断题会在这里抠字眼。第一，在计算上产生密钥非常容易；第二，已知公钥的情况下对明文加密在计算上很容易实现；第三，已知私钥的情况下对密文解密在计算上很容易实现；第四，尽管两个密钥在数学上相关，但已知公钥要求得私钥在计算上不可行；第五，已知公钥和密文，要求得明文在计算上不可行。
明
阿明
前三个「容易」，后两个「不可行」，方向别记反。公钥算法有哪些？
雅
小雅
原文点名 RSA、背包密码、McEliece、Diffie Hellman、Rabin、Ong Fiat Shamir、零知识证明的算法、椭圆曲线、ElGamal 等。这些全是公钥阵营，多选题认脸就行。主角是 RSA：1977 年由 Ron Rivest、Adi Shamir 和 Leonard Adleman 提出，以他们的名字命名，是第一个既能用于数据加密也能用于数字签名的算法。
雅
小雅
RSA 的地位原文两句定性：被普遍认为是目前优秀的公钥加密方法之一；但它的安全性一直未能得到理论上的证明。后面这半句判断题爱考——「RSA 的安全性已被数学证明」，错。
明
阿明
那 RSA 到底难在哪？我记得跟大数分解有关。
雅
小雅
对，原文表述是：RSA 的安全性依赖于大数的分解，即求得两个大数——例如大于 100 位的十进制数——的乘积非常容易，但要把一个大数分解为两个素数却非常困难。注意干扰项三件套：离散对数、椭圆曲线是别的公钥算法的数学基础，生成大素数本身也不难，RSA 的命门就是「大数分解的困难性」。
雅
小雅
钥匙的记法：每个用户有公开密钥 PK 等于 N 加 e，私人密钥 SK 等于 N 加 d。N 为两个大素数的乘积，为了保密性更好，一般都取两个 100 位以上的大素数相乘得到 N。e 和 d 根据一定运算法则计算得到，虽然 N、e、d 之间存在一定的计算关系，但攻击者根据 N 和 e 无法求解 d——这就是不对称的来路。
明
阿明
两个 100 位以上的素数乘出 N。加密怎么算？公式念一下。
雅
小雅
先做分组：把需要加密的明文按比特位分成等长的数据段，使每个数据段对应的十进制数小于 N，也就是数据段的长度小于以 2 为底 N 的对数。然后依次对每个明文数据段 m 做加密运算得到密文 c：c 等于 m 的 e 次方 mod N。解密反过来：m 等于 c 的 d 次方 mod N。加密用 e 次方、解密用 d 次方、都对着 N 取余——幂次和取余对象别张冠李戴。
明
阿明
「每个数据段对应的十进制数小于 N」这句，为什么要小于？
雅
小雅
因为取余运算会把一切数压到 0 到 N 减 1 之间，明文段若不小于 N，信息就永久丢了，解密回不去。这个条件本身就会出判断题。数字信封那集你还会看到同一句，先记牢。
雅
小雅
第三条公式是签名。用户 B 要向 A 发送信息 m，且要让 A 确信信息就是 B 本人发出的：B 用自己的私钥 SK 等于 N 加 d，对信息加密得密文 c，c 等于 m 的 d 次方 mod N，发送给 A；A 收到后用 B 的公钥 PK 等于 N 加 e 解密，m 等于 c 的 e 次方 mod N。
明
阿明
发现了：保密是「接收方公钥加密、接收方私钥解密」，签名是「发送方私钥加密、发送方公钥解密」，幂次正好一换。
雅
小雅
总结得漂亮，这两句互为镜像，选择题里问「B 给 A 发签名的文件，A 用什么解密」，答 B 的公钥——不是 A 自己的公钥，用谁的钥匙取决于「谁来验证或解密」。原文的收尾逻辑也念给你：A 之所以能确认信息确实由 B 发出，是因为只有 B 本人才有与该公钥对应的私钥，其他人即使知道公钥，也无法猜出或计算出 B 的私钥来冒充他。
明
阿明
那反过来，B 拿 A 的公钥加密发保密信息，中间人拿到也没用。
雅
小雅
对，两件事合起来就是「保密加签名」要各做一遍。这些在下一集 RSA 结合 MD5 和数字信封里都会落地。本集必背：n 用户两两通信，总密钥数 n 乘 n 减 1 除以 2，10 人 45 把、100 人 4950 把，别算成 90 和 9900；公钥可公开甚至列入公共目录，私钥自己保存；私钥解公钥加密的数据、公钥解私钥加密的数据；
明
阿明
接着背。
雅
小雅
RSA 是 1977 年 Rivest、Shamir、Adleman 三人提出、第一个既能数据加密又能数字签名的算法，安全性依赖大数分解且从未被理论证明；PK 是 N 加 e、SK 是 N 加 d，N 是两个 100 位以上大素数的乘积；加密 c 等于 m 的 e 次方 mod N，解密 m 等于 c 的 d 次方 mod N，签名用 d 次方、验证用 e 次方；明文段的十进制值必须小于 N。
明
阿明
公式和方向都捋顺了。下一集开始讲散列函数和数字签名？
雅
小雅
对，MD5 的 128 位、SHA 的 160 位、RSA 结合 MD5 的六步流程和 2004 年电子签名法，一个数字都别放过。