|
|
如何在一个月内入门密码学？
关注者
2,887
被浏览
626,407
83 个回答
不邀自答。
写在前面
这个问题在我时间线上停留很久了，今天无意中看到 @Megumi Megumi 的回答，突然有种想答题的冲动。因为工作原因，我也经常需要向没有太多密码学甚至抽象代数基础的朋友介绍密码学的基本概念。为此，我也尝试了很多不同的方法。实话说，大部分的方法都不是特别好，很容易让人对密码学有畏惧情绪。不过，最近我在尝试的方法有不错的效果，特来推荐。
英语，英语，英语
要说入门密码学，本质上还是要看知友当前的知识深入和广度，以及知友的英语水平。是的，没错，如果真的想认认真真入门密码学，还是建议知友直接取看英文的内容。用英文直接理解密码学的基本概念反而比中文更合适一些。举个例子，前一阵子我和另一个朋友在翻译安全多方计算（Secure Multi-Party Computation，SMPC）的一本书。SMPC是密码学中非常重要的研究领域了，毕竟几乎所有的密码学方案都可以看成SMPC的一个特例。SMPC中有一个非常常见的术语，叫做Corrupted Party。这个词如果直译的话应该叫做”腐蚀参与方“，听起来就令人费解。这个术语的本意是，协议的攻击者可以控制一部分参与方，使这些参与方可以和攻击者一起实施攻击，像是被攻击者“腐蚀”了一样。我们一直没有找到Corrupted Party的准确翻译，直到将翻译的初稿发送给原作者，原作者邀请自己之前的博士生Yan Huang老师查阅，Yan Huang老师推荐了一个非常准确的翻译：攻陷参与方。我们一致认为这是一个非常准确的翻译，但我们之前从来没有见过有谁提出应该这么翻译。反之，如果直接用英文理解，就可以避免这类理解有偏差的情况出现。
另一个有趣的例子是Oblivious Transfer，这也是SMPC中的一个术语，表示一种特定的协议，协议的功能是：参与方Alice的输入是两个消息 m_0,m_1 ，参与方Bob的输入是一个比特 b 。协议执行完毕后，如果 b=0 ，则Bob可以得到 m_0 ，但没法得到 m_1 ；反之，如果 b=1 ，则Bob可以得到 m_1 ，但没法得到 m_0 ；Alice自始至终都无法知道Bob的输入比特 b 是什么。如果稍微理解一下这个协议的功能就会发现，Alice相当于给Bob发送了一条消息，但Alice不知道发送的消息是哪一个，而Bob也不知道另一条消息是什么。这就好像Alice莫名其妙地给Bob传输了一个她都不知道传的是哪个的消息。Oblivious Transfer的标准翻译叫做“不经意传输”，也有学者翻译为”茫然传输“、”默然传输“，但好像都不能非常形象地描述出Oblivious这个词的意思。如果直接用英文理解，这个词的意思很清晰，用中文理解反而会引入一些歧义。
公开课，不错的入门方法
对于入门一个领域，我一般不会推荐去读一本书，而是推荐看一门优秀的公开课，特别是领域著名专家讲解的公开课。入门一个新领域，我认为最重要的是把握好节奏，确定每天要学哪些内容，并且按照计划把要学习的内容看完。虽然书是分章节的，可以按照章节进行时间划分，但由于每个章节的难度对每个读者来说都不一样，且新领域的知识都是新的，哪怕这本书写得再通俗易懂、再一目了然，也很难明确地给自己一个清晰的时间规划。如果不能按照计划完成相应的章节，很容易出现挫败感。例如，《Head First Java》对于Java初学者来说已经是非常优秀的入门教材了，但面对IO流、UI界面这种不是特别好理解的章节，可能相对需要花费更多的时间。反之，优秀的公开课每个章节的内容量相对比较平均，难度大的章节讲得会细一些，难度低的章节讲得会快一些。这样一来，每个时间段获取的知识相对是比较平均的。于此同时，公开课的内容相对更注重连续性，知识点之间环环相扣，更容易触类旁通、举一反三。此外，公开课一般都会有讨论区，可以和同一时间学习的小伙伴们一起交流。
这就好像会议论文都需要主讲人去会议现场讲解一样。现场讲解会给出论文的主要内容、最核心的思想和贡献，可以让其他学者快速了解论文的主要贡献，从而带着基本思想去阅读论文，达到事半功倍的目的。与之类似，等学习完公开课，具备了入门的知识后，可以再去看相应的教材、甚至是论文。
密码学入门公开课及其优劣比较
密码学领域一直以来有两个非常著名的公开课。一个是斯坦福大学教授Dan Boneh在Coursera上的公开课《Cryptography I》（ https://www. coursera.org/learn/cryp to ）。Coursera现在访问速度有点慢，B站有人搬运了所有的视频，还有简单的翻译（参见 https://www. bilibili.com/video/BV1H t411w7Re?from=search&seid=17308888762148494411 ）。然而，Dan Boneh公开课的问题是：
- Dan Boneh的语速太太太太快了。熟悉我的知友们肯定知道我一直在翻译BIU Winter School的讲座，但我一直没胆量翻译BIU Winter School on Cryptography 2013, Pairing-Based Cryptography（ http:// cyber.biu.ac.il/event/t he-3rd-biu-winter-school/ ）。我自己博士期间就是做身份加密（Identity-Based Encryption）、属性加密（Attribute-Based Encryption）的，要说对Pairing-Based Cryptography应该很熟，最主要的原因就是我实在没法准确听译出Dan Boneh的讲座，不敢乱翻…
- Dan Boneh的课程只包括第一部分。我应该是第一波学习完这门课程的，时间大概是2012年6月左右，但现在已经是2020年6月了，第二部分还没出…
另一个著名的公开课就是Jonathan Katz教授的《Cryptography》（ https://www. coursera.org/learn/cryp tography ）。这门课目前我没有找到比较好的搬运版本，知友们需要在Coursera上面观看。Jonathan Katz是著名密码学教材《Introduction to Modern Cryptography, edition 2》的作者之一。无论是书籍还是课程，都是非常好的密码学学习材料。然而，这门课相对来说有点”数学“，无论是讲解还是作业，涉及到的数学运算都比较多。如果喜欢数学的话，这门公开课是比较不错的选择。
《Applied Cryptography》，怒荐
如果对数学有些许的畏惧，想先了解了解密码学的基本知识，并在一个月内能够入门，我会强烈推荐Udacity的公开课《Applied Cryptography》（ https://www. udacity.com/course/appl ied-cryptography--cs387 ）。
这门课的主讲人是David Evans，也是密码学领域、乃至计算机科学领域的著名教授。如果浏览David Evans的主页（ http://www. cs.virginia.edu/~evans/ ），会发现他竟然出过一本面向儿童的计算机科普漫画，可见David Evans的科普功底。他和密码学家Vladimir Kolesnikov、Mike Rosulek合著的教材《A Pragmatic Introduction to Secure Multi-Party Computation》也是目前最新、最全面的SMPC教材之一。没错，我和另一位朋友翻译的就是这本书，我们也为这本书找到了不少笔误，David Evans、Vladimir Kolesnikov、Mike Rosulek也非常高兴地把我们的意见列举在勘误列表之中（ https:// securecomputation.org/d ocs/errata.pdf ）。
我这里主要推荐《Applied Cryptography》的原因如下：
- 这门课难度非常适中。我在工作中尝试让小伙伴们一起来学习，并且为大家讲解课程中的内容，基本都可以顺利的讲出来并了解的比较全面。
- 这门课的英文讲解很清晰。很少有老师能同时做到上课清晰、科研前沿。David Evans的语速适中，几乎没有任何口音，用词非常简单，内容讲解也非常的清晰。
- 这门课的英文字幕非常准确。作为长期听译英文演讲视频的人来说，我知道很难能制作准确的英文字幕。这门课的英文字幕已经非常准确，部分内容甚至有中文翻译。当然了，这个中文翻译不是我做的… 后面有机会我可以问问David Evans，看有没有兴趣帮他翻译一下这门课。
- 这门课是完全免费的，可以提交小练习、提交作业，有着很好的互动操作。
- 这门课的讲解速度适中。这门课没有讲义，大部分内容都是David Evans教授手写。手写讲义的好处在于，讲义书写节奏适中，方便学生跟上讲解速度。当然了，David Evans也是一个灵魂画手，来看看这灵魂一般的作图：
《Applied Cryptography》一共有10个Lessons，涵盖了古典密码学、对称密码学、非对称密码学、密钥协商、秘密分享及其应用、乃至电子货币、区块链、安全多方计算等前沿密码学研究领域。把这门课听完，基本上可以了解密码学的整体概览，为进一步深入研究相应分支领域提供帮助。
热心的学生们也整理了David Evans课程的讲义（ https://www. cs.virginia.edu/~evans/ courses/crypto-notes.pdf ），David Evans也将讲义免费放出，供参考。从讲义内容也可以看出，这门课覆盖的知识点已经足够丰富了。
我自己对密码学有着基本的了解，每个Lesson平均学习时间大约在3小时（就是听一遍所有的视频、把内容简单整理一下），做编程练习（这是可选项）大约需要2小时的时间。如果对密码学没有太多的了解，可能需要3-4天的时间完成一个Lesson，差不多1个月的时间就可以完成整个课程的学习了。
其他材料推荐
近年来隐私事件频出、区块链蓬勃发展，数据安全领域大火，很多知友都想学习密码学的基础知识。提到密码学书籍，相信大多数人都会推荐两本书，一本是Jonathan Katz和Yehuda Lindell撰写的《Introduction to Modern Cryptography, edition 2》（ http://www. cs.umd.edu/~jkatz/imc.h tml ），另一本是Oded Goldreich撰写的《Foundations of Cryptography》（ http://www. wisdom.weizmann.ac.il/~ oded/foc.html ）。这两本书都是非常优秀的教材，对于想深入理解密码学原理的知友们来说是不可多得的优秀材料。
不过，上面两本书有点老生常谈了。实际上，很多新生代密码学家也撰写了新的书籍。我这里推荐两本目前还没有写完，还在更新的教材。
一本是Dan Boneh和Vector Shoup撰写的密码学研究生教材《A Graduate Course in Applied Cryptography》（ http:// toc.cryptobook.us/ ）。这是一本非常全面的密码学教材，我认为可能比《Introduction to Modern Cryptography》甚至是《The Foundation of Cryptography》更加全面，当前的最新版本是2020年01月更新的，已经接近1000页了。
另一本是新生代密码学家Mike Rosulek的教材《The Joy of Cryptography》（ https:// web.engr.oregonstate.edu /~rosulekm/crypto/ ）。Mike Rosulek是个大帅哥，相信可以吸引很多迷妹… 他的演讲视频讲解得非常清晰，估计过一段时间我就会为知友们带来不少他讲解的讲座了。《The Joy of Cryptography》目前的版本是2020年02月更新的。大概在2周前，Mike Rosulek给我发送了邮件，称预计9个月之后这本书基本可以撰写完毕。如无变化，届时我也会主要参与这本书的翻译工作。当然了，由于这本书是完全免费公开的，翻译版本大概率也会是免费公开的。
以上。
说个靠谱点的流程吧。我就冒昧地当题主零基础了。可以根据实际情况跳过一些步骤。
有问题可以一起交流。
day 1-3: 准备。
数学方面:
需要有一些基本的数论知识。
整除。同余。辗转相除法。
质数及其基本性质。
费马小定理。裴蜀定理。中国剩余定理。
还有对概率要有个基本概念。哪些是很大可能的。哪些是几乎不可能的。
暂时想到这些。当然数学知识肯定是多多益善。
计算机方面:
需要掌握异或运算及其基本性质。
对算法复杂度有个基本概念就行。big O notation什么的稍微理解一下。
最好能编写简单程序。不行的话也没关系。
当然很重要的一点。你要大概知道当今计算机的能力上限。
也就是说哪些是可以很快算出来的。哪些是不现实的。
拿分解质因数来说。你要知道什么样的数是当今计算机分解不了的。
个人认为就今天的计算机来说 (今天是20151031。)
2的40次方次运算是容易 (easy)。
2的56次方次运算是可做 (feasible)。
2的64次方次运算是勉强能做 (barely feasible)。
2的80次方次运算是不能做 (infeasible)。
2的128次方次运算是绝逼不能做 (totally infeasible)。
当然仅仅是个人认为。有异议欢迎提。
day 4-6: 对称密钥加密 (Symmetric Key Encryption)。
掌握以下:
1. 对称密钥加密的基本定义。
2. 几种经典的加密方式及其破解办法。比如替代密码 (Substitution Cipher)和维吉尼亚密码 (Vigenere Cipher)。
3. 一次一密 (One-Time Pad。不是卫生巾!)。
需要知道只有一次一密 (OTP)能保证完美秘密 (Perfect Secrecy)。不过不需要掌握证明过程。
需要知道重复使用OTP有什么后果。
需要知道OTP在实际操作中并没有什么用途。
4. 实际应用中的加密方式。
算是历史啦。大概了解一下就行。
二战期间的:
德国人的谜团 (Enigma)还有Lorenz。
日本人的紫码 (PURPLE)。
还有美国人的纳瓦霍密码 (Navajo Code)。
60年代的:
Feistel Network (找不到中文)。
代换-置换网络 (Substitution-Permutation Network)。
还有IBM的路西法 (LUCIFER)。
然后就是数据加密标准 (Data Encryption Standard。简称DES。)和高级加密标准 (Advanced Encryption Standard。简称AES。)了。
这两个最好重点了解一下。
5. 流加密 (Stream Cipher)和块加密 (Block Cipher)的区别。
(其实一句话就说清啦。)
6. 电码本模式 (Electronic Codebook。简称ECB。)和分组链接模式 (Cipher Block Chaining。简称CBC。)的异同。
7. 几种攻击的定义。
唯密文攻击 (Ciphertext-only Attack)。
已知明文攻击 (Known-plaintext Attack)。
选择明文攻击 (Chosen-plaintext Attack)。
选择密文攻击 (Chosen-ciphertext Attack)。
边信道攻击 (Side-channel Attacks)。
物理攻击 (Physical Attacks)。
day 7: 休息。
day 8-9: 线性密码分析 (Linear Cryptanalysis)和差分密码分析 (Differential Cryptanalysis)。
代换-置换网络 (Substitution-Permutation Network。简称SPN。)。
线性密码分析的原理及基本过程。
如何利用线性关系 (Linear Relations)构造线性逼近(Linear Approximations)。
差分密码分析的原理及基本过程。
day 10: 流加密。
线性反馈移位寄存器 (Linear Feedback Shift Registers。简称LFSR。)。
RC4加密算法。
day 11: 无线网络安全。
大致了解一些标准和协议就行。
如IEEE 802.11。有线等效安全 (Wired Equivalent Privacy。简称WEP。)。
day 12-15: 哈希函数。
哈希函数的定义。
抗原像性 (Preimage Resistance)。
抗第二原像性 (2nd Preimage Resistance)。
抗碰撞性 (Collision Resistance)。
哈希函数的常见应用。比如保护密码。(题外话。国内很多网站好像都存密码原文的。这在我看来是不道德的... 按理说应该只存hash之后的才对。)。修改检测码 (Modification Detection Codes。简称MDCs。)。消息鉴别码 (Message Authentication Codes。简称MACs。)。伪随机比特生成。等等。稍微了解一下就行。
常见哈希函数。如MD5。SHA1。还有各种SHA系列。
详细了解一下SHA1的过程。
大概了解几种经典的在哈希函数中找碰撞的办法和流程。不需要学证明。
大概了解一下王小云这个人以及她的成就。
找到碰撞以后如何利用? 大概了解一下选择前缀碰撞攻击 (Chosen-Prefix Collision Attacks)。还有火焰病毒 (Flame Malware)。
大概了解SHA2和SHA3的过程。
(我真是说了好多个大概了解...)
day 16-17: 消息鉴别码 (MACs)。
MAC的定义。
一个MAC系统怎样才算安全?
MAC的应用。
基本的攻击方法。
CBC-MAC。
如何利用哈希函数构造MAC? 了解一下安全前缀法 (Secret Prefix Method)。安全后缀法 (Secret Suffix Method)。还有信封法 (Envelope Method)。
day 18: 认证加密 (Authenticated Encryption)。
了解几种可能的策略及其应用。
比如
MAC-then-encrypt。应用于安全套接层 (咳。注意断句。)和安全传输层 (SSL/TLS)。
encrypt-then-MAC。应用于IP安全协议 (IPSec)。
encrypt-and-MAC。应用于安全外壳 (SSH)。
如果可以的话最好从理论角度详细了解一下几种策略的过程。
day 19: 公钥加密 (Public-Key Encryption)
思考对称密钥加密的缺点。
理解并掌握公钥加密的定义及过程。
day 20-23: RSA加密算法。
希望这块学得详细点。因为真的很酷。应用也非常广。
数学底子好的话。最好是自己证明加密和解密的过程。
喜欢编程的话。可以自己写程序试试分解大数。看看到什么级别就分解不动了。
呀。要出门了。后边的简略说吧。
day 24: Diffie-Hellman和Elgamal算法。
这个也很重要的。至少了解一下。
day 25: 电子签名 (Digital Signatures)和数字证书 (Digital Certificate)。
看到很多网站地址栏边上的小锁了么?
day 26: 椭圆曲线算法 (Elliptic Curves)。
这个强度比RSA还厉害。但我觉得纯从数学角度讲没RSA美。
嗯。到这儿应该算是"入门"了吧。后面几天选读吧。也可以巩固一下之前的。
day 27: 硬件实施 (Hardware Implementations)。
day 28: 量子密码学 (Quantum Cryptography)。
day 29: 边信道攻击 (Side-channel Attacks)。
好多方法真的闻所未闻。想都想不到。感兴趣可以了解一下。非常有趣。
好了。一个月以内。
嘻嘻。先说这么多。
纯手打。希望不要有错字。