第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加密器解密器接收者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相加，作为下一轮迭代时右边的段，并将原来右边未经变换的段直接送到左边的寄存器中作为下一轮迭代时左边的段。在每一轮迭代时，右边的段要经过扩展置换E、密钥加密运算、S盒代换、直接置换P和左右混合运算。DES算法乘积变换

扩展置换E。将输入的32bitRi-1扩展成48bit的输出，令s表示E原输入数据比特的原下标，则E的输出是将原下标s0或1(mod4)的各比特重复一次得到的，即对原第32,1,4,5,8,9,12,13,16,17,20,21,24,25,28,29各位都重复一次,实现数据扩展。将表中数据按行读出得到48bit输出。

密钥加密运算。将子密钥产生器输出的48bit子密钥ki与选择扩展运算E输出的48bits数据按位模2相加。S盒代换。将前面送来的48bit数据自左至右分成8组，每组为6bit。而后并行送入8个S一盒，每个S盒为一非线性代换网络，有4个输出，运算S的框图在图4-4-6中给出。DES算法扩展置换E3212345456789891011121312131415161716171819202120212223242524252627282928293031321直接置换P672021291228171152326518311028241432273919133062211425DES算法Li-1(32bit)

Ri-1(32bit)

扩展置换E48bit寄存器按bit模2加密48bit寄存器

S盒代换32bit寄存器直接置换P按bit模2和Li(32bit)Ri(32bit)F函数变换框图密钥产生器S盒代换

6bit8个S盒4bit

48bit寄存器32bit寄存器S1S2S3S4S5S6S7S8DES算法

列行0123456789101112131415014413121511831061259071015741421311061211953824114813621115129731050315128249175113141006130151814611349721312051013134715281412011069115201471110413158126932153138101315421167120514901009146315511312711428113709346102851412111512136498153011121251014731101306987415143115212S盒定义DES算法乘积变换

直接置换P。对S1至S8盒输出的32bit数据进行坐标置换，置换P输出的32bit数据与左边32bit即Ri-1逐位模2相加，所得到的32bit作为下一轮迭代用的右边的数字段。并将Ri-1并行送到左边的寄存器，作为下一轮迭代用的左边的数字段。

子密钥产生器。将64bit初始密钥经过置换选择PC1、循环移位置换、置换选择PC2给出每次迭代加密用的子密钥ki，DES算法

子密钥产生器框图

密钥（64bit）置换选择1，PC1置换选择2，PC2

Ci(28bit)

Di(28bit)

循环左移ti+1bit

循环左移ti+1bit除去第8,16,,64位(8个校验位)ki2.3.4.2DES算法DES加密的一个例子

取16进制明文X：0123456789ABCDEF

密钥K为：133457799BBCDFF1

去掉奇偶校验位以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000

应用IP，我们得到：

L0=11001100000000001100110011111111

L1=R0=11110000101010101111000010101010

然后进行16轮加密。

最后对L16,R16使用IP-1得到密文：85E813540F0AB405DES算法DES的安全问题S盒设计

DES靠S盒实现非线性变换。①由于S盒的设计细节没有公开，因此DES刚刚提出时，曾被人们怀疑有陷门（Trapdoors），而使美国美国国家安全局能轻易的解密消息，但到目前为止并没有任何证据可以证明这一点。

②在DES加密算法的所有部件中，S盒是唯一的具有差分扩散功能的部件（相对于逐比特异或），而其它部件除了群加密（逐比特异或）以外，都是简单的位置交换、添加或删减，毫无差分扩散能力。

③在DES加密算法的所以部件中，S盒是唯一的非线性部件。

DES算法密钥搜索机

对DES安全性批评意见中，较为一致的看法是DES的密钥短了些。IBM最初向NBS提交的建议方案采用112bits密钥，但公布的DES标准采用64bits密钥。有人认为NSA故意限制DES的密钥长度。采用穷搜索对已经对DES构成了威胁．

DES的密钥只有56比特，总密钥量为256个，不能抵抗穷举搜索攻击。例如1997年，美国科罗拉多州的程序员Verser用了96天的时间，在Internet上数万名志愿者的帮助下，成功的找到的DES的密钥，并获得了RSA公司发的10000美金的奖励。更为严重的是专用密码搜索机的设计。据新华社1998年7月22日消息，电子边境基金协会（EFF）使用一台25万美金的计算机在56个小时内攻破了DES。DES的安全问题二重DES

