MS in Telecommunications TCOM 500: Modern Telecommunications Dr. Bernd-Peter Paris George Mason University Spring 2009MS in Telecommunications Outline • Context • Encryption • Ciphers – encrypting information based on a cryptographic key • Public-Key Cryptography – secure exchange of cryptographic keys • Error-correction coding • Protecting against transmission errors Paris 2 TCOM 500: Modern TelecommunicationsMS in Telecommunications Context • Today’s class addresses two “value-added” services that can be applied to a sequence of bits. • Encryption: ensures privacy and authenticity of information. • Error-correction coding: protects against transmission errors. Paris 3 TCOM 500: Modern Telecommunications Hi! How are you? ADC Compression 01011… 1011… bits fewer bits Encryption 1101… secret bits Error-correction Coding 0101… protected bitsMS in Telecommunications ENCRYPTION Paris 4 TCOM 500: Modern TelecommunicationsMS in Telecommunications Introduction • When information is sent through public networks, there exists the potential for: • Eavesdropping: information is observed by some one other than the intended recipient. • Altering of information by an intermediate person. • To prevent either of these problems, cryptography provides a powerful set of tools for protecting information. Paris 5 TCOM 500: Modern Telecommunications Encryption Public Network Decryption Plaintext M Encryption Key K Encryption Key K Plaintext M Ciphertext C Ciphertext CMS in Telecommunications Definitions • Encryption algorithms are chosen from a family of similar ciphers. • Each member of the family is distinguished by an encryption key. • Encryption and decryption are governed by the key. • Strength of a cipher is related to the number of possible keys. Paris 6 TCOM 500: Modern Telecommunications Encryption Public Network Decryption Plaintext M Encryption Key K Encryption Key K Plaintext M Ciphertext C Ciphertext CMS in Telecommunications Transposition Ciphers • Transposition ciphers change the order of symbols. • In principle, for a message of p symbols there are p! permutations. • Each permutation can be associated with a particular key. • In practice, transposition is often done via block interleaving: • Place message row-wise in a matrix. • Permute columns according to a key. • Read cipher text out column-wise. 2 4 3 1 5 T H E I N V A S I O N W I L L B E G I N T O D A Y Paris 7 TCOM 500: Modern Telecommunications Plaintext M: THE INVASION WILL BEGIN TODAY Ciphertext C: IILIA TVNBT ESIGD HAWEO NOLNY Read out column-wise in the order indicated by column header – the encryption key determines this order. Fill matrix row-wise.MS in Telecommunications Ciphertext C: IILIA TVNBT ESIGD HAWEO NOLNY Transposition Ciphers - Decryption • To decrypt a transposition cipher, the encryption process is simply reversed. • Place ciphertext column-wise into a matrix. • Columns are filled in the order indicated by key. • Plain text M is recovered by reading out information row-wise. 2 4 3 1 5 T H E I N V A S I O N W I L L B E G I N T O D A Y Paris 8 TCOM 500: Modern Telecommunications Plaintext M: THE INVASION WILL BEGIN TODAY Fill matrix column-wise in the order indicated by the encryption key. Read matrix row-wise.MS in Telecommunications Substitution Ciphers • Substitution ciphers employ look-up tables to map each symbol of the plaintext into a corresponding ciphertext symbol. • There maybe multiple look-up tables indexed by the encryption key. • In other words, the encryption key may indicate which look-up table to use. • If there are m possible symbols in a message, then m! permutations of these symbols exist. Paris 9 TCOM 500: Modern Telecommunications Plain A B C D E F G H I J K L M Cipher D E F G H I J K L M N O P Plain N O P Q R S T U V W X Y Z Cipher Q R S T U V W X Y Z A B CMS in Telecommunications Substitution Cipher Paris 10 TCOM 500: Modern Telecommunications Plain A B C D E F G H I J K L M Cipher D E F G H I J K L M N O P Plain N O P Q R S T U V W X Y Z Cipher Q R S T U V W X Y Z A B C Look-up table: Plaintext M: THE INVASION WILL BEGIN TODAY Ciphertext C: WKH LQYDVLRQ ZLOO EHJLP WRGDB Encryption: Replace each plaintext symbol with corresponding ciphertext symbol. Plaintext M: THE INVASION WILL BEGIN TODAY Decryption: Replace each ciphertext symbol with corresponding plaintext symbol.MS in Telecommunications Example: DES – Basic Building Block Paris 11 TCOM 500: Modern Telecommunications Block of information bits Repeat half of bits 48 bits Fixed substitution cipher: 6 bits to 4 bits Full key has 56 bits. XOR Fixed transposition cipher DES: Data Encryption StandardMS in Telecommunications Example: DES – Full Algorithm Paris 12 TCOM 500: Modern Telecommunications Initial permutation Final permutation Basic Building Block (see previous slide) 32 bits 32 bits • DES was standardized in 1976. • Not adequate today • Can be broken within a few hours. • Successor: AES (Advanced Encryption Standard)MS in Telecommunications One-time Pads • A very powerful idea for encrypting information is provided by one-time pads. • One-time pads can be thought of as ever changing, random keys. • The basic idea is easily illustrated with binary messages. • Each bit in the plain text is xor-ed with a bit from a random sequence of bits. Paris 13 TCOM 500: Modern Telecommunications Binary plaintext: 01101010… One-time pad (random bit sequence): 01011110… Binary ciphertext: 00110100… XORMS in Telecommunications Exclusive-OR (XOR) • The exclusive-or (XOR) function is a standard logic function. • It accepts two input bits, and • Produces one output bit. • The exclusive-or of bits a and b is denoted xor(a,b). • The table on the right shows the exclusive-or for all combinations of input bits. a b xor(a,b) 0 0 0 0 1 1 1 0 1 1 1 0 Paris 14 TCOM 500: Modern Telecommunications Note: • If b=0, then xor(a,b) = a. • If b=1, then xor(a,b) is the inverse of a.MS in Telecommunications One-time Pads • One-time pads are very attractive because they are very difficult to break. • The encryption keys (one-time pads) are as long as the message. • However, they pose a difficult practical problem: • The encryption key must be known by sender and