← COMP5521 全部讲次
L04a · 第 5 周

L04a RSA 签名:私钥盖章、公钥验章

从「怎么证明这条消息是某人发的」讲起,一帧一帧走完先哈希再签的流程,用平方-乘手算 RSA 签名,再看一道不先哈希就会被钻的存在性伪造。

一句话版

上一讲把消息锁进箱子,这一讲在消息上盖章。章用你的私钥盖,谁都能用你的公钥验。这一页用 RSA 实现它:先讲签名长什么样,再手算一次 RSA 签名,最后看为什么签之前一定要先哈希。

RSA 的公钥私钥怎么来、模逆怎么求,见 L03a;扩展欧几里得见 L02a。

先认识这几个词

词 全称 / 读法 一句人话
数字签名 digital signature 用私钥给消息盖章,谁都能用公钥验章
哈希 H(M) hash function,读「H of M」 把任意长的消息压成一段固定长度的「指纹」
不可否认 non-repudiation 签了就赖不掉,第三方也能认定是你签的
平方-乘 square-and-multiply 手算大指数取模的办法:反复平方,挑几项相乘
存在性伪造 existential forgery 没有私钥也能造出某条消息的合法签名,但消息内容由不得自己
Valid / Invalid 有效 / 无效 验签算法只吐这两个结果之一

一个类比:一枚只有你能盖、谁都能验的印章

数字签名像一枚印章。世上只有你能盖,因为只有你握着私钥。盖出来的印谁都能拿放大镜对,因为公钥是公开的。

手写签名有三个性质,数字版照搬:你盖章容易,别人仿造难,任何人核对都容易。

印章和上一讲的挂锁,钥匙方向正好相反。加密用收件人的公钥锁、收件人的私钥开。签名用发件人的私钥盖、发件人的公钥验。盖了章的文件照样明着传,签名不管保密。

盖章之前还有一步:先把文件压成一页摘要,再在摘要上盖。这一步看着多余,后面会看到它堵住了一个漏洞。

类比在哪里失效:

  • 印章能被拓到别的文件上。数字签名和消息绑死,换一份文件,章就对不上。
  • 印章盖歪了还算数。数字签名差一个 bit 就是 Invalid,没有「大致像」这回事。

从零讲起

1. 签名的形状:私钥签、公钥验

它解决什么问题

Bob 收到一份「来自 Alice」的文件。他想知道三件事:真是 Alice 发的吗?路上被改过吗?Alice 事后能不能抵赖?

加密回答不了第一个问题。Alice 的公钥谁都有,谁都能用它造出一段密文。签名要回答的正是这三件事,对应三个词:认证、完整性、不可否认。

从哪来(补充)

Whitfield Diffie 和 Martin Hellman 在 1976 年第一次提出「数字签名方案」这个概念,当时只猜想这样的方案存在。不久后 Rivest、Shamir、Adleman 发明了 RSA 算法,它可以用来做最早的数字签名。

1988 年,Goldwasser、Micali、Rivest 第一次把数字签名的安全要求严格写清楚。出处:Wikipedia: Digital signature

直觉

签名系统有两个盒子。签名盒吃进消息和私钥,吐出签名。验证盒吃进消息、签名和公钥,只吐出「有效」或「无效」。

验证盒不「解出」任何东西。它只回答一个是非题:这枚章是不是握私钥的那个人对这条消息盖的。

Stallings Figure 13.1 两列流程:左列 Bob 把消息 M 先过 cryptographic hash function 得到 h,再用 Bob's private key 跑 digital signature generation algorithm 得到签名 S,输出 M 和 S;右列 Alice 收到 M 和 S,把 M 重新哈希得 h,用 Bob's public key 跑 verification algorithm,返回 signature valid or not valid
图片来源:COMP5521 Lecture 4 Digital Signature, p.8

这张图里签名的是 Bob、验的是 Alice。人名谁当都行,只认一条:私钥签、公钥验。

一步一步看

目标:分五帧跟着 Bob 签名、Alice 验证,看出消息本身不加密,验证靠两边各算一次哈希再核对。

