Cryptography Cryptography is the technique of secret writing A cipher is a method of secret writing The purpose is to convert an intelligible message referred to as plaintext into apparently random nonsense text referred to as ciphertext The encryption process consists of an algorithm and a key The algorithm will produce a different output depending on the specific key being used at the time 2 Conventional Cryptography Basic Definitions Plaintext This is the original message or data that is fed into the algorithm as input Encryption Algorithm The encryption algorithm performs various substitutions and transformations on the plaintext Secret Key The secret key is also an input to the algorithm The exact substitutions and transformations performed by the algorithm depend on the key Ciphertext This is the scrambled message produced as output It depends on the plaintext and on the secret key For a given message two different keys will produce two different ciphertexts Basic Definitions Decryption algorithm This is essentially the encryption algorithm run in reverse It takes the ciphertext and the secret key and produces the origin plaintext Ciphertext cryptogram Cleartext plaintext message Ciphering encryption Deciphering decryption 1 2 There are two requirements for secure use of conventional encryption The opponent should be unable to decrypt cryptogram or discover the key even if he or she is in possession of a number of cryptograms together with the plaintext that produced each cryptogram Sender a receiver must have obtained copies of the secret key in a secure fashion and must keep the key secure It is important to note that the security of conventional encryption depends on the secrecy of the key not the secrecy of the algorithm The algorithm is supposed to be public Classification of Cryptographic systems 1 1 By the numbers of keys used If both sender and receiver use the same key the system is referred to as symmetric or single key secret key conventional cryptosystem If the sender and receiver uses a different key the system is referred to as symmetric or two key or public key cryptosystem By the way in which the plaintext is processed A block cipher processes the input one block of elements at a time producing an output block for each input block By the way in which the plaintext is processed A stream cipher processes the input elements continuously producing output one element at a time as it goes along Cryptanalysis The process of attempting to discover the plaintext or key is known as cryptanalysis The strategy used by the cryptanalyst depends on the nature of the encryption scheme and the information available to the cryptanalyst A cipher is breakable if is possible to determine systematically the key or the plaintext from pairs plaintext ciphertext given 1 2 An encryption scheme is computationally secure if the ciphertext generated by the scheme meets one or both of the following criteria The cost of breaking the cipher exceeds the value of the encrypted information The time required to break the cipher exceeds the useful lifetime of the information It is very difficult to estimate the amount of effort required to cryptanalize ciphertext successfully However assuming there are no inherent mathematical weaknesses in the algorithm then a brute force approach is indicated and here we can make some reasonable estimates about costs and time A brute force approach involves trying every possible key until an intelligible translation of the ciphertext into plaintext is obtained Assuming 1E12 Decryptions sec 12 Caesar Cipher A historical note A substitution cipher is one in which the letters of plaintext are replaced by other letters or by numbers or symbols The Caesar cipher involves replacing each letter of the alphabet with the letter standing three places further down the alphabet For example Rule algorithm a b c d e f g h i j k l m n o p q r s t u v w x y z d e f g h i j k l m n o p q r s t u v w x y z a b c Message Ciphertext meet phhw me ph after the toga party diwhu wkh wrjd sduwb Caesar Cipher A historical note If we assign a numerical equivalent to each letter a 0 b 1 z 25 then the algorithm can be expressed as follows C E p p 3 modulo 26 Where p is a letter i e a number between 0 and 25 and C E P is the corresponding ciphertext The decryption algorithm is as follows p D C C 3 modulo 26 The key space has 25 elements i e There are 25 possible keys XOR Operation 0 0 1 0 1 1 1 0 Example 1100 0111 1011 Permutations Example P 0101 1010 Left Circular rotation or shift of a Block of Bits Input bit 1 bit 2 bit3 bit 4 Output bit2 bit 3 bit 4 bit1 Input Output bit 1 bit 2 bit3 bit 4 bit3 bit 4 bit 1 bit2 Basic Operation i th round Li Ri 1 Ri Li 1 F Ri 1 Ki Feistel Cipher Structure Virtually all conventional block ciphers have a structure first described by H Feistel of IBM in 1973 Parameters Block size larger block sizes mean greater security all other things being equal but reduce encryption decryption speed A block size is a reasonable tradeoff and is nearly universal in block cipher design Key Size Larger key size means greater security but may decrease encryption decryption speed The most common key length in modern algorithms is 128 bits Number of rounds The essence of the Feistel cipher is that a single round offers inadequate security but that multiple rounds offer increasing security A typical size is 16 rounds 17 18 Feistel Cipher Structure Subkey generation algorithm Greater complexity in this algorithm lead to greater difficulty of cryptanalysis Round Function Again greater complexity generally means greater resistance to cryptanalysis Decryption Process The decryption process is as follows use the ciphertext as input to the algorithm but use the subkeys Ki in reverse order That is use Kn in the first round Kn 1 in the second and so on until K1 is used in the last round 19 Data Encryption Standard DES The most widely used encryption scheme is defined in the data encryption standard DES adopted in 1977 by National Institute of Standards and Technology NIST as a Federal Information Processing Standard 46 FIPS PUB 46 In 1994 NIST reaffirmed DES for federal use for another five years in FIPS PUB46 2 Block cipher 64 bits Key 64 bits but 8 bits are used as parity bits DES has a Feistel cipher structure with 16 rounds 20 Data Encryption Standard DES The process of decryption with DES is essentially the same as the encryption process The rule is as follows use the