MCA644 CU-MCA-SEM-II-Network Security & Cryptography-converted-converted

Figure 5.1The Caesar Cipher A transposition cipher consists of breaking the original plaintext into separate blocks first. A deterministic procedure is then applied to shuffle characters across different blocks. For example, a transposition can split the secret message \"PHONE HOME\" into the two separate blocks \"PHONE\" and \" HOME\". Then, characters are cyclically shuffled across the two blocks to result in the ciphertext of \"POMHE HOEN\". Another example of a simple transposition cipher consists of writing the plaintext along a two-dimensional matrix of fixed rows and columns and then simply transposing the matrix, as shown in Figure Figure 5.2 Transposition Matrix Generally, transposition ciphers are easy to break. However, composing them by setting the result of one transposition as the input of another one greatly enhances the ciphering against attacks. With the age of computers, early modern cryptography carried on these same concepts, using the various elementary transformations that we have listed. The primary difference is that 100 CU IDOL SELF LEARNING MATERIAL (SLM)

these transformations now apply at the bit level of the binary representation of data instead of characters only. 5.3 BLOCK ENCRYPTION Block cipher is an encryption and decryption method which operates on the blocks of plain text, instead of operating on each bit of plain text separately. Each block is of equal size and has fixed no of bits. The generated ciphertext has blocks equal to the number of blocks in plaintext and also has the same number of bits in each block as of plain text. Block cipher uses the same key for encryption and decryption. Block cipher is an encryption method which divides the plain text into blocks of fixed size. Each block has an equal number of bits. At a time, block cipher operates only on one block of plain text and applies key on it to produce the corresponding block of ciphertext. While decryption also only one block of ciphertext is operated to produce its corresponding plain text. Data Encryption Standard (DES) is the best example of it. DES divides the plain text into the number of blocks, each of 64-bit. DES operates on one block of plain text at a time. Key of 56-bit is applied to each block of plain text to produce its corresponding ciphertext of 64-bit. During decryption also only one block of ciphertext is operated at a time to produce its corresponding block plain text. In DES the decryption algorithm is the same as the encryption one. On an all the block cipher operates on a block of bits at a time instead of one bit a time. Operating bit by bit is a very time-consuming process and as block cipher is a computer- based cryptographic algorithm it needs to be fast. That’s why operating one block of bits at a time makes it faster as compared to a stream cipher. 101 CU IDOL SELF LEARNING MATERIAL (SLM)

But there was a limitation in the block cipher as it would generate the same ciphertext for the repeating text pattern in plain text. However, this limitation was resolved by implementing chaining in the block cipher. 5.3.1 Block Cipher Principles A block cipher is designed by considering its three critical aspects which are listed as below: 1. Number of Rounds 2. Design of Function F 3. Key Schedule Algorithm 1. Number of Rounds The number of rounds judges the strength of the block cipher algorithm. It is considered that more is the number of rounds, difficult is for cryptanalysis to break the algorithm. It is considered that even if the function F is relatively weak, the number of rounds would make the algorithm tough to break. 2. Design of Function F The function F of the block cipher must be designed such that it must be impossible for any cryptanalysis to unscramble the substitution. The criterion that strengthens the function F is it non-linearity. More the function F is nonlinear, more it would be difficult to crack it. Well, while designing the function F it should be confirmed that it has a good avalanche property which states that a change in one-bit of input must reflect the change in many bits of output. The Function F should be designed such that it possesses a bit independence criterion which states that the output bits must change independently if there is any change in the input bit. 3. Key Schedule Algorithm 102 CU IDOL SELF LEARNING MATERIAL (SLM)

It is suggested that the key schedule should confirm the strict avalanche effect and bit independence criterion. 5.3.2 Block Cipher Modes of Operation There are five important block cipher modes of operation defined by NIST. These five modes of operation enhance the algorithm so that it can be adapted by a wide range of applications which uses block cipher for encryption. 1. Electronic Code Book Mode 2. Cipher Block Chaining Mode 3. Cipher Feedback Mode 4. Output Feedback Mode 5. Counter Mode 1. Electronic Feedback Mode This is considered to be the easiest block cipher mode of operation. In electronic codebook mode (ECB) the plain text is divided into the blocks, each of 64-bit. Each block is encrypted one at a time to produce the cipher block. The same key is used to encrypt each block. Figure 5.3 Encryption 103 CU IDOL SELF LEARNING MATERIAL (SLM)

When the receiver receives the message i.e., ciphertext. This ciphertext is again divided into blocks, each of 64-bit and each block is decrypted independently one at a time to obtain the corresponding plain text block. Here also the same key is used to decrypt each block which was used to encrypt each block. Figure 5.4 Decryption As the same key used to encrypt each block of plain text there arises an issue that for a repeating plain text block it would generate the same cipher and will ease the cryptanalysis to crack the algorithm. Hence, ECB is considered for encrypting the small messages which have a rare possibility of repeating text. 2. Cipher Block Chaining Mode To overcome the limitation of ECB i.e. the repeating block in plain text produces the same ciphertext, a new technique was required which is Cipher Block Chaining (CBC) Mode. CBC confirms that even if the plain text has repeating blocks its encryption won’t produce same cipher block. To achieve totally different cipher blocks for two same plain text blocks chaining has been added to the block cipher. For this, the result obtained from the encryption of the first plain text block is fed to the encryption of the next plaintext box. 104 CU IDOL SELF LEARNING MATERIAL (SLM)