用DES进行两次加密，但这是否就意味着两重DES加密的强度等价于112bit密钥的密码的强度？答案是否定的。

中途相遇攻击法(Meet-in-the-MiddleAttack)

由Diffie和Hellman[1977]最早提出，可以降低搜索量其基本想法如下。若有明文密文对(xi,yi)满足

yi=Ek2[Ek1[xi]]则可得z=Ek1[xi]=Dk2[yi]

2.3.4.2DES算法二重DES图4-14-1中途相遇攻击示意图zEEDDxiyixizyi

k1

k1k2k22.3.4.2DES算法中途相遇攻击给定一已知明密文对(x1,y1)，可按下述方法攻击。以密钥k1的所有256个可能的取值对此明文x1加密，并将密文z存储在一个表中；从所有可能的256个密钥k2中依任意次序选出一个对给定的密文y1解密，并将每次解密结果z在上述表中查找相匹配的值。一旦找到，则可确定出两个密钥k1和k2；以此对密钥k1和k2对另一已知明文密文对(x2,y2)中的明文x2进行加密，如果能得出相应的密文y2就可确定k1和k2是所要找的密钥。2.3.4.2DES算法中途相遇攻击对于给定明文x，以两重DES加密将有264个可能的密文。可能的密钥数为2112个。所以，在给定明文下，将有2112/264=248个密钥能产生给定的密文。用另一对64bits明文密文对进行检验，就使虚报率降为248-64=2-16。这一攻击法所需的存储量为256×8Byte，最大试验的加密次数2×256=257。这说明破译双重DES的难度为257量级。2.3.4.2DES算法三重DES加密加密：y=Ek1[Dk2[Ek1[x]]]解密：x=Dk1[Ek2[Dk1[y]]]称其为加密-解密-加密方案，简记为EDE(encrypt-decrypt-encrypt)。此方案已在ANSIX9.17和ISO8732标准中采用，并在保密增强邮递(PEM)系统中得到利用。破译它的穷举密钥搜索量为21125×1035量级，而用差分分析破译也要超过1052量级。此方案仍有足够的安全性。2.3.4.2DES算法2.2.3AES加密标准AES(AdvancedEncryptionStandard)

出现的原因：3DES的执行时间是DES的3倍S盒的人为制定美国国家标准技术局（NIST）公布了AES要求：AES为对称密钥加密算法AES为分组加密算法，分组长度最少为128位AES密钥长度是变动的，为128、192、256位可选可同时由硬件或软件实现无专利限制，可自由使用2.2.3AES加密标准2000年10月2日NIST正式宣布比利时两位密码专家所设计的Rijndael称为AES算法。AES算法基于代换和置换运算AES算法最小密钥长度是128位，即使每秒能实现256个密钥的搜索，也需要149万亿年，穷举对其无效。AES也可有效抵抗差分密码分析和线性密码分析。对称加密算法分类对称密码学分类：流密码（序列密码）和分组密码（块密码）。分组密码工作方法：将明文分成固定长度的（块），用同一密钥和算法对每一块加密，输出也是固定长度的密文。核心技术：在相信复杂函数可以通过简单函数迭代若干圈得到的原则下，利用简单圈函数及对数运算，充分利用非线性运算。

明文序列x1,x2,…,xi,…加密函数E:EKYn解密函数D：DKXn解密算法加密算法密钥k密钥k明文x=(x0,x1,…,xm-1)明文x=(x0,x1,…,xm-1)密文x=(y0,y1,…,ym-1)分组密码分组密码算法应满足的要求分组长度n要足够大防止明文穷举攻击法奏效。密钥量要足够大尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。由密钥确定置换的算法要足够复杂充分实现明文与密钥的扩散和混淆，没有简单的关系可循，要能抗击各种已知的攻击。

分组密码加密和解密运算简单易于软件和硬件高速实现。数据扩展一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。差错传播尽可能的小分组密码算法应满足的要求分组密码流密码（序列密码）序列密码也称为流密码（StreamCipher），它是对称密码算法的一种。序列密码具有实现简单、便于硬件实施、加解密处理速度快、没有或只有有限的错误传播等特点流密码是将明文划分成字符（单个字母），或其编码的基本单位（如0,1数字），字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现流密码强度完全依赖于密钥序列的随机性和不可预测性。

