I.3.网络安全密码学基本理论

网络信息安全第一部分网络信息安全基础(密码学基础)第3章网络安全密码学基本理论2.1密码学概况2.2密码体制分类2.3常见密码算法2.4杂凑函数2.5数字签名2.6安全协议2.8本章小结3.1密码学概况密码学是一门研究信息安全保护的科学。它最早可追溯到几千年前，主要用于军事和外交通信。随着网络与信息技术的发展，密码学的应用不再局限于军事、政治、外交领域，而是逐步应用于社会各个领域，例如电子商务、个人安全通信、网络安全管理等。密码学的发展可大致划分为四个阶段：第一阶段：从古代到1949年。该时期的密码学没有数学理论基础，其应用领域仅限于通信。第二阶段：从1949年到1975年。这一时期的标志性事件是香农在1949年发表的著名论文—《保密系统的信息理论》，该文为私钥密码系统奠定了理论基础。3.1密码学概况密码学是一门研究信息安全保护的科学。它最早可追溯到几千年前，主要用于军事和外交通信。随着网络与信息技术的发展，密码学的应用不再局限于军事、政治、外交领域，而是逐步应用于社会各个领域，例如电子商务、个人安全通信、网络安全管理等。密码学的发展可大致划分为四个阶段：第三阶段：1976年到1990年。这一时期的密码技术出现了革命性变化，一是开辟了公钥密码学的新纪元，公钥密码体制诞生。二是美国政府提出了数据加密标准(DES)。这两个引人瞩目的事件标志着现代密码学的诞生。这一阶段的密码学应用不够广泛，使用人员并不多。第四阶段：1990年到至今。因特网技术的普及和信息技术的发展极大地带动了密码学的应用需求，密码技术成为网络与信息安全的核心技术。在这一时期，密码学的应用得到了社会的广泛认同，密码学正影响着网络与信息技术的发展。密码学的历史古罗马：Caesar密码ABCDEFGHIGKLMNOPQRSTUVWXYZDEFGHIGKLMNOPQRSTUVWXYZABCCaesarwasagreatsoldier密码本密文Fdhvduzdvdjuhdwvroglhu明文密文CAESAR密码：c=(m+3)Mod26有趣的加密：巴比伦的文字密码学的历史美国南北战争CANYOUUNDERSTAND输入方向输出方向明文：Canyouunderstand密文：codtaueanurnynsd密码学的历史转轮密码机ENIGMA，由ArthurScherbius于1919年发明，4轮ENIGMA在1944年装备德国海军。密码学的历史英国的TYPEX打字密码机，是德国3轮ENIGMA的改进型密码机。它在英国通信中使用广泛，且在破译密钥后帮助破解德国信号。密码学的历史图灵（AlanMathisonTuring）AlanMathisonTuring,1912～1954.英国数学家。一生对智能与机器之间的关系进行着不懈探索。1936年，24岁的图灵提出“图灵机”的设想。二战期间成功地破译了纳粹德国的密码，设计并制造了COLOSSUS,向现代计算机迈进了重要一步。1952年，图灵遭到警方拘捕，原因是同性恋。1954年6月8日，服毒自杀，年仅42岁。图灵去世12年后，美国计算机协会以他的名字命名了计算机领域的最高奖“图灵奖”。一个简单的加密算法—异或一个简单的加密算法—异或异或

密文：0110

解密： 密钥：

0101

明文：0011 已知明文、密文，怎样求得密钥？C=PKP=CK异或运算（不带进位加法）： 明文:0011

加密： 密钥:0101

密文：0110K=CP消息和加密遵循国际命名标准，加密和解密可以翻译成：“Encipher（译成密码）”和“（Decipher）（解译密码）”。也可以这样命名：“Encrypt（加密）”和“Decrypt（解密）”。消息被称为明文。用某种方法伪装消息以隐藏它的内容的过程称为加密，加了密的消息称为密文，而把密文转变为明文的过程称为解密，下图表明了加密和解密的过程。Mathisfun!CYPHERTEXTSecret

