密码学基础-清华大学讲稿

1密码学基础密码学基础李德全[e-mail],[e-mail]中科院，软件所信息安全国家重点实验室（2005.08.19于清华大学信息楼FIT1-101会议室）2主要内容一、密码简介二、分组密码三、公钥密码四、消息认证3一、密码简介4信息为什么不安全•信息需要共享...•信息需要使用...•信息需要交换...•信息需要传输...5为什么需要密码信息的存储:在公开的地方信息的交换:使用非隐秘介质信息的传输:通过不安全信道6基本概念密码学(Cryptology):是研究信息系统安全保密的科学.¾密码编码学(Cryptography):主要研究对信息进行编码,实现对信息的隐蔽.¾密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造.7基本术语消息被称为明文(Plaintext)。用某种方法伪装消息以隐藏它的内容的过程称为加密(Encrtption)，被加密的消息称为密文(Ciphertext)，而把密文转变为明文的过程称为解密(Decryption)。密码算法(CryptographyAlgorithm):是用于加密和解密的数学函数。密钥（key），加密或解密所需要的除密码算法之外的关键信息.密码员对明文进行加密操作时所采用的一组规则称作加密算法(EncryptionAlgorithm).所传送消息的预定对象称为接收者(Receiver).接收者对密文解密所采用的一组规则称为解密算法(DecryptionAlgorithm).8加密与解密加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(EncryptionKey)和解密密钥(DecryptionKey).明文明文密文加密算法解密算法密钥密钥9加密通信模型密码学的目的：发方和收方两个人在不安全的信道上进行通信，而敌方（攻击者）不能理解他们通信的内容。发方加密机解密机收方安全信道密钥源攻击者xyxk10密码体制密码体制：它是一个五元组（P,C,K,E,D)满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）*（4）任意k∈K,有一个加密算法和相应的解密算法，使得和分别为加密解密函数，满足dk(ek(x))=x,这里x∈P。Eek∈Ddk∈CPek→:PCdk→:11密码算法分类基于密钥的算法，按照密钥的特点分类：¾对称密码算法（symmetriccipher)：又称传统密码算法（conventionalcipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法。¾非对称密钥算法（asymmetriccipher):加密密钥和解密密钥不相同。如果从一个很难推出另一个。又称公开密钥算法（public-keycipher)。公开密钥算法用一个密钥进行加密,而用另一个进行解密.其中的加密密钥可以公开,又称公开密钥（publickey)，简称公钥.解密密钥必须保密又称私人密钥（privatekey)私钥简称私12对称密钥密码又可分为¾分组密码（也称块密码）每次对一块数据加密多数网络加密应用DES,IDEA,RC6,Rijndael¾流密码（序列密码）每次对一位或一字节加密13密码学的起源和发展三个阶段：•1949年之前密码学是一门艺术•1949～1975年密码学成为科学•1976年以后密码学的新方向——公钥密码学14密码学的起源隐写术(steganography):通过隐藏消息的存在来保护消息.a.隐形墨水b.字符格式的变化c.图形图像15古典密码代替密码（substitutioncipher)置换密码(permutationcipher)，又称换位密码（transpositioncipher)16古典密码•单表替换密码的破译•通过字母的使用频率破译17古典密码移位密码移12位：移3位，即Caesar密码18古典密码移位密码分析给定加密的消息:PHHWPHDIWHUWKHWRJDSDUWB如果移1位得：QIIXQI….如果移2位得：RJJYRJ….…如果移23位得：meetmeafterthetogaparty可能尝试的密钥只有２6个,而事实上，还有一个是不变，因此，昀多尝试25次即可得到明文！19古典密码仿射密码加密函数取形式为y=e(x)=ax+b(mod26),a,b,x,y∈Z/(26)，要求唯一解的充要条件是gcd(a,26)=1加密函数取形式为：x=dk(y)=a-1(y-b)(mod26)可能的密钥是26*12=311个20二、分组密码21密码的设计原则信息的保密取决于密钥的保密，加密算法可以公开——一切秘密寓于密钥之中（Kerckhoff假设）22分组密码设计要求‹Diffusion(扩散)密文没有统计特征，明文一位影响密文的多位，密钥的一位也影响密文的多位‹Confusion(混淆)明文与密文、密钥与密文的依赖关系充分复杂‹结构简单、易于分析23实现方面的设计原则软件实现的要求：使用子块和简单的运算。密码运算在子块上进行，要求子块的长度能自然地适应软件编程，如8、16、32比特等。应尽量避免按比特置换，在子块上所进行的密码运算尽量采用易于软件实现的运算。昀好是用处理器的基本运算，如加法、乘法、移位等。硬件实现的要求：加密和解密的相似性，即加密和解密过程的不同应仅仅在密钥使用方式上，以便采用同样的器件来实现加密和解密，以节省费用和体积。尽量采用标准的组件结构，以便能适应于在超大规模集成电路中实现。24分组密码的操作模式电子密码本ECB(electroniccodebookmode)密码分组链接CBC(cipherblockchaining)密码反馈CFB(cipherfeedback)输出反馈OFB(outputfeedback)25电子密码本（ECB）Ci=EK(Pi)⇔Pi=DK(Ci)26密码分组链接CBC•Ci=EK(Ci-1⊕Pi)⇔Pi=EK(Ci)⊕Ci-127CBC特点•没有已知的并行实现算法•能隐藏明文的模式信息–需要共同的初始化向量IV–相同明文Ö不同密文–初始化向量IV可以用来改变第一块•对明文的主动攻击是不容易的–信息块不容易被替换、重排、删除、重放–误差传递：密文块损坏Ö两明文块损坏安全性好于ECB适合于传输长度大于64位的报文，还可以进行用户鉴别,是大多系统的标准如SSL、IPSec采用的模式28密文反馈CFB模式•CFB:分组密码Ö流密码Si为移位寄存器,j为流单元宽度加密:Ci=Pi⊕(EK(Si)的高j位)Si+1=(Sij)|Ci解密:Pi=Ci⊕(EK(Si)的高j位)Si+1=(Sij)|Ci29密文反馈CFB30输出反馈模式（OFB）31分组密码的分析方法根据攻击者所掌握的信息,可将分组密码的攻击分为以下几类:–唯密文攻击–已知明文攻击–选择明文攻击•攻击的复杂度–数据复杂度:实施该攻击所需输入的数据量–处理复杂度:处理这些数据所需要的计算量32三、公钥密码33基本思想加密与解密由不同的密钥完成(KP,KS)加密:XÎY:Y=EKP(X)解密:YÎX:X=DKS(Y)=DKS(EKP(X))从解密密钥得到加密密钥在计算上是不可行的34公钥密码学的历史76年Diffie和Hellman发表了“密码学的新方向”，奠定了公钥密码学的基础公钥技术是二十世纪昀伟大的思想之一改变了密钥分发的方式可以广泛用于数字签名和身份认证服务78年，RSA算法PKI35公钥算法的条件公钥算法的条件：产生一对密钥是计算可行的已知公钥和明文，产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者，利用公钥来推断私钥是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选)加密和解密的顺序可交换36如何设计一个公钥算法公钥和私钥必须相关，而且从公钥到私钥不可推断必须要找到一个难题，从一个方向走是容易的，从另一个方向走是困难的如何把这个难题跟加解密结合起来计算可行和不可行的界37公钥密码学的研究情况与计算复杂性理论密切相关计算复杂性理论可以提供指导但是需求不尽相同•计算复杂性通常针对一个孤立的问题进行研究•而公钥密码学往往需要考虑一些相关的问题比如，密码分析还需要考虑已知明文、选择明文等相关的情形讨论的情形不同•计算复杂性考虑昀坏的情形•而对于公钥密码学则是不够的一个困难问题必然会导致一个保密性很好的密码系统吗？不一定，还需要有好的构造38背包(knapsack)问题0-1背包问题：给定一个正整数S和一个背包向量A=(a1,…,an)，其中ai是正整数，求满足方程S=∑aixi的二进制向量X=(x1,…,xn)。这是一个NP完全问题，解决这个问题所需要的时间与n呈指数增长背包问题用于公钥密码学奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能把易解的背包问题修改成难解的背包问题•公开密钥使用难解的背包问题•私钥使用易解的背包问题39易解的背包问题——超递增背包满足下列条件的背包ai∑aj(j=1,…,i-1)这样的背包也被称为简单背包求解从昀大的ai开始，如果S大于这个数，则减去ai,记xi为1，否则记xi为0如此下去，直到昀小的ai例如背包序列{2,3,6,13,27,52}求解70的背包•结果为{2,3,13,52}•所以，密文70对应的明文为11010140转换背包简单背包用作私钥如何产生相应的公钥——转换做法：选择一个整数m∑ai(i=1,…,n)然后选择一个与m互素的整数w，然后ai’=wai(modm)(i=1,…,n)这里的ai’是伪随机分布的这样得到的背包是非超递增背包41基于背包问题的公钥密码系统——MH公钥算法加密将明文分为长度为n的块X=(x1,…,xn)然后用公钥A’=(a1’,…,an’)，将明文变为密文SS=E(X)=∑ai’xi解密先计算S’=w-1Smodm再求解简单背包问题S’=∑aixi42背包密码系统的意义是第一个公钥密码系统有较好的理论价值在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷43RSA算法1977年由RonRivest、AdiShamir和LenAdleman发明，1978年公布是一种分组加密算法。明文和密文在0~n-1之间,n是一个正整数应用昀广泛的公钥密码算法只在美国申请专利，且已于2000年9月到期44RSA算法描述分组大小为k,2kn≤2k+1加密:C=Memodn解密:M=Cdmodn=Medmodn公钥:KP={e,n},私钥:KS={d,n}上述算法需要满足以下条件:能够找到e,d,n,使得Medmodn=M,对所有Mn计算Me和Cd相对容易从e和n得到d是在计算上不可行的45公钥密码与私钥密码公钥密码由于速度慢，直接用于加密效率低当单向通信的时候，可以采用公钥和私钥结合的办法。如设B的公开密钥为Pb，A要向B发送消息m。则A可以用私钥k加密m，再用Pb加密k，同时把E（k，m）和E（Pb，k）发给B.当双向通信时，A、B可以利用公钥协商一个私钥密码的密钥。46四、消息认证47消息认证在网络通信中，有一些针对消息内容的攻击方法伪造消息窜改消息内容改变消息顺序消息重放或者延迟消息认证：对收到的消息进行验证，证明确实是来自声称的发送方，并且没有被修改过。如果在消息中加入时间及顺序信息，则可以完成对时间和顺序的认证48消息认证的四种方式Messageencryption：用整个消息的密文作为认证标识接收方必须能够识别错误MAC：一个公开函数，加上一个密钥产生一个固定长度的值作为认证标识Hashfunction：一个公开函数将任意长度的消息映射到一个固定长度的散列值，作为认证标识数字签名49Hash函数Hash是一种直接产生认证码的方法Hash函数:h=H(x),要求:可作用于任何尺寸数据且均产生定长输出H(x)能够快速计算单向性:给定h，找到x使h=H(x)在计算上不可行WeakCollisionResistence(