下面五帧把上图拆开走。青绿框是这一帧正在做的事,浅底是做完的,虚线是还没做的。

  1. Bob 准备好消息 M 和自己的私钥。M 不加密,等会儿原样发出。

    签名流程第 1 帧:五个格子从左到右是消息 M、哈希、私钥签、收方重算、公钥验;第一个格子消息 M 原样发出被青绿框标出,其余四格是虚线问号

  2. Bob 把 M 放进哈希函数,得到固定长度的指纹 h = H(M)。

    签名流程第 2 帧:消息 M 已完成变浅底,哈希格子被青绿框标出,写着 h = H(M),后三格仍是虚线;下方说明后面签的是 h 不是 M

  3. Bob 用私钥签 h,得到签名 S,把 M 和 S 一起发给 Alice。

    签名流程第 3 帧:前两格浅底,私钥签格子被青绿框标出,写着 S;下方说明只有握着私钥的 Bob 能做这一步,M 和 S 一起发出

  4. Alice 收到后,自己把 M 再哈希一遍,算出 h。

    签名流程第 4 帧:前三格浅底,收方重算格子被青绿框标出,写着 h = H(M);下方说明 M 在路上被改过一个 bit 这里算出的 h 就会变

  5. Alice 用 Bob 的公钥核对 S 和 h,对得上输出 Valid,对不上输出 Invalid。

    签名流程第 5 帧:前四格浅底,公钥验格子被青绿框标出,写着 Valid?;下方说明对得上输出 Valid,对不上输出 Invalid,验证不解出任何东西

怎么判断

拿到一个方案,问两句话就能判断它是不是签名。

第一句:生成那一步用的是不是只有一个人有的东西?是私钥,就只有他能签。第二句:核对那一步用的是不是谁都能拿到的东西?是公钥,任何第三方都能验。

两句都答「是」,才有不可否认。MAC(消息认证码)也能核对消息没被改,但它用收发双方共享的密钥,双方都能造出同一个 MAC,第三方分不清是谁造的,所以 MAC 给不了不可否认。

再问第三句:消息本身被藏起来了吗?没有,签名不负责保密。要保密得另外加密。

常见误解

以为签名就是「用私钥加密」

裸 RSA 的公式看上去确实像把加密倒过来。可验签返回的是真假,解密返回的是明文;真实系统签的又是哈希值,验的人从签名里拿不回原文。两件事的目的不一样,别混着记。

以为签过名的消息别人就看不到了

签名只加了一枚章,原文 M 照样明着传。想既签名又保密,要先签再用收件人的公钥加密,两件事各用一对钥匙。

试一下

Alice 想让 Bob 确信消息是她发的,又不想让路人看到内容。她该用哪几把钥匙,各用在哪一步?

签名用 Alice 自己的私钥,Bob 用 Alice 的公钥验。保密用 Bob 的公钥加密,Bob 用自己的私钥解。一共两对钥匙,各管一件事。

2. 先补一块:平方-乘(补充)

它解决什么问题

RSA 签名要算 Mᵈ mod n,d 常常是几十、几百,真实系统里更是几千 bit 长。老老实实乘 d 次,手算算不完,电脑也嫌慢。平方-乘把乘法次数压到和 d 的二进制位数差不多。

直觉

想算 3 的 13 次方,不用乘 13 次。先连续平方:3、3²、3⁴、3⁸,每次只要把上一个数平方。13 = 8 + 4 + 1,再把 3⁸、3⁴、3 这三个乘起来就是答案。

每一步都取模,数字就一直小于 n,手算也不会爆。

一步一步看

目标:把 688⁷⁹ mod 3337 拆成连续平方再挑项相乘,看出大指数只需几次乘法就能算出 1570。

用上一张图里的数:算 688⁷⁹ mod 3337。

  1. 把指数 79 写成 2 的幂之和:79 = 64 + 8 + 4 + 2 + 1,二进制是 1001111。

  2. 从 688 开始连续平方,每次取模 3337,得到 688 的 1、2、4、8、16、32、64 次方。

  3. 只挑 79 里用到的那五行:64、8、4、2、1。

  4. 把这五个数一个一个乘起来,每乘一次取模,最后得到 1570。

    平方-乘表格:指数 1、2、4、8、16、32、64 七行,688 的对应次方 mod 3337 依次是 688、2827、3151、1226、1426、1243、18;79 用到 1、2、4、8、64 五行,16 和 32 两行跳过;底部 18 × 1226 × 3151 × 2827 × 688 逐步取模得 1570

