密码学

密码学

学习目标

完美保密性(perfect secrecy)的定义
一次性密码本加密方案(one-time pad encryption scheme)
完美保密性需要长密钥的必然性
计算安全性(computational secrecy)与去随机化的一次性密码本
公钥加密
前沿课题浅尝

Quote

“人类才智创造出的任何密码, 都将被人类才智破解. “

-Edgar Allen Poe, 1841年

Quote

“一个好的伪装不应暴露此人的身高. “

-Shafi Goldwasser和Silvio Micali, 1982年

Quote

“一个系统若满足: 当敌人截获到密文后, 该密文代表各消息的后验概率, 与截获前这些消息本身的先验概率完全相同, 则称该系统具有‘完美保密性’. 研究表明, 完美保密性是可以实现的, 但若消息数量有限, 则要求相同数量的可能密钥. “

-Claude Shannon, 1945年

Quote

“我们今天正站在密码学革命的门槛上. “

-Whitfeld Diffie和Martin Hellman, 1976年

密码学——研究“秘密书写“的艺术或科学——已经存在了数千年. 在这几乎所有的漫长岁月里, Edgar Allen Poe上面的那句名言都一直成立. 的确, 密码学的历史中充斥着那些曾被信为安全, 尔后被攻破的密码系统的“形象化“的残骸, 有时甚至包括那些错误地将信任寄托于这些密码系统的人们所留下的真实骸骨.

然而, 在过去的几十年里, 情况发生了变化, 这正是指(并且在很大程度上由)上文引用的Diffie和Hellman于1976年的论文所预示的那场“革命“. 人们已经找到了新型的密码系统, 尽管遭到了巨大的破解努力——这些努力涉及的人类才智和计算能力的规模完全超越了Allen Poe时代的“密码破译者“, 但它们至今仍未被攻破. 更令人称奇的是, 这些密码系统不仅看似牢不可破, 而且是在更为严苛的条件下实现的. 如今的攻击者不仅拥有更强大的计算能力, 他们可供利用的数据也更多. 在爱伦·坡的时代, 攻击者若能获得少量几个已知消息的加密结果, 就算很幸运了. 而如今, 攻击者可能拥有海量数据——TB级别甚至更多——可供其使用. 实际上, 有了公钥(public key)加密, 攻击者甚至可以随心所欲地生成任意多的密文.

成功的关键在于, 人们对于如何定义密码工具的安全性, 以及如何将这种安全性与具体的计算难题联系起来, 有了更清晰的理解. 密码学是一个广阔且不断发展的领域, 本章仅能触及其中部分内容.

本章: 一个直观的概述

密码学无法在一章的篇幅之内详尽解释, 因此本章仅是对密码学的一次“浅尝“, 重点关注其与计算复杂性理论最相关的方面. 更全面的论述, 请参阅我的讲义, 本章即改编自该讲义. 我们将讨论一些“经典密码系统“, 并展示如何从数学上定义加密的安全性, 以及如何使用一次性密码本(one-time pad)来实现一种可证明满足该定义的加密方法. 随后, 我们将看到该定义的根本局限性, 以及为了规避这一局限, 我们如何通过仅关注计算资源有限的攻击者来放宽安全性要求. 这种计算安全性的概念与计算复杂性以及 $P$ 与 $NP$ 问题有着内在的联系. 我们还将简要介绍一些远远超出传统加密范畴的“悖论式“的密码学构造, 包括公钥密码学, 全同态加密以及多方安全计算.

古典密码系统

历史上, 人们设计出了大量的密码系统, 而它们也相继被破译. 在此, 我们仅讲述其中几个故事. 1587年, 苏格兰女王Mary, 也是当时英格兰王位的继承人, 密谋刺杀她的表亲——英格兰女王Elizabeth一世, 以便自己能登上王位, 并最终摆脱已持续18年的软禁生活. 作为这个复杂阴谋的一部分, 她向Anthony Babington爵士发送了一封加密的信件.

maryscottletterfig

图 21.1. Mary女王与Babington爵士之间加密通信的片段

玛丽使用的是所谓的替换加密(substitution cipher), 其中每个字母都被转换成另一个晦涩的符号(见图 21.1). 乍一看, 这样一封信似乎相当费解——一串毫无意义的奇怪符号. 然而, 稍加思索, 人们可能会注意到这些符号重复出现了多次, 而且不同的符号重复的频率也不同. 那么, 我们不难推测, 也许每个符号对应一个不同的字母, 而出现更频繁的符号则对应字母表中出现频率更高的字母. 基于这个观察, 距离完全破解该密码就只差一小步了. 事实上, 伊丽莎白女王的间谍们正是这样做的, 他们利用解码后的信件获知了所有同谋者, 并给玛丽女王定了叛国罪, 她因此被处决. 迷信于表面的安全措施(例如使用“难以理解的“符号)是密码使用者们年复一年反复落入的陷阱. (正如许多事情一样, 一部精彩的XKCD漫画也以此为题材, 见图 21.2)

XKCDnavajofig

图 21.2. XKCD对于使用生僻符号能增加安全性的看法

Vigenère加密以Blaise de Vigenère的名字命名, 他在1586年的一本书中描述了这种方法(尽管它是由Bellaso更早发明的). 其思想是使用一组替换加密: 如果有 $n$ 种不同的密码, 那么明文的第一个字母用第一种密码编码, 第二个字母用第二种密码, 第 $n$ 个字母用第 $n$ 种密码, 然后第 $n + 1$ 个字母再次用第一种密码编码. 密钥 $k$ 通常是一个由 $n$ 个字母组成的单词或短语. 第 $i$ 种替换密码会将每个字母按照从A到 $k_{i}$ 所需的相同偏移量进行移位. 例如, 如果 $k_{i}$ 是C, 那么第 $i$ 种替换密码就会将每个字母向后移动两位. 这种方法“抹平“了频率, 使得频率分析变得困难得多, 这也是为什么这种密码在300多年里被认为“不可破译“, 并赢得了“不可破译的密码“(le chiffre indéchiffrable)绰号的原因. 尽管如此, Charles Babbage还是在1854年破解了Vigenère加密(尽管他没有发表). 1863年, Friedrich Kasiski破译了该密码并发表了结果. 其思路是, 一旦你猜出了密钥的长度, 就可以将任务简化为破解一个简单的替换加密, 而后者可以通过频率分析来完成(你能想到为什么吗? ). 美国内战期间, 南方邦联的将军们经常使用维吉尼亚密码, 而他们的信息也经常被联邦军官分析.

tmplabelfig1

图 21.3. 南方邦联用于进行Vigenère加密的密码盘

tmplabelfig2

图 21.4. 南方邦联的信息“Pemberton将军: 你无法从河这边得到任何帮助. 如有可能, 请告知Johnston将军你何时能攻击敌军战线上的同一地点. 也请通知我, 我将尽力进行牵制. 我已送去一些雷管. 随信附上Johnston将军的一则快讯. “的加密结果

Enigma加密是一种机械密码机(外形像打字机, 见图 21.5), 每输入一个字母, 会根据(相当复杂的)密钥和机器的当前状态映射成另一个不同的字母. 机器的状态由几个以不同速度旋转的转子决定. 另一端的相同布线的机器可用于解密. 正如历史上的许多密码一样, 德国人也相信它是“不可能被破译的“, 甚至在战争后期, 尽管有越来越多的证据表明它已被破译, 他们仍拒绝相信这一事实. (事实上, 一些德国将军甚至在战后都拒绝相信它被破译了)破译Enigma是一项英勇的壮举, 由波兰人发起, 随后由英国人在Bletchley园完成, Alan Turing(就是图灵机的那个Turing)在其中扮演了关键角色. 作为这项工作的一部分, 英国人建造了可以说是世界上第一台大规模机械计算设备(尽管它们看起来更像洗衣机而不是iPhone). 在此过程中, 德国操作员的一些操作失误和错误也帮了忙. 例如, 他们的信息以“希特勒万岁“结尾这一事实被证明非常有用.

enigmafig

图 21.5. 在Enigma机械密码中, 密钥是转子和内部接线的设置. 当操作员键入信息时, 加密版本会显示在上方的显示区, 同时密码机的内部状态会更新(因此, 两次输入同一个字母通常会产生两个不同的输出字母). 解密过程相同: 如果发送方和接收方使用相同的密钥, 那么键入密文就会在显示区出现明文.

这里有一个有趣的小故事: Enigma机永远不会将一个字母映射为它本身. 1941年3月, Bletchley园的密码分析家Mavis Batey收到了一封试图解密的长信息. 她随后注意到了一个奇特的性质——信息中完全没有出现字母“L“. ¹ 她意识到信息中没有“L“的概率太小了, 不可能是偶然发生的. 因此她推测, 原始信息一定只由L组成. 也就是说, 情况很可能是操作员(也许是为了测试机器)简单地反复按下字母“L“发送了一条信息. 这一观察帮助她解码了下一条信息, 这条信息揭示了意大利计划中的袭击, 并帮助英军在后来被称为“马塔潘角海战“的战斗中取得了决定性的胜利. Mavis还帮助破译了另一台Enigma机. 利用她提供的情报, 英国人成功地让德国人相信, 盟军的主要登陆地点是在加莱海峡, 而不是诺曼底.

用Eisenhower将军的话来说, 来自Bletchley园的情报具有“无价的价值“. 它们对盟军的战争努力产生了巨大影响, 从而缩短了第二次世界大战, 挽救了数百万人的生命. 另见对Harry Hinsley爵士的采访.

定义加密

