Chapter3OUTLINEAuthenticationApproaches to Message AuthenticationSlide 5Slide 6One-way HASH functionSecure HASH FunctionsSimple Hash FunctionMessage Digest Generation Using SHA-1SHA-1 Processing of single 512-Bit BlockOther Secure HASH functionsHMACHMAC StructurePublic-Key Cryptography PrinciplesEncryption using Public-Key systemAuthentication using Public-Key SystemApplications for Public-Key CryptosystemsRequirements for Public-Key CryptographySlide 20Public-Key Cryptographic AlgorithmsThe RSA Algorithm – Key GenerationExample of RSA AlgorithmThe RSA Algorithm - EncryptionThe RSA Algorithm - DecryptionDiffie-Hellman Key EchangeOther Public-Key Cryptographic AlgorithmsKey Management Public-Key Certificate UseHenric Johnson 1Chapter3Chapter3Public-Key Public-Key Cryptography and Cryptography and Message Message AuthenticationAuthenticationHenric JohnsonBlekinge Institute of Technology, Swedenhttp://www.its.bth.se/staff/hjo/[email protected] Johnson 2OUTLINEOUTLINE•Approaches to Message Authentication•Secure Hash Functions and HMAC•Public-Key Cryptography Principles•Public-Key Cryptography Algorithms•Digital Signatures•Key ManagementHenric Johnson 3AuthenticationAuthentication•Requirements - must be able to verify that:1. Message came from apparent source or author,2. Contents have not been altered,3. Sometimes, it was sent at a certain time or sequence.•Protection against active attack (falsification of data and transactions)Henric Johnson 4Approaches to Message Approaches to Message AuthenticationAuthentication•Authentication Using Conventional Encryption–Only the sender and receiver should share a key•Message Authentication without Message Encryption–An authentication tag is generated and appended to each message•Message Authentication Code–Calculate the MAC as a function of the message and the key. MAC = F(K, M)Henric Johnson 5Henric Johnson 6One-way HASH One-way HASH functionfunctionHenric Johnson 7One-way HASH functionOne-way HASH function•Secret value is added before the hash and removed before transmission.Henric Johnson 8Secure HASH FunctionsSecure HASH Functions•Purpose of the HASH function is to produce a ”fingerprint.•Properties of a HASH function H :1. H can be applied to a block of data at any size2. H produces a fixed length output3. H(x) is easy to compute for any given x.4. For any given block x, it is computationally infeasible to find x such that H(x) = h5. For any given block x, it is computationally infeasible to find with H(y) = H(x).6. It is computationally infeasible to find any pair (x, y) such that H(x) = H(y)xy Henric Johnson 9Simple Hash FunctionSimple Hash Function•One-bit circular shift on the hash value after each block is processed would improveHenric Johnson 10Message Digest Message Digest Generation Using SHA-Generation Using SHA-11Henric Johnson 11SHA-1 Processing of SHA-1 Processing of single 512-Bit Blocksingle 512-Bit BlockHenric Johnson 12Other Secure HASH Other Secure HASH functionsfunctionsSHA-1 MD5 RIPEMD-160Digest length 160 bits 128 bits 160 bitsBasic unit of processing512 bits 512 bits 512 bitsNumber of steps80 (4 rounds of 20)64 (4 rounds of 16)160 (5 paired rounds of 16)Maximum message size264-1 bitsHenric Johnson 13HMACHMAC•Use a MAC derived from a cryptographic hash code, such as SHA-1.•Motivations:–Cryptographic hash functions executes faster in software than encryptoin algorithms such as DES–Library code for cryptographic hash functions is widely available–No export restrictions from the USHenric Johnson 14HMAC StructureHMAC StructureHenric Johnson 15Public-Key Public-Key Cryptography Cryptography PrinciplesPrinciples•The use of two keys has consequences in: key distribution, confidentiality and authentication.•The scheme has six ingredients (see Figure 3.7)–Plaintext–Encryption algorithm–Public and private key–Ciphertext–Decryption algorithmHenric Johnson 16Encryption using Encryption using Public-Key systemPublic-Key systemHenric Johnson 17Authentication usingAuthentication using Public-Key SystemPublic-Key SystemHenric Johnson 18Applications for Public-Applications for Public-Key CryptosystemsKey Cryptosystems•Three categories:–Encryption/decryption: The sender encrypts a message with the recipient’s public key.–Digital signature: The sender ”signs” a message with its private key.–Key echange: Two sides cooperate two exhange a session key.Henric Johnson 19Requirements for Requirements for Public-Key Public-Key CryptographyCryptography1. Computationally easy for a party B to generate a pair (public key KUb, private key KRb)2. Easy for sender to generate ciphertext: 3. Easy for the receiver to decrypt ciphertect using private key:)(MECKUb)]([)( MEDCDMKUbKRbKRbHenric Johnson 20Requirements for Requirements for Public-Key Public-Key CryptographyCryptography4. Computationally infeasible to determine private key (KRb) knowing public key (KUb)5. Computationally infeasible to recover message M, knowing KUb and ciphertext C6. Either of the two keys can be used for encryption, with the other used for decryption:)]([)]([ MEDMEDMKRbKUbKUbKRbHenric Johnson 21Public-Key Public-Key Cryptographic Cryptographic AlgorithmsAlgorithms•RSA and Diffie-Hellman •RSA - Ron Rives, Adi Shamir and Len Adleman at MIT, in 1977.–RSA is a block cipher–The most widely implemented•Diffie-Hellman –Echange a secret key securely–Compute discrete logarithmsHenric Johnson 22The RSA Algorithm – The RSA Algorithm – Key GenerationKey Generation1. Select p,q p and q both prime2. Calculate n = p x q3. Calculate 4. Select integer e5. Calculate d6. Public Key KU = {e,n}7. Private key KR = {d,n})1)(1()(  qpn)(1;1)),(gcd( neen )(mod1ned Henric Johnson 23Example of RSA Example of RSA AlgorithmAlgorithmHenric Johnson 24The RSA Algorithm - The RSA Algorithm - EncryptionEncryption•Plaintext: M<n•Ciphertext: C = Me (mod n)Henric Johnson 25The RSA Algorithm - The RSA Algorithm - DecryptionDecryption•Ciphertext: C•Plaintext: M = Cd (mod n)Henric Johnson 26Diffie-Hellman Key Diffie-Hellman Key EchangeEchangeHenric Johnson 27Other Public-Key Other Public-Key Cryptographic Cryptographic AlgorithmsAlgorithms•Digital Signature Standard (DSS)–Makes use of the SHA-1–Not for encryption or key echange•Elliptic-Curve Cryptography (ECC)–Good for smaller bit size–Low confidence level, compared