怎么算

设要算 a^d mod n,d 的二进制是 d = 2^(i₁) + 2^(i₂) + …。

a^d = a^(2^(i₁)) × a^(2^(i₂)) × …

意思是:把指数拆成几个 2 的幂相加,乘方就拆成几项相乘。每一项 a^(2^i) 都是上一项平方得来,所以全部准备好只要「位数减一」次平方。

取模可以每步都做,依据是 (x × y) mod n = ((x mod n) × (y mod n)) mod n。意思是:中间结果先取模再乘,最后答案不变。

拿 688⁷⁹ 数一下:平方 6 次(从 688 到 688⁶⁴),乘法 4 次(五项相乘),一共 10 次乘法,老实乘要 78 次。

常见误解

以为要先把 688⁷⁹ 整个算出来再取模

那个数有两百多位,手算和计算器都扛不住。平方-乘的要点就是每一步都取模,中间数永远小于 n。

把二进制位挑错了行

79 = 64 + 8 + 4 + 2 + 1,没有 16 和 32。先把指数拆好写在旁边,再去表里挑行,别边算边拆。

试一下

用平方-乘算 5¹³ mod 7。

13 = 8 + 4 + 1。5¹ = 5,5² = 25 ≡ 4,5⁴ ≡ 16 ≡ 2,5⁸ ≡ 4。挑 8、4、1 三行:4 × 2 × 5 = 40 ≡ 5。答案 5。

3. RSA 签名:把加密公式倒过来用

它解决什么问题

手上已经有一对 RSA 密钥,能不能直接拿来签名?能。RSA 签名就是用同一套 n、e、d,把加密时的两步换个顺序。

直觉

加密是用 e 锁、用 d 开。签名换过来:用 d 盖章,用 e 验章。

d 只有你知道,所以只有你盖得出来。e 是公开的,所以谁都能把章「还原」回去,看看和原消息对不对得上。

一步一步看

目标:用课件的小数字从造钥匙走到验签,看出签名用 d 做幂,验证用 e 做幂再比回 M。

用课件这组小数字走一遍:p = 47、q = 71、e = 1019,签 M = 688。

  1. 算模数和 φ,再由 e 求 d:

    量 怎么算 结果
    n 47 × 71 3337
    φ(n) 46 × 70 3220
    d 1019⁻¹ mod 3220 79
    验算 1019 × 79 = 80501 = 25 × 3220 + 1 ✓
  2. 公开 (e, n) = (1019, 3337),自己留着 d = 79。

  3. 签名:S = 688⁷⁹ mod 3337,用上一节的平方-乘算出 1570。

  4. 把 M = 688 和 S = 1570 一起发出。

  5. 验证方算 1570¹⁰¹⁹ mod 3337,得到 688,和收到的 M 相等,输出 Valid。

怎么算

签名:S = Mᵈ mod n

验证:检查 Sᵉ mod n 是否等于 M

意思是:用私钥指数 d 把 M 变成 S,再用公钥指数 e 把 S 变回来,变回来的和原消息一致就算通过。

为什么一定变得回来,推一遍:

Sᵉ ≡ (Mᵈ)ᵉ = M^(de) (mod n)

e 和 d 满足 ed ≡ 1 (mod φ(n)),也就是 ed = 1 + t·φ(n),t 是某个整数。上一讲证过 M^(1 + t·φ(n)) ≡ M (mod n)。所以 Sᵉ ≡ M。

真实系统把 M 换成哈希 h = H(M),公式不变:S = hᵈ mod n,验证 Sᵉ mod n 是否等于重算出来的 h。

钥匙长度还有代价。RSA 的安全强度随模长涨得很慢,签名时间却涨得很快:

RSA 模长与对称强度对照条形图:80 bit 对应 RSA-1024,112 bit 对应 RSA-2048,128 bit 对应 RSA-3072,192 bit 对应 RSA-7680,256 bit 对应 RSA-15360;条形按模长画,越往下越长;底部说明强度从 128 到 256 只翻一倍,模长却从 3072 涨到 15360,签名时间跟模长立方走,2048 比 1024 慢 8 倍

