Part I: Crypto
Chapter 2
Part 1 Cryptography 1
Chapter 2: Crypto Basics
MXDXBVTZWVMXNSPBQXLIMSCCSGXSCJXBOVQX
CJZMOJZCVC
TVWJCZAAXZBCSSCJXBQCJZCOJZCNSPOXBXSBTV
WJC
JZDXGXXMOZQMSCSCJXBOVQXCJZMOJZCNSPJZH
GXXMOSPLH
JZDXZAAXZBXHCSCJXTCSGXSCJXBOVQX
plaintext from Lewis Carroll, Alice in Wonderland
The solution is by no means so difficult as you might
be led to imagine from the first hasty inspection of the characters.
These characters, as any one might readily guess,
form a cipher that is to say, they convey a meaning…
Part 1 Cryptography 2
Edgar Allan Poe, The Gold Bug
Crypto
❑ Cryptology The art and science of
making and breaking “secret codes”
❑ Cryptography making “secret codes”
❑ Cryptanalysis breaking “secret
codes”
❑ Crypto all of the above (and more)
Part 1 Cryptography 3
How to Speak Crypto
❑ A cipher or cryptosystem is used to encrypt
the plaintext
❑ The result of encryption is ciphertext
❑ We decrypt ciphertext to recover plaintext
❑ A key is used to configure a cryptosystem
❑ A symmetric key cryptosystem uses the same
key to encrypt as to decrypt
❑ A public key cryptosystem uses a public key
to encrypt and a private key to decrypt
Part 1 Cryptography 4
Crypto
❑ Basic assumptions
o The system is completely known to the attacker
o Only the key is secret
o That is, crypto algorithms are not secret
❑ This is known as Kerckhoffs’ Principle
❑ Why do we make such an assumption?
o Experience has shown that secret algorithms
tend to be weak when exposed
o Secret algorithms never remain secret
o Better to find weaknesses beforehand
Part 1 Cryptography 5
Crypto as Black Box
key key
plaintext encrypt decrypt plaintext
ciphertext
A generic view of symmetric key crypto
Part 1 Cryptography 6
Simple Substitution
❑ Plaintext: fourscoreandsevenyearsago
❑ Key:
Plaintext a b c d e f g h i j k l m n o p q r s t u v w x y z
Ciphertext D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
❑ Ciphertext:
IRXUVFRUHDQGVHYHQBHDUVDJR
❑ Shift by 3 is “Caesar’s cipher”
Part 1 Cryptography 7
Ceasar’s Cipher Decryption
❑ Suppose we know a Caesar’s cipher is
being used:
Plaintext a b c d e f g h i j k l m n o p q r s t u v w x y z
Ciphertext D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
❑ Given ciphertext:
VSRQJHEREVTXDUHSDQWV
❑ Plaintext: spongebobsquarepants
Part 1 Cryptography 8
Not-so-Simple Substitution
❑ Shift by n for some n ∈ {0,1,2,…,25}
❑ Then key is n
❑ Example: key n = 7
Plaintext ab c d e f g h i j k l m n o p q r s t u v w x y z
Ciphertext H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
Part 1 Cryptography 9
Cryptanalysis I: Try Them All
❑ A simple substitution (shift by n) is used
o But the key is unknown
❑ Given ciphertext: CSYEVIXIVQMREXIH
❑ How to find the key?
❑ Only 26 possible keys try them all!
❑ Exhaustive key search
❑ Solution: key is n = 4
Part 1 Cryptography 10
Simple Substitution: General Case
❑ In general, simple substitution key can be
any permutation of letters
o Not necessarily a shift of the alphabet
❑ For example
Plaintext a b c d e f g h i j k l m n o p q r s t u v w x y z
Ciphertext J I C A X S E Y V D K W B Q T Z R H F M P N U L G O
❑ Then 26! > 288 possible keys
Part 1 Cryptography 11
Cryptanalysis II: Be Clever
❑ We know that a simple substitution is used
❑ But not necessarily a shift by n
❑ Find the key given the ciphertext:
PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOX
BTFXQWAXBVCXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQ
WAEBIPBFXFQVXGTVJVWLBTPQWAEBFPBFHCVLXBQUFEVWLXGD
PEQVPQGVPPBFTIXPFHXZHVFAGFOTHFEFBQUFTDHZBQPOTHXTY
FTODXQHFTDPTOGHFQPBQWAQJJTODXQHFOQPWTBDHHIXQV
APBFZQHCFWPFHPBFIPBQWKFABVYYDZBOTHPBQPQJTQOTOGHF
QAPBFEQJHDXXQVAVXEBQPEFZBVFOJIWFFACFCCFHQWAUVWF
LQHGFXVAFXQHFUFHILTTAVWAFFAWTEVOITDHFHFQAITIXPFH
XAFQHEFZQWGFLVWPTOFFA
Part 1 Cryptography 12
Cryptanalysis II
❑ Cannot try all 288 simple substitution keys
❑ Can we be more clever?
❑ English letter frequency counts…
Part 1 Cryptography 13
Cryptanalysis II
❑ Ciphertext:
PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQ
WAXBVCXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQWAEBIPBFXFQ
VXGTVJVWLBTPQWAEBFPBFHCVLXBQUFEVWLXGDPEQVPQGVPPBFTIXPFH
XZHVFAGFOTHFEFBQUFTDHZBQPOTHXTYFTODXQHFTDPTOGHFQPBQW
AQJJTODXQHFOQPWTBDHHIXQVAPBFZQHCFWPFHPBFIPBQWKFABVYY
DZBOTHPBQPQJTQOTOGHFQAPBFEQJHDXXQVAVXEBQPEFZBVFOJIWFF
ACFCCFHQWAUVWFLQHGFXVAFXQHFUFHILTTAVWAFFAWTEVOITDHFH
FQAITIXPFHXAFQHEFZQWGFLVWPTOFFA
❑ Analyze this message using statistics below
Ciphertext frequency counts:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
21 26 6 10 12 51 10 25 10 9 3 10 0 1 15 28 42 0 0 27 4 24 22 28 6 8
Part 1 Cryptography 14
Cryptanalysis: Terminology
❑ Cryptosystem is secure if best know
attack is to try all keys
o Exhaustive key search, that is
❑ Cryptosystem is insecure if any
shortcut attack is known
❑ But then insecure cipher might be
harder to break than a secure cipher!
o What the … ?
Part 1 Cryptography 15
Double Transposition
❑ Plaintext: attackxatxdawn
Permute rows
and columns
⇒
❑ Ciphertext: xtawxnattxadakc
❑ Key is matrix size and permutations:
(3,5,1,4,2) and (1,3,2)
Part 1 Cryptography 16
One-Time Pad: Encryption
e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111
Encryption: Plaintext ⊕ Key = Ciphertext
h e i l h i t l e r
Plaintext: 00 00 01 10 00 01
111
10 00
101
1 0 0 0 1 0 0 0
Key: 10 00 00
111 101 110 101 111 101 110
0 0 0
Ciphertext: 10 00 00
110 101 110 110 111 110 101
0 1 1
s r l h s s t h s r
Part 1 Cryptography 17
One-Time Pad: Decryption
e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111
Decryption: Ciphertext ⊕ Key = Plaintext
s r l h s s t h s r
Ciphertext: 110 101 10 00 110 110 111 00 110 101
0 1 1
Key: 111 101 110 101 111 10 00 00
101 110
0 0 0
Plaintext: 00 00 01 10 00 01 10 00
111 101
1 0 0 0 1 0 0 0
h e i l h i t l e r
Part 1 Cryptography 18
One-Time Pad
Double agent claims following “key” was used:
s r l h s s t h s r
Ciphertext: 110 101 10 00 110 110 111 00 110 101
0 1 1
“key”: 101 111 00 10 00 00
101 111 101 110
0 0 0 0
“Plaintext”: 01 10 10 00 01 10 00
011 111 101
0 0 0 1 0 0 0
k i l l h i t l e r
e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111
Part 1 Cryptography 19
One-Time Pad
Or claims the key is…
s r l h s s t h s r
Ciphertext: 110 101 10 00 110 110 111 00
110 101
0 1 1
“key”: 111 101 00 00
011 101 110 011 101 101
0 1
“Plaintext”: 00 00 10 01 00 01 00
011 110 011
1 0 0 0 0 0 0
h e l i k e s i k e
e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111
Part 1 Cryptography 20
One-Time Pad Summary
❑ Provably secure
o Ciphertext gives no useful info about plaintext
o All plaintexts are equally likely
❑ BUT, only when be used correctly
o Pad must be random, used only once
o Pad is known only to sender and receiver
❑ Note: pad (key) is same size as message
❑ So, why not distribute msg instead of pad?
Part 1 Cryptography 21
Real-World One-Time Pad
❑ Project VENONA
o Soviet spies encrypted messages from U.S. to
Moscow in 30’s, 40’s, and 50’s
o Nuclear espionage, etc.
o Thousands of messages
❑ Spy carried one-time pad into U.S.
❑ Spy used pad to encrypt secret messages
❑ Repeats within the “one-time” pads made
cryptanalysis possible
Part 1 Cryptography 22
VENONA Decrypt (1944)
[C% Ruth] learned that her husband [v] was called up by the army but
he was not sent to the front. He is a mechanical engineer and is now
working at the ENORMOUS [ENORMOZ] [vi] plant in SANTA FE, New
Mexico. [45 groups unrecoverable]
detain VOLOK [vii] who is working in a plant on ENORMOUS. He is a
FELLOWCOUNTRYMAN [ZEMLYaK] [viii]. Yesterday he learned that
they had dismissed him from his work. His active work in progressive
organizations in the past was cause of his dismissal. In the
FELLOWCOUNTRYMAN line LIBERAL is in touch with CHESTER [ix].
They meet once a month for the payment of dues. CHESTER is
interested in whether we are satisfied with the collaboration and
whether there are not any misunderstandings. He does not inquire
about specific items of work [KONKRETNAYa RABOTA]. In as much
as CHESTER knows about the role of LIBERAL's group we beg
consent to ask C. through LIBERAL about leads from among people
who are working on ENOURMOUS and in other technical fields.
❑ “Ruth” == Ruth Greenglass
❑ “Liberal” == Julius Rosenberg
❑ “Enormous” == the atomic bomb
Part 1 Cryptography 23
Codebook Cipher
❑ Literally, a book filled with “codewords”
❑ Zimmerman Telegram encrypted via codebook
Februar 13605
fest 13732
finanzielle 13850
folgender 13918
Frieden 17142
Friedenschluss 17149
: :
❑ Modern block ciphers are codebooks!
❑ More about this later…
Part 1 Cryptography 24
Codebook Cipher: Additive
❑ Codebooks also (usually) use additive
❑ Additive book of “random” numbers
o Encrypt message with codebook
o Then choose position in additive book
o Add in additives to get ciphertext
o Send ciphertext and additive position (MI)
o Recipient subtracts additives before
decrypting
❑ Why use an additive sequence?
Part 1 Cryptography 25
Zimmerman
Telegram
❑ Perhaps most
famous codebook
ciphertext ever
❑ A major factor in
U.S. entry into
World War I
Part 1 Cryptography 26
Zimmerman
Telegram
Decrypted
❑ British had
recovered
partial
codebook
❑ Then able to
fill in missing
parts
Part 1 Cryptography 27
Random Historical Items
❑ Crypto timeline
❑ Spartan Scytale transposition
cipher
❑ Caesar’s cipher
❑ Poe’s short story: The Gold Bug
❑ Election of 1876
Part 1 Cryptography 28
Election of 1876
❑ “Rutherfraud” Hayes vs “Swindling” Tilden
o Popular vote was virtual tie
❑ Electoral college delegations for 4 states
(including Florida) in dispute
❑ Commission gave all 4 states to Hayes
o Voted on straight party lines
❑ Tilden accused Hayes of bribery
o Was it true?
Part 1 Cryptography 29
Election of 1876
❑ Encrypted messages by Tilden supporters
later emerged
❑ Cipher: Partial codebook, plus transposition
❑ Codebook substitution for important words
ciphertext plaintext
Copenhagen Greenbacks
Greece Hayes
Rochester votes
Russia Tilden
Warsaw telegram
: :
Part 1 Cryptography 30
Election of 1876
❑ Apply codebook to original message
❑ Pad message to multiple of 5 words (total
length, 10,15,20,25 or 30 words)
❑ For each length, a fixed permutation
applied to resulting message
❑ Permutations found by comparing several
messages of same length
❑ Note that the same key is applied to all
messages of a given length
Part 1 Cryptography 31
Election of 1876
❑ Ciphertext: Warsaw they read all
unchanged last are idiots can’t situation
❑ Codebook: Warsaw == telegram
❑ Transposition: 9,3,6,1,10,5,2,7,4,8
❑ Plaintext: Can’t read last telegram.
Situation unchanged. They are all idiots.
❑ A weak cipher made worse by reuse of key
❑ Lesson? Don’t overuse keys!
Part 1 Cryptography 32
Early 20th Century
❑ WWI Zimmerman Telegram
❑ “Gentlemen do not read each other’s mail”
o Henry L. Stimson, Secretary of State, 1929
❑ WWII golden age of cryptanalysis
o Midway/Coral Sea
o Japanese Purple (codename MAGIC)
o German Enigma (codename ULTRA)
Part 1 Cryptography 33
Post-WWII History
❑ Claude Shannon father of the science of
information theory
❑ Computer revolution lots of data to protect
❑ Data Encryption Standard (DES), 70’s
❑ Public Key cryptography, 70’s
❑ CRYPTO conferences, 80’s
❑ Advanced Encryption Standard (AES), 90’s
❑ The crypto genie is out of the bottle…
Part 1 Cryptography 34
Claude Shannon
❑ The founder of Information Theory
❑ 1949 paper: Comm. Thy. of Secrecy Systems
❑ Fundamental concepts
o Confusion obscure relationship between
plaintext and ciphertext
o Diffusion spread plaintext statistics through
the ciphertext
❑ Proved one-time pad is secure
❑ One-time pad is confusion-only, while double
transposition is diffusion-only
Part 1 Cryptography 35
Taxonomy of Cryptography
❑ Symmetric Key
o Same key for encryption and decryption
o Modern types: Stream ciphers, Block ciphers
❑ Public Key (or “asymmetric” crypto)
o Two keys, one for encryption (public), and one
for decryption (private)
o And digital signatures nothing comparable in
symmetric key crypto
❑ Hash algorithms
o Can be viewed as “one way” crypto
Part 1 Cryptography 36
Taxonomy of Cryptanalysis
❑ From perspective of info available to Trudy…
o Ciphertext only Trudy’s worst case scenario
o Known plaintext
o Chosen plaintext
▪ “Lunchtime attack”
▪ Some protocols will encrypt chosen data
o Adaptively chosen plaintext
o Related key
o Forward search (public key crypto)
o And others…
Part 1 Cryptography 37
