MIT 6.858 计算机系统安全讲义 2014 秋季（三）（1）

SSL/TLS 和 HTTPS

**注意：**这些讲座笔记略有修改自 2014 年 6.858 课程网站上发布的笔记。

这节课涉及两个相关主题：

• 如何在比 Kerberos 更大规模上加密保护网络通信？

• 技术：证书

• 如何将网络流量的加密保护整合到 Web 安全模型中？

• HTTPS，安全 cookie 等。

对称与非对称加密

**回顾：**两种加密方案。

• E是加密，D是解密
  
• 对称密钥加密意味着相同密钥用于加密和解密

• 密文 = E_k(明文)
  
• 明文 = D_k(密文)
  

• 非对称密钥（公钥）加密：加密和解密密钥不同

• 密文 = E_PK(明文)
  
• 明文 = D_SK(密文)
  
• PK和SK分别称为公钥和私钥（秘密密钥）
  

• 公钥加密比对称加密慢几个数量级
  
• 加密提供数据保密性，但我们通常也希望完整性。
  
• *消息认证码（MAC）*使用对称密钥可以提供完整性。

• 如果你对更多细节感兴趣，请查看HMAC。

• 可以使用公钥加密进行签名和验证，几乎相反：

• 使用秘密密钥生成签名（计算D_SK）
  
• 使用公钥检查签名（计算E_PK）
  

Kerberos

• 中央 KDC 知道所有主体及其密钥。
  
• 当A想要与B交流时，A要求 KDC 发放一张票。
  
• 票据包含一个由 KDC 生成的A与B通话的会话密钥。
  

为什么 Kerberos 不够？

• 例如，为什么 Web 不基于 Kerberos？
  
• 可能没有一个单一的 KDC 被信任生成会话密钥。
  
• 不是每个人都可能在这个单一 KDC 上有帐户。
  
• 如果用户每次访问网站都联系 KDC，KDC 可能无法扩展。
  
• 不幸的是，KDC 知道每个用户连接到哪个服务。

• 这些限制在对称加密中很大程度上是不可避免的。

*备选方案：*使用公钥加密

• 假设A知道B的公钥。
  
• 不想一直使用公钥加密（速度慢）。
  
• 用于在A和B之间建立安全连接的草案协议：

• A生成一个随机对称会话密钥S。
  
• A为PK_B加密S，发送给B。
  
• 现在我们有A和B之间共享的秘密密钥S，可以加密和
  
• 使用对称加密验证消息，类似于 Kerberos。
  

这个草案协议的好处：

• A的数据只被B看到。

• 只有B（具有SK_B）才能解密S。
  
• 只有B才能解密使用S加密的数据。
  

• 不需要类似 KDC 的中央机构来分发会话密钥。
  

这个草案有什么问题？

• 对手可以记录并稍后重放A的流量；B不会注意到。

• 解决方案：让B发送一个随机值（nonce）。
  
• 将 nonce 合并到最终主密钥S' = f(S, nonce)中。
  
• 通常，S被称为预主密钥，S'被称为主密钥。
  
• 建立S'的过程称为“握手”。
  

• 对手可以冒充A，发送另一个对B的对称密钥。

• 如果B在乎A是谁，有许多可能的解决方案。
  
• 例如，B还选择并使用PK_A加密的对A发送对称密钥。
  
• 然后A和B都使用两个密钥组合的哈希。
  
• 这大致是 TLS 客户端证书的工作原理。
  

• 对手稍后可以获取SK_B，解密对称密钥和所有消息。

• 解决方案：使用类似 Diffie-Hellman 的密钥交换协议，
  
• 提供前向保密，如上次讲座中讨论的。
  

难题： 如果两台计算机都不知道对方的公钥怎么办？

• 常见方法：使用可信第三方生成证书。
  
• 证书是元组（名称，公钥），由证书颁发机构签名。
  
• 含义：证书颁发机构声称名称的公钥是公钥。
  
• B除了发送证书外，还向A发送一个公钥。
  
• 如果A信任证书颁发机构，继续如上操作。
  