历史上(直至今日! )加密系统设计者面临的许多问题, 都可归因于最初未能正确定义或理解他们想要实现的目标. 让我们聚焦于私钥加密(private key encryption)的场景.(这也被称为“对称加密“(symmetric encryption) 数千年来, “私钥加密“一直是加密的同义词, 直到20世纪70年代公钥加密(public key encryption)的概念才被发明出来, 见定义 21.5)发送方(传统上称为“Alice”)想要向接收方(传统上称为“Bob“)发送一条消息(也称为明文, plaintext) $x \in {0, 1}^{*} .$ 他们希望消息对窃听或“窃听“通信信道(传统上称为“Eve“)的敌手保密.

Alice和Bob共享一个密钥(secret key) $k \in {0, 1}^{*} .$ (虽然本书其他地方常用字母 $k$ 表示自然数, 但在本章中, 我们用其表示对应于密钥的字符串)Alice使用密钥 $k$ 将明文 $x$ “打乱“或加密成密文 $y,$ Bob使用密钥 $k$ 将密文 $y$ “恢复“或解密回明文 $x .$ 这促使我们给出以下定义, 该定义试图描述无论加密方案是否安全, 它要有效或“有意义“所需满足的条件:

定义 21.1 (有效加密方案).

令 $L : N \to N$ 和 $C : N \to N$ 为两个从自然数映射到自然数的函数. 一对将字符串映射到字符串的多项式时间可计算函数 $(E, D),$ 如果对于每个 $n \in N,$ $k \in {0, 1}^{n}$ 和 $x \in {0, 1}^{L (n)},$ 都有 $∣ E_{k} (x) ∣ = C (n)$ 且 $D (k, E (k, x)) = x . (21.1)$ 则称其为具有明文长度函数 $L (\cdot)$ 和密文长度函数 $C (\cdot)$ 的有效私钥加密方案(valid private key scheme, 简称加密方案encryption scheme).

我们经常将加密和解密的第一个输入(即密钥)写作下标, 因此(21.1)也可写为 $D_{k} (E_{k} (x)) = x .$

validencryption

图 21.6. 私钥加密方案是一对算法 $E, D,$ 使得对于每个密钥 $k \in {0, 1}^{n}$ 和明文 $x \in {0, 1}^{L (n)},$ $y = E_{k} (x)$ 是长度为 $C (n)$ 的密文. 如果对于每个这样的 $y,$ 都有 $D_{k} (y) = x,$ 则该加密方案是有效的. 也就是说, 只要加密和解密使用相同的密钥, 对 $x$ 加密后再解密的结果就是 $x .$

Question

练习 21.1 (密文与明文的长度).

证明: 对于任何具有函数 $L, C$ 的有效加密方案 $(E, D),$ 对于每个 $n,$ 都有 $C (n) \geq L (n) .$

对练习 21.1的解答

对于每个固定的密钥 $k \in {0, 1}^{n},$ 方程(21.1)表明映射 $y \mapsto D_{k} (y)$ 是映射 $x \mapsto E_{k} (x)$ 的逆映射, 这尤其意味着映射 $x \mapsto E_{k} (x)$ 必须是单射. 因此, 其陪域必须至少与其定义域一样大, 由于其定义域是 ${0, 1}^{L (n)},$ 陪域是 ${0, 1}^{C (n)},$ 因此可得 $C (n) \geq L (n) .$

由于密文长度始终至少等于明文长度(并且在大多数应用中, 它不会比明文长度长很多), 我们通常将明文长度作为加密方案中需要优化的量. $L (n)$ 越大, 方案就越好, 因为这意味着保护相同长度的消息所需的密钥更短.

定义加密的安全性

定义 21.1完全没有提及 $E$ 和 $D$ 的安全性, 甚至允许那种完全忽略密钥, 对所有 $x$ 都设 $E_{k} (x) = x$ 的平凡加密方案存在. 定义安全性并非易事.

暂停一下

如果你在此处暂停阅读五分钟, 试着(或许与同伴一起)集思广益, 思考如何用数学语言定义加密方案是安全的, 即它能保护明文 $x$ 的保密性, 你将更能体会到定义加密安全性的精妙之处.

纵观历史, 许多对密码系统的攻击, 其根源都在于密码系统设计者依赖“隐匿安全性“——相信他们的方法不为敌人所知就能保护其不被破解. 这是一个错误的假设——如果你反复使用同一种方法(即使每次都更换密钥), 你的对手最终会弄清楚你在做什么. 而且, 如果Alice和Bob频繁地在安全地点会面以决定新方法, 他们还不如直接利用这个机会交换秘密. 这些考量促使Auguste Kerckhoffs于1883年提出了以下原则:

Quote

*一个密码系统, 即使除密钥之外的整个系统的所有信息都是公开的, 也应该是安全的. *²

为什么假设密钥是保密的而算法可以公开是可行的? 因为我们总能选择一个新的密钥. 当然, 如果我们的密钥是“1234“或“password! “, 那也于事无补. 事实上, 如果你使用任何确定性的算法来选择密钥, 你的对手最终也能搞清楚这一点. 因此, 为了安全, 我们必须随机地选择密钥, 并且可以将Kerckhoffs原则重申如下:

Quote

没有随机性, 就没有保密性

这一点至关重要, 值得重申:

重要启示

重要提示 21.1.

没有随机性, 就没有保密性.

每个密码方案的核心都有一个密钥, 而这个密钥总是随机选择的. 其必然结论是, 要理解密码学, 你需要懂概率论.

Info

备注 21.1 (现实世界中的随机性).

为密码学选择密钥需要生成随机性, 这通常通过测量一些“不可预测“或“高熵“的数据, 然后对其应用哈希函数以“提取“出均匀随机的字符串来完成. 此过程必须极其谨慎, 随机数生成器往往成为安全系统的“阿喀琉斯之踵“.

2006年, 一位程序员从Debian分发的OpenSSL软件包中的熵生成过程中删除了几行代码, 因为它们在某个自动验证代码中引起了警告. 结果在长达两年的时间里(直到问题被发现), 该过程生成的所有随机数仅使用进程ID作为“不可预测“的来源. 这意味着在此期间用户进行的所有通信都相当容易被破解(而且, 如果某些实体记录了这些通信, 他们甚至可以事后追溯性地破解它们). 参见XKCD对此事件的趣谈.

2012年, 两个独立的研究团队扫描了网络上大量的RSA密钥, 发现其中约4%的密钥很容易被破解. 主要问题出在路由器, 联网打印机等设备上. 这些设备有时运行的是Linux的变体——一种桌面操作系统——但由于没有硬盘, 鼠标或键盘, 它们无法获得桌面机所拥有的许多熵源. 再加上一些老派的无知(指对密码学的无知)和软件缺陷, 导致大量密钥极易被破解, 详情见这篇博文和这个网页.

由于随机性对安全性至关重要, 破坏生成随机性的过程可能导致使用该随机性的系统完全崩溃. 事实上, Snowden泄露的文件, 结合Shumow和Ferguson的观察, 强烈暗示美国国家安全局在美国国家标准与技术研究院发布的一个伪随机数生成器中故意插入了后门. 幸运的是, 这个生成器没有被广泛采用, 但显然美国国家安全局确实向RSA安全公司支付了1000万美元, 以便后者将这个生成器设为它们产品的默认选项.

完美保密性

如果你思考一段时间的加密方案安全性, 你可能会提出以下定义安全性的原则: “如果一个加密方案无法从 $E_{k} (x)$ 中恢复出密钥 $k,$ 那么它就是安全的”. 然而, 稍加思考就会发现, 密钥并不是我们真正想要保护的东西. 毕竟, 加密的全部意义在于保护明文 $x$ 的机密性. 因此, 我们可以尝试这样定义: “如果一个加密方案无法从 $E_{k} (x)$ 中恢复出明文 $x,$ 那么它就是安全的”. 但这似乎也不明确. 假设一个加密方案泄露了明文 $x$ 的前 10 个比特. 它可能仍然无法完全恢复 $x,$ 但从直觉上看, 在实践中使用这样的加密方案似乎极其不明智. 事实上, 通常即使是明文的部分信息也足以让对手实现其目标.

上述思考促使香农在1945年形式化了完美保密性的概念, 即加密不会泄露关于消息的任何信息. 有几种等价的方式来定义它, 但或许最简洁的定义如下:

定义 21.2 (完美保密性).

一个有效的加密方案 $(E, D),$ 其明文长度为 $L (\cdot),$ 如果对于每个 $n \in N$ 以及每个长度为 $L (n)$ 的明文 $x, x^{'} \in {0, 1}^{L (n)},$ 以下两个在 ${0, 1}^{*}$ 上的分布 $Y$ 和 $Y^{'}$ 是完全相同的, 则该方案具有完美保密性:

* $Y$ 是通过采样 $k \sim {0, 1}^{n}$ 并输出 $E_{k} (x)$ 得到的分布. * $Y^{'}$ 是通过采样 $k \sim {0, 1}^{n}$ 并输出 $E_{k} (x^{'})$ 得到的分布.

暂停一下

这个定义可能需要阅读多次才能理解. 试着思考这个条件如何对应于你对从观察 $E_{k} (x)$ 中“不获取关于 $x$ 的任何信息“这一直观概念, 以及如何对应本章开头香农的引述.