KeyEncrypt(Lock)Decrypt(Unlock)DataConfidentialityCYPHERTEXTMathisfun!明文密文明文用M（Message，消息）或P（Plaintext，明文）表示，它可能是比特流、文本文件、位图、数字化的语音流或者数字化的视频图像等。密文用C（Cipher）表示，也是二进制数据，有时和M一样大，有时稍大。通过压缩和加密的结合，C有可能比P小些。加密函数E作用于M得到密文C，用数学公式表示为：E（M）=C。解密函数D作用于C产生M，用数据公式表示为：D（C）=M。先加密后再解密消息，原始的明文将恢复出来，D（E（M））=M必须成立。算法和密钥密码算法也叫密码函数，是用于加密和解密的数学函数。通常情况下有两个相关的函数，一个用作加密，另一个用作解密。算法本身是保密的称为受限制的算法。受限制的算法不可能进行质量控制或标准化，每个用户组织必须有它们自己的唯一的算法，这样的组织不可能采用流行的硬件或软件产品。密码算法的分类根据算法和密钥是否分开古典密码：不分开现代密码：分开根据密钥特点对称密码体制：加、解密密钥相同，或彼此容易相互确定非对称密码体制：加、解密密钥不同，彼此很难互相确定加、解密分离根据加密方式流密码：明文消息按字符逐位加密分组密码：将明文消息分组，逐组进行加密古典密码和现代密码古典密码代替密码（SubstitutionCipher）换位密码(transpositionCipher)代替密码与换位密码的组合古典密码（受限密码）的缺陷密码体制的安全性在于保持算法本身的保密性受限算法的缺陷不适合大规模生产不适合较大的或者人员变动较大的组织用户无法了解算法的安全性古典密码和现代密码现代密码算法把算法和密钥分开密码算法可以公开，密钥保密密码系统的安全性在于保持密钥的保密性发送方接收方mm加密E解密Dc=Ek(m)m=Ek(c)密码分析密钥分配（秘密信道）kk鉴别、完整性和抗抵赖性除了提供机密性外，密码学需要提供三方面的功能：鉴别、完整性和抗抵赖性。这些功能是通过计算机进行社会交流，至关重要的需求。鉴别：消息的接收者应该能够确认消息的来源；入侵者不可能伪装成他人。完整性：消息的接收者应该能够验证在传送过程中消息没有被修改；入侵者不可能用假消息代替合法消息。抗抵赖性：发送消息者事后不可能虚假地否认他发送的消息。3.1.2密码学基本概念密码学的主要目的是保持明文的秘密以防止攻击者获知，而密码分析学则是在不知道密钥的情况下识别出明文的科学。所谓明文，是指需要采用密码技术进行保护的消息。而密文则是指用密码技术处理“明文”后的结果，通常称为加密消息。将明文变换成密文的过程称作加密(encryption)。其逆过程，即由密文恢复出原明文的过程称作解密(decryption)。加密过程所使用的一组操作运算规则称作加密算法；而解密时使用的一组运算规则称作解密算法。加密和解密算法的操作通常都是在密钥(key)控制下进行的，分别称为加密密钥和解密密钥。3.1.2密码学基本概念根据密码分析者破译时已具备的前提条件，人们通常将攻击类型分为三种：惟密文攻击密码分析者只拥有一个或多个用同一个密钥加密的密文，没有其他可利用的信息。已知明文攻击密码分析者仅知道当前密钥下的一些明文及所对应的密文。选择明文攻击密码分析者能够得到当前密钥下自己选定的明文所对应的密文。选择密文攻击攻击者能够得到任何选定的密文所对应的明文。3.2密码体制分类根据密钥的特点，密码体制分为私钥和公钥密码体制两种。介于私钥与公钥之间的密码体制称为混合密码体制。3.2.1私钥密码体制私钥密码体制又称作对称密码体制，是广泛应用的普通密码体制。该体制的特点是加密和解密使用相同的密钥，如图所示。当用户应用这种体制时，消息的发送者和接收者必须事先通过安全渠道交换密钥，以保证发送消息或接收消息时能够有供使用的密钥。3.2.1私钥密码体制双方共享一个密钥加密方解密方奉天承运皇帝诏曰……共享密钥yHidYTVdkd;AOt……yHidYTVdkd;AOt……奉天承运皇帝诏曰……加密解密共享密钥用户保存的密钥数ABCD秘密密钥加密技术特点算法简单、速度快，被加密的数据块长度可以很大密钥在加密方和解密方之间传递和分发必须通过安全通道进行3.2.1私钥密码体制在私钥体制中，使用者A和B具有相同的加、解密能力，因此使用者B无法证实收到的A发来的消息确实来自A。私钥密码体制的缺陷可归纳为三点：密钥分配问题、密钥管理问题无法源认证。虽然私钥密码体制有不足之处，但私钥密码算法处理速度快，常常用作数据加密处理。目前，私钥密码典型算法已有DES、IDEA、AES等，其中，DES是美国早期数据加密标准，现在已经被AES取代。私钥密码加密示意图Internet明文数据“m”②加密函数E(k，m)=c③解密函数D(k，c)=m明文数据“m”①共享密钥k密文数据“c”3.2.2公钥密码体制1976年，W.Diffie和M.E.Hellman发表了论文《密码学的新方向》，提出了公钥密码体制的思想。公钥密码体制又称作非对称密码体制基本的原理是在加密和解密的过程中使用不同的密钥处理方式。加密密钥可以公开，而只需要把解密密钥安全存放即可。在安全性方面，密码算法即使公开时，由加密密钥推知解密密钥的计算也是不可行的。公钥密码体制原理示意如图所示。明文明文密文加密解密公开密钥秘密密钥3.2.2公钥密码体制加密方解密方奉天承运皇帝诏曰……解密方的公开密钥yHidYTVdkd;AOt……yHidYTVdkd;AOt……奉天承运皇帝诏曰……加密解密解密方的私有密钥加密和解密的密钥不同用户需要保存的密钥数ABCDInternet公开密钥加密技术特点算法复杂、速度慢，被加密的数据块长度不宜太大公钥在加密方和解密方之间传递和分发不必通过安全通道进行3.2.2公钥密码体制公钥密码体制可看成邮箱，任何人都能容易地把邮件放进邮箱，只要打开口子投进去就行了。把邮件放进邮箱是一件公开的事情，但打开邮箱却不是，它是难的，需要吹焊器或其他工具。然而，如果持有秘密信息(钥匙或组合密码)，就很容易打开邮箱了。与对称密码体制相比较，公钥密码体制有以下优点:(1)密钥分发方便，可以以公开方式分配加密密钥。例如，因特网中的个人安全通信常将自己的公钥公布在网页中，方便其他人用它进行安全加密。(2)密钥保管量少。网络中的消息发送方可以共用一个公开加密密钥，从而减少密钥数量。(3)支持数字签名。目前，只有三类体制被证明是安全和有效的，即RSA体制、ELGamal体制以及椭圆曲线密码体制公钥加密示意图Internet②公钥加密E(p，m)=c③私钥解密D(q，c)=m①将公钥给对方明文数据“m”密文数据“c”明文数据“m”私钥始终未在网上传输对非对称密码算法的误解非对称密钥算法比对称密钥密码算法更安全？任何一种算法都依赖于密钥长度、破译密码的工作量，从抗分析角度，没有一方更优越非对称密钥算法使对称密钥成为过时了的技术？非对称密钥算法的计算速度比较慢，一般用于密钥管理和数字签名，而对称密钥密码算法计算速度快，二者各有优势，分别适用于不同的场景，将长期共同存在。不可不提的非对称密码Diffie-Hellman密钥交换RSA体制ElGamal体制椭圆曲线密码体制非对称密码算法的用途需要注意的是，非对称密码算法不但可以用来保护数据的保密性，而且可以用来保护数据的真实性和完整性。例如，如果A想要保护消息M的真实性和完整性，他可以给M计算数字签名S。当消息M的接收者B接收到消息M和数字签名S后，他可以对这个消息的真实性和完整性进行验证，这样能确保消息M是A发送给他的，并且在传送的过程中没有遭到破坏。3.2.3混合密码体制混合密码体制利用公钥密码体制分配私钥密码体制的密钥，消息的收发双方共用这个密钥，然后按照私钥密码体制方式，进行加密和解密运算。混合密码体系工作原理明文明文密文对称密钥密文密文B私钥解密解密B公钥加密对称密钥AB3.3常见密码算法—1.DESDESDES是数据加密标准的简称，由IBM在20世纪60年代研制出来。DES是一个分组加密算法，能够支持64比特的明文块加密，其密钥长度为56比特。DES是世界上应用最广泛的密码算法。但是，随着计算机系统运算速度的增加和网络计算的进行，在有限的时间内进行大量的运算将变得更可行。1997年，RSA实验室发出了破解DES密文的挑战。DES56比特的密钥长度已不足以保证密码系统的安全了。NIST于1999年10月25日采用三重DES作为过渡期间的国家标准，以增强DES的安全性，并开始征集AES(AdvancedEncryptionStandard)算法。3.3常见密码算法—1.DESDES算法的安全性DES算法正式公开发表以后，引起了一场激烈的争论。1977年Diffie和Hellman提出了制造一个每秒能测试106个密钥的大规模芯片，这种芯片的机器大约一天就可以搜索DES算法的整个密钥空间，制造这样的机器需要两千万美元。1993年R.Session和M.Wiener给出了一个非常详细的密钥搜索机器的设计方案，它基于并行的密钥搜索芯片，此芯片每秒测试5×107个密钥，当时这种芯片的造价是10.5美元，5760个这样的芯片组成的系统需要10万美元，这一系统平均1.5天即可找到密钥，如果利用10个这样的系统，费用是100万美元，但搜索时间可以降到2.5小时。可见这种机制是不安全的。3.3常见密码算法—1.DESDES算法的安全性1997年1月28日，美国的RSA数据安全公司在互联网上开展了一项名为“密钥挑战”的竞赛，悬赏一万美元，破解一段用56比特密钥加密的DES密文。一位名叫RockeVerser的程序员设计了一个可以通过互联网分段运行的密钥穷举搜索程序，组织实施了一个称为DESHALL的搜索行动，成千上万的志愿者加入到计划中，在计划实施的第96天，即挑战赛计划公布的第140天，1997年6月17日晚上10点39分，美国盐湖城Inetz公司的职员MichaelSanders成功地找到了密钥，在计算机上显示了明文：“Theunknownmessageis:Strongcryptographymakestheworldasaferplace”。3.3常见密码算法—1.DESDES算法原理DES算法的入口参数有三个：Key、Data、Mode。其中Key为8个字节共64位，是DES算法的工作密钥；Data为8个字节64位，是要被加密或被解密的数据；Mode为DES的工作方式有两种：加密或解密。DES算法是这样工作的：如Mode为加密，则用Key去把数据Data进行加密，生成Data的密码形式（64位）作为DES的输出结果；如Mode为解密，则用Key去把密码形式的数据Data解密，还原为Data的明码形式（64位）作为DES的输出结果。3.3常见密码算法—1.DESDES算法实现加密需要三个步骤：1.变换明文。对给定的64位比特的明文x，首先通过一个置换IP表来重新排列x，从而构造出64位比特的x0，x0=IP(x)=L0R0，其中L0表示x0的前32比特，R0表示x0的后32位。2.按照规则迭代。规则为Li=Ri-1Ri=Li⊕f(Ri-1,Ki)（i=1,2,3…16）经过第一步变换已经得到L0和R0的值，其中符号⊕表示的数学运算是异或，f表示一种置换，由S盒置换构成，Ki是一些由密钥编排函数产生的比特块。f和Ki将在后面介绍。3.对L16R16利用IP-1作逆置换，就得到了密文y。加密过程如图示。3.3常见密码算法—1.DES从图中可看出，DES加密需要四个关键点：1、IP置换表和IP-1逆置换表。2、函数f。3、子密钥Ki。4、S盒的工作原理。输入64位bit明文IP置换表L0R0IP逆置换表输出64位bit明文迭代16次Li=Ri-1Ri=Lif(Ri-1,Ki)