In this way, each ciphertext block obtained is dependent on its corresponding current plain text block input and all the previous plain text blocks. But during the encryption of first plain text block, no previous plain text block is available so a random block of text is generated called Initialization vector. Now let’s discuss the encryption steps of CBC Step 1: The initialization vector and first plain text block are XORed and the result of XOR is then encrypted using the key to obtain the first ciphertext block. Step 2: The first ciphertext block is fed to the encryption of the second plain text block. For the encryption of second plain text block, first ciphertext block and second plain text block is XORed and the result of XOR is encrypted using the same key in step 1 to obtain the second ciphertext block. Similarly, the result of encryption of second plain text block i.e. the second ciphertext block is fed to the encryption of third plain text block to obtain third ciphertext block. And the process continues to obtain all the ciphertext blocks. You can see the steps of CBC in the figure below: 105 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.5 Encryption Decryption steps of CBC: Step 1: The first ciphertext block is decrypted using the same key that was used for encrypting all plain text blocks. The result of decryption is then XORed with the initialization vector (IV) to obtain the first plain text block. Step 2: The second ciphertext block is decrypted and the result of decryption is XORed with the first ciphertext block to obtain the second plain text block. And the process continues till all plain text blocks are retrieved. 106 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.6 Decryption There was a limitation in CBC that if we have two identical messages and if we use the same IV for both the identical message it would generate the same ciphertext block. 3. Cipher Feedback Mode All applications may not be designed to operate on the blocks of data, some may be character or bit-oriented. Cipher feedback mode is used to operate on smaller units than blocks. Let us discuss the encryption steps in cipher feedback mode: Step 1: Here also we use initialization vector, IV is kept in the shift register and it is encrypted using the key. Step 2: The left most s bits of the encrypted IV is then XORed with the first fragment of the plain text of s bits. It produces the first ciphertext C1 of s bits. Step 3: Now the shift register containing initialization vector performs left shift by s bits and s bits C1 replaces the rightmost s bits of the initialization vector. Then again, the encryption is performed on IV and the leftmost s bit of encrypted IV is XORed with the second fragment of plain text to obtain s bit ciphertext C2. 107 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.7 Encryption The process continues to obtain all ciphertext fragments. Decryption Steps: Step 1: The initialization vector is placed in the shift register. It is encrypted using the same key. Keep a note that even in the decryption process the encryption algorithm is implemented instead of the decryption algorithm. Then from the encrypted IV s bits are XORed with the s bits ciphertext C1 to retrieve s bits plain text P1. Step 2: The IV in the shift register is left-shifted by s bits and the s bits C1 replaces the rightmost s bits of IV. The process continues until all plain text fragments are retrieved. 108 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.8 Decryption It has a limitation that if there occur a bit error in any ciphertext Ci it would affect all the subsequent ciphertext units as Ci is fed to the encryption of next Pi+1 to obtain Ci+1. In this way, bit error would propagate. 4. Output Feedback Mode The output feedback (OFB) mode is almost similar to the CFB. The difference between CFB and OFB is that unlike CFB, in OFB the encrypted IV is fed to the encryption of next plain text block. The other difference is that CFB operates on a stream of bits whereas OFB operates on the block of bits. Steps for encryption: Step 1: The initialization vector is encrypted using the key. Step 2: The encrypted IV is then XORed with the plain text block to obtain the ciphertext block. 109 CU IDOL SELF LEARNING MATERIAL (SLM)

The encrypted IV is fed to the encryption of next plain text block as you can see in the image below. Figure 5.9 Encryption Steps for decryption: Step 1: The initialization vector is encrypted using the same key used for encrypting all plain text blocks. Note: In the decryption process also the encryption function is implemented. Step2: The encrypted IV is then XORed with the ciphertext block to retrieve the plain text block. The encrypted IV is also fed to the decryption process of the next ciphertext block. The process continues until all the plain text blocks are retrieved. 110 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.10 Decryption The advantage of OFB is that it protects the propagation of bit error means the if there occurs a bit error in C1 it will only affect the retrieval of P1 and won’t affect the retrieval of subsequent plain text blocks. 5. Counter Mode It is similar to OFB but there is no feedback mechanism in counter mode. Nothing is being fed from the previous step to the next step instead it uses a sequence of number which is termed as a counter which is input to the encryption function along with the key. After a plain text block is encrypted the counter value increments by 1. Steps of encryption: Step1: The counter value is encrypted using a key. Step 2: The encrypted counter value is XORed with the plain text block to obtain a ciphertext block. To encrypt the next subsequent plain text block the counter value is incremented by 1 and step 1 and 2 are repeated to obtain the corresponding ciphertext. 111 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.11 Encryption The process continues until all plain text block is encrypted. Steps for decryption: Step1: The counter value is encrypted using a key. Note: Encryption function is used in the decryption process. The same counter values are used for decryption as used while encryption. Step 2: The encrypted counter value is XORed with the ciphertext block to obtain a plain text block. Figure 5.12 Decryption 112 CU IDOL SELF LEARNING MATERIAL (SLM)

To decrypt the next subsequent ciphertext block the counter value is incremented by 1 and step 1 and 2 are repeated to obtain corresponding plain text. The process continues until all ciphertext block is decrypted. So, this is all about Block cipher, its designing principles and its mode of operation’ 5.4 DES rounds The Data Encryption Standard (DES) is a symmetric-key block cipher published by the National Institute of Standards and Technology (NIST). DES is an implementation of a Feistel Cipher. It uses 16 round Feistel structure. The block size is 64-bit. Though, key length is 64-bit, DES has an effective key length of 56 bits, since 8 of the 64 bits of the key are not used by the encryption algorithm (function as check bits only). General Structure of DES is depicted in the following illustration − 113 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.13 DES is depicted Since DES is based on the Feistel Cipher, all that is required to specify DES is − • Round function • Key schedule • Any additional processing − Initial and final permutation 5.4.1 Initial and Final Permutation The initial and final permutations are straight Permutation boxes (P-boxes) that are inverses of each other. They have no cryptography significance in DES. The initial and final permutations are shown as follows − Figure 5.14 Initial and Final Permutation 5.4.2 Round Function The heart of this cipher is the DES function, f. The DES function applies a 48-bit key to the rightmost 32 bits to produce a 32-bit output. 114 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.15 Round Function • Expansion Permutation Box − Since right input is 32-bit and round key is a 48-bit, we first need to expand right input to 48 bits. Permutation logic is graphically depicted in the following illustration − Figure 5.16 • Expansion Permutation Box • The graphically depicted permutation logic is generally described as table in DES specification illustrated as shown − 115 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.17 • XOR (Whitener). − After the expansion permutation, DES does XOR operation on the expanded right section and the round key. The round key is used only in this operation. • Substitution Boxes. − The S-boxes carry out the real mixing (confusion). DES uses 8 S-boxes, each with a 6-bit input and a 4-bit output. Refer the following illustration − Figure 5.18 • Substitution Boxes • The S-box rule is illustrated below − 116 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.19 S-box rule • There are a total of eight S-box tables. The output of all eight s-boxes is then combined in to 32 bit section. • Straight Permutation − The 32 bit output of S-boxes is then subjected to the straight permutation with rule shown in the following illustration: Figure 5.20 • Straight Permutation 5.4.3 Key Generation The round-key generator creates sixteen 48-bit keys out of a 56-bit cipher key. The process of key generation is depicted in the following illustration − 117 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.21 Key Generation The logic for Parity drop, shifting, and Compression P-box is given in the DES description. 5.4.5 DES Analysis The DES satisfies both the desired properties of block cipher. These two properties make cipher very strong. • Avalanche effect − A small change in plaintext results in the very great change in the ciphertext. • Completeness − Each bit of ciphertext depends on many bits of plaintext. During the last few years, cryptanalysis have found some weaknesses in DES when key selected are weak keys. These keys shall be avoided. 118 CU IDOL SELF LEARNING MATERIAL (SLM)