签名时间和密钥长度的立方成正比。模长翻倍,时间变成 2³ = 8 倍,所以 RSA-2048 比 RSA-1024 慢 8 倍。立方的来历:指数变长一倍,乘法次数多一倍;每个数变长一倍,单次大数乘法的代价变成 4 倍;合起来 2 × 4 = 8。

e 也能选得小。课件把 e 换成 3 重做了一遍:验签只要两次乘法,d 却变大,签名变慢。实际系统常用 e = 65537 = 2¹⁶ + 1,二进制只有两个 1,验签快,也避开了 e = 3 的一些已知攻击。

常见误解

把强度对照表最后一行的 15,380 当准确数

课件那张表最后一行印的是 15,380,NIST SP 800-57 的对照表写的是 15360,也就是 15 × 1024。差 20 bit 不影响结论。答题写 15360 更稳,老师坚持课件数字就按课件。

以为签名直接签 M 就行

RSA 一次只能处理小于 n 的数,长文件放不进去。更要紧的是,不先哈希会被伪造,下一节就讲这件事。

试一下

同一组 p = 47、q = 71,改用 e = 3。d 是多少?验证时要算几次乘法?

3220 = 1073 × 3 + 1,所以 d ≡ −1073 ≡ 2147,验算 3 × 2147 = 6441 = 2 × 3220 + 1。验证算 S³,只要两次乘法:先平方,再乘一次。

4. 存在性伪造:为什么要先哈希

它解决什么问题

前面一直说「真实系统先哈希再签」。这一节回答为什么:不哈希的裸 RSA 签名,连私钥都不用,就能造出一对能过验证的消息和签名。

直觉

正常人先有消息,再用私钥算签名。伪造者倒着来:先随手挑一个数当「签名」,再用公钥算出它对应的「消息」。

验证只检查 Sᵉ mod n 和 m 对不对得上。m 本来就是用 Sᵉ 算出来的,当然对得上。

一步一步看

目标:跟着 Eve 先挑签名再反推消息,看出不先哈希时验签照样通过,但她定不了消息内容。

用课件 Exercise-4 的数:n = 2021、e = 155。

  1. Eve 没有 Bob 的私钥,她随手挑一个数当签名:S = 1158。

  2. 用 Bob 的公钥算出「消息」:m = 1158¹⁵⁵ mod 2021 = 1702。

  3. Eve 把 (1702, 1158) 发给 Alice,假装是 Bob 签的。

  4. Alice 验签:1158¹⁵⁵ mod 2021 = 1702,和收到的 m 相等,输出 Valid。

    存在性伪造对照图:上排正常方向,消息 411 用私钥 d = 1583 签成 402,Alice 验 402 的 155 次方 mod 2021 等于 411 接受;下排 Eve 随便挑签名 1158,只用公钥 e = 155 算出消息 1702,Alice 验 1158 的 155 次方 mod 2021 等于 1702 也接受;Eve 没有 d 却造出一对能过验证的消息和签名,但控制不了消息内容

  5. Eve 的局限:1702 是算出来的乱数,她没法让 m 恰好是「转账一万元」。

怎么判断

「存在性」三个字是关键:伪造者能证明「存在」某条消息的合法签名,但挑不了是哪一条。

判断一个签名方案有没有这个漏洞,就问:验证式里的 m 能不能由 S 用公开信息直接算出来?裸 RSA 能(m = Sᵉ mod n),所以有漏洞。

先哈希就堵上了。签的是 h = H(m),Eve 用同样的手法只能得到一个 h。她还得找一条消息,让它的哈希正好等于这个 h,这叫求哈希原像,做不到。

常见误解

以为 Alice「应该」能发现 1702 是假的

验证算法只做一件事:算 Sᵉ mod n 和 m 比。它不判断 m 有没有意义。裸 RSA 签名在数学上就允许这种伪造,防御在协议层(先哈希),不在验证式里。

以为存在性伪造等于能伪造任意消息

两件事差得远。存在性伪造只能造出「某一条」消息的签名,消息内容由不得伪造者。能为指定消息造签名的攻击要强得多,裸 RSA 也挡得住,因为那要知道 d。