(i=1,2,…,16)DES加密过程3.3常见密码算法—1.DES输入64位bit明文IP置换表L0R0IP逆置换表输出64位bit明文迭代16次Li=Ri-1Ri=Lif(Ri-1,Ki)

(i=1,2,…,16)输入的64位数据按置换IP表进行重新组合，并把输出分为L0、R0两部分，每部分各长32位，其置换IP表如下表所示将输入64位比特的第58位换到第一位，第50位换到第二位，依此类推，最后一位是原来的第7位。L0、R0则是换位输出后的两部分，L0是输出的左32位，R0是右32位。比如：置换前的输入值为D1D2D3…D64，则经过初始置换后的结果为：L0=D58D50...D8，R0=D57D49...D7。（1）IP置换表和IP-1置换表3.3常见密码算法—1.DES输入64位bit明文IP置换表L0R0IP逆置换表输出64位bit明文迭代16次Li=Ri-1Ri=Lif(Ri-1,Ki)

(i=1,2,…,16)经过16次迭代运算后。得到L16、R16，将此作为输入，进行逆置换，即得到密文输出。逆置换正好是初始置的逆运算，例如，第1位经过初始置换后，处于第40位，而通过逆置换IP-1，又将第40位换回到第1位，其逆置换IP-1规则如下表所示。（1）IP置换表和IP-1置换表3.3常见密码算法—1.DES函数f有两个输入：32位Ri-1和48位Ki，f处理流程如图示S1S2S3S4S5S6S7S832位Ri-1E变换P变换32位输出48位Ki48位48位输入64位bit明文IP置换表L0R0IP逆置换表输出64位bit明文迭代16次Li=Ri-1Ri=Lif(Ri-1,Ki)