DES has proved to be a very well designed block cipher. There have been no significant cryptanalytic attacks on DES other than exhaustive key search. 5.5 S BOXES In cryptography, a S-Box (Substitution-box) is a basic component of symmetric-key algorithms. In block ciphers, the S-Boxes are used to make the relation between the key and the ciphertext (coded text) difficult to understand–Shannon's property of confusion. The S- Boxes are carefully chosen to resist cryptanalysis (decoding). In general, an S-Box takes some number of inputs bits, m, and transforms them into some number of output bits, n: an man S-Box can be implemented as a lookup table with 2m words of n bits each. Fixed tables are normally used, as in the Data Encryption Standard (DES), but in some ciphers the tables are generated dynamically from the key; e.g. the Blowfish and the Twofish encryption algorithms. Bruce Schneier describes IDEA's modular multiplication step as a key-dependent S-Box. One good example is this 6×4-bit S-Box from DES (S5): Middle (inner) 4 bits of input 0 S5 0 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 01 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 Oute 0 110 010 000 011 101 101 011 100 010 001 111 110 000 111 100 00 r bits 10 0 1 1 0 1 0 0 1 1 1 1 0 0 1 0 119 CU IDOL SELF LEARNING MATERIAL (SLM)

1 1 101 001 110 010 011 110 000 010 000 111 101 001 100 100 011 01 11 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 1 001 000 101 101 110 011 100 111 100 110 010 011 001 000 111 10 00 1 1 0 1 1 0 1 1 0 1 0 1 0 0 0 1 0 100 110 011 000 111 001 110 011 111 000 100 101 010 010 001 11 10 0 1 1 0 0 1 0 1 0 1 0 0 1 1 1 Given a 6-bit input, the 4-bit output is found by selecting the row using the outer two bits, and the column using the inner four bits. For example, an input \"011011\" has outer bits \"01\" and inner bits \"1101\"; the corresponding output would be \"1001\". The 8 S-Boxes of DES were the subject of intensive studies for many years cause of a concern that a method of bypassing the DES cipher to obtaining access to the plaintext– a vulnerability (susceptibility) known only to its designers–might have been planted (inserted) in the cipher. In 1994, the S-Box design criteria were finally published by its designers after the public rediscovery of differential cryptanalysis, showing that they had been carefully tuned the design to increase resistance against differential cryptanalysis attacks. Other research had already indicated that even a very small modification to one of the 8 S-Box used by the DES could weaken it very much. 120 CU IDOL SELF LEARNING MATERIAL (SLM)

The design of good S-Boxes was the subject of a great amount of research; now much more is understood about their use in block ciphers than when the DES S-Boxes were released. 5.6 SUMMARY Computer cryptography started with the invention of the first computer nicknamed 'Colossus'. The cipher machines that were used before, during the Second World War, were in many ways the predecessors to today's computer devices. The simple language codes used in those early devices were replaced by the binary computer language of 0s and 1s to give rise to modern computer cryptography. In today's time, cyber cryptographic algorithms are used to transfer electronic data over the internet so that no third-party is able to read the data. Cryptography historically dealt with the construction and analysis of protocols that would prevent any third parties from reading a private communication between two parties. In the digital age, cryptography has evolved to address the encryption and decryption of private communications through the internet and computer systems, a branch of cyber and network security, in a manner far more complex than anything the world of cryptography had seen before the arrival of computers. The aim of cyber security is to attempt to create encryption systems that perform perfectly on all four of the above-mentioned parameters. This can be almost impossible to fully accomplish, since the strength of the encryption depends not only on computer programs but also on human behaviour. The best security systems in the world can still be defeated by an easily-guessed password, or the user not logging out after a session or discussing security information with outsiders. Today, cryptography uses some of the finest computer and mathematical minds on the planet. Every industry on the planet, from war to healthcare makes use of encryption to protect sensitive information that is being transmitted across the internet 121 CU IDOL SELF LEARNING MATERIAL (SLM)

5.7 KEY WORDS/ABBREVIATIONS • Plaintext- Text that is not computationally tagged, specially formatted, or written in code. • Encryption-It is the process of encoding a message or information in such a way that only authorized parties can access it. Encryption does not itself prevent interference, but denies the intelligible content to a would-be interceptor. • Cyphertext-It is the encrypted text. Plaintext is what you have before encryption, and ciphertext is the encrypted result. The term cipher is sometimes used as a synonym for ciphertext, but it more properly means the method of encryption rather than the result. • Decryption-Decryption is the process of taking encoded or encrypted text or other data and converting it back into text that you or the computer can read and understand. • Secure Sockets Layer (SSL)-A protocol that uses cryptography to enable secure communication over the Internet. SSL is widely supported by leading web browsers and web servers. • Security Console- An administrative user interface through which the user performs most of the day-to-day administrative activities. • Security domain-A container that defines an area of administrative management responsibility, typically in terms of business units, departments, partners, and so on. 5.8 LEARNING ACTIVITY 1. Define encryption and decryption process Output Feedback Mode in Key schedule algorithm. 122 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Implement substitutions and transpositions techniques in network to append security 5.9 UNIT END QUESTIONS (MCQ AND DESCRIPTIVE) A. Descriptive Questions 1. Draw a structure of Secret Key Cryptography 2. What is Block Encryption? 3. What is function of Data Encryption Standard Rounds? 4. Explain Substitution-Boxes. 5. Explain Symmetric Cryptography. B. Multiple Choice Questions 1. When plain text is converted to unreadable format, it is termed as a. rotten text b. raw text c. cipher-text d. ciphen-text 2. Cryptographic algorithms are based on mathematical algorithms where these algorithms use for a secure transformation of data. a. secret key 123 b. external programs c. add-ons CU IDOL SELF LEARNING MATERIAL (SLM)

