Cryptography

• What is Encryption/Decription?
• Foundations of Cryptology
• Cipher Methods
• Cryptographic Algorithm,
• Cryptographic Tools,
• Protocols for secure communication,
• Attacks on cryptosystems

• Cryptography, a word with Greek origins, means “secret writing.” However, we use the term to refer to the science and art of transforming messages to make them secure and immune to attacks.

• Cryptography algorithm should be secure even if everyone knows how it works, the security of a cryptosystem should depend solely on the secrecy of the key and the private randomizer
• Based on Kerckhoff s principle, one should always ’ assume that the adversary, Eve, knows the encryption/decryption algorithm. The resistance of the cipher to attack must be based only on the secrecy of the key.
• In short:
  • Algorithm must be made public
  • Only the key is kept secret

• Number of Keys Used
  • Same secret key is used for encryption and decryption Symmetric/ → Conventional Encryption
  • Different keys for encryption and decryption Asymmetric/ Public → Key Encryption
• Type of operation used for encryption
  • Substitution – Each letter in the plaintext (bit, letter, group of bits or letters) is mapped into another element
  • Transposition/Permutation – Rearranging elements of the plaintext
• Plaintext processing
  • Blocks - Block ciphers processes one block of input at a time and produces an output for each input block
  • Bit by bit – Stream Cipher processes the input elements simultaneously, producing output one element at a time, as it goes along

• Efficiency
  • Functions E and D should have efficient algorithms K K
  • Symmetric key encryption is fast compared to public key encryption
  • How fast? Almost 30,000 times faster
• Consistency
  • Decrypting the ciphertext yields the plaintext
  • D (E (P)) = P K K

• not even the large number of keys in a monoalphabetic cipher provides security
• one approach to improving security was to encrypt multiple letters
• the Playfair Cipher is an example
• invented by Charles Wheatstone in 1854, but named after his friend Baron Playfair

• a 5X5 matrix of letters based on a keyword
• fill in letters of keyword (sans duplicates)
• fill rest of matrix with other letters
• eg. using the keyword MONARCHY

• plaintext is encrypted two letters at a time if a pair is a repeated letter, insert filler like 'X’ 1. if both letters fall in the same row, replace each 2. with letter to right (wrapping back to start from end) if both letters fall in the same column, replace 3. each with the letter below it (wrapping to top from bottom) otherwise each letter is replaced by the letter in 4. the same row and in the column of the other letter of the pair

• security much improved over monoalphabetic
• since have 26 x 26 = 676 digrams
• would need a 676 entry frequency table to analyse (verses 26 for a monoalphabetic)
• and correspondingly more ciphertext
• was widely used for many years eg. by US & British military in WW1 ⚫
• it can be broken, given a few hundred letters
• since still has much of plaintext structure

• There is one type of substitution cipher that is absolutely unbreakable.
  • The one-time pad was invented in 1917 by Joseph Mauborgne and Gilbert Vernam
  • We use a block of shift keys, (k, k, . . . , k ), to 1 2 n encrypt a plaintext, M, of length n, with each shift key being chosen uniformly at random.
• Since each shift is random, every ciphertext is equally likely for any plaintext.

• Developed by mathematician Lester Hill in 1929, the encryption algorithm takes m successive plaintext letters and substitutes with m ciphertext letters.
• Each letter is represented by a number modulo 26. (E.g. A = 0, B = 1, ..., Z = 25) n
• To encrypt a message, each block of letters is multiplied by an n × n invertible matrix, modulus 26.
• To decrypt the message, each block is multiplied by the inverse of the matrix used for encryption.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

• In a transposition cipher, the characters retain their plaintext form but change their positions to create the ciphertext
• The text is organized into a two-dimensional table, and the columns are interchanged according to a key
• The key defines which columns should be swapped

• Block ciphers require the length n of the plaintext to be a multiple of the block size b
• Padding the last block needs to be unambiguous (cannot just add zeroes)

• Example for b = 64 bits (8 bytes) “ Roberto (7 bytes) ”
  • Plaintext: “ Roberto9 (8 bytes), where ”
  • Padded plaintext: 9 denotes the number and not the character
• We need to always pad the last block, which may consist only of padding

• Advanced Encryption Standard (AES)
  • Selected by NIST in 2001 through open international competition and public discussion
  • 128-bit blocks and several possible key lengths: 128, 192 and 256 bits
  • Exhaustive search attack not currently possible
• International Data Encryption Algorithm (IDEA)
  • Uses a 128-bit key and is used in Pretty Good Privacy (PGP) encryption for e-mail systems
• RC5
  • Developed at MIT, and allows for variable length keys.
• Blowfish
  • Designed by Bruce Schneier in 1993 allows for variable length keys up to 448 bits

Objective: To recover the key and not just the messages, so that the attacker can easily compromise all future and past cipher texts.

General Approaches

• Cryptanalysis
• Brute force attack

• Based on what is known to the attacker, cryptanalytic attempts are classified as:
  • Ciphertext Only
  • Known Plaintext
  • Chosen Plaintext
  • Chosen Ciphertext
• Encryption algorithm is assumed to be known for all the attacks.
• In each case, the object is to determine the key (and plaintext) that was used.

Thank you