(英文)计算机非对称密钥加密.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,Chapter 4,Computer-based Asymmetric Key Encryption,计算机非对称密钥加密,Overview of Asymmetric Key encryption,非对称密钥加密概述,probably most significant advance in the 3000 year history of cryptography,在3000年密码学历史长河中是一个巨大的进步,uses,two,keys a public&a private key,使用两个密钥一个公钥和一个私钥,asymmetric,since parties are,not,equal,非对称是因为通信双方使用的密钥不相同,complements,rather than,replaces private key crypto,是对对称密钥加密的补充而不是取代,Overview of Asymmetric Key encryption,非对称密钥加密概述,Important to know who should know which key(s),重要的是收发双方应该知道哪些密钥而不需知道哪些密钥,In general:,通常,Sender encrypts with recipients public key,发送者用接收者的公钥加密,Recipient decrypts with its private key,接收者用自己的私钥解密,Matrix of Keys,密钥矩阵,Fig 4.1,Key details,A,should know,B,should know,As private key,Yes,No,As public key,Yes,Yes,Bs private key,No,Yes,Bs public key,Yes,Yes,Asymmetric Key Cryptography,非对称密钥加密,Fig 4.2,Plain text,Encrypt with Bs public key,Plain text,Decrypt with Bs private key,Sender,(A),Network,Receiver,(B),Cipher text,Cipher text,Asymmetric Key Example,非对称密钥举例,Consider a bank and its customers,考虑一个银行和其客户之间的交易行为,Customers encrypt their messages with banks public key,客户用银行的公钥加密消息,Bank decrypts messages with its private key,银行用自己的私钥解密消息,Asymmetric Key Cryptography Example,非对称密钥加密举例,Fig 4.3,Customer A,Customer B,Customer C,Banks public key,Banks public key,Banks public key,Banks private key,Bank,RSA Algorithm,RSA,算法,By,Rivest,Shamir,&,Adleman,of MIT in 1977,Worlds most popular Asymmetric Key Encryption algorithm,世界上最著名的非对称密钥加密算法,Based on,exponentiationin,a finite(Galois)field over integers modulo a prime,基于有限域中素数的幂模运算,nb,.exponentiation takes O(log n),3,)operations(easy),幂运算时间复杂度为,O(log n),3,)（,容易）,security due to cost of factoring large numbers,安全保证在于大数的因式分解,nb,.factorization takes O(e,log n log log n,)operations(hard),因式分解,时间复杂度为,O(e,log n log log n,),（,困难）,RSA Algorithm,RSA,算法,Fig 4.4,1.,Choose two large prime numbers P and Q.,2.Calculate N=P x Q.,3.Select the public key(i.e.the encryption key)E such that it is not a factor of(P 1)and(Q 1).,4.Select the private key(i.e.the decryption key)D such that the following equation is true:,(D x E)mod(P 1)x(Q 1)=1,5.For encryption,calculate the cipher text CT from the plain text PT as follows:,CT=PT,E,mod N,6.Send CT as the cipher text to the receiver.,7.For decryption,calculate the plain text PT from the cipher text CT as follows:,PT=CT,D,mod N,RSA Example,RSA,例子,Select primes:,p,=17&,q,=11,Compute,n,=,pq,=17,11=187,Compute,(,p,1)(,q-,1)=16,10=160,Select,e,:,gcd,(e,160)=1;,choose,e,=7,Determine,d,:,d*e=,1 mod 160,and,d,160,Value is,d=23,since,23,7=161=10,160+1,Publish public key,E=7,187,Keep secret private key,D=23,17，11,RSA Example,RSA,例子,Select primes:,p,=17&,q,=11,Compute,n,=,pq,=17,11=187,Compute,(,p,1)(,q-,1)=16,10=160,Select,e,:,gcd,(e,160)=1;,choose,e,=7,Determine,d,:,de=,1 mod 160,and,d,160,Value is,d=23,since,23,7=161=10,160+1,Publish public key,KU=7,187,Keep secret private key,KR=23,17，11,为什么不能公布,p,和,q,的值？,Example of RSA Algorithm,RSA,算法举例,Fig 4.6,A,F,F 6,6,5,Result modulo 119,=41,1.,Encode the original character using A=1,B=2 etc.,2.Raise the number to the power,E,here 5.,3.Divide the result by 119 and get the remainder.The resulting number is the cipher text.,Encryption algorithm using the public key,B,41,41,77,Result modulo 119,6 F,1.,Raise the number to the power,D,here 77.,2.Divide the result by 119 and get the remainder.The resulting number is the cipher text.,3.Decode the original character using 1=A,2=B etc.,Decryption algorithm using the private key,F,Symmetric v/s Asymmetric,对称和非对称的比较,Fig 4.7,Characteristic,Symmetric Key Cryptography,Asymmetric Key Cryptography,Key used for encryption/decryption,Same key is used for encryption and decryption,One key used for encryption and another,different key is used for decryption,Speed of encryption/decryption,Very fast,Slower,Size of resulting encrypted text,Usually same as or less than the original clear text size,More than the original clear text size,Key agreement/exchange,A big problem,No problem at all,Number of keys required as compared to the number of participants in the message exchange,Equals about the square of the number of participants,so scalability is an issue,Same as the number of participants,so scales up quite well,Usage,Mainly for encryption and decryption(confidentiality),cannot be used for digital signatures(integrity and non-repudiation checks),Can be used for encryption and decryption(confidentiality)as well as for digital signatures(integrity and non-repudiation checks),The best of both worldsdigital envelope,两全其美数字信封,A encrypts the plain text with symmetric key K1,Then encrypts K1 with Bs public key K2Key wrapping,A puts the cipher text and encrypted symmetric key K1 inside a,digital envelope,and send to B,B decrypts the encrypted symmetric key K1 with its private key K3 and gets K1,Finally decrypts the cipher text with symmetric key K1 and gets the plain text,Digital Signature Concept,数字签名概念,Sender encrypts message or its fingerprint with its private key,发送方用自己的私钥加密消息或其指纹,Guarantees that only the sender could have created this message,保证了只有发送方才能产生这些消息,Basis for Non-repudiation,是不可抵赖检查的基础,Basis for Digital Signatures,数字签名基础,Fig 4.16,Plain text,Encrypt with As private key,Plain text,Decrypt with As public key,Sender,(A),Network,Receiver,(B),Cipher text,Cipher text,Message Digest Concept,消息摘要概念,Also called as,Hash,也叫散列（哈希）,Unique representation of a message,是消息的唯一表示,Similar to finger print of a human,类似于人的指印,Message Digest Idea,消息摘要思想,Fig 4.18,Original number is 7391743,OperationResult,Multiply 7 by 3 21,Discard first digit 1,Multiply 1 by 9 9,Multiply 9 by 1 9,Multiply 9 by 7 63,Discard first digit 3,Multiply 3 by 4 12,Discard first digit 2,Multiply 2 by 3 6,Message digest is 6,消息中的每一位都参加运算,Message Digest Concept,消息摘要概念,Fig 4.19,Original data,101010101,010101010,.,.,0101,1011,Message Digest,Message digest algorithm,Message Digest Demands 1,消息摘要要求-1,Fig 4.20,Original data,Message digest algorithm,Message digest,Should be possible and the result should always be the same,可行且结果总是相同,Message Digest Demands 2,消息摘要要求-2,Fig 4.21,Original data,Reverse Message digest algorithm,Message digest,Must not be possible,反向不可行,Message Digest Demands 3,消息摘要要求-3,Fig 4.22,Original data block 1,Message digest algorithm,Message digest 1,Original data block 2,Message digest algorithm,Message digest 2,These two message digests must be different,这两个消息摘要必须不相同,Message Digest Differences,消息摘要差异,Even if the original messages differ minutely,message digests differ dramatically,即使原始消息差别很小，但消息摘要的差别却很大,Basis for the guarantee of uniqueness,是消息摘要唯一性保证的基础,Message Digest Example,消息摘要举例,Fig 4.23,Please,pay,the newspaper bill today,Please pay the,newspaper,bill tomorrow,306706092,A864886F70D010705A05A3058020100300906052B0E03021A0500303206092A864886F70D010701A0250423506C656173652070617920746865206E65777370617065722062696C6C20746F646179041479630AC8041BAA1C40747F2FC29D881AEF92299B,Message,Message digest,Message,Message digest,306,A06092A864886F70D010705A05D305B020100300906052B0E03021A0500303506092A864886F70D010701A0280426506C656173652070617920746865206E65777370617065722062696C6C20746F6D6F72726F7704146EEC2E0DB9570A5AF6CEB631CE057AE830A87C5B,Message Digest Algorithms,消息摘要算法,Basic principle:Take the original message,and reduce it to a smaller,fingerprint,基本原理：将原始消息处理成比其小的指印,Examples:MD5,SHA-1,例如：,MD5，SHA-1,SHA-1 is considered stronger,SHA-1,算法要强壮些,MD5 Overview,MD5,概要,1 Pad message so its length is 448 mod 512,填充消息使其长度为,448 mod 512,2 Append a 64-bit length value to message,在末尾附加一个64位的消息长度,3 Divide the input into 512-bit blocks,将输入分成512位的块,4 initialise 4-word(128-bit)chaining variables(A,B,C,D),初始4个字（128位）的链接变量,(A,B,C,D),MD5 Overview,MD5,概要,5 process message in 16-word(512-bit)blocks:,处理16个字（512位）的消息块,using 4 rounds of 16 steps operations on message block&chaining variables,对消息块和链接变量使用4轮16步运算,add output to chaining variables input to form new chaining variables value,将输出加到链接变量输入以形成新的链接变量值,6 output hash value is the final chaining variables value,输出的散列值是最后的链接变量值,MD5 Overview,MD5,概要,4轮16次迭代运算,MD5 Compression Function,MD5,压缩函数,each round has 16 steps of the form:,每一轮要进行16次如下形式的运算,a=b+(a+P(b,c,d)+Mi+Tk)s),a,b,c,d refer to the chaining variables,but used in varying permutations,链接变量,a,b,c,d,在每步迭代中要进行置换变化,where P(b,c,d)is a different nonlinear function in each round,P(b,c,d),是非线性函数,Ti is a constant value,Ti,是常量值,One MD5 Operation,a,b,c,d,Process P,Add,Add,tk,Shift,Add,a,b,c,d,Step 1,Step 2,Step 3,Step 4,Step 5,Step 6,Add,Mi,Step 7,每一次迭代,ABCD,分别循环右移一位,Strength of MD5,MD5,的强度,MD5 hash is dependent on all message bits,Rivest,claims security is good as can be,known attacks are:,Berson,92 attacked any 1 round using differential cryptanalysis(but cant extend),Boer&,Bosselaers,93 found a pseudo collision(again unable to extend),Dobbertin,96 created collisions on MD compression function(but initial constants prevent exploit),conclusion is that MD5 looks vulnerable soon,Secure Hash Algorithm(SHA-1),安全,Hash,算法,(,SHA-1),SHA was designed by NIST&NSA in 1993,revised 1995 as SHA-1,SHA,由,NIST&NSA,在1993年设计，1995年修正为,SHA-1,produces 160-bit hash values,产生160位的散列值,now the generally preferred hash algorithm,是目前首选的散列算法,based on design of MD4 with key differences,基于,MD4,的设计，但在密钥上有差别,Two characteristic of SHA-1,SHA-1,的两个,特征,It should be computationally infeasible：,Obtain the original message,given its message digest,根据消息摘要取得原消息不可行,Find two messages,producting,the same message digest,找到两个消息产生相同消息摘要不可行,SHA Overview,SHA,概要,pad message so its length is 448 mod 512,append a 64-bit length value to message,initialise 5-word(,160-bit,)buffer(A,B,C,D,E)to,(67452301,efcdab89,98badcfe,10325476,c3d2e1f0,),process message in 16-word(512-bit)chunks:,use 4 rounds of,20 steps,operations on message block&chaining variables,add output to input to form new chaining variables value,output hash value is the final chaining variables value,SHA-1 Compression Function,SHA-1,压缩函数,each round has 20 steps which replaces the 5 buffer words thus:,(A,B,C,D,E)-(E+p,t,(B,C,D)+(A5)+Wt+Kt),A,(B30),C,D),a,b,c,d refer to the 4 words of the buffer,t is the step number,p,t,(B,C,D),is nonlinear function for round,Wt,is derived from the message sub-block,Kt,is a constant value derived from sin,Single SHA-1 Iteration,单步,SHA-1,迭代,Fig 4.39,a,b,c,d,e,Process,P,Add,s,5,Add,Add,Wt,Add,Kt,a,b,c,d,e,有错误？,Single SHA-1 Iteration,单步,SHA-1,迭代,Comparison of MD5 and SHA-1,MD5,与,SHA-1,比较,Fig 4.42,Point of discussion,MD5,SHA,Message digest length in bits,128,160,Attack to try and find the original message given a message digest,Requires 2,128,operations to break in,Requires 2,160,operations to break in,therefore more secure,Attack to try and find two messages producing the same message digest,Requires 2,64,operations to break in,Requires 2,80,operations to break in,Successful attacks so far,There have been reported attempts to some extent(as we discussed earlier),No such claims so far,Speed,Faster(64 iterations,and 128-bit buffer),Slower(80 iterations,and 160-bit buffer),Software implementation,Simple,does not need any large programs or complex tables,Simple,does not need any large programs or complex tables,Message Authentication Code(MAC),消息鉴别码,Similar to message digest,与消息摘要相似,In addition,also involves encryption,另外，涉及加密,Sender and receiver must know a shared secret key,发送方和接收方必须知道共享密钥,Message Authentication Code(MAC),消息鉴别码,Fig 4.43,S,E,N,D,E,R,(A),M,H1,MAC,M,H1,Send,M,H2,MAC,R E C E I V E R,(B),Compare,Step 1,Step 2,Step 3,Step 4,K,K,Message Authentication Code(MAC),消息鉴别码,T,he important respect is that the MAC algorithm is not reversibleit is sufficient to be a one-way function,重要的一点是,MAC,算法不需要可逆一个单向函数就可以了,HMAC Concept,HMAC,概念,Fig 4.44,Existing message digest algorithms such as MD5 or SHA-1,Original message,Message Digest,(MD),Encrypt,MAC,Final output,Key K,Complete HMAC Operation,完整,HMAC,操作,Fig 4.52,Transformed key(K),Key(K),ipad,XOR,S1,M,Message Digest algorithm,H,Transformed key(K),opad,XOR,S2,H,HMAC,Message Digest algorithm,