d. secondary key 3. Data Encryption Standard is an example of a cryptosystem. a. Conventional b. public key c. hash key d. asymmetric-key 4. In asymmetric key cryptography, the private key is kept by a. sender b. receiver c. sender and receiver d. all the connected devices to the network 5. In which way does the Combined Encryption combine symmetric and asymmetric encryption? a. First, the message is encrypted with symmetric encryption and afterwards it is encrypted asymmetrically together with the key. b. The secret key is symmetrically transmitted, the message itself asymmetrically. c. First, the message is encrypted with asymmetric encryption and afterwards it is encrypted symmetrically together with the key. d. The secret key is asymmetrically transmitted, the message itself symmetrically. Answer 2.a 3.a 4.b 5.d 1.c CU IDOL SELF LEARNING MATERIAL (SLM) 124

5.10 REFERENCES • Becket, B (1988). Introduction to Cryptology. Blackwell Scientific Publications. ISBN 978-0-632-01836-9. OCLC 16832704. Excellent coverage of many classical ciphers and cryptography concepts and of the \"modern\" DES and RSA systems. • Cryptography and Mathematics by Bernhard Eslinger, 200 pages, part of the free open- source package CrypTool, PDF download at the Way back Machine (archived 22 July 2011). CrypTool is the most widespread e-learning program about cryptography and cryptanalysis, open source. • W. Stallings, \"Cryptography and Network Security\", Pearson Education. • Douglas Stinson, \"Cryptography Theory and Practice\", 2nd Edition, Chapman & Hall/CRC. • . A. Forouzan, \"Cryptography & Network Security\", Tata Mc Graw Hill. • In Code: A Mathematical Journey by Sarah Flannery (with David Flannery). Popular account of Sarah's award-winning project on public-key cryptography, co-written with her father. • Hirsch, Frederick J. \"SSL/TLS Strong Encryption: An Introduction\". Apache HTTP Server. Retrieved 17 April 2013. The first two sections contain a very good introduction to public-key cryptography. • Ferguson, Niels; Schneier, Bruce (2003). Practical Cryptography. Wiley. ISBN 0-471- 22357-3. • Katz, Jon; Lindell, Y. (2007). Introduction to Modern Cryptography. CRC Press. ISBN 978-1-58488-551-1. 125 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 6: PUBLIC KEY CRYPTOGRAPHY 1 Structure 6.0 Learning Objectives 6.1 Introduction 6.2 RSA: Generate keys 6.3 Encryption and Decryption 6.4 Summary 6.5 Key Words/Abbreviations 6.6 Learning Activity 6.7 Unit End Questions (MCQ and Descriptive) 6.8 References 6.0 LEARNING OBJECTIVES At the end of the unit learner will able to understand and have knowledge of following aspects of Public Key Cryptography: • Understanding of Public Key Cryptography • Knowledge of Generation of keys in RSA • Process of Encryption and Decryption 6.1 INTRODUCTION Public-key cryptography, or asymmetric cryptography, is a cryptographic system that uses pairs of keys: public keys, which may be disseminated widely, and private keys, which are known only to the owner. The generation of such keys depends on cryptographic algorithms based on mathematical problems to produce one-way functions. Effective security only 126 CU IDOL SELF LEARNING MATERIAL (SLM)

requires keeping the private key private; the public key can be openly distributed without compromising security. In such a system, any person can encrypt a message using the receiver's public key, but that encrypted message can only be decrypted with the receiver's private key. Robust authentication is also possible. A sender can combine a message with a private key to create a short digital signature on the message. Anyone with the sender's corresponding public key can combine the same message and the supposed digital signature associated with it to verify whether the signature was valid, i.e. made by the owner of the corresponding private key. Before the mid-1970s, all cipher systems used symmetric key algorithms, in which the same cryptographic key is used with the underlying algorithm by both the sender and the recipient, who must both keep it secret. Of necessity, the key in every such system had to be exchanged between the communicating parties in some secure way prior to any use of the system – a secure channel. This requirement is never trivial and very rapidly becomes unmanageable as the number of participants increases, or when secure channels aren't available for key exchange, or when, (as is sensible cryptographic practice), keys are frequently changed. In particular, if messages are meant to be secure from other users, a separate key is required for each possible pair of users. By contrast, in a public key system, the public keys can be disseminated widely and openly, and only the private key needs to be kept secure by its owner. Two of the best-known uses of public key cryptography are: Public key encryption, in which a message is encrypted with a recipient's public key. The message cannot be decrypted by anyone who does not possess the matching private key, who is thus presumed to be the owner of that key and the person associated with the public key. This is used in an attempt to ensure confidentiality. 127 CU IDOL SELF LEARNING MATERIAL (SLM)