特别地, 假设你事先知道Alice发送的是 $x$ 的加密或者是 $x^{'}$ 的加密. 观察Alice实际发送的消息的加密结果, 你是否会从中了解到任何新信息? 查看图 21.7可能会对你有所帮助.

perfectsecfig

图 21.7. 对于任意密钥长度 $n,$ 我们可以将加密方案 $(E, D)$ 可视化为一个图, 其中包含 $2^{L (n)}$ 个可能的明文顶点, 以及所有形如 $E_{k} (x)$ (其中 $k \in {0, 1}^{n},$ $x \in {0, 1}^{L (n)})$ 的密文顶点. 对于每个明文 $x$ 和密钥 $k,$ 我们在 $x$ 和 $E_{k} (x)$ 之间添加一条标记为 $k$ 的边. 根据有效性的条件, 如果我们选取任意固定的密钥 $k,$ 那么映射 $x \mapsto E_{k} (x)$ 必须是单射. 完美保密性的条件简单地说就是要求任意两个明文 $x$ 和 $x^{'}$ 拥有完全相同的邻居集合(如果存在平行边, 则是多重集).

示例: 战场上的完美保密性

为了理解定义 21.2, 假设Alice只发送两条可能消息中的一条: “进攻“或“撤退”, 我们分别用 $x_{0}$ 和 $x_{1}$ 表示, 并且她发送每条消息的概率都是 $1/2.$ 让我们设身处地地想象我们是窃听者 Eve. 先验地, 我们会猜测Alice发送 $x_{0}$ 或 $x_{1}$ 的概率各为 $1/2.$ 现在我们观察到 $y = E_{k} (x_{i}),$ 其中 $k$ 是从 ${0, 1}^{n}$ 中均匀选择的密钥. 这个新信息如何改变我们对Alice发送的是明文 $x_{0}$ 还是明文 $x_{1}$ 的信念?

暂停一下

在阅读下一段之前, 你可能想自己尝试分析一下. 查看关于贝叶斯推断的Wikipedia条目或这些MIT讲义可能会有所帮助.

让我们定义 $p_{0} (y)$ 为(在 $k \sim {0, 1}^{n}$ 上) $y = E_{k} (x_{0})$ 的概率, 类似地, $p_{1} (y)$ 为 $Pr_{k \sim {0, 1}^{n}} [y = E_{k} (x_{1})] .$ 注意, 由于Alice随机选择要发送的消息, 我们观察到 $y$ 的先验概率是 $\frac{1}{2} p_{0} (y) + \frac{1}{2} p_{1} (y) .$ 然而, 根据定义 21.2, 完美保密性条件保证 $p_{0} (y) = p_{1} (y)$ ! 我们将 $p_{0} (y) = p_{1} (y)$ 这个值记为 $p .$ 根据条件概率公式, 在我们观察到 $y$ 的条件下, Alice发送了消息 $x_{0}$ 的概率就是 $Pr [i = 0∣ y = E_{k} (x_{i})] = \frac{Pr [ i = 0 \land y = E _{k} ( x _{i} )]}{Pr [ y = E _{k} ( x )]} (21.2)$

(方程(21.2)是贝叶斯规则的一个特例, 虽然它只是条件概率公式的简单重述, 但在统计学和数据分析中是一个极其重要且广泛使用的工具)

因为 $i = 0$ 且 $y$ 是密文 $E_{k} (0)$ 的概率等于 $\frac{1}{2} \cdot p_{0} (y),$ 而观察到 $y$ 的先验概率是 $\frac{1}{2} p_{0} (y) + \frac{1}{2} p_{1} (y),$ 我们可以将(21.2)重写为 $Pr [i = 0∣ y = E_{k} (x_{i})] = \frac{\frac{1}{2} p _{0} ( y )}{\frac{1}{2} p _{0} ( y ) + \frac{1}{2} p _{1} ( y )} = \frac{p}{p + p} = \frac{1}{2}$ 这里用到了 $p_{0} (y) = p_{1} (y) = p$ 这一事实. 这意味着观察到密文 $y$ 对我们没有任何帮助! 我们仍然无法以优于 50/50 的几率猜测Alice发送的是“进攻“还是“撤退“!

这个例子可以广泛推广, 以表明完美保密性确实是“完美的“, 因为观察密文不会给Eve带来任何关于明文的额外信息, 除了她先验已知的信息之外.

构建完美保密的加密方案

完美保密性是一个非常强的条件, 它意味着窃听者从观察密文中不会学到任何信息. 你可能认为满足如此强条件的加密方案是不可能实现的, 或者至少实现起来极其复杂. 但事实证明, 我们可以相当容易地获得一个完美保密的加密方案. 图 21.8展示了一个针对两比特消息的此类方案.

onetimepadtwofig

图 21.8. 一个针对两比特密钥和两比特明文的完美保密加密方案. 蓝色顶点代表明文, 红色顶点代表密文, 每条将明文 $x$ 映射到密文 $y = E_{k} (x)$ 的边都标有相应的密钥 $k .$ 因为有四种可能的密钥, 所以该图的度为4, 实际上它是一个完全二分图. 该加密方案是有效的, 因为对于每个 $k \in {0, 1}^{2},$ 映射 $x \mapsto E_{k} (x)$ 都是单射, 换句话说, 标有 $k$ 的边集构成一个完美匹配.

事实上, 这可以推广到任意数量的比特:

定理 21.1 (一次性密码本(Vernam 1917, Shannon 1949)).

存在一个完美保密的有效加密方案 $(E, D),$ 其满足 $L (n) = C (n) = n .$

定理 21.1的证明思路

我们的方案是一次性密码本, 也称为“Vernam密码“, 见图 21.8. 加密过程非常简单: 要使用密钥 $k \in {0, 1}^{n}$ 加密消息 $x \in {0, 1}^{n},$ 我们只需输出 $x \oplus k,$ 其中 $\oplus$ 是按位异或运算, 输出的是将 $x$ 和 $k$ 的每个坐标进行异或后得到的字符串.

定理 21.1的证明

对于两个长度相同为 $n$ 的二进制串 $a$ 和 $b,$ 我们定义 $a \oplus b$ 为串 $c \in {0, 1}^{n},$ 使得对于每个 $i \in [n],$ 有 $c_{i} = a_{i} + b_{i} mod 2.$ 加密方案 $(E, D)$ 定义如下: $E_{k} (x) = x \oplus k$ 且 $D_{k} (y) = y \oplus k .$ 根据加法结合律(模二也成立), $D_{k} (E_{k} (x)) = (x \oplus k) \oplus k = x \oplus (k \oplus k) = x \oplus 0^{n} = x,$ 这里用到了对于每个比特 $σ \in {0, 1},$ 有 $σ + σ mod 2 = 0$ 且 $σ + 0 = σ mod 2.$ 因此 $(E, D)$ 构成了一个有效的加密方案.

为了分析完美保密性, 我们断言对于每个 $x \in {0, 1}^{n},$ 分布 $Y_{x} = E_{k} (x)$ (其中 $k \sim {0, 1}^{n})$ 就是 ${0, 1}^{n}$ 上的均匀分布, 因此特别地, 对于每个 $x, x^{'} \in {0, 1}^{n},$ 分布 $Y_{x}$ 和 $Y_{x^{'}}$ 是相同的. 实际上, 对于每个特定的 $y \in {0, 1}^{n},$ 值 $y$ 被 $Y_{x}$ 输出当且仅当 $y = x \oplus k,$ 这成立当且仅当 $k = x \oplus y .$ 由于 $k$ 是从 ${0, 1}^{n}$ 中均匀随机选取的, $k$ 恰好等于 $x \oplus y$ 的概率正好是 $2^{- n},$ 这意味着每个串 $y$ 被 $Y_{x}$ 输出的概率都是 $2^{- n} .$

onetimepadfig

图 21.9. 在一次性密码本加密方案中, 我们使用密钥 $k \in {0, 1}^{n}$ 将明文 $x \in {0, 1}^{n}$ 加密为密文 $x \oplus k,$ 其中 $\oplus$ 表示按位异或运算.

暂停一下

上述论证相当简单, 但值得再读一遍. 为了理解为什么一次性密码本是完美保密的, 将其设想为我们在图 21.8中所做的二分图是很有帮助的. (实际上, 图21.8中的加密方案正是 $n = 2$ 时的一次性密码本)对于每个 $n,$ 一次性密码本加密方案对应于一个二分图, 其“左侧“有 $2^{n}$ 个顶点, 对应于 ${0, 1}^{n}$ 中的明文; “右侧“有 $2^{n}$ 个顶点, 对应于密文 ${0, 1}^{n} .$ 对于每个 $x \in {0, 1}^{n}$ 和 $k \in {0, 1}^{n},$ 我们将 $x$ 与顶点 $y = E_{k} (x)$ 用一条标记为 $k$ 的边连接起来. 可以看出, 这是一个完全二分图, 其中左侧的每个顶点都连接到所有右侧的顶点. 这尤其意味着, 对于每个左侧顶点 $x,$ 通过随机选取 $k \in {0, 1}^{n}$ 并沿着标记为 $k$ 的边走到 $x$ 的邻居而得到的密文分布, 正是 ${0, 1}^{n}$ 上的均匀分布. 这确保了完美保密性条件.

长密钥的必要性

那么, 定理 21.1是否给出了密码学的最终定论, 并意味着我们都可以进行完美保密的通信, 并从此过上幸福的生活呢? 并非如此. 虽然一次性密码本是高效的, 并且提供了完美保密性, 但它有一个明显的缺点: 要通信n比特, 你需要存储一个长度为n的密钥. 相比之下, 实际使用的密码系统, 如 AES-128, 只有 128 比特(即 16 字节)的短密钥, 却可以用于保护TB级甚至更多的通信! 想象一下, 如果我们都必须使用一次性密码本. 如果是这样, 那么如果你需要与m个人通信, 你就必须(安全地! )维护m个巨大的文件, 每个文件都与你预期与该人通信的最大总长度相当. 想象一下, 每次你在亚马逊, 谷歌或任何其他服务开设账户时, 他们都需要通过邮件(理想情况下是用安全的信使)给你寄一张装满随机数的 DVD, 而每次你怀疑有病毒时, 你都需要向所有这些服务索要一张新的 DVD. 这听起来可不太吸引人.

这不仅仅是一个理论问题. 苏联从 1940 年代之前就开始使用一次性密码本进行机密通信. 事实上, 甚至在香农的工作之前, 美国情报部门在 1941 年就已经知道一次性密码本在原则上是“不可破译的“(见Venona 文件第 32 页). 然而, 结果证明, 为所有通信制造如此多密钥的麻烦给苏联带来了负面影响, 他们最终为了发送多于一条的消息而重复使用了相同的密钥. 他们确实试图将相同的密钥用于完全不同的接收者, 错误地希望这样不会被发现. 美国陆军的Venona 项目由Gene Grabeel(见图 21.10, 一位来自弗吉尼亚州麦迪逊高地的前家政学教师)和Leonard Zubko中尉于 1943 年 2 月创立. 1943 年 10 月, 当他们发现俄罗斯人正在重复使用其密钥时, 该项目取得了突破. 在其存在的 37 年里, 该项目产生了一笔情报宝藏, 揭露了在美国和其他国家的数百名克格勃特工和俄罗斯间谍, 包括Julius Rosenberg, Harry Gold, Klaus Fuchs, Alger Hiss, Harry Dexter White等等.

genegrabeelfig

图 21.10. Gene Grabeel, 她于 1943 年 2 月 1 日创立了美国俄罗斯SigInt项目. 照片摄于 1942 年, 见Venona 历史研究第 7 页.

longkeygraphfig

图 21.11. 一个密钥数量少于明文数量的加密方案对应于一个二分图, 其中左侧的度数小于顶点数. 结合有效性条件, 这意味着将存在两个左侧顶点 $x, x^{'}$ 具有不完全相同的邻域, 因此该方案并不满足完美保密性.

不幸的是, 事实证明, 如此长的密钥对于完美保密性来说是必需的:

定理 21.2 (完美保密性需要长密钥).

对于每一个完美保密性的加密方案 $(E, D),$ 长度函数 $L$ 满足 $L (n) \leq n .$

定理 21.2的证明思路

证明背后的思想如图 21.11所示. 我们在明文和密文之间定义一个图, 如果存在某个密钥 $k$ 使得 $y = E_{k} (x),$ 则在明文 $x$ 和密文 $y$ 之间连一条边. 这个图的度数最多等于潜在密钥的数量. 度数小于明文数量(因此也小于密文数量)这一事实意味着将存在两个具有不同邻居集合的明文 $x$ 和 $x^{'},$ 因此对应于 $x$ 的密文分布(使用随机密钥)将与对应于 $x^{'}$ 的密文分布不相同.

定理 21.2的证明

设 $E, D$ 是一个有效的加密方案, 其消息长度为 $L,$ 密钥长度为 $n < L .$ 我们将通过提供两个明文 $x_{0}, x_{1} \in {0, 1}^{L}$ 来证明 $(E, D)$ 不是完美保密的, 使得分布 $Y_{x_{0}}$ 和 $Y_{x_{1}}$ 不相同, 其中 $Y_{x}$ 是通过选取 $k \sim {0, 1}^{n}$ 并输出 $E_{k} (x)$ 得到的分布.

我们选择 $x_{0} = 0^{L} .$ 设 $S_{0} \subseteq {0, 1}^{*}$ 是在 $Y_{x_{0}}$ 中输出概率非零的所有密文的集合. 即 $S_{0} = {y ∣ \exists_{k \in {0, 1}^{n}} y = E_{k} (x_{0})} .$ 因为只有 $2^{n}$ 个密钥, 我们知道 $∣ S_{0} ∣ \leq 2^{n} .$

我们将证明以下断言:

断言1: 存在某个 $x_{1} \in {0, 1}^{L}$ 和 $k \in {0, 1}^{n}$ 使得 $E_{k} (x_{1}) \neq \in S_{0} .$

断言1意味着字符串 $E_{k} (x_{1})$ 被 $Y_{x_{1}}$ 输出的概率为正, 而被 $Y_{x_{0}}$ 输出的概率为零, 因此特别地, $Y_{x_{0}}$ 和 $Y_{x_{1}}$ 不相同. 为了证明断言1, 只需选择一个固定的 $k \in {0, 1}^{n} .$ 根据有效性条件, 映射 $x \mapsto E_{k} (x)$ 是从 ${0, 1}^{L}$ 到 ${0, 1}^{*}$ 的一一映射, 因此特别地, 此映射的像, 即集合 $I_{k} = {y ∣ \exists_{x \in {0, 1}^{L}} y = E_{k} (x)}$ 的大小至少为(实际上恰好为) $2^{L} .$ 由于 $∣ S_{0} ∣ \leq 2^{n} < 2^{L},$ 这意味着 $∣ I_{k} ∣ > ∣ S_{0} ∣,$ 因此特别地, 存在某个字符串 $y$ 属于 $I_{k} ∖ S_{0} .$ 但根据 $I_{k}$ 的定义, 这意味着存在某个 $x \in {0, 1}^{L}$ 使得 $E_{k} (x) \neq \in S_{0},$ 这就完成了断言1的证明, 从而也完成了定理 21.2的证明.

计算保密性

总结前文, 我们现在知道:

可以获得密钥长度与明文相同的完美保密性加密方案.
不可能获得密钥比明文短(甚至是只短一个比特)的此类方案.

这与我们已知的事实如何协调? 即人们通常使用的密码系统, 其密钥仅为 16 字节(即 128 位), 却可以加密数TB的明文. 定理 21.2的证明确实给出了一种破解所有这些密码系统的方法, 但对该证明的检验表明, 它仅能得出一个时间开销为密钥长度指数级的算法. 这促使我们将完美保密性条件放宽为一种称为计算保密性(computational secrecy)的条件. 直观地讲, 如果一个加密方案没有多项式时间算法能够攻破它, 那么它在计算上是保密的. 其正式定义如下:

定义 21.3 (计算保密性).

设 $(E, D)$ 是一个有效的加密方案, 其中对于长度为 $n$ 的密钥, 明文长度为 $L (n),$ 密文长度为 $m (n) .$ 如果对于每个多项式 $p : N \to N$ 和足够大的 $n,$ 若 $P$ 是一个至多包含 $p (n)$ 行代码, 具有 $m (n)$ 个输入和单个输出的NAND-CIRC程序, 并且 $x_{0}, x_{1} \in {0, 1}^{L (n)},$ 那么 $E_{k \sim {0, 1}^{n}} [P (E_{k} (x_{0}))] - E_{k \sim {0, 1}^{n}} [P (E_{k} (x_{1}))] < \frac{1}{p ( n )} (21.3)$

暂停一下

要真正理解定义 21.3, 需要读两到三遍并进行一些练习. 一个检验你是否理解了的极好练习是, 看看如果我们允许 $P$ 是任意函数, 将 ${0, 1}^{m (n)}$ 映射到 ${0, 1},$ 并且将(21.3)中的条件(左边小于 $\frac{1}{p ( n )})$ 替换为左边等于 $0,$ 那么我们就得到了定义 21.2中的完美保密性条件. 事实上, 如果分布 $E_{k} (x_{0})$ 和 $E_{k} (x_{1})$ 完全相同, 那么对它们应用任何函数 $P$ 都会得到相同的期望值. 另一方面, 如果上述两个分布对某个元素 $y^{*} \in {0, 1}^{m (n)}$ 给出的概率不同, 那么函数 $P (y)$ (当且仅当 $y = y^{*}$ 时输出 $1)$ 在前一个分布下的期望值与在后一个分布下的期望值将不同.

定义 21.3提出了两个自然的问题:

它是否足够强, 足以确保一个计算保密性的加密方案能够保护其所加密消息的保密性?
它是否足够弱, 以至于与完美保密性不同, 可以获得一个密钥远小于消息的计算保密性加密方案?

据我们所知, 这两个问题的答案都是“是“. 这只是一个更广泛现象中的一个例子. 我们可以利用计算难度来实现许多密码学目标, 包括一些人类梦想了数千年的目标, 以及其他一些人们甚至不敢想象的目标.

重要启示

重要提示 21.2.

计算难度(computational hardness)对于几乎所有密码学应用来说都是既必要又充分的.

关于第一个问题, 不难证明, 例如, 如果Alice使用一个计算保密的加密算法来加密“攻击“或“撤退“(每个选择的概率为 $1/2),$ 那么只要她仅限于使用多项式时间算法, 即使观察到了其加密形式, 敌手Eve猜中消息的概率也不可能高于, 比如说0.51. (我们省略了证明, 但这对你来说是一个极好的练习, 可以自己尝试解答)

为了回答第二个问题, 我们将证明, 在与我们用于去随机化 $BPP$ 相同的假设下, 我们可以获得一个计算保密的密码系统, 其中密钥几乎比明文指数级地小.

流加密或“去随机化的一次性密码本“

结果表明, 如果存在如最优PRG猜想所述的伪随机生成器, 那么存在一种计算上安全的加密方案, 其密钥比明文短得多. 下面的构造被称为流加密(stream cipher), 尽管或许更好的名称是“去随机化的一次性密码本“. 它在实践中被广泛使用, 密钥长度仅为几十或几百比特, 却能保护数TB甚至PB的通信.

derandonetimepadfig

图 21.12. 在流加密或“去随机化的一次性密码本“中, 我们使用一个伪随机生成器 $G : {0, 1}^{n} \to {0, 1}^{L}$ 来获得一个密钥长度为 $n,$ 明文长度为 $L$ 的加密方案. 我们使用密钥 $k \in {0, 1}^{n}$ 将明文 $x \in {0, 1}^{L}$ 加密为密文 $x \oplus G (k) .$

我们首先回顾定义20.9中给出的伪随机生成器(pseudorandom generator)的概念. 在本章中, 我们将采用该定义的一个特例:

定义 21.4 (密码学伪随机生成器).

设 $L : N \to N$ 为某个函数. 一个拉伸度为 $L (\cdot)$ 的密码学伪随机生成器(cryptographic pseudorandom generator)是一个多项式时间可计算的函数 $G : {0, 1}^{*} \to {0, 1}^{*},$ 使得:

对于每个 $n \in N$ 和 $s \in {0, 1}^{n},$ 有 $∣ G (s) ∣ = L (n) .$
对于每个多项式 $p : N \to N$ 以及足够大的 $n,$ 如果 $C$ 是一个具有 $L (n)$ 个输入, 一个输出且至多 $p (n)$ 个门的电路, 那么 $s \sim {0, 1}^{ℓ} Pr [C (G (s)) = 1] - r \sim {0, 1}^{m} Pr [C (r) = 1] < \frac{1}{p ( n )}$

在本章中, 我们将密码学伪随机生成器简称为伪随机生成器或 PRG. 第 20.4.2 节的最优PRG猜想意味着存在一个伪随机生成器, 它可以“欺骗“指数级大小的电路, 并且概率差异至多为指数级小量. 由于指数级增长速度超过任何多项式, 最优PRG猜想蕴含以下结论:

密码学PRG猜想: 对于每个 $a \in N,$ 存在一个拉伸度为 $L (n) = n^{a}$ 的密码学伪随机生成器.

密码学PRG猜想比最优PRG猜想弱, 但(正如我们将看到的)它仍然比 $P \neq = NP$ 猜想更强.

定理 21.3 (去随机化的一次性密码本).

假设密码学PRG猜想成立. 那么对于每个常数 $a \in N,$ 存在一个计算上秘密的加密方案 $(E, D),$ 其明文长度 $L (n)$ 至少为 $n^{a} .$

定理 21.3的证明思路

证明过程如图 21.12所示. 我们简单地采用针对 $L$ 比特明文的一次性密码本, 但将密钥替换为 $G (k),$ 其中 $k$ 是 ${0, 1}^{n}$ 中的字符串, 且 $G : {0, 1}^{n} \to {0, 1}^{L}$ 是一个伪随机生成器. 由于一次性密码本是不可破译的, 任何能攻破去随机化一次性密码本的敌手都可以被用来区分伪随机生成器的输出和均匀分布.

定理 21.3的证明

设 $G : {0, 1}^{n} \to {0, 1}^{L}$ (其中 $L = n^{a})$ 是密码学PRG猜想保证存在的伪随机生成器 $G$ 在输入长度 $n$ 上的限制. 我们现在如下定义加密方案: 给定密钥 $k \in {0, 1}^{n}$ 和明文 $x \in {0, 1}^{L},$ 加密 $E_{k} (x)$ 就是 $x \oplus G (k) .$ 要解密密文 $y \in {0, 1}^{m},$ 我们输出 $y \oplus G (k) .$ 这是一个有效的加密方案, 因为 $G$ 可以在多项式时间内计算, 并且对于每个 $x \in {0, 1}^{L},$ 有 $(x \oplus G (k)) \oplus G (k) = x \oplus (G (k) \oplus G (k)) = x .$

计算上的保密性来自于伪随机生成器的条件. 为了得到矛盾, 假设存在一个多项式 $p,$ 一个至多包含 $p (L)$ 行代码的NAND-CIRC程序 $Q,$ 以及 $x, x^{'} \in {0, 1}^{L (n)},$ 使得 $E_{k \sim {0, 1}^{n}} [Q (E_{k} (x))] - E_{k \sim {0, 1}^{n}} [Q (E_{k} (x^{'}))] > \frac{1}{p ( L )}$ (这里我们使用了一个简单事实: 对于一个取值为 ${0, 1}$ 的随机变量 $X,$ 有 $Pr [X = 1] = E [X])$