明文序列：x1,x2,…,xi,…密钥流：K1，K2…,Ki…加密函数E:EKnCn解密函数D：DKnXn解密算法加密算法密钥k=(k0,k1,…,kt-1)密钥k=(k0,k1,…,kt-1)明文x=(x0,x1,…,xm-1)明文x=(x0,x1,…,xm-1)密文x=(y0,y1,…,ym-1)流密码（序列密码）序列密码与分组密码的对比

分组密码已一定大小作为每次处理的基本单元，而序列密码则是以一个元素（一个字母或一个比特）作为基本的处理单元。序列密码是一个随时间变化的加密变换，具有转换速度快、低错误传播的优点，硬件实现电路更简单；其缺点是：低扩散（意味着混乱不够）、插入及修改的不敏感性。分组密码使用的是一个不随时间变化的固定变换，具有扩散性好、插入敏感等优点；其缺点是：加解密处理速度慢、存在错误传播。流密码（序列密码）分类：同步流密码和自同步流密码核心问题是：密钥流生成器的设计保持收发两端密钥流的精准同步是实现可靠解密的关键流密码是将明文划分成字符（单个字母），或其编码的基本单位（如0,1数字），字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现流密码强度完全依赖于密钥序列的随机性和不可预测性。流密码（序列密码）自同步流密码：密钥流的每一位是前面固定数量密文位的函数，即密钥流的产生和前面已经产生的若干个密文字有关。自同步特点：当密文被修改时即密码在同步性遭到破坏时，可自动重建正确的解密。有限的错误传播：密文字符只与其相依赖的密文字符相关，其后的不受影响。主动攻击：对检测主动攻击时，较困难。明文统计扩散：每个明文字符会影响其后的整个密文。同步流密码：密钥流是独立生成的，和前面已经产生的若干个密文字无关。同步特点：消息的发送者和接收者必须同步才能做到正确的加密和解密，即双方用相同密钥，并对同一位置操作。无错误传播：密文字符即使被修改也不影响其他密文字符的解密。主动攻击：对主动攻击的防御性不强。流密码（序列密码）一次一密密码本一次一密（onetimepadding）指在流密码当中使用与消息长度等长的随机密钥,密钥本身只使用一次。优点:由于使用与消息等长的随机密钥,产生与原文没有任何统计关系的随机输出,因此一次一密方案不可破解。缺点:因密钥与明文要求具有相同长度，密钥在传递和分发上存在很大困难。

流密码（序列密码）RC4算法RC4算法是一种在电子信息领域加密的技术手段，用于无线通信网络，是一种电子密码，只有经过授权（缴纳相应费用）的用户才能享受该服务。RC4算法加密是采用的xor，一旦子密钥序列出现了重复，密文就有可能被破解。2001年就有以色列科学家指出RC4加密算法存在着漏洞，这可能对无线通信网络的安全构成威胁。流密码（序列密码）非对称密码技术2.3非对称密码技术20世纪70年代Diffie和Hellman最早引入非对称密码学的概念。成功的非对称密码学算法：RSA椭圆曲线密码算法公钥加密算法也称为非对称密钥算法，用一对密钥：一个公钥和一个私钥。用户需要保障私钥的安全；公钥可以公布出去。用公钥加密的信息只能用私钥解密，反之亦然。主要特点：加密和解密能力分开多个用户加密的消息只能由一个用户解读，（用于公共网络中实现保密通信）只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。无需事先分配密钥。非对称密码技术非对称密码加解密流程密文明文非对称密码技术加解密步骤：Bob产生一对密钥，分别为公钥B和私钥B’。Bob将公钥予以公开，私钥自己保管。Alice要向Bob发消息，加密所用密钥为Bob公开的公钥B，表示为：C=EB(M)Bob收到密文后，用自己的私钥B’解密，表示为:M=DB’(C)非对称密码技术公钥密码应满足的要求接收方B产生密钥对在计算上是容易的发送方A用收方的公开钥对消息m加密以产生密文c在计算上是容易的。收方B用自己的秘密钥对密文c解密在计算上是容易的。敌手由密文c和B的公开密钥恢复明文在计算上是不可行的。敌手由密文c和B的公开密钥恢复秘密密钥在计算上是不可行的加解密次序可换，即EPKB[DSKB(m)]=DSKB[EPKB(m)],不是对任何算法都做此要求。非对称密码技术2.4.3非对称密码学的特点使用非对称密码技术时，用一个密钥（公钥或私钥）加密的信息只能用另外一个密钥（私钥或公钥）来解密。非对称加密是安全的非对称加密不必担心密钥被中途拦截的问题需要分发的密钥数目和参与者的数目一样非对称加密没有复杂的密钥分发问题非对称加密不需要事先在各参与方建立关系以交换密钥非对称加密支持数字签名和不可否认性非对称加密速度加密较慢非对称加密会导致得到的密文变长非对称密码学的主要特点：RSA算法概况MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman

等1978发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。它既可用于加密、又可用于数字签字。RSA算法的安全性基于数论中大整数分解的困难性。算法描述－密钥产生独立地选取两大素数p和q(各100～200位十进制数字)计算n=p×q，其欧拉函数值(n)=(p－1)(q－1)

随机选一整数e，1<

e<(n)，gcd[(n),e]=1在模(n)下，计算e的有逆元d*e=1mod(n)以{e,n}为公钥。{d,n}为私钥。(p,q不再需要，可以销毁。)算法描述－加密和解密加密将明文比特串分组，各组对应的十进制数小于nc=memodn解密

m=cd

modnRSA算法举例选P=7,q=17。设明文为m=19求密文.n=p*q=7*17=119(n)=(p-1)*(q-1)=6*16=96取e＝5，满足1<e<(n),且gcd((n),e)=1确定d*e=1mod(n),且小于96的d即求96*x+1=5d因为77*5=385=4*96+1所以d=77故公钥为(5,119)私钥为(77,119)加密：C=195mod119=2476099mod119=66解密：m=6677mod119=19RSA的安全性RSA的安全性是基于分解大整数的困难性假定（尚未证明分解大整数是NP问题）如果分解n=p×q，则立即获得(n)=(p－1)(q－1)，从而能够确定e的模(n)乘法逆dRSA-129历时8个月被于1996年4月被成功分解，RSA－130于1996年4月被成功分解密钥长度应该介于1024bit到2048bit之间由n直接求(n)等价于分解nRSA的安全性P和q的长度相差不要太大，即|p-q|要大p-1,q-1都应有大的素因子。gcd(p-1)(q-1)应小e<n且d<n1/4,则d能被容易的确定。2.3.3椭圆曲线密码体制椭圆曲线算法（ECC）：为保证RSA算法的安全，密钥长度增加带来运算负担增加。ECC算法能采用短的多的密钥获得同样的安全性。ECC算法密码体制优点：安全性高密钥量小灵活性好RSA/DSA5127681024204821000ECC106132160211600ECC和RSA/DSA在保持同等安全条件下所需密钥长度（比特）椭圆曲线密码体制的优点：安全性高ECC和其他几种公钥加密相比，安全性更高。它的离开对数问题的计算复杂度是完全指数级的，而RSA是亚指数级的。计算量小而处理速度快在相同条件下，ECC的私钥处理速度比RSA快，同时，ECC的密钥生成速度比RSA快百倍以上，因此加密性能更优。存储空间占用小因为相同安全强度下，密钥更短，因此空间占用少。带宽要求低在短消息加密时，ECC所需带宽比RSA少很多。2.3.3椭圆曲线密码体制单向函数一个可逆函数f：AB，若它满足：1对所有xA，易于计算f(x)。2对“几乎所有xA”由f(x)求x“极为困难”，以至于实际上不可能做到，则称f为一单向(One-way)函数。定义中的“易于计算”是指函数值能在其输入长度的多项式时间内求出，即若输入长度为n，计算函数的时间是na的倍数，a为一固定的常数。若计算函数时间是an的倍数，则为不可能做到的。2.3.4单向散列函数2.3.4单向散列函数单向散列函数又称单向Hash函数、杂凑函数，就是把任意长的输入消息串变化成固定长的输出串且由输出串难以得到输入串的一种函数。这个输出串称为该消息的散列值。一般用于产生消息摘要，密钥加密等。常见的单向散列函数：MD5、SHA、MAC、CRC性质：

给定一个消息M，容易计算出散列值h。给定散列值h，很难根据H(M)=h计算出消息M。给定一个消息M，很难再找出另一消息满足H(M)=H(M’)2.3.4单向散列函数单向散列函数安全的单向散列函数应该具备的条件①输入长度是任意的;

②输出长度是固定的,根据目前的计算技术应至少取128bits长,以便抵抗生日攻击;