Digital signatures, in which a message is signed with the sender's private key and can be verified by anyone who has access to the sender's public key. This verification proves that the sender had access to the private key, and therefore is likely to be the person associated with the public key. This also ensures that the message has not been tampered with, as a signature is mathematically bound to the message it originally was made with, and verification will fail for practically any other message, no matter how similar to the original message. One important issue is confidence/proof that a particular public key is authentic, i.e. that it is correct and belongs to the person or entity claimed, and has not been tampered with or replaced by a malicious third party. There are several possible approaches, including: A public key infrastructure (PKI), in which one or more third parties – known as certificate authorities – certify ownership of key pairs. TLS relies upon this. A \"web of trust\" which decentralizes authentication by using individual endorsements of the link between user and public key. PGP uses this approach, as well as lookup in the domain name system (DNS). The DKIM system for digitally signing emails also uses this approach. When the two parties communicate to each other to transfer the intelligible or sensible message, referred to as plaintext, is converted into apparently random nonsense for security purpose referred to as ciphertext. The process of changing the plaintext into the ciphertext is referred to as encryption. The encryption process consists of an algorithm and a key. The key is a value independent of the plaintext. Once the ciphertext is produced, it may be transmitted. The security of conventional encryption depends on the major two factors: 1. The Encryption algorithm 2. Secrecy of the key The algorithm will produce a different output depending on the specific key being used at the time. Changing the key changes the output of the algorithm. Once the ciphertext is produced, 128 CU IDOL SELF LEARNING MATERIAL (SLM)

it may be transmitted. Upon reception, the ciphertext can be transformed back to the original plaintext by using a decryption algorithm and the same key that was used for encryption. Decryption: The process of changing the ciphertext to the plaintext that process is known as decryption. Asymmetric is a form of Cryptosystem in which encryption and decryption are performed using different keys-Public key (known to everyone) and Private key (Secret key). This is known as Public Key Encryption. Characteristics of Public Encryption key: • Public key Encryption is important because it is infeasible to determine the decryption key given only the knowledge of the cryptographic algorithm and encryption key. • Either of the two keys (Public and Private key) can be used for encryption with another key used for decryption. • Due to Public key cryptosystem, public keys can be freely shared, allowing users an easy and convenient method for encrypting content and verifying digital signatures, and private keys can be kept secret, ensuring only the owners of the private keys can decrypt content and create digital signatures. • The most widely used public-key cryptosystem is RSA (Rivest–Shamir–Adleman). The difficulty of finding the prime factors of a composite number is the backbone of RSA. Example: Public keys of every user are present in the Public key Register. If B wants to send a confidential message to C, then B encrypt the message using C Public key. When C receives the message from B then C can decrypt it using its own Private key. No other recipient other than C can decrypt the message because only C know C’s private key. 129 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 6.1 Public Encryption key Components of Public Key Encryption: • PlainText: This is the message which is readable or understandable. This message is given to the Encryption algorithm as an input. • CipherText: The cipher text is produced as an output of Encryption algorithm. We cannot simply understand this message. • EncryptionAlgorithm: The encryption algorithm is used to convert plain text into cipher text. • DecryptionAlgorithm: It accepts the cipher text as input and the matching key (Private Key or Public key) and produces the original plain text 130 CU IDOL SELF LEARNING MATERIAL (SLM)

• Public and Private Key: One key either Private key (Secret key) or Public Key (known to everyone) is used for encryption and other is used for decryption Weakness of the Public Key Encryption: • Public key Encryption is vulnerable to Brute-force attack. • This algorithm also fails when the user lost his private key, then the Public key Encryption becomes the most vulnerable algorithm. • Public Key Encryption also is weak towards man in the middle attack. In this attack a third party can disrupt the public key communication and then modify the public keys. • If user private key used for certificate creation higher in the PKI (Public Key Infrastructure) server hierarchy is compromised, or accidentally disclosed, then a “man-in-the-middle attack” is also possible, making any subordinate certificate wholly insecure. This is also the weakness of Public key Encryption. Applications: • Confidentiality can be achieved using Public Key Encryption. In this the Plain text is encrypted using receiver public key. This will ensures that no one other than receiver private key can decrypt the cipher text. • Digital signature is for sender’s authentication purpose. In this sender encrypt the plain text using his own private key. This step will make sure the authentication of the sender because receiver can decrypt the cipher text using senders pubic key only. • This algorithm can use in both Key-management and securely transmission of data. 6.2 RSA: GENERATE KEYS RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission. The acronym RSA is the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who publicly described the algorithm in 131 CU IDOL SELF LEARNING MATERIAL (SLM)

1977. In such a cryptosystem, the encryption key is public and distinct from the decryption key which is kept secret (private). In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the \"factoring problem\". Clifford Cocks, an English mathematician working for the British intelligence agency Government Communications Headquarters (GCHQ), had developed an equivalent system in 1973, which was not declassified until 1997. A user of RSA creates and then publishes a public key based on two large prime numbers, along with an auxiliary value. The prime numbers must be kept secret. Anyone can use the public key to encrypt a message, but only someone with knowledge of the prime numbers can decode the message. Breaking RSA encryption is known as the RSA problem. Whether it is as difficult as the factoring problem is an open question. There are no published methods to defeat the system if a large enough key is used. RSA is a relatively slow algorithm, and because of this, it is less commonly used to directly encrypt user data. More often, RSA passes encrypted shared keys for symmetric key cryptography which in turn can perform bulk encryption-decryption operations at much higher speed. The idea of an asymmetric public-private key cryptosystem is attributed to Whitfield Diffie and Martin Hellman, who published this concept in 1976. They also introduced digital signatures and attempted to apply number theory. Their formulation used a shared-secret-key created from exponentiation of some number, modulo a prime number. However, they left open the problem of realizing a one-way function, possibly because the difficulty of factoring was not well-studied at the time. Ron Rivest, Adi Shamir, and Leonard Adleman at the Massachusetts Institute of Technology, made several attempts over the course of a year to create a one-way function that was hard to 132 CU IDOL SELF LEARNING MATERIAL (SLM)

invert. Rivest and Shamir, as computer scientists, proposed many potential functions, while Adleman, as a mathematician, was responsible for finding their weaknesses. They tried many approaches including \"knapsack-based\" and \"permutation polynomials\". For a time, they thought what they wanted to achieve was impossible due to contradictory requirements. In April 1977, they spent Passover at the house of a student and drank a good deal of Manischewitz wine before returning to their homes at around midnight. Rivest, unable to sleep, lay on the couch with a math textbook and started thinking about their one-way function. He spent the rest of the night formalizing his idea, and he had much of the paper ready by daybreak. The algorithm is now known as RSA – the initials of their surnames in same order as their paper. Clifford Cocks, an English mathematician working for the British intelligence agency Government Communications Headquarters (GCHQ), described an equivalent system in an internal document in 1973.However, given the relatively expensive computers needed to implement it at the time, it was considered to be mostly a curiosity and, as far as is publicly known, was never deployed. His discovery, however, was not revealed until 1997 due to its top-secret classification. Kid-RSA (KRSA) is a simplified public-key cipher published in 1997, designed for educational purposes. Some people feel that learning Kid-RSA gives insight into RSA and other public-key ciphers, analogous to simplified DES Operation The RSA algorithm involves four steps: key generation, key distribution, encryption and decryption. 133 CU IDOL SELF LEARNING MATERIAL (SLM)

