Ch4_Part2_Cryptography.pdf

Ch4-Part 2: Cryptography Block Ciphers 2023 Cryptography Cryptography 2023 1  Stream Ciphers vs Block Ciphers Stream Ciphers: For stream encryption each byte of the data For stream encryption spahrep ro ,tib hcae hcihw ni , stream is e...

Ch4-Part 2: Cryptography Block Ciphers 2023 Cryptography Cryptography 2023 1  Stream Ciphers vs Block Ciphers Stream Ciphers: For stream encryption each byte of the data For stream encryption spahrep ro ,tib hcae hcihw ni , stream is encrypted separately..yletarapes detpyrcne si maerts atad eht fo ,etyb hcae The input symbols are transformed one at atime. The advantage of a stream cipher is that it can be applied immediately to whatever data items are ready to transmit. Cryptography Cryptography 2023 2 Block Ciphers : A block cipher encrypts a group of plaintext symbols as a singleblock. A block cipher algorithm performs its work on a quantity of plaintext data all at once. Blocks for such algorithms are typically 64, 128, 256 bits or more. All blocks have to have the same size of bits, otherwise Padding is used. Cryptography 2023 3 Categories of cryptography Cryptography Cryptography 2023 4  Symmetric Encryption Algorithms (Private Key Cryptography) DES: The Data Encryption Standard DES uses only standard arithmetic and logical operations on a block of data up to 64 bits long and a private key 56 bits long. Encrypting with DES involves 16 cycles (rounds) , each employing replacing blocks of bits (called a substitution step), shuffling the bits (called a permutation step), and mingling in bits from the key (called a key transformation). Cryptography 2023 5 Cryptography 2023 6 Security of DES In 1997, researchers using a network of over 3,500 machines in parallel were able to infer a DES key in four months’ work. And in 1998 for approximately $200,000 U.S. researchers built a special DES cracker machine that could find a DES key in approximately four days. Cryptography 2023 7 AES: Advanced Encryption Standard Like DES, AES usesrepeat cycles. There are 10, 12, or 14 cycles (rounds) for private keys of 128, 192, and 256 bits, respectively. Each round consists of four steps: Byte substitution. This step uses a substitution substituting each byte of a 128- bit block according to a substitution table. This is a straight diffusion operation. Shift row. Certain bits are shifted to other positions. This is a straight confusion operation. Mix column. This step involves shifting left and XORing bits with themselves. Add subkey. Here, a portion of the key unique to this cycle is XORed with the cycle result. This operation delivers confusion and incorporates the key. Cryptography 2023 8 Cryptography 2023 9 Cryptography Cryptography 2023 10  Asymmetric Encryption Algorithms (Public Key Cryptography) RSA Algorithm: The Rivest-Shamir-Adelman RSA uses two keys (public and private, 256 bits as minimum usable length). Encryption in RSA is done by exponentiation, raising each plaintext block to a power; that power is the keye. Thus, RSA is markedly slower than DES and AES, but stronger in security. C= E(kPUB,P) >>> P = D(kPRIV, C) Or C = E(kPRIV,P) >>> P = D(kPUB, C) Cryptography Cryptography 2023 11 General Alice’s setup: Chooses two prime numbers p and q. Calculates the product n = pq. Calculates m = (p − 1)(q − 1). Chooses numbers e and d so that ed has a remainder of 1 when divided by m (ed % m = 1). Publishes her public key (n, e). General Bob encrypts a message M for Alice: Finds Alice’s public key (n, e). Finds the remainder C when Me is divided by n (C = Me % n). Sends ciphertext C to Alice. General Alice receives and decrypts ciphertext C: Uses her private key (n, d). Finds remainder R when Cd is divided by n (R = Cd % n). R matches the message M that Bob wanted to send to Alice! Working example Alice’s setup: p=11 and q=3. n=pq=11×3=33. m=(p−1)(q−1)=10×2=20. If e=3 and d=7, then ed=21 has a remainder of 1 when divided by m = 20. Publish (n, e) = (33, 3). Working example Bob encrypts message M = 14: (n, e) = (33, 3). When 143 = 2744 is divided by 33, the remainder is C = 5. Sends ciphertext C = 5 to Alice. Working example Alice decrypts ciphertext C = 5: (n, d) = (33, 7). When 57 = 78125 is divided by 33, the remainder is R = 14. R = 14 = M, the original message from Bob! Working Example: 1. Select primes p=11, q=3. 2. n = pq = 11*3 = 33 3. φ(n) = (p-1)(q-1)= 1 0 *2 = 20 4. Choose e=3 such that gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1), and gcd(e, q-1) = gcd(3, 2) = 1 5. Compute d such that ed mod φ = 1 i.e. compute d = 1 e−1 mod φ = 3−1 mod20 Check: ed % φ =1 where d< φ , 3*d % 20 =1 We can use 3*7 % 20 =1 , S o d = 7. Hence, Public key = (n, e) = (33, 3) and Private key = (n, d) = (33, 7). Now we want to encrypt the message m = 7,then: C= me mod n = 73 mod 33 = 343 mod 33 = 13. Hence the ciphertext c = 13. To check decryption we compute, P= C d mod n = 137 mod 33 = 7. Cryptography Cryptography 2023 12  Example Bob chooses 7 and 11 as p and q and calculates n = 7 * 11 = 77. The value of  = (7 − 1)*(11 − 1) or 60. Now he chooses two keys, e and d. If he chooses e to be 13, then d is 37. (Compute d such that ed mod φ = 1) ed = (? * φ ) +1 Now imagine Alice sends the plaintext 5 to Bob. She uses the public key 13 to encrypt 5. Cryptography 13 Cryptography Cryptography 2023 14  Key Exchange Protocols Suppose you need to send a protected message to someone you do not know and who does not know you. For instance, you may want to send your income tax return to the government. You want the information to be protected, but you do not necessarily know the person who is receiving the information. Public key cryptography can help. Public Key Cryptography can be used to exchange Secret Keys. Cryptography Cryptography 2023 15 - Simple Key Exchange Protocol - Bus what is the problem with this protocol? Cryptography Cryptography 2023 16 A Man in the Middle Cryptography Cryptography 2023 17 Key Exchange solution (1) Amy should send to Bill E(kPUB−B , E(kPRIV −A , K)) This confirms confidentiality and authenticity. Thus, as we have seen, asymmetric cryptographic functions are a powerful means for exchanging cryptographic keys between people who have no prior relationship. Cryptography Cryptography 2023 18 Diffie-Hellman Key Exchange (Solution 2) Cryptography Cryptography 2023 19 Diffie-Hellman Key Exchange (Solution 2)I Alice and Bob agree, publicly, on a prime number P, and a base number N. Eve will know these two numbers, and it won’t matter! Alice chooses a number A, which we’ll call her ”secret exponent.” She keeps A secret from everyone, including Bob. Bob, likewise, chooses his ”secret exponent” B, which he keeps secret from everyone, including Alice. Then, Alice computes the number J = N A (mod P) and sends J to Bob. Similarly, Bob computes the number K = N B (mod P) and sends K to Alice. Note that Eve now has both J and K in her possession. Cryptography Cryptography 2023 20 Diffie-Hellman Key Exchange (Solution 2)II The final mathematical trick is that Alice now takes K, the number she got from Bob, and computes K A(mod P). Bob does the same step in his own way, computing J B (mod P). The number they get is the same! Why is this so? Since K = N B (modP) Alice Computes K A (mod P) = (N B ) A (mod P) = NBA (mod P) Bob used J = NA (mod P) Bob computes JB (mod P) = (N A ) B (mod P) = NAB (mod P). Cryptography Cryptography 2023 21  Example Let us give a trivial example to make the procedure clear. Our example uses small numbers, but note that in a real situation, the numbers are very large. Assume N = 7 and p = 23. The steps are as follows: 1. Alice chooses A = 3 private key and calculate K = 73 mod 23 =21. 2. Bob chooses B = 6 private key and calculates J = 76 mod 23 = 4. 3. Alice sends the number 21 to Bob. 4. Bob sends the number 4 to Alice. 5. Alice calculates the symmetric key 43 mod 23 = 18. 6.Bob calculates the symmetric key 216 mod 23 = 18. 7.The value of the Key is the same for both Alice and Bob; NAB mod p = 718 mod 23 =18. Cryptography 22  Error Detecting Codes The basic purpose of Error Detecting Codes is to demonstrate that a block of data has been modified. Error detecting codes come under many names, such as Parity, hash codes, message digests, checksums, integrity checks, error detection and correction codes, and redundancy tests. Detection and correction codes are procedures or functions applied to a block ofdata. Cryptography 2023 23 Cryptography 2023 24  Hash Codes I Cryptography can be used to seal a file. One technique for providing the seal is to compute a function, sometimes called a hash or checksum or message digest of the file. Hashing is the process of transforming any given data into a value using a hashing function. Cryptography 2023 25  Hash Codes II A cryptographic checksum is a cryptographic function that uses a cryptographic key that is presumably known only to the originator and the proper recipient of the data. Cryptography 2023 26 Cryptography 2023 27  Hash Codes III  Secure Hash Standard or Algorithm (SHS or SHA), actually a collection of algorithms, for computing checksums.  The most widely used cryptographic hash functions are MD4, MD5 (MD stands for Message Digest), and SHA or SHS (Secure Hash Algorithm or Standard). Cryptography 2023 28  Message Digest Examples Hash functions provide protection to password storage. Instead of storing password ) P) in clear, mostly all logon processes store the hash values of passwords in the file. The Password file consists of a table of pairs which are in the form (user id, h(P)). Cryptography 2023 29 Cryptography 2023 30  Digital Signatures- All the Pieces In the physical world, it is common to use handwritten signatures on handwritten or typed messages to bind signatory to the message. Similarly, a digital signature is a technique that binds a person/entity to thedigital data. It meets non-repudiation feature. Cryptography 2023 31  Digital Signatures- All the Pieces I Each person adopting this scheme has a public-private keypair. Signer feeds data to the hash function and generates hash of data. Hash value and signature key (sender private-key) are then fed to the signature algorithm which produces the digital signature on given hash. Signature is appended to the data and then both are sent to theverifier. Cryptography 2023 32 Digital Signatures- All the Pieces II Verifier also runs same hash function on received data to generate hash value. the hash value is compared to with original data. Based on the comparison result, verifier decides whether the digital signature is valid. Since digital signature is created by private key of signer and no one else can have this key; the signer cannot repudiate signing the data in future. Let us assume RSA is used as the signing algorithm. Cryptography 2023 33 The receiver after receiving the encrypted data and signature on it, first verifies the signature using senders public key. After ensuring the validity of the signature, he then retrieves the data through decryption using his private key. Cryptography 2023 34  Certificates I Digital certificates, similar to identification cards, are unique for each person, and used to certify the online identities of individuals, organizations, and computers. A certificate is a trustable Identities and Public Keys signed by a certificate authority (CA). Certificates are issued and certified by certificate authorities (CAs( that supports industry standard X.509. Cryptography 2023 35  Certificates II  A certificate contains information such as: The certificate’s owner (called the subject) as an entity on the network. The owner’s public key. ACertificateAuthority digital signature.  A certificate Authority (CA) uses its private key to digitally sign each certificate it issues.  To create the digital signature, the CA generates a message digest from the certificate, signs the digest with its private key, and includes the digital signature as part of the certificate. Anyone can use the message digest function and the CA’s public key to verify the certificate’sintegrity. Cryptography 2023 36 Cryptography 2023 37 Cryptography 2023 38 Cryptography 2023 39