| Cryptographic Shakespeare |
| Cryptographic Shakespeare |
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:
o conceal the context of some message from all except the sender and recipient (privacy or secrecy), and/or
o 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
o 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:
o write key (with repeated letters deleted)
o then write all remaining letters in columns underneath
o 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
(limited to monoalphabetic substitution)
# cryptography is the study of secret (crypto-) writing (-graphy)
* concerned with developing algorithms which may be used to:
o conceal the context of some message from all except the sender and recipient (privacy or secrecy), and/or
o 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
o 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:
o write key (with repeated letters deleted)
o then write all remaining letters in columns underneath
o 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
 |
 |