Introduction. Basic Cryptography CS 3IS3
Ryszard Janicki
Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada
Acknowledgments: Material based on Information Security by Mark Stamp (Chapter 2)
Ryszard Janicki
Introduction. Basic Cryptography 1/37
Basic Information
Instructor: Dr. Ryszard Janicki, ITB 217, e-mail: janicki@mcmaster.ca, tel: 525-9140 ext: 23919 Teaching Assistants:
Mahdee Jodayree: mahdijaf@yahoo.com
Course website: http://www.cas.mcmaster.ca/~cs3is3, Lectures: 11:30pm – 12:30pm, Wednesday 11:30am-12:20pm, Friday 1:30-2:20,
TA Office Hours/Unofficial Tutorials: Thursday 1:00-2:00 pm Office hours: Monday: 12:30pm – 12:30pm, by e-mail appointment, via Teams or Skype
Ryszard Janicki
Introduction. Basic Cryptography 2/37
Course Details
Calendar Description:
Basic principles of information security; threats and defences; cryptography; introduction to network security and security management.
Mission:
This course aims to give an introduction to information security, including computer security, network security, cryptography, and web application security.
Ryszard Janicki
Introduction. Basic Cryptography 3/37
Learning Objectives: Preconditions
Preconditions:
Students should have basic knowledge of discrete mathematics (see Appendix A2 of the text book), basic knowledge of data structures and algorithms. They should be familiar with principal ideas of software development and know how to program in at least one programming language.
Ryszard Janicki
Introduction. Basic Cryptography 4/37
Learning Objectives: Postconditions
Postconditions:
A. Students should know and understand:
1 Cryptography: concepts and techniques
2 Access control
3 Security protocols
4 Security in software
5 Security in Operating Systems
6 Blockchains
B. Students should be able to:
1 Find security flaws in software
2 Design basic security protocols
Outline and Texts
Course Outline (Tentative): Basic cryptography. Symmetric key and public key cryptography. Hush functions and advanced cryptanalysis. Authentication and authorization. Simple authentication protocols and real-world security protocols. Software flaws and malware. Insecurity in software. Operating systems and security. Blockchains.
Texts: Mark Stamp, Information Security. Principles and Practice. 2nd Edition, J. Wiley 2011.
The course will not always follow the text-book closely.
Reference book: C. P. Pfleeger, S. L. Pfleeger, J. Margulies, Security in Computing. 5th Edition, Prentice Hall 2015.
Lecture Notes will be on the website a few days after or before a class. I deliver this course for the first time in this form, do not have anything to show from the past.
Ryszard Janicki
Introduction. Basic Cryptography 6/37
Evaluation
Evaluation: The will be a 2.5 hours (take home) final examination (40%) and three assignments (3 × 20% = 60%).
Detailed grading scheme:
Grade = 0.40 × exam + 0.2 × (assg1 + assg2 + assg3)
Late assignments will not be accepted.
Although you may discuss the general concept of the course material with your classmates, your assignment must be your individual effort.
Ryszard Janicki
Introduction. Basic Cryptography 7/37
Basic Cryptography
Ryszard Janicki
Introduction. Basic Cryptography 8/37
Cryptography: Vocabulary
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)
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
Ryszard Janicki
Introduction. Basic Cryptography 9/37
Crypto
Basic assumptions:
The system is completely known to the attacker
Only the key is secret
That is, crypto algorithms are not secret
This is known as Kerckhoffs’ Principle Why do we make such an assumption?
Experience has shown that secret algorithms tend to be weak when exposed
Secret algorithms never remain secret
Better to find weaknesses beforehand
Ryszard Janicki
Introduction. Basic Cryptography 10/37
Simple Substitution and Ceasar’s cipher
D
Simple Substitution
Plaintext: fourscoreandsevenyearsago Key:
Plaintext Ciphertext
Ciphertext: IRXUVFRUHDQGVHYHQBHDUVDJR
Shift by 3 is “Caesar’s cipher”
a
b
E
c
F
d
G
e
H
f
I
g
J
h
K
i
L
j
M
k
N
l
O
m
P
n
Q
o
R
p
S
q
T
r
U
s
V
t
W
u
X
v
Y
w
Z
x
A
y
z
B
C
Part 1 Cryptography 7
Ryszard Janicki
Introduction. Basic Cryptography 11/37
Ceasar’s Cipher Decryption
Suppose we know a Caesar’s cipher is being used:
Plaintext Ciphertext
Given ciphertext: VSRQJHEREVTXDUHSDQWV
Plaintext: spongebobsquarepants
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
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
Part 1 Cryptography 8
Ryszard Janicki
Introduction. Basic Cryptography 12/37
Ceasar’s Cipher Decryption
Analysis I
A simple substitution (shift by n) is used 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
Ryszard Janicki
Introduction. Basic Cryptography 13/37
Simple Substitution: General Case
Simple Substitution: General Case
In general, simple substitution key can be any permutation of letters
In general, simple substitution key can be any permutation of letters
o Not necessarily a shift of the alphabet Not necessarily a shift of the alphabet
For example For example
Plaintext Ciphertext
a
J
b
I
c
C
d
A
e
X
f
S
g
E
h
Y
i
V
j
D
k
K
l
W
m
B
n
Q
o
T
p
Z
q
R
r
H
s
F
t
M
u
P
v
N
w
U
x
L
y
z
G
O
Then 26! > 288 possible keys Then 26! > 288 possible keys
Part 1 Cryptography 11
Ryszard Janicki
Introduction. Basic Cryptography 14/37
Analysis II: Be Clever
We know that a simple substitution is used
But not necessarily a shift by n
Find the key given the ciphertext: PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJK- TOYQWIPBVWLXTOXBTFXQWAXBVCXQWAX FQJVWLEQNTOZQGGQLFXQWAKVWLXQWAE- BIPBFXFQVXGTVJVWLBTPQWAEBFPBFHCV XBQUFEVWLXGDPEQVPQGVPPBFTIXPFHXZHVFAG- FOTHFEFBQUFTDHZBQPOTHXTYFTO DXQHFTDPTOGHFQPBQWAQJJTODXQHFOQPWTBD- HHIXQVAPBFZQHCFWPFHPBFIPBQ WFABVYYDZBOTHPBQPQJTQOTOGHFQAPBFE- QJHDXXQVAVXEBQPEFZBVFOJIWFFACF CCFHQWAUVWFLQHGFXVAFXQHFUFHILTTAVWAF- FAWTEVOITDHFHFQAITIXPFHX- AFQHEZQWGFLVWPTOFFA
Ryszard Janicki
Introduction. Basic Cryptography 15/37
Analysis II: Frequency Counts
Cannot try all 288 simple substitution keys Can we be more clever?
English letter frequency counts!
Cryptanalysis II
Cannot try all 288 simple substitution keys Can we be more clever?
English letter frequency counts…
0.14 0.12 0.10 0.08 0.06 0.04 0.02 0.00
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Part 1 Cryptography
Ryszard Janicki
Introduction. Basic Cryptography 16/37
13
Analysis II
21
26
6
Ciphertext: PBFPVYFBQXZTYFPBFEQJHDXXQVAPT- PQJKTOYQWIPBVWLXTOXBTFXQWAXBVCXQWAX FQJVWLEQNTOZQGGQLFXQWAKVWLXQWAE- BIPBFXFQVXGTVJVWLBTPQWAEBFPBFHCV XBQUFEVWCLrXGyDpPtEQaVnPQaGlVyPsPBisFTIXPIFHXZHVFAG-
Ciphertext: DXQHFTDPTOGHFQPBQWAQJJTODXQHFOQPWTBD-
FOTHFEFBQUFTDHZBQPOTHXTYFTO
PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQ WAXBVCXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQWAEBIPBFXFQ
HHIXQVAPBFZQHCFWPFHPBFIPBQ
VXGTVJVWLBTPQWAEBFPBFHCVLXBQUFEVWLXGDPEQVPQGVPPBFTIXPFH WXZFHAVBFAVGYFOYTDHFZEBFBOQTUFHTPDHBZQBQPPQOJTTHXQTOYFTODGXQHHFFQTDAPPTOBGFHEFQ- PBQW AQJJTODXQHFOQPWTBDHHIXQVAPBFZQHCFWPFHPBFIPBQWKFABVYY
QJHDXXQVAVXEBQPEFZBVFOJIWFFACF
DZBOTHPBQPQJTQOTOGHFQAPBFEQJHDXXQVAVXEBQPEFZBVFOJIWFF
ACFCCFHQWAUVWFLQHGFXVAFXQHFUFHILTTAVWAFFAWTEVOITDHFH
CCFHQWAUVWFLQHGFXVAFXQHFUFHILTTAVWAF-
FQAITIXPFHXAFQHEFZQWGFLVWPTOFFA
FAWTEVOITDHFHFQAITIXPFHX- AFQHEZQWGFLVWPTOFFA
Analyze this message using statistics below Analyze this message using statistics below:
Ciphertext frequency counts:
A
B
C
D
10
E
12
F
51
G
10
H
25
I
10
J
9
K
3
L
10
M
0
N
1
O
15
P
28
Q
42
R
0
S
0
T
27
U
4
V
24
W
22
X
28
Y
6
Z
8
Ryszard Janicki
Introduction. Basic Cryptography 17/37
Can we be more clever? Cryptanalysis II
En•gliCsihphlertetxet:r PfBreF.q..uency counts…
•
Ciphertext:
English letter frequency counts:
PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQ WAEBIPBFXFQ GVPPBFTIXPFH
WAXBVCXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQ JVWLBTPQWAEBFPBFHCVLXBQUFEVWLXGDPEQVPQ
0.14 0.12 0.10 0.08 0.06 0.04 0.02
0.00 Analyze this message using statistic ABCDEFGHIJKLMNOPQRSTUVWXYZ
VXGTV XZHVF AQJJ DZBOT ACFCC FQAIT
AGFOTHFEFBQUFTDHZBQPOTHXTYFTODXQHFTDP TODXQHFOQPWTBDHHIXQVAPBFZQHCFWPFHPBFIP HPBQPQJTQOTOGHFQAPBFEQJHDXXQVAVXEBQPE
FHQWAUVWFLQHGFXVAFXQHFUFHILTTAVWAFFA IXPFHXAFQHEFZQWGFLVWPTOFFA
TOGHFQPBQW BQWKFABVYY FZBVFOJIWFF
WTEVOITDHFH
Part 1 Cryptography 13 Ciphertext frequency counts:
• Ciphertext frequency counts:
s below
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
• By comparing these two statistics, we may propose the Part 1 Cryptography 14
following initial relationship: F → E, P → T or A, B → H, I, N, O, R, or S.
• AssignmentF→E,P→TandB→H,resultsin
PBF → THE, so we might have a good start!
Ryszard Janicki
Introduction. Basic Cryptography 18/37
Secure vs Insecure
Cryptosystem is secure if best know attack is to try all keys 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, since the length of keys determines the number of possible cases.
Ryszard Janicki
Introduction. Basic Cryptography 19/37
Double Transposition
Double Transposition
Plaintext: attackxatxdawn Permute rows
andcolumns Ciphertext: xtawxnattxadakc
Key is matrix size and permutations: (3,5,1,4,2) and (1,3,2)
Part 1 Cryptography 16
Ryszard Janicki
Introduction. Basic Cryptography 20/37
Operator ‘XOR’: ⊕
Formally,forallx,y∈{,1}:x⊕y=x+y mod2,i.e: 0⊕0=0
0⊕1=1 1⊕0=1 1⊕1=0
Fundamental property used in cryptography:
(x ⊕ y) ⊕ y = x
Interpretation: x – plaintext, y – key
We will use this operation very often in this course!
Ryszard Janicki
Introduction. Basic Cryptography 21/37
One-Time Pad: Encryption
One-Time Pad: Encryption
e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111
Encryption: Plaintext Key = Ciphertext heilhitler
Plaintext: 001 000 010 100 001 010 111 100 000 101 Key: 111 101 110 101 111 100 000 101 110 000
Ciphertext: 110 101 100 001 110 110 111 001 110 101 srlhssthsr
Part 1 Cryptography 17
Ryszard Janicki
Introduction. Basic Cryptography 22/37
One-Time Pad: Decryption
One-Time Pad: Decryption
e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111
Decryption: Ciphertext Key = Plaintext srlhssthsr
Ciphertext:
Key: 111 101 110 101 111 100 000 101 110 000
Plaintext:
110 101 100 001 110 110 111 001 110 101
001 000 010 100 001 010 111 100 000 101 heilhitler
Part 1 Cryptography 18
Ryszard Janicki
Introduction. Basic Cryptography 23/37
One-Time Pad: Properties I
One-Time Pad
Double agent claims following “key” was used: srlhssthsr
Ciphertext: 110 101 100 001 110 110 111 001 110 101 “key”: 101 111 000 101 111 100 000 101 110 000
“Plaintext”:
011 010 100 100 001 010 111 100 000 101 killhitler
e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111
Part 1 Cryptography
19
Ryszard Janicki
Introduction. Basic Cryptography 24/37
One-Time Pad: Properties II
One-Time Pad
Or claims the key is…
srlhssthsr Ciphertext: 110 101 100 001 110 110 111 001 110 101
“key”: 111 101 000 011 101 110 001 011 101 101
“Plaintext”:
001 000 100 010 011 000 110 010 011 000 helikesike
e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111
Part 1 Cryptography 20
Ryszard Janicki
Introduction. Basic Cryptography 25/37
One-Time Pad Summary
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
Ryszard Janicki
Introduction. Basic Cryptography 26/37
Real-World One-Time Pad
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
Ryszard Janicki
Introduction. Basic Cryptography 27/37
Codebook Cipher
Codebook Cipher
Literally, a book filled with “codewords”
Zimmerman Telegram encrypted via codebook
Februar
fest finanzielle folgender Frieden Friedenschluss
13605 13732 13850 13918 17142 17149
::
Modern block ciphers are codebooks!
More about this later…
Part 1 Cryptography 24
Ryszard Janicki
Introduction. Basic Cryptography 28/37
Zimmerman Telegram
Perhaps most famous codebook ciphertext ever A major factor in U.S. entry into World War I British had recovered partial codebook
Then able to fill in missing parts
Ryszard Janicki
Introduction. Basic Cryptography 29/37
Zimmerman Telegram
ZiCmiphmertextrman Plaintext
Telegram Decrypted
British had recovered partial codebook
Then able to fill in missing parts
Part 1 Cryptography 26
27
Ryszard Janicki
Introduction. Basic Cryptography 30/37
Codebook Cipher: Additive
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
Ryszard Janicki
Introduction. Basic Cryptography 31/37
Vigen`ere Cipher
Invented by Blaise de Vigen`ere in 1586.
Definition
The Vigen`ere cipher chooses a sequence of keys, represented by a string. The key letters are applied to successive plaintext characters, and when the end of the key is reached, the key starts over. The length of the key is called the period of the cipher.
In other words, like Caesar cipher, but we use a phrase. The next page shows a tableau to implement this cipher
efficiently.
Because this requires several different key letters, this type of cipher is called polyalphabetic.
Ryszard Janicki
Introduction. Basic Cryptography 32/37
The Vigen`ere Tableau
Ryszard Janicki
Introduction. Basic Cryptography 33/37
Vigen`ere Cipher
Example
Letters enumeration:
A → 0,…,G → 6,…,I → 8,…,V → 21,…,Z → 25.
Message: THE BOY HAS THE BALL Key: VIG or 21-8-6.
We encipher using Caesar cipher for each letter:
Plaintext THEBOYHASTHEBALL Keys VIGVIGVIGVIGVIGV Ciphertext O P K W W E C I Y O P K W I M G,
since(T+V) mod26=O,(H+I) mod26=P, (E+G) mod26=K,etc.
Ryszard Janicki
Introduction. Basic Cryptography 34/37
Vigen`ere Cipher
Breaking is not easy but possible (Friedrich Kasiski in 1863). Breaking is based on the observation, that repetitions occur
when characters of the key appear over the same characters in the ciphertext.
One-Time Pad is a Vigen`ere cipher with a random key at least as long as the message.
Example
Plaintext THEBOYHASTHEBALL Keys VIGVIGVIGVIGVIGV Ciphertext O P K W W E C I Y O P K W I M G,
The string OPK appears twice. The ciphertext repetitions are nine character apart. Hence 9 is a multiple of the period, i.e. period must be either 3 or 9.
We can then use some statistical analysis to break the cipher, however it is not easy.
Ryszard Janicki
Introduction. Basic Cryptography 35/37
Taxonomy of Cryptography
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
Ryszard Janicki
36
Introduction. Basic Cryptography 36/37
Claude Shannon
The founder of Information Theory Confusion and Diffusion
1T9h4e9fpoaupnedre:rCoofmImnf.oTrhmya.toiof nSeTchreocyrySystems F19u4nd9apmaepnetra:lCcomncme.pTtshy. of Secrecy Systems
o Confusion obscure relationship between Fundamental concepts
plaintext and ciphertext
o Confusion obscure relationship between
o Diffusion spread plaintext statistics through plaintext and ciphertext
the ciphertext
o Diffusion spread plaintext statistics through
Protvhedcipohner-tteixmte pad is secure
OPrnoev-etdimoenep-atdimise cpoandfuisisoenc-uornely, while double transposition is diffusion-only
One-time pad is confusion-only, while double Part 1 Cryptography 35
transposition is diffusion-only
Part 1 Cryptography 35
Ryszard Janicki
Introduction. Basic Cryptography 37/37