[ Security ] Ch02. Cryptography Techniques

Introduction

Basic Terminology

• Cryptography is the art(수단, 방법) of achieving security by encoding messages to make them non-readable.
• Cryptanalysis is the technique of decoding messages from a nonreadable format back to a readable format without knowing how they were initially converted from readable format to non-readable format.
  • Breaking a code
• Cryptology is a combination of cryptography and cryptanalysis.

• Plain Text: Language that can be easily understood
• Also called as clear text
• Cipher Text: Language that cannot be understood
• To achieve security, plain text is transformed into cipher text
• Caesar Cipher
  • Proposed by Julius Caesar (100 BC ~ 44 BC)
  • Mechanism to make a message non-understandable
  • Replaces each alphabet with the one three places down
  • Example: Replace each A with D, B with E, etc.

• Cipher Text Conversion
• Techniques for plain text to cipher text conversion
  • Substitution techniques
  • Transposition techniques

• Steganography
  • Steganography is the art and science of writing hidden messages in such a way that no one except the sender and intended recipient even realizes there is a hidden message
    • EX) One ancient example is that of Histiaeus, who shaved the head of his most trusted slave and tattooed a message on it. After his hair had grown the message was hidden.

---

Substitution Techniques

• In the substitution cipher technique, the characters of a plain text message are replaced by other characters, numbers or symbols.
  • Monoalphabetic substitution ciphers
    • Additive cipher (shift cipher or Caesar cipher)
  • Homophonic substitution ciphers
  • Polygram substitution ciphers
  • Polyalphabetic substitution ciphers
    • Autokey cipher
    • Vernam cipher

Monoalphabetic Substitution Ciphers

• In monoalphabetic substitution, the relationship between a symbol in the plaintext to a symbol in the ciphertext is always one-to-one
• Example
  • The following shows a plaintext and its corresponding ciphertext. The cipher is probably monoalphabetic because both l’s (els) are encrypted as O’s.

• Additive Cipher
  • The simplest monoalphabetic cipher is the additive cipher.
  • This cipher is sometimes called a shift cipher and sometimes a Caesar cipher, but the term additive cipher better reveals its mathematical nature.
  • Example
    • Eve has intercepted the ciphertext “UVACLYFZLJBYL”. Show how she can use a brute-force attack to break the cipher.
    • Eve tries keys from 1 to 7. With a key of 7, the plaintext is “not very secure”, which makes sense.
  • We can look for patterns of alphabets in a cipher text
  • Example
    • Eve has intercepted the following ciphertext. Using a statistical attack, find the plaintext.
    • When Eve tabulates the frequency of letters in this ciphertext, she gets: I =14, V =13, S =12, and so on. The most common character is I with 14 occurrences. This means key = 4 (I → E).

Homophonic Substitution Cipher

• One plaintext alphabet can map to more than one ciphertext alphabet.
  → cf. one-to-one (Monoalphabetic)
• The cipher-text character can be any one of the chosen set.
• For instance, ‘A’ can be replaced by ‘D’, ‘H’, ‘P’, ‘R’ / ‘B' can be replaced by ‘E’, ‘I’, ‘Q’, ‘S’, etc.
• Example

Polygram Substitution Cipher

• Block of plain text transformed into block of cipher text
• Similar text patterns can yield completely different cipher text patterns
• Block-by-block replacement, rather than character-by-character

Polyalphabetic Substitution Ciphers

• In polyalphabetic substitution, each occurrence of a character may have a different substitute.
• The relationship between a character in the plaintext to a character in the ciphertext is one-to-many.
• Autokey cipher is an example of polyalphabetic substitution cipher
  • The key is a stream of subkeys which is used to encrypt the corresponding character in the plaintext→ 중요!

• Autokey cipher
  • Assume that Alice and Bob agreed to use an autokey cipher with initial key value k1 = 12. Now Alice wants to send Bob the message “Attack is today”.
    Enciphering is done character by character.