根据我们加密方案的定义, 这意味着 $E_{k \sim {0, 1}^{n}} [Q (G (k) \oplus x)] - E_{k \sim {0, 1}^{n}} [Q (G (k) \oplus x^{'})] > \frac{1}{p ( L )} (21.4)$

现在, 由于(正如我们在一次性密码本的安全性分析中看到的)对于每个字符串 $x, x^{'} \in {0, 1}^{L},$ 分布 $r \oplus x$ 和 $r \oplus x^{'}$ 是相同的, 其中 $r \sim {0, 1}^{L} .$ 因此 $E_{r \sim {0, 1}^{L}} [Q (r \oplus x)] = E_{r \sim {0, 1}^{L}} [Q (r \oplus x^{'})] (21.5)$ 将(21.5)代入(21.4), 我们可以推导出 $∣ E_{k \sim {0, 1}^{n}} [Q (G (k) \oplus x)] - E_{r \sim {0, 1}^{L}} [Q (r \oplus x)] + E_{r \sim {0, 1}^{L}} [Q (r \oplus x^{'})] - E_{k \sim {0, 1}^{n}} [Q (G (k) \oplus x^{'})] ∣ > \frac{1}{p ( L )} (21.6)$ (请确保你能理解为什么这是正确的)

现在我们可以使用三角不等式 $∣ A + B ∣ \leq ∣ A ∣ + ∣ B ∣$ (对于任意两个数 $A, B),$ 将其应用于 $A = E_{k \sim {0, 1}^{n}} [Q (G (k) \oplus x)] - E_{r \sim {0, 1}^{L}} [Q (r \oplus x)]$ 和 $B = E_{r \sim {0, 1}^{L}} [Q (r \oplus x^{'})] - E_{k \sim {0, 1}^{n}} [Q (G (k) \oplus x^{'})],$ 得到 $E_{k \sim {0, 1}^{n}} [Q (G (k) \oplus x)] - E_{r \sim {0, 1}^{L}} [Q (r \oplus x)] + E_{r \sim {0, 1}^{L}} [Q (r \oplus x^{'})] - E_{k \sim {0, 1}^{n}} [Q (G (k) \oplus x^{'})] > \frac{1}{p ( L )} (21.7)$

特别地, (21.7)左侧的第一项或第二项必须至少为 $\frac{1}{2 p ( L )} .$ 假设第一项成立(第二种情况以完全相同的方式分析). 那么我们得到 $E_{k \sim {0, 1}^{n}} [Q (G (k) \oplus x)] - E_{r \sim {0, 1}^{L}} [Q (r \oplus x)] > \frac{1}{2 p ( L )} (21.8)$

但如果现在定义NAND-CIRC程序 $P_{x},$ 它在输入 $r \in {0, 1}^{L}$ 时输出 $Q (r \oplus x),$ 那么(因为 $L$ 比特的异或可以在 $O (L)$ 行内计算), 我们得到 $P_{x}$ 有 $p (L) + O (L)$ 行, 并且根据(21.8), 它能以优于 $\frac{1}{2 p ( L )}$ 的优势区分形式为 $G (k)$ 的输入和形式为 $r \sim {0, 1}^{k}$ 的输入. 由于多项式受指数级支配, 如果我们使 $L$ 足够大, 这将与伪随机生成器 $G$ 的 $(2^{δ n}, 2^{- δ n})$ 安全性相矛盾.

Info

备注 21.2 (实践中的流加密).

实践中两种最广泛使用的(私钥)加密方案是流加密和分组加密. (更令人困惑的是, 分组加密总是在某种操作模式下使用, 而其中一些模式有效地将分组加密转换为流加密)分组加密可以被认为是某种从 ${0, 1}^{n}$ 到 ${0, 1}^{n}$ 的“随机可逆映射“, 并且可用于构造伪随机生成器, 进而构造流加密, 或使用其他操作模式直接加密数据. 除了计算上的保密性之外, 加密方案还有大量其他的安全概念和考虑因素. 其中许多涉及处理诸如选择明文, 中间人和选择密文攻击等场景, 在这些场景中, 敌手不仅仅是被动的窃听者, 而是可以某种方式影响通信. 虽然本章旨在让你初步了解密码学背后的思想, 但在正确应用它以获得安全应用之前, 还有更多东西需要了解, 并且已经有很多人在这方面犯过错误.

计算保密性与 $NP$

我们之前也提到过, 一个能解决 $NP$ 问题的有效算法可以用来破解所有的密码学. 现在我们给出一个例子来说明如何做到这一点:

定理 21.4 (使用 $NP$ 算法破解加密).

如果 $P = NP,$ 那么不存在任何明文长度 $L (n) > n$ 的计算保密的加密方案.

此外, 对于每一个有效的加密方案 $(E, D)$ 且满足 $L (n) > n + 100,$ 存在一个多项式 $p,$ 使得对于每一个足够大的 $n,$ 存在 $x_{0}, x_{1} \in {0, 1}^{L (n)}$ 和一个 $p (n)$ 行的NAND-CIRC程序 $EVE,$ 满足: $i \sim {0, 1}, k \sim {0, 1}^{n} Pr [EVE (E_{k} (x_{i})) = i] \geq 0.99 .$

请注意, “此外“这部分是非常强的. 它意味着如果明文甚至只比密钥长一点点, 那么我们就已经能够以一种非常强的方式破解该方案. 也就是说, 将会存在一对消息 $x_{0},$ $x_{1}$ (把 $x_{0}$ 想象为“卖出”, $x_{1}$ 想象为“买入“)和一个有效的策略给Eve, 使得如果Eve得到一个密文 $y,$ 她就能够以非常接近 $1$ 的概率判断出 $y$ 是 $x_{0}$ 还是 $x_{1}$ 的加密. (我们将破解方案建模为Eve输出 $0$ 或 $1,$ 对应于发送的消息是 $x_{0}$ 还是 $x_{1} .$ 注意, 我们也可以同样地将Eve修改为输出 $x_{0}$ 代替 $0,$ 输出 $x_{1}$ 代替 $1.$ 关键点在于, 先验地, Eve猜测Alice发送的是 $x_{0}$ 还是 $x_{1}$ 只有50/50的机会, 但在看到密文后, 这个概率增加到高于99/100)条件 $P = NP$ 可以放宽到 $NP \subseteq BPP,$ 甚至更弱的条件 $NP \subseteq P_{/poly},$ 其证明思路基本相同.

定理 21.4的证明思路

证明遵循定理 21.2的思路, 但这次关注计算方面. 如果 $P = NP,$ 那么对于每一个明文 $x$ 和密文 $y,$ 我们可以有效地判断是否存在 $k \in {0, 1}^{n}$ 使得 $E_{k} (x) = y .$ 所以, 为了证明这个结果, 我们需要证明如果明文足够长, 就会存在一对 $x_{0}, x_{1},$ 使得一个随机的 $x_{1}$ 的加密同时也是一个有效的 $x_{0}$ 的加密的概率非常小. 下面是如何证明这一点的细节.

定理 21.4的证明

我们只着重证明“此外“这部分, 因为它更有趣, 另一部分基本上可以通过相同的证明得到.

假设 $(E, D)$ 是这样的一个加密方案, 令 $n$ 足够大, 并令 $x_{0} = 0^{L (n)} .$ 对于每一个 $x \in {0, 1}^{L (n)},$ 我们定义 $S_{x}$ 为 $x$ 的所有有效加密的集合. 即 $S_{x} = {y ∣ \exists_{k \in {0, 1}^{n}} y = E_{k} (x)} .$ 如定理 21.2的证明, 因为有 $2^{n}$ 个密钥 $k,$ 所以对于每一个 $x \in {0, 1}^{L (n)},$ 都有 $∣ S_{x} ∣ \leq 2^{n} .$

我们用 $S_{0}$ 表示集合 $S_{x_{0}} .$ 我们定义我们的算法 $EVE,$ 对于输入 $y \in {0, 1}^{*},$ 如果 $y \in S_{0}$ 则输出 $0,$ 否则输出 $1.$ 如果 $P = NP,$ 这可以在多项式时间内实现, 因为密钥 $k$ 可以充当一个有效可验证解的角色. (你能明白为什么吗? )显然 $Pr [EVE (E_{k} (x_{0})) = 0] = 1,$ 所以在 $EVE$ 得到 $x_{0}$ 的加密的情况下, 她猜对的概率是 $1.$ 证明的其余部分致力于证明存在 $x_{1} \in {0, 1}^{L (n)}$ 使得 $Pr [EVE (E_{k} (x_{1})) = 0] \leq 0.01,$ 这将通过表明 $EVE$ 猜错的概率最多为 $\frac{1}{2} 0 + \frac{1}{2} 0.01 < 0.01$ 来结束证明.

现在考虑下面的概率实验(我们仅为了分析而定义它). 我们考虑均匀选择 $x$ 在 ${0, 1}^{L (n)}$ 中的样本空间, 并定义随机变量 $Z_{k} (x)$ 等于 $1$ 当且仅当 $E_{k} (x) \in S_{0} .$ 对于每一个 $k,$ 映射 $x \mapsto E_{k} (x)$ 是单射, 这意味着 $Z_{k} = 1$ 的概率等于 $x \in E_{k}^{- 1} (S_{0})$ 的概率, 即 $\frac{∣ S _{0} ∣}{2 ^{L (n)}} .$ 所以由期望的线性性, $E [\sum_{k \in {0, 1}^{n}} Z_{k}] \leq \frac{2 ^{n} ∣ S _{0} ∣}{2 ^{L (n)}} \leq \frac{2 ^{2 n}}{2 ^{L (n)}} .$

我们现在将使用一个极其简单但有用的事实, 称为平均原理(另见引理18.10): 对于每一个随机变量 $Z,$ 如果 $E [Z] = μ,$ 那么以正概率有 $Z \leq μ .$ (确实, 如果 $Z > μ$ 的概率为1, 那么 $Z$ 的期望值必然大于 $μ,$ 就像你不可能在一个班级里所有学生都得了A或A-, 但总体平均成绩却是B+一样)在我们的情况中, 这意味着以正概率有 $\sum_{k \in {0, 1}^{n}} Z_{k} \leq \frac{2 ^{2 n}}{2 ^{L (n)}} .$ 换句话说, 存在某个 $x_{1} \in {0, 1}^{L (n)}$ 使得 $\sum_{k \in {0, 1}^{n}} Z_{k} (x_{1}) \leq \frac{2 ^{2 n}}{2 ^{L (n)}} .$ 然而这意味着, 如果我们选择一个随机的 $k \sim {0, 1}^{n},$ 那么 $E_{k} (x_{1}) \in S_{0}$ 的概率最多是 $\frac{1}{2 ^{n}} \cdot \frac{2 ^{2 n}}{2 ^{L (n)}} = 2^{n - L (n)} .$ 所以, 特别地, 如果我们有一个算法 $EVE,$ 当 $x \in S_{0}$ 时输出 $0,$ 否则输出 $1,$ 那么 $Pr [EVE (E_{k} (x_{0})) = 0] = 1$ 且 $Pr [EVE (E_{k} (x_{1})) = 0] \leq 2^{n - L (n)},$ 如果 $L (n) \geq n + 10,$ 这个值将小于 $2^{- 10} < 0.01.$

回顾起来, 定理 21.4也许并不令人惊讶. 毕竟, 正如我们之前提到的, 已知最优PRG猜想(它是去随机化一次性密码本加密的基础)如果 $P = NP$ (实际上即使是 $NP \subseteq BPP$ 或甚至 $NP \subseteq P_{/poly})$ 则是错误的.

公钥密码学

至少从Leonardo Da Vinci的时代(更不用说希腊神话中的伊卡洛斯了)起, 人们就一直梦想着制造出比空气重的飞行器. Jules Verne在1865年就以相当有洞察力的细节描写了去月球旅行. 但是, 据我所知, 在人们使用秘密书写的数千年里, 直到大约50年前, 还没有人考虑过在不预先交换共享密钥的情况下进行安全通信的可能性.

然而在20世纪60年代末和70年代初, 有几个人开始质疑这种“常识“. 这些远见者中最令人惊讶的也许是伯克利的一名本科生, 名叫Ralph Merkle. 1974年秋天, 梅克尔在他的计算机安全课程的项目提案中写道: “如果两个人从来没有机会预先约定一种加密方法, 那么他们将无法在不安全的信道上安全地通信, 这似乎是直观上显而易见的……但我认为这是错误的”. 这个项目提案被他的教授以“不够好“为由拒绝了. Merkle后来向《ACM通讯》提交了一篇论文, 在论文中他为缺乏参考文献而道歉, 因为他无法在科学文献中找到任何提及该问题的地方, 而他唯一看到该问题被提出的出处是一篇科幻小说. 这篇论文被拒绝了, 拒绝理由是: “经验表明, 以明文形式传输密钥信息是极其危险的. “ Merkle表明, 可以设计一种协议, 让Alice和Bob使用哈希函数的 $T$ 次调用来交换一个密钥, 但敌手(在随机谕言模型random oracle model中, 尽管他当时当然没有使用这个名字)需要大约 $T^{2}$ 次调用才能破解它. 他推测, 有可能获得这样的协议, 使得破解的难度指数级地高于使用它们的难度, 但他想不出任何具体的方法来实现这一点.

我们直到很久以后才发现, 在20世纪60年代末, 比Merkle早几年, 英国情报机构GCHQ的James Ellis也有类似的想法. 他的好奇心是由贝尔实验室一份二战时期的手稿激起的, 该手稿提出了两个人可以通过电话线安全通信的以下方式. Alice会向线路中注入噪声, Bob会中继他的消息, 然后Alice会减去噪声以得到信号. 其想法是, 线路上的敌手只看到Alice和Bob信号的总和, 不知道哪个信号来自谁. 这让James Ellis思考是否有可能以数字方式实现类似的东西. 正如Ellis后来回忆的那样, 在1970年, 他意识到原则上这应该是可能的, 因为他可以设想一个假设的黑匣子 $B,$ 当输入一个“句柄“ $α$ 和明文 $x$ 时, 它会给出一个“密文“ $y,$ 并且会有一个与 $α$ 对应的密钥 $β,$ 这样将 $β$ 和 $y$ 输入黑匣子就能恢复出 $x .$ 然而, Ellis不知道如何实际实例化这个黑匣子. 他和同事们一直把这个难题作为谜题交给聪明的新员工, 直到1973年, 其中一位新员工Clifford Cocks基于因数分解问题提出了一个候选解决方案; 1974年, 另一位GCHQ新员工Malcolm Williamson利用模幂运算提出了一个解决方案.

但在所有思考公钥密码学的人中, 看得最远的可能是Stanford大学的两位研究员, Whit Diffie和Martin Hellman. 他们意识到, 随着电子通信的出现, 密码学将在间谍和潜艇的军事领域之外找到新的应用, 他们理解在这个用户众多, 点对点通信的新世界里, 密码学将需要扩展规模. Diffie和Hellman设想了一种对象, 我们现在称之为“陷门(trapdoor)置换“, 尽管他们当时称之为“单向陷门函数“或者有时简称为“公钥加密“. 虽然他们没有完整的正式定义, 但他们的想法是, 这是一个容易(例如, 多项式时间内)计算但困难(例如, 指数时间内)求逆的单射函数. 然而, 存在某个特定的陷门, 知晓它就能在多项式时间内求逆. Diffie和Hellman认为, 使用这样的陷门函数, Alice和Bob有可能从未交换过密钥就安全地通信. 但他们并没有止步于此. 他们意识到, 保护通信的完整性(integrity)与保护其保密性(secrecy)同样重要. 因此, 他们设想Alice可以“反向运行加密“来认证或签名消息.

在那个时候, Diffie和Hellman的处境与那些预言某种粒子应该存在但没有任何实验验证的物理学家们颇为相似. 幸运的是, 他们遇到了Ralph Merkle, 他关于概率性密钥交换协议(probabilistic key exchange protocol)的想法, 连同他们的Stanford同事John Gill的一个建议, 启发他们提出了今天众所周知的Diffie-Hellman密钥交换(他们不知道的是, 这个协议两年前已被GCHQ的Malcolm Williamson发现). 他们于1976年发表了论文《密码学的新方向》, 这篇论文被认为催生了现代密码学.

Diffie-Hellman密钥交换至今仍广泛应用于安全通信. 然而, 它仍未实现Diffie和Hellman梦寐以求的陷门函数. 这一点在次年由Rivest, Shamir和Adleman完成, 他们提出了RSA陷门函数, 通过Diffie和Hellman的框架, 该函数不仅实现了加密, 还实现了签名. (RSA 函数的一个近似变体早些时候已被GCHQ的Clifford Cocks发现, 但据我所知, Cocks, Ellis和Williamson并未意识到其在数字签名方面的应用)从那时起, 密码学领域开始了一系列进展, 热潮延续至今.

diffiehellmanmerklegillfig

图 21.13. 左上: Ralph Merkle, Martin Hellman和Whit Diffie, 他们在1976年共同提出了公钥加密的概念和一个密钥交换协议. 左下: Adi Shamir, Ron Rivest和Leonard Adleman, 他们继Diffie和Hellman的论文之后, 发现了可用于公钥加密和数字签名的RSA函数. 有趣的是, 可以看到他们身后黑板上的方程 $P = NP .$ 右: John Gill, 他是第一个向Diffie和Hellman建议使用模幂运算作为易于计算但难以求逆函数的人.

定义公钥加密

公钥加密由三个算法组成:

密钥生成算法, 我们记作 $Key G e n$ 或简称 $K G,$ 是一个随机化算法, 输出一对字符串 $(e, d),$ 其中 $e$ 称为公钥(或加密密钥), $d$ 称为私钥(或解密密钥). 密钥生成算法的输入是 $1^{n}$ (即一个长度为 $n$ 的 1 组成的字符串). 我们将 $n$ 称为方案的安全参数. $n$ 越大, 加密越安全, 但效率也会越低.
加密算法, 我们记作 $E,$ 输入加密密钥 $e$ 和明文 $x,$ 输出密文 $y = E_{e} (x) .$
解密算法, 我们记作 $D,$ 输入解密密钥 $d$ 和密文 $y,$ 输出明文 $x = D_{d} (y) .$

publickeyencfig

图 21.14. 在公钥加密中, Alice生成一个私钥/公钥对 $(e, d),$ 公开 $e$ 并保密 $d .$ 要为Alice加密一条消息, 只需要知道 $e .$ 要解密密文, 则需要知道 $d .$

现在我们给出一个正式定义:

定义 21.5 (公钥加密).

一个具有明文长度 $L : N \to N$ 的计算上保密的公钥加密(computationally secret public key encryption)方案, 是一个由三个随机化多项式时间算法 $(K G, E, D)$ 组成的三元组, 满足以下条件:

对于每个 $n,$ 如果 $(e, d)$ 是以正概率由 $K G (1^{n})$ 输出的, 且 $x \in {0, 1}^{L (n)},$ 那么 $D_{d} (E_{e} (x)) = x$ 的概率为 1.
对于每个多项式 $p$ 和所有足够大的 $n,$ 如果 $P$ 是一个最多有 $p (n)$ 行代码的NAND-CIRC程序, 那么对于每个 $x, x^{'} \in {0, 1}^{L (n)},$ 有 $∣ E [P (e, E_{e} (x))] - E [P (e, E_{e} (x^{'}))] ∣ < 1/ p (n),$ 其中该概率取值于 $K G$ 和 $E$ 的随机性.

定义 21.5允许 $E$ 和 $D$ 是随机化算法. 事实上, 为了实现计算安全性, $E$ 必须是随机化的. 同样也表明, 与私钥加密的情况不同, 我们可以将一个仅能处理一比特长消息的公钥加密方案, 转化为能够加密任意长消息(特别是比密钥更长的消息)的公钥加密方案. 这尤其意味着, 即使对于一比特长的消息, 我们也不可能获得一个完美保密的公钥加密方案(因为这将暗示存在一个完美保密的公钥加密方案, 从而特别是存在一个能够加密比密钥更长消息的私钥加密方案).

在本章中, 我们不会给出公钥加密方案的完整构造, 但会提及当今最广泛使用的一些方案所基于的基本思想. 这些方案通常属于以下两类之一:

群论构造: 基于诸如整数分解, 有限域或椭圆曲线上的离散对数等问题.
格/编码构造: 基于诸如格上的最近向量或有界距离解码等问题.

基于群论的加密方案, 如RSA密码系统, Diffie-Hellman协议和椭圆曲线密码学, 目前应用更为广泛. 但基于格/编码的方案近来日益兴起, 特别是因为已知的群论加密方案可以被量子计算机破解, 我们将在第23章讨论这一点.

Diffie-Hellman密钥交换

仅作为公钥加密方案如何构造的一个例子, 现在让我们描述一下Diffie-Hellman密钥交换. 我们将以较为非正式的方式描述Diffie-Hellman协议, 不给出完整的安全性分析.

支撑Diffie-Hellman协议的计算问题是离散对数问题(discrete logarithm problem). 假设 $g$ 是某个整数. 我们可以计算映射 $x \mapsto g^{x}$ 及其逆映射 $y \mapsto lo g_{g} y .$ (例如, 我们可以通过二分搜索来计算对数: 从一个保证包含 $lo g_{g} y$ 的区间 $[x_{min}, x_{ma x}]$ 开始. 然后测试区间的中点 $x_{mi d}$ 是否满足 $g^{x_{mi d}} > y,$ 并据此将区间大小减半)

然而, 现在假设我们使用模运算, 即对某个素数 $p$ 取模. 如果 $p$ 有 $n$ 位二进制数字, 且 $g$ 在 $[p]$ 中, 那么我们可以在 $n$ 的多项式时间内计算映射 $x \mapsto g^{x} mod p .$ (这并不简单, 对你来说是一个很好的练习; 提示: 首先证明可以使用模 $p$ 下的 $k$ 次模乘来计算映射 $k \mapsto g^{2^{k}} mod p .$ 如果遇到困难, 可以查阅维基百科相关条目)另一方面, 由于模运算的“回绕“特性, 我们无法运行二分搜索来找到这个映射的逆(称为离散对数). 事实上, 目前没有已知的多项式时间算法可以计算这个离散对数映射 $(g, x, p) \mapsto lo g_{g} x mod p,$ 这里我们将 $lo g_{g} x mod p$ 定义为满足 $g^{a} = x mod p$ 的数 $a \in [p] .$

Bob 使用Diffie-Hellman协议向Alice发送消息的过程如下:

Alice: 随机选择一个 $n$ 比特长的素数 $p$ (可以通过随机选择数并对其运行素性测试算法来实现), 并随机选择 $g$ 和 $a$ (在 $[p]$ 范围内). 她将三元组 $(p, g, g^{a} mod p)$ 发送给 Bob.
Bob: 收到三元组 $(p, g, h)$ 后, Bob要向Alice发送一条消息 $x \in {0, 1}^{L} .$ 他随机选择 $b \in [p],$ 然后将一对值 $(g^{b} mod p, re p (h^{b} mod p) \oplus x)$ 发送给 Alice. 这里 $re p : [p] \to {0, 1}^{*}$ 是一个“表示函数“, 将 $[p]$ 映射到 ${0, 1}^{L} .$ (函数 $re p$ 不必是单射, 你可以认为 $re p (z)$ 就是简单地输出 $z$ 的自然二进制表示中的 $L$ 位. 它确实需要满足某些技术条件, 在此描述中我们省略了这些条件)
Alice: 收到 $g^{'}, z$ 后, Alice通过计算 $re p (g^{' a} mod p) \oplus z$ 来恢复出 $x .$

该协议的正确性源于一个简单事实: 对于任意 $g, a, b,$ 有 $(g^{a})^{b} = (g^{b})^{a},$ 并且在对素数 $p$ 取模时这仍然成立. 其安全性依赖于一个计算性假设, 即即使在某种“平均情况“下, 计算这个映射也是困难的(这个计算性假设被称为判定性Diffie-Hellman假设, Decisional Diffie Hellman assumption). Diffie-Hellman密钥交换协议可以被视为一种公钥加密, 其中Alice的第一条消息是公钥, Bob的消息是加密后的密文.

我们可以将Diffie-Hellman协议理解为基于一个“陷门伪随机生成器“, 其中三元组 $g^{a}, g^{b}, g^{ab}$ 对不知道 $a$ 的人来说看起来是“随机的“, 但知道 $a$ 的人可以看到, 将第二个元素取 $a$ 次幂就能得到第三个元素. Diffie-Hellman协议可以在任何我们能有效计算群运算的有限阿贝尔群的环境下抽象地描述. 它已经在除模 $p$ 数群以外的其他群上实现, 特别是椭圆曲线密码学(ECC, Elliptic Curve Cryptography) 就是通过在椭圆曲线群上实现Diffie-Hellman协议而获得的, 这带来了一些实际优势. 另一个常见的基于群论的密钥交换/公钥加密协议基础是RSA函数. Diffie-Hellman(包括模算术变体和椭圆曲线变体)和RSA的一个主要缺点是, 这两种方案都可以被量子计算机在多项式时间内破解. 我们将在本课程后续章节讨论量子计算.

其他安全性概念

密码学的范畴远不止加密方案和被动敌手的概念. 其核心目标之一是完整性或认证: 保护通信免遭敌手的篡改. 完整性通常比保密性更为基础: 无论是软件更新还是浏览新闻, 人们往往更关心信息是否确实来自其所声称的来源, 而非通信内容是否保密. 数字签名方案是用于认证的公钥加密的对应物, 并被广泛使用(特别是作为公钥证书的基础), 为数字世界提供了信任的基础.

类似地, 即使对于加密, 我们也常常需要确保能抵御主动攻击的安全性, 因此出现了诸如不可延展性和适应性选择密文安全性等概念. 加密方案的安全性取决于密钥的安全性, 因此确保密钥被正确生成, 能够抵御泄露甚至实现密钥更新(即前向安全性)的机制也得到了研究. 希望本章能让你对密码学这一知识领域有所欣赏, 但不会让你产生在实现密码学方案时虚假的自信.

密码哈希函数是另一种广泛使用的工具, 具有多种用途, 包括从高熵源中提取随机性, 生成文件难以伪造的短“摘要“, 保护密码等等.

魔法

除了加密和签名方案, 密码学家们还成功构建了一些看似矛盾, 如同“魔法“般的成果. 我们简要讨论其中一些. 这里不提供任何细节, 但希望能激发您的好奇心去探索更多.

零知识证明

1903年10月31日, 数学家Frank Nelson Cole在美国数学会的一次会议上做了一个小时的演讲, 期间他没有说一个字. 相反, 他在黑板上计算了 $2^{67} - 1$ 的值, 等于 $147, 573, 952, 589, 676, 412, 927,$ 然后证明了这个数等于 $193, 707, 721 \times 761, 838, 257, 287.$ Cole的证明显示了 $2^{67} - 1$ 不是素数, 但它也揭示了额外的信息, 即它的实际因子. 证明通常如此: 它们教给我们的不仅仅是陈述的真实性.

而在零知识证明(zero knowledge proof)中, 我们试图达到相反的效果. 我们想要一个关于陈述 $X$ 的证明, 这个证明可以严格地显示, 除了 $X$ 为真这一事实之外, 它绝不透露关于 $X$ 的任何额外信息. 这被证明是一个极其有用的工具, 可用于各种任务, 包括认证, 安全协议, 投票, 加密货币中的匿名性等等. 构建这些工具依赖于 $NP$ 完备性理论. 因此, 这个最初旨在给出负面结果(表明某些问题是困难的)的理论, 最终产生了积极的应用, 使我们能够实现否则无法实现的任务.

全同态加密

假设我们有一个字符串的逐比特加密结果 $E_{k} (x_{0}), \dots, E_{k} (x_{n - 1}) .$ 根据设计, 这些密文应该是“完全不可读的“, 我们不应该能从中提取关于 $x_{i}$ 的任何信息. 然而, 早在1978年, Rivest, Adleman和Dertouzos就观察到, 这并不意味着我们不能操作这些加密数据. 例如, 事实证明, 加密方案的安全性并不立即排除这样一种能力: 获取一对密文 $E_{k} (a)$ 和 $E_{k} (b),$ 并从中计算出 $E_{k} (a NAND b)$ 而不知道密钥 $k$ . 但是, 是否存在允许这种操作的加密方案? 如果存在, 这是一个漏洞还是一个特性?

Rivest等人已经表明, 这种加密方案可能极其有用, 并且在云计算时代, 其效用只增不减. 毕竟, 如果我们能计算NAND, 那么我们就可以利用它在加密数据上运行任何算法 $P,$ 将 $E_{k} (x_{0}), \dots, E_{k} (x_{n - 1})$ 映射到 $E_{k} (P (x_{0}, \dots, x_{n - 1})) .$ 例如, 客户端可以将其秘密数据 $x$ 以加密形式存储在云端, 让云提供商对这些数据执行各种计算, 而永远不会向提供商透露私钥, 因此提供商永远无法获知关于秘密数据的任何信息.

这种方案是否存在的问题花了更长的时间才得以解决. 直到2009年, Craig Gentry才首次提出了一种加密方案的构造, 该方案允许在数据上计算通用的基础门电路(在密码学术语中称为全同态加密方案). 金特里的方案在效率方面还有很多不足之处, 而改进该方案一直是一项密集研究计划的焦点, 并且已经取得了显著进展.

多方安全计算

密码学关乎让互不信任的各方能够实现共同目标. 或许实现这一目标最通用的原语是安全多方计算(secure multiparty computation). 安全多方计算的思想是, $n$ 方交互以计算某个函数 $F (x_{0}, \dots, x_{n - 1}),$ 其中 $x_{i}$ 是第 $i$ 方的私有输入. 关键在于不存在普遍信任的方或权威机构, 并且除了函数的输出外, 关于秘密数据的任何信息都不会被泄露. 一个例子是电子投票协议, 其中只揭示总票数, 保护了选民的个人隐私, 同时无需信任任何权威机构能够正确计票或保密信息. 另一个例子是实现第二价格(又称Vickrey)拍卖, 其中 $n - 1$ 方对属于第 $n$ 方的物品出价, 物品归出价最高者所有, 但价格是第二高出价. 使用安全多方计算, 我们可以实现第二价格拍卖, 其方式将确保所有出价的数值(甚至包括最高出价)保密, 只公开第二高的出价; 并确保所有出价者的身份(甚至包括第二高出价者)保密, 只公开最高出价者. 我们强调, 这样的协议甚至不需要信任拍卖师本人, 拍卖师也不会了解到任何额外信息. 安全多方计算甚至可以用于计算随机化过程, 其中一个例子是在网上玩扑克, 而无需信任任何服务器能够正确洗牌或不泄露信息.

本章回顾

我们可以形式化地定义加密方案安全性的概念.
完美保密性确保敌手无论拥有何种计算能力, 都无法从密文中获知任何关于明文的信息.
一次性密码本是一种完美保密的加密方案, 其密钥长度等于消息长度. 没有任何完美保密的加密方案可以使用短于消息的密钥.
计算保密性可以与完美保密性相媲美, 因为它确保计算能力受限的敌手从观察密文中获得的优势是极小的(指数级小). 如果最优 PRG 猜想成立, 那么存在一种计算上安全的加密方案, 其消息长度可以(几乎)指数级地大于密钥长度.
存在许多远超私钥加密范畴的密码学工具. 这些工具包括公钥加密, 数字签名和哈希函数, 以及更“魔法“般的工具, 如多方安全计算, 全同态加密, 零知识证明等等.

习题

参考书目

本文大部分内容取自我的密码学讲义.

Shannon的手稿撰写于1945年, 但当时属于保密文件, 直至1949年才发表了部分版本. 尽管如此, 它彻底变革了密码学领域, 成为后续众多研究的先驱.

Venona项目的历史记载于本文档中. 除Grabeel和Zubko外, 发现苏联重复使用密钥的贡献者还包括Richard Hallock中尉, Carrie Berry, Frank Lewis以及Karl Elmquist中尉, 此外还有其他人员对该项目做出了重要贡献. 详见文档第27-28页.

在最近才披露的1955年致NSA的信函中, John Nash提出了一种“不可破解“的加密方案. 他写道: “*希望我的笔迹等不会让人以为我只是个妄人或者妄想化圆为方者……这一猜想(即特定加密方案对密钥恢复攻击具有指数级安全性)的意义在于, 设计出实际上不可破解的密码是完全可行的. *”³John Nash在数学和博弈论领域做出了开创性贡献, 先后获得数学界阿贝尔奖和诺贝尔经济学纪念奖. 然而他一生深受精神疾病困扰, 其传记《美丽心灵》曾被改编为著名电影. 人们自然会将Nash1955年的这封信与我们之前提到的 Gödel 致von Neumann的信进行比较. 从理论计算机科学角度看, 关键区别在于: 虽然Nash非正式地讨论了指数级与多项式级计算时间的差异, 但他并未提及“图灵机“或其他计算模型, 我们无从判断他是否意识到自己的猜想可以(在形式化“足够复杂的加密类型“前提下)获得精确的数学表述.

本文采用的计算安全性定义源自Goldwasser和Micali于1982年提出的“计算不可区分性“(computational indistinguishability)概念(已知等价于“语义安全性“, semantic security).

尽管Diffie和Hellman使用了不同术语, 但他们已在论文中明确指出其协议可用作公钥加密, 只需将第一条消息放入“公共文件“. 1985年,ElGamal展示了如何基于Diffie-Hellman思想构建“签名方案“, 由于他在同一篇论文中描述了Diffie-Hellman加密方案, 这个由Diffie和Hellman首创的公钥加密方案有时也被称为ElGamal加密.

本人的综述文章讨论了各类公钥假设的差异. 标准椭圆曲线密码方案虽与 Diffie-Hellman 和RSA同样易受量子计算机攻击, 但其主要优势在于: 椭圆曲线群上离散对数问题的最佳已知经典算法时间复杂度为 $2^{ϵ n}$ (其中 $ϵ > 0,$ $n$ 为描述群元素所需的比特数). 相比之下, 模素数 $p$ 的乘法群上最佳算法的时间复杂度为 $2^{O (n^{1/3} p o l y l o g (n))},$ 这意味着(假设已知算法为最优)要达到同等安全级别, 必须设置更大的素数(从而密钥尺寸更大, 通信和计算开销相应增加).

零知识证明由 Goldwasser, Micali和Rackoff于1982年提出, 其广泛应用价值由 Goldreich, Micali和Wigderson于1986年(利用 $NP$ 完全性理论)得以展现.

两方与多方安全计算协议分别由Yao(1982年)以及Goldreich, Micali和Wigderson(1987年)构建. 后者通过引入零知识证明, 实现了将被动敌手安全协议向主动敌手安全协议的一般性转化.

1: 这里有个不错的练习题: 计算一封由随机字母组成的50个字母的信息不包含字母“L“的概率(估算数量级).

2: 原文是 “Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi”, 大意是“系统不能要求保密, 且即便落入敌人手中也不应带来麻烦“. 据史蒂夫·贝洛文所述, 美国国家安全局的版本是“假设我们制造的任何设备的第一个副本都运往了克里姆林宫“.

3: 原文: I hope my handwriting, etc. do not give the impression I am just a crank or circle-squarer…. The significance of this conjecture [that certain encryption schemes are exponentially secure against key recovery attacks] .. is that it is quite feasible to design ciphers that are effectively unbreakable.

| 理论计算机科学导论 |