A basic principle behind RSA is the observation that it is practical to find three very large positive integers e, d and n such that with modular exponentiation for all integers m (with 0 ≤ m < n): {\\displaystyle (m^{e})^{d}\\equiv m{\\pmod {n}}}{\\displaystyle (m^{e})^{d}\\equiv m{\\pmod {n}}} and that knowing e and n, or even m, it can be extremely difficult to find d. The triple bar (≡) here denotes modular congruence. In addition, for some operations it is convenient that the order of the two exponentiations can be changed and that this relation also implies: {\\displaystyle (m^{d})^{e}\\equiv m{\\pmod {n}}}{\\displaystyle (m^{d})^{e}\\equiv m{\\pmod {n}}} RSA involves a public key and a private key. The public key can be known by everyone, and it is used for encrypting messages. The intention is that messages encrypted with the public key can only be decrypted in a reasonable amount of time by using the private key. The public key is represented by the integers n and e; and, the private key, by the integer d (although n is also used during the decryption process. Thus, it might be considered to be a part of the private key, too). m represents the message Key generation 134 The keys for the RSA algorithm are generated in the following way: Choose two distinct prime numbers p and q. CU IDOL SELF LEARNING MATERIAL (SLM)

For security purposes, the integers p and q should be chosen at random, and should be similar in magnitude but differ in length by a few digits to make factoring harder. Prime integers can be efficiently found using a primality test. p and q are kept secret. Compute n = pq. n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length. n is released as part of the public key. Compute λ(n), where λ is Carmichael's totient function. Since n = pq, λ(n) = lcm(λ(p),λ(q)), and since p and q are prime, λ(p) = φ(p) = p − 1 and likewise λ(q) = q − 1. Hence λ(n) = lcm(p − 1, q − 1). λ(n) is kept secret. The lcm may be calculated through the Euclidean algorithm, since lcm(a,b) = |ab|/gcd(a,b). Choose an integer e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1; that is, e and λ(n) are coprime. e having a short bit-length and small Hamming weight results in more efficient encryption – the most commonly chosen value for e is 216 + 1 = 65,537. The smallest (and fastest) possible value for e is 3, but such a small value for e has been shown to be less secure in some settings. e is released as part of the public key. Determine d as d ≡ e−1 (mod λ(n)); that is, d is the modular multiplicative inverse of e modulo λ(n). This means: solve for d the equation d⋅e ≡ 1 (mod λ(n)); d can be computed efficiently by using the Extended Euclidean algorithm, since, thanks to e and λ(n) being coprime, said equation is a form of Bézout's identity, where d is one of the coefficients. 135 CU IDOL SELF LEARNING MATERIAL (SLM)

d is kept secret as the private key exponent. The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the private (or decryption) exponent d, which must be kept secret. p, q, and λ(n) must also be kept secret because they can be used to calculate d. In fact, they can all be discarded after d has been computed. In the original RSA paper, the Euler totient function φ(n) = (p − 1) (q − 1) is used instead of λ(n) for calculating the private exponent d. Since φ(n) is always divisible by λ(n) the algorithm works as well. That the Euler totient function can be used can also be seen as a consequence of the Lagrange's theorem applied to the multiplicative group of integers modulo pq. Thus, any d satisfying d⋅e ≡ 1 (mod φ(n)) also satisfies d⋅e ≡ 1 (mod λ(n)). However, computing d modulo φ(n) will sometimes yield a result that is larger than necessary (i.e. d > λ(n)). Most of the implementations of RSA will accept exponents generated using either method (if they use the private exponent d at all, rather than using the optimized decryption method based on the Chinese remainder theorem described below), but some standards like FIPS 186-4 may require that d < λ(n). Any \"oversized\" private exponents not meeting that criterion may always be reduced modulo λ(n) to obtain a smaller equivalent exponent. Since any common factors of (p − 1) and (q − 1) are present in the factorisation of n − 1 = pq − 1 = (p − 1)(q − 1) + (p − 1) + (q − 1),[16] it is recommended that (p − 1) and (q − 1) have only very small common factors, if any besides the necessary 2. Note: The authors of the original RSA paper carry out the key generation by choosing d and then computing e as the modular multiplicative inverse of d modulo φ(n), whereas most 136 CU IDOL SELF LEARNING MATERIAL (SLM)

current implementations of RSA, such as those following PKCS#1, do the reverse (choose e and compute d). Since the chosen key can be small whereas the computed key normally is not, the RSA paper's algorithm optimizes decryption compared to encryption, while the modern algorithm optimizes encryption instead. Key distribution Suppose that Bob wants to send information to Alice. If they decide to use RSA, Bob must know Alice's public key to encrypt the message and Alice must use her private key to decrypt the message. To enable Bob to send his encrypted messages, Alice transmits her public key (n, e) to Bob via a reliable, but not necessarily secret, route. Alice's private key (d) is never distributed. 6.3 ENCRYPTION AND DECRYPTION Encryption using RSA: To encrypt a plaintext M using an RSA public key we simply represent the plaintext as a number between 0 and N-1 and then compute the ciphertext C as: C = Me mod N. Decryption using RSA: To decrypt a ciphertext C using an RSA public key we simply compute the plaintext M as: M = Cd mod N. Note that both RSA encryption and RSA decryption involve a modular exponentiation and so we would be well advised to use the Repeated Squares Algorithm if we want to make these processes reasonably efficient. 137 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 6.2 RSA 138 RSA Encryption Suppose someone wants to encrypt the plaintext 19. We thus have to calculate: C ≡ 199 mod 1189. This is most efficiently calculated using the Repeated Squares Algorithm: Step 1: C ≡ 198+1 mod 1189 C ≡ (198) (191) mod 1189 Step 2: 191 ≡ 19 mod 1189 192 ≡ 192 = 361 mod 1189 194 = (192)2 ≡ (361)2 = 130321 ≡ 720 mod 1189 198 = (194)2 ≡ (720)2 = 518400 ≡ 1185 mod 1189 Step 3: CU IDOL SELF LEARNING MATERIAL (SLM)

