何大可 彭代渊 唐小虎 何明星 梅其祥 现代密码学-第1章概论-20091010

1,现代密码学,21世纪高等学校计算机规划教材,Modern Cryptography,彭代渊 信息科学与技术学院 dypengswjtu.edu.cn 2009.9-2010.1,作 者：何大可 彭代渊 唐小虎 何明星 梅其祥 出版社：人民邮电出版社,2,现代密码学 Modern Cryptography,彭代渊 信息科学与技术学院 dypengswjtu.edu.cn 2009年9月,第1章 概论,3,第1章 概论,1.1 信息系统安全与密码技术 1.2 密码系统模型和密码体制 1.3 几种简单密码体制 1.4 初等密码分析,1.5 密码学的信息论基础 1.6密码学的复杂性理论基础,4,1.1 信息系统安全与密码技术,信息时代 农业革命工业革命信息革命 20世纪80年代美国Toffler A. 著第三次浪潮，预言： 计算机网络的建立与普及将彻底改变人类的生存和生活模式 信息、资源、能源是人类生存的三大支柱,5,1.1 信息系统安全与密码技术,民用 Internet普及 电子政务 电子商务 电子金融 军事 第三次军事革命 信息战 网络战,6,1.1 信息系统安全与密码技术,信息时代的安全威胁,7,1.1 信息系统安全与密码技术,安全威胁特点 网络遭受攻击数量与日俱增 网络病毒在全球范围内高速扩散 网络垃圾邮件成为新的焦点 网络犯罪（经济、政治）触目惊心,8,1.1 信息系统安全与密码技术,安全威胁的危害 使用Internet的困扰 经济巨大损失 国家安全受到威胁 信息安全技术的落后严重阻碍了社会的发展！,9,各国政府的对策 2002年11月27日美国总统签署网络安全法案。在未来几年中政府为大学拨款9亿美元，用于成立计算机安全中心，招收研究生进行安全研究。 我国 党的十五届五中全会明确指出，大力推进国民经济和社会信息化是覆盖现代化建设全局的战略举措。要以信息化带动工业化。 在科技教育发展“十五”重点专项规划（高技术产业发展规划）中明确提出攻克信息保护、隐患发现、安全反应等关键技术，为国家信息基础建设提供技术支撑。 1999年国务院颁布商用密码管理条例，对密码的管理使用进行了具体规定。,1.1 信息系统安全与密码技术,10,1.1 信息系统安全与密码技术,信息安全的基本属性 信息安全（information Security）、数据安全（data Security） 机密性（confidentiality） 完整性（integrity） 认证性（nonrepudiation）也称“不可否认性”或“抗抵赖” 可用性（availability） 公平性（fairness） 可控性（controllability）,11,1.1 信息系统安全与密码技术,对信息安全的威胁或攻击: 对信息属性的侵害 属于人为故意的威胁或攻击中，窃取、破译是对机密性的侵害 篡改是对完整性的侵害 伪造、重放是对认证性的侵害 干扰、占用、资源耗尽以至摧毁信息处理器或载体是对可用性的侵害 在电子媒体商品的网上交易中，获得商品后不按时付款或者收取货款后不按时提供商品，是对公平性的侵害,12,13,1.1 信息系统安全与密码技术,网络通信系统安全性分析构架,14,1.1 信息系统安全与密码技术,信息安全关键技术 密码学理论与技术,15,第1章 概论,1.1 信息系统安全与密码技术 1.2 密码系统模型和密码体制 1.3 几种简单密码体制 1.4 初等密码分析 1.5 密码学的信息论基础 1.6密码学的复杂性理论基础,16,1.2 密码系统模型和密码体制,Shannon的保密系统模型,17,1.2 密码系统模型和密码体制,现代密码系统模型,18,1.2 密码系统模型和密码体制,密码体制(Cryptosystem) 六元组 (M, C, K1, K2, E, D) 明文空间:M ，mM 称为明文(plaintext) 密文空间:C ，cC 称为密文(ciphertext) 加密密钥空间:K1 ， k1K1 称为加密密钥(encryption key) 解密密钥空间: K2 k2K2 称为解密密钥(decryption key) 密钥(key): k=(k1, k2),19,密码体制(Cryptosystem) 六元组 (M, C, K1, K2, E, D) 加密变换簇: E,解密变换簇: D,1.2 密码系统模型和密码体制,20,密码体制(Cryptosystem) 加密变换与解密变换的关系,1.2 密码系统模型和密码体制,21,密码体制系统的分类 对称密码体制(symmetric cryptosystem) k=k1=k2 或 k1 k2 单钥、私钥 (one-key, private key)密码体制,1.2 密码系统模型和密码体制,22,密码体制系统的分类 对称密码体制(symmetric cryptosystem) 分组密码(block cipher) 将明文消息分为包含若干个符号的组，在选定密钥后使用固定的加密变换对明文分组逐组地进行加密。 例如， DES(1977), AES(2001) 流密码(stream cipher) 明文：m=m1m2m3 密钥：k=k1k2k3. 加密：c1=Ek1(m1), c2=Ek2(m2), c3=Ek3(m3),. 密文：c=c1c2c3 . 例如，GSM移动台（手机）到基站BS之间无线传输 中使用的加密算法A5/1是一种流密码,1.2 密码系统模型和密码体制,23,非对称密码体制(asymmetric cryptosystem) 双钥、公钥 (two-key, public key)密码体制 k1k2 或 k1不能k2 公钥: k1=pk； 私钥: k2=sk,1.2 密码系统模型和密码体制,24,1.2 密码系统模型和密码体制,密码系统的设计原则 设计加密函数与解密函数的学科称为密码编码学 (Cryptography)、密码学或保密学。 具有某种安全性 理论上不可破 实际上不可破 Kerckhoff假设：系统的保密性不依赖于对加密体制或加（解）密算法的保密，而仅依赖于密钥的保密。 加密和解密算法适用于密钥空间的全部元素 系统便于实现和使用方便,25,1.2 密码系统模型和密码体制,密码学发展简史 密码学发展史简图,26,密码学发展简史 古典密码时期(1949) 特定应用领域：军事、政治、外交 神秘性 艺术性 现代密码学(1949)： 密码技术成为一门学科,著名论文: Communication theory of secrecy systems, Bell Syst. Tech. J., Volume 28, 656-715, 1949. 仙农(C. D. Shannon: 1916-2001),1.2 密码系统模型和密码体制,27,密码学发展简史 公钥密码学(1976) 计算机网络环境中的应用 W. Diffie和M. E. Hellman提出公钥密码的思想(1976) 著名论文：W. Diffie and M. E. Hellman, New direction in cryptography, IEEE Tran. On Information Theory, IT-22, (6), 644-654,1976.,密码学的商业应用 (1977) 1977：美国国家标准局(National Bureau of Standards)颁布数据加密标准DES (Data Encryption Standard) 1994：美国政府颁布数字签名标准DSS (Data Signature Standard) 2001：美国政府颁布高级加密标准AES (Advanced Encryption Standard),1.2 密码系统模型和密码体制,28,代换密码(substitution cipher ) 明文空间:M = ZqL 明文字母表: Zq =0,1,q-1 明文组(L-报文) : m=(m0, m1,mL-1)ZqL 密文空间:C = ZqL ， 密文字母表: Zq =0,1,q-1 密文组 : c=(c0, c1,cL-1)ZqL 密钥空间:K ，kK 加密变换: fk : ZqL ZqL 任给mZqL ，记fk(m)= f (k,m)=c. 设f是单射，则f的逆就是解密变换： Dk(c)= f -1.,1.2 密码系统模型和密码体制,29,代换密码(substitution cipher ) q=q L=L: f可为1-1映射；无数据扩张 LL: f不可逆，不能作加密映射；数据压缩 q=q, Zq= Zq L=L=1 单表代换（monoalphabetic substitute） 对所有的明文字母，都用一种固定的代换进行加密。 多表代换（polyalphabetic substitute） 对所有的明文字母，用一个以上的代换表进行加密。,1.2 密码系统模型和密码体制,30,第1章 概论,1.1 信息系统安全与密码技术 1.2 密码系统模型和密码体制 1.3 几种简单密码体制 1.4 初等密码分析 1.5 密码学的信息论基础 1.6密码学的复杂性理论基础,31,1.3 几种简单密码体制,换位密码（transposition cipher） 明文：m= the simplest possible transposition ciphers 分成长度为5的组： m= thesi | mples | tposs | iblet | ransp | ositi | oncip | hersx 加密变换：将各组内字符按位置下标号（04）实施下述置换（permutation）,密文： c=STIEH EMSLP STSOP EITLB SRPNA TOIIS IOPCN SHXRE,32,换位密码（transposition cipher） Ek的逆置换：,解密： 密文：c=STIEH EMSLP STSOP EITLB SRPNA TOIIS IOPCN SHXRE 明文：m= thesi mples tposs iblet ransp ositi oncip hersx,换位密码,密钥量：|K |=L！,33,仿射密码（affine cipher） M =C =Zq K =(a,b) |(a,b) ZqZq, gcd(b,q)=1 加密变换 Ek(m)=a+bm mod q (m Zq) 解密变换 Dk(c)=(c-a)b-1 mod q (c Zq) 密钥量太小，不安全！ 设q=26，|K |=26(26) =2612=312.,1.3 几种简单密码体制,34,k=(0, 1)时，Ek(m)=a+bm=m 为恒等变换 a=0时 Ek(m)=bm 为乘数密码（multiplicative cipher） b=1时 Ek(m)=a+m 为移位代换密码（shift substitution cipher）或加法密码（additive cipher） 全部26个加密变换的代换表合在一起构成一个密文形如26阶对称矩阵的表(该矩阵的第一行、第一列是从A到Z顺序排列的字母), 称为维吉尼亚表(Vigenere Table) Ek(m)=3+m 为凯撒密码（Caesar Cipher）,仿射密码,35,例1.3.1 设密钥k=(3, 7)，则加密变换 Ek(m)=3+7m mod 26 (mZ26), Ek(6)=3+76=45=19 mod 26. 解密变换： Dk(c)=(c-a)b-1=(c-3) 7-1 mod 26. 因为715=105=1 mod 26, 所以7-1=15 mod 26, Dk(c)= (c-3)15=15c-45 =15c+7 mod 26. D