第2章密码学基础详解

第2章密码学基础第2章密码学基础密码学真的有必要吗密码学对称密码学非对称密码学哈希函数数字签名数字证书安全传送文件的含义：确保文件来自正确的发送方接收方能确保在通过Internet传输时，文件没有被修改；只有指定的接收方能够看到文件，其他各方无法看到，防止文件被窃；事后发送方不能否认曾经发送过文件。密的化码艺时学术代前5世纪：明文木棍密文(换位密码)人类有记载的通信密码始于公元前400年。古希腊人是置换密码的发明者。前1世纪：明文字母后移3位密文(替代密码)密码学的发展史密码学的发展密码学是实现认证、加密、访问控制的核心技术密码学的发展9世纪、16世纪：比较现实字母频度与密文字母频率(频度分析法)1918年,一次性便笺密码1881年世界上的第一个电话保密专利出现。电报、无线电的发明使密码学成为通信领域中不可回避的研究课题。密码学的发展二战：恩格玛密码机(第一次用电脑协助破密)在第二次世界大战初期，德国军方启用“恩尼格玛”密码机，盟军对德军加密的信息有好几年一筹莫展，“恩尼格玛”密码机似乎是不可破的。但是经过盟军密码分析学家的不懈努力，“恩尼格玛”密码机被攻破，盟军掌握了德军的许多机密，而德国军方却对此一无所知。太平洋战争中，美军破译了日本海军的密码机，读懂了日本舰队司令官山本五十六发给各指挥官的命令，在中途岛彻底击溃了日本海军，导致了太平洋战争的决定性转折，而且不久还击毙了山本五十六。相反轴心国中，只有德国是在第二次世界大战的初期在密码破译方面取得过辉煌的战绩。因此，我们可以说，密码学在战争中起着非常重要的作用。密码学的发展1977年，DES成为美国国家标准1977年，美国国家标准局公布实施了“美国数据加密标准（DES）”，军事部门垄断密码的局面被打破，民间力量开始全面介入密码学的研究和应用中。民用的加密产品在市场上已有大量出售，采用的加密算法有DES、IDEA、RSA等。1976年,公开密钥思想(密钥分开)1977年,RSA(公钥密码)1985年,量子计算机(解密)密码学的发展三个阶段:1949年以前:数据的安全基于算法保密1949~1975:数据的安全基于密钥的保密1976以后:安全的无密钥传输(公钥密码学)2.1.1密码学的基本概念密码学的分类：密码编码学（Cryptography）密码分析学（Cryptanalysis）密码编码学(Cryptography)，对信息进行编码实现隐蔽信息的一门学问密码分析学(Cryptanalytics)，研究分析破译密码的学问编码密码学主要致力于信息加密、信息认证、数字签名和密钥管理方面的研究。分析密码学主要分析密码算法的弱点，对其进行拷问和攻击以求攻破该密码算法。密码学是计算机科学中唯一一门有着两个平行、对立而又共生的子分支的分支科学概念明文(消息)(Plaintext)：被隐蔽消息。密文(Ciphertext)或密报(Cryptogram)：明文经密码变换成的一种隐蔽形式。加密(Encryption)：将明文变换为密文的过程。解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程。加密员或密码员(Cryptographer)：对明文进行加密操作的人员。密码体制五元组:P(M),C,K,E,DDk(Ek(M))=M加密算法(Encryptionalgorithm)：密码员对明文进行加密时所采用的一组规则。接收者(Receiver)：传送消息的预定对象。解密算法：接收者对密文进行解密时所采用的一组规则。密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密钥和解密密钥。截收者(Eavesdropper)：在信息传输和处理系统中的非授权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。概念信源Mm加密器)(1mEck解密器)(2cDmk接收者m非法接入者搭线信道（主动攻击）C’搭线信道（被动攻击）密码分析员m‘密钥源K1k1密钥源K2k2密钥信道保密系统模型概念保密系统应当满足的要求系统即使达不到理论上是不可破的，即pr{m’=m}=0，也应当为实际上不可破的。就是说，从截获的密文或某些已知明文密文对，要决定密钥或任意明文在计算上是不可行的。系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。这是著名的Kerckhoff原则。加密和解密算法适用于所有密钥空间中的元素。系统便于实现和使用。密码体制分类密码体制有2大类：单钥体制(One-keysystem)：加密密钥和解密密钥相同双钥体制(Twokeysystem)：加密密钥和解密密钥不同密码体制分类单钥体制加密器EK解密器DK密文明文明文K密钥产生器K单钥体制或私钥体制(privatekeysystem)每个用户事先约定共同选定的密钥k，数据的加密和解密使用相同的密钥。密码体制分类单钥体制单钥体制主要研究问题：密钥产生(Keygeneration)，密钥管理(Keymanagement)。分类：流密码(Streamcipher)分组密码(Blockcipher)单钥体制不仅可用于数据加密，也可用于消息的认证。密码体制分类双钥体制双钥体制或公钥体制(Publickeysystem)每个用户都有一对选定的密钥(公钥k1；私钥k2)，公开的密钥k1可以像电话号码一样进行注册公布。加密器EK解密器DK密文明文明文K1密钥产生器K2密钥产生器公钥体制的主要特点加密和解密能分开可以实现多个用户加密的消息只能由一个用户解读（用于公共网络中实现保密通信）只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。无需事先分配密钥。2.1.2传统加密技术1置换密码依据一定的规则，明文字母被相应替代移位密码（模运算）加密：Ek(x)=(x+k)mod26解密：Dk(y)=(y-k)mod26x:明文字母、y:密文字母、k:密钥恺撒密码就是移位密码（k＝3）缺点：密钥空间小，容易被破解（穷举法）2.1.2传统加密技术单表代换密码用一个表将一个明文字母对应一个密文字母，加解密则按照此表相应转换字母。缺点：对应关系固定，容易被频度分析法破解多表代换密码（vigenere密码）密钥K不单一，同一密文字母可能对应不同明文字母加密变换：ci≡(mi+ki)mod26解密变换：mi≡(ci-ki)mod26密钥空间较前两种大，较安全2.1.2传统加密技术2代换密码保持明文不变，将字母顺序重新排列倒序密码：颠倒明文书写顺序。abamimiaowamimiaow栅栏密码：明文交替书写排列。密的化码艺时学术代行列转置：明文行列转置书写。仍不能抵御统计分析类的攻击方法（频度分析）密码分析概念密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反。两者解决问题的途径有很大差别密码设计是利用数学来构造密码密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力……，有时还靠点运气。密码分析方法--穷举破译法对截收的密报依次用各种可解的密钥试译，直到得到有意义的明文；或在不变密钥下，对所有可能的明文加密直到得到与截获密报一致为止，此法又称为完全试凑法(Completetrial-and-errorMethod)。只要有足够多的计算时间和存储容量，原则上穷举法总是可以成功的。但实际中，任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的密码分析方法—分析法确定性分析法利用一个或几个已知量(比如，已知密文或明文-密文对)用数学关系式表示出所求未知量(如密钥等)。已知量和未知量的关系视加密和解密算法而定，寻求这种关系是确定性分析法的关键步骤。统计分析法利用明文的已知统计规律进行破译的方法。密码破译者对截收的密文进行统计分析，总结出其间的统计规律，并与明文的统计规律进行对照比较，从中提取出明文和密文之间的对应或变换信息。密码可能经受的攻击攻击类型攻击者拥有的资源惟密文攻击加密算法截获的部分密文已知明文攻击加密算法截获的部分密文和相应的明文选择明文攻击加密算法加密黑盒子，可加密任意明文得到相应的密文选择密文攻击加密算法解密黑盒子，可解密任意密文得到相应的明文无条件安全和计算安全无条件安全如果算法产生的密文不能给出唯一决定相应明文的足够信息，无论截获多少密文，花费所少时间都不能解密密文。Shannon指出，仅当密钥至少和明文一样长时达到无条件安全（即一次一密）计算安全破译密文的代价超过被加密信息的价值破译密文所花时间超过信息的有效期2.2对称密码技术2.2.1基本概念密码算法的分类：对称密码算法和非对称密码算法对称密码算法：接受明文作为输入，然后使用一个对称密钥进行运算，输出明文的一个加密版本（密文）。对称密钥算法注意事项：采用一个好的随机数发生器来创建对称密钥随机数的来源是专门设计的产生真正随机数的硬件数据加密标准DES（DataEncryptionStandard，DES）是目前广泛使用的分组密码典型代表。主要用于电子银行的资金转帐（EFT）组成部分：加密处理、加密变换、子密钥生成。优点：容易标准化、通用化。算法运算速度快，易于产生密钥。缺点：不是非常安全，容易被暴力破解。2.2.2DES加密标准对称加密流程对称密码学的特点对称密码学中，同一个密钥既可以用于加密也可用于解密。对称加密速度快对称加密是安全的对称加密得到的密文是紧凑的对称加密容易受到中途拦截窃听的攻击密钥个数以使用者数目的平方速度增长，难以扩大使用范围对称密码系统需要复杂的密钥管理对称密码技术不适用于数字签名和不可否认性美国制定数据加密标准简况DES发展史确定了发展公用标准算法模式，而EES的制定路线与DES的背道而驰。人们怀疑有陷门和政府部门肆意侵犯公民权利。此举遭到广为反对。1995年5月AT&TBellLab的M.Blaze博士在PC机上用45分钟时间使SKIPJACK的LEAF协议失败，伪造ID码获得成功。1995年7月美国政府宣布放弃用EES来加密数据，只将它用于语音通信。1997年1月美国NIST着手进行AES（AdvancedEncryptionStandard）的研究，成立了标准工作室。2001年Rijndael被批准为AES标准。DES算法DES算法框图输入64bit明文数据初始置换IP乘积变换（16轮迭代）逆初始置换IP-164bit密文数据输出标准数据加密算法DES算法初始置换将64bit明文的位置进行置换，得到一个乱序的64bit明文组，而后分成左右两段，每段为32bit，以L0和R0表示，IP中各列元素位置号数相差为8，相当于将原明文各字节按列写出，各列比特经过偶采样和奇采样置换后，再对各行进行逆序。将阵中元素按行读出构成置换输出。DES算法58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157逆初始置换将16轮迭代后给出的64bit组进行置换，得到输出的密文组。输出为阵中元素按行读得的结果。IP和IP-1在密码意义上作用不大，它们的作用在于打乱原来输入的顺序关系。40848165624643239747155523633138646145422623037545135324612936444125217602835343115119592734242105021582633141949235725DES算法乘积变换一轮加解密处理示意图DES算法乘积变换它是DES算法的核心部分。将经过IP置换后的数据分成32bit的左右两组，在迭代过程中彼此左右交换位置。每次迭代时只对右边的32bit进行一系列的加密变换，在此轮迭代即将结束时，把左边的32bit与右边得到的32bit逐位模2相加，作为下一轮迭代时右边的段，并将原