密码技术基础.ppt

第二章 密码技术基础,密码技术概述 传统密码技术 现代密码技术 网络加密技术,2.1 密码技术概述,2.1.1 密码基本概念 安全问题包含两个主要内容： 数据的保密性 数据的完整性 密码学 密码学是研究密码分析和密码编制的一门科学，它涉及数学、物理、计算机科学、电子学、系统工程、语言学等学科内容。 加密(encryption) 用某种方法伪装消息并隐藏它的内容的方法称作加密 明文(plaintext) 待加密的消息被称作明文 明文空间 所有明文的集合称为明文空间,2.1 密码技术概述,密文(ciphertext) 被加密以后的消息称为密文 密文空间 所有密文的集合称为密文空间 解密(decryption) 把密文转变成明文的过程称为解密 密钥 加密体制中的加密运算是由一个算法类组成，这些算法类的不同运算可用 不同的参数表示，不同的参数分别代表不同的算法，被称作密钥 密钥空间 密钥空间是所有密钥的集合 明文空间 所有明文的集合称为明文空间 注: 任何一个密码系统包含明文空间、密文空间、密钥空间和算法。密码系统的两个基本单元是算法和密钥。其中算法是相对稳定的，视为常量；密钥则是不固定的，视为变量。密钥安全性是系统安全的关键，因此为了密码系统的安全，频繁更换密钥是必要的，在密钥的分发和存储时应当特别小心。,2.1 密码技术概述,简单加密、解密过程,加密,解密,接受方,第三方,发送方,明文,密文,原来的明文,图21 简单加密、解密过程,发送方用加密密钥，通过加密设备或算法，将信息加密后发送出去。接收方 在收到密文后，用解密密钥将密文解密，恢复为明文。如果传输中有人窃取，他只能得到无法理解的密文，从而对信息起到保密作用。,2.1 密码技术概述,2.1.2 密码技术的分类 密码体制一般可分为传统密码和现代密码,从不同的角度根据不同的标准，可以把密码分成若干类: 按应用技术或历史发展阶段划分 1手工密码 2机械密码 3电子机内乱密码 4计算机密码 按保密程度划分 1理论上保密的密码 2实际上保密的密码 3不保密的密码 按密钥方式划分 1对称式密码 2非对称式密码 按明文形态分 1模拟型密码 2数字型密码 按编制原理划分 1移位 2代替 3置换 4组合形式 与电子商务密切相关的安全理论主要有以下三大类： 1分组密码 2公开密钥密码 3非密码的安全理论和技术,2.2 传统密码技术,2.2.1 换位密码 换位密码根据一定的规则重新安排明文字母，使之成为密文。常用的换位密码有两种，一种是列换位密码，另一种是周期换位密码。 例1 假定有一个密钥是type的列换位密码，我们把明文can you believe her写成4行4列矩阵，如表21所示。 表21,密钥type顺序3 4 2 1c a n yo u b el i e ve h e r按照密钥type所确定的顺序，按列写出该矩阵中的字母，就得出密文： y e v r n b e e a u i h co l e,例2 假设有一个周期是4的换位密码，其密钥是i1，2，3，4的一个置换f(i)3，4，2，l。明文同上例，加密时先将明文分组，每组4个字母，然后根据密钥所规定的顺序变换如下： 明文： mc a n y o u b e 1 i e v e h e r 密文： cn y a c b e u o e v i l e r h e,2.2 传统密码技术,2.2.2 代替密码 密码体制一般可分为传统密码和现代密码,从不同的角度根据不同的标准，可以把密码分成若干类: 简单代替密码（simple substitution cipher） 简单代替密码就是将明文字母表m中的每个字母用密文字母表c中的相应字母来代替。 1移位密码 加密变换可表示为：ek(m)=(k+m)mod q=c，解密变换为；dk(c)=(m-k)mod q=m，其中q为字母表m的长度，m为明文字符在字母表m中的位置，c为密文字母在字母表c中的位置。移位密码就是对英文26个字母进行移位代替的密码 。 2乘数密码 加密过程可表示为： ek(m)km mod q=c， 其中k和q为互素的，这样字母表中的字母会产生一个复杂的剩余集合。 3仿射密码 加密的形式为：ek(m)=(k1m+k2)mod q=c，其中要求k1和q是互素的。,2.2 传统密码技术,多名或同音代替密码(homophonic substitution cipher) 在同音代替中，一个明文字母表的字母a，可以变换为若干个密文字母f(a)，称为同音字母，因此，从明文到密文的映射f的形式是f：a2c，其中a，c分别为明文和密文的字母表。 例3 假定一个同音代替密码的密钥是一段短文，该文及其其中各个单词的编号，如下所示： (1) canadas large land mass and (6) scattered population make efficient communication (11) a necessityextensive railway，road (16) and other transportation systems，as (21) well as telephone，telegraph，and (26) cable networks，have helped to (31) link communities and have played (36) a vital part in the (41) countrys development for future 在上表中，每一个单词的首字母都和一个数字对应，例如字母c与数字1,10，26，32，41对应；字母m和数字4，8对应等，加密时可以用与字母对应的任何一个数字代替字母，例如，如果明文为i love her forever的密文可能是39 2 17 37 9 28 9 14 43 17 14 13 37 13 14,2.2 传统密码技术,多表代替密码(polyalphabetic substitution cipher) 在vigenere密码中，用户钥是一个有限序列k(kl，k2，k3，kd),我们可以通过周期性(周期为d)将k扩展为无限序列，得到工作钥 k(kl，k2，k3，),其中 kik(i mod d)，li,如果我们用和分别表示密文和明文字母，则vigenere密码的变换公式为: (+ki)(mod n) 例4 在用户钥为cat的vigenere密码(周期为3)中，加密明 文vigenere cipher的过程如下(n26): 明 文 mvig ene rec iph er 工作钥 kcat cat cat cat ca, 密 文 cxiz gnx tev kpa gr. 在这个例子中,每个三字母组中的第一个、第二个和第三个字母分别移动（mod 26）2个、0个和19个位置。 游动钥密码是一种非周期性的vigenere密码，它的密钥和明文信息一样长，而且不重复。,2.2 传统密码技术,例5 假定一个游动钥密码的密钥是美国1776年7月4日发布的独立宣 言，从第一段开始，因此，明文the object of 明文： mt h e o b j e c t o f 密钥： kw h e n i n t h e c o 密文： cp o i b j w x j x q t 多字母代替密码(polygram substitution cipher) 每一对明文字母m1和m2，都根据以下5条规则进行加密： (1)若ml和m2在密钥方阵中的同一行，则密文字母c1和c2分别是ml和m2右边字母(第一行看作在第五行的下边)。 (2)若ml和m2在同一列，则c1和c2分别是m1和m2右边的字母(第一行看作为第五行的下边)。 (3)若m1和m2在密钥方阵中的不同行和列，密文字母c1和c2分别是以m1和m2为顶点组成的长方形中的另两个顶点，其中c1和m1、 c2和m2分别在同一行。 (4)若m1m2，则在ml和m2之间插进一个无效字母，例如x。 (5)若明文信息共有奇数个字母，则在明文末尾附加一个无效字母。,2.2 传统密码技术,例6 用playfair密码加密明文bookstore,我们有 明文 mbo xo ks to re 密文 cid rg lp qd hg,2.2 传统密码技术,2.2.3 转轮机 轮转机有一个键盘和一系列转轮，每个转轮是字母的任意组合，有26个位置，并且完成一种简单代替。例如，一个转轮可能被用线连起来以完成用k代替a，月w代替d，用l代替t等，而且转轮的输出栓连接到相邻的输入栓。 例如，有一个密码机，有4个转轮，第一个转轮可能用g代替b，第二个转轮可能内n代替g，第二个转轮可能用s代替n。第四个转轮可能用c替s，c应该是输出密文。当转轮移动后，下一次代替将不同。为使机器更加安全，可以把几种转轮和移动的齿轮结合起来。因为所有的转轮以不同的速度移动，n个转轮的机器周期为26n。为进一步阻止密码分析，有些转轮机在每个转轮上还有不同的位置号。,2.2 传统密码技术,2.2.4 一次一密密码 每个密钥仅对一个消息使用次。发方对所发的消息加密，然后销毁乱码本中用过的一页或用过的磁带部分。收方有一个同样的乱码本，并依次使用乱码本上的每个密钥去解密密文的每个字符。收方在解密消息后销毁乱码本中用过的一页或用过的磁带部分。新的消息则用乱码本中新的密钥加密。 例如， 消息 0netimepad 乱码本的密钥序列 tbfrgfarfm 密文 ipklpsfhgq，,因为 o+t mod26i n+b mod26p e+f mod26k,密钥序列也可能是： poyyaeaazx 解密出来是： salmoneggs 或密钥序列为： bxfgbmtmxm 解密出来的明文为： greenfluid,2.2 传统密码技术,使用一次一密乱码本需要注意 密钥字母必须随机产生。对这种方案的攻击主要是针对用来产生密钥序列的方法。伪随机数发生器通常只有非随机性，所以不能用于产生随机密钥序列。采用真随机源，它才是安全的。 0netimepad 密钥序列不能重复使用。如果密码分析家有多个密钥重叠的密文，那么即使你用多兆字节的乱码本，他也能重构明文。他可以把每排密文移来移去，并计算每个位置的适配量。如果他们排列正确，则适配的比例会突然升高(准确的百分比与明文的语种有关)。从这一点来说，密码分析是容易的，它类似于重合指数法只不过用两个“周期”。所以千万别重复使用密钥序列。,2.3 现代密码技术,2.3.1 对称密码技术 对称密钥密码系统使用的加密密钥和解密密钥是相同的，或者可以简单地相互推导出来。典型的对称密钥密码系统是数据加密标准(des-data encryption standard)，此外还有idea(international data encryption algorithm)、aes(advanced encryption standard)等。 数据加密标准（des）,逆初始变换,子密钥生成 k1,k2,k16,初始变换,64比特密文,64比特明文,64比特密钥,初始换位,图22 des加密的数据流程,2.3 现代密码技术,1加密处理 a 初始换位：加密处理首先要对64比特的明文按表23所示的初始换位表1p进行换位。 表中的数值表示输入比特被置换后的新比特位置。例如，输入的第58比特，在输出时被置换到第l比特的位置；输入的第2比特，在输出时被置换到第8比特的位置；输入的第l比特，在输出时被置换到第40比特的位置；输入的第7比特，在输出时被置换到第64比特的位置上。,表23,2.3 现代密码技术,b 加密处理： 上述换位处理的输出、中间要经过16层复杂的加密变换。经过初始换位的64比特的输出变为下一步的输入，此64比特分成左、有两个32比特，左为lo，右为ro，从lo和ro到ll6和r16共进行了如图24所示的16层加密变换。换完之后，若经过第n层处理后的左、右32比特分别为ln和rn，则ln和rn可作如下的定义； ln=rn-1 rn=ln-1f(rn-1，kn) 这里，kn是向第n层输入的48比特的密钥；ln-1和rn-1分别是第n-1层的输出；f是以rn-1和kn为变量的输出32比特的函数。,2.3 现代密码技术,明文(64),初始变换,左移位,左移位,d0(28),c0(28),密钥(56),压缩型变换,压缩型变换,f(r1,k2),r0(32),r2(32),l1(32),f(r0,k1),l0(32),压缩型换位,密钥(64),c1(28),c1(28),左移位,c2(28),c2(28),左移位,左移位,左移位,第一层,加密处理部分,密钥生成部分,图23 des算法的框图,2.3 现代密码技术,d16(28),c16(28),r16(32),压缩型换位,f(r15,k15),r2(32),r15(32),l15(32),l16(32),l2(32),密文(64),最后变换,第16层,加密变换,( )内为比特数,k16 (48),k16,2.3 现代密码技术,ln-1,rn,ln,f(rn-1,kn),rn-1,32比特,32比特,32比特,32比特,48比特,kn,图24 第n层的加密变换,2.3 现代密码技术,c 最后换位： 进行完16次的加密变换之后，将l16和r16合成64位数据，再按表24所示的最后换位表ip1进行换位，得到64比特的密文，这就是des加密的结果。,表24 最后换位表ip1,由图25可以看出，表24和表23是完全的逆变换。,2.3 现代密码技术,2加密变换 例: 向s1输入一个二进制状态0ll01l时，因开头的0和末尾的1合起来为01(即十进制数1)，所以选中了编号为1的代替表；又因中间4个比特状态为1101(十进制数13)，表示选第13列。第1行第13列所指示的值为5，即输出状态为0101，这4个比特就是经过代替之后的状态。表27给出了s1s8的s盒代替表，其中的每一行代表一种代替表。接着，从8个s盒输出的32比特，根据表28所示的单纯换位表p进行换位，这样便实现了f(r，k)的变换。,表25 扩展型换位表e,2.3 现代密码技术,表26 s盒的代替表（s1）,2.3 现代密码技术,图25 初始换位和最后换位,2.3 现代密码技术,2.2 传统密码技术,表27 s盒代替表,2.3 现代密码技术,表28 单纯换位表p,2.3 现代密码技术,3.子密钥的生成,下面，说明子密钥k1k16的16层子密钥的生成过程。在64比特的密钥里包含了8位的奇偶校验位，所以实际密钥长度是56比特，而每层要生成48比特的子密钥。 输入64比特的密钥，首先通过压缩型换位pc1(permutation choice)去掉奇偶校验位，再将不含奇偶校验位的56比特进行输出，而每层要分成两部分，上部分的28比特为c0，下部分的28比特为d0，如表29所示。c0和d0依次进行循环左移位，这样就生成了cl和dl，然后将cl和dl合成56位，再通过压缩型换位pc2(表210)，输出的结果即为48位的子密钥k1。再将c1和d1进行循环左移位和pc2的转换，即得子密钥k2。依次类推，就可以得出16级的子密钥k1，k2，k16。16层子密钥的生成过程如图23右半部所示。值得注意的是，在产生16级子密钥的过程中，l1、l2、l9、 l16是循环左移1位的变换，而其余的ln都是循环左移2位的变换。16层变换中的循环左移位次数如表211所示。,2.2 传统密码技术,2.2 传统密码技术,表211 密钥生成中的循环左移位次数,2.3 现代密码技术,4解密处理 从密文到明文的解密处理可采用与加密算法完全相同的算法。不过解密要用加密的逆变换，也就是把上述的最后换位表1p-1和初始换位表lp完全倒过来变换。另外，在16层的变换处理中，由于rn-1ln和ln-1rnfln，kn，因此要求出rn-1和ln-1只要知道ln、rn和kn，并使用同一个函数f所表示的变换便可以实现，从而在各层变换中，如果采用与加密时相同的kn来处理，就能实现解密。具体地说，输入des算法中的密文,经过初始换位可得到l16和r16,第1层处理时的密钥是逆序的，用k16可以求出l15和r15，其中f(r，k)即使不可逆也没有关系；然后用k15进行变换求出l14和r14。依次类推，经过16层的变换即可得到l0和r0。,5des加密的评价,2.3 现代密码技术,6二重des 二重des是多重使用des时最简单的形式，其中明文为p，两个加密密钥为k1和k2，密文为： cek2ek1p. 解密时，以相反顺序使用两个密钥： pdk1dk2c.因此，二重des所用密钥长度为112比特，强度极大地增加。然而，如果对任意两个密钥k1和k2，能够找出另一密钥k3，使得 ek2ek1p=ek3p. 那么，二重des以及多重des都没有意义，因为它们与56比特密钥的单重des等价。,2.3 现代密码技术,7两个密钥的三重des,2.3 现代密码技术,8三个密钥的三重des 三个密钥的三重des密钥长度为168比特，加密方式为: cek3dk2ek1p 令k3k2或k1k2，则变为一重des。 三个密钥的三重des己在因特网的许多应用(如pgf和s/mime)中被采用。,2.3 现代密码技术,国际数据加密算法（idea） 高级加密标准（aes） 整个算法包括加密过程与轮密钥生成两个独立的部分 1.加密过程 设信息块是m，轮密钥分别是k0, k1,knr-1 ,加密过程如图210所示。解密过程把加密过程完全反过来即可。,+,+,+,+,e,e1,e,明文m,密文,bytesub,shiftrow,mixcolumn,bytesub,shiftrow,2.3 现代密码技术,bytesub函数 把每个8bit的字节看成有限域gf(28)中的一个元素，那么函数bytesub是作用在每个字节上的非线性变换，它定义为：bytesub:gf(28)gf(28) 如右图： 图211描述了信息块长度是192bit时， 函数bytesub的作用情况。 shiftrow函数 把信息块记为4行、nb列的矩阵形式， 函数shiftrow就是对每行实行不同的 左移位，每行的左移位数c1,c2,c3分 别由nb按照表213决定。 函数shiftrow的作用可表示成图212。,2.3 现代密码技术,bytesub,图211 函数bytesub,表213 左移位函数的确定,2.3 现代密码技术,不移位,左移c1位,左移c2位,左移c3位,图212 函数shiftrow,2.3 现代密码技术,mixcolumn函数 mixcolumn函数是gf(28)4上的一个线性变换，变换矩阵c定义为：,其中,的运算均为在gf(28)中进行。图213描述了信息块长度是192bit时， mixcolumn函数的作用情况。此处矩阵c中的元素xy理解为两个4 bit长的 二进制数的串接，比如02理解为0000 0010。,2.3 现代密码技术,图213 函数mixcolumn,2.3 现代密码技术,2.轮密钥的生成,轮密钥的生成过程包括加密密钥的扩张和轮密钥的选取两个部分。,加密密钥的扩张 假设信息块的长度是nb个32bit字，由于整个加密过程需要nr +1个轮密钥，每个轮密钥的长度是nb个32bit字，因此密钥的扩张过程需要产生nb（nr 1）个32bit字，记为w0,w1,，wnb(nr +1)-1。加密密钥的扩张根据密钥长度nk的不同，有两种不同的扩张方式。假设加密密钥为wk0 wk1wknr-1,令w0= wk0,w1= wk1,wnr-1= wknr-1。 当nr6时，对于nkinb(nr +1),如图214a所示。当nr6时，对于nkinb(nr +1),如图214b所示。 其中，rotbyte把(a,b,c,d)变为(b,c,d,a),a,b,c,d是8bit字节； rconti=(rci,00,00,00);rc1=1,rci=xrci-1=xi-1,2.3 现代密码技术,2.3 现代密码技术,轮密钥的选取 加密密钥经过扩张产生了nb(nr +1)个32bit字，把它们均等地分成nr +l块，每块包含nb个32bit字，那么第一个轮密钥就是第一个块，第二个轮密钥就是第二个块，依此类推得到所有的轮密钥。 3.关于aes的讨论 与其他分组码相比，aes具有如下特点：可变的密钥长度；混合的运算；数据相关的圈数；密钥相关的圈数；密钥相关的s盒；长密钥调度算法；可变长明文/密文块长度；可变圈数；每圈操作作用于全部数据。,2.3 现代密码技术,轮密钥的选取 加密密钥经过扩张产生了nb(nr +1)个32bit字，把它们均等地分成nr +l块，每块包含nb个32bit字，那么第一个轮密钥就是第一个块，第二个轮密钥就是第二个块，依此类推得到所有的轮密钥。 3.关于aes的讨论 与其他分组码相比，aes具有如下特点：可变的密钥长度；混合的运算；数据相关的圈数；密钥相关的圈数；密钥相关的s盒；长密钥调度算法；可变长明文/密文块长度；可变圈数；每圈操作作用于全部数据。,2.3 现代密码技术,2.3.2 非对称密码技术 公钥加密技术原理概述 公钥加密是基于单向陷门(trap door)函数来实现的，单向陷门函数是指满足下列条件的函数f(x)： (1)给定x，计算yf(x)是容易的； (2)给定y，计算xf-1(y)是困难的； (3)存在，已知时，对给定的任何y，若相应的x存在，则计算x=f-1(y)是容易的。 仅满足第(1)条、第(2)条的称为单向函数，第(3)条称为陷门性，称为陷门信息。当用陷门函数f(x)作为加密函数时可将f(x)公开，这相当于公钥。f(x)函数的设计者将保密，用作解密密钥，这相当于私钥。由于加密函数是公开的，任何人都可以将信息x加密成y=f(x)，然后送给函数的设计者，当然可以通过不安全信道传送，由于设计者拥有(私钥)，他可以容易地解出xf-1(y)。单向陷门函数的第(2)条性质表明窃听者由截获的密文yf(x)推测x是不可行的。 目前公钥密码系统单向陷门函数的设计主要依赖下面3种数学难题： (1)背包问题；(2)大整数因子分解问题；(3)离散对数问题,2.3 现代密码技术,rsa加密系统 1.rsa算法的描述 rsa算法的实现步骤如下：(b为实现者) (1)b寻找出两个大素数p和q。 (2)b计算出n=pq和f(n)(p一1)(q一1)。 (3)b选择一个随机数e(0ej(n)，满足(e，f(n)=1。 (4)b使用欧几里得扩展算法计算d=e-1(mod f(n)。 (5)b在目录中公开n和e作为他的公开钥，保密p、q和d。 密码分析者攻击rsa体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出f(n)=(p-1)(q1)，然后由公开的e解出秘密的d。加密时，对每一明文分组如下计算：ci=mie (mod n).解密时，取每一密文分组c并计算：mi=cie (mod n) rsa算法主要用于数据加密和数字签名。rsa算法用于数字签名时，公钥和私钥的角色变换即可。即将消息用d加密签名，用e验证签名。,2.3 现代密码技术,2.rsa算法实例 若b选择了p=101和q=113，那么，n=11413，f(n)=100x112=11200；再用辗转相除法(euclidean算法)来求得e，使(e，f(n)=1)。假设b选择了e=3533，那么用辗转相除法将求得：d=e-1(mod ll200)，于是b的解密密钥d= 6597。 b在一个目录中公开n=11413和e=3533，现假设a想发送明文9726给b，他计算：97263533(mod ll413)=5761，且在一个信道上发送密文5761。当b接收到密文5761时，他用他的秘密解密指数(私钥)d=6597进行解密： 57616597(mod ll413)=9726 3.关于rsa的讨论,2.3 现代密码技术,3 elgamal加密系统 1.密钥对产生方法 密钥对产生办法如下： (1)选择一个素数p，两个随机数g和x,要求g，xp。 (2)计算ygx (mod p)，则其公钥为y、g和p；私钥是x。g和p可由一组 用户共享。 2.eigamal用于加密 假定被加密信息为m，首先选择一个随机数k，k与p-1互质，计算 a=gk(mod p)， b=ykm(mod p). (a，b)为密文，是明文的两倍长。解密 时计算 mb/ax(mod p) 3.eigamal用于数字签名 eigamal主要用于数字签名。假定被签信息为m，首先选择一个随机数 k，k与p-1互质，计算a=gk(mod p)，再用扩展euclidean算法对下面方程 求解b： m=xa + kb(mod p-1)签名就是(a，b)。随机数k须丢弃。验证时要验证下式： yaab (mod p)=gm(mod p)同时一定要检验是否满足lap，否则签名容易伪造。,2.3 现代密码技术,椭圆曲线密码体制 1.有限域上的椭圆曲线定义 设k表示一个有限域，e是域k上的椭圆曲线，则e是一个点的集合： e/k=(x,y)|y2+a1xy+a3y=x3+a2x2+a4x+a6,a1,a3,a2,a4,a6,x,yko 其中o表示无穷远点。 在e上定义“+”运算，p+qr，r是过p、q的直线与曲线的另一交点关于x轴的对称点(如图215所示)，当pq时r是p点的切线与曲线的另一交点关于x轴的对称点(如图216所示)。这样，(e，+)构成可换群(abel群)，o是加法单位元(零元)。,2.3 现代密码技术,椭圆曲线离散对数问题定义如下：给定定义在k上的椭圆曲线e， 一个n阶的点p e/k和点qe/k，如果存在l，确定整数1，0ln1，q=lp,2.3 现代密码技术,2.椭圆曲线上的密码算法 利用eigamal思想构造的椭圆曲线密码体制如下： 首先是产生密钥阶段。b从zn中随机选取充分大的整数kb，随后计算出椭圆曲线上的点p=kbq(q是椭圆曲线上的适当的一点)，将kb保密，作为秘密密钥，并将p公开，作为公钥。 加密方法如下：如果a想把消息m(同样是椭圆曲线上的一点)发送给b，就从zn中随机选择整数lzn后，计算出s1=lq和s2m+lp的值，加密以后的信息就是椭圆曲线上两点(s1，s2)。 解密：b收到加密信息(s1，s2)后，通过密钥kb就可以计算ms2kbs1得到消息m。 例如：椭圆曲线密码实例 作为加密过程的例子，取p=751；ep(-1，188)，这等价于曲线