密码学的历史源远流长，人类对密码的使用可以追溯到古巴比伦时代。

如图的Phaistos圆盘是一种直径约为160mm的粘土圆盘，它始于公元前17世纪，表面有明显字间空格的字母。

这便是古典密码学的萌芽状态，至于圆盘上的奇怪符号究竟有怎样的含义，我们已经无从得知。

而在古典密码学中，最为知名的莫过于凯撒密码。在两千多年前，罗马国王Julius Caesar(凯撒)就开始使用”凯撒密码”,这一阶段的密码学还不能称为一门学科，密码的编码多半是字谜，这一时期的密码专家常常靠直觉，猜测和信念来设计，分析密码，而不是凭借推理和证明。密码算法采用针对字符的替代（substitution）和置换(permutation)。

从二十世纪到1949年，是近代密码发展阶段。由于机械工业的迅猛发展，这一阶段开始使用机械代替手工计算，发明了机械密码以及进一步的机电密码机，但是密码算法的安全性仍然取决于对称算法本身的保密。这个阶段最具代表的密码机是ENIGMA转轮机。

1949年到1975年，是现代密码学的早期发展阶段。1949年香农发表了论文《保密系统的信息理论》，提出了混淆(confusion)和扩散(diffusion)两大设计原则，为对称密码学建立了理论基础，从此密码学成为一门科学。

克劳德·艾尔伍德·香农（Claude Elwood Shannon）

1967年David Kahn出版了《破译者》，此后，以IBM的horst feistel为代表的大量学者和研究人员开始对密码学产生兴趣并进行研究。

1976年，Whitfield Diffie和Martin Hellman发表了论文《密码学的新方向》，标志着公钥密码学的诞生，他们也因此获得了2015年的图灵奖。

公钥密码体制的特点是采用两个相关的密钥将加密与解密操作分开，一个密钥是公开的，称为公钥，用于加密；另一个密钥保密，为用户专有，称为私钥，用于解密。公钥密码与之前的密码学完全不同，因为公钥算法的基础不再是香农提出的代替和置换，而是基于一种特殊的数学函数——单向陷门函数。

1977年，美国制定了数据加密标准(Data Encryption standard,DES)，公开密码算法的细节，并准许用于非机密单位各商业应用。密码学得到了广泛的应用。

最经典的公钥加密算法莫过于1978年由Rivest，Shamir和Adleman用数论方法构造的RSA算法，它是迄今为止理论上最成熟最完善的公钥密码体制，并已得到广泛应用。RSA算法的安全性可以归约到大整数分解的困难性，即给定两个大素数，将它们相乘很容易，但是给出它们的乘积，再找出它们的因子就很困难。

RonRivest、AdiShamir和LeonardAdleman

目前为止，世界上尚未有任何可靠的攻击RSA算法的手段，只要其密钥长度足够长而且使用方法得当，用RSA加密的信息是很难被破解的。这就是为什么WannaCry病毒那么令人束手无策的原因。

由此可见，密码学的发展经历了漫长的过程，建立了越来越完善的密码体制。

问津课堂邀请来自英国布里斯托大学计算机系博士刘老师，开设线上科研课程《密码学基础理论课程》。通过本期科研课程, 我们可以学习许多经典、好玩、前沿的密码学知识，领略密码学别具一格的内涵与风情。

课题导师

刘老师

毕业于英国布里斯托大学计算机系博士（密码学方向）

// 研究领域主要集中在密码学协议设计与安全分析，具体研究内容有：正式的安全模型、密码学访问控制、区块链及共识算法。

// 相关经历：博士在读期曾担任部分顶级国际会议及期刊审稿人，有辅导本科生论文以及授课经历，现为英国萨里大学任职博士后研究共识算法。

课程安排

题目：密码学基础理论课程

第一课：正式开题，向学生介绍密码学作为一门科学的发展历史、学科基础知识的构成以及现时的应用。同时，本节课将介绍一些密码学的基础知识，并讲述一些古典密码算法以及对应的破译方法。

