密码学基础 电子科技大学•计算机学院

目 的 了解什么是密码学？ 熟练掌握各种密码算法原理 利用密码算法构造各种安全协议 为密码学理论研究、各类安全应用打基础

学习方法 基础：信息安全数学基础、数论和近世代数 算法和协议：掌握算法和协议的流程，合理性，安全性基础和设计方法。 阅读文献，了解密码学最新进展 密码学顶级会议：CRYPTO、Eurocrypt、Asiacrypt…… 密码学顶级期刊：Journal of Cryptology 相关网址：http://www.iacr.org/ 中国密码学会

课程考核 平时考勤 10分 作业、小论文 20分 期末考试 70分

教材及参考书目 教材： 《现代密码学》许春香等编著，电子科技大学出版社，2008年。 参考书：  参考书： 《现代密码学》，杨波编著，清华大学出版社，2003年。 《计算机密码学—计算机网络中的数据保密与安全》，卢开澄等编著，清华大学出版社，1998年 《现代密码学理论与实践》，[英]Wenbo Mao 著， 王继林等译，王育民等审校，电子工业出版社，2004年。

本课程学习内容： 第1章 引言-密码学的发展概况及基本概念 第2章 流密码 第3章 分组密码 第4章 公钥密码 第5章 数字签名 第1章 引言-密码学的发展概况及基本概念 第2章 流密码 第3章 分组密码 第4章 公钥密码 第5章 数字签名 第6章 Hash函数 第7章 密码协议 第8章 可证明安全性理论 第9章 基于身份的公钥密码体制 第10章 密码学的新方向

第一章 引言 1.1 密码学的发展概况 1.2 密码学的基本概念 1.3 古典密码体制

1.1 密码学的发展概况 密码学是一门古老、年轻且深奥的学科。 密码学经历了从古典密码学到现代密码学的演变。 1.1 密码学的发展概况 密码学是一门古老、年轻且深奥的学科。 密码学经历了从古典密码学到现代密码学的演变。 密码学是研究信息系统安全保密的科学。它包括密码编码学和密码分析学。 1949年前密码技术是一门技术性很强的艺术，而不是一门科学。 1949年shannon “保密系统的通信理论”，密码学成为科学。 1976年Diffie和Hellman“密码学的新方向”，密码学的一场革命。 1977年美国国家标准局公布DES，并公开算法，揭开神秘面纱。

现代密码技术的应用已经深入到数据处理过程的各个环节，包括：数据加密、密码分析、数字签名、信息鉴别、零知识认证、秘密共享等。密码学的数学工具也更加广泛，有概率统计、数论、代数、混沌和椭圆曲线等。

密码学 重要术语 消息 又被称为明文，用某种方法伪装消息以隐藏它的内容的过程称为加密，加了密的消息称为密文，而把密文转变为明文的过程称为解密。

现代密码学引入了密钥，密钥用K表示。 加密 EK（M）=C 解密 DK（C）=M 对密文解密记为 DK（EK（M））=M

有些算法使用不同的加密密钥和解密密钥： EK1（M）=C DK2（C）=M 函数必须具有的特性是，DK2（EK1（M））=M

密码学起源 大约在4000年以前，在古埃及的尼罗河畔，一位擅长书写者在贵族的基碑上书写铭文时有意用加以变形的象形文字而不是普通的象形文字来写铭文，从而揭开了有文字记载的密码史。这篇颇具神秘感的碑文，已具备了密码的基本特征：把一种符号(明文)用另一种符号(密文)代替

公元前5世纪，古斯巴达人使用了一种叫做“天书”的器械，这是人类历史上最早使用的密码器械。“天书”是一根用草纸条、皮条或羊皮纸条紧紧缠绕的木棍。密信自上而下写在羊皮纸条上。然后把羊皮纸条解开送出。把羊皮纸条重新缠在一根直径和原木棍相同的木棍上，这样字就一圈圈跳出来。

公元前1世纪古罗马凯撒大帝时代曾使用过一种“替代式密码”，在这种密码中，每个字母都由其后的第三个字母（按字母顺序）所代替。这种替代式密码直到第二次大战时还被日本海军使用。 公元前4世纪前后，希腊著名作家艾奈阿斯在著作《城市防卫论》中就曾提到一种被称为“艾奈阿斯绳结”的密码。它的作法是从绳子的一端开始，每隔一段距离打一个绳结，而绳结之间距离不等，不同的距离表达不同的字母。

暗号：通过用物件的状态或人的行为来传达事先约定的信息． 隐语：把信息变换成与此信息完全无关的(但有意义的)语言．据说，1941年，日本偷袭珍珠港前，美国情报人员曾截获一次重要的电话对话．对话里“小孩出生”的真正意思是“发动战争” ． 在华盛顿的日本人：是不是真的有个小孩要出生了? 在东京的日本人：是的．而且看来马上就要出生了． 在华盛顿的日本人：这个小孩真的要生了吗?是在哪个方向呢?

