Cryptographic TechniquesTopic: Crytographic TechniquesSlide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Cryptographic TechniquesInstructor: Jerry Gao Ph.D.San Jose State Universityemail: [email protected]: http://www.engr.sjsu.edu/gaojerryMay, 2000Topic: Crytographic Techniques- Encryption and decryption- Symmetric encryption - Asymmetric or public-key encryption- Message digesting or hashing - Digital signatures and enveloping- digital signatures, dual signatures, blind signatures- Public key management- certificates and certification authoritiesJerry Gao Ph.D. 5/20000OutlineAll Rights ReservedJerry Gao Ph.D. 5/2000Introduction to Crytographic TechniquesTopic: Crytographic TechniquesJerry Gao Ph.D. 5/2000In cryptographics, a message in human readable form is referred to plaintext or cleartext.Encryption:Encryption refers to a process which disguises a cleartext message to hide its substance and generates a message, known as ciphertext.Plaintext is denoted by P, whereas ciphertext is denoted by C.The encryption function E operates on P to produce C based on a key value K:E k (P) = CEncryption and DecryptionEncryptionKeyPlaintext CiphtextTopic: Crytographic TechniquesJerry Gao Ph.D. 5/2000Encryption and DecryptionDecryption:The reverse process of encryption is known as a decryptiondecryption, in which a cihhertext is converted back to its original cleartext form.In the reverse process, the decryption function D operates on C to produce Pbased on a key value K:D k (C) = PEncryptionKeyCiphertext PlaintextTopic: Crytographic TechniquesJerry Gao Ph.D. 5/2000Symmetric EncryptionTopic: Crytographic TechniquesSymmetric encryption (secret-key encryption, or single-key encryption):Secret-key encryption refers to the use of a shared key for both encryption bythe transmitter and decryption by the receiver.Work step:- Sender sends a message after encryption with a secret-key.- Receiver decrypt the message with the same secret key after receiving it.InternetAnne sends a messageBobreceivesAnne’smessageEncryptwith a secret keyDecryptwith a secret keyEncryptedMessageEncryptedMessageJerry Gao Ph.D. 5/2000Symmetric EncryptionTopic: Crytographic TechniquesSpecial features of symmetric encryption:- Two communication parties use and share the same key.- Encryption and decryption is carried out based on the same key.- Both parties must agree on the secret key before communications.Advantages:- Useful in many cases which only involves two-party communications.Problems and limitations:- Complex in key distribution (key generation, transmission, and storage).- Not scalable.- Impractical to support large group of communications in networks.- Impossible to support exchanging messages with a large group of previouslyunknown parties over a public open network. Example: DES (the Data Encryption Standard)Jerry Gao Ph.D. 5/2000Asymmetric EncryptionTopic: Crytographic TechniquesAsymmetric encryption (public-key encryption):Public-key encryption (asymmetric encryption) use a pair of keys for each party.- One key is known as a “public key”, which is known to other parties.- One key is known as a “private key” or a “secret key”, which must be confidential, and is known only to its owner.- The public key encrypts the message.- The private key decrypts the message. InternetAnne sends a messageBobreceivesAnne’smessageEncryptwith a public keyPK(Bob)Decryptwith Bob’ private keySK(Bob)ScrambledMessageScrambledMessageJerry Gao Ph.D. 5/2000Asymmetric EncryptionTopic: Crytographic TechniquesSpecial features of asymmetric encryption (public-key encryption):SK(PK(M)) = MAdvantages:- Easy to key distribution (key generation, maintain and storage)- Scalable to support large group of users in an public network- Easy to support unknown users since no previous consent is needed.- Better protection than symmetric encryption.Problems and limitations:- Slow performanceApplications: E-commerce, snoop-proof email system.Standards: the best known public-key encryption algorithm --> RSAJerry Gao Ph.D. 5/2000, ShRSA AlgorithmTopic: Crytographic TechniquesThe RSA algorithm was developed by Rivest, Shamir, and Adleman at MIT in 1978.The basic algorithm is outlined below:1: Choose two large distinct primes, p and q.2: Compute the product (modulus) n = pq. 3: Randomly choose encryption key e, such that e and (p-1)(q-1) are relatively prime.4: Finally use Euclid’s algorithm to compute the decryption key, d such thate . d = 1 (mod (p-1) . (q -1)). Where, d and n are relatively prime. e and n are the public key. d is the secret key.To encrypt a message M, eC = M mod nTo decrypt C, dM = C mod nJerry Gao Ph.D. 5/2000Comparing Symmetric Encryption and Asymmetric EncryptionTopic: Crytographic TechniquesFeatures Secret-Key Encryption Public-Key EncryptionNo. of keys Single Key Pair of KeysTypes of keys Secret Key only One Public Key andone Private KeyKey Management Simple but difficult to Need digital certificatesmanage and trusted third partiesPerformance Very fast SlowerUsage Used for bulk data Used for less demandingencryption, such as applications such as a phone system, encryption small doc. orto sign messagesStandards Data Encryption the RSA algorithmStandard (DES)Jerry Gao Ph.D. 5/2000Message Digesting or HashingTopic: Crytographic TechniquesMessage digesting is a way to provide integrity without confidentiality.The basic idea is to apply a digesting or hash algorithm to the (long) message to produce a (short) message digest.Since the encryption is only applied to a very small quantity, and message digesting is very much faster than encryption. Checking==>When the message arrives, the receiver computes a hash of the message using the same algorithm. If this matches the decrypted MIC that came with the message, then the message has not been tampered with.A good Hash function has two properties:- It must be difficult to invert.- It must be resistant to collision.Two well-known Hash functions in payment protocols are MD5 and SHA.Jerry Gao Ph.D. 5/2000Computing a message integrity check (MIC)Topic: Crytographic TechniquesMessageMIC MessageHashDigestAlgorithmBlockCipherMessageIntegrity CheckSecret KeyJerry Gao Ph.D. 5/2000Digital SignaturesTopic: Crytographic TechniquesWhat is a digital signature?- Digital signatures are implemented using public-key encryption.- A digital