③对每一个给定的输入,计算输出即散列值是很容易的④给定散列函数的描述,找到两个不同的输入消息杂凑到同一个值是计算上不可行的

哈希函数定义：将任意长的字符串M映射成一个较短的定长输出字符串H的函数，以h表示，即h（M）H＝h（M）为M的哈希值、哈希码、哈希结果H又称为输入M的数字指纹h为多对一的关系，不能逆推分类：密码哈希函数一般哈希函数哈希函数报文CRC匹配CRC'报文多项式收到的报文循环冗余检验哈希函数设计运用特点用户无法反向执行算法来恢复最初的明文得到的摘要不会泄漏明文信息创建/发现摘要为某个特定值的明文计算上是不可行的哈希函数的安全性针对哈希函数的基本攻击方式穷举攻击法（ExhaustiveAttack）目标攻击自由起始目标攻击生日攻击（BirthdayAttact）中途相遇攻击（MeetintheMiddleAttack）生日攻击（BirthdayAttact）

如果房间里有183个人，那么其中某个人和你的生日相同的概率是50%。然而，如果希望找到其中任意两个人生日相同的概率为50%，则房间里需要多少人呢？答案是23。计算公式参看P79这个就是生日悖论，结果要比主观猜想的要小得多。也就是说你走进一个22人的教室，要其中一个人和你的生日相同的概率很小，但要其中任意两个生日相同的概率则很高。转到代码安全中的哈希加密，情况转换成两段不同的字符（人），用哈希加密可能得到相同的密码（生日），而生日悖论的结果说明只要不关心是哪两个字符，找到两个匹配的难度会降低很多。利用该理论来破解密码的方法就叫做“生日攻击”。MD-5哈希算法MD5算法MD5的全称是Message-DigestAlgorithm5（信息-摘要算法），在90年代初由MITLaboratoryforComputerScience和RSADataSecurityInc的RonaldL.Rivest开发出来，经MD2、MD3和MD4发展而来。它的作用是让大容量信息在用数字签名软件签署私人密匙前被“压缩”成一种保密的格式（就是把一个任意长度的字节串变换成一定长的大整数）。不管是MD2、MD4还是MD5，它们都需要获得一个随机长度的信息并产生一个128位的信息摘要。MD5之父RonaldRivest算法的应用

MD5的典型应用是对一段信息（Message）产生信息摘要（Message-Digest），以防止被篡改。比如，在UNIX下有很多软件在下载的时候都有一个文件名相同，文件扩展名为.md5的文件，在这个文件中通常只有一行文本，大致结构如：MD5(tanajiya.tar.gz)=0ca175b9c0f726a831d895e269332461以此保证下载文件的完整性和防抵赖性应用2：UNIX系统中用户的密码就是以MD5（或其它类似的算法）经加密后存储在文件系统中。有效的避免黑客攻击中的“跑字典法”MD-5算法王小云教授，1983年至1993年就读于山东大学数学系，先后获得学士、硕士和博士学位，1993年毕业后留校任教。2005年获国家自然科学基金杰出青年基金资助，同年入选清华大学“百名人才计划”，2005年6月受聘为清华大学高等研究中心“杨振宁讲座教授”，现为清华大学“长江学者特聘教授”。王小云教授带领的研究小组于2004年、2005年先后破解了被广泛应用于计算机安全系统的MD5和SHA-1两大密码算法，对于这项十几年来国际上首次成功破解全球广泛使用的密码算法与标准的工作，整个国际密码学界为之震惊，密码学领域最权威的两大刊物Eurocrypto与Crypto将2005年度最佳论文奖授予了这位中国女性，其研究成果引起了国际同行的广泛关注。

2004年8月，在美国加州圣芭芭拉召开的国际密码大会上王小云在国际会议上首次宣布了她及她的研究小组近年来的研究成果——对MD5、HAVAL-128、MD4和RIPMD等四个著名密码算法的破译结果。

王小云的研究成果表明了从理论上讲电子签名可以伪造，必须及时添加限制条件，或者重新选用更为安全的密码标准，以保证电子商务的安全。MD5安全性探讨：第一，MD5并没有被完全的破解，目前只是获得了快速产生碰撞的算法（大约需要2^40次尝试，在当前的计算能力下仅需几小时即可）。因为要从经过MD5散列处理所得到的结果逆向分析从而得到散列前的原文是根本不可能的！