16世纪卡尔达诺发明 “卡尔达诺漏格板”．漏格板是一张用硬质材料(如硬纸、羊皮、金属等)做成的板，上面挖了一些长方形的孔，即漏格．

“谜”（ENIGMA）密码 德国人Arthur Scheribius人发明 德国人将其改装为军用型，使之更为复杂可靠 1926年开始使用“ENIGMA”，陆军则于1928年开始使用。 1933年，纳粹最高统帅部通信部决定将“ENIGMA”作为德国国防军新式闪击部队的通信装置。 1940年，盟军破译ENIGMA

传说，古时候有一对夫妻，男的名叫李石匠，女的叫张小花。李石匠靠手艺赚钱，张小花在家纺纱织布。一年，李石匠参加修建石桥，因工程紧张，十一个月也没回家一次。张小花独自在家只有纺车做伴。一天石匠工地回来一个工友路过她家，她托这个工友给丈夫带去一封书信。 归，归，归！速归！如果（鱼果）不归，一刀两断

吴用智赚玉麒麟 卢花滩上有扁舟，俊杰黄昏独自游。 义到尽头原是命，反躬逃难必无忧。

唐伯虎的卖身契 我康宣，今年一十八岁，姑苏人氏，身家清白，素无过犯。只 为家况清贫，卖身华相府中，充当书僮。身价银五十两，自 秋节起，暂存帐房，以三年后支取，从此承值书房，每日焚 香扫地，洗砚、磨墨等事，听凭使唤。从头做起。立此契凭。

几何图形密码 以一种形式写下消息，以另一种形式读取消息 I came I saw I conquered

密码学历史回顾 1949～1975年: 数据的安全基于密钥而不是算法的保密 计算机使得基于复杂计算的密码成为可能 1949年Shannon的“The Communication Theory of Secret Systems” 1967年David Kahn的《The Codebreakers》 1971-73年IBM Watson实验室的Horst Feistel等的几篇技术报告： A Cryptographic Device for Data Communication, 1971 An Experimental Application of Cryptography to a remotely Accessed Data System, 1972 Cryptography and Computer Privacy, 1973 数据的安全基于密钥而不是算法的保密

密码学历史回顾 1976年以后: 公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！！ 1976年Diffie & Hellman的“New Directions in Cryptography”提出了不对称密钥密码 1977年Rivest,Shamir & Adleman提出了RSA公钥算法 90年代逐步出现椭圆曲线等其它公钥算法 公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！！

1976年以后,对称密钥密码算法进一步发展 1977年DES正式成为标准 80年代出现“过渡性”的“post DES”算法,如IDEA,RCx,CAST等 90年代对称密钥密码进一步成熟 Rijndael,RC6, MARS, Twofish, Serpent等出现 2001年Rijndael成为DES的替代者

对称算法 加密和解密由同一个密钥来控制，也叫“单钥算法”，如图所示。

非对称算法 用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来，就是非对称算法（Asymmetric Algorithm），如图所示。

1.2 密码学的基本概念 明文（plaintext）: 没有加密的信息 密文（ciphertext）: 加密后的信息 1.2 密码学的基本概念 明文（plaintext）: 没有加密的信息 密文（ciphertext）: 加密后的信息 加密变换（encryption）: 从明文到密文的变换 解密变换（decryption）: 从密文到明文的变换 密钥(key): 加密和解密是在密钥控制下进行的。 一、密码系统模型 二、密码体制分类 三、密码体制的攻击方法

1.2.1 密码系统模型 公开信道

1.2.2 密码体制分类 对称密码 (单钥密码, 私钥密码): 加密密钥与解密密钥相同 如：分组密码，流密码 对称密码 (单钥密码, 私钥密码): 加密密钥与解密密钥相同 如：分组密码，流密码 非对称密码体制(双钥密码,公钥密码): 加密密钥与解密密钥不同 如：公钥密码

一个好的密码体制至少应满足的两个条件： （1）在已知明文m和加密密钥k1时，计算 容易， 在已知密文c和解密密钥k2时，计算 容易； （2）在不知解密密钥k2时，不可能由密文c恢复出明文m。

可破译的：如果能够根据密文确定明文或密钥，或根据明文及对应的密文确定密钥； 否则称为不可破译的。

1.2.3 密码体制的攻击方法 密码分析者攻击密码体制的方法： （1）穷举攻击：通过试遍所有的密钥来进行破译。 对抗：可增大密钥的数量。 （2）统计分析攻击：通过分析密文和明文的统计规律来破译。 对抗：设法使明文和密文的统计规律不一样。 （3）解密变换攻击：针对加密变换的数学基础，通过数学求解设法找到解密变换。 对抗：选用具有坚实的数学基础和足够复杂的加密算法。

