密码学基础

信息安全InformationSecurity武汉大学计算机学院武汉大学信息安全研究所傅建明博士[e-mail]密码学基础知识•密码学概述•传统的密码学•对称密码•公钥密码•序列密码密码学概述•通信保密（COMSEC）：60-70年代信息保密•计算机安全（COMPUSEC）:60年代机密性、访问控制、认证,TCSEC标准•信息安全（INFOSEC）：80-90年代机密性、完整性、可用性、不可否认性等•信息保障（IA）：90年代-至今信息安全发展的四个阶段年代通信安全发展时期计算机安全发展时期信息安全发展时期信息安全保障发展时期安全保障能力•基本的通讯模型•通信的保密模型通信安全-60年代（COMSEC）发方收方信源编码信道编码信道传输通信协议发方收方敌人信源编码信道编码信道传输通信协议密码•信息安全的三个基本方面–保密性Confidentiality即保证信息为授权者享用而不泄漏给未经授权者。–完整性Integrity•数据完整性，未被未授权篡改或者损坏•系统完整性，系统未被非授权操纵，按既定的功能运行–可用性Availability即保证信息和信息系统随时为授权者提供服务，而不要出现非授权者滥用却对授权者拒绝服务的情况。信息安全的含义(80-90年代)•信息安全的其他方面–信息的不可否认性Non-repudiation：要求无论发送方还是接收方都不能抵赖所进行的传输–鉴别Authentication鉴别就是确认实体是它所声明的。适用于用户、进程、系统、信息等–审计Accountability•确保实体的活动可被跟踪–可靠性Reliability•特定行为和结果的一致性安全需求的多样性•保密性•一致性•可用性•可靠性•可认证，真实性•责任定位，审计性•高性能•实用性•占有权•……如何保证这些需求？•美国人提出的概念:InformationAssurance•保护（Protect）•检测（Detect）•反应（React）•恢复（Restore）保护Protect检测Detect反应React恢复Restore信息保障•电子邮件@[e-mail]•自动提款机•电话卡:IP卡、201电话卡•银行取钱•信用卡购物密码从军事走向生活•密码学(Cryptology):是研究信息系统安全保密的科学.密码编码学(Cryptography):主要研究对信息进行编码,实现对信息的隐蔽.密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造.基本概念•量子密码(单量子不可复制定理)•DNA密码•化学密码•……密码新技术•消息被称为明文(Plaintext)。用某种方法伪装消息以隐藏它的内容的过程称为加密(Encrtption)，被加密的消息称为密文(Ciphertext)，而把密文转变为明文的过程称为解密(Decryption)。•对明文进行加密操作的人员称作加密员或密码员(Cryptographer).•密码算法(CryptographyAlgorithm):是用于加密和解密的数学函数。•密码员对明文进行加密操作时所采用的一组规则称作加密算法(EncryptionAlgorithm).•所传送消息的预定对象称为接收者(Receiver).•接收者对密文解密所采用的一组规则称为解密算法(DecryptionAlgorithm).加解密过程示意图•加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(EncryptionKey)和解密密钥(DecryptionKey).明文明文密文加密算法解密算法密钥密钥密码学的目的：Alice和Bob两个人在不安全的信道上进行通信，而破译者Oscar不能理解他们通信的内容。加密通信的模型Alice加密机解密机Bob安全信道密钥源Oscarxyxk•密码体制：它是一个五元组（P,C,K,E,D)满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）*（4）任意k∈K,有一个加密算法和相应的解密算法，使得和分别为加密解密函数，满足dk(ek(x))=x,这里x∈P。EekDdkCPek:PCdk:密码体制（系统）•按照保密的内容分:受限制的（restricted)算法:算法的保密性基于保持算法的秘密。基于密钥（key-based)的算法:算法的保密性基于对密钥的保密。----现代密码理论密码算法分类-i•基于密钥的算法，按照密钥的特点分类：对称密码算法（symmetriccipher)：又称传统密码算法（conventionalcipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法。非对称密钥算法（asymmetriccipher):加密密钥和解密密钥不相同，从一个很难推出另一个。又称公开密钥算法（public-keycipher)。•公开密钥算法用一个密钥进行加密,而用另一个进行解密.其中的加密密钥可以公开,又称公开密钥（publickey)，简称公钥.解密密钥必须保密,又称私人密钥（privatekey)私钥.简称私钥。密码算法分类-ii•按照明文的处理方法：分组密码（blockcipher):将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。流密码（streamcipher):又称序列密码.序列密码每次加密一位或一字节的明文，也可以称为流密码。序列密码是手工和机械密码时代的主流密码算法分类-iii•对称密钥密码又可分为：分组密码每次对一块数据加密多数网络加密应用DES,IDEA,RC6,Rijndael流密码每次对一位或一字节加密手机One-timepadding,Vigenére,Vernam密码算法分类-iv•公开密钥密码:大部分是分组密码，只有概率密码体制属于流密码每次对一块数据加密数字签名,身份认证RSA,ECC,ElGamal加密解密速度慢密码算法分类-v三个阶段：•1949年之前密码学是一门艺术•1949～1975年密码学成为科学•1976年以后密码学的新方向——公钥密码学密码学的起源和发展-i密码学的起源•隐写术(steganography):通过隐藏消息的存在来保护消息.a.隐形墨水b.字符格式的变化c.图象图像•(象形文字的修改)ModifiedHieroglyphics,c.1900B.C.密码学的第一个例子是对标准书写符号的修改example-i我去君留十载中爱无南北与西东万株松树青山上洁白孤高生不同example-ii•SpartanScytale,c.500B.C.斯巴达人用于加解密的一种军事设备发送者把一条羊皮螺旋形地缠在一个圆柱形棒上思想：置换（permutation)•Polybius’Checkerboard,205~123B.C.•明文:POLYBIUS•密文:3534315412244543123451ABCDE2FGHIJK3LMNOP4QRSTU5VWXYZexample-iii•CaesarCipher,c.50B.C.ABCDEFG……XYZDEFGHIJ……ABC明文:Caesarcipherisashiftsubstitution密文:FDHVDUFLSKHULVDVKLIWVXEVWLWXWLRQexample-iV•Nomenclator代码本c.1400字母、符号、单词、短语代码代码字母、符号、单词、短语应用：WorldWarIIExample-VExample–Con’t•网格加密法：中国–例：密文：王先生：来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。弟：李明2001年11月7日•网格加密法：中国–例：密文：王先生：来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。弟：李明2001年11月7日明文：情报在雨伞把中。•兽栏法：–明文：System–密文：ABCDEFGHIJ.K..LM.N..OP.Q..RS:T::UV:W::XY:Z::.：：：：.密文字母表：古典实例•双轨密码：1861~1865年例：明文：DiscreteandSystem密文：DsrtadytmIceensse加密方法：DsrtadytmiceensseBeale密码C=115732481837524917316265722715…M=Ihavedeposited…(1)When,inthecourseofhumanevents,itbecomesnecessary(11)Foronepeopletodissolvethepoliticalbandswhichhave(21)Connectedthemwithanother,andtoassumeamongthePowers(31)Oftheearththeseparateandequalstationtowhich(41)TheLawsofNatureandofNature’sGodentitlethem,(51)Adecentrespecttotheopinionsofmankindrequiresthat(61)Theyshoulddeclarethecauseswhichimpelthemtothe(71)separation.Weholdthesetruthstobeself-evident,that(81)Allmenarecreatedequal,thattheyareendowedby(91)TheirCreatorwithcertainunalienablerights,thatamong(99)TheseareLife,Liberty,andthepursuitofHappiness.古典密码古典密码（6）•Vigenère密码是一种基于移位字母表的周期代替密码，它的密钥K由一个字母序列来指定：k＝k1…kd。其中：ki（i＝1，…，d）给出了第i个字母表的移动位数，即fi(a)＝(a+ki)modn.•例如：明文INTELLIGENT用密钥PLAY加密为：M＝INTELLIGENTK＝PLAYPLAYPLAEk(M)＝XYTCAMIETYT•例设m＝6，且密钥字是CIPHER,这相应于密钥。假定明文串是thiscryptosystemisnotsecure首先将明文串转化为数字串，按6个一组分段，然后模26“加”上密钥字得：86252315211747158217218871915222182301747158224181419152491219191211747158218812419181982582215174715822418191413192522158241720使用Vigenère表可以方便地进行加密和解密。相应的密文串将是:VPXZGIAXIVWPUBTTMJPWIZITWZT解密过程与加密过程类似,不同的只是进行模26减,而不是模26加。明文ABCDEFGHIJKLMNOPQRSTUVWXYZAABCDEFGHIJKLMNOPQRSTUVWXYZBBCDEFGHIJKLMNOPQRSTUVWXYZACCDEFGHIJKLMNOPQRSTUVWXYZABDDEFGHIJKLMNOPQRSTUVWXYZABCEEFGHIJKLMNOPQRSTUVWXYZABCDFFGHIJKLMNOPQRSTUVWXYZABCDEGGHIJKLMNOPQRSTUVWXYZABCDEFHHIJKLMNOPQRSTUVWXYZABCDEFGIIJKLMNOPQRSTUVWXYZABCDEFGHJJKLMNOPQRSTUVWXYZABCDEFGHIKKLMNOPQRSTUVWXYZABCDEFGHIJLLMNOPQRSTUVWXYZABCDEFGHIJKMMNOPQRSTUVWXYZABCDEFGHIJKLNN