第二讲 信息加密技术

第二讲信息加密与鉴别技术古典密码2.2对称密码2.3公钥密码2.42.1密码系统概述2对称密钥算法的工作模式2.5第二讲信息加密与鉴别技术2加密方式2.6密码系统概述•密码学的发展史密码学是一门古老而年轻的科学，密码学的发展历程大致经历了三个阶段：古代密码阶段、古典密码阶段和近代密码阶段。a）古代加密方法（手工阶段）b）古典密码（机械阶段）c）近代密码（计算机阶段）2.1密码系统概述•密码学的发展史a)古代密码阶段2.1密码系统概述•密码学的发展史b)古典密码阶段（恺撒密码）2.1密码系统概述•密码学的发展史b)古典密码阶段（恩尼格玛密码）2.1密码系统概述2.1密码系统概述•密码学的发展史c)近代密码阶段1949年密码学正式成为一门科学的理论基础应该首推美国科学家Shannon（香侬）于1949年发表的一篇文章《保密通信的信息理论》，他在研究保密机的基础上，提出了将密码建立在某个已知的数学难题基础上的观点。2.1密码系统概述•密码学的发展史c)近代密码阶段1976W.Diffie和M.Hellman发表了《密码学的新方向》一文，提出了适应网络上保密通信的公钥密码思想，开辟了公开密钥密码学的新领域，掀起了公钥密码研究的序幕。受他们的思想启迪，各种公钥密码体制被提出，特别是1978年RSA公钥密码体制的出现，成为公钥密码的杰出代表，并成为事实标准，在密码学史上是一个里程碑。2.1密码系统概述•密码学的发展史c)近代密码阶段1977美国国家标准局（NBS，即现在的国家标准与技术研究所NIST）于1977年1月15日正式公布实施了美国的数据加密标准（DataEncryptionStandard，DES），公开它的加密算法，并被批准用于政府等非机密单位及商业上的保密通信。2.1密码系统概述•密码学基本概念密码学（cryptology）作为数学的一个分支，它是密码编码学和密码分析学的统称。其中密码编码学就是研究密码编制的科学,密码分析学就是研究密码破译的科学。a)密码学的基本思想密码技术的基本思想是伪装信息，使未授权者不能理解它的真实含义。伪装就是对数据施加一种可逆的数学变换。下面给出了带有加密系统的安全通信的模型图：2.1密码系统概述•密码学基本概念2.1密码系统概述•密码学基本概念a)密码学的基本思想通过以上模型可以看到，伪装前的数据称为明文，伪装后的数据称为密文。伪装的过程称为加密，去掉伪装恢复明文的过程称为解密。加解密要在密钥的控制下进行。将数据以密文的形式存储在计算机的文件中或送入网络信道中传输，而且只给合法用户分配密钥。2.1密码系统概述•密码学基本概念b)密码体制的构成一个密码系统，通常称为密码体制有五个部分构成：明文空间M：它是全体明文的集合。密文空间C：它是全体密文的集合。密钥空间K：它是全体密钥的集合。其中每一个密钥K由加密密钥Ke和解密密钥Kd组成加密算法E：它是一族由M到C的加密变换。解密算法D：它是一族由C到M的解密变换。2.1密码系统概述•密码学基本概念c)密码体制的分类按照密钥的管理方式分为两类：对称密钥体制非对称密钥体制按照加密模式分：序列密码（流密码）分组密码2.1古典密码•模运算a)模的定义如果a是一个整数，n是一个正整数，定义amodn为a除以n的余数a＝b·a/n+(amodn)。b)模算术运算由定义可知，运算（modn）将所有的整数映射到集合{0，1，…，n-1},那么在这个集合上进行的算术运算称为模算术。2.2古典密码•模运算c)模算术的性质[(amodn)+(bmodn)]modn=(a+b)modn;[(amodn)–(bmodn)]modn=(a-b)modn;[(amodn)×(bmodn)]modn=(a×b)modn.2.2古典密码•数学基础（欧几里德扩展算法）①（A1，A2，A3）←（1，0，a）;（B1，B2，B3）←（0，1，b）；②ifB3=0returnA3=gcd(a,b);noinverse③ifB3=1returnB3=gcd(a,b);B2=b-1moda④Q=⑤（T1,T2,T3）←（A1-QB1,A2-QB2,A3-QB3）⑥（A1,A2,A3）←（B1,B2,B3）⑦（B1,B2,B3）←（T1,T2,T3）⑧goto②2.2A3/B3古典密码例：在Z26中求解17对于mod26的乘法逆元。2.2循环次数QA1A2A3B1B2B3初值—102601171101171-19211-19-12831-1282-3117-1mod26=-3mod26=23mod26,逆元为23。古典密码•编码方法概述古典密码的发展也经历了很长的一个历史过程，形成了众多的密码算法，但是其编码方法只有两种：代换和置换。其中，代换密码的使用较为频繁。古典密码中的代换密码体制重要有：单表（简单）代换密码体制，多名代换密码体制，多字母代换密码体制和多表代换密码体制。其中又以单表代换密码体制和多表代换密码体制较为常用。2.2古典密码•单表代换（移位密码）最简单的一类单表代换密码。其加解密算法如下:加密算法：C=(M+K)mod26解密算法：M=(C-K)mod26密钥：K∈[0,25]例1：使用恺撒密码加密明文信息”meetmeaftertheparty”.解：因为密钥K=3，其加密算法为：C=M+3mod26故密文为：phhwphdiwhowkhsduwb2.2古典密码•单表代换（仿射密码）密钥空间312它也是单表代换密码中的一种。它的明文空间和密文空间一样是26个英文字母。其加解密算法与密钥如下：加密算法：C＝ａM＋ｂ(mod26)解密算法：M＝a-1（C－ｂ）(mod26)密钥：Ｋ＝（a,b）其中，ａ要求与26要互素，ａ∈(1,3,5,7,9,11,15,17,19,21,23,25)，ｂ可以取0～25中的任意一个数。与前面a的取值相对应的ａ-1∈（1，9，21，15，3，19，7，23，11，5，17，25）。2.2古典密码•单表代换（仿射密码）例2：设K=（7，3），7-1mod26=15,加密函数是C=7M+3mod26,加密明文信息hot。解：（1）将明文hot转化为其对应的数字信息；｛7，14，19｝（2）利用加密变换：C=7M+3mod26进行加密；（3）所得密文对应的数字为：｛0，23，6｝；（4）hot对应的密文为axg。2.2古典密码•多表代换多表代换密码体制是古典密码体制的又一个典型的代表，其代表算法有：维吉尼亚（Vigenere）密码、轮转（机）密码等，其中维吉尼亚密码是美国内战时期军方广泛使用的一种密码技术，而轮转密码则是二战时期，各国争相使用和破译的密码。单表代换密码体制中，明密文是一一对应的关系，所以容易受到基于统计分析的相关攻击，而多表代换体制从一定程度上挫败了密文的统计特性。2.2古典密码•多表代换（维吉尼亚密码）Vigenere密码是一种典型的多表替代密码，其密码表是以字母表移位为基础，把26个英文字母进行循环移位，并按n个字母一组进行变换，其加解密算法表示如下：设密钥K = k0k1k2…kn，明文M = m0m1m2…mn加密算法：ci=(mi + ki)mod26,i = 0,1,…,n解密算法：mi=(ci-ki)mod26,i = 0,1,2,…,n2.2古典密码•多表代换（维吉尼亚密码）密钥空间26的N次方例3：令密钥字为K=play,明文信息为intelligent,利用维吉尼亚密码加密该明文。解：先根据密钥字长度将要加密的明文分组：明文：M＝INTELLIGENT密钥：K＝PLAYPLAYPLA密文：C=Ek(M)＝XYTCAMIETYT2.2明文ABCDEFGHIJKLMNOPQRSTUVWXYZAABCDEFGHIJKLMNOPQRSTUVWXYZBBCDEFGHIJKLMNOPQRSTUVWXYZACCDEFGHIJKLMNOPQRSTUVWXYZABDDEFGHIJKLMNOPQRSTUVWXYZABCEEFGHIJKLMNOPQRSTUVWXYZABCDFFGHIJKLMNOPQRSTUVWXYZABCDEGGHIJKLMNOPQRSTUVWXYZABCDEFHHIJKLMNOPQRSTUVWXYZABCDEFGIIJKLMNOPQRSTUVWXYZABCDEFGHJJKLMNOPQRSTUVWXYZABCDEFGHIKKLMNOPQRSTUVWXYZABCDEFGHIJLLMNOPQRSTUVWXYZABCDEFGHIJKMMNOPQRSTUVWXYZABCDEFGHIJKLNNOPQRSTUVWXYZABCDEFGHIJKLMOOPQRSTUVWXYZABCDEFGHIJKLMNPPQRSTUVWXYZABCDEFGHIJKLMNOQQRSTUVWXYZABCDEFGHIJKLMNOPRRSTUVWXYZABCDEFGHIJKLMNOPQSSTUVWXYZABCDEFGHIJKLMNOPQRTTUVWXYZABCDEFGHIJKLMNOPQRSUUVWXYZABCDEFGHIJKLMNOPQRSTVVWXYZABCDEFGHIJKLMNOPQRSTUWWXYZABCDEFGHIJKLMNOPQRSTUVXXYZABCDEFGHIJKLMNOPQRSTUVWYYZABCDEFGHIJKLMNOPQRSTUVWXZZABCDEFGHIJKLMNOPQRSTUVWXY密钥古典密码•置换（换位）密码将明文中的字母不变而位置改变的密码称为换位密码，也称为置换密码。如，把明文中的字母逆序来写，然后以固定长度的字母组发送或记录。列换位法是最常用的换位密码，其加密方法如下：把明文字符以固定的宽度m（分组长度）水平地（按行）写在一张纸上（如果最后一行不足m,则需要补充固定字符），按1,2,3…,m的一个置换∏交换列的位置次序，再按垂直方向（即按列）读出，即可得到密文。2.2古典密码•置换（换位）密码解密的方法如下，将密文按固定宽度n（加密时的列数）垂直地写在纸上，按置换∏的逆置换交换列的位置次序，然后水平地读出，即可得到明文。置换∏就是密钥。例4：设明文”Jokerisamurderer”，密钥∏=(41)(32)(即∏（4）=1，∏（1）=4，∏（3）=2，∏（2）=3)，按4,3,2,1列的次序读出，即可得到密文，试写出加密和解密的结果。解：加密时，把明文字母按长度为4进行分组，每组2.2古典密码•置换（换位）密码写成一行，这样明文字母”Jokerisamurderer”被写成4行4列，然后把这4行4列按4,3,2,1列的次序写出，即得到密文。过程与结果如下：1）：按4字母一行写出，即：jokerisamurderer2.2古典密码•置换（换位）密码2）：按列写出的顺序：43213）：按列写出密文：eadrksreoiurjrme解密时，把密文字母按4个一列写出，再按∏的逆置换重排列的次序，最后按行写出，即得到明文，如下：1）：按4字母一列写出，即：ekojasir2.2古典密码•置换（换位）密码drumrere2):交换列的顺序：43213):按行写出明文：jokerisamurderer.纯换位密码易于识别，因为它具有与原文字母相同的频率，但通过多次换位可以使密码的安全性有较大的改观。2.2古典密码•古典密码的统计分析加密算法产生以来，对加密信息的破解技术就应运而生。对于古典密码来说，因为它自身是基于26个英文字母的，所以关于它的破解技术大都是基于英文字母的统计特性的，此类破解技术利用了以下原理：在明文出现频率较高的字符，与该明文对应的密文字符在密文出现的频率也会比较高；字符组也存在这样的特征。2.2古典密码•古典密码的统计分析将26个英文字母划分为4个频率组：高ETAONIRSH中DLUCM低PFYWGBV缺少JKQXZ仅仅依靠以上规律通常还是很不充分的，很多时候还会用到双联字母或三联字母的出现频率来辅助破译。例如，TH，HE，IN，RE，DE，ST，EN等都比较常出现。2.2古典密码假设攻击者Oscar