试一下

公钥 n = 55、e = 3。Eve 挑 S = 2,她发出的消息是多少?Alice 会接受吗?

m = 2³ mod 55 = 8。Alice 验 2³ mod 55 = 8,等于收到的 m,会接受。可 8 是 Eve 算出来的,她选不了。

把它们串起来

这一页是一条线:先立形状,再算一遍,最后补漏洞。

签名的形状是私钥签、公钥验、先哈希。私钥只有一个人有,所以签得出来就证明是他;公钥谁都有,所以谁都能验。原文照样明传,签名只管认证、完整性和不可否认。

RSA 是这个形状最直接的实现:同一套 n、e、d,把加密的两步换个顺序。手算靠平方-乘,每一步取模。代价是 RSA 的强度随模长涨得慢,签名时间按立方涨,这是后面椭圆曲线登场的理由。

存在性伪造回头说明了第一块为什么非要先哈希。裸 RSA 允许倒着算:先挑签名,再推消息。哈希让这条路走不通。

下一页不换算法,在 RSA 签名前后各乘一个随机数,让签名者签了字却看不到签的是什么。

课件里的坑

  • [补充校订] p.13 表最后一行印的 15,380,NIST SP 800-57 的数字是 15360(= 15 × 1024);写 15360 更稳(p.13)
  • [读图] p.8 图里签名者是 Bob、验证者是 Alice,和 p.4–7 反过来;只认钥匙不认人名(p.8)
  • [计算] p.11 签名一栏留空,要自己手算 688⁷⁹ 的平方链:688² mod 3337 = 2827,后面依次是 3151、1226、1426、1243、18;链错一步,最后的 1570 就对不上(p.11)
  • [板书笔误] p.12 课堂上讲师补充的试 k 求 d 写成 k = 3、d = (3 × 3220 + 1) ÷ 3 = 2147 → 这个式子除不尽,对的是 k = 2:(2 × 3220 + 1) ÷ 3 = 2147(p.12)
  • [考法] p.39 只给公钥 (n, e),第一步是分解 n,不是直接签名;忘了先求 d 整题拿不到分(p.39)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写 RSA 签名和验证两个公式;再把下面 p.39 那道完整例题不看步骤重算一遍,重点练分解 n 和扩展欧几里得;最后用一句话说清存在性伪造为什么控制不了消息内容。三步做完再往下看答案。

必背

  1. 签名用发件人私钥、验签用发件人公钥,与加密方向相反;签名提供认证、不可否认、完整性,不提供保密,原文明传。
  2. 签名流程:签名者先对 M 哈希得 h,再用私钥签 h;验证者重算 h,用公钥验 S,输出 Valid 或 Invalid。
  3. RSA 签名 S = Mᵈ mod n,验证 Sᵉ mod n = M;p = 47、q = 71、e = 1019 时 d = 79,M = 688 签成 1570;实际系统签的是哈希 H(M)。
  4. RSA-2048 约等于 112 bit、RSA-3072 约等于 128 bit 对称强度;签名时间与密钥长度的立方成正比,2048 比 1024 慢 8 倍。
  5. 平方-乘:把指数写成二进制,逐次平方取模,只把二进制位为 1 的那几项乘起来。
  6. 裸 RSA 签名可被存在性伪造:先挑 S 再算 m = Sᵉ mod n,验证照样通过;伪造者控制不了 m,防御是先哈希再签。
  7. Exercise-3:只给公钥 n = 2021、e = 155 时先分解 2021 = 43 × 47,φ = 1932,d = 1583,m = 411 签成 S = 402。

课件例题

例 1(课件 p.11):RSA 签名,填出公钥、私钥和签名

题面:p = 47、q = 71,e = 1019。写出公钥 PK、私钥 SK,对 M = 688 签名,并写出验证要检查什么。

提示

先算 n 和 φ(n),再用扩展欧几里得求 1019 在 mod 3220 下的逆。签名那一步用平方-乘,79 拆成 64 + 8 + 4 + 2 + 1。

解答

n = 47 × 71 = 3337,φ(n) = 46 × 70 = 3220。d = 1019⁻¹ mod 3220 = 79,验算 1019 × 79 = 80501 = 25 × 3220 + 1。