第二课：介绍完美保密性的概念、一次一密体制（OTP）以及香农理论，并讨论完美保密性的局限性，以此引申出计算安全性和介绍现代密码学及其基本原则。

第三课：详细讲解现代密码学基本原则并从协议设计者角度讲解协议安全，然后引出可证明安全性理论，最后向学生介绍对称密码体系和基于游戏的安全定义。

第四课：初步介绍分组密码、其各种工作模式以及其多种安全定义，然后以归约方式介绍对应安全定义之间的关系，并指导学生尝试以归约方式证明定义之间的关系以此加深认识。

第五课：讲解数据完整性，并介绍保护数据完整性相关的相关密码学方案，包括：认证加密（AE）和带关联数据的认证加密（AEAD）、消息认证码（MAC）以及哈希函数（Hash）。

第六课：继续深入讲解分组密码，介绍现代分组密码设计原则、数据加密标准（DES）以及高级加密标准（AES）。

第七课：讲述部分数论基础知识，目的为了让学生能更好接受接下来的要学习的公钥密码学知识。

第八课：介绍公钥密码学及部分关于公钥加密方案的正式安全模型，讲解RSA密码体制、相关数学难题假设、安全性以及一些针对RSA的攻击，最后介绍最佳非对称加密填充。

第九课：介绍基于离散对数问题的公钥密码学，讲解ElGamal密码体制、相关数学难题假设以及安全性，最后介绍随机预言模型。

第十课：介绍数字签名方案的定义和正式安全模型，讲解RSA、ElGamal和Schnorr签名方案，介绍可证明安全的签名方案。最后讨论在现实应用中的密钥分布问题和证书解决方案。

第十一课：深入讲解基于游戏的安全定义以及讲解复杂协议的安全性证明，介绍以游戏序列来证明协议安全性的手段（基于Victor Shoup和Alexander W. Dent的论文）和混合论证（Hybrid argument），培养学生证明协议安全的基本能力。

第十二课：介绍基于模拟的安全定义并讲解Ran Canetti的Universal Composability（UC）框架，详述在UC框架中如何定义协议的安全性、证明协议安全性以及该框架的Composition理论。

第十三课：以密码学协议的基石之一——密钥交换协议为例，向学生讲解两种不同的正式安全定义途径（基于游戏和基于模拟）的联系和二者间存在的间隙，最后总结二者优缺点以及局限性等。

第十四课：介绍由机械检查协议安全的技术，分别介绍在Dolve-Yao模型下使用的ProVerif以及在计算模型下使用的CryptoVerif，最后讨论此项技术现时的发展与研究。

第十五课：介绍以下进阶密码学协议：秘密分享方案、承诺方案、不经意传输和零知识证明，以及介绍安全多方计算。

第十六课：介绍基于配对的密码学和密码学访问控制，介绍密码学访问控制的安全性、隐私问题、实现和效率。

第十七课：答疑课，针对前面的知识点进行答疑，前面课程的涵盖了现代密码学大部分基础知识和部分密码学协议安全性的定义和证明手段，学生在尝试进行安全性证明时容易遇见各种问题，需要老师指导和讲解。

第十八课：对密码学的一些前沿研究进行讲解以及讨论其应用，让学生对现今密码学研究有所认识并启发自身未来的研究方向。

项目收获

01. 学术报告

课程结束后，学生会在导师和助教的帮助下，完成一篇符合欧美名校标准的学术报告，并能作为学生将来申请国内外名校的附加资料。

02. 学术论文

学术科研精品课程+论文辅导及保发(1v1)项目中，学生将会在导师和助教的全程辅导下，以第一作者身份完成并发表一篇全英文的EI/CPCI国际会议论文。如果英文写作功底较弱，也可以选择发表国内省刊或者国家级期刊（非核心学术期刊）。

03. 推荐信

项目导师会针对每个学生在项目中的研究内容和具体表现写一封实名推荐信，实现真实和权威的定制化推荐。同时学生也会收到一份电子档副本，以便选取最有价值的推荐信用于申请。

04. 结业证书

在学生顺利完成项目后，将会被授予由问津课堂项目委员会签发的结业证书，并由委员会主席和项目导师亲笔签名。