(i=1,2,…,16)（2）函数f3.3常见密码算法—1.DESS1S2S3S4S5S6S7S832位Ri-1E变换P变换32位输出48位Ki48位48位E变换的算法是从Ri-1的32位中选取某些位，构成48位。即E将32比特扩展变换为48位，变换规则根据E位选择表，如下表所示。Ki是由密钥产生的48位比特串，具体的算法下面介绍。将E的选位结果与Ki作异或操作，得到一个48位输出。分成8组，每组6位，作为8个S盒的输入。（2）函数f3.3常见密码算法—1.DESS1S2S3S4S5S6S7S832位Ri-1E变换P变换32位输出48位Ki48位48位每个S盒输出4位，共32位，S盒的工作原理将在第第四步介绍。S盒的输出作为P变换的输入，P的功能是对输入进行置换，P换位表如下表所示。（2）函数f3.3常见密码算法—1.DES假设密钥为K，长度为64位，但是其中第8、16、24、32、40、48、64用作奇偶校验位，实际上密钥长度为56位。K的下标i的取值范围是1到16，用16轮来构造。构造过程如图示。（3）子密钥Ki64位密钥字符串KPC1变换C0D0LS2LS2C2D2LS16LS16C16D16LS1LS1C1D1PC2变换PC2变换PC2变换48位K148位K148位K128bit28bit3.3常见密码算法—1.DES（3）子密钥Ki64位密钥字符串KPC1变换C0D0LS2LS2C2D2LS16LS16C16D16LS1LS1C1D1PC2变换PC2变换PC2变换48位K148位K148位K128bit28bit57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124首先，对于给定的密钥K，应用PC1变换进行选位，选定后的结果是56位，设其前28位为C0，后28位为D0。PC1选位如上表所示。3.3常见密码算法—1.DES（3）子密钥Ki64位密钥字符串KPC1变换C0D0LS2LS2C2D2LS16LS16C16D16LS1LS1C1D1PC2变换PC2变换PC2变换48位K148位K148位K128bit28bit第一轮：对C0作左移LS1得到C1，对D0作左移LS1得到D1，对C1D1应用PC2进行选位，得到K1。其中LS1是左移的位数，如下表所示。1122222212222221表中的第一列是LS1，第二列是LS2，以此类推。3.3常见密码算法—1.DES（3）子密钥Ki64位密钥字符串KPC1变换C0D0LS2LS2C2D2LS16LS16C16D16LS1LS1C1D1PC2变换PC2变换PC2变换48位K148位K148位K128bit28bit左移的原理是所有二进位向左移动，原来最右边的比特位移动到最左边。其中PC2如上表所示。14171124153281562110231912,426816727201324152313747553040514533484449395634534642503629323.3常见密码算法—1.DES（3）子密钥Ki64位密钥字符串KPC1变换C0D0LS2LS2C2D2LS16LS16C16D16LS1LS1C1D1PC2变换PC2变换PC2变换48位K148位K148位K128bit28bit第二轮：对C1，D1作左移LS2得到C2和D2，进一步对C2D2应用PC2进行选位，得到K2。如此继续，分别得到K3，K4…K16。3.3常见密码算法—1.DESS盒以6位作为输入，而以4位作为输出，现在以S1为例说明其过程。假设输入为A=a1a2a3a4a5a6，则a2a3a4a5所代表的数是0到15之间的一个数，记为：k=a2a3a4a5；由a1a6所代表的数是0到3间的一个数，记为h=a1a6。在S1的h行，k列找到一个数B，B在0到15之间，它可以用4位二进制表示，为B=b1b2b3b4，这就是S1的输出。DES算法的解密过程是一样的，区别仅仅在于第一次迭代时用子密钥K15，第二次K14、最后一次用K0，算法本身并没有任何变化。DES的算法是对称的，既可用于加密又可用于解密。（4）S盒的工作原理3.3常见密码算法—1.DESDES算法的误区DES算法具有比较高安全性，到目前为止，除了用穷举搜索法对DES算法进行攻击外，还没有发现更有效的办法。而56位长的密钥的穷举空间为256，这意味着如果一台计算机的速度是每一秒种检测一百万个密钥，则它搜索完全部密钥就需要将近2285年的时间，可见，这是难以实现的。当然，随着科学技术的发展，当出现超高速计算机后，我们可考虑把DES密钥的长度再增长一些，以此来达到更高的保密程度。3.3常见密码算法—2.IDEA2.IDEAIDEA(InternationalDataEncryptionAlgorithm)是国际数据加密算法的简记，是一个分组加密处理算法，其明文和密文分组都是64比特，密钥长度为128比特。该算法是由来学嘉(X.J.Lai)和Massey提出的建议标准算法，已在PGP中得到应用。IDEA算法能够接受64比特分组加密处理，同一算法既可用于加密又可用于解密该算法的设计思想是：“混合使用来自不同代数群中的运算”。3.3常见密码算法—3.AES3.AES1997年4月15日，美国国家标准技术研究所(NIST)发起征集AES(AdvancedEncryptionStandard)算法的活动，并专门成立了AES工作组。目的是为了确定一个非保密的、公开的、全球免费使用的分组密码算法，用于保护下一世纪政府的敏感信息。NIST规定候选算法必须满足下面的要求：密码必须是没有密级的，绝不能像保护商业秘密那样来保护它；算法的全部描述必须公开披露；密码必须可以在世界范围内免费使用；密码系统支持至少128比特长的分组；密码支持的密钥长度至少为128、192和256比特。3.3常见密码算法—4.RSA4.RSAWhitefieldDiffie和MartinHellman于1976年提出了公钥密码系统的思想，然而他们并没有给出一个实用的公钥密码系统。Diffie-Hellman的文章发表两年后，MIT的RonaldRivist、AdiShamir和LenAdlemar开发出了第一个公钥密码体制。1977年，Rivest、Shamir和Adleman三个人实现了公开密钥密码体制，现在称为RSA公开密钥体制，它是第一个既能用于数据加密也能用于数字签名的算法。这种算法易于理解和操作，算法的名字以发明者的名字命名：RonRivest，AdiShamir和LeonardAdleman。但RSA的安全性一直未能得到理论上的证明。它经历了各种攻击，至今未被完全攻破。3.3常见密码算法—4.RSARSA算法原理可以简单描述如下：1.生成两个大素数p和q。2.计算这两个素数的乘积n=p×q。3.计算小于n且与n互质的整数的个数，即欧拉函数φ(n)=(p-1)(q-1)。4.选择一个随机数e满足1<e<φ(n)，并且e和φ(n)互质，即gcd(e,φ(n))=1。5.计算de≡1modφ(n)。d称为e的模反元素。有：de-1=kφ(n)6.保密d，p和q，公开n和e。如果两个正整数a和n互质，那么一定可以找到整数b，使得ab-1被n整除，或者说ab被n除的余数是1。b就叫做a的"模反元素"3.3常见密码算法—4.RSARSA加密的具体实例。设素数p=3，q=17，并令e=13，则RSA的加密操作如下：(1)计算nn=pq=3×17=51，得出公钥n=51，e=13。(2)计算φ(n)和dφ(n)=(p－1)(q－1)=2×16=32。de≡1modφ(n)，所以d=(kφ(n)+1)/e,k=gdc(p-1,q-1)由此算出d=(2×32+1)/13=5，即解密钥是d=5(3)加密和解密处理计算(Alice发送明文”2”)已知Bob的公开密钥是e=13、n=51，则Alice计算密文C=Memodn=213mod51=8192mod51=32Bob收到Alice发来的密文C后，用自己的私钥d解密密文C，即M=Cd