• Vernam Cipher
  • Also called as One-Time Pad
  • Use a random set of non-repeating characters as the input cipher text
  • If an input cipher text is used, it is never used again
    • Hence the name one time
  • Key of the same length as the plaintext is required!
    • Suitable for small plain-text message
    1. Treat each plain text alphabet as a number in an increasing sequence, i.e. A = 0, B = 1, … Z = 25.
    2. Do the same for each character of the input cipher text.
    3. Add each number corresponding to the plain text alphabet to the corresponding input cipher text alphabet number.
    4. If the sum thus produced is greater than 26, subtract 26 from it.
    5. Translate each number of the sum back to the corresponding alphabet. This gives the output cipher text.
  • When One-time key pad is “NCBTZQARX”→ Short msg에 적합

• Other Techniques
  • Playfair Cipher
  • Hill Cipher

---

Transposition Techniques

• A transposition cipher does not substitute one symbol for another,
  instead it changes the location of the symbols.
• A transposition cipher reorders symbols.
  • Keyless transposition ciphers
    • Rail-Fence technique
    • Simple columnar transposition technique
  • Keyed transposition ciphers
  • Combining two approaches

Rail-Fence Technique

• Example of keyless transposition cipher
• The ciphertext is created reading the pattern row by row
• For example, to send the message “Meet me at the park” to Bob,
  Alice writes

Simple Columnar Transposition Technique

• The simple columnar transposition arranges the plain text as a sequence of rows of a rectangle that are read in columns randomly
• Simple columnar transposition technique with multiple rounds

Keyed Transposition Ciphers

• The keyless ciphers permute the characters by using writing plaintext in one way and reading it in another way.
• The permutation is done on the whole plaintext to create the whole ciphertext.
• Another method is to divide the plaintext into groups of predetermined size, called blocks, and then use a key to permute the characters in each block separately
• Example
  • Alice needs to send the message “Enemy attacks tonight” to Bob
  • The key used for encryption and decryption is a permutation key, which shows how the character are permuted
  • The permutation yields

Combining Two Approaches

• Keyless transposition ciphers + Keyed transposition ciphers

---

Symmetric and Asymmetric Key Cryptography

• Encryption: Conversion of plain text to cipher text

• Decryption: Conversion of cipher text to plain text
  

• Requirements
  • Two requirements for secure use of encryption:
    • a strong encryption algorithm
    • a secret key known only to sender / receiver
  • Mathematically have:
    • Y = E(K, X) < Encryption
    • X = D(K, Y) < Decryption
  • Assume encryption algorithm is known
  • Implies a secure channel to distribute key
    
    

• Kerckhoff’s Principle
  • : a cryptosystem should be secure, even if everything about the system, except the key, is public knowledge.
  • 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.
    
    

• Cryptographic Systems
  • Cryptographic systems can be characterized:
    • The type of encryption operations used
      • Substitution
      • Transposition
      • Product: Multi stages of substitutions and transpositions
    • The number of keys used
      • Single-key or secret → Symmetric key (sender와 reciever가 공유)
      • Two-key or public → Asymmetric key
    • The way in which plaintext is processed
      • Block
      • Stream
        
        

• Symmetric Key Cryptography
  • Also known as secret key algorithm
  • Use single key on encrypt and decrypt
  • Usually hardware assisted
• Asymmetric Key Cryptography
  • Also known as public-key algorithms
  • Pair of keys (i.e. private and public)
    • Key management is relatively easy
  • Computational intensive
    • Slow (100 times slower than symmetric algorithms of similar strengths!!)
  • Many new algorithms are developed recently
    
    

• Key Range and Key Size
  • The encryption/decryption algorithm is usually not a secret
  • Only the actual value of the key remains a challenge for the attacker
  • Attacker can consider brute-force attack, which works on the principle of trying every possible key in the key range, until getting the right key
    • Brute-force attack can be successful if key length is small
    • Start with Key = 0, then Key = 1, etc.
  • Specifies the number of possible keys
  • Bigger the key range, more difficult is the attack
  • In practice, at least 64, 128, 256 bit keys are used
  • Always possible to simply try every key
  • Most basic attack, proportional to key size
  • Assume either know / recognize plaintext

HGU 전산전자공학부 고윤민 교수님의 24-2 컴퓨터 보안 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.