C ≡ (198)(191) mod 1189 ≡ (1185)(19) mod 1189 ≡ 22515 mod 1189 ≡ 1113 mod 1189 So the ciphertext C is 1113. RSA Decryption Suppose we now receive this ciphertext C=1113. To decrypt it we have to calculate: M ≡ 1113249 mod 1189. This is most efficiently calculated using the Repeated Squares Algorithm: Step 1: M ≡ 1113249 mod 1189 M ≡ 1113128+64+32+16+8+1 mod 1189 M ≡ (1113128)(111364)(111332)(111316)(11138)(11131) mod 1189 Step 2: 139 11131 ≡ 1113 mod 1189 11132 ≡ 11132 = 1238769 ≡ 1020 mod 1189 11134 = (11132)2 ≡ (1020)2 = 1040400 ≡ 25 mod 1189 11138 = (11134)2 ≡ (25)2 = 625 mod 1189 111316 = (11138)2 ≡ (625)2 = 390625 ≡ 633 mod 1189 111332 = (111316)2 ≡ (633)2 = 400689 ≡ 1185 mod 1189 CU IDOL SELF LEARNING MATERIAL (SLM)

111364 = (111332)2 ≡ (1185)2 = 1404225 ≡ 16 mod 1189 1113128 = (111364)2 ≡ (16)2 = 256 mod 1189 Step 3: M ≡ (1113128)(111364)(111332)(111316)(11138)(11131) mod 1189 ≡ (256)(16)(1185)(633)(625)(1113) mod 1189 ≡ 2137259174400000 mod 1189 ≡ 19 mod 1189 So the plaintext M is 19. This agrees with what we originally encrypted. The decryption has been successful. Algorithm: Encryption using PKCS#1v1.5 INPUT: Recipient's RSA public key, (n, e), of length k = |n| bytes; data D (typically a session key) of length |D| bytes with |D|<=k-11. OUTPUT: Encrypted data block of length k bytes 1. Form the k-byte encoded message block, EB, 2. EB = 00 || 02 || PS || 00 || D where || denotes concatenation and PS is a string of k-|D|-3 non-zero randomly-generated bytes (i.e., at least eight random bytes). 3. Convert the byte string, EB, to an integer, m, most significant byte first, 4. m = StringToInteger(EB) 5. Encrypt with the RSA algorithm 6. c = m^e mod n 7. Convert the resulting ciphertext, cc, to a kk-byte output block, OB‡ 140 CU IDOL SELF LEARNING MATERIAL (SLM)

8. OB = IntegerToString(c, k) 9. Output OB. The conversions in steps (2) and (4) from byte string to large integer representative and back again may not be immediately obvious. Large integers and byte (bit) strings are conceptually different even though they may both be stored as arrays of bytes in your computer. 6.4 SUMMARY Public-key cryptography, or asymmetric cryptography, is an encryption scheme that uses two mathematically related, but not identical, keys - a public key and a private key. Unlike symmetric key algorithms that rely on one key to both encrypt and decrypt, each key performs a unique function. The public key is used to encrypt and the private key is used to decrypt. It is computationally infeasible to compute the private key based on the public key. Because of this, public keys can be freely shared, allowing users an easy and convenient method for encrypting content and verifying digital signatures, and private keys can be kept secret, ensuring only the owners of the private keys can decrypt content and create digital signatures. Since public keys need to be shared but are too big to be easily remembered, they are stored on digital certificates for secure transport and sharing. Since private keys are not shared, they are simply stored in the software or operating system you use, or on hardware (e.g., USB token, hardware security module) containing drivers that allow it to be used with your software or operating system. Public key algorithms are fundamental security ingredients in modern cryptosystems, applications and protocols assuring the confidentiality, authenticity and non-repairability of electronic communications and data storage. They underpin various Internet standards, such as Transport Layer Security (TLS), S/MIME, PGP, and GPG. Some public key algorithms 141 CU IDOL SELF LEARNING MATERIAL (SLM)

provide key distribution and secrecy (e.g., Diffie–Hellman key exchange), some provide digital signatures (e.g., Digital Signature Algorithm), and some provide both (e.g., RSA). 6.5 KEY WORDS/ABBREVIATIONS • RSA Public Keys: RSA (Rivest–Shamir–Adleman) is one of the first practical public- key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and it is different from the decryption key which is kept secret (private). • Public Key Cryptography: Public-key encryption is a cryptographic system that uses two keys – a public key known to everyone and a private or secret key known only to the recipient of the message. • Public Key Cryptographic Algorithms: Find a hard math problem, that is easy to compute in the forward direction, but is difficult to solve in the reverse direction, unless you have some special knowledge. • Key Generation: The keys for the RSA algorithm are generated the following way: Choose two distinct prime numbers p and q. For security purposes, the integers p and q should be chosen at random, and should be similar in magnitude but ’differ in length by a few digits’ to make factoring harder. • Deployment: An installation of Authentication Manager that consists of a primary instance and, optionally, one or more replica instances. • Demilitarized zone: The area of a network configured between two network firewalls. 6.6 LEARNING ACTIVITY 1. Implement the Encryption using PKCS#1v1.5 142 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Explain the process of implementing encryption and decryption through RSA on simple text 21. 6.7 UNIT END QUESTIONS (MCQ AND DESCRIPTIVE) A. Descriptive Questions 1. What is Public key Cryptography? 2. How key is generated in Public key cryptography? 3. How do we generate keys in RSA? 4. Explain Encryption and Decryption. 5. Explain the characteristics of Public Encryption key: B. Multiple Choice Questions 1. In a RSA cryptosystem a particular A uses two prime numbers p = 13 and q =17 to generate her public and private keys. If the public key of Ais 35. Then the private key of A is . a. 11 b. 13 c. 16 d. 17 2. Anarkali digitally signs a message and sends it to Salim. Verification of the signature by Salim requires 143 CU IDOL SELF LEARNING MATERIAL (SLM)