PK = (1019, 3337),SK = 79。签名 S = 688⁷⁹ mod 3337 = 1570。验证检查 1570¹⁰¹⁹ mod 3337 是否等于 688,相等就有效。

手算平方链(每步模 3337):688² = 473344 ≡ 2827,688⁴ ≡ 3151,688⁸ ≡ 1226,688¹⁶ ≡ 1426,688³² ≡ 1243,688⁶⁴ ≡ 18。挑 64、8、4、2、1 五项:18 × 1226 ≡ 2046,× 3151 ≡ 3199,× 2827 ≡ 303,× 688 ≡ 1570。考场不会给这么大的模,链的写法要会。

例 2(课件 p.12):Exercise-1,把 e 换成 3 重做

题面:仍取 p = 47、q = 71,改用 e = 3。求 d,对 M = 688 签名并验证。

提示

先查 gcd(3, 3220) = 1。3220 除以 3 余 1,扩展欧几里得一步就出来。验证只要算 513 的立方。

解答

先查 gcd(3, 3220) = 1:3220 分解后没有因子 3。

求 d:3220 = 1073 × 3 + 1,所以 1 = 3220 − 1073 × 3,d ≡ −1073 ≡ 2147。验算 3 × 2147 = 6441 = 2 × 3220 + 1。

公钥 (3, 3337),私钥 2147。签名 S = 688²¹⁴⁷ mod 3337 = 513。

验证 513³ mod 3337:513² = 263169,减去 78 × 3337 得 2883;2883 × 513 = 1478979,减去 443 × 3337 得 688,有效。

这题的教学点:e 小验签只要两次乘法,d 却变大,签名变慢。

课堂批注(课件 p.12):Exercise-1 换一条路,试 k 求 d,用 CRT 求 S

课堂上讲师补充了两处不同的算法:求 d 不走扩展欧几里得,直接试 ed = kφ(n) + 1 里的 k;求签名把 688²¹⁴⁷ mod 3337 拆到模 47 和模 71 两边。

提示

d = (k × 3220 + 1) ÷ 3,从 k = 1 往上试,能整除就停。签名那步先把 688 和 2147 分别对 47、71 和 46、70 取余,再合并。

解答

试 k:k = 1 时 3221 除以 3 余 2,不行;k = 2 时 6441 = 3 × 2147,整除。d = 2147,和扩展欧几里得的结果相同。课堂板书把 k = 2 打了叉、写成 k = 3 得出,对照 3 × 2147 = 6441 = 2 × 3220 + 1,应当是 k = 2。

模 47:688 = 14 × 47 + 30,2147 = 46 × 46 + 31,由费马小定理 S ≡ 30³¹ ≡ 43 (mod 47)。

模 71:688 = 9 × 71 + 49,2147 = 30 × 70 + 47,S ≡ 49⁴⁷ ≡ 16 (mod 71)。

合并:设 S = 47t + 43,代入 47t + 43 ≡ 16 (mod 71),得 47t ≡ 44。47⁻¹ mod 71 = 68,t ≡ 44 × 68 = 2992 ≡ 10。S = 47 × 10 + 43 = 513。

验证 513³ mod 3337 = 688,和上一题一致。

例 3(课件 p.39):Exercise-3,只给公钥的 RSA 签名

见下方完整例题。

例 4(课件 p.40):Exercise-4,存在性伪造

题面:沿用 n = 2021、e = 155。Eve 不知道 d,她先挑「签名」S = 1158,算出 m 后把 (m, S) 发给 Alice。m 是多少?Alice 验签会接受吗?这说明什么?

提示

Eve 能用的只有公钥。想想验证式算的是什么,她就照着那个式子先算一遍。

解答

m = 1158¹⁵⁵ mod 2021 = 1702。Alice 验签算 1158¹⁵⁵ mod 2021,得 1702,和收到的 m 相等,她会接受,以为 1702 来自 Bob。

这叫存在性伪造:伪造者能造出某条消息的合法签名,但消息是什么由不得她。防御是先哈希再签:Eve 还得找到一条哈希值等于 1702 的消息,这是求原像,做不到。

另外检查 gcd(1158, 2021) = 1,题面条件成立。

