密码学基础---2010

计算机网络与信息安全技术研究中心1密码学基础主讲人：翟健宏Email:[e-mail]办公室:新技术楼509Tel:[phone]计算机网络与信息安全技术研究中心2内容1.密码体系概述2.古典密码3.对称密钥密码4.公开密钥密码5.数字签名与摘要函数计算机网络与信息安全技术研究中心3数据加密基本概念•密码：是一组含有参数的变换•明文（plaintext)：作为加密输入的原始信息•加密算法：变换函数•密文（ciphertext)：:明文变换结果•密钥（key)：:参与变换的参数计算机网络与信息安全技术研究中心4加密通信的模型Alice加密机Oscar解密机Bob密钥源安全信道XYXKK•密码学的目的：Alice和Bob两个人在不安全的信道上进行通信，而破译者Oscar不能理解他们通信的内容。计算机网络与信息安全技术研究中心5密码体制•通常一个完整密码体制要包括如下五个要素M,C,K,E,D–M是可能明文的有限集称为明文空间–C是可能密文的有限集称为密文空间–K是一切可能密钥构成的有限集称为密钥空间–对于密钥空间的任一密钥，有一个加密算法和相应的解密算法使得ek:MC和dk:CM（分别为加密解密函数），满足,这里。Mxx(x))(edkk计算机网络与信息安全技术研究中心6一个密码体制必须满足如下特性–每一个加密函数Ek和每一个解密函数Dk都能有效地计算–破译者取得密文y后,将不能在有效的时间内破解出密钥k或明文x–一个密码系统是安全的必要条件：•穷举密钥搜索将是不可行的，即密钥空间非常大计算机网络与信息安全技术研究中心7密码分类按发展进程分：古典密码对称密钥密码公开密钥密码按密钥管理的方式分为秘密密钥算法公开密钥算法按加密模式分：序列密码分组密码计算机网络与信息安全技术研究中心81.密码体系概述2.古典密码3.对称密钥密码4.公开密钥密码5.数字签名与摘要函数计算机网络与信息安全技术研究中心9经典密码•代替密码:–简单代替、多名或同音代替、多表代替、多字母或多码代替.•简单代替密码–将明文字母表M中的每个字母用密文字母表C中的相应字母来代替。–这一类密码包括移位密码、替换密码、仿射密码、乘数密码等。计算机网络与信息安全技术研究中心10移位密码•移位密码：–是最简单的一类代替密码，将字母表的字母右移k个位置，并对字母表长度作模运算。•加密变换：ek(m)=(k+m)(modq)；•解密变换：dk(c)=(m-k)(modq)计算机网络与信息安全技术研究中心11凯撒Caesar密码•Caesar密码是对英文26个字母进行移位代替的密码，其M=C；q=26,k=3。•使用凯撒密码将明文M=meetmeafterthetogaparty加密为C=phhwphdiwhowkhwrjdsduwb计算机网络与信息安全技术研究中心12乘数密码•乘数密码：–是一种替换密码，它将每个字母乘以一个密钥k，即Ek(m)=kmmodq；–其中k和q为互素的，这样字母表中的字母会产生一个复杂的剩余集合。–若k和q不互素，则会有一些明文字母被加密成相同的密文字母，而且，不是所有的字母都会出现在密文字母表中。•算法描述–设M=C=Z/(26)，K={a∈Z/(26)|gcd(a,26)=1},x、y∈Z/(26)；–对k=a∈K,Ek(x)=ax(mod26)；Dk(y)=a-1(y)(mod26)，aa-1modq=1a=5,a-1=21a=7,a-1=15计算机网络与信息安全技术研究中心13•例子:a=9，Ek(x)=9x(mod26)ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR–明文=密文cipher=SUFLKX–对于乘数密码，当且仅当a与２６互素时，加密变换才是一一映射的，因此a的选择有11种：a=3,5,7,9,11,15,17,19,21,23,25。–可能尝试的密钥只有11个。计算机网络与信息安全技术研究中心14仿射密码•仿射密码是替换密码的另一个特例，形式为ek(m)=(k1m+k2)modq=cmodq；其中k1和q是互素的。k1=1,3,5,7,9,11,15,17,19,21,23,25•定义：ek(x)=ax+b(mod26)dk(y)=a-1(y-b)(mod26)；x,y∈Z/(26)，q=26时，可能的密钥是26*12=312个。计算机网络与信息安全技术研究中心15仿射密码—例•例子，设k＝（7，3），注意到7-1(mod26)=15,加密函数是ek(x)=7x+3(mod26),相应的解密函数是dk(y)=15(y-3)=15y–19(mod26),易见dk(ek(x))=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod26)•若加密明文：hot，首先转换字母hot成为数字7,14,19,加密：解密：计算机网络与信息安全技术研究中心16单表替换密码的破译•通过字母的使用频率破译计算机网络与信息安全技术研究中心17多表代替密码•单字母出现频率分布与密文中相同，安全性受到威胁。•多表代替密码思想：–使用从明文字母到密文字母的多个映射，来隐藏单字母出现的频率分布，每个映射是简单代替密码中的一对一映射。–维吉尼亚Vigenere密码、博福特Beaufort密码均是多表代替密码。•维吉尼亚Vigenere密码算法如下：–设密钥明文加密变换ek(m)=c1c2…cn；其中：Ci=（mi+ki）mod26；密钥k可以通过周期性地延长，反复进行以至无穷。计算机网络与信息安全技术研究中心181.密码体系概述2.古典密码3.对称密钥密码4.公开密钥密码5.数字签名与摘要函数计算机网络与信息安全技术研究中心19对称密钥密码模型Alice加密机Oscar解密机Bob密钥源安全信道XYXKK计算机网络与信息安全技术研究中心20数据加密标准•DES的产生1973年5月15日,NBS开始公开征集标准加密算法,并公布了它的设计要求:(1)算法必须提供高度的安全性(2)算法必须有详细的说明,并易于理解(3)算法的安全性取决于密钥,不依赖于算法(4)算法适用于所有用户(5)算法适用于不同应用场合(6)算法必须高效、经济(7)算法必须能被证实有效(8)算法必须是可出口的•1974年8月27日,NBS开始第二次征集,IBM提交了算法LUCIFER，该算法由IBM的工程师在1971~1972年研制•最近的一次评估是在1994年1月，已决定1998年12月以后，DES将不再作为联邦加密标准。计算机网络与信息安全技术研究中心21简化的DES•SimplifiedDES方案，简称S-DES方案。加密算法涉及五个函数：(1)初始置换IP(initialpermutation)(2)复合函数fk1，它是由密钥K确定的，具有置换和替代的运算。(3)转换函数SW(4)复合函数fk2(5)初始置换IP的逆置换IP-1(6)置换函数P8、P10计算机网络与信息安全技术研究中心22S-DES的流程计算机网络与信息安全技术研究中心23（1）S-DES的密钥生成•设10bit的密钥为(k1,k2,k3,k4,k5,k6,k7,k8,k9,k10)•置换P10是这样定义的–P10(k1,…,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6)•相当于P10=（35274101986）•LS-1为循环左移一次，•置换P8=(637485109)计算机网络与信息安全技术研究中心24•算法如下图–若K选为(1010000010),产生的两个子密钥分别为•K1=(10100100)；K2=(01000011)计算机网络与信息安全技术研究中心25（2）S-DES的加密运算:初始置换用IP函数:IP=末端算法的置换为IP的逆置换:IP-1=易见IP-1(IP(X))=X。计算机网络与信息安全技术研究中心26简化的得DES方案加密细节如右图计算机网络与信息安全技术研究中心27•函数fk–fk(L,R)=(L⊕F(R,SK),R)是加密方案中的最重要部分，–其中，L、R为8位输入的左右各4位,，–F为从4位集到4位集的一个映射。–SK为子密钥。计算机网络与信息安全技术研究中心28•对映射F来说：–首先输入是一个4位数（n1,n2,n3,n4），第一步运算是扩张/置换（E/P）运算：E/P=(41232341)计算机网络与信息安全技术研究中心29–然后,E/P的结果与子密钥作异或运算得：•8-bit子密钥：K1=(k11,k12,k13,k14,k15,k16,k17,k18),计算机网络与信息安全技术研究中心30•把它们重记为8位：计算机网络与信息安全技术研究中心31•上述第一行的4位输入进S盒S0，产生2-位的输出；•第二行的4位输入进S盒S1，产生2-位的输出。•两个S盒按如下定义：计算机网络与信息安全技术研究中心32•S盒按下述规则运算：–将第1和第4的输入比特做为2bit数，指示为S盒的一个行；将第2和第3的输入比特做为S盒的一个列。如此确定为S盒矩阵的（i,j）数。–例如：（P0,0,P0,3）=(00)，并且(P0,1,P0,2)=(10)，确定了S0中的第0行2列（0，2）的系数为3，记为（11）输出。–由S0,S1输出4bit经置换P4=(2431)；即F的输出。计算机网络与信息安全技术研究中心33回顾：计算机网络与信息安全技术研究中心34•DES是一种对二元数据进行加密的算法,–数据分组长度为64位,密文分组长度也是64位,使用的密钥为64位,有效密钥长度为56位,有8位用于奇偶校验；–解密时的过程和加密时相似,但密钥的顺序正好相反；–DES的整个体制是公开的,系统的安全性完全靠密钥的保密.计算机网络与信息安全技术研究中心35计算机网络与信息安全技术研究中心36其它分组加密算法•三重DES、IDEA、RC5、RC6、Blowfish、CAST、RC2•AES算法:–为AES开发Rijndael算法的是两位来自比利时的密码专家Joandaemen博士、VincentRijmen计算机网络与信息安全技术研究中心371.密码体系概述2.古典密码3.对称密钥密码4.公开密钥密码5.数字签名与摘要函数计算机网络与信息安全技术研究中心38公钥加密模型计算机网络与信息安全技术研究中心39公钥密码体制•公钥密码又称为双钥密码和非对称密码–1976年由Diffie和Hellman在其“密码学新方向”一文中提出的。{见划时代的文献W.DiffieandM.E.Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654}•单向陷门函数是满足下列条件的函数f–给定x计算y=f(x)是容易的；–给定y,计算x使y=f(x)是困难的(所谓计算x=f-1(Y)困难是指计算上相当复杂已无实际意义)；–存在δ，已知δ时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的。计算机网络与信息安全技术研究中心40基于公开密钥的加密过程计算机网络与信息安全技术研究中心41基于公开密钥的鉴别过程计算机网络与信息安全技术研究中心42公钥密码实现保密、鉴别•用户拥有自己的密钥对(KU,KR)•保密：A-B：Y=EKUb(X)B：DKRb(Y)=DKRb(EKUb(X))=X•鉴别：–条件：两个密钥中任何一个都可以用作加密而另一个用作解密A–ALL：Y=DKRa(X)ALL：EKUa(Y)=EKUa(DKRa(X))=X•鉴别+保密：A-B：Z=EKUb(DKRa(X))B：EKUa(DKRb(Z))=X计算机网络与信息安全技术研究中心43数论问题•离散对数:–y≡gxmodp–已知g,x,p,计算y是容易的；–已知y,g,p,计算x是困难的。–≡表示amodp=bmodp，称“模P同余”。•素数p的原根(