a. Anarkali’s public key. b. Salim’s public key. c. Salim’s private key. d. Anarkali’s private key. 3. A sender is employing public key cryptography to send a secret message to a receiver. Which one of the following statements is TRUE? a. Sender encrypts using receiver’s public key b. Sender encrypts using his own public key c. Receiver decrypts using sender’s public key d. Receiver decrypts using his own public key 4. Which of the following are used to generate a message digest by the network security protocols? (P) RSA (Q) SHA-1 (R) DES (S) MD5 a. P and R only b. Q and R only c. Q and S only d. R and S only 144 CU IDOL SELF LEARNING MATERIAL (SLM)

5. In the RSA public key cryptosystem, which one of the following numbers will always be largest? a. e b. n c. p d. q Answer 1.a 2.a 3.a 4.c 5.b 6.8 REFERENCES • Smart, Nigel (February 19, 2008). \"Dr Clifford Cocks CB\". Bristol University. Retrieved August 14, 2011. • Rivest, R.; Shamir, A.; Adleman, L. (February 1978). \"A Method for Obtaining Digital Signatures and Public-Key Cryptosystems\" (PDF). Communications of the ACM. 21 (2): 120–126. CiteSeerX 10.1.1.607.2677. doi:10.1145/359340.359342. S2CID 2873616. • Diffie, W.; Hellman, M.E. (November 1976). \"New directions in cryptography\". IEEE Transactions on Information Theory. 22 (6): 644–654. CiteSeerX 10.1.1.37.9720. doi:10.1109/TIT.1976.1055638. ISSN 0018-9448. • Chan Dai Truyen Thai; Jemin Lee; Tony Q. S. Quek (Feb 2016). \"Physical-Layer Secret Key Generation with Colluding Untrusted Relays\". IEEE Transactions on Wireless Communications. 15 (2): 1517–1530. doi:10.1109/TWC.2015.2491935. • Chan Dai Truyen Thai; Jemin Lee; Tony Q. S. Quek (Dec 2015). \"Secret Group Key Generation in Physical Layer for Mesh Topology\". 2015 IEEE Global Communications Conference (GLOBECOM). San Diego. pp. 1–6. doi:10.1109/GLOCOM.2015.7417477. 145 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 7: PUBLIC KEY CRYPTOGRAPHY 2 Structure 7.0 Learning Objectives 7.1 Introduction 7.2 Digital Signature (Algorithm) 7.2.1 The DSS Approach 7.2.2 The Digital Signature Algorithm 7.3 El-Gamal signatures 7.4 Zero-knowledge signatures 7.5 Summary 7.6 Key Words/Abbreviations 7.7 Learning Activity 7.8 Unit End Questions (MCQ and Descriptive) 7.9 References 7.0 LEARNING OBJECTIVES At the end of the unit learner will able to understand and have knowledge of following aspects of Cryptography and its keys: • State of Digital Signature • Introduction to El-Gamal Signature • Provision of Zero Knowledge Signatures 7.1 INTRODUCTION Properties 146 CU IDOL SELF LEARNING MATERIAL (SLM)

Message authentication protects two parties who exchange messages from any third party. How ever, it does not protect the two parties against each other. Several forms of dispute between the two are possible. Figure 7.1 Properties For example, suppose that John sends an authenticated message to Mary, using one of the schemes of Figure Consider the following disputes that could arise. 1. Mary may forge a different message and claim that it came from John. Mary would simply have to create a message and append an authentication code using the key that John and Mary share. 2. John can deny sending the message. Because itis possible for Mary to forge a message , there is no way to prove that John did in fact send the message. 147 CU IDOL SELF LEARNING MATERIAL (SLM)

Both scenarios are of legitimate concern. Here is an example of the first scenario:An electronic funds transfer takes place, and the receiver increases the amount of funds transferred and claims that the larger amount had arrived from the sender. An example of the second scenario is that an electronic mail message contains instructions to a stockbroker for a transaction that subsequently turns out bad ly.The sender pretends that the message was never sent. Figure 7.2 Properties In situations where there is not complete trust between sender and receiver, something more than authentication is needed. The most attractive solution to this problem is the digital signature. The digital signature must have the following properties: • It must verify the author and the date and time of the signature. • It must authenticate the contents at the time of the signature. • It must be verifiable by third parties, to resolve disputes. 148 CU IDOL SELF LEARNING MATERIAL (SLM)

Thus, the digital signature function includes the authentication function. Attacks and Forgeries [GOLD88] lists the following types of attacks, in order of increasing severity. Here A denotes the user whose signature method is being attacked, and C denotes the attacker. • Key-only attack: C only knows A’s public key. • Known messageattack: C is given access to a set of messages and their signatures. • Generic chosen message attack: C chooses a list of messages before attempt- ing to breaks A’s signature scheme, independent of A’s public key. C then obtains from A valid signatures for the chosen messages. The attack is generic, because it does not depend on A’s public key; the same attack is used against everyone. • Directed chosen message attack: Similar to the generic attack, except that thelist of messa ges to be signed is chosen after C knows A’s public key but before any signatures areseen. • Adaptive chosen message attack: C is allowed to use A as an “oracle.” This means the A may request signatures of messages that depend on previously obtained message– signaturepairs. [GOLD88] then defines success at breaking a signature scheme as an outcome in which C can do any of the following with a non-negligible probability: • Totalbreak: C determines A’sprivate key. • Universal forgery: C finds an efficient signing algorithm that provides an equivalent way of constructing signatures on arbitrary messages. • Selective forgery: C forges a signature for a particular message chosen by C. • Existential forgery: C forges a signature for at least one message. C has no control over the message. Consequently, this forgery may only be a minor nuisance to A. Digital Signature Requirements 149 CU IDOL SELF LEARNING MATERIAL (SLM)