Classical Cryptography

Introduction to Cryptography

(limited to monoalphabetic substitution)


  • cryptography is the study of secret (crypto-) writing (-graphy)

    • concerned with developing algorithms which may be used to:
      • conceal the context of some message from all except the sender and recipient (privacy or secrecy), and/or
      • verify the correctness of a message to the recipient (authentication)
    • form the basis of many technological solutions to computer and communications security problems
    • for a good overview paper see:
    W Diffie, M E Hellman, "Privacy and Authentication: An Introduction to Cryptography", in Proc. IEEE, Vol 67(3) Mar 1979, pp 397-427

    Basic Concepts

    cryptography
    the art or science encompassing the principles and methods of transforming an intelligible message into one that is unintelligible, and then retransforming that message back to its original form
    plaintext
    the original intelligible message
    ciphertext
    the transformed message
    cipher
    an algorithm for transforming an intelligible message into one that is unintelligible by transposition and/or substitution methods
    key
    some critical information used by the cipher, known only to the sender & receiver
    encipher (encode)
    the process of converting plaintext to ciphertext using a cipher and a key
    decipher (decode)
    the process of converting ciphertext back into plaintext using a cipher and a key
    cryptanalysis
    the study of principles and methods of transforming an unintelligible message back into an intelligible message without knowledge of the key. Also called codebreaking
    cryptology
    both cryptography and cryptanalysis
    code
    an algorithm for transforming an intelligible message into an unintelligible one using a code-book

    Concepts

    Encryption C = E_(K)(P)

    Decryption P = E_(K)^(-1)(C)

    E_(K) is chosen from a family of transformations known as a cryptographic system.

    The parameter that selects the individual transformation is called the key K, selected from a keyspace K

    More formally a cryptographic system is a single parameter family of invertible transformations

    E_(K) ; K in K : P -> C

    with the inverse algorithm E_(K)^(-1) ; K in K : C -> P

    such that the inverse is unique

    Usually assume the cryptographic system is public, and only the key is secret information

    Cryptanalytic Attacks

    • have several different types of attacks

    ciphertext only

    • only have access to some enciphered messages
    • use statistical attacks only

    known plaintext

    • know (or strongly suspect) some plaintext-ciphertext pairs
    • use this knowledge in attacking cipher

    chosen plaintext

    • can select plaintext and obtain corresponding ciphertext
    • use knowledge of algorithm structure in attack

    chosen plaintext-ciphertext

    • can select plaintext and obtain corresponding ciphertext, or select ciphertext and obtain plaintext
    • allows further knowledge of algorithm structure to be used

    Unconditional and Computational Security

    • two fundamentally different ways ciphers may be secure
      unconditional security
      - no matter how much computer power is available, the cipher cannot be broken
      computational security
      - given limited computing resources (eg time needed for calculations is greater than age of universe), the cipher cannot be broken

    A Brief History of Cryptography

    Ancient Ciphers

    • have a history of at least 4000 years
    • ancient Egyptians enciphered some of their hieroglyphic writing on monuments
    • ancient Hebrews enciphered certain words in the scriptures
    • 2000 years ago Julius Ceasar used a simple substitution cipher, now known as the Caesar cipher
    • Roger Bacon described several methods in 1200s
    • Geoffrey Chaucer included several ciphers in his works
    • Leon Alberti devised a cipher wheel, and described the principles of frequency analysis in the 1460s
    • Blaise de Vigenère published a book on cryptology in 1585, & described the polyalphabetic substitution cipher
    • increasing use, esp in diplomacy & war over centuries

    Machine Ciphers

    • Jefferson cylinder, developed in 1790s, comprised 36 disks, each with a random alphabet, order of disks was key, message was set, then another row became cipher
    • Wheatstone disc, originally invented by Wadsworth in 1817, but developed by Wheatstone in 1860's, comprised two concentric wheels used to generate a polyalphabetic cipher
    • Enigma Rotor machine, one of a very important class of cipher machines, heavily used during 2nd world war, comprised a series of rotor wheels with internal cross-connections, providing a substitution using a continuosly changing alphabet

    Classical Cryptographic Techniques

    • have two basic components of classical ciphers: substitution and transposition
    • in substitution ciphers letters are replaced by other letters
    • in transposition ciphers the letters are arranged in a different order
    • these ciphers may be:
    • monoalphabetic - only one substitution/ transposition is used, or
    • polyalphabetic - where several substitutions/ transpositions are used
    • several such ciphers may be concatentated together to form a product cipher

    Caesar Cipher - a monoalphabetic cipher

    • replace each letter of message by a letter a fixed distance away eg use the 3rd letter on
    • reputedly used by Julius Caesar
    eg. 
    	L FDPH L VDZ L FRQTXHUHG
	I CAME I SAW I CONQUERED
    ie mapping is 
    	ABCDEFGHIJKLMNOPQRSTUVWXYZ
	DEFGHIJKLMNOPQRSTUVWXYZABC
    • can describe this cipher as:
    Encryption E_(k) : i -> i + k mod 26

    Decryption D_(k) : i -> i - k mod 26

    Cryptanalysis of the Caesar Cipher

    • only have 26 possible ciphers
    • could simply try each in turn - exhaustive key search 
    				GDUCUGQFRMPCNJYACJCRRCPQ
				HEVDVHRGSNQDOKZBDKDSSDQR
	Plain	-	IFWEWISHTOREPLACELETTERS
				JGXFXJTIUPSFQMBDFMFUUFST
				KHYGYKUJVQTGRNCEGNGVVGTU
	Cipher -	LIZHZLVKWRUHSODFHOHWWHUV
				MJAIAMWLXSVITPEGIPIXXIVW
    • also can use letter frequency analysis 
    Single Letter              Double Letter             Triple Letter              
