《密码学》教案
张焕国，唐明，伍前红 武汉大学计算机学院
一、 教学目的
本课程是计算机科学与技术、信息安全专业的专业选修课。开设本课程的目的是使学生了解并掌握计算机安全保密所涉及的基本理论和方法，具备保障信息安全的基本能力。
二、 教学要求
通过讲授、讨论、实践，使学生了解计算机安全的威胁、密码学算法、安全技术的发展，熟悉计算机安全保密的基本概念、操作系统安全和网络安全，掌握计算机密码学的基本理论、基本方法、常见加密算法及其实现技术、应用方法，重点掌握传统加密算法、DES算法、AES算法、背包算法、RSA算法、ECC算法、DSA算法等。
第一讲 密码学的基本概念
一、信息安全学科概论 1、信息安全学科建设
2001年经教育部批准武汉大学创建了全国第一个信息安全本科专业； 2007年全国信息安全本科专业已达70多所高校；
2003年经国务院学位办批准武汉大学建立信息安全硕士点、博士点、博士后流动站 2007年1月成立国家信息安全教指委
2006年武汉大学信息安全专业获湖北省“品牌专业”
武汉大学成为我国信息安全科学研究和人才培养的重要基地。 2、信息安全学科特点
? 信息安全学科是交叉学科：计算机、通信、数学、物理、生物、管理、法律等； ? 具有理论与实际相结合的特点；
? 信息安全技术强调整体性、系统性、底层性；
? 对信息安全来说，法律、管理、教育的作用很大，必须高度重视。 ? 人才是关键，人的综合素质是关键的关键！ 3、武汉大学的办专业思路
以学信息安全为主，兼学计算机、通信，同时加强数学、物理、法律等基础，掌握信息安全的基本理论与技能，培养良好的品德素质。 二、信息安全的基本概念 1、信息安全事关国家安全
信息成为社会发展的重要战略资源，信息技术改变着人们的生活和工作方式。信息产业成为新的经济增长点。社会的信息化已成为当今世界发展的潮流。 信息获取、处理和安全保障能力成为综合国力的重要组成部分。 信息安全事关国家安全，事关社会稳定。 2、信息系统安全的概念 能源、材料、信息是支撑现代社会大厦的三根支柱。 信息是逻辑的、抽象的，不能脱离系统而独立存在！
① 信息系统安全包括四个层面
信息系统安全＝设备安全＋数据安全＋内容安全＋行为安全
简称信息系统安全为信息安全！ ② 中文词安全＝Security + Safety
–中文安全的含义等于英文Security 加上Safety的含义。
–Security是指阻止人为的对安全的危害。 –Safety是指阻止非人为的对安全的危害。
③信息系统设备安全的概念
信息系统设备的安全是信息系统安全的首要问题和基础之一。
三个侧面：设备的稳定性(Stability )，设备的可靠性(Reliability)，设备的可用性(Availabity)。
设备：硬设备，软设备 ④数据安全的概念
IBM公司的定义：采取措施确保数据免受未授权的泄露、篡改和毁坏。
–说明：这个定义明确了信息安全的三个侧面：数据的秘密性(Secrecy)，数据的真实性(Authenticity)，数据的完整性(Integrity)。
–这个定义还说明了，为了信息安全必须采取措施，必须付出代价，代价就是资源（时间和空间）。 ⑤内容安全的概念
内容安全是信息安全在法律、政治、道德层次上的要求。 政治上健康
符合国家法律、法规 符合中华民族道德规范 ⑥行为安全的概念
行为安全是信息安全的终极目的。
符合哲学上，实践是检验真理的唯一标准的原理。 从过去的仅看身份，发展为既看身份更看行为。 三个侧面：
行为的秘密性； 行为的完整性； 行为的可控性。 3、信息安全措施
◆信息安全措施＝{法律措施，教育措施，管理措施，技术措施，
注意：决不能低估法律、教育、管理的作用，许多时候它们的作用大于技术。 ①信息安全的技术措施
信息安全技术措施＝{硬件系统安全、操作系统安全、密码技术、通信安全、网络安全、数据库安全、病毒防治技术，防电磁辐射技术，信息隐藏技术，数字资源保护技术，电子对抗技术，···}。
注意：硬件结构的安全和操作系统安全是基础，密码、网络安全等是关键技术。 ②信息安全的管理措施
信息安全管理措施既包括信息设备、机房的安全管理，又包括对人的安全管理，其中对人的管理是最主要的。
目前，计算机网络系统安全的最大威胁之一是缺少有效的计算机网络安全监管。 ③信息安全的法律措施
信息安全措施包括各级政府关于信息安全的各种法律、法规。 商用密码管理条例； 计算机安全管理条例； 因特网安全管理条例等。 ④信息安全的教育措施
对人的思想品德教育、安全意识教育、安全法律法规的教育等。国内外的计算机犯罪事件都是人的思想品德出问题造成的。
信息安全是一个系统工程必须综合采取各种措施才能奏效。 4、计算机系统的安全服务功能： 身份认证服务， 访问控制服务， 数据加密服务， 数据完整性服务， 不可否认服务，
安全审计。
三、密码学的基本概念
密码技术是一门古老的技术。世界各国都视密码为武器。战争的刺激和科学技术的发展推动了密码学的发展。信息技术的发展和广泛应用为密码学开辟了广阔的天地。 我国的密码分级：
①核心密码： 用于保护党、政、军的核心机密。 ②普通密码：
用于保护国家和事企业单位的低于核心机密而高于商用的机密信息。 ③商用密码：
用于保护国家和事企业单位的非机密的敏感信息。 ④个人密码：
用于保护个人的隐私信息。
前三种密码均由国家密码管理局统一管理！ 我国商用密码政策：
①统一领导： 国家密码管理局统一领导。 ②集中管理：
国家密码管理局办公室集中管理。 ③定点研制： 只允许定点单位进行研制。 ④专控经营：
经许可的单位才能经营。 ⑤满足使用：
国内各单位都可申请使用。 1、密码的基本思想
伪装信息，使未授权者不能理解它的真实含义。所谓伪装就是对信息进行一组可逆的数学变换。伪装前的原始信息称为明文, 伪装后的信息称为密文，伪装的过程称为加密。去掉伪装还原明文的过程成为解密。加密在加密密钥的控制下进行。解密在解密密钥的控制下进行。用于加密的一组数学变换称为加密算法。用于解密的一组数学变换称为解密算法。 2、密码体制(Cryptosystem)的构成
密码体制由以下五部分组成： ①明文空间M：全体明文的集合 ②密文空间C：全体密文的集合
③密钥空间K：全体密钥的集合，K＝
⑤解密算法D：一族由C?M的解密变换。解密变换是加密变换的逆。 对于一个确定的密钥，加密算法将确定出一个具体的加密变换，解密算法将确定出一个具体的解密变换，而且解密变换就是加密变换的逆变换。 对于明文空间的每一个明文M，加密算法E在密钥Ke的控制下将明文M加密成密文C： C＝E(M, Ke )。
而解密算法D在密钥Kd的控制下将密文解出同一明文M。 M＝D(C, Kd)= D(E(M, Ke), Kd) 3、密码体制的分类
从加密钥与解密钥是否相等划分：
⑴ 传统密码：
⑵ 公开密钥密码： 从密钥的使用方式划分：
⑴ 序列密码：
①明文、密文、密钥以位（字符）为单位加解密； ②核心密码的主流； ⑵ 分组密码：
①明文、密文、密钥以分组为单位加解密； ②商用密码的主流：
①传统密码： 分组：DES IDEA EES AES MS4 序列：RC4
②公开密钥密码： RSA ELGamal ECC 新型密码：
(1)演化密码
①密码算法不断演化变化，越来越强的密码。 ②密码设计自动化的一种方法。
③借鉴生物进化，将密码学与演化计算结合 (2)量子密码
①在唯密文攻击下绝对安全的密码。 ②逐步走向实用。 ③2007年我国宣布，国际上首个量子密码通信网络由我国科学家在北京测试运行成功。这是迄今为止国际公开报道的唯一无中转、可同时、任意互通的量子密码通信网络，标志着量子保密通信技术从点对点方式向网络化迈出了关键一步。 (3)DNA密码
? DNA密码基于生物学中的某种困难问题。
? 由于DNA密码的安全不依赖于计算困难问题，所以不管未来的电子计算机、量子
计算机和DNA计算机具有多么强大的计算能力，DNA密码对于它们的计算攻击都是免疫的 。
4、密码学的组成
①研究密码编制的科学称为密码编制学(Cryptography), ②研究密码破译的科学称为密码分析学(Cryptanalysis)，
③而密码编制学和密码分析学共同组成 密码学(Cryptology)。 5、密码分析
①如果能够根据密文系统地确定出明文或密钥，或者能够根据明文-密文对系统地确定出密钥，则我们说这个密码是可破译的。
②一个密码，如果无论密码分析者截获了多少密文和用什么方法进行攻击都不能被攻破，则称为是绝对不可破译的。
③绝对不可破译的密码学在理论上是存在的—— “一次一密”
1)穷举攻击 密码分析者采用依次试遍所有可能的密钥对所获密文进行解密，直至得到正确的明文；或者依次用一个确定的密钥对所有可能的明文进行加密，直至得到所获得的密文。显然，理论上，对于任何实用密码只要有足够的资源，都可以用穷举攻击将其改破。实例：1997年美国一个密码分析小组宣布：1万多人参加，通过INTERNET网络，利用数万台微
机，历时4个多月，通过穷举攻破了DES的一个密文。美国现在已有DES穷举机，多CPU并行处理，24小时穷举出一个密钥。
2)统计分析攻击 所谓统计分析攻击就是指密码分析者通过分析密文和明文的统计规律来破译密码。统计分析攻击在历史上为破译密码作出过极大的贡献。许多古典密码都可以通过统计分析而破译。
3)数学分析攻击 所谓数学分析攻击是指密码分析者针对加密算法的数学依据通过数学求解的方法来破译密码。为了对抗这种数学分析攻击，应当选用具有坚实数学基础和足够复杂的加密算法。
根据占有的数据资源分类：
A)仅知密文攻击（Ciphertext-only attack）
所谓仅知密文攻击是指密码分析者仅根据截获的密文来破译密码。因为密码分析者所能利用的数据资源仅为密文，因此这是对密码分析者最不利的情况。 密码学的基本假设：攻击者总能获得密文。 攻击者总能知道密码算法。 攻击者不知道密钥。 根据占有的数据资源分类：
B)已知明文攻击（Known-plaintext attack）
所谓已知明文攻击是指密码分析者根据已经知道的某些明文-密文对来破译密码。 攻击者总是能获得密文，并猜出部分明文。
计算机程序文件加密特别容易受到这种攻击。 根据占有的数据资源分类：
C)选择明文攻击（Chosen-plaintext attack）
所谓选择明文攻击是指密码分析者能够选择明文并获得相应的密文。
计算机文件加密和数据库加密特别容易受到这种攻击。 这是对攻击者最有利的情况！ 6、密码学的理论基础
⑴ 商农信息论
①从信息在信道传输中可能受到攻击，引入密码理论； ②提出以扩散和混淆两种基本方法设计密码；
③阐明了密码系统，完善保密，理论保密和实际保密等概念。 ⑵ 计算复杂性理论
①密码的安全性以计算复杂度来度量；
②现代密码往往建立在一个数学难题之上，而难是计算复杂度的概念； ③计算复杂度只能为密码提供一个必要条件。 7、密码设计的基本方法
⑴ 公开设计原则
密码的安全应仅依赖于对密钥的保密，不依赖于对算法的保密。 ⑵ 扩散和混淆
①扩散(diffusion)：将明文和密钥的每一位的影响散布到尽量多的密文位中；理想情况下达到完备性。
②混淆(confusion):使明文、密钥和密文之间的关系复杂化。 ⑶ 迭代与乘积
①迭代：设计一个轮函数，然后迭代。
②乘积：将几种密码联合应用。 8、密码学的一些结论：
① 公开设计原则：密码的安全只依赖于密钥的保密，不依赖于算法的保密； ② 理论上绝对安全的密码是存在的：一次一密； ③ 理论上，任何实用的密码都是可破的； ④ 我们追求的是计算上的安全。
⑤计算上的安全：使用可利用的计算资源不能破译。
复习题
① 解释信息安全的含义。 ② 密码的基本思想是什么？
③ 密码体制分哪些类型？各有什么优缺点？ ④ 什么是密码分析？密码分析有哪些类型？
⑤ 为什么说理论上，任何实用的密码都是可破的？
⑥ 计算机的程序文件和数据库文件加密容易受到什么攻击？为什么？
第二讲 古典密码
一、主要古典密码 C. D. Shannon:
采用混淆、扩散和乘积的方法来设计密码 混淆：使密文和明文、密钥之间的关系复杂化
扩散：将每一位明文和密钥的影响扩大到尽可能多的密文位中。 乘积和迭代：多种加密方法混合使用对一个加密函数多次迭代 古典密码编码方法：
置换，代替，加法 1、置换密码
把明文中的字母重新排列，字母本身不变，但其位置改变了，这样编成的密码称为置换密码。最简单的置换密码是把明文中的字母顺序倒过来，然后截成固定长度的字母组作为密文。
明文：明晨5点发动反攻。
MING CHEN WU DIAN FA DONG FAN GONG 密文：GNOGN AFGNO DAFNA IDUWN EHCGN IM 理论上：
①、置换密码的加密钥是置换矩阵 p，解密钥是置换矩阵 p-1 。 ②、置换密码经不起已知明文攻击。 ⑴单表代替密码
①、加法密码
A和B是有 n个字母的字母表。 定义一个由A到B的映射：f:A→B f(ai )= bi=aj j=i+k mod n
加法密码是用明文字母在字母表中后面第 k个字母来代替。 K=3 时是著名的凯撒密码。 ②、乘法密码
A和B是有n个字母的字母表。 定义一个由A到B的映射：f:A→B f(ai )= bi= aj j=ik mod n
其中，(n,k)=1。
注意：只有(n,k)=1，才能正确解密。
③密钥词组代替密码：随机选一个词语，去掉其中的重复字母，写到矩阵的第一行，从明文字母表中去掉这第一行的字母，其余字母顺序写入矩阵。然后按列取出字母构成密文字母表。 举例：
密钥： HONG YE
矩阵： HONGYE 选出顺序：按列 ABCDFI
JKLMPQ 改变密钥、矩阵大小 RSTUVW 和取出序列，得到不同的 XZ 密文字母表。 密文字母表 :
B={ HAJRXOBKSZNCLTGDMUYFPVEIQW }
⑵、多表代替密码
单表代替密码的安全性不高，一个原因是一个明文字母只由一个密文字母代替。 构造多个密文字母表，
在密钥的控制下用相应密文字母表中的一个字母来代替明文字母表中的一个字母。一个明文字母有多种代替。
Vigenere密码：著名的多表代替密码 3、代数密码： ① Vernam密码
明文、密文、密钥都表示为二进制位：
M=m1,m2,… ,mn K =k1,k2,… ,kn C =c1,c2,… ,cn ② 加密 ： c1= mi⊕ ki ,i=1,2,… ,n 解密 ： m1= ci⊕ ki ,i=1,2,… ,n
③因为加解密算法是模2加，所以称为代数密码。 ④对合运算：f=f-1，模 2加运算是对合运算。
密码算法是对和运算，则加密算法＝解密算法，工程实现工作量减半。 ⑤ Vernam密码经不起已知明文攻击。
⑥ 如果密钥序列有重复，则Vernam密码是不安全的。 ⑦一种极端情况：一次一密
? 密钥是随机序列。
? 密钥至少和明文一样长。 ? 一个密钥只用一次。
⑧一次一密是绝对不可破译的，但它是不实用的。
⑨ 一次一密给密码设计指出一个方向，人们用序列密码逼近一次一密。 二、古典密码的穷举分析 1、单表代替密码分析 ①加法密码
因为f(ai )= bi=aj j=i+k mod n
所以k=1,2，... ,n-1,共n-1种可能，密钥空间太小。以英文为例，只有25种密钥。 经不起穷举攻击。 ②乘法密码
因为f(ai )= bi=aj
j=ik mod n，且（k,n）=1。
所以k共有?（n）种可能，密钥空间更小。
对于英文字母表，n=26，k=1,3,5,7,9,11,15,17,19,21,23,25 取掉1，共11种，比加法密码更弱。经不起穷举攻击。 ③密钥词语代替密码
因为密钥词语的选取是随机的，所以密文字母表完全可能穷尽明文字母表的全排列。 以英文字母表为例，n=26，所以共有26！种可能的密文字母表。
26！≈4?10
用计算机也不可能穷举攻击。
注意：穷举不是攻击密钥词语代替密码的唯一方法。 三、古典密码的统计分析
1、密钥词组单表代替密码的统计分析
任何自然语言都有自己的统计规律。如果密文中保留了明文的统计特征，就可用统计方法攻击密码。由于单表代替密码只使用一个密文字母表，一个明文字母固定的用一个密文字母来代替，所以密文的统计规律与明文相同。因此，单表代替密码可用统计分析攻破。 2、英语的统计规律 每个单字母出现的频率稳定。 最高频率字母 E
次高频率字母 T A O I N S H R 中高频率字母 D L
低频率字母 C U M W F G Y P B 最低频率字母 V K J X Q Z 频率最高的双字母组：
TH HE IN ER AN RE ED ON ES ST EN AT TO NT HA ND OU EA NG AS OR TI IS ET IT AR TE SE HI OF 频率最高的三字母组：
THE ING AND HER ERE ENT THA WAS ETH FOR DHT HAT SHE ION HIS ERS VER
其中THE的频率是ING的3倍！
英文单词以E，S，D，T为结尾的超过一半。 英文单词以T，A，S，W为起始字母的约占一半。 还有其它统计规律！
教科书上有一个完整的统计分析例子。 经得起统计分析是对近代密码的基本要求！
26
复习题
① 已知置换如下： 1 2 3 4 5 6 3 5 1 6 4 2 明文＝642135 ,密文＝？ 密文＝214365 ，明文＝？
②使加法密码算法称为对合运算的密钥k称为对合密钥，以英文为例求出其对合密钥。 ③ 已知一个加法密码的密文如下：
BEEAKFYDJXUQYHYJIQRYHTYJIQFBQDUYJIIKFUHCQD 用穷举法求出明文。
④以英文为例，用加法密码，取密钥常数 k= 7,对明文 INFORMATION SECURITY，进行加密，求出密文。 ⑤证明，在置换密码中，置换p是对合的，当且仅当对任意的i和j(i, j=1,2,3,…,n)，若p(i)=j，
则必有p(j)=i 。
⑥编程实现Vigenre密码。 ⑦ 分析仿射密码的安全性。
第三讲数据加密标准DES
一、DES的概况
1、重要时间：
1973年美国国家标准局（NBS）向社会公开征集加密算法，以制定加密算法标准； 1974年第二次征集；
1975年选中IBM的算法，公布征求意见； 1977年1月15日正式颁布； 1998年底以后停用。
1999年颁布3DES为新标准。 2、标准加密算法的目标
①用于加密保护政府机构和商业部门的非机密的敏感数据。 ②用于加密保护静态存储和传输信道中的数据。 ③安全使用10 ~15年。 3、整体特点
①分组密码:明文、密文和密钥的分组长度都是64位。
②面向二进制的密码算法:因而能够加解密任何形式的计算机数据。 ③对合运算:因而加密和解密共用同一算法，使工程实现的工作量减半。 ④综合运用了置换、代替、代数等多种密码技术。 4、应用
①许多国际组织采用为标准。 ②在全世界范围得到广泛应用。
③产品形式：软件（嵌入式，应用软件）；硬件（芯片，插卡） 5、结论
用于其设计目标是安全的。
设计精巧、实现容易、使用方便，堪称典范。
二、算法
1、DES加密过程的数学描述： Li = Ri-1
Ri =Li-1⊕f (Ri-1,Ki) i =1,2,3,…16 2、置换选择1：
①、作用
去掉密钥中的8个奇偶校验位。
打乱重排，形成C0 (左28位)，D0 (右28位) 。 3、循环移位：
①、作用
对C0 ，D0 分别循环移位。 4、置换选择2：
①、作用
从Ci 和 Di（56位）中选择出一个48位的子密钥Ki。 5、初始置换IP
①、作用
把64位明文打乱重排。
左一半为L0 (左32位) ，右一半为R0 (右32位) 。
例：把输入的第1位置换到第40位，把输入的第58位置换到第1位。
－
6、逆初始置换IP1
①、作用
把64位中间密文打乱重排。 形成最终的64位密文。 7、加密函数f
①作用
DES的核心。 加密数据。
数据处理宽度32位。 ②选择运算E
把32位输入扩充为48位中间数据； 重复使用数据实现扩充。 ③选择替换S（S盒）
S盒是DES唯一的非线性变换。 S盒是DES安全的关键。 共有8个S盒。
每个S盒有6个输入，4个输出，是一种非线性压缩变换。
设输入为b1b2b3b4b5b6 ,则以b1b6组成的二进制数为行号，b2b3b4b5组成的二进制数为列号。行列交点处的数（二进制）为输出。 ④置换运算P
把数据打乱重排。 8、DES的解密过程
DES的运算是对和运算，解密和加密可共用同一个运算。
不同点：子密钥使用的顺序不同。第一次解密迭代使用子密钥 K16 ，第二次解密迭代使用子密钥 K15 ，第十六次解密迭代使用子密钥 K1 。 DES解密过程的数学描述： Ri-1= Li
Li-1= Ri ⊕f (Li,Ki) i =16,15,14，...，1 9、DES的对和性证明 1、可逆性证明
①定义 T是把64位数据的左右两半交换位置： T（L，R）＝（R，L）
2
因为，T（L，R）＝（L，R）＝I ，其中 I为恒等变换，于是，
1
T=T –，
所以 T变换是对合运算。 ②记DES第 i轮中的主要运算为，即
Fi（Li –1，Ri -1）＝（Li -1⊕f（Ri -1, Ki），R i -1）
Fi 2＝Fi（Li -1⊕f（Ri -1, Ki），R i -1）
＝（Li -1⊕f（Ri -1, Ki）⊕f（Ri -1, Ki），R i -1） ＝（Li –1，Ri -1） ＝I
所以，Fi ＝Fi –1 。 所以 Fi变换也是对合运算。
③结合①、②，便构成DES的轮运算 Hi ＝FiT 因为（FiT）（TFi）=（Fi（TT）Fi）=FiFi =I ， 所以
－
（FiT）1＝（TFi）
－
（FiT）＝（TFi）1 ④加解密表示
-1
⑴ DES(M) ＝IP (F16) (T F15) … (TF2) (TF1)IP（M）＝C
-1
⑵ DES(C)＝IP -1(F1) (T F2) (T F3)… (T F15) (T F16)IP（C） 把⑴ 式代入⑵式可证：
-1
DES(DES(M))＝M 所以，DES是可逆的。 2、对合性证明
DES ＝IP -1(F16) (TF15) (TF14)…(TF3) (TF2) (TF1)IP -1
DES＝IP -1(F1) (TF2) (TF3)…(TF14) (TF15) (TF16)IP
-1
DES和DES除了子密钥的使用顺序相反之外是相同的， 所以DES的运算是对合运算。 10、DES的安全性 ①攻击
穷举攻击。目前最有效的方法。 差分攻击。 线性攻击。 11、3重DES
①美国NIST在1999年发布了一个新版本的DES标准（FIPS PUB46-3）： DES只用于遗留系统。
3DES将取代DES成为新的标准。 国际组织和我国银行都接受3DES。 ② 3DES的优势：
3密钥的3DES：密钥长度是168位。 2密钥的3DES：密钥长度是112位。 安全：密钥足够长；
经过最充分的分析和实践检验。 兼容性好。 12、DES的历史回顾
DES的出现标志着商业密码需求的增加。 DES体现商农的密码设计理论。
体现了公开设计原则，开创公开算法的先例。
DES代表当时商业密码的最高水平。
大作业1
以3DES作为加密算法开发出文件加密软件系统：
具有文件加密和解密功能； 具有加解密速度统计功能；
采用密文反馈链接和密文挪用短块处理技术； 具有较好的人机界面。
复习题
1、分析DES的弱密钥。
2、证明DES具有互补对称性。
3、画出3密钥 3DES的框图。
第四讲 高级数据加密标准
一、AES的概况 1、历史时间：
1997年美国政府向社会公开征集高级数据加密标准（AES）； 1998年8月20日从应征的21个算法中选出15个。 1999年8月又选中其中5个算法。 2000年10月2日再选出1个算法。 2001年11月26日接受其作为标准。 2001年12月4日正式公布：FIPS－197。 2、AES产生的背景
①1984年12月里根总统下令由国家保密局研制新密码标准，以取代DES。 ②1991年新密码开始试用并征求意见。
民众要求公开算法，并去掉法律监督。 ③1994年颁布新密码标准（EES）。
④1995年5月贝尔实验室的博士生M.Blaze在PC 机上用45分钟攻击法律监督字段获得成功。
⑤1995年7月美国政府放弃用EES加密数据。 ⑥1997年美国政府向社会公开征AES。
⑦美国商用密码政策的变化
公开征集 秘密设计 公开征集
成功 不成功 预计成功 3、AES的设计要求
①安全性：抵抗所有已知攻击； ②实用性：适应各种环境，速度快； ③扩展性：分组长度和密钥长度可扩展。 4、整体特点
①分组密码:明文长度128,密文长度、密钥长度可变（128/192/256等,现在一般取 128 ） 。
②面向二进制的密码算法:能够加解密任何形式的计算机数据。 ③不是对合运算:加、解密使用不同的算法。 ④综合运用置换、代替、代数等多种密码技术 ⑤整体结构：基本轮函数加迭代。圈数可变，≥10 5、应用
①许多国际组织采用为标准。 ②尚未大范围应用。
③产品形式：软件（嵌入式，应用软件）；硬件（芯片，插卡） 6、结论
只有通过实际应用的检验才能证明其安全。
我们相信：经过全世界广泛分析的AES是不负众望的。 二、AES的基本变换 1、AES的数据处理方式
①字节 ②字 ③状态 2、状态
①加解密过程中的中间数据。
②以字节为元素的矩阵，或二维数组。 ③符号：Nb－明密文所含的数据的字数。 Nk－密钥所含的数据的字数。 Nr－迭代圈数。
④ 例：Nb＝4时的状态 Nk＝4时的密钥数组
a0,0 a0,1 a0,2 a0,3 k0,0 k0,1 k0,2 k0,3 a1,0 a1,1 a1,2 a1,3 k1,0 k1,1 k1,2 k1,3 a2,0 a2,1 a2,2 a2,3 k2,0 k2,1 k2,2 k2,3
a3,0 a3,1 a3,2 a3,3 k3,0 k3,1 k3,2 k3,3
⑤Nb、Nk、Nr之间的关系：
Nr Nb=4 Nb=6 Nb=8
Nk=4 10 12 14 Nk=6 12 12 14 Nk=8 14 14 14 3、圈变换－加密轮函数
①标准圈变换：
Round(State,RoundKey)
?
ByteSub(State); S盒变换 ShiftRow(State); 行移位变换 MixColumn(State); 列混合变换
AddRoundKey(State,RoundKey) 圈密钥加变换 ?
②最后一圈的圈变换： Round(State,RounKey)
?
ByteSub(State); S盒变换 ShiftRow(State);行移位变换
AddRoundKey(State,RoundKey) 圈密钥加变换
?
注：最后一圈的圈变换中没有列混合变换。 4、S盒变换 ByteSub(State)
①S盒变换是AES的唯一的非线性变换，是AES安全的关键。 ②AES使用16个相同的S盒，DES使用8个不相同的S盒。
③AES的S盒有8位输入8位输出，DES的S盒有6位输入4位输出。 ④S盒变换:
a)将输入字节用其GF(28)上的逆来代替； b)对a)的结果作如下的仿射变换：
（以x0－ x7作输入，以y0－ y7作输出。）
y0 1 0 0 0 1 1 1 1 x0 1 y1 1 1 0 0 0 1 1 1 x1 1 y2 1 1 1 0 0 0 1 1 x2 0 y3 = 1 1 1 1 0 0 0 1 x3 + 0 y4 1 1 1 1 1 0 0 0 x4 0 y5 0 1 1 1 1 1 0 0 x5 1 y6 0 0 1 1 1 1 1 0 x6 1 y7 0 0 0 1 1 1 1 1 x7 1 注意：
S盒变换的第一步是把字节的值用它的乘法逆来代替，是一种非线性变换。 由于系数矩阵中每列都含有 5个1，这说明改变输入中的任意一位，将影响输出中的 5位发生变化。
由于系数矩阵中每行都含有 5个1，这说明输出中的每一位，都与输入中的 5位相关。 三、圈密钥生成
W0 W1 W2 … WNk-1 WNk WNk+1 …
用户密钥
当 j 不是Nk的整数倍时: Wj＝Wj-Nk ⊕ Wj-1
当 j 是Nk的整数倍时:
Wj＝Wj-Nk ⊕ByteSub (Rotl ( Wj-1) )⊕ Rcon[j/Nk];
四、AES的解密算法
加密算法不是对合运算：
-1
(AES)≠AES
解密算法的结构与加密算法的结构相同
解密中的变换为加密算法变换的逆变换，且密钥扩展策略稍有不同。
Decryption(State,CipherKey)
{ Inv_KeyExpansion(CipherKey,Inv_ RoundKey); AddRoundKey(State,Inv_ RoundKey); For(I=1;I Inv_Round(State, Inv_ RoundKey); {Inv_ByteSub(State); Inv_ShiftRow(State); Inv_MixColumn(State); AddRoundKey(State, Inv_ RoundKey ；} Inv_FinalRound(State,Inv_RoundKey) { InvByteSub(State); InvShiftRow(State); AddRoundKey(State, Inv_ RoundKey )；} } 五、AES的实现 适应多种环境，高效，方便是AES的突出优点。由于AES的基本运算由ByteSub、MixColumn、ShiftRow和AddRoundKey变换构成，因此AES的实现主要是这些变换的实 现。其中ShiftRow和AddRoundKey的实现比较容易，因此主要是ByteSub和MixColumn变换的实现问题。有了这些基本运算的实现，便可以有效地实现整个AES。 实现方法：软件 硬件 软件方法：基于算法描述；基于查表 1、基于算法描述的软件实现 AES的算法描述是一种程序化的描述，便于实现。 AES的四种基本变换都比较简单，便于实现。 用 C语言仿照算法描述，可方便地实现。 这种实现的速度不是最快的！ 2、基于查表的软件实现 用查表实现算法是一种高效的软件设计方法。 时空折换是信息科学的基本策略。 用查表实现算法，就是用空间换取时间。 目前计算机系统的存储空间大、而且便宜，为查表实现算法提供了物资基础。 ①S盒的实现 实现S盒变换的最快方法是，直接计算出S盒的变换的结果，并存储造表，使用时时直接查表。因为ByteSub变换是字节函数，所以表的规模不大，只含256个元素。 注意：解密时用的是逆S盒，因此共需要造两个S盒表。 六、AES的安全性 能够抵抗目前所有的已知攻击： 穷举攻击。 差分攻击。 线性攻击。 Square攻击。 七、AES的评说 AES体现商农的密码设计理论。 体现了公开设计原则：公开算法 AES代表当今商业密码的最高水平。 大作业 以AES作为加密算法开发出文件加密软件系统： ? 具有文件加密和解密功能； ? 具有加解密速度统计功能； ? 采用密文反馈链接和密文挪用短块处理技术； ? 具有较好的人机界面。 复习题 1、对比AES和DES有什么不同？ 2、AES的解密算法与加密算法有什么不同？ 3、在GF（2）中，01的逆元素是什么？ 4、对于字节“ 00”和“ 01”计算S盒的输出。 4 5、证明c(x)与d(x)互逆，模x+1。 i4i mod 4 6、证明:x mod (x+1)=x 8 第五讲 中国商用密码SMS4 一、我国的密码分级： ①核心密码： 用于保护党、政、军的核心机密。 ②普通密码： 用于保护国家和事企业单位的低于核心机密而高于商业机密的密码信息。 ③商用密码： 用于保护国家和事企业单位的非机密的敏感信息。 ④个人密码： 用于保护个人的隐私信息。 前三种密码均由国家密码管理局统一管理。 二、我国商的业密码政策 ①统一领导： 国家密码管理局统一领导。 ②集中管理： 国家密码管理局办公室集中管理。 ③定点研制： 研制只允许定点单位进行。 ④专控经营： 经许可的单位才能经营。 ⑤满足使用： 国内各单位都可申请使用。 三、我国商用密码概况 ⑴ 密码的公开设计原则 密码的安全应仅依赖于对密钥的保密，不依赖于对算法的保密。 ⑵ 公开设计原则并不要求使用时公开所有的密码算法 核心密码不能公布算法； 核心密码的设计也要遵循公开设计原则。 ⑶ 商用密码应当公开算法 ①美国DES开创了公开商用密码算法的先例； ②美国经历DES（公开）→EES（保密）→AES（公开）。 ③欧洲也公布商用密码算法 ⑷我国的商用 密码概况 ●我国在密码技术方面具有优势： 密码理论、密码分析 ●长期以来不公开密码算法，只提供密码芯片 少数专家设计，难免有疏漏； 难于标准化，不利于推广应用。 ●2006年2月我国公布了部分商用密码算法； ☆商用密码管理更科学化、与国际接轨； ☆将促进我国商用密码的发展。 四、我国商用密码SMS4 ①分组密码： 数据分组长度=128位、密钥长度=128位 数据处理单位：字节（ 8位），字（32位） ②密码算法结构： 基本轮函数加迭代 对合运算：解密算法与加密算法相同 五、SMS4 密码算法 1、基本运算： ① 模2加：⊕，32 比特异或运算 ② 循环移位：<<< i ，把32位字循环左移i 位 2、基本密码部件： ① 非线性字节变换部件S盒： ☆ 8位输入、8位输出。 ☆本质上， 8位的非线性置换。 ☆设输入位a，输出位b，表示为： b=S_Box（a） S盒中数据为16进制数 ☆S盒的置换规则：以输入的前半字节为行号，后半字节为列号，行列交叉点处的数据即为输出。 举例：设输入为“ef ”，则行号为e，列号为f ，于是S 盒的输出值为表中第e 行和第f 列交叉点的值， Sbox(‘ef’)= ‘84’。 ②非线性字变换?：32位字的非线性变换 ▼4个S盒并行置换； ▼设输入字A=(a0,a1,a2,a3),输出字B=(b0,b1,b2,b3), B= ?(A)=(S_box(a0), S_box(a1), S_box(a2), S_box(a3)) ③字线性部件L变换： ☆ 32位输入、32位输出。 ☆设输入位B，输出位C，表为： C=L（B） ☆运算规则： C=L（B） =B⊕(B<<<2)⊕(B<<<10)⊕(B<<<18) ⊕(B<<<24) ④字合成变换T： ☆由非线性变换τ 和线性变换L 复合而成； ☆ T(X)=L(τ(X))。先S盒变换，再L变换。 3、轮函数F： ☆输入数据：（X0，X1，X2，X3），128位，四个32位字。 ☆输入轮密钥：rk ，32位字。 ☆输出数据：32位字。 ☆轮函数F ： F（X0，X1，X2，X3，rk） = X0 ⊕T（ X1⊕ X2⊕ X3⊕rk) 4、加密算法： 输入明文：（X0，X1，X2，X3），128位，四个字。 输入轮密钥：rki ，i=0,1,…,31，32个字。 输出密文：（Y0，Y1，Y2，Y3），128位，四个字。 算法结构：轮函数的32轮迭代，每轮使用一个轮密钥。 加密算法 ： Xi+4=F（Xi，Xi+1，Xi+2，Xi+3，rki） = Xi ⊕T（ Xi+1⊕ Xi+2⊕ Xi+3⊕rki)， i=0,1…31 （Y0，Y1，Y2，Y3）=（X35，X34，X33，X32） 5、解密算法： 输入密文：（X0，X1，X2，X3） 输入轮密钥：rki ，i=31,30，…,1，0 输出明文：（Y0，Y1，Y2，Y3） 算法：轮函数的32轮迭代，每轮使用一个轮密钥。 解密算法 ： Xi+4=F（Xi，Xi+1，Xi+2，Xi+3，rki） = Xi ⊕T（ Xi+1⊕ Xi+2⊕ Xi+3⊕rki), i=31,…1,0 （Y0，Y1，Y2，Y3）=（X35，X34，X33，X32） 6、密钥扩展算法： ①常数FK 在密钥扩展中使用一些常数 FK0=(A3B1BAC6)，FK1=(56AA3350)，FK2=(677D9197 )， FK3=(B27022DC)。 ②固定参数CK 32 个固定参数Cki，i=0,1,2…31 00070e15, 1c232a31, 383f464d, 545b6269, 70777e85, 8c939aa1, a8afb6bd, c4cbd2d9, e0e7eef5, fc030a11, 181f262d, 343b4249, 50575e65, 6c737a81, 888f969d, a4abb2b9, c0c7ced5, dce3eaf1, f8ff060d, 141b2229, 30373e45, 4c535a61, 686f767d, 848b9299, a0a7aeb5, bcc3cad1, d8dfe6ed, f4fb0209, 10171e25, 2c333a41, 484f565d, 646b7279 产生规则：Ckij= (4i+j)×7（mod 256） ，i=0,1,2…31,j=0,1,…3 。 输入加密密钥：MK=（MK0，MK1，MK2，MK3） 输出轮密钥：rki ，i=0，1…,30，31 中间数据：Ki，i=0，1…,34，35 密钥扩展算法： ① (K0,K1,K2,K3)=(MK0⊕FK0,MK1⊕FK1,MK2⊕FK2,MK3⊕FK3) ② For i=0，1…,30，31 Do iki= Ki+4= Ki⊕T’(Ki+1 ⊕Ki+2 ⊕ Ki+3 ⊕ CKi) 说明：T’ 变换与加密算法轮函数中的T 基本相同，只将其中的线性变换L 修改为以下：L’ L’ (B)=B⊕(B<<< 13)⊕(B<<< 23) 7、实例： 明文: 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10 密钥: 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10 密文: 68 1e df 34 d2 06 96 5e 86 b3 e9 4f 53 6e 42 46 8、安全性 ①国家专业机构设计。算法简洁，以字和字节为处理单位，对合运算，符合当今分组密码主流。 ②专业机构进行了密码分析，因此是安全的。 ③民间学者对21轮SMS4进行了差分密码分析。 ④尚需经过实践检验。 练习题 1、分析SMS4在密码结构上与DES和AES有何异同？ 2、编程研究SMS4的S盒的以下特性： ①输入改变1位，输出平均改变多少位？ ②对于一个输入，连续施加S盒变换，变换多少次时出现输出等于输入？ 3、我国公布商用密码算法有何意义？ 大作业 以SMS4作为加密算法开发出文件加密软件系统： ? 具有文件加密和解密功能； ? 具有加解密速度统计功能； ? 采用密文反馈链接和密文挪用短块处理技术； ? 具有较好的人机界面。 第六讲分组密码的应用技术 一、计算机数据的特殊性 1、存在明显的数据模式： 许多数据都具有某种固有的模式。这主要是由数据冗余和数据结构引起的。 各种计算机语言的语句和指令都十分有限，因而在程序中便表现为少量的语句和指令的大量重复。 各种语言程序往往具有某种固定格式。 数据库的记录也往往具有某种固定结构。 操作系统和网络也有同样的问题。 根据明文相同、密钥相同，则密文相同的道理，这些固有的数据模式将在密文中表现出来。 掩盖明文数据模式的方法： 预处理技术(随机掩盖) 链接技术 如果不能掩盖数据模式，既使采用安全的密码算法也是徒劳的。 二、分组密码的工作模式 1977年DES颁布。1981年美国针对DES的应用制定了四种基本工作模式： 电码本模式（ECB） 密文反馈链接模式（CBC） 密码反馈模式（CFB） 输出反馈模式（OFB） 2000年美国在征集AES的同时又公开征集AES的工作模式。共征集到 15个候选工作模式。新的工作模式标准还在评审中。这些新的工作模式将为AES的应用作出贡献。 1、电码本模式（ECB） 直接利用分组密码对明文的各分组进行加密。 设 明文M=（M1 ，M2 ，…，Mn ）, 密钥为K， 密文C＝ ( C1 ，C2 ，…，Cn ), 其中 Ci ＝E（Mi，K）, i=1,2,…,n 电码本方式是分组密码的基本工作模式。 缺点：可能出现短块，这时需要特殊处理。 缺点：暴露明文的数据模式。 应用：适合加密密钥等短数据 2、密文反馈链接模式（CBC） ①明密文链接方式（Plaintext and Ciphertext Block Chaining） 设明文 M=（M1 ，M2 ，…，Mn ）, 密钥为K， 密文 C = ( C1 ，C2 ，…，Cn ), 其中 E（Mi ⊕Z ，K）， i=1 E（Mi ⊕Mi-1 ⊕Ci-1，K）, i=2,…,n Z为初始化向量。 即使Mi ＝Mj ，但因一般都有Mi-1 ⊕Ci-1 ≠Mj-1 ⊕Cj-1 ，从而使Ci ≠Cj ，从而掩盖了明文中的数据模式。加密时，当Mi 或Ci 中发生一位错误时，自此以后的密文全都发生错误。这种现象称为错误传播无界。解密时也是错误传播无界。 2、密文反馈链接模式（CBC） ①明密文链接方式 错误传播无界的缺点：当磁盘发生一点损坏时将导致整个文件无法解密。 错误传播无界的优点：可用于数据完整性、真实性认证。 明密文链接方式具有加解密错误传播无界的特性，而磁盘文件加密和通信加密通常希望解密错误传播有界，这时可采用密文链接方式。 ②密文链接方式（ Ciphertext Block Chaining） 设明文 M=（M1 ，M2 ，…，Mn ）, 密钥为K， 密文 C = ( C1 ，C2 ，…，Cn ), 其中 E（ Mi ⊕ Z ，K）， i=1 E（Mi ⊕Ci-1，K）, i=2,…,n 加密：错误传播无界 解密时：错误传播有界 D（Ci ，K）⊕Z ， i=1 D（Ci ，K）⊕Ci-1 , i=2,…,n Ci-1 发生了错误，则只影响Mi-1 和Mi 发生错误，其余不错，因此错误传播有界。 缺点也是要求数据的长度是密码分组长度的整数倍，否则最后一个数据块将是短块。 3、输出反馈模式 (OFB) 将一个分组密码转换为一个密钥序列产生器。从而可以实现用分组密码按流密码的方式进行加解密。 如果分组密码是安全的，则产生的密钥序列也是安全的。 加解密都没有错误传播。 适于加密冗余度较大的数据，如语音和图象数据。 为了提高速度可输出最右边的 8位。 但因无错误传播而对密文的篡改难以检测。 4、密码反馈模式 CFB（Cipher Feedback） CFB模式也是用分组密码产生密钥序列。 与OFB的不同是，把密文反馈到移位寄存器。 加密时若明文错了一位，则影响相应的密文错，这一错误反馈到移位寄存器后将影响到后续的密钥序列错，导致后续的密文都错。 解密时若密文错了一位，则影响相应的明文错，但密文的这一错误反馈到移位寄存器后将影响到后续的密钥序列错，导致后续的明文都错。 因错误传播无界，可用于检查发现对明密文的篡改。 5、X CBC (Extended Cipher Block Chaining Encryption)模式 2000年美国学者John Black和Phllip Rogaway提出X CBC模式，作为CBC模式的扩展，被美国政府采纳作为标准。X CBC主要是解决了CBC要求明文数据的长度是密码分组长度的整数倍的限制，可以处理任意长的数据。如果用分组密码是安全的，则密钥序列就是安全的。 设明文M=（M1 ，M2 ，…，Mn-1，Mn ），相应的密文C=( C1 ，C2 ，…，Cn－1，Cn )，而Mn 可能是短块。 使用3个密钥 K1，K2，K3进行加密。 使用填充函数 Pad（X）对短块数据进行填充。 填充函数Pad（X）定义如下： X， 当X不是短块； X10…0， 当X是短块。 经填充函数 Pad（X）填充后的数据块一定是标准块。 令Z＝0，以Z作为初始化向量。加密过程如下： E（Mi ⊕Z ，K1），i=1 E（Mi ⊕Ci-1，K1）, i=2,…,n－1 E（Mn ⊕Cn -1 ⊕K2，K1）， 当Mn 不是短块； E（PAD（Mn）⊕Cn -1 ⊕K3，K1），当Mn是短块。 X CBC与CBC区别： CBC要求最后一个数据块是标准块，不是短块。 X CBC既允许最后一个数据块是标准块，也允许是短块。最后一个数据块的加密方法 与 CBC不同。因为有填充，需要传输填充长度信息。 X CBC模式的主要优点： 可以处理任意长度的数据。 适于计算产生检测数据完整性的消息认证码MAC。 6、CTR（Counter Mode Encryption）模式 CTR模式是Diffie和Hellman于1979年提出的，在征集AES工作模式的活动中由California大学的Phillip Rogaway等人的推荐。 设T1，T2 ，…，Tn-1，Tn 是一给定的计数序列，M1，M2，…，Mn-1，Mn 是明文，其中M1，M2，…，Mn-1是标准块，Mn 的可能是标准块，也可能是短块。设其长度等于u，u小于等于分组长度。 CTR的工作模式的加密过程如下： Oi＝E（Ti，K），i=1,2,…,n. Ci＝Mi⊕Oi ，i=1,2,…,n-1. Cn＝Mn⊕MSBu（On）. 其中MSBu（On）表示On 中的高u位。 CTR的工作模式的解密过程如下： Oi＝E（Ti，K），i=1,2,…,n. Mi＝Ci⊕Oi ，i=1,2,…,n-1. Mn＝Cn⊕MSBu（On）. CTR的工作模式的优点： CTR模式的优点是安全、高效、可并行、适合任意长度的数据； Oi的计算可预处理高速进行； 加解密过程仅涉及加密运算，不涉及解密运算，因此不用实现解密算法。 适合随机存储数据的解密。 CTR模式的缺点是没有错误传播，因此不易确保数据完整性。 三、短块加密 分组密码一次只能对一个固定长度的明文（密文）块进行加（解）密。 称长度小于分组长度的数据块为短块。 必须采用合适的技术解决短块加密问题。 短块处理技术： 1、填充技术 2、密文挪用技术 3、序列加密 1、填充技术 用无用的数据填充短块，使之成为标准块。 为了确保加密强度，填充数据应是随机的。 但是收信者如何知道哪些数字是填充的呢？这就需要增加指示信息，通常用最后8位作为填充指示符。 填充法适于通信加密而不适于文件和数据库加密。 2、密文挪用技术 密文挪用法也需要指示挪用位数的指示符，否则收信者不知道挪用了多少位，从而不能正确解密。 密文挪用加密短块的优点是不引起数据扩展。 缺点是解密时要先解密Cn 、还原挪用后再解密Cn-1 ，从而使控制复杂。 3、序列加密 对于最后一块短块数据，直接使用密钥K与短块数据模2相加。 序列加密方法的优点是简单。 但是如果短块太短，则加密强度不高。 大作业 以DES、AES或SMS4作为加密算法开发出文件加密软件系统： ? 具有文件加密和解密功能； ? 具有加解密速度统计功能； ? 采用密文反馈链接和密文挪用短块处理技术； ? 具有较好的人机界面。 复习题 ① 计算机数据加密有些什么特殊问题？ ② 分析CBC和X CBC工作模式的加解密错误传播情况。 ③ 为什么说填充法不适合计算机文件和数据库加密应用？ ④ 密文挪用方法有什么优缺点？ 第七讲 序列密码 一、序列密码的基本概念 ①明文、密文、密钥以位（字符）为单位加解密； ②模型 ③人们用序列密码模仿 “一次一密 ” 密码； ④加密运算最简单，而且是对合运算； ⑤安全取决于密钥序列产生算法； ⑥理论和技术都十分成熟； ⑦核心密码的主流密码。 1、序列密码的分类 ①同步序列密码（Synchronous Stream Cipher） 密钥序列产生算法与明文无关，所产生的密钥序列也与明文无关。 在通信过程中，通信的双方必须保持精确的同步，收方才能正确解密，如果失步收方将不能正确解密。例如，如果通信中丢失或增加了一个密文字符，则收方的解密将一直错误。 设密文失步 c = c1, c3, c4, … cn-1, cn （ c2 丢失） ⊕ k= k1, k2, k3, … kn-1, kn （密钥正确） m=m1,×, ×, … ×, × （ m1 后的明文全错） 对失步的敏感性，使我们能够容易检测插入、删除、重播等主动攻击。 另一个优点是没有错误传播，当通信中某些密文字符产生了错误（不是插入和删除），只影响相应字符的解密，不影响其它字符。 注意：错误与失步是不同的概念！ 设密文错误 c = c1, c2, c3, … cn-1, cn （ c2 错） ⊕ k= k1, k2, k3, … kn-1, kn （密钥正确） m=m1,×, m3, … mn-1, mn （仅 m2 错） ②自同步序列密码（ Self- Synchronous Stream Cipher） 密钥序列产生算法与明文（密文）相关，则所产生的密钥序列与明文（密文）相关。 设密钥序列产生器具有 n位存储，则加密时一位密文错误将影响后面连续 n个密文错误。在此之后恢复正确。 解密时一位密文错误也将影响后面连续 n个明文错。在此之后恢复正确。 加解密会造成错误传播。在错误过去之后恢复正确。 二、线性移位寄存器序列密码 1、线性移位寄存器（Linear Sift Registor） s0 ，s1 ，...，sn-1 组成左移移位寄存器，并称每一时刻移位寄存器的取值为一个状态。移位寄存器的输出同时要送入sn-1，其值要通过函数 F(s0 ,s1 ,...,sn-1 )计算产生。称函数 F(s0 ,s1 ,...,sn-1 )为反馈函数。如果反馈函数 F(s0 ,s1 ,...,sn-1 )是s0 ,s1 ,...,sn-1 的线性函数，则称为线性移位寄存器，否则称为非线性移位寄存器。设F(s0,s1 ,...,sn-1 )为线性函数，则可写成 F(s0,s1,...,sn-1)=g0s0+g1s1+,...,+gn-1sn-1其中，g0,g1 ,...,gn-1为反馈系数。 在二进制的情况下，式中的+即为⊕，反馈系数gi ∈GF(2 )，如果gi=0，则表示式中的gisi 项不存在，因此表示si不连接 。同理，gi=1表示si连接。故 gi的作用相当于一个开关。形式地，用xi与si 相对应，则根据反馈函数可导出一个文字x的多项式： g(x)= gn x n +gn-1 x n-1 +,...,+g1x +g0 称g(x) 为线性移位寄存器的连接多项式。与图对照可知，gn=g0 =1。否则，若gn=0则输出不反馈到sn -1，若g1=0则s0不起作用，应将其去掉。n级线性移位寄存器最多有2n个不同的状态。若其初始状态为零，则其后续状态恒为零。若其初始状态不为零，则其后续状态也不为零。因此，n级线性移位寄存器的状态周期≤2n –1，其输出序列的周期≤2n –1。只要选择合适的连接多项式便可使线性移位寄存器的输出序列周期达到最大值2n –1，并称此时的输出序列为最大长度线性移位寄存器输出序列，简称为m序列。仅当连接多项式g(x)为本原多项式时，其线性移位寄存器的输出序列为m序列。设f(x)为GF（2）上的多项式，使f(x)| x p－1的最小正整数p称为f(x)的周期。如果f(x)的次数为n，且其周期为2 n－1，则称f(x)为本原多项式。已经证明，对于任意的正整数n，至少存在一个n次本原多项式。而且有有效的产生算法。 举例：设g(x)=x4 +x +1， g(x)为本原多项式，以其为连接多项式的线性移位寄存器的输出序列为100110101111000··· ，它是周期为2 4-1=15的m序列。 m序列具有良好的随机性： 游程：称序列中连续的i个1为长度等于i的1游程，同样，称序列中连续的i个0为长度等于i的0游程。 ①在一个周期内，0和 1出现的次数接近相等，即0出现的次数为2 n - 1 -1，1出现的次数为2 n-1 ； 。 ②将序列的一个周期首尾相接，其游程总数N=2 n-1 ③其中1游程和0游程的数目各占一半。当n>2时，游程分布如下（1≤i≤n-2）： 长为i的1游程有N/2 i+1个； 长为i的0游程有N/2 i+1个； 长为n-1的0游程有1个； 长为n的1游程有1个. ④自相关函数反映一个周期内平均每位的相同程度。 2、线性移位寄存器序列密码 m序列具有良好的随机性； 50年代开始用作密钥序列，并用于军用。 60年代发现其是不安全的。 设m序列线性移位寄存器的状态为 S=（s0,s1 ,...,sn-1）T， ， 下一状态为S’=（s’0,s’1 ,...,s’n-1）T 其中 s’0 = s1 s’1 = s2 ... s’n-2= sn-1 s’n-1= g0s0+g1s1+,...,+gn-1sn-1 写成矩阵形式：S’=HS mod 2 0 1 0 ...0 s’0 s0 0 0 1 ...0 s’1 s1 0 0 0 ...0 0 0 0 ...1 g0 g1...gn-1 s’n-1 sn-1 矩阵H称为连接多项式的伴侣矩阵。 进一步假设攻击者知道了一段长2n位的明密文对，即已知： M= m1,m2 ,...,m2n C= c1,c2 ,...,c2n 于是可求出一段长2n位的密钥序列， K= k1 ,k2,...,k2n， 其中 ki= mi⊕ci = mi ⊕(mi⊕ki)。 由此可以推出线性移位寄存器连续 n+1个状态： S1 =（k1,k2 ,...,kn）T S2 =（k2,k3 ,...,kn+1）T … Sn+1 =（kn+1,kn+2 ,...,k2n）T 作矩阵 X =（S1,S2 ,...,Sn）T Y =（S2,S3 ,...,Sn+1）T 根据S’=HS mod 2，有 S2=HS1 S3=HS2 ... Sn+1=HSn 于是， Y=HX mod 2 因为m序列的线性移位寄存器连续 n个状态向量彼此线性无关，因此X矩阵为满秩矩阵，故存在逆矩阵X -1，于是 H=YX -1 mod 2 求出H矩阵，便确定出连接多项式g(x)，从而完全确定线性移位寄存器的结构。 例：m序列 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 连续4个状态 1001，0011，0110，1101线性无关 求逆矩阵X -1的计算复杂度为O（n 3）。一般，对于n=1000的线性移位寄存器序列密码，用每秒100万次的计算机，一天之内便可破译。 三、非线性序列密码 线性移位寄存器序列密码在已知明文攻击下是可破译的，可破译的根本原因在于线性移位寄存器序列是线性的，这一事实促使人们向非线性领域探索。目前研究得比较充分的方法： ①非线性移位寄存器序列 ②对线性移位寄存器序列进行非线性组合 ③利用非线性分组码产生非线性序列 ①非线性移位寄存器序列 令反馈函数f(s0,s1 ,...,sn-1 )为非线性函数便构成非线性移位寄存器，其输出序列为非线性序列。称输出序列的周期达到最大值2n的非线性移位寄存器序列为M序列。M序列的0，1分布和游分布是均匀的，而且周期最大。非线性移位寄存器反馈函数的数量极大。GF（2）上的n级移位寄存器共有 2 n个状态，因此共有？种不同的反馈函数，其中线性反馈函数只有 2n-1种，其余均为非线性。显然，非线性移位寄存器的空间极大！ 例：令n=3，f(s0,s1,s2)=s0⊕s2⊕1⊕s1? s2，由于与运算为非线性运算，故反馈函数为非线性反馈函数，其输出序列为10110100...，为M 序列。 ②对线性移位寄存器序列进行非线性组合 非线性移位寄存器序列的研究比较困难，但人们对线性移位寄存器序列的研究却比较充分和深入。于是人们想到，利用线性移位寄存器序列设计容易、随机性好等优点，对一个或多个线性移位寄存器序列进行非线性组合可以获得良好的非线性序列。在这里用线性移位寄存器作为驱动源来驱动非线性电路产生非线性序列。其中用线性移位寄存器序列来确保所产生序列的长周期和均匀性，用非非线性电路来确保输出序列的非线性和其它密码性质。通常称这里的非线性电路为前馈电路，称这种输出序列为前馈序列。 对多个LSR进行非线性组合 四、RC4序列密码 RC4序列密码是美国RSA数据安全公司设计的一种序列密码。RSA数据安全公司将其收集在加密工具软件BSAFE中。最初并没有公布RC4的算法。人们通过对软件进行逆向分析得到了算法。在这种情况下RSA数据安全公司于1997年公布了RC4密码算法。密钥40位的RC4，通过Internet 32小时攻破。 RC4密码与基于移位寄存器的序列密码不同。它是一种基于非线性数据表变换的序列密码。 它以一个足够大的数据表为基础，对表进行非线性变换，产生非线性的密钥序列。RC4使用256个字节的S表和两个指针（I 和J）。S表的值S0,S1,…，S255是0,1,…，255的一个排列。I和J的初值为0。我们把RC4算法看成一个有限状态自动机。把S表和I、J指针的具体取值称为RC4的一个状态： T=< S0 ,S1，…，S255 ,I,J> 对状态T进行非线性变换，产生出新的状态 ，并输出密钥序列中一个字节k 。 RC4的下一状态函数定义如下： ⑴ I＝0，J＝0; ⑵ I= I+1 mod 256; ⑶ J=J+S[I] mod 256; ⑷ 交换S[I]和S[J] 。 RC4的输出函数定义如下： ⑴ h= S[I] + S[J] mod 256; ⑵ k = S[h] 。 在用RC4加解密之前，应当首先对S表初始化。初始化的过程如下： ⑴ 对S表进行线性填充，即令 S[0]＝0，S[1]＝1，S[2]＝2，…，S[255] ＝255； ⑵ 用密钥填充另一个256字节的R表R[0],R[1],…，R[255]，如果密钥的长度小于R表的长度，则依次重复填充，直至将R表填满。 ⑶ J＝0; ⑷ 对于I=0 到255重复以下操作， ① J＝（J+S[I]+R[I]） mod 256; ② 交换S[I]和S[J] 。 注意，对S表初始化的过程实质上是对S表进行随机化处理的过程，只有当这一过程完成后，才能计算产生密钥字符，才能进行加解密，否则将是不安全的。 RC4算法的优点是算法简单，高效，特别适合软件实现。 RC4是目前应用最广的商密级序列密码。 复习题 ①设g(x)=x4 +x3 +1， g(x)为本原多项式，以其为连接多项式组成线性移位寄存器。画出逻辑图，写出输出序列及状态变迁。 ②令n=3，f(s0,s1,s2)= s0⊕s2⊕1⊕s1 s2，以其为连接多项式组成非线性移位寄存器。画出逻辑图，求出非线性移位寄存器的状态变迁及输出。 ③令n=3，f(s0,s1,s2)=1⊕s0⊕s1⊕s2⊕s0s1⊕s1 s2⊕s2 s3 ，以其为连接多项式组成非线性移位寄存器。画出逻辑图，求出非线性移位寄存器的状态变迁及输出。 ④回答并证明：GF（2）上的 n级移位寄存器共有 2 n个状态，因此共有多少种不同的反馈函数，其中线性反馈函数只有 2n-1种，其余均为非线性。 第八讲 习题课：复习对称密码 要求 ①同学们书面作业为所有奇数号的题目，要交作业。 ② 偶数号的题目中的一部分由辅导老师在作业课上讲解，一部分点学生上台解答。 ③期末验收大作业。 一、复习题 ① 解释信息安全的含义。 ② 密码的基本思想是什么？ ③密码体制分哪些类型？各有什么优缺点？ ④什么是密码分析？密码分析有哪些类型？ ⑤为什么说理论上，任何实用的密码都是可破的？ ⑥计算机的程序文件和数据库文件加密容易受到什么攻击？为什么？ 二、复习题 ① 已知置换如下： 明文＝642135 ,密文＝？ 密文＝214365 ，明文＝？ ②使加法密码算法称为对合运算的密钥k称为对合密钥， 以英文为例求出其对合密钥。 ③ 已知一个加法密码的密文如下： BEEAKFYDJXUQYHYJIQRYHTYJIQFBQDUYJIIKFUHCQD 用穷举法求出明文。 ④以英文为例，用加法密码，取密钥常数 k= 7,对明文 INFORMATION SECURITY，进行加密，求出密文。 ⑤证明，在置换密码中，置换p是对合的，当且仅当对任意的i和j(i, j=1,2,3,…,n)，若p(i)=j，则必有p(j)=i 。 ⑥编程实现Vigenre密码。 ⑦ 分析仿射密码的安全性。 大作业 以3DES作为加密算法开发出文件加密软件系统： ? 具有文件加密和解密功能； ? 具有加解密速度统计功能； ? 采用密文反馈链接和密文挪用短块处理技术； ? 具有较好的人机界面。 三、复习题 ①分析DES的弱密钥和半弱密钥。 ②分析DES的互补对称性。 ③证明DES的可逆性。 ④证明DES的对合性。 ⑤画出3密钥 3DES的框图。 大作业 以AES作为加密算法开发出文件加密软件系统： ? 具有文件加密和解密功能； ? 具有加解密速度统计功能； ? 采用密文反馈链接和密文挪用短块处理技术； ? 具有较好的人机界面 四、复习题 1、对比AES和DES有什么不同？ 2、AES的解密算法与加密算法有什么不同？ 3、在GF（28）中，01的逆元素是什么？ 4、对于字节“ 00”和“ 01”计算S盒的输出。 5、证明c (x)与d (x)互逆，模x4+1。 6、证明:xi mod (x4+1)=xi mod 4 ①复习有限域理论。 ②证明： C(x)=03x3+01x2+01x+02 D(x)=0Bx3+0Dx2+09x+0E 互逆。 ③利用AES的对数表或反对数表计算ByteSub(25)。 ④求出AES的 S盒的逆矩阵。 五、复习题 ① 计算机数据加密有些什么特殊问题？它对加密的安全性有什么影响？ ② 分析ECB、CBC、CFB、OFB、X CBC、CTR工作模式的加解密错误传播情况。 ③ 为什么说填充法不适合计算机文件和数据库加密应用？ ④ 密文挪用方法有什么优缺点？ 六、复习题 ①设g(x)=x4 +x3 +1， g(x)为本原多项式，以其为连接多项式组成线性移位寄存器。画出逻辑图，写出输出序列及状态变迁。 ②令n =3，f(s0,s1,s2)= s0⊕s2⊕1⊕s1 s2，以其为连接多项式组成非线性移位寄存器。画出逻辑图，求出非线性移位寄存器的状态变迁及输出。 ③令n =3，f(s0,s1,s2)=1⊕s0⊕s1⊕s2⊕s0s1⊕s1 s2⊕s2 s3 ，以其为连接多项式组成非线性移位寄存器。画出逻辑图，求出非线性移位寄存器的状态变迁及输出。 ④证明：GF（2）上的 n级移位寄存器共有2n个状态，因此共有2种不同的反馈函数，其中 线性反馈函数只有 2n-1种，其余均为非线性。 七、复习题 1、分析SMS4在密码结构上与DES和AES有何异同？ 2、编程研究SMS4的S盒的以下特性： ①输入改变1位，输出平均改变多少位？ ②对于一个输入，连续施加S盒变换，变换多少次时出现输出等于输入？ 3、我国公布商用密码算法有何意义？ 大作业 以SMS4作为加密算法开发出文件加密软件系统： ? 具有文件加密和解密功能； ? 具有加解密速度统计功能； ? 采用密文反馈链接和密文挪用短块处理技术； ? 具有较好的人机界面。 2n第九讲 公开密钥密码 一、公开密钥密码体制的基本思想 1、传统密码的缺点： ①收发双方持有相同密钥，密钥分配困难，网络环境更突出。 ②不能方便地实现数字签名，商业等应用不方便。 2、公开密钥密码的基本思想： ①将密钥 K一分为二，一个专门加密，一个专门解密： Ke ≠ Kd ②且由Ke 不能计算出 Kd ，于是可将Ke公开，使密钥分配简单。 ③由于Ke ≠ Kd且由Ke 不能计算出 Kd ，所以 Kd 便成为用户的指纹，于是可方便地实现数字签名。 3、公开密钥密码的基本条件： ①E和 D互逆； 基本条件，保密条件 D（E（M））＝M ② Ke ≠ Kd且由Ke 不能计算出 Kd ；安全条件 ③E和 D都高效。 实用条件 ④E（D（M））＝M 保真条件 如果满足① ② ③可保密，如果满足② ③ ④可保真，如果4个条件都满足，可同时保密保真。 二、公开密钥密码的基本工作方式 ? 设 M为明文，C为密文，E为公开密钥密码的加密算法，D为解密算法，Ke为公开 的加密钥，Kd为保密的解密钥，每个用户都分配一对密钥，而且将所有用户的公开的加密钥Ke存入共享的密钥库PKDB。 1、确保数据秘密性：A B 发方： ①A首先查PKDB，查到B的公开的加密钥KeB 。 ②A用KeB 加密M得到密文C： C=E（M，KeB） ③A发C给B。 收方： ①B接受C。 ②B用自己的KdB解密，得到明文M=D(C，KdB)。 安全性分析： ①只有B才有KdB ，因此只有B才能解密，所以确保了秘密性。 ②任何人都可查PKDB得到A的KeA，所以任何人都可冒充A给B发送数据。不能确保真实性。 2、确保数据真实性：A发送给B消息M。 发方： ①A首先用自己的KdA对M解密，得到C=D(M，KdA)。 ② A发C给B。 收方： ①B接受C。 ②B查PKDB查到A的公开的加密钥KeA 。 ③B用KeA加密C，得到明文M=E（C，KeA）。 2、确保数据秘密性： 安全性分析： ①只有A才有KdA ，因此只有A才能解密产生C，所以确保了真实性。 ②任何人都可查PKDB得到A的KeA，所以任何人都可加密得到明文。不能确保秘密性。 3、同时确保数据秘密性和真实性：A发送给B消息M。 发方： ① A首先用自己的KdA对M解密，得到S： S=D(M，KdA) ② 查PKDB，查到B的公开的加密钥KeB 。 ③ 用KeB 加密S得到C： C=E（S，KeB） ④A发C给B。 3、同时确保数据秘密性和真实性： 收方： ①B接受C。 ②B用自己的KdB解密C，得到S： S=D（C，KdB） ③B查PKDB查到A的公开的加密钥KeA。 ④B用A的公开的加密钥KeA 加密S，得到M： M=E（S，KeA） 安全性分析： ①只有A才有KdA ，因此只有A才能解密产生S，所以确保了真实性。 ②只有B才有KdB ，因此只有B才能获得明文，所以确保了秘密性。 三、RSA公开密钥密码 ? 1978年美国麻省理工学院的三名密码学者R.L.Rivest,A.Shamir和L.Adleman提出了 一种基于大合数因子分解困难性的公开密钥密码，简称为RSA密码。 ? RSA密码被誉为是一种风格幽雅的公开密钥密码。既可用于加密，又可用于数字签 名，安全、易懂。 ? RSA密码已成为目前应用最广泛的公开密钥密码。 1、加解密算法 ①随机地选择两个大素数 p和 q，而且保密； ②计算n=pq，将 n公开； ③计算φ(n)=(p-1)(q-1)，对φ(n)保密； ④随机地选取一个正整数e，1 ① E和D的可逆性 要证明：D(E(M))=M M＝Cd ＝(Me)d＝Med mod n 因为ed＝1 modφ(n)，这说明ed＝tφ(n)+1,其中t为某整数。所以， φ Med ＝Mt(n)+1 mod n 。 因此要证明 Med ＝M mod n ，只需证明 φ M t(n)+1 ＝M mod n 。 ① E和D的可逆性 在（M，n）＝1的情况下，根据数论(Euler定理)， φ M t(n) ＝1 mod n ， 于是有， φ M t(n)+1 ＝M mod n 。 在（M，n）≠1的情况下，分两种情况： 第一种情况：M∈{1,2,3,…,n-1} 因为n=pq，p和q为素数， M∈{1,2,3,…,n-1}，且（M，n）≠1 。 这说明M必含p或q之一为其因子，而且不能同时包含两者，否则将有M≥n，与M∈{1,2,3,…,n-1}矛盾。 不妨设M＝ap 。 φ 又因q为素数，且M不包含q，故有（M，q）＝1， 于是有，M (q) ＝1 mod q 。 φ 进一步有，M t(p-1)(q) ＝1 mod q。 因为q是素数，φ(q)＝（q-1），所以t(p-1)φ(q)＝tφ(n)，所以有 φ M t(n) ＝1 mod q。 φ 于是，M t(n) ＝bq+1，其中b为某整数。 两边同乘M， φ M t(n)+1 ＝bqM+M 。 因为M＝ap，故 φ M t(n)+1 ＝bqap+M =abn+M 。 取模n得， φ M (n)+1 ＝M mod n 。 在（M，n）≠1的情况下，分两种情况： 第二种情况：M＝0 当M＝0时，直接验证，可知命题成立。 ②加密和解密运算的可交换性 D(E(M))=(Me)d =Med =(Md))e =E(D(M)) mod n 所以，RSA密码可同时确保数据的秘密性和数据的真实性。 ③加解密算法的有效性 RSA密码的加解密运算是模幂运算，有比较有效的算法。 ④在计算上由公开密钥不能求出解密钥 小合数的因子分解是容易的，然而大合数的因子分解却是十分困难的。关于大合数的因子分解的时间复杂度下限目前尚没有一般的结果，迄今为止的各种因子分解算法提示人们这 ） 一时间下限将不低于O（EXP（lnNlnlnN）1/2。根据这一结论，只要合数足够大，进行因子分解是相当困难的。 假设截获密文C，从中求出明文M。他知道 M≡Cd mod n ， 因为n是公开的，要从C中求出明文M，必须先求出d，而d是保密的。但他知道， ed≡1 mod φ(n)， e是公开的，要从中求出d，必须先求出φ(n)，而φ(n)是保密的。 但他又知道， φ(n)=(p-1)(q-1)， 要从中求出φ(n)，必须先求出p和q，而p和q是保密的。但他知道， n=pq， 要从n求出p和q，只有对n进行因子分解。而当n足够大时，这是很困难的。 只要能对n进行因子分解，便可攻破RSA密码。由此可以得出，破译RSA密码的困难性≤对n因子分解的困难性。目前尚不能证明两者是否能确切相等，因为不能确知除了对n进行因子分解的方法外，是否还有别的更简捷的破译方法。 目前只有Rabin密码具有： 破译Rabin密码的困难性=对n因子分解的困难性。 1、参数选择 为了确保RSA密码的安全，必须认真选择密码参数： ① p和q要足够大； 一般应用：p和q应 512 b 重要应用：p和q应 1024 b ②p和q应为强素数 文献指出，只要(p-1)、(p+1)、(q-1)、(q+1)四个数之一只有小的素因子，n就容易分解。 ③ p和q的差要大； ④（p-1）和（q-1）的最大公因子要小。 如果（ p-1）和（q-1）的最大公因子太大，则易受迭代加密攻击。 ⑤ e的选择 随机且含1多就安全，但加密速度慢。于是，有的学者建议取e＝216+1＝65537 ⑥ d的选择 d不能太小，要足够大 ⑦ 不要许多用户共用一个模 n；易受共模攻击 ①概率产生 目前最常用的概率性算法是Miller检验算法。Miller检验算法已经成为美国的国家标准。 ②确定性产生 ? 确定性测试 ? 确定性构造 3、大素数的运算 ①快速乘方算法 ? 反复平方乘算法： 设e的二进制表示为 e＝ek-1 2k-1 + ek-2 2k-2 +...,+ e1 21 + e0 则 Me = ((…(Mek-1)2 Mek-2)2…Me1)2 Me0 mod n ? 设e为k位二进制数，w(e)为e的二进制系数中为1的个数，则最多只需要计算w(e) -1次平方和w(e)次数的模乘。从而大大简化了计算。 ②快速模乘算法 ? 反复平方乘算法解决了快速乘方取模的问题，仍未解决快速模乘的问题； ? Montgomery算法是一种快速模乘的好算法； ? 将以上两种算法结合成为实现RSA密码的有效方法。 ? 硬件协处理器是提高运算效率的有效方法。 ? Montgomery算法的思路： ? 要计算 Y=AB mod n ,因为n很大，取模运算困难，采取一个小的模 R，回避大模的计 算。 ? 利用空间换时间，多用存储空间换取快速。 ? 缺点：不能直接计算出 Y=AB mod n ，只能计算出中间值 ABR-1 mod n ，因此还需要预处理和调整运算。一次性计算Y=AB mod n并不划算。 ? 适合：RSA等密码中多次的模乘计算。 习 题 ①证明RSA密码加解密算法的可逆性 ② 证明RSA密码加解密算法的可交换性 ③ 说明对于RSA密码从公开加密钥不能求出保密的解密钥 ④令p=3,q=11,d=7,m=5,手算密文C 。 ⑤设RSA密码的 e=31,n=35,C=10,手算明文M 。 ⑥设A，B为正整数，D=(A,B)。试证明： ?(AB)=D ?(A) ?(B)/ ?(D) ⑦ RSA密码的快速运算 ? 分析反复平方乘算法的效率 ? 说明 Montgomery算法为什么效率高？它适合哪些情况下应用？ ⑧编程实现RSA密码的加解密运算。 ⑨ 在RSA中使用e=3作为加密指数有和优缺点？使用d=3作解密指数的做法好吗？为什么？ ①证明RSA密码加解密算法的可逆性 ② 证明RSA密码加解密算法的可交换性 ③ 说明对于RSA密码从公开加密钥不能求出保密的解密钥 ④令p=3,q=11,d=7,m=5,手算密文C 。 ⑤设RSA密码的 e=31,n=35,C=10,手算明文M 。 ⑥设A，B为正整数，D=(A,B)。试证明： ?(AB)=D ?(A) ?(B)/ ?(D) ⑦RSA密码的快速运算 ? 分析反复平方乘算法的效率 ? 说明 Montgomery算法为什么效率高？它适合哪些情况下应用？ ⑧编程实现RSA密码的加解密运算。 ⑨在RSA中使用e=3作为加密指数有和优缺点？使用d=3作解密指数的做法好吗？为什么？ 第十讲 公开密钥密码 一、ELGamal公钥密码的基本情况 1、基本情况： ①ELGamal密码是除了RSA密码之外最有代表性的公开密钥密码。 ②RSA密码建立在大合数分解的困难性之上。 ③ELGamal密码建立在离散对数的困难性之上。 2、离散对数问题： ①设p为素数，则模p的剩余构成有限域： Fp={0,1,2,… ,p-1} Fp 的非零元构成循环群Fp* Fp* ={1,2,… ,p-1} ={α，α2，α3，，αp-1}， 则称α为Fp*的生成元或模 p 的本原元。 ②求α的摸幂运算为: y =αx mod p，1≤x≤p-1, 2、离散对数问题： 求对数 X 的运算为 x=logαy，1≤x≤p-1 由于上述运算是定义在模p有限域上的，所以称为离散对数运算。 ③从x计算y是容易的。可是从y计算x就困难得多，利用目前最好的算法，对于小心选择的p将至少需用O(p ?)次以上的运算，只要p足够大，求解离散对数问题是相当困难的。 ? 准备：随机地选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原 元α。将p和α公开。 ⑴ 密钥生成 ? 用户随机地选择一个整数d作为自己的秘密的解密钥，2≤d≤p-2 。 ? 计算y=αd mod p，取y为自己的公开的加密钥。 ? 由公开钥y 计算秘密钥d，必须求解离散对数，而这是极困难的。 ⑵ 加密 ? 将明文消息M（0≤M≤p-1)加密成密文的过程如下： ①随机地选取一个整数k，2≤k≤p-2。 ②计算： U ＝y k mod p； C1＝αk mod p； C2＝UM mod p； ③取 C＝（C1 ，C2）作为的密文。 ⑶ 解密 ? 将密文（C1 ，C2）解密的过程如下： ①计算V＝C1 d mod p； ②计算M＝C2 V -1 mod p。 ? 解密的可还原性可证明如下： C2 V-1 mod p ＝(UM)V-1 mod p ＝UM（C1 d）-1 mod p ＝UM（（αk）d）-1 mod p ＝UM（（αd）k）-1 mod p ＝UM（（y）k）-1 mod p ＝UM（U）-1 mod p ＝M mod p ⑷ 安全性 ? 由于ELGamal密码的安全性建立在GF（p）离散对数的困难性之上，而目前尚无求 解GF（p）离散对数的有效算法，所以在p足够大时ELGamal密码是安全的。 ? 为了安全p应为150位以上的十进制数，而且p-1应有大素因子。 ? 为了安全加密和签名所使用的k必须是一次性的。 ? d和k都不能太小。 ? 如果 k不是一次性的，时间长了就可能被攻击着获得。又因y是公开密钥，攻击者 自然知道。于是攻击者就可以根据U＝y k mod p计算出U，进而利用Euclid算法求 出U1。又因为攻击者可以获得密文C2，于是可根据式C2＝UM mod p通过计算U－1 C2得到明文M。 ? 设用同一个k加密两个不同的明文M和M’，相应的密文为（C1 ，C2）和（C1’， C2’）。因为C2∕C2’＝ M∕M’，如果攻击者知道M，则很容易求出M’。 ⑸ ELGamal密码的应用 ? 由于ELGamal密码的安全性得到世界公认，所以得到广泛的应用。著名的美国数字 签名标准DSS，采用了ELGamal密码的一种变形。 ? 为了适应不同的应用，人们在应用中总结出18种不同的ELGamal密码的变形。 ①加解密速度快 由于实际应用时ELGamal密码运算的素数p比RSA要小，所以ELGamal密码的加解密速度比RSA稍快。 ②随机数源 由ELGamal密码的解密钥d和随机数k都应是高质量的随机数。因此，应用ELGamal密码需要一个好的随机数源，也就是说能够快速地产生高质量的随机数。 ③大素数的选择 为了ELGamal密码的安全，p应为150位（十进制数）以上的大素数，而且p-1应有大素因子。 三、椭圆曲线密码 1、椭圆曲线密码的一般情况 ? 受ELGamal密码启发，在其它离散对数问题难解的群中，同样可以构成ELGamal 密码。于是人们开始寻找其它离散问题难解的群。 ? 研究发现，有限域GF（p）上的椭圆曲线的解点构成交换群，而且离散对数问题是 难解的。于是可在此群上建立ELGamal密码，并称为椭圆曲线密码。 1、椭圆曲线密码的一般情况 ? 椭圆曲线密码已成为除RSA密码之外呼声最高的公钥密码之一。 ? 它密钥短、签名短，软件实现规模小、硬件实现电路省电。 ? 普遍认为，160位长的椭圆曲线密码的安全性相当于1024位的RSA密码，而且运 算速度也较快。 ? 一些国际标准化组织已把椭圆曲线密码作为新的信息安全标准。如，IEEE P1363/D4， ANSI F9.62，ANSI F9.63等标准，分别规范了椭圆曲线密码在Internet协议安全、电子商务、Web服务器、空间通信、移动通信、智能卡等方面的应用。 2、椭圆曲线 设p是大于3的素数，且4a3+27b2 ≠0 mod p ，称 y2 =x3 +ax+b ，a,b∈GF(p) 为GF（p）上的椭圆曲线。 由椭圆曲线可得到一个同余方程： y2 =x3 +ax+b mod p 其解为一个二元组 为了利用解点构成交换群，需要引进一个O元素，并定义如下的加法运算： ①定义单位元 引进一个无穷点O（∞，∞），简记为0，作为0元素。 O（∞，∞）＋O（∞，∞）＝0＋0＝0 。 并定义对于所有的解点P（x ，y）， － P（x ，y）+O＝O+ P（x ，y）＝P（x ，y）。 ②定义逆元素 设P（x1 ，y1）和Q（x2 ，y2）是解点，如果x1=x2 且y1=-y2 ，则 P（x1 ，y1）＋Q（x2 ，y2）＝0 。 这说明任何解点R（x ，y）的逆就是 R（x ，-y）。 注意：规定无穷远点的逆就是其自己。 O（∞，∞）＝-O（∞，∞） ③定义加法 设P(x1，y1)≠Q(x2，y2)，且P和Q不互逆 ，则 P（x1 ，y1）＋Q（x2 ，y2）＝R（x3 ，y3） 。其中 x3 = λ2 - x1 -x2 ， y3 = λ(x1 –x3)- y1 ， λ =（y2 -y1 ）/(x2 - x1 ）。 ? 当P （x1 ，y1） = Q(x2，y2)时 P（x1 ，y1）＋ Q(x2，y2) ＝2 P（x1 ，y1） ＝R（x3 ，y3）。 其中 x3 = λ2 - 2x1 ， y3 =λ(x1 –x3)- y1 ， λ=（3x12 + a）/（2 y1）。 ? 作集合E={全体解点，无穷点O }。 ? 可以验证，如上定义的集合E和加法运算构成加法交换群。 ? 复习：群的定义 ? G是一个非空集，定义了一种运算，且运算是自封闭的； ? 运算满足结合律； ? G中有单位元； ? G中的元素都有逆元； 3、椭圆曲线解点加法运算的几何意义： 设P（x1 ，y1）和Q（x2 ，y2）是椭圆曲线的两个点，则连接P（x1 ，y1）和Q（x2 ，y2）的直线与椭圆曲线的另一交点关于横轴的对称点即为P（x1 ，y1）+Q（x2 ，y2）点。 4、举例： ? 取p=11，椭圆曲线y2=x3 +x+6 。由于p较小，使GF(p)也较小，故可以利用穷举的 方法根据y2=x3 +x+6 mod 11求出所有解点。 ? 复习：平方剩余 设p为素数，如果存在一个正整数x，使得x2=a mod p,则称 a是模p的平方剩余。 ? 根据表可知全部解点集为： (2，4),(2，7),(3，5),(3，6),(5，2), (5，9),(7，2),(7，9),(8，3),(8，8), (10，2),(10，9)。 再加上无穷远点O，共13的点构成一个加法交换群。 ? 由于群的元素个数为13，而13为素数，所以此群是循环群，而且任何一个非O元 素都是生成元。 ? 由于是加法群，n个元素G相加，G+G+...+G ＝ nG 。我们取G ＝（2，7）为生 成元，具体计算加法表如下： 2G=（2，7）+（2，7）=（5，2） ? 因为λ=（3×22+1）（2×7）-1 mod 11 =2×3-1 mod 11=2×4 mod 11=8 。于是， x3 =82-2×2 mod 11=5 ，y3 =8（2-5）-7 mod 11=2。 G ＝（2，7）， 2G ＝（5，2）， 3G ＝（8，3）， 4G ＝（10，2）， 5G ＝（3，6）， 6G ＝（7，9）， 7G ＝（7，2）， 8G ＝（3，5）， 9G ＝（10，9），10G ＝（8，8）， 11G ＝（5，9）， 12G ＝（2，4）， 13G ＝O（ ∞，∞ ）。 ? 除了GF(p)上的椭圆曲线，外还有定义在GF(2m)上的椭圆曲线。这两种椭圆曲线都 可以构成安全的椭圆曲线密码。 ? 在上例中，由于p较小，使GF(p)也较小，故可以利用穷举的方法求出所有解点。 但是，对于一般情况要确切计算椭圆曲线解点数N的准确值比较困难。 ? N满足以下不等式 P+1-2P 1/2≤N≤P+1+2P 1/2 。 5、椭圆曲线密码 ELGamal密码建立在有限域GF（p）的乘法群的离散对数问题的困难性之上。而椭圆曲线密码建立在椭圆曲线群的离散对数问题的困难性之上。两者的主要区别是其离散对数问题所依赖的群不同。因此两者有许多相似之处。 ① 椭圆曲线群上的离散对数问题 在上例中椭圆曲线上的解点所构成的交换群恰好是循环群，但是一般并不一定。于是我们希望从中找出一个循环子群E1 。可以证明当循环子群E1 的阶n是足够大的素数时，这个循环子群中的离散对数问题是困难的。 ① 椭圆曲线群上的离散对数问题 设P和Q是椭圆曲线上的两个解点，t 为一正整数，且1≤t 除了几类特殊的椭圆曲线外，对于一般ECDLP目前尚没有找到有效的求解方法。于是可以在这个循环子群E1中建立任何基于离散对数困难性的密码，并称这个密码为椭圆曲线密码。 ②椭圆曲线密码 T= ? p为大于3素数，p确定了有限域GF（p）； ? 元素a,b∈GF(p),a和b确定了椭圆曲线； ? G为循环子群E1的生成元点，n为素数且为生成元G的阶，G和n确定了循环子群 E1； ? h=|E|/n，并称为余因子，h将交换群E和循环子群联系起来。 密钥： ? 用户的私钥定义为一个随机数d， d∈{1,2,···,n-1}。 ? 用户的公开钥定义为Q点， Q=dG 。 ? 设d为用户私钥，Q为公钥，将Q存入PKDB。 ? 设要加密的明文数据为M，将M划分为一些较小的数据块，M=[m1 ，m2 ，··· ， mt]，其中0≤mi < n 。 加密过程：A把M加密发给B ⑴A查PKDB，查到B的公开密钥QB 。 ⑵A选择一个随机数k，且k∈{1,2,···,n-1}。 ⑶A计算点X1（x1 ，y1）=kG 。 ⑷A计算点X2（x2 ，y2）=kQB ，如果分量x2=O，则转⑵。 ⑸A计算密文 C = mi x2 mod n 。 ⑹A发送加密数据（X1，C）给B。 ? 解密过程： ? 用户B用自己的私钥dB 求出点X2 ： dBX1 = dB（kG） = k(dB G) = k QB = X2（x2 ，y2） ? 对C解密，得到明文mi =C x2 –1 mod n 。 ? 椭圆曲线密码的实现 ? 由于椭圆曲线密码所依据的数学基础比较复杂，从而使得其具体实现也比较困难。 难点： ? 安全椭圆曲线的产生； ? 倍点运算。 四、公钥密码的理论模型 1、单向函数 设函数 y=f(x)，如果满足以下两个条件，则称为单向函数： ? 如果对于给定的 x，要计算出 y很容易； ? 而对于给定的 y，要计算出 x很难。 2、单向函数的应用 ? 安全HASH函数 ? 操作系统口令 3、利用单向函数构造密码 ? 用正变换作加密，加密效率高； ? 用逆变换作解密，安全，敌手不可破译； ? 但是加密后不能还原。 4、单向陷门函数 设函数 y=f(x)，且 f 具有陷门，如果满足以下两个条件，则称为单向陷门函数： ? 如果对于给定的 x，要计算出 y很容易； ? 而对于给定的 y，如果不掌握陷门要计算出 x很难，而如果掌握陷门要计算出 x 就很容易。 5、单向陷门函数的应用 ? 用正变换作加密，加密效率高； ? 用逆变换作解密，安全； ? 把陷门信息作为密钥，且只分配给合法用户。确保合法用户能够方便地解密，而非 法用户不能破译。 6、单向函数的研究现状 ? 理论上：不能证明单向函数一定存在； ? 实际上：只要函数的单向性足够工程应用就行； ? 实际上已找到的单向性足够的函数有： ①合数的因子分解问题 大素数的乘积容易计算（ p?q ? n），而大合数的因子分解困难( n ? p?q)。 ②有限域上的离散对数问题 有限域上大素数的幂乘容易计算（ ab ? c），而对数计算困难( log a c ? b)。 习 题 ①证明椭圆曲线密码的可逆性。 ②为令p=5,求出椭圆曲线 y2=x3+4x+2的全部解点 ③以教材例5-5为例，分别以G=(2,7)和G=(5,2)构造椭圆曲线密码，并设m=3，分别进行加密和解密。 第十一讲 数字签名 一、数字签名的基本概念 ①在人们的工作和生活中，许多事物的处理需要当事者签名。 ②签名起到确认、核准、生效和负责任等多种作用。 ③签名是证明当事者的身份和数据真实性的一种信息。 ④签名可以用不同的形式来表示。 ⑤在传统的以书面文件为基础的事物处理中，采用书面签名的形式： 手签、印章、手印等 ⑥书面签名得到司法部门的支持。 ⑦在以计算机文件为基础的现代事物处理中，应采用电子形式的签名，即数字签名（Digital Signature）。 ⑧数字签名已得到一些国家的法律支持。 ⑨一种完善的签名应满足以下三个条件： ⑴签名者事后不能抵赖自己的签名； ⑵任何其他人不能伪造签名； ⑶如果当事的双方关于签名的真伪发生争执，能够在公正的仲裁者面前通过验证签名来确认其真伪。 ⑩数字签名基于密码技术，其形式是多种多样的： 通用签名、仲裁签名、不可否认签名、盲签名、群签名、门限签名等。 ? 1994年月美国政府正式颁布了美国数字签名标准DSS（Digital Signature Standard）。 ? 1995年我国也制定了自己的数字签名标准（GB15851－1995）。 ? 2004年我国颁布《中华人民共和国电子签名法》 。 二、数字签名的模型 ? 一个数字签名体制包括两个方面的处理： 施加签名和验证签名。 ? 设施加签名的算法为SIG，产生签名的密钥为K，被签名的数据为M，产生的签名 信息为S，则有 SIG (M，K)＝S 。 ? 设验证签名的算法为 VER ，用VER对签名S进行验证，可鉴别 S的真假。即 真，当S＝SIG (M，K)； 假，当S≠SIG (M，K)。 ? 签名函数必须满足以下条件，否则文件内容及签名被篡改或冒充均无法发现： ① 当M’≠M时，有SIG (M’，K) ≠SIG (M，K)。 条件①要求签名S至少和被签名的数据M一样长。当M较长时，应用很不方便。 将条件①改为：虽然当M’≠M时，存在S＝S’，但对于给定的M或S，要找出相应的M’在计算上是不可能的。 ② 签名 S 只能由签名者产生，否则别人便可伪造，于是签名者也就可以抵赖。 ③ 收信者可以验证签名S的真伪。这使得当签名S为假时收信者不致上当。 ④ 签名者也应有办法鉴别收信者所出示的签名是否是自己的签名。这就给签名者以自卫的能力。 三、利用公钥密码实现数字签名 1、一般方法： 对于一个公钥密码，如果满足E（D（M，Kd），Ke）=M，则可确保数据的真实性。 凡是能够确保数据的真实性的公开密钥密码都可用来实现数字签名，例如RSA密码、ELGamal密码、椭圆曲线密码ECC等都可以实现数字签名。 为了实现数字签名，应成立管理机构； 制定规章制度， 统一技术问题， 用户登记注册， 纠纷的仲裁等。 签名通信协议： A B ① A用自己的解密钥 KdA对数据 M进行签名： SA =D（M，KdA） ②如果不需要保密，则 A直接将 SA 发送给用户B。 ③如果需要保密，则A查到B的公开的加密钥KeB ，并用 KeB 对 SA 再加密，得到密文C， C=E（SA ，KeB） ④最后，A把 C发送给 B，并将 SA或 C留底。 ⑤B收到后，若是不保密通信，则先查到A的公开加密钥KeA ，然后用KeA 对签名进行验证： E（SA，KeA）=E（D（M，KdA），KeA）=M ⑥若是保密通信，则B先用自己的保密的解密钥KdB 对C解密，然后再查到A的公开加密钥KeA ，用KeA 对签名进行验证： D（C，KdB）=D（E（SA，KeB），KdB）= SA E（SA，KeA）=E（D（M，KdA），KeA）=M 如果能够恢复出正确的M，则说明SA是A的签名，否则SA不是A的签名。 签名通信协议安全分析： ① 因为只有A才拥有KdA ，而且由公开的KeA 在计算上不能求出保密的解密钥KdA 。因此签名的操作只有A才能进行，任何其他人都不能进行。所以，KdA 就相当于A的印章或指纹，而SA 就是A对M的签名。对此A不能抵赖，任何其他人不能伪造。 ② 事后如果A和B关于签名的真伪发生争执，则他们应向公正的仲裁者出示留底的签名数据，由仲裁者当众验证签名，解决纠纷。 签名通信协议的问题： ①验证签名的过程就是恢复明文的过程。而B事先并不知道明文M，否则就用不着通信了。那末B怎样判定恢复出的M是否正确呢？ ②怎样阻止B或A用A以前发给B的签名数据，或用A发给其他人的签名数据来冒充当前A发给B的签名数据呢？ 仅仅靠签名本身并不能解决这些问题。 ? 解决问题的一种办法： ① 合理设计明文的数据格式： 发方标识 收方标识 报文序号 时间 数据 纠错码 M= 于是，A以 ③只要用A的公钥验证签名并恢复出正确的附加信息H= ④设附加信息 H= ? 解决问题的另一种办法：对HASH（M）签名，而不直接对M签名。 发方标识 收方标识 报文序号 时间 数据 HASH码 M= D(E(M))=(Me)d =Med =(Md)e =E(D(M)) mod n ， 所以RSA可同时确保数据的秘密性和真实性。 因此利用RSA密码可以同时实现数字签名和数据加密。 设M为明文，KeA = KdA = SA = D(M，KdA)= （M d ）mod n SA 便是A对M的签名。 验证签名的过程是， E（SA ，KeA）=（M d ）e mod n = M 3、对RSA数字签名的攻击 ①一般攻击:设e和n是用户A的公开密钥，所以任何人都可以获得并使用e和n。攻击者可随意选择一个数据Y，并用A的公钥计算 X＝（Y）e mod n 因为 Y＝（X）d mod n ，于是可以用Y伪造A的签名。因为Y是A对X的一个有效签名。注意：这样的 X 往往无正确语义！ ②利用已有的签名进行攻击: 攻击者选择随机数据 M3，且M3=M1M2 mod n 。 攻击者设法让A对M1和M2签名： S1＝（M1）d mod n ， S2＝（M2）d mod n 于是可以由S1和S2计算出A对M3的签名。因为 (S1S2)=(M1)d(M2)d mod n =（M3）d mod n = S3 对策：A不对数据M签名，而是对HASH(M)签名。 此时： S1＝HASH(M1)d mod n ， S2＝HASH(M2)d mod n 而，HASH(M1)d HASH(M2)d≠HASH(M1M2)d mod n 所以：S3≠S1S2 于是不能由S1和S2计算出A对M3的签名。