《cnspp-ch09-publickeycryptographyandrsa》由会员分享，可在线阅读，更多相关《cnspp-ch09-publickeycryptographyandrsa（35页珍藏版）》请在金锄头文库上搜索。
1、Computer Science&Technology School of Shandong University,Instructor: Hou Mengbo Email: houmb AT Office: Information Security Research Group,Guide to Information Security,Chapter 9 Public Key Cryptography and RSA,Private-Key Cryptography,traditional private/secret/single key cryptography uses one ke
2、y shared by both sender and receiver if this key is disclosed communications are compromised also is symmetric, parties are equal hence does not protect sender from receiver forging a message & claiming is sent by sender Based on substitution and permutation,Public-Key Cryptography,probably most sig
3、nificant advance in the 3000 year history of cryptography uses two keys a public & a private key asymmetric since parties are not equal uses clever application of number theoretic concepts to function complements rather than replaces private key crypto Based on hard problems in mathematics,Are these
4、 opinions right?,Public key crypto is safer than private key crypto (X) Public key crypto will replace private key crypto (X) Key distribution of private key crypto is more complicated than that of public key(X),Public-Key Cryptography,public-key/two-key/asymmetric cryptography involves the use of t
5、wo keys: a public-key, which may be known by anybody, and can be used to encrypt messages, and verify signatures a private-key, known only to the recipient, used to decrypt messages, and sign (create) signatures is asymmetric because those who encrypt messages or verify signatures cannot decrypt mes
6、sages or create signatures,Why Public-Key Cryptography?,developed to address two key issues: key distribution how to have secure communications in general without having to trust a KDC with your key digital signatures how to verify a message comes intact from the claimed sender public invention due
7、to Whitfield Diffie & Martin Hellman at Stanford Uni in 1976 known earlier in classified community,Public-Key Characteristics,Public-Key algorithms rely on two keys with the characteristics that it is: computationally infeasible to find decryption key knowing only algorithm & encryption key computat
8、ionally easy to en/decrypt messages when the relevant (en/decrypt) key is known either of the two related keys can be used for encryption, with the other used for decryption (in some schemes),Public-Key Crypto:Encryption,Public-Key Crypto:Authentication,Public key crypto vs private key crypto,Public
9、-Key Cryptosystem:Secrecy,Public-Key Cryptosys:Authentication,Public-Key Cryptosystems:Secrecy&Authentication,Public-Key Applications,can classify uses into 3 categories: encryption/decryption (provide secrecy) digital signatures (provide authentication) key exchange (of session keys) some algorithm
10、s are suitable for all uses, others are specific to one,Examples,Requests for public key cryptography,Public Key pairs generation is easy. Encryption is computationally easy(know plaintext M and KU). Decryption is computationally easy (know ciphertext C and KR). computationally infeasible to find KR
11、 from KR. computationally infeasible to find plaintext from KU and ciphertext. Sequence of encryption and decryption is commutative,The inbeing of public key crypto,One-way function y=f(x) easy,while x=f-1(y) difficult. One-way trapdoor function know k and x, y=fk(x) easy know k and y, x= fk-1(y) ea
12、sy know y,but not k, x= fk-1(y) difficult One-way trapdoor function is the key to design public key cryptography.,Security of Public Key Schemes,like private key schemes brute force exhaustive search attack is always theoretically possible but keys used are too large (512bits) security relies on a l
13、arge enough difference in difficulty between easy (en/decrypt) and hard (cryptanalyse) problems more generally the hard problem is known, its just made too hard to do in practise requires the use of very large numbers hence is slow compared to private key schemes,RSA,by Rivest, Shamir & Adleman of M
14、IT in 1977 best known & widely used public-key scheme based on exponentiation in a finite (Galois) field over integers modulo a prime uses large integers (eg. 1024 bits) security due to cost of factoring large numbers nb. factorization takes O(e log n log log n) operations (hard),RSA Key Setup,each
15、user generates a public/private key pair by: selecting two large primes at random - p, q computing their system modulus N=p.q note (N)=(p-1)(q-1) selecting at random the encryption key e where 1e(N), gcd(e,(N)=1 solve following equation to find decryption key d e.d=1 mod (N) and 0dN publish their pu
16、blic encryption key: KU=e,N keep secret private decryption key: KR=d,N,RSA Use,to encrypt a message M the sender: obtains public key of recipient KU=e,N computes: C=Me mod N, where 0MN to decrypt the ciphertext C the owner: uses their private key KR=d,N computes: M=Cd mod N note that the message M must be smaller than the modulus N (block if needed),Why RSA Works,because of Eulers Theorem: a(n) = 1 mod N where gcd(a,N)=1 in RSA have: N=p.q (N)=(p-1)(q-1) c
