现代密码学-第1章概论

1现代密码学21世纪高等学校计算机规划教材ModernCryptography彭代渊信息科学与技术学院[e-mail]2009.9-2010.1作者：何大可彭代渊唐小虎何明星梅其祥出版社：人民邮电出版社2现代密码学ModernCryptography彭代渊信息科学与技术学院[e-mail]2009年9月第1章概论3第1章概论1.1信息系统安全与密码技术1.2密码系统模型和密码体制1.3几种简单密码体制1.4初等密码分析1.5密码学的信息论基础1.6密码学的复杂性理论基础41.1信息系统安全与密码技术信息时代农业革命工业革命信息革命20世纪80年代美国TofflerA.著《第三次浪潮》，预言：计算机网络的建立与普及将彻底改变人类的生存和生活模式信息、资源、能源是人类生存的三大支柱51.1信息系统安全与密码技术民用Internet普及电子政务电子商务电子金融军事第三次军事革命信息战网络战61.1信息系统安全与密码技术信息时代的安全威胁网络特洛伊木马黑客攻击后门、隐蔽通道计算机病毒拒绝服务攻击内部、外部泄密蠕虫逻辑炸弹信息丢失、篡改、销毁71.1信息系统安全与密码技术安全威胁特点网络遭受攻击数量与日俱增网络病毒在全球范围内高速扩散网络垃圾邮件成为新的焦点网络犯罪（经济、政治）触目惊心81.1信息系统安全与密码技术安全威胁的危害使用Internet的困扰经济巨大损失国家安全受到威胁信息安全技术的落后严重阻碍了社会的发展！9各国政府的对策2002年11月27日美国总统签署《网络安全法案》。在未来几年中政府为大学拨款9亿美元，用于成立计算机安全中心，招收研究生进行安全研究。我国党的十五届五中全会明确指出，大力推进国民经济和社会信息化是覆盖现代化建设全局的战略举措。要以信息化带动工业化。在《科技教育发展“十五”重点专项规划（高技术产业发展规划）》中明确提出攻克信息保护、隐患发现、安全反应等关键技术，为国家信息基础建设提供技术支撑。1999年国务院颁布商用密码管理条例，对密码的管理使用进行了具体规定。1.1信息系统安全与密码技术101.1信息系统安全与密码技术信息安全的基本属性信息安全（informationSecurity）、数据安全（dataSecurity）机密性（confidentiality）完整性（integrity）认证性（nonrepudiation）——也称“不可否认性”或“抗抵赖”可用性（availability）公平性（fairness）可控性（controllability）111.1信息系统安全与密码技术对信息安全的威胁或攻击:对信息属性的侵害属于人为故意的威胁或攻击中，窃取、破译是对机密性的侵害篡改是对完整性的侵害伪造、重放是对认证性的侵害干扰、占用、资源耗尽以至摧毁信息处理器或载体是对可用性的侵害在电子媒体商品的网上交易中，获得商品后不按时付款或者收取货款后不按时提供商品，是对公平性的侵害12侵害对象威胁或攻击手段案例机密性入侵系统取得高级授权猜测口令，系统漏洞，安置木马破译密码穷举法搜索DES密钥，对密码器件的边信道攻击（side-channelattack）完整性插入、删除、篡改用原消息m的MD5碰撞m’取代m可用性信道干扰无线干扰摧毁系统硬件微波炸弹，处理器内潜藏破坏性指令，嗜晶片微生物扰乱以至摧毁系统软件计算机病毒用户恶意占用内部用户资源占用、资源耗尽业务拒绝“轰炸”端口认证性发送方身份假冒，接收抵赖中间人攻击破坏收发审计记录公平性非对等的密钥协商单方面控制生成密钥参数利用非公平交易协议获取利益中途终止不满足“公平性”的交易协议可控性破坏“密钥托管”，阻止“匿名撤消”抗内容检测过滤的“穿透”阻止司法取证131.1信息系统安全与密码技术网络通信系统安全性分析构架U1U2UiTAAAAAA141.1信息系统安全与密码技术信息安全关键技术——密码学理论与技术密码学通信理论计算机科学数学信息安全技术15第1章概论1.1信息系统安全与密码技术1.2密码系统模型和密码体制1.3几种简单密码体制1.4初等密码分析1.5密码学的信息论基础1.6密码学的复杂性理论基础161.2密码系统模型和密码体制Shannon的保密系统模型171.2密码系统模型和密码体制现代密码系统模型信源M加密器cm1kE非法接入者密码分析员（窃听者）搭线信道（主动攻击）搭线信道（被动攻击）解密器接收者mc2kD密钥源密钥源1K2Kmm'mc'c1k2k信道密钥信道181.2密码系统模型和密码体制密码体制(Cryptosystem)——六元组(M,C,K1,K2,E,D)明文空间:M，mM称为明文(plaintext)密文空间:C，cC称为密文(ciphertext)加密密钥空间:K1，k1K1称为加密密钥(encryptionkey)解密密钥空间:K2k2K2称为解密密钥(decryptionkey)密钥(key):k=(k1,k2)19密码体制(Cryptosystem)——六元组(M,C,K1,K2,E,D)加密变换簇:E1111,,:)kkkEE(encryptionmap,function,algorithm加密变换（映射、函数、算法）KEMC解密变换簇:D2222,,:)kkkDD(decryptionmap,function,algorithm解密变换（映射、函数、算法）KDCM1.2密码系统模型和密码体制20密码体制(Cryptosystem)加密变换与解密变换的关系..))((,,,),(1212212121的左逆变换称为有：满足kkkkkkEDmmEDmDEkkkMDEKK)(1mEckmcDk)(2)(1mEckmMCcmcDk)(21.2密码系统模型和密码体制21密码体制系统的分类对称密码体制(symmetriccryptosystem)k=k1=k2或k1k2单钥、私钥(one-key,privatekey)密码体制加密器cmkE解密器mckD密钥产生器mckk密钥信道明文密文解读后明文密钥产生器1.2密码系统模型和密码体制22密码体制系统的分类对称密码体制(symmetriccryptosystem)分组密码(blockcipher)将明文消息分为包含若干个符号的组，在选定密钥后使用固定的加密变换对明文分组逐组地进行加密。例如，DES(1977),AES(2001)流密码(streamcipher)明文：m=m1m2m3…..密钥：k=k1k2k3….加密：c1=Ek1(m1),c2=Ek2(m2),c3=Ek3(m3),….密文：c=c1c2c3….例如，GSM移动台（手机）到基站BS之间无线传输中使用的加密算法A5/1是一种流密码1.2密码系统模型和密码体制23非对称密码体制(asymmetriccryptosystem)双钥、公钥(two-key,publickey)密码体制k1k2或k1不能k2公钥:k1=pk；私钥:k2=skBpkEBskDmc明文密文用户A用户Bm搭线信道',...h'm查找B的公开密钥Bpk使用自己的秘密密钥Bsk1.2密码系统模型和密码体制241.2密码系统模型和密码体制密码系统的设计原则设计加密函数与解密函数的学科称为密码编码学(Cryptography)、密码学或保密学。具有某种安全性理论上不可破实际上不可破Kerckhoff假设：系统的保密性不依赖于对加密体制或加（解）密算法的保密，而仅依赖于密钥的保密。加密和解密算法适用于密钥空间的全部元素系统便于实现和使用方便251.2密码系统模型和密码体制密码学发展简史密码学发展史简图远古1949年1976年1977年1949年现代密码古典密码1976年私钥密码公钥密码1977年商用密码26密码学发展简史古典密码时期(—1949)特定应用领域：军事、政治、外交神秘性艺术性现代密码学(1949—)：密码技术成为一门学科著名论文:Communicationtheoryofsecrecysystems,BellSyst.Tech.J.,Volume28,656-715,1949.仙农(C.D.Shannon:1916-2001)1.2密码系统模型和密码体制27密码学发展简史公钥密码学(1976—)计算机网络环境中的应用W.Diffie和M.E.Hellman提出公钥密码的思想(1976)著名论文：W.DiffieandM.E.Hellman,Newdirectionincryptography,IEEETran.OnInformationTheory,IT-22,(6),644-654,1976.密码学的商业应用(1977—)1977：美国国家标准局(NationalBureauofStandards)颁布数据加密标准DES(DataEncryptionStandard)1994：美国政府颁布数字签名标准DSS(DataSignatureStandard)2001：美国政府颁布高级加密标准AES(AdvancedEncryptionStandard)1.2密码系统模型和密码体制28代换密码(substitutioncipher)明文空间:M=ZqL明文字母表:Zq={0,1,…,q-1}明文组(L-报文):m=(m0,m1,…,mL-1)ZqL密文空间:C=Zq’L’，密文字母表:Zq’={0,1,…,q’-1}密文组:c=(c0,c1,…,cL’-1)Zq’L’密钥空间:K，kK加密变换:fk:ZqLZq’L’任给mZqL，记fk(m)=f(k,m)=c.设f是单射，则f的逆就是解密变换：Dk(c)=f-1.1.2密码系统模型和密码体制29代换密码(substitutioncipher)q=q’L=L’:f可为1-1映射；无数据扩张LL’:f可为1对多映射；有数据扩张LL’:f不可逆，不能作加密映射；数据压缩q=q’,Zq=Zq’L=L’=1单表代换（monoalphabeticsubstitute）对所有的明文字母，都用一种固定的代换进行加密。多表代换（polyalphabeticsubstitute）对所有的明文字母，用一个以上的代换表进行加密。1.2密码系统模型和密码体制30第1章概论1.1信息系统安全与密码技术1.2密码系统模型和密码体制1.3几种简单密码体制1.4初等密码分析1.5密码学的信息论基础1.6密码学的复杂性理论基础311.3几种简单密码体制换位密码（transpositioncipher）明文：m=thesimplestpossibletranspositionciphers分成长度为5的组：m=thesi|mples|tposs|iblet|ransp|ositi|oncip|hersx加密变换：将各组内字符按位置下标号（0~4）实施下述置换（permutation）0123414302kE密文：c=STIEHEMSLPSTSOPEITLBSRPNATOIISIOPCNSHXRE32换位密码（transpositioncipher）Ek的逆置换：解密：密文：c=STIEHEMSLPSTSOPEITLBSRPNATOIISIOPCNSHXRE明文：m=thesimplestpossibletranspositionciphersx换位密码0123430421kD0123414302kE密钥量：|K|=L！33仿射密码（affinecipher）M=C=ZqK={(a,b)|(a,b)ZqZq,gcd(b,q)=1}加密变换Ek(m)=a+bmmodq(m