E                          TH                        THE                        
T                          HE                        AND                        
R                          IN                        TIO                        
N                          ER                        ATI                        
I                          RE                        FOR                        
O                          ON                        THA                        
A                          AN                        TER                        
S                          EN                        RES

    Character Frequencies

    • in most languages letters are not equally common
    • in English e is by far the most common letter
    • have tables of single double & triple letter frequencies
    • these are different for different languages (see Appendix A in Seberry & Pieprzyk)

    • use these tables to compare with letter frequencies in ciphertext, since a monoalphabetic substitution does not change relative letter frequencies
  • do need a moderate amount of ciphertext (100+ letters)

    Modular Arithmetic monoalphabetic cipher

    • more generally could use a more complex equation to calculate the ciphertext letter for each plaintext letter
    E_(a b) : i ->a.i + b mod 26

    nb a must not divide 26 (ie gcd(a,26) = 1)

    otherwise cipher is not reversible eg a=2

    and a=0, b=1, c=2 ... , y=24, z=25

    • eg E_(5 7) : i ->5.i + 7 mod 26
    Cryptanalysis:
    • use letter frequency counts to guess a couple of possible letter mappings
      • nb frequency pattern not produced just by a shift
    • use these mappings to solve 2 simultaneous equations to derive above parameters

    Example - Sinkov pp 34-35

    Mixed Alphabets

    • most generally we could use an arbitrary mixed (jumbled) alphabet
    • each plaintext letter is given a different random ciphertext letter, hence key is 26 letters long 
    Plain:   ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher:  DKVQFIBJWPESCXHTMYAUOLRGZN
Plaintext:  IFWEWISHTOREPLACELETTERS
Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA
    • now have a total of 26! ^(~) 4 ^(x) 10^(26) keys
    • with so many keys, might think this is secure
    !!!WRONG!!!
    • problem is not the number of keys, rather:
    1) there is lots of statistical information in message

    2) can solve the problem piece by piece

    (ie can get key nearly right, and nearly get message)

    (near enough MUST NOT be good enough!)

    Cryptanalysis

    • use frequency counts to guess letter by letter
    • also have frequencies for digraphs & trigraphs

    General Monoalphabetic

    • special form of mixed alphabet
    • use key as follows:
      • write key (with repeated letters deleted)
      • then write all remaining letters in columns underneath
      • then read off by columns to get ciphertext equivalents

    Example Seberry p66 

    	STARW
	BCDEF
	GHIJK
	LMNOP
	QUVXY
	Z

Plain:  ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: SBGLQZTCHMUADINVREJOXWFKPY

Plaintext:  I KNOW ONLY THAT I KNOW NOTHING
Ciphertext: H UINF NIAP OCSO H UINF INOCHIT