modn=325mod51=512mod51=23.3常见密码算法—4.RSA利用RSA加密时，明文以分组的方式加密：每一个分组的比特数应该小于log2n比特。加密明文x时，利用公钥(e,n)来计算c=xemodn就可以得到相应的密文c。解密的时候，通过计算cdmodn就可以恢复出明文x。选取的素数p和q要足够大，从而乘积n足够大，在事先不知道p和q的情况下分解n是计算上不可行的。常用的公钥加密算法包括：RSA密码体制、ElGamal密码体制散列函数密码体制（MD4、MD5等）3.3常见密码算法—4.RSARSA算法的安全性RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定基于安全性考虑，要求n的长度至少应为1024比特。然而从长期的安全性来看n的长度至少应为2048比特3.3常见密码算法—4.RSARSA算法的速度由于进行的都是大数计算，使得RSA最快的情况也比DES慢上倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近40年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一3.3常见密码算法—5.DH密钥交换算法5.Diffie-Hellman密钥交换协议W.Deffie和M.E.Hellman于1976年首次提出密钥交换体制，通常简称Diffie-Hellman密钥交换协议。Diffie-Hellman密钥交换协议基于求解离散对数问题的困难性，即对于下述等式：Cd=MmodPd称为模P的以C为底数的M的对数在已知C和P的前提下，由d求M很容易，只相当于进行一次指数计算。而再由M反过来求d，则需要指数级次计算。随着P取得足够大，就能实现足够的安全强度。对称密钥交换对称加密和hash都要求通信双方具有相同的密钥。问题：怎样在双方之间安全地传递密钥？密钥哈哈，要是敢直接传递密钥，我就只好偷看了密钥DH算法的基本原理RouterARouterB生成一个整数p生成一个整数qp把p发送到对端把q发送到对端q根据p、q生成g根据p、q生成g生成密钥Xa生成密钥Xb发送YaYa=(g^Xa)modp发送YbYb=(g^Xb)modpYaYbKey=(Yb^Xa)modpKey=(Ya^Xb)modp最后得到的对称密钥双方没有直接传递密钥Diffie-Hellman密钥交换协议例现在假设Alice和Bob使用Diffie-Hellman密钥交换协议，在一个不安全的信道上交换密钥，则其操作步骤如下：1.Alice和Bob确定一个适当的素数p和整数a，并使a是p的原根，其中a和p可以公开。2.Alice秘密选取一个整数，计算，并把发送给Bob。3.Bob秘密选取一个整数，计算，并把发送给Alice。和就是所说的Diffie-Hellman公开值。4.Alice和Bob双方分别计算出共享密钥，即Alice通过计算生成密钥；Bob通过计算生成密钥；因为：