为什么证书可能比 Kerberos 更好？

• 客户端每次连接到新服务器时无需与 KDC 通信。
  
• 服务器可以向客户端呈现证书；客户端可以验证签名。
  
• KDC 不参与生成会话密钥。
  
• 可以支持没有长期密钥/证书的“匿名”客户端。
  

保护 Web 浏览器的计划：HTTPS

• 新协议：https 而不是 http（例如，www.paypal.com/）。
  
• 需要保护几样东西：

• (A) 数据在网络上传输。
  
• (B) 用户浏览器中的代码/数据。
  
• © 用户看到的 UI。
  

• (A)如何确保数据在网络上不被窃听或篡改？

• 使用 TLS（一种使用证书的加密协议）。
  
• TLS 加密和认证网络流量。
  
• 协商密码（和其他功能：压缩，扩展）。
  
• 协商是明文进行的。
  
• 包括对所有握手消息进行 MAC 认证。
  

• (B)如何保护用户浏览器中的数据和代码？

• 目标： 将浏览器安全机制与 TLS 提供的内容连接起来。
  
• 记住浏览器有两个主要的安全机制：
  
• 同源策略。
  
• Cookie 策略（略有不同）。
  
• 与 HTTPS/TLS 的同源策略。
  
• TLS 证书名称必须与 URL 中的主机名匹配。

• 在我们的示例中，证书名称必须是 www.paypal.com。
  
• 也允许一级通配符（*.paypal.com）。
  
• 浏览器信任多个证书颁发机构。
  

• 来源（来自同源策略）包括协议。

• http://www.paypal.com/ 与 https://www.paypal.com/ 不同。
  
• 在这里，我们关心数据的完整性（例如 JavaScript 代码）。
  
• 结果： 非 HTTPS 页面无法篡改 HTTPS 页面。
  
• 原因： 非 HTTPS 页面可能已被对手修改。
  

• 使用 HTTPS/TLS 的 Cookie。

• 服务器证书帮助客户端区分服务器。
  
• Cookie（用户凭证的常见形式）有一个“安全”标志。
  
• 安全的 Cookie 只能随 HTTPS 请求发送。
  
• 非安全的 Cookie 可以随 HTTP 和 HTTPS 请求发送。
  

• 如果对手篡改 DNS 记录会发生什么？

• 好消息：安全性不依赖于 DNS。
  
• 我们已经假设对手可以篡改网络数据包。
  
• 错误的服务器将不知道与证书匹配的正确私钥。
  

• ©最后，用户可以直接输入凭据。如何确保安全？

• 浏览器中的锁图标告诉用户他们正在与 HTTPS 站点交互。
  
• 浏览器应该向用户指示站点证书中的名称。
  
• 用户应验证他们打算提供凭据的站点名称。
  

这个计划怎么会出错？

• 正如你所料，上述每一步都可能出错。
  
• 不是详尽的列表，但涉及 ForceHTTPS 想要解决的问题。
  

1 (A) 密码学

SSL/TLS 的密码部分曾受到一些攻击。

• Rizzo 和 Duong 的攻击可以让对手通过在单个连接上发出许多精心选择的请求来学习一些明文。参考
  
• 同一人使用压缩进行最近的攻击，在 iSEC 讲座中提到。参考
  
• 最近，更多的填充预言攻击。参考
  
• 一些服务器/CA 使用弱加密，例如使用 MD5 的证书。
  
• 一些客户端选择弱加密（例如，Android 上的 SSL/TLS）。参考
  
• 但是，密码学很少是系统中最薄弱的部分。
  

2 (B) 服务器认证

对手可能能够为他人的名字获得证书。

• 以前需要在公司抬头纸上传真请求（但如何检查？）
  
• 现在通常需要在 root@domain.com 或类似位置接收秘密令牌
  
• 安全性取决于最不安全证书颁发机构的政策
  
• 大多数浏览器中有数百个受信任的证书颁发机构
  
• 2011 年发生了几起 CA 被破坏的事件（gmail、facebook 等的证书）。参考
  