根据MD5的基本原理，该算法是将一段任意长的数据转换成一段长度为128位的数据，并且保证转换后得到的数据是伪随机的。从函数的角度而言，MD5即是将一个不做任何要求的自变量映射成为一个长度固定的因变量，显然，这是一个多对一的映射（因变量空间仅为2^128，而自变量空间为无穷大，所以可以将MD5视为一个无穷多对一的映射）。由最基本的数学定理可知，多对一的函数是不可逆的，即是说，不可能从MD5的散列结果逆推出原文。所以，用户不用担心其使用MD5进行散列处理后得到的结果会被人破解得到原文。第二，MD5的碰撞的发现，仅仅是使得使用其进行对随机序列的哈希操作变得不可靠，而对于一段有特殊意义或者格式的文字进行哈希而言仍然是安全的。

根据当初王教授演示的结果，我们知道，使用她的碰撞算法得到的结果是一串随机字符串。因此，我们仍然可以使用MD5对软件等进行哈希，并且，目前市面上仍然有大量的软件是使用的MD5进行哈希作为验证码。只是利用MD5存储密码等已经不再安全！RSA公司的blog上一篇讨论MD5在目前仍然可以使用的文章，作者提出的解决方案是在需要哈希处理的代码前加入一段格式固定的字符串，这个简单的做法就可以使王教授的攻击无效，这一点是值得我们去进一步探讨的！

当然，为了获得更高的安全性，在仍然使用MD5的同时，我们也应该考虑将软件向SHA-256等仍然安全的算法进行迁移，并且期待密码学家们提出更加安全的哈希算法。

SHA算法家族安全散列算法SHA(SecureHashAlgorithm)一种数据加密算法，公认的最安全的散列算法之一。

取一串输入码（称为预映射或信息），并把它们转化为长度较短、位数固定的输出序列即散列值（也称为信息摘要或信息认证代码）的过程。散列函数值可以说时对明文的一种“指纹”或是“摘要”。SHA-1输入：512位分组，输出：160位。MAC算法MAC（MessageAuthenticationCode）消息认证码（带密钥的Hash函数）:密码学中，通信实体双方使用的一种验证机制，保证消息数据完整性的一种工具。2.3.5非对称密钥技术的应用1.混合密码系统产生原因：对称加密密钥管理和分发困难，不能实现数字签名，而非对称加密运算速度太慢。解决方法：对称加密与非对称加密结合。基本方法：非对称密码体制用来加密关键的核心的数据（密钥），对称密钥体制用来加密大量数据（明文）。结果：从对称密码得到速度和紧凑的密文，你也可以从公／私钥密码学当中得到你想要的伸缩性、简化的密钥管理、抗窃听以及对数字签名／不可否认性的支持过程：先生成一个随机对称密钥（会话密钥）。用会话密钥加密明文。用接受者公钥加密对称密钥。将被打包的密钥附在密文的后面发送给接收者。AB密文数据包密钥打包2.3.5非对称密钥技术的应用2.数字信封数字信封是公钥密码体制在实际中的一个应用，是用加密技术来保证只有规定的特定收信人才能阅读通信的内容。信息发送方采用对称密钥来加密信息内容，然后将此对称密钥用接收方的公开密钥来加密，这部分称数字信封。2.3.5非对称密钥技术的应用3.Diffie-Hellman密钥交换Diffie–Hellmankeyexchange，简称“D–H”

是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道创建起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。算法的有效性（安全性）依赖于计算离散对数的难度。2.3.5非对称密钥技术的应用算法表示（蓝色表示非秘密信息,红色表示秘密信息）：爱丽丝与鲍伯协定使用p=23以及baseg=5.爱丽丝选择一个秘密整数a=6,计算A=g

amodp并发送给鲍伯。

A=56mod23=8.鲍伯选择一个秘密整数b=15,计算B=

g

bmodp并发送给爱丽丝。

B=5

15mod23=19.爱丽丝计算s=B

amodp

19

6mod23=2.鲍伯计算<s=A

bmodp

815mod23=22.3.5非对称密钥技术的应用爱丽丝和鲍伯最终都得到了同样的值，因为在modp下gab和gba相等。注意a,b和gab=gbamodp是秘密的。其他所有的值都可以在公共信道上传递。一旦爱丽丝和鲍伯得出了公共秘密，他们就可以把它用作对称密钥，以进行双方的加密通讯，因为这个密钥只有他们才能得到。