所以，Alice和Bob生成的密钥K是相同的，这样一来就实现了密钥的交换。

Alice和Bob采用Diffie-Hellman密钥交换的安全性是求解离散对数问题的困难性，即从yA或yB以及计算或在计算上是不可行的。Diffie-Hellman密钥交换协议例3.3常见密码算法—5.ElGamal体制1985年，ElGamal设计出该密码体制安全性基于有限域上求解离散对数的困难性即可用于数据加密，亦可用于数字签名美国数字签名标准（DSS）的基础3.3常见密码算法—6.椭圆曲线密码体制ECC1985年，Koblitz和Miller分别将椭圆曲线用于非对称密码体制的设计二人并未发明使用椭圆曲线的密码算法，但用有限域上的椭圆曲线实现了已经存在的非对称密码算法ECC实现同等安全性所需使用的密钥长度比ElGamal、RSA等密码体制短很多，软件实现规模小，硬件实现电路省电。3.4Hash函数杂凑函数简称Hash函数，它能够将任意长度的信息转换成固定长度哈希值(又称数字摘要或消息摘要)，并且任意的不同消息或文件所生成的哈希值是不一样。令h表示Hash函数，则h应满足下列条件：

h的输入可以是任意长度的消息或文件M；

h的输出长度是固定的；

给定h和M，计算h(M)是容易的；

给定h的描述，找两个不同的消息M1和M2，使得h(M1)=h(M2)在计算上是不可行的。3.4Hash函数Hash函数的安全性是指：在现有的计算资源下，找到一个碰撞是不可能的。Hash函数在网络安全应用中，不仅能用于保护消息或文件的完整性，而且也能用作密码信息的安全存储。例如，网页防篡改应用。网页文件管理者首先用网页文件生成系列Hash值，并将Hash值备份存放在安全地方。然后定时再计算这些网页文件的Hash值，如果新产生的Hash值与备份的Hash值不一样，则说明网页文件被篡改了。目前，主要Hash算法有MD2、MD4、MD5、SHA。其中，MD5能产生128比特长度的哈希值，它的使用广泛，常用于网络中文件的完整性检查。但是，据最新研究表明，MD5的安全性受到挑战，已被中国的王小云女士攻破。而SHA由NIST和NSA研究开发，在美国政府中使用，作为安全哈希标准，SHA产生的哈希值比MD5长，有160比特。单向哈希函数一个函数是单向函数，如果：对于所有的，很容易计算；而对于给定的，不可能计算出一个，使得。这里的“不可能计算”可以理解为，用当前最快速的计算机，需要非常长，比如几百万年的时间才能计算出来。单向哈希函数WhitfieldDiffie曾在《应用密码学》中举了一个很生动的比喻，单向函数就像是把盘子打碎，打碎它很容易，但是要把盘子重新拼起来确实难上加难。简而言之，单向函数是一种易于正向计算，但很难反向计算的函数。需要注意的是，单向函数的存在至今仍然是一个没有经过证明的假设，也就是说，到目前为止没有一个函数被证明为单向函数。单向哈希函数什么是哈希函数呢？哈希函数H把一个值x（值x属于一个有很多个值的集合（或者是无穷多个值）），影射到另外一个值ｙ，ｙ属于一个有固定数量个值（少于前面集合）的集合。哈希函数不是可逆函数——不同的输入值可能产生相同的输出，也就是碰撞，或称为冲突。如果一个哈希函数具有单向函数的性质——也就是：给定一个值x，很容易计算H(x)但是，给定一个值y，很难找到一个值x，使得H(x)=y，这个哈希函数叫做单向哈希函数。单向哈希函数如果一个哈希函数除了具有单向函数的性质以外，从计算的可能性来说，很难找到两个不同的输入值x1,x2∈X，使得H(x1)=H(x2)，那么这个函数叫做无碰撞的单向哈希函数。无碰撞是很重要的——可以防止攻击者伪造消息摘要等信息。单向哈希函数(4)从密码学角度而言，适用的哈希函数的基本要求如下：