完整例题

课件 p.39 这道 take-home 把「只给公钥」和 RSA 签名连在一起,适合练手算,不代表官方承诺考试题型。

n = 2021、e = 155,Bob 签 m = 411(p.39 Exercise-3)

  1. 题目只给公钥,先分解:试除到 45,2021 = 43 × 47。φ = 42 × 46 = 1932。
  2. 求 d = 155⁻¹ mod 1932,扩展欧几里得:1932 = 12 × 155 + 72,155 = 2 × 72 + 11,72 = 6 × 11 + 6,11 = 1 × 6 + 5,6 = 1 × 5 + 1。
  3. 回代得 1 = 28 × 1932 − 349 × 155,所以 d ≡ −349 ≡ 1583。验算 155 × 1583 = 245365 = 127 × 1932 + 1 ✓。
  4. 签名 S = 411¹⁵⁸³ mod 2021 = 402(平方-乘,逐步取模)。
  5. 验证 402¹⁵⁵ mod 2021 = 411 ✓。
  6. 给分点是分解 n 和五步回代,签名那一步考场上只要求写出平方-乘的形式。

变式题(先自己做)

改编自课件 p.11 与 p.40:p = 5、q = 11,e = 3。(1) 求 d,对 M = 4 签名并验证。(2) Eve 只知道公钥,挑 S = 2,她能造出哪条消息的签名?

提示

φ = 40,3 × 27 是多少?签名的指数 27 拆成 16 + 8 + 2 + 1。第 (2) 问照验证式先算一遍。

判分点与答案(非官方评分标准)

判分点:n、φ 写对;d 有验算;平方链每步取模;伪造题写出「消息由不得 Eve」。

(1) n = 55,φ = 4 × 10 = 40。3 × 27 = 81 = 2 × 40 + 1,d = 27。平方链:4¹ = 4,4² = 16,4⁴ = 256 ≡ 36,4⁸ ≡ 31,4¹⁶ ≡ 26。27 = 16 + 8 + 2 + 1:26 × 31 = 806 ≡ 36,36 × 16 = 576 ≡ 26,26 × 4 = 104 ≡ 49。验证 49³ mod 55:49 ≡ −6,(−6)³ = −216 ≡ 4 ✓。

(2) m = 2³ mod 55 = 8。Alice 验 2³ mod 55 = 8,会接受。这是存在性伪造,8 是算出来的,Eve 选不了。

闪卡自测

1. 签名和加密的钥匙方向各是什么?签名提供保密吗?

签名用发件人私钥、验用发件人公钥;加密用收件人公钥、解用收件人私钥。签名不提供保密,原文明传(p.5–7)。

2. 签名提供的三个功能是什么?哪一个 MAC 给不了?

认证、不可否认、完整性。不可否认 MAC 给不了,因为共享密钥双方都能造(p.9)。

3. Figure 13.1 里签的是 M 还是 H(M)?为什么?

签的是 h = H(M)。RSA 一次只能处理小于 n 的数,且哈希堵住存在性伪造(p.8、p.40)。

4. p = 47、q = 71、e = 1019:PK、SK 和 M = 688 的签名各是多少?

n = 3337,φ = 3220,d = 79;PK = (1019, 3337),SK = 79,S = 1570,验证 1570¹⁰¹⁹ mod 3337 = 688(p.11)。

5. RSA-2048 比 RSA-1024 签名慢多少倍?为什么?

8 倍。签名时间与密钥长度的立方成正比,2³ = 8(p.14)。

6. 平方-乘算 688⁷⁹ 要挑哪几行?

79 = 64 + 8 + 4 + 2 + 1,挑 688 的 64、8、4、2、1 次方五行相乘,每步取模(p.11)。

7. Eve 挑 S = 1158 后发出的消息是多少?Alice 接受吗?

m = 1158¹⁵⁵ mod 2021 = 1702,Alice 验签相等会接受。这是存在性伪造,先哈希再签可防(p.40)。

下一讲

下一页讲 Chaum 盲签名:签名者签了字,却看不到签的是什么。数学上只是在 RSA 签名前后各乘一个随机数,见 L04b。

下一讲 →
L04b L04b 盲签名:隔着信封盖章

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。