• 服务器可能被入侵，相应的私钥被盗。
  

如何处理受损的证书（例如，无效证书或被盗私钥）？

• 证书有到期日期。
  
• 每次请求都要与 CA 检查证书状态很难扩展。
  
• 一些 CA 发布的证书吊销列表（CRL），但其中的证书相对较少

• 其中一些（抽查：大多数没有被吊销的证书）。

• 客户端必须定期下载 CRL。

• 如果许多证书被吊销，可能会很慢。
  
• 如果很少或零个证书被吊销，则不是问题，但并不太有用。
  

• OCSP：在线证书状态协议。

• 查询证书是否有效。
  
• 一个问题：OCSP 协议不要求签署“稍后再试”消息。参考
  

• 用于猜测证书是否正常的各种启发式方法。

• CertPatrol，EFF 的 SSL Observatory 等。
  
• 不像“证书是否更改那么容易”。网站有时会测试新的 CA。
  

• 问题：在线吊销检查是软失败。

• 主动网络攻击者可以使检查不可用。
  
• 浏览器不喜欢在侧通道上阻塞。
  
• 性能、单点故障、强制门户等问题。[ 参考：https://www.imperialviolet.org/2011/03/18/revocation.html ]
  

• 实际上，浏览器在重大违规事件后会推送黑名单更新。[ 参考：https://www.imperialviolet.org/2012/02/05/crlsets.html ]
  

用户忽略证书不匹配错误。

• 尽管证书很容易获得，但许多网站配置错误。
  
• 有些人不想处理获得证书的（非零）成本。
  
• 其他人忘记更新它们（证书有到期日期）。
  
• 最终结果：浏览器允许用户覆盖不匹配的证书。

• 问题在于：人现在成为决定证书是否有效的过程的一部分。
  
• 开发人员很难确切知道浏览器将接受哪些证书。
  

• 根据经验，Chrome 显示的约 60% 的绕过按钮被点击通过。（尽管这些数据可能已经过时…）
  

用户接受无效证书的风险是什么？

• 可能是良性的（过期证书，服务器操作员忘记续订）。
  
• 可能是中间人攻击，连接到对手的服务器。
  
• 为什么这是不好的？

• 用户的浏览器将用户的 cookie 发送给对手。
  
• 用户可能会将敏感数据输入对手的网站。
  
• 用户可能会认为页面上的数据来自正确的网站。
  

3 (B) 混合 HTTP 和 HTTPS 内容

• 网页的来源由页面本身的 URL 确定。
  
• 页面可以有许多嵌入元素：

• Javascript 通过 <SCRIPT> 标签
  
• CSS 样式表通过 <STYLE> 标签
  
• Flash 代码通过 <EMBED> 标签
  
• 图像通过 <IMG> 标签
  

• 如果对手能够篡改这些元素，可能控制页面。

• 特别是，Javascript 和 Flash 代码可以控制页面。
  
• CSS：控制较少，但仍然可滥用，尤其是使用复杂的属性选择器。
  

• 开发人员可能不会包含来自攻击者网站的 Javascript。
  
• 但是，如果 URL 不是 HTTPS，对手可以篡改 HTTP 响应。
  
• 另一种方法：明确验证嵌入元素。
  
• 例如，可以包含正在加载的 Javascript 代码的哈希值。

• 防止对手篡改响应。
  
• 不需要完整的 HTTPS。
  

• 可能会在不久的将来在浏览器中部署。参考
  

4 (B) 保护 cookie

• Web 应用程序开发人员可能会犯错误，忘记了 Secure 标志。
  
• 用户访问 http://bank.com/ 而不是 https://bank.com/，泄漏 cookie。
  
• 假设用户只访问 https://bank.com/。

• 为什么这仍然是一个问题？

• 对手可以导致另一个 HTTP 网站重定向到 http://bank.com/。
  
• 即使用户从未访问任何 HTTP 网站，应用程序代码可能存在错误。
  

• 一些网站通过 HTTPS 提供登录表单，并通过 HTTP 提供其他内容。
  
• 在同时使用 HTTP 和 HTTPS 时要小心。

• 例如，Google 的登录服务在请求时创建新的 cookie。
  
• 登录服务有自己的（安全的）cookie。
  
• 可以通过加载登录的 HTTPS URL 请求登录到 Google 网站。
  
• 以前还可以通过不安全的 cookie 登录。
  
• ForceHTTPS 通过将 HTTP URL 重定向到 HTTPS 来解决问题。参考
  

• cookie 完整性问题。

• 在 http://bank.com 上设置的非 Secure cookie 仍然发送到 https://bank.com。
  
• 无法确定是谁设置了 cookie。
  

5（C） 用户直接输入凭据

• 钓鱼攻击。
  
• 用户不检查锁图标。
  
• 用户不仔细检查域名，不知道要查找什么。

• 例如，拼写错误的域名（paypa1.com），unicode

• Web 开发人员将登录表单放在 HTTP 页面上（目标登录脚本是 HTTPS）。

• 对手可以修改登录表单以指向另一个 URL。
  
• 登录表单没有受到篡改的保护，用户无法辨别。
  

ForceHTTPS

ForceHTTPS（本文）如何解决这些问题？

• 服务器可以在用户的浏览器中为自己的主机名设置标志。

• 将 SSL/TLS 证书配置错误变成致命错误。
  
• 将 HTTP 请求重定向到 HTTPS。
  
• 禁止非 HTTPS 嵌入（+ 为它们执行 ForceHTTPS）。
  

ForceHTTPS 解决了哪些问题？

• 主要是 2、3，某种程度上是 4（见上面的列表）

• 用户接受无效证书。
  
• 开发人员错误：嵌入不安全的内容。
  
• 开发人员错误：忘记将 cookie 标记为 Secure。
  
• 对手通过 HTTP 注入 cookie。
  

这真的有必要吗？我们只能使用 HTTPS，设置 Secure cookie 等吗？

• 用户仍然可以点击错误，因此对于＃2 仍然有帮助。
  
• 对于＃3 来说并不是必要的，假设 Web 开发人员永远不会犯错误。
  
• 对于＃4 仍然有帮助。

• 将 cookie 标记为 Secure 可以确保保密性，但不能保证完整性。
  
• 主动攻击者可以在 http://bank.com 上提供虚假设置，并设置 cookie。

• 用于 https://bank.com。 （https://bank.com 无法区分）

为什么不为所有人打开 ForceHTTPS？

• HTTPS 站点可能不存在。
  
• 如果是这样，可能不是同一个站点（https://web.mit.edu 是

• 认证，但 http://web.mit.edu 不是）。

• HTTPS 页面可能期望用户点击通过（自签名证书）。
  

实施 ForceHTTPS

• ForceHTTPS 位存储在 cookie 中。
  
• 有趣的问题：

• 状态耗尽（ForceHTTPS cookie 被驱逐）。
  
• 拒绝服务（强制整个域；通过 JS 强制；通过 HTTP 强制）。

• 为什么 ForceHTTPS 只允许特定主机，而不是整个域？
  
• 为什么 ForceHTTPS 要求通过标头设置 cookie，而不是通过 JS？
  
• 为什么 ForceHTTPS 要求通过 HTTPS 设置 cookie，而不是 HTTP？
  

• 引导（如何获取 ForceHTTPS 位；如何避免隐私泄漏）。

• 可能的解决方案 1：DNSSEC。
  
• 可能的解决方案 2：在 URL 名称中嵌入 ForceHTTPS 位（如果可能）。
  
• 如果有一种方法可以从服务器所有者那里获取一些经过身份验证的位（DNSSEC、URL 名称等），我们是否应该直接获取公钥？
  
• 困难：用户网络不可靠。浏览器不愿意在侧通道请求上阻止握手。
  

ForceHTTPS 的当前状态

• 一些 ForceHTTPS 的想法已被采纳为标准。
  
• HTTP Strict-Transport-Security 头部类似于 ForceHTTPS cookie。参考：RFC6797，参考：HTTP Strict Transport Security

• 使用标题而不是魔术 Cookie：

• Strict-Transport-Security：max-age=7884000；includeSubDomains

• 将 HTTP 链接转换为 HTTPS 链接。
  
• 禁止用户覆盖 SSL/TLS 错误（例如，错误的证书）。
  
• 可选择应用于所有子域。

• 这有什么用？非安全和伪造的 cookie 可能会泄漏或设置在子域上。

• 可选择为用户提供手动启用的界面。
  
• 在 Chrome、Firefox 和 Opera 中实施。
  
• 引导程序在很大程度上尚未解决。
  
• Chrome 有一个硬编码的预加载列表。
  

• IE9，Firefox 23 和 Chrome 现在默认阻止混合脚本。

• 参考：结束混合脚本漏洞，
  
• 参考：Firefox 中启用混合内容阻止，
  
• 参考：保护消费者免受恶意混合内容
  

在这个领域的另一个最近的实验：HTTPS-Everywhere。

• 专注于 ForceHTTPS 的“高级用户”方面。
  
• 允许用户强制某些域名使用 HTTPS。
  
• Tor 和 EFF 之间的合作。
  
• 适用于 Firefox 和 Chrome 的附加组件。
  
• 附带用于重写流行网站 URL 的规则。
  

SSL/TLS 中解决问题的其他方法

• 更好的工具/更好的开发人员以避免编程错误。

• 将所有敏感 cookie 标记为 Secure（#4）。
  
• 避免任何不安全的嵌入（#3）。
  
• 不幸的是，似乎容易出错。
  
• 不帮助最终用户（需要开发者参与）。
  

• EV 证书。

• 尝试解决问题 5：用户不知道在证书中寻找什么。
  
• 除了 URL，还嵌入公司名称（例如，“PayPal, Inc.”）
  
• 通常显示为 URL 栏旁边的绿色框。
  
• 为什么这样更安全？
  
• 什么情况下实际上会提高安全性？
  
• 如果用户开始期望 EV 证书，可能间接有助于解决问题 2。
  

• 黑名单弱加密。

• 浏览器开始拒绝证书上的 MD5 签名（iOS 5，Chrome 18，Firefox 16）
  
• 以及 Chrome 18、OS X 10.7.4、Windows XP+最近更新后的 RSA 密钥< 1024位。
  
• 甚至被 Chrome 淘汰的 SHA-1。参考：逐步淘汰 SHA1
  

• OCSP 装订。

• OCSP 响应由 CA 签名。
  
• 服务器在握手中发送 OCSP 响应，而不是在线查询（#2）。
  
• 实际上是一个短暂的证书。
  
• 问题：

• 尚未广泛部署。
  
• 只能装订一个 OCSP 响应。
  

• 密钥固定。

• 仅接受由每个站点白名单的 CA 签名的证书。
  
• 消除对最不安全 CA 的依赖（#2）。
  
• 目前在 Chrome 中有一个硬编码的站点列表。
  
• 2011 年 Diginotar 妥协是因为密钥固定。
  
• 计划添加站点广告固定的机制。

• 参考：IETF 关于 websec 关键固定的草案
  
• 参考：tack.io
  

• 与 ForceHTTPS 中的引导困难相同。
  

其他参考资料

• www.imperialviolet.org/2012/07/19/hope9talk.html

RSA 的侧信道攻击

注意： 这些讲义略有修改自 6.858 课程网站 上发布的讲义，时间为 2014 年。

侧信道攻击

• 历史上，担心电磁信号泄露。NSA TEMPEST。
  
• 广泛地，系统可能需要担心许多意外的方式
  
• 信息可能会被泄露。
  

示例设置： 服务器（例如，Apache）有一个 RSA 私钥。

• 服务器使用 RSA 私钥（例如，解密来自客户端的消息）。
  
• 服务器的计算信息泄露给客户端。
  

已经研究了许多信息泄漏：

• 解密需要多长时间。
  
• 解密如何影响共享资源（缓存、TLB、分支预测器）。
  
• CPU 本身的辐射（射频、音频、功耗等）。
  

侧信道攻击不一定与加密相关。

• 例如，操作时间与密码中哪个字符不正确有关。
  
• 或时间与你和某个用户在 Facebook 上有多少共同好友有关。
  
• 或加载页面在浏览器中需要多长时间（取决于是否被缓存）。
  
• 或基于点阵打印机的声音恢复打印文本。参考
  
• 但对密码或密钥的攻击通常是最具破坏性的。
  

对手可以分析信息泄漏，用它来重建私钥。

• 目前，本文描述的系统上的侧信道攻击是罕见的。

• 例如，Apache web 服务器运行在某个连接到互联网的机器上。
  
• 通常存在其他一些漏洞，更容易利用。
  
• 慢慢地成为一个更大的关注点：新的侧信道（虚拟机）、更好的攻击。
  

• 侧信道攻击更常用于攻击受信任/嵌入式硬件。

• 例如，芯片在智能卡上运行加密操作。
  
• 通常这些具有较小的攻击面，没有太多其他方式可以进入。
  
• 如论文所述，一些密码协处理器设计用于避免此类攻击。
  

“远程时间攻击是实际的” 论文的贡献是什么？参考

• 时间攻击已知已久。
  
• 本文：可能通过网络攻击标准的 Apache web 服务器。
  
• 使用了许多关于时间攻击的先前工作的观察/技术。
  
• 要理解这是如何工作的，首先让我们看一些 RSA 的内部…
  

RSA：高级计划

• 选择两个随机素数，p和q。

• 让 n = p*q。

• 今天一个合理的密钥长度，即 |n| 或 |d|，是 2048 位。
  
• 欧拉函数phi(n)：与n互质的Z_n^*元素的数量。

• 定理 [此处无证明]：a^(phi(n)) = 1 mod n，对所有的 a 和 n。

• 那么，如何加密和解密？

• 选择两个指数d和e，使得m^(e*d) = m (mod n)，这

• 意味着 e*d = 1 mod phi(n)。

• 加密将是 c = m^e (mod n)；解密将是 m = c^d (mod n)。
  

• 如何获得这样的e和d？

• 对于 n=pq，phi(n) = (p-1)(q-1)。
  
• 如果我们知道phi(n)，很容易计算d=1/e。扩展欧几里得算法
  
• 在实践中，选择小的e（例如，65537），使加密更快。
  

• 公钥是(n, e)。
  
• 私钥原则上是(n, d)。

• 注意：p和q必须保密！
  
• 否则，对手可以像我们上面做的那样从e计算d。
  
• 知道p和q对快速解密也很有帮助。
  
• 因此，在实践中，私钥也包括(p, q)。
  

RSA 在“安全”使用上有些棘手–如果直接使用 RSA，请小心！

• 密文是可乘的。

• E(a)*E(b) = a^e * b^e = (ab)^e。
  
• 可以让对手操纵加密，生成新的加密。
  

• RSA 是确定性的。

• 加密相同的明文每次都会生成相同的密文。
  
• 对手可以知道何时重新加密相同的内容。
  

• 通常通过在加密前对消息进行“填充”来解决。OAEP

• 取明文消息位，加上明文前后的填充位。
  
• 加密组合位（总位数必须小于|n|位）。
  
• 填充包括随机性，以及固定位模式。
  
• 有助于检测篡改（例如，密文乘法）。
  

如何实现 RSA？

• **关键问题：**快速模指数运算。

• 一般来说，是二次复杂度。

• 两个 1024 位数相乘很慢。
  
• 计算 1024 位数的模很慢（1024 位除法）。
  

优化 1：赛里斯剩余定理（CRT）。

• 回想一下 CRT 的原理：

• 如果x==a1 (mod p)和x==a2 (mod q)，其中p和q是互质的，
  
• 那么就有一个唯一解x==a (mod pq)。

• 并且，有一种高效的算法来计算a。

• 假设我们想要计算m = c^d (mod pq)。
  
• 可以计算m1 = c^d (mod p)，以及m2 = c^d (mod q)。
  
• 然后使用 CRT 从m1、m2计算m = c^d (mod n)；这是唯一且快速的。
  
• 计算m1（或m2）比直接计算m快约 4 倍（~二次）。
  
• 使用 CRT 从m1和m2计算m的速度与忽略不计。
  
• 因此，大约加速 2 倍。
  

优化 2：重复平方和滑动窗口。

• 计算c^d的朴素方法：将c乘以自身，d次。
  
• 更好的方法，称为重复平方：

• c^(2x) = (c^x)²
  
• c^(2x+1) = (c^x)² * c
  
• 要计算c^d，首先计算c^(floor(d/2))，然后使用上述方法计算c^d。
  
• 递归应用，直到计算到c⁰ = 1。
  
• 平方次数：|d|（表示d所需的位数）。
  
• 乘法次数：d中的 1 位数。
  

• 更好的方法（有时），称为滑动窗口：

• c^(2x) = (c^x)²
  
• c^(32x+1) = (c^x)³² * c
  
• c^(32x+3) = (c^x)³² * c³
  
• …
  
• c^(32x+z) = (c^x)³² * c^z，通常情况下（其中z<=31）。
  
• 可以预先计算所有必要的c^z幂的表，存储在内存中。
  
• 选择 2 的幂常数（例如，32）取决于使用情况。

• 成本：额外内存，额外时间来预先计算幂。

• 注意：仅预先计算c的奇数次幂（对于偶数使用第一条规则）。
  
• OpenSSL 使用 32（具有 16 个预先计算的条目的表）。
  

优化 3：蒙哥马利表示。

• 每次（平方或乘法后）都进行mod p减少是昂贵的。

• 典型实现：进行长除法，找到余数。
  
• 难以避免减少：否则，值会呈指数增长。
  

• 理念（由彼得·蒙哥马利提出）：在另一种表示中进行计算。

• 将基数（例如c）提前转换为不同的表示。
  
• 在这种表示中执行模运算（会更便宜）。
  
• 完成后将数字移回原始表示。
  
• 理想情况下，减少的节省应超过移位的成本。
  

• 蒙哥马利表示：将所有内容乘以某个因子 R。

• a mod q <-> aR mod q
  
• b mod q <-> bR mod q
  
• c = a*b mod q <-> cR mod q = (aR * bR)/R mod q
  
• 每个在蒙哥马利空间中的乘法（或平方）需要除以R。
  

• 蒙哥马利表示中模乘法为何更便宜？

• 选择R使得除以R更容易：R = 2^|q|（1024 位密钥为2⁵¹²）。
  
• 因为我们除以R，通常不需要进行mod q。

• |aR| = |q|
  
• |bR| = |q|
  
• |aR * bR| = 2|q|
  
• |aR * bR / R| = |q|
  

• 如何便宜地除以R？

• 仅当低位为零时才有效。

• 观察： 因为我们关心值mod q，所以q的倍数并不重要。
  
• 技巧：向被除以R的数字添加q的倍数，使低位为 0。

• 例如，假设R=2⁴ (10000)，q=7 (111)，将x=26 (11010)除以 R。
  
• x+2q = (二进制) * 101000
  
• x+2q+8q = (二进制) 1100000
  
• 现在，可以轻松地除以R：结果是二进制 110（或 6）。
  
• 通常，总是可能的：
  
• q的最低位为 1（q是质数），因此可以"击倒"任何位。
  
• 要"击倒"比特k，添加2^k * q
  
• 要击倒低位l，添加q*(l*(-q^-1) mod R)
  
• 然后，除以R意味着简单地丢弃低零位。
  

• 一个仍未解决的问题：结果将会< R，但可能会> q。

• 如果结果恰好大于q，需要减去q。
  
• 这被称为"额外减少"。
  
• 计算x^d mod q时，Pr[额外减少] = (x mod q) / 2R。

• 这里，假设x已经处于蒙哥马利形式。
  
• 直觉： 随着我们乘以更大的数字，将更频繁地溢出。

MIT 6.858 计算机系统安全讲义 2014 秋季（三）（2）https://developer.aliyun.com/article/1484158