密码分析者通常可以在下述情况下进行攻击： （1）唯密文攻击：密码分析者仅知道一些密文。 （2）已知明文攻击：密码分析者知道一些明文和相应的密文。 （3）选择明文攻击：密码分析者可以选择一些明文，并得到相应的密文。 （4）选择密文攻击：密码分析者可以选择一些密文，并得到相应的明文。 唯密文攻击的强度最弱，攻击强度依此增加。

无条件安全的(不可破译的)：一次一密方案(一次一密乱码本) 计算上安全的：流密码、分组密码、公钥密码 密码算法只要满足以下两条准则之一就行： （1） 破译密文的代价超过被加密信息的价值。 （2 ) 破译密文所花的时间超过信息的有用期。 满足以上两个准则的密码算法在实际中是可用的。

1.3 古典密码体制 古典密码的重要的两种构造方法，代替密码 和置换密码 置换密码 单表代替密码 多表代换密码

1.3.1 置换密码 在置换密码体制中，明文中的字或字母被重新排列，字或字母本身不变，但位置发生了改变，形成密文，又称为易位密码。 最简单的易位密码是采用报文倒置法，即将报文按字的顺序依次倒置，并截成固定长度的字母组，形成密文.

明文：never accept failure no matter how often it visits you 密文：uoys tisi vtin etfo wohr etta mone ulia ftpe ccar even 特点： 简单，缺点是不安全，很容易被识破。 返回

1.3.2 单表代替密码 代替密码是把明文中的每一个字符替换成密文字母表中的另一个字符，并使用密钥K与之进行运算，得到密文；接收者对密文进行逆运算就可以恢复出明文

1.3.2 单表代替密码 在单表代替密码中，只使用一个密文字母表，并且用密文字母表中的一个字母来代替一个明文字母表中的一个字母。设A和B分别为含个字母的明文字母表和密文字母表：定义A到B的一一映射 f :A B: f (ai)=bi f(•) f(•) f(•) f(•)

1.3.2 单表代替密码 单表代换密码又可以分为 加法密码 乘法密码 仿射密码 密钥短语代替密码。

1.3.2 单表代替密码 1、加法密码 Caesar密码就是一种加法密码 f (ai) = bi = aj j = i+k(mod n) , (ai∈A ,0<k<n) Caesar密码就是一种加法密码 明文：ATTACK START FROM TEN PM TONIGHT 密文：DWWDFN VWDUW IURP WHQ SP WRQLJKW

1.3.2 单表代替密码 2、乘法密码 f (ai) = bi = aj j = ik(mod n) , (ai∈A ,0<k<n，(k,n)=1)

1.3.2 单表代替密码 3、仿射密码 是乘法密码和加法密码的结合 f (ai) = bi = aj j = k0 +ik1 (mod n) , (ai∈A ,0<k0 <n，(k1 ,n)=1)

1.3.2 单表代替密码 4、密钥短语代替密码 这种密码选用一个英文短语或者单词串作为密钥，称为密钥字或密钥短语， 例如 HAPPY NEW YEAR，去掉其中的重复字母，得到一个无重复字母的字母串，即HAPYNEWR，把它依次写在明文字母表之下，而后再将字母表中未在字母串中出现过的字母依次写于此短语之后，就可以构造一个字母替换表

1.3.2 单表代替密码 a b c d e f g h i j k l m H A P Y N E W R B C D F G n o p q r s t u v w x y z I J K L M O Q S T U V X Z 当选择密钥短语代替密码和上述的密钥进行加密时，若明文为 h e l l o，则密文为R N F F J。不同的密钥字可以得到不同的替换表，对于明文为英文单词时，密钥短语密码最多可能 有个不同的替换表。

国内密码学发展 西安电子科技大学: 肖国镇教授、王育民教授、王新梅教授 肖国镇教授

上海交通大学：来学嘉教授、陈克非教授、曹珍富教授等

山东大学: 王小云教授、李大兴教授 王小云教授

中科院软件所：冯登国教授、吴文玲教授、胡磊教授等 北京邮电大学：杨义先教授 解放军信息工程大学：戚文峰教授、祝跃飞教授 中山大学：黄继武教授、张方国教授等 武汉大学: 张焕国教授 电子科技大学：秦志光教授、许春香教授、范明钰教授、佘坤教授、张凤荔教授等

第一章重点 密码体制的分类。 密码分析者攻击密码体制的方法： （1）穷举攻击；（2）统计分析；（3）解密变换攻击。 密码分析者通常在下列四种情况下攻击： （1）唯密文攻击；（2）已知明文攻击； （3）选择明文攻击；（4）选择密文攻击。 了解古典密码