(1)输入可以是任意长度的；

(2)输出是可以固定长的；

(3)对于任意的值x，H(x)很容易计算；

(4)H(x)是单向的；

(5)H(x)是无冲突的；单向哈希函数Merkle提出了安全哈希函数的一般结构。它是一种迭代结构，将输入报文分为L个大小为b位的分组，若第L个分组不足b位则填充至b位，然后再附加上一个表示输入总长度的分组。由于输入中包含长度，所以攻击者必须找出具有相同哈希值且长度相等的两条报文，或者找出两条长度不等但加入报文长度后哈希值相同的报文，从而增加了攻击的难度。单向哈希函数哈希函数的一般结构可归纳如下：单向哈希函数哈希函数MD2，MD4和MD5产生128位的哈希值RIPEMD也是一个单向哈希函数。SHA-1产生160位的哈希值。RIPEMD-160是RIPEMD的增强版，它产生的是160位的哈希值。MD5和SHA-1是目前应用最广泛的单向哈希函数。MD5的应用MD5算法可以用来在数据库系统中为用户的密码加密。如下：问题：如果所有用户的密码都是一样的会有什么问题？密码学中加盐的含义具体来说就是在原有材料（用户自定义密码）中加入其它成分（一般是用户自有且不变的因素），以此来增加系统复杂度。当这种盐和用户密码相结合后，再通过摘要处理，就能得到隐蔽性更强的摘要值。数字签名数据报文验证HMAC实现数据完整性验证实现身份验证InternetABB+K1加密后的数据“d”数字签名Hash算法加密后的数据d数字签名+K1加密后的数据+K1Hash算法是否相同如果数据被篡改将无法得到相同的数字签名数字签名数据报文验证HMAC实现数据完整性验证MD5实现身份验证SHAInternetABB数字签名Hash算法数字签名+K1加密后的数据+K1Hash算法是否相同加密后的用户信息身份验证使用用户信息经历相同的过程通信双方的身份是靠判断用户信息的真假而被验证的吗？数字签名对数据进行hash运算来保证完整性完整性：数据没有被非法篡改。通过对数据进行hash运算，产生类似于指纹的数据摘要，以保证数据的完整性。土豆两块钱一斤Hash4ehIDx67NMop9土豆两块钱一斤4ehIDx67NMop9土豆三块钱一斤4ehIDx67NMop9我偷改数据Hash2fwex67N32rfee3两者不一致代表数据已被篡改土豆两块钱一斤Hashfefe23fgrNMop7土豆两块钱一斤fefe23fgrNMop7土豆三块钱一斤2fwex67N32rfee3我同时改数据和摘要两者还是不一致Hashfergergr23frewfgh对数据和密钥一起进行hash运算攻击者篡改数据后，可以根据修改后的数据生成新的摘要，以此掩盖自己的攻击行为。通过把数据和密钥一起进行hash运算，可以有效抵御上述攻击。3.5数字签名数字签名(DigitalSignature)是手写签名的电字模拟，是通过电子信息计算处理，产生的一段特殊字符串消息，该消息具有与手写签名一样的特点，是可信的、不可伪造的、不可重用的、不可抵赖的以及不可修改的。因而，通常将这种消息称为数字签名。与手写签名类似，数字签名至少应满足以下三个条件：签名者事后不能否认自己的签名；接收者能验证签名，而任何其他人都不能伪造签名；当双方就签名的真伪发生争执时，第三方能解决双方之间发生的争执。数字签名的原理在文件上手写签名长期以来被用作作者身份的证明，或表明签名者同意文件的内容。实际上，签名体现了以下5个方面的保证：1.签名是可信的。签名使文件的接收者相信签名者是慎重地在文件上签名的。2.签名是不可伪造的。签名证明是签字者而不是其他的人在文件上签字。3.签名不可重用。签名是文件的一部分，不可能将签名移动到不同的文件上。4.签名后的文件是不可变的。在文件签名以后，文件就不能改变。5.签名是不可抵赖的。签名和文件是不可分离的，签名者事后不能声称他没有签过这个文件。数字签名一个数字签名方案一般由签名算法和验证算法组成。签名算法的密钥是秘密的，只有签名人掌握；验证算法则是公开的，以便他人验证。典型的数字签名方案RSA签名体制、Rabin签名体制、ElGamal签名体制和DSS标准。签名与加密很相似一般是签名者利用秘密密钥(私钥)对需签名的数据进行加密验证方利用签名者的公开密钥(公钥)对签名数据做解密运算。签名与加密的不同之处加密的目的是保护信息不被非授权用户访问签名的目的是让消息接收者确信信息的发送者是谁，信息是否被他人篡改。数字签名的产生原理摘要算法签名算法消息摘要数字签名(发送给接收者)消息(发送给接收者)发送者的私钥数字签名的验证原理摘要算法签名算法摘要签名(来自发送者)消息(来自发送者)发送者的公钥消息摘要消息摘要两者相同吗？数字签名下面我们给出数字签名的基本流程。假设Alice需要签名发送一份电子合同文件给Bob。Alice的签名步骤如下：1.Alice使用Hash函数将电子合同文件生成一个消息摘要。2.Alice使用自己的私钥，把消息摘要加密，形成一个数字签名。3.Alice把电子合同文件和数字签名一同发送给Bob。数字签名的验证过程+IDInformation加密Hash_I解密Hash_I私钥公钥本地远端Hash=+身份信息Hash对称密钥数字签名+身份信息Hash12数字证书+Internet对称密钥数字签名数字证书&公钥为信息发送者的公钥&验证数字签名过程数字签名特点:是一种加密的消息摘要，可防止攻击者同时替换消息和消息摘要，同时不需共享密钥，安全性高。缺点是在抗抵赖性和欺骗性方面较弱。（可用带时间戮的数字签名解决）应用用于数据的完整性（即防止数据被修改）验证（确定签名者的身份）。用于签署合同、电子邮件等常用算法：RSA与MD5或SHA-1组合。DSA（只进行数字签名不进行数据加密）算法区别：DSA签名的速度更快，而RSA验证的速度更快。由于大多数情况下签名验证所花费的时间比签名产生所花时间多得多，故在大多数应用程序中RSA要快一些。数字签名存在的问题计算机上进行数字签名并使用这些保证能够继续有效还存在一些问题。计算机文件易于复制，即使签名难以伪造，但是将有效的签名从一个文件剪辑和粘贴到另一个文件比较容易。这就使签名失去了意义。文件在签名后也易于修改，并且不会留下任何修改痕迹。使用公钥加密算法都能用作数字签名，其基本过程如下：1.Alice用她的私钥对文件加密，从而对文件签名。2.Alice将签名后的文件传给Bob3.Bob用Alice的公钥解密文件，从而验证签名。数字签名基本协议过程在实际过程中，上面的做法效率太低。为节省时间，数字签名协议常与单向Hash函数一起使用。Alice并不对整个文件签名，而是只对文件的Hash值签名。Hash函数和数字签名算法是事先协商好的。过程如下：Alice产生文件的单向散列值。2.Alice用她的私人密钥对散列加密，以此表示对文件的签名。3.Alice将文件和散列签名送给Bob4.Bob用Alice发送的文件产生文件的单向散列值，同时用Alice的公钥对签名的散列解密。如果签名的散列值与自己产生的散列值匹配，签名是有效的。3.5.2数字签名的应用例子现在Alice向Bob传送数字信息，为了保证信息传送的保密性、真实性、完整性和不可否认性，需要对要传送的信息进行数字加密和数字签名，其传送过程为：1.Alice准备好要传送的数字信息（明文）。2.Alice对数字信息进行哈希运算，得到一个信息摘要。3.Alice用自己的私钥对信息摘要进行加密得到Alice的数字签名，并将其附在数字信息上。4.Alice随机产生一个加密密钥，并用此密钥对要发送的信息进行加密，形成密文。5.Alice用Bob的公钥对刚才随机产生的加密密钥进行加密，将加密后的DES密钥连同密文一起传送给Bob3.5.2数字签名的应用例子现在Alice向Bob传送数字信息，为了保证信息传送的保密性、真实性、完整性和不可否认性，需要对要传送的信息进行数字加密和数字签名，其传送过程为：6.Bob收到Alice传送过来的密文和加过密的DES密钥，先用自己的私钥对加密的DES密钥进行解密，得到DES密钥。7.Bob然后用DES密钥对收到的密文进行解密，得到明文的数字信息，然后将DES密钥抛弃（即DES密钥作废）。8.Bob用Alice的公钥对Alice的数字签名进行解密，得到信息摘要。9Bob用相同的hash算法对收到的明文再进行一次hash运算，得到一个新的信息摘要。10.Bob将收到的信息摘要和新产生的信息摘要进行比较，如果一致，说明收到的信息没有被修改过。3.6数字水印数字水印(DigitalWatermark)技术，是指在数字化的数据内容中嵌入不明显的记号。被嵌入的记号通常是不可见或不可察的，但是通过计算操作可以检测或者被提取。水印与源数据紧密结合并隐藏其中，成为源数据不可分离的一部分，并可以经历一些不破坏源数据使用价值或商用价值的操作而存活下来。根据信息隐藏的目的和技术要求，数字水印应具有3个基本特性：1.隐藏性（透明性）。水印信息和源数据集成在一起，不改变源数据的存储空间；嵌入水印后，源数据必须没有明显的降质现象；水印信息无法为人看见或听见，只能看见或听见源数据；2.鲁棒性（免疫性、强壮性）。鲁棒性是指嵌入水印后的数据经过各种处理操作和攻击操作以后，不导致其中的水印信息丢失或被破坏的能力。处理操作包括：模糊、几何变形、放缩、压缩、格式变换、剪切、D/A和A/D转换等攻击操作包括：有损压缩、多拷贝联合攻击、剪切攻击、解释攻击等等。3.安全性。指水印信息隐藏的位置及内容不为人所知，这需要采用隐蔽的算法，以及对水印进行预处理（如加密）等措施。3.6.1数字水印产生背景多媒体通信业务和Internet——“数字化、网络化”的迅猛发展给信息的广泛传播提